Visual Servoing Platform  version 3.6.1 under development (2024-02-13)
vpConnectedComponents.cpp
1 /*
2  * ViSP, open source Visual Servoing Platform software.
3  * Copyright (C) 2005 - 2023 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
43 {
44 void getNeighbors(const vpImage<unsigned char> &I, std::queue<vpImagePoint> &listOfNeighbors, unsigned int i,
45  unsigned int j, const vpImageMorphology::vpConnexityType &connexity)
46 {
47  unsigned char currValue = I[i][j];
48 
49  if (connexity == vpImageMorphology::CONNEXITY_4) {
50  // Top
51  if (I[i - 1][j] == currValue) {
52  listOfNeighbors.push(vpImagePoint(i - 1, j));
53  }
54 
55  // Left
56  if (I[i][j - 1] == currValue) {
57  listOfNeighbors.push(vpImagePoint(i, j - 1));
58  }
59 
60  // Right
61  if (I[i][j + 1] == currValue) {
62  listOfNeighbors.push(vpImagePoint(i, j + 1));
63  }
64 
65  // Bottom
66  if (I[i + 1][j] == currValue) {
67  listOfNeighbors.push(vpImagePoint(i + 1, j));
68  }
69  }
70  else {
71  for (int cpt1 = -1; cpt1 <= 1; cpt1++) {
72  for (int cpt2 = -1; cpt2 <= 1; cpt2++) {
73  // Everything except the current position
74  if (cpt1 != 0 || cpt2 != 0) {
75  if (I[(int)i + cpt1][(int)j + cpt2] == currValue) {
76  listOfNeighbors.push(vpImagePoint((int)i + cpt1, (int)j + cpt2));
77  }
78  }
79  }
80  }
81  }
82 }
83 
84 void visitNeighbors(vpImage<unsigned char> &I_copy, std::queue<vpImagePoint> &listOfNeighbors, vpImage<int> &labels,
85  int current_label, const vpImageMorphology::vpConnexityType &connexity)
86 {
87  // Visit the neighbors
88  while (!listOfNeighbors.empty()) {
89  vpImagePoint imPt = listOfNeighbors.front();
90  unsigned int i = (unsigned int)imPt.get_i();
91  unsigned int j = (unsigned int)imPt.get_j();
92  listOfNeighbors.pop();
93 
94  if (I_copy[i][j]) {
95  getNeighbors(I_copy, listOfNeighbors, i, j, connexity);
96 
97  // Reset current position and set label
98  I_copy[i][j] = 0;
99  labels[i][j] = current_label;
100  }
101  }
102 }
103 } // namespace
104 
105 namespace vp
106 {
107 void connectedComponents(const vpImage<unsigned char> &I, vpImage<int> &labels, int &nbComponents, const vpImageMorphology::vpConnexityType &connexity)
108 {
109  if (I.getSize() == 0) {
110  return;
111  }
112 
113  labels.resize(I.getHeight(), I.getWidth());
114 
115  vpImage<unsigned char> I_copy(I.getHeight() + 2, I.getWidth() + 2);
116  // Copy and add border
117  for (unsigned int i = 0; i < I_copy.getHeight(); i++) {
118  if (i == 0 || i == I_copy.getHeight() - 1) {
119  memset(I_copy[i], 0, sizeof(unsigned char) * I_copy.getWidth());
120  }
121  else {
122  I_copy[i][0] = 0;
123  memcpy(I_copy[i] + 1, I[i - 1], sizeof(unsigned char) * I.getWidth());
124  I_copy[i][I_copy.getWidth() - 1] = 0;
125  }
126  }
127 
128  vpImage<int> labels_copy(I.getHeight() + 2, I.getWidth() + 2, 0);
129 
130  int current_label = 1;
131  std::queue<vpImagePoint> listOfNeighbors;
132 
133  for (unsigned int cpt1 = 0; cpt1 < I.getHeight(); cpt1++) {
134  unsigned int i = cpt1 + 1;
135 
136  for (unsigned int cpt2 = 0; cpt2 < I.getWidth(); cpt2++) {
137  unsigned int j = cpt2 + 1;
138 
139  if (I_copy[i][j] && labels_copy[i][j] == 0) {
140  // Get all the neighbors relative to the current position
141  getNeighbors(I_copy, listOfNeighbors, i, j, connexity);
142 
143  // Reset current position and set label
144  I_copy[i][j] = 0;
145  labels_copy[i][j] = current_label;
146 
147  visitNeighbors(I_copy, listOfNeighbors, labels_copy, current_label, connexity);
148 
149  // Increment label
150  current_label++;
151  }
152  }
153  }
154 
155  for (unsigned int i = 0; i < labels.getHeight(); i++) {
156  memcpy(labels[i], labels_copy[i + 1] + 1, sizeof(int) * labels.getWidth());
157  }
158 
159  nbComponents = current_label - 1;
160 }
161 };
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:780
unsigned int getSize() const
Definition: vpImage.h:223
unsigned int getHeight() const
Definition: vpImage.h:184
VISP_EXPORT void connectedComponents(const vpImage< unsigned char > &I, vpImage< int > &labels, int &nbComponents, const vpImageMorphology::vpConnexityType &connexity=vpImageMorphology::CONNEXITY_4)