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