Visual Servoing Platform  version 3.4.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 
78 namespace
79 {
80 bool 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 
113 bool 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 
132 void 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 
147 void 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 
215 bool 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 
220 bool 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 
225 void 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 
250 void 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 
275 void 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 
300 void 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
332  vpContour *root = new vpContour(vp::CONTOUR_HOLE);
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) {
360  case vp::CONTOUR_OUTER:
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) {
385  case vp::CONTOUR_OUTER:
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 }
double get_i() const
Definition: vpImagePoint.h:203
unsigned int getWidth() const
Definition: vpImage.h:246
unsigned char B
Blue component.
Definition: vpRGBa.h:150
Type * bitmap
points toward the bitmap
Definition: vpImage.h:143
vpContour * m_parent
Definition: vpContours.h:174
Class to define RGB colors available for display functionnalities.
Definition: vpColor.h:157
std::vector< vpImagePoint > m_points
Definition: vpContours.h:175
error that can be emited by ViSP classes.
Definition: vpException.h:71
std::vector< vpContour * > m_children
Definition: vpContours.h:172
unsigned char G
Green component.
Definition: vpRGBa.h:149
double get_j() const
Definition: vpImagePoint.h:214
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
Definition: vpRGBa.h:66
unsigned int getSize() const
Definition: vpImage.h:227
vpContourType m_contourType
Definition: vpContours.h:173
VISP_EXPORT void drawContours(vpImage< unsigned char > &I, const std::vector< std::vector< vpImagePoint > > &contours, unsigned char grayValue=255)
Definition: vpContours.cpp:250
void set_j(double jj)
Definition: vpImagePoint.h:177
void setParent(vpContour *parent)
Definition: vpContours.h:234
unsigned char R
Red component.
Definition: vpRGBa.h:148
vpContourRetrievalType
Definition: vpContours.h:164
unsigned int getHeight() const
Definition: vpImage.h:188
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
Definition: vpImagePoint.h:87
Definition of the vpImage class member functions.
Definition: vpImage.h:126