Visual Servoing Platform version 3.6.0
Loading...
Searching...
No Matches
vpContours.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 * Basic contours extraction based on the original work of
32 * Sina Samangooei (ss@ecs.soton.ac.uk).
33 */
70#include <map>
71#include <visp3/imgproc/vpImgproc.h>
72
73namespace
74{
75bool fromTo(const vpImagePoint &from, const vpImagePoint &to, vpDirection &direction)
76{
77 if (from == to) {
78 return false;
79 }
80
81 if (std::fabs(from.get_i() - to.get_i()) < std::numeric_limits<double>::epsilon()) {
82 if (from.get_j() < to.get_j()) {
83 direction.m_direction = EAST;
84 }
85 else {
86 direction.m_direction = WEST;
87 }
88 }
89 else if (from.get_i() < to.get_i()) {
90 if (std::fabs(from.get_j() - to.get_j()) < std::numeric_limits<double>::epsilon()) {
91 direction.m_direction = SOUTH;
92 }
93 else if (from.get_j() < to.get_j()) {
94 direction.m_direction = SOUTH_EAST;
95 }
96 else {
97 direction.m_direction = SOUTH_WEST;
98 }
99 }
100 else {
101 if (std::fabs(from.get_j() - to.get_j()) < std::numeric_limits<double>::epsilon()) {
102 direction.m_direction = NORTH;
103 }
104 else if (from.get_j() < to.get_j()) {
105 direction.m_direction = NORTH_EAST;
106 }
107 else {
108 direction.m_direction = NORTH_WEST;
109 }
110 }
111
112 return true;
113}
114
115bool crossesEastBorder(const vpImage<int> &I, bool checked[8], const vpImagePoint &point)
116{
117 vpDirection direction;
118 if (!fromTo(point, vpImagePoint(point.get_i(), point.get_j() + 1), direction)) {
119 return false;
120 }
121
122 bool b = checked[(int)direction.m_direction];
123
124 if (point.get_i() < 0 || point.get_j() < 0) {
125 return false;
126 }
127
128 unsigned int i = (unsigned int)point.get_i();
129 unsigned int j = (unsigned int)point.get_j();
130
131 return I[i][j] != 0 && ((unsigned int)point.get_j() == I.getWidth() - 1 || b);
132}
133
134void addContourPoint(vpImage<int> &I, vp::vpContour *border, const vpImagePoint &point, bool checked[8], int nbd)
135{
136 border->m_points.push_back(vpImagePoint(point.get_i() - 1, point.get_j() - 1)); // remove 1-pixel padding
137
138 unsigned int i = (unsigned int)point.get_i();
139 unsigned int j = (unsigned int)point.get_j();
140
141 if (crossesEastBorder(I, checked, point)) {
142 I[i][j] = -nbd;
143 }
144 else if (I[i][j] == 1) {
145 // Only set if the pixel has not been visited before (3.4) (b)
146 I[i][j] = nbd;
147 } // Otherwise leave it alone
148}
149
150void followBorder(vpImage<int> &I, const vpImagePoint &ij, vpImagePoint &i2j2, vp::vpContour *border, int nbd)
151{
152 vpDirection dir;
153 if (!fromTo(ij, i2j2, dir)) {
154 throw vpException(vpException::fatalError, "ij == i2j2");
155 }
156
157 vpDirection trace = dir.clockwise();
158 vpImagePoint i1j1(-1, -1);
159
160 // Find i1j1 (3.1)
161 while (trace.m_direction != dir.m_direction) {
162 vpImagePoint activePixel = trace.active(I, ij);
163
164 if (activePixel.get_i() >= 0 && activePixel.get_j() >= 0) {
165 i1j1 = activePixel;
166 break;
167 }
168
169 trace = trace.clockwise();
170 }
171
172 if (i1j1.get_i() < 0 || i1j1.get_j() < 0) {
173 //(3.1) ; single pixel contour
174 return;
175 }
176
177 i2j2 = i1j1;
178 vpImagePoint i3j3 = ij; //(3.2)
179
180 bool checked[8] = { false, false, false, false, false, false, false, false };
181
182 while (true) {
183 if (!fromTo(i3j3, i2j2, dir)) {
184 throw vpException(vpException::fatalError, "i3j3 == i2j2");
185 }
186
187 trace = dir.counterClockwise();
188 vpImagePoint i4j4(-1, -1);
189
190 // Reset checked
191 for (int cpt = 0; cpt < 8; cpt++) {
192 checked[cpt] = false;
193 }
194
195 while (true) {
196 i4j4 = trace.active(I, i3j3); //(3.3)
197 if (i4j4.get_i() >= 0 && i4j4.get_j() >= 0) {
198 break;
199 }
200
201 checked[(int)trace.m_direction] = true;
202 trace = trace.counterClockwise();
203 }
204
205 addContourPoint(I, border, i3j3, checked, nbd);
206
207 if (i4j4 == ij && i3j3 == i1j1) {
208 //(3.5)
209 break;
210 }
211
212 //(3.5)
213 i2j2 = i3j3;
214 i3j3 = i4j4;
215 }
216}
217
218bool isOuterBorderStart(const vpImage<int> &I, unsigned int i, unsigned int j)
219{
220 return (I[i][j] == 1 && (j == 0 || I[i][j - 1] == 0));
221}
222
223bool isHoleBorderStart(const vpImage<int> &I, unsigned int i, unsigned int j)
224{
225 return (I[i][j] >= 1 && (j == I.getWidth() - 1 || I[i][j + 1] == 0));
226}
227
228void getContoursList(const vp::vpContour &root, int level, vp::vpContour &contour_list)
229{
230 if (level > 0) {
231 vp::vpContour *contour_node = new vp::vpContour;
232 contour_node->m_contourType = root.m_contourType;
233 contour_node->m_points = root.m_points;
234
235 contour_list.m_children.push_back(contour_node);
236 }
237
238 for (std::vector<vp::vpContour *>::const_iterator it = root.m_children.begin(); it != root.m_children.end(); ++it) {
239 getContoursList(**it, level + 1, contour_list);
240 }
241}
242} // namespace
243
244namespace vp
245{
246void drawContours(vpImage<unsigned char> &I, const std::vector<std::vector<vpImagePoint> > &contours, unsigned char grayValue)
247{
248 if (I.getSize() == 0) {
249 return;
250 }
251
252 for (std::vector<std::vector<vpImagePoint> >::const_iterator it1 = contours.begin(); it1 != contours.end(); ++it1) {
253 for (std::vector<vpImagePoint>::const_iterator it2 = it1->begin(); it2 != it1->end(); ++it2) {
254 unsigned int i = (unsigned int)it2->get_i();
255 unsigned int j = (unsigned int)it2->get_j();
256 I[i][j] = grayValue;
257 }
258 }
259}
260
261void drawContours(vpImage<vpRGBa> &I, const std::vector<std::vector<vpImagePoint> > &contours, const vpColor &color)
262{
263 if (I.getSize() == 0) {
264 return;
265 }
266
267 for (std::vector<std::vector<vpImagePoint> >::const_iterator it1 = contours.begin(); it1 != contours.end(); ++it1) {
268 for (std::vector<vpImagePoint>::const_iterator it2 = it1->begin(); it2 != it1->end(); ++it2) {
269 unsigned int i = (unsigned int)it2->get_i();
270 unsigned int j = (unsigned int)it2->get_j();
271 I[i][j] = vpRGBa(color.R, color.G, color.B);
272 }
273 }
274}
275
276void findContours(const vpImage<unsigned char> &I_original, vpContour &contours,
277 std::vector<std::vector<vpImagePoint> > &contourPts, const vpContourRetrievalType &retrievalMode)
278{
279 if (I_original.getSize() == 0) {
280 return;
281 }
282
283 // Clear output results
284 contourPts.clear();
285
286 // Copy uchar I_original into int I + padding
287 vpImage<int> I(I_original.getHeight() + 2, I_original.getWidth() + 2);
288 for (unsigned int i = 0; i < I.getHeight(); i++) {
289 if (i == 0 || i == I.getHeight() - 1) {
290 memset(I.bitmap, 0, sizeof(int) * I.getWidth());
291 }
292 else {
293 I[i][0] = 0;
294 for (unsigned int j = 0; j < I_original.getWidth(); j++) {
295 I[i][j + 1] = I_original[i - 1][j];
296 }
297 I[i][I.getWidth() - 1] = 0;
298 }
299 }
300
301 // Ref: http://openimaj.org/
302 // Ref: Satoshi Suzuki and others. Topological structural analysis of
303 // digitized binary images by border following.
304 int nbd = 1; // Newest border
305 int lnbd = 1; // Last newest border
306
307 // Background contour
308 // By default the root contour is a hole contour
310
311 std::map<int, vpContour *> borderMap;
312 borderMap[lnbd] = root;
313
314 for (unsigned int i = 0; i < I.getHeight(); i++) {
315 lnbd = 1; // Reset LNBD at the beginning of each scan row
316
317 for (unsigned int j = 0; j < I.getWidth(); j++) {
318 int fji = I[i][j];
319
320 bool isOuter = isOuterBorderStart(I, i, j);
321 bool isHole = isHoleBorderStart(I, i, j);
322
323 if (isOuter || isHole) { // else (1) (c)
324 vpContour *border = new vpContour;
325 vpContour *borderPrime = NULL;
326 vpImagePoint from(i, j);
327
328 if (isOuter) {
329 //(1) (a)
330 nbd++;
331 from.set_j(from.get_j() - 1);
333 borderPrime = borderMap[lnbd];
334
335 // Table 1
336 switch (borderPrime->m_contourType) {
338 border->setParent(borderPrime->m_parent);
339 break;
340
341 case vp::CONTOUR_HOLE:
342 border->setParent(borderPrime);
343 break;
344
345 default:
346 break;
347 }
348 }
349 else {
350 //(1) (b)
351 nbd++;
352
353 if (fji > 1) {
354 lnbd = fji;
355 }
356
357 borderPrime = borderMap[lnbd];
358 from.set_j(from.get_j() + 1);
360
361 // Table 1
362 switch (borderPrime->m_contourType) {
364 border->setParent(borderPrime);
365 break;
366
367 case vp::CONTOUR_HOLE:
368 border->setParent(borderPrime->m_parent);
369 break;
370
371 default:
372 break;
373 }
374 }
375
376 vpImagePoint ij(i, j);
377 followBorder(I, ij, from, border, nbd);
378
379 //(3) (1) ; single pixel contour
380 if (border->m_points.empty()) {
381 border->m_points.push_back(vpImagePoint(ij.get_i() - 1, ij.get_j() - 1)); // remove 1-pixel padding
382 I[i][j] = -nbd;
383 }
384
385 if (retrievalMode == CONTOUR_RETR_LIST || retrievalMode == CONTOUR_RETR_TREE) {
386 // Add contour points
387 contourPts.push_back(border->m_points);
388 }
389
390 borderMap[nbd] = border;
391 }
392
393 //(4)
394 if (fji != 0 && fji != 1) {
395 lnbd = std::abs(fji);
396 }
397 }
398 }
399
400 if (retrievalMode == CONTOUR_RETR_EXTERNAL || retrievalMode == CONTOUR_RETR_LIST) {
401 // Delete contours content
402 contours.m_parent = NULL;
403
404 for (std::vector<vpContour *>::iterator it = contours.m_children.begin(); it != contours.m_children.end(); ++it) {
405 (*it)->m_parent = NULL;
406 if (*it != NULL) {
407 delete *it;
408 *it = NULL;
409 }
410 }
411
412 contours.m_children.clear();
413 }
414
415 if (retrievalMode == CONTOUR_RETR_EXTERNAL) {
416 // Add only external contours
417 for (std::vector<vpContour *>::const_iterator it = root->m_children.begin(); it != root->m_children.end(); ++it) {
418 // Save children
419 std::vector<vpContour *> children_copy = (*it)->m_children;
420 // Erase children
421 (*it)->m_children.clear();
422 // Copy contour
423 contours.m_children.push_back(new vpContour(**it));
424 // Restore children
425 (*it)->m_children = children_copy;
426 // Set parent to children
427 for (size_t i = 0; i < contours.m_children.size(); i++) {
428 contours.m_children[i]->m_parent = &contours;
429 }
430 contourPts.push_back((*it)->m_points);
431 }
432 }
433 else if (retrievalMode == CONTOUR_RETR_LIST) {
434 getContoursList(*root, 0, contours);
435
436 // Set parent to root
437 for (std::vector<vpContour *>::iterator it = contours.m_children.begin(); it != contours.m_children.end(); ++it) {
438 (*it)->m_parent = &contours;
439 }
440 }
441 else {
442 // CONTOUR_RETR_TREE
443 contours = *root;
444 }
445
446 delete root;
447 root = NULL;
448}
449};
Class to define RGB colors available for display functionalities.
Definition vpColor.h:152
error that can be emitted by ViSP classes.
Definition vpException.h:59
@ fatalError
Fatal error.
Definition vpException.h:84
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
void set_j(double jj)
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
unsigned int getSize() const
Definition vpImage.h:223
Type * bitmap
points toward the bitmap
Definition vpImage.h:139
unsigned int getHeight() const
Definition vpImage.h:184
unsigned char B
Blue component.
Definition vpRGBa.h:140
unsigned char R
Red component.
Definition vpRGBa.h:138
unsigned char G
Green component.
Definition vpRGBa.h:139
VISP_EXPORT void findContours(const vpImage< unsigned char > &I_original, vpContour &contours, std::vector< std::vector< vpImagePoint > > &contourPts, const vpContourRetrievalType &retrievalMode=vp::CONTOUR_RETR_TREE)
VISP_EXPORT void drawContours(vpImage< unsigned char > &I, const std::vector< std::vector< vpImagePoint > > &contours, unsigned char grayValue=255)
vpContourRetrievalType
Definition vpContours.h:197
@ CONTOUR_RETR_LIST
Definition vpContours.h:200
@ CONTOUR_RETR_TREE
Definition vpContours.h:198
@ CONTOUR_RETR_EXTERNAL
Definition vpContours.h:201
@ CONTOUR_HOLE
Definition vpContours.h:190
@ CONTOUR_OUTER
Definition vpContours.h:189
vpContourType m_contourType
Contour type.
Definition vpContours.h:212
void setParent(vpContour *parent)
Definition vpContours.h:294
vpContour * m_parent
Parent contour.
Definition vpContours.h:214
std::vector< vpImagePoint > m_points
Vector of points belonging to the contour.
Definition vpContours.h:216
std::vector< vpContour * > m_children
Children contour.
Definition vpContours.h:210