Visual Servoing Platform version 3.6.0
Loading...
Searching...
No Matches
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
42namespace
43{
44void 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
84void 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
105namespace vp
106{
107void 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 ...
double get_j() const
double get_i() const
Definition of the vpImage class member functions.
Definition vpImage.h:135
unsigned int getWidth() const
Definition vpImage.h:242
void resize(unsigned int h, unsigned int w)
resize the image : Image initialization
Definition vpImage.h:795
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)