Visual Servoing Platform version 3.5.0
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
47namespace
48{
49void getNeighbors(const vpImage<unsigned char> &I, std::queue<vpImagePoint> &listOfNeighbors, unsigned int i,
50 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
88void visitNeighbors(vpImage<unsigned char> &I_copy, std::queue<vpImagePoint> &listOfNeighbors, vpImage<int> &labels,
89 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
119void 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}
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
Definition: vpImagePoint.h:88
double get_j() const
Definition: vpImagePoint.h:214
double get_i() const
Definition: vpImagePoint.h:203
unsigned int getWidth() const
Definition: vpImage.h:246
void resize(unsigned int h, unsigned int w)
resize the image : Image initialization
Definition: vpImage.h:800
unsigned int getSize() const
Definition: vpImage.h:227
unsigned int getHeight() const
Definition: vpImage.h:188
VISP_EXPORT void connectedComponents(const vpImage< unsigned char > &I, vpImage< int > &labels, int &nbComponents, const vpImageMorphology::vpConnexityType &connexity=vpImageMorphology::CONNEXITY_4)