Visual Servoing Platform  version 3.6.1 under development (2024-10-13)
vpConnectedComponents.cpp
1 /*
2  * ViSP, open source Visual Servoing Platform software.
3  * Copyright (C) 2005 - 2024 by Inria. All rights reserved.
4  *
5  * This software is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  * See the file LICENSE.txt at the root directory of this source
10  * distribution for additional information about the GNU GPL.
11  *
12  * For using ViSP with software that can not be combined with the GNU
13  * GPL, please contact Inria about acquiring a ViSP Professional
14  * Edition License.
15  *
16  * See https://visp.inria.fr for more information.
17  *
18  * This software was developed at:
19  * Inria Rennes - Bretagne Atlantique
20  * Campus Universitaire de Beaulieu
21  * 35042 Rennes Cedex
22  * France
23  *
24  * If you have questions regarding the use of this file, please contact
25  * Inria at visp@inria.fr
26  *
27  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
28  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
29  *
30  * Description:
31  * Connected components.
32  */
33 
39 #include <queue>
40 #include <visp3/imgproc/vpImgproc.h>
41 
42 namespace VISP_NAMESPACE_NAME
43 {
44 
45 void getNeighbors(const vpImage<unsigned char> &I, std::queue<vpImagePoint> &listOfNeighbors, unsigned int i,
46  unsigned int j, const vpImageMorphology::vpConnexityType &connexity)
47 {
48  unsigned char currValue = I[i][j];
49 
50  if (connexity == vpImageMorphology::CONNEXITY_4) {
51  // Top
52  if (I[i - 1][j] == currValue) {
53  listOfNeighbors.push(vpImagePoint(i - 1, j));
54  }
55 
56  // Left
57  if (I[i][j - 1] == currValue) {
58  listOfNeighbors.push(vpImagePoint(i, j - 1));
59  }
60 
61  // Right
62  if (I[i][j + 1] == currValue) {
63  listOfNeighbors.push(vpImagePoint(i, j + 1));
64  }
65 
66  // Bottom
67  if (I[i + 1][j] == currValue) {
68  listOfNeighbors.push(vpImagePoint(i + 1, j));
69  }
70  }
71  else {
72  for (int cpt1 = -1; cpt1 <= 1; ++cpt1) {
73  for (int cpt2 = -1; cpt2 <= 1; ++cpt2) {
74  // Everything except the current position
75  if ((cpt1 != 0) || (cpt2 != 0)) {
76  if (I[static_cast<int>(i) + cpt1][static_cast<int>(j) + cpt2] == currValue) {
77  listOfNeighbors.push(vpImagePoint(static_cast<int>(i) + cpt1, static_cast<int>(j) + cpt2));
78  }
79  }
80  }
81  }
82  }
83 }
84 
85 void visitNeighbors(vpImage<unsigned char> &I_copy, std::queue<vpImagePoint> &listOfNeighbors, vpImage<int> &labels,
86  int current_label, const vpImageMorphology::vpConnexityType &connexity)
87 {
88  // Visit the neighbors
89  while (!listOfNeighbors.empty()) {
90  vpImagePoint imPt = listOfNeighbors.front();
91  unsigned int i = static_cast<unsigned int>(imPt.get_i());
92  unsigned int j = static_cast<unsigned int>(imPt.get_j());
93  listOfNeighbors.pop();
94 
95  if (I_copy[i][j]) {
96  getNeighbors(I_copy, listOfNeighbors, i, j, connexity);
97 
98  // Reset current position and set label
99  I_copy[i][j] = 0;
100  labels[i][j] = current_label;
101  }
102  }
103 }
104 
105 void connectedComponents(const vpImage<unsigned char> &I, vpImage<int> &labels, int &nbComponents, const vpImageMorphology::vpConnexityType &connexity)
106 {
107  if (I.getSize() == 0) {
108  return;
109  }
110 
111  labels.resize(I.getHeight(), I.getWidth());
112 
113  vpImage<unsigned char> I_copy(I.getHeight() + 2, I.getWidth() + 2);
114  // Copy and add border
115  unsigned int i_copy_height = I_copy.getHeight();
116  for (unsigned int i = 0; i < i_copy_height; ++i) {
117  if ((i == 0) || (i == (I_copy.getHeight() - 1))) {
118  memset(I_copy[i], 0, sizeof(unsigned char) * I_copy.getWidth());
119  }
120  else {
121  I_copy[i][0] = 0;
122  memcpy(I_copy[i] + 1, I[i - 1], sizeof(unsigned char) * I.getWidth());
123  I_copy[i][I_copy.getWidth() - 1] = 0;
124  }
125  }
126 
127  vpImage<int> labels_copy(I.getHeight() + 2, I.getWidth() + 2, 0);
128 
129  int current_label = 1;
130  std::queue<vpImagePoint> listOfNeighbors;
131 
132  unsigned int i_height = I.getHeight();
133  for (unsigned int cpt1 = 0; cpt1 < i_height; ++cpt1) {
134  unsigned int i = cpt1 + 1;
135 
136  unsigned int i_width = I.getWidth();
137  for (unsigned int cpt2 = 0; cpt2 < i_width; ++cpt2) {
138  unsigned int j = cpt2 + 1;
139 
140  if (I_copy[i][j] && (labels_copy[i][j] == 0)) {
141  // Get all the neighbors relative to the current position
142  getNeighbors(I_copy, listOfNeighbors, i, j, connexity);
143 
144  // Reset current position and set label
145  I_copy[i][j] = 0;
146  labels_copy[i][j] = current_label;
147 
148  visitNeighbors(I_copy, listOfNeighbors, labels_copy, current_label, connexity);
149 
150  // Increment label
151  ++current_label;
152  }
153  }
154  }
155  unsigned int labels_height = labels.getHeight();
156  for (unsigned int i = 0; i < labels_height; ++i) {
157  memcpy(labels[i], labels_copy[i + 1] + 1, sizeof(int) * labels.getWidth());
158  }
159 
160  nbComponents = current_label - 1;
161 }
162 
163 } // namespace
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
Definition: vpImagePoint.h:82
double get_j() const
Definition: vpImagePoint.h:125
double get_i() const
Definition: vpImagePoint.h:114
unsigned int getWidth() const
Definition: vpImage.h:242
void resize(unsigned int h, unsigned int w)
resize the image : Image initialization
Definition: vpImage.h:542
unsigned int getSize() const
Definition: vpImage.h:221
unsigned int getHeight() const
Definition: vpImage.h:181
VISP_EXPORT void connectedComponents(const VISP_NAMESPACE_ADDRESSING vpImage< unsigned char > &I, VISP_NAMESPACE_ADDRESSING vpImage< int > &labels, int &nbComponents, const VISP_NAMESPACE_ADDRESSING vpImageMorphology::vpConnexityType &connexity=VISP_NAMESPACE_ADDRESSING vpImageMorphology::CONNEXITY_4)
void getNeighbors(const vpImage< unsigned char > &I, std::queue< vpImagePoint > &listOfNeighbors, unsigned int i, unsigned int j, const vpImageMorphology::vpConnexityType &connexity)
void visitNeighbors(vpImage< unsigned char > &I_copy, std::queue< vpImagePoint > &listOfNeighbors, vpImage< int > &labels, int current_label, const vpImageMorphology::vpConnexityType &connexity)