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