Visual Servoing Platform  version 3.6.1 under development (2023-12-07)
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 
73 namespace
74 {
75 bool 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 
115 bool 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 
134 void 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 
150 void 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 
218 bool 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 
223 bool 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 
228 void 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 
244 namespace vp
245 {
246 void 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 
261 void 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 
276 void 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
309  vpContour *root = new vpContour(vp::CONTOUR_HOLE);
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 = nullptr;
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) {
337  case vp::CONTOUR_OUTER:
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) {
363  case vp::CONTOUR_OUTER:
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 = nullptr;
403 
404  for (std::vector<vpContour *>::iterator it = contours.m_children.begin(); it != contours.m_children.end(); ++it) {
405  (*it)->m_parent = nullptr;
406  if (*it != nullptr) {
407  delete *it;
408  *it = nullptr;
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 = nullptr;
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 ...
Definition: vpImagePoint.h:82
void set_j(double jj)
Definition: vpImagePoint.h:294
double get_j() const
Definition: vpImagePoint.h:125
double get_i() const
Definition: vpImagePoint.h:114
Definition of the vpImage class member functions.
Definition: vpImage.h:69
unsigned int getWidth() const
Definition: vpImage.h:240
unsigned int getSize() const
Definition: vpImage.h:221
Type * bitmap
points toward the bitmap
Definition: vpImage.h:139
unsigned int getHeight() const
Definition: vpImage.h:182
Definition: vpRGBa.h:61
unsigned char B
Blue component.
Definition: vpRGBa.h:137
unsigned char R
Red component.
Definition: vpRGBa.h:135
unsigned char G
Green component.
Definition: vpRGBa.h:136
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:276
VISP_EXPORT void drawContours(vpImage< unsigned char > &I, const std::vector< std::vector< vpImagePoint > > &contours, unsigned char grayValue=255)
Definition: vpContours.cpp:246
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