Visual Servoing Platform  version 3.6.1 under development (2024-04-18)
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[static_cast<int>(direction.m_direction)];
123 
124  if ((point.get_i() < 0) || (point.get_j() < 0)) {
125  return false;
126  }
127 
128  unsigned int i = static_cast<unsigned int>(point.get_i());
129  unsigned int j = static_cast<unsigned int>(point.get_j());
130 
131  return (I[i][j] != 0) && ((static_cast<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 = static_cast<unsigned int>(point.get_i());
139  unsigned int j = static_cast<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  // --comment: 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[static_cast<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) && (level < std::numeric_limits<int>::max())) {
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 = static_cast<unsigned int>(it2->get_i());
255  unsigned int j = static_cast<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 = static_cast<unsigned int>(it2->get_i());
270  unsigned int j = static_cast<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 
289  unsigned int i_height = I.getHeight();
290  unsigned int i_width = I.getWidth();
291  unsigned int i_original_width = I_original.getWidth();
292 
293  for (unsigned int i = 0; i < i_height; ++i) {
294  if ((i == 0) || (i == (i_height - 1))) {
295  memset(I.bitmap, 0, sizeof(int) * i_width);
296  }
297  else {
298  I[i][0] = 0;
299  for (unsigned int j = 0; j < i_original_width; ++j) {
300  I[i][j + 1] = I_original[i - 1][j];
301  }
302  I[i][i_width - 1] = 0;
303  }
304  }
305 
306  // Ref: http://openimaj.org/
307  // Ref: Satoshi Suzuki and others. Topological structural analysis of
308  // digitized binary images by border following.
309  int nbd = 1; // Newest border
310  int lnbd = 1; // Last newest border
311 
312  // Background contour
313  // By default the root contour is a hole contour
314  vpContour *root = new vpContour(vp::CONTOUR_HOLE);
315 
316  std::map<int, vpContour *> borderMap;
317  borderMap[lnbd] = root;
318 
319  for (unsigned int i = 0; i < i_height; ++i) {
320  lnbd = 1; // Reset LNBD at the beginning of each scan row
321 
322  for (unsigned int j = 0; j < i_width; ++j) {
323  int fji = I[i][j];
324 
325  bool isOuter = isOuterBorderStart(I, i, j);
326  bool isHole = isHoleBorderStart(I, i, j);
327 
328  if (isOuter || isHole) { // else (1) (c)
329  vpContour *border = new vpContour;
330  vpContour *borderPrime = nullptr;
331  vpImagePoint from(i, j);
332 
333  if (isOuter) {
334  //(1) (a)
335  nbd++;
336  from.set_j(from.get_j() - 1);
338  borderPrime = borderMap[lnbd];
339 
340  // Table 1
341  switch (borderPrime->m_contourType) {
342  case vp::CONTOUR_OUTER:
343  border->setParent(borderPrime->m_parent);
344  break;
345 
346  case vp::CONTOUR_HOLE:
347  border->setParent(borderPrime);
348  break;
349 
350  default:
351  break;
352  }
353  }
354  else {
355  //(1) (b)
356  nbd++;
357 
358  if (fji > 1) {
359  lnbd = fji;
360  }
361 
362  borderPrime = borderMap[lnbd];
363  from.set_j(from.get_j() + 1);
365 
366  // Table 1
367  switch (borderPrime->m_contourType) {
368  case vp::CONTOUR_OUTER:
369  border->setParent(borderPrime);
370  break;
371 
372  case vp::CONTOUR_HOLE:
373  border->setParent(borderPrime->m_parent);
374  break;
375 
376  default:
377  break;
378  }
379  }
380 
381  vpImagePoint ij(i, j);
382  followBorder(I, ij, from, border, nbd);
383 
384  //(3) (1) ; single pixel contour
385  if (border->m_points.empty()) {
386  border->m_points.push_back(vpImagePoint(ij.get_i() - 1, ij.get_j() - 1)); // remove 1-pixel padding
387  I[i][j] = -nbd;
388  }
389 
390  if ((retrievalMode == CONTOUR_RETR_LIST) || (retrievalMode == CONTOUR_RETR_TREE)) {
391  // Add contour points
392  contourPts.push_back(border->m_points);
393  }
394 
395  borderMap[nbd] = border;
396  }
397 
398  //(4)
399  if ((fji != 0) && (fji != 1)) {
400  lnbd = std::abs(fji);
401  }
402  }
403  }
404 
405  if ((retrievalMode == CONTOUR_RETR_EXTERNAL) || (retrievalMode == CONTOUR_RETR_LIST)) {
406  // Delete contours content
407  contours.m_parent = nullptr;
408 
409  for (std::vector<vpContour *>::iterator it = contours.m_children.begin(); it != contours.m_children.end(); ++it) {
410  (*it)->m_parent = nullptr;
411  if (*it != nullptr) {
412  delete *it;
413  *it = nullptr;
414  }
415  }
416 
417  contours.m_children.clear();
418  }
419 
420  if (retrievalMode == CONTOUR_RETR_EXTERNAL) {
421  // Add only external contours
422  for (std::vector<vpContour *>::const_iterator it = root->m_children.begin(); it != root->m_children.end(); ++it) {
423  // Save children
424  std::vector<vpContour *> children_copy = (*it)->m_children;
425  // Erase children
426  (*it)->m_children.clear();
427  // Copy contour
428  contours.m_children.push_back(new vpContour(**it));
429  // Restore children
430  (*it)->m_children = children_copy;
431  // Set parent to children
432  size_t contours_m_children_size = contours.m_children.size();
433  for (size_t i = 0; i < contours_m_children_size; ++i) {
434  contours.m_children[i]->m_parent = &contours;
435  }
436  contourPts.push_back((*it)->m_points);
437  }
438  }
439  else if (retrievalMode == CONTOUR_RETR_LIST) {
440  getContoursList(*root, 0, contours);
441 
442  // Set parent to root
443  for (std::vector<vpContour *>::iterator it = contours.m_children.begin(); it != contours.m_children.end(); ++it) {
444  (*it)->m_parent = &contours;
445  }
446  }
447  else {
448  // CONTOUR_RETR_TREE
449  contours = *root;
450  }
451 
452  delete root;
453  root = nullptr;
454 }
455 };
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:304
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:245
unsigned int getSize() const
Definition: vpImage.h:224
Type * bitmap
points toward the bitmap
Definition: vpImage.h:139
unsigned int getHeight() const
Definition: vpImage.h:184
Definition: vpRGBa.h:61
unsigned char B
Blue component.
Definition: vpRGBa.h:139
unsigned char R
Red component.
Definition: vpRGBa.h:137
unsigned char G
Green component.
Definition: vpRGBa.h:138
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:199
@ CONTOUR_RETR_LIST
Definition: vpContours.h:202
@ CONTOUR_RETR_TREE
Definition: vpContours.h:200
@ CONTOUR_RETR_EXTERNAL
Definition: vpContours.h:203
@ CONTOUR_HOLE
Definition: vpContours.h:192
@ CONTOUR_OUTER
Definition: vpContours.h:191
vpContourType m_contourType
Contour type.
Definition: vpContours.h:214
void setParent(vpContour *parent)
Definition: vpContours.h:296
vpContour * m_parent
Parent contour.
Definition: vpContours.h:216
std::vector< vpImagePoint > m_points
Vector of points belonging to the contour.
Definition: vpContours.h:218
std::vector< vpContour * > m_children
Children contour.
Definition: vpContours.h:212