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