Visual Servoing Platform  version 3.4.1 under development (2021-05-17)
vpFloodFill.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  * Flood fill algorithm.
33  *
34  * Authors:
35  * Souriya Trinh
36  *
37  *****************************************************************************/
38 /*
39  * Copyright (c) 2004-2007, Lode Vandevenne
40  *
41  * All rights reserved.
42  *
43  * Redistribution and use in source and binary forms, with or without
44  * modification, are permitted provided that the following conditions are met:
45  *
46  * * Redistributions of source code must retain the above copyright notice,
47  * this list of conditions and the following disclaimer.
48  * * Redistributions in binary form must reproduce the above copyright
49  * notice, this list of conditions and the following disclaimer in the
50  * documentation and/or other materials provided with the distribution.
51  *
52  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
53  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
54  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
55  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
56  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
57  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
58  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
59  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
60  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
61  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
62  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
63  *
64  */
65 
71 #include <queue>
72 #include <visp3/imgproc/vpImgproc.h>
73 
85 void vp::floodFill(vpImage<unsigned char> &I, const vpImagePoint &seedPoint, const unsigned char oldValue,
86  const unsigned char newValue, const vpImageMorphology::vpConnexityType &connexity)
87 {
88  // Code from Lode Vandevenne tutorial.
89  // Naive modification for 8-connexity implementation
90  if (oldValue == newValue || I.getSize() == 0) {
91  return;
92  }
93 
94  std::queue<vpImagePoint> seed_queue;
95 
96  // Add initial seed point
97  seed_queue.push(seedPoint);
98 
99  while (!seed_queue.empty()) {
100  vpImagePoint current_seed = seed_queue.front();
101  seed_queue.pop();
102 
103  unsigned int x = (unsigned int)current_seed.get_j();
104  unsigned int y = (unsigned int)current_seed.get_i();
105  int x1 = (int)x;
106 
107  // Find most left pixel
108  while (x1 >= 0 && I[y][x1] == oldValue) {
109  x1--;
110  }
111  x1++;
112 
113  bool spanAbove = false, spanBelow = false;
114 
115  while (x1 < (int)I.getWidth() && I[y][x1] == oldValue) {
116  I[y][x1] = newValue;
117 
118  if (!spanAbove && y > 0) {
119  if (I[y - 1][x1] == oldValue) {
120  // North
121  spanAbove = true;
122  seed_queue.push(vpImagePoint(y - 1, x1));
123  }
124 
125  if (connexity != vpImageMorphology::CONNEXITY_4) {
126  if (x1 > 0 && I[y - 1][x1 - 1] == oldValue) {
127  // North west
128  spanAbove = true;
129  seed_queue.push(vpImagePoint(y - 1, x1 - 1));
130  }
131  if (x1 < (int)I.getWidth() - 1 && I[y - 1][x1 + 1] == oldValue) {
132  // North east
133  spanAbove = true;
134  seed_queue.push(vpImagePoint(y - 1, x1 + 1));
135  }
136  }
137  } else if (spanAbove && y > 0 && I[y - 1][x1] != oldValue) {
138  spanAbove = false;
139  }
140 
141  if (!spanBelow && y < I.getHeight() - 1) {
142  if (I[y + 1][x1] == oldValue) {
143  // South
144  seed_queue.push(vpImagePoint(y + 1, x1));
145  spanBelow = true;
146  }
147 
148  if (connexity != vpImageMorphology::CONNEXITY_4) {
149  if (x1 > 0 && I[y + 1][x1 - 1] == oldValue) {
150  // South west
151  seed_queue.push(vpImagePoint(y + 1, x1 - 1));
152  spanBelow = true;
153  }
154  if (x1 < (int)I.getWidth() - 1 && I[y + 1][x1 + 1] == oldValue) {
155  // South east
156  seed_queue.push(vpImagePoint(y + 1, x1 + 1));
157  spanBelow = true;
158  }
159  }
160  } else if (spanBelow && y < I.getHeight() - 1 && I[y + 1][x1] != oldValue) {
161  spanBelow = false;
162  }
163 
164  // TODO: improve 8-connexity
165  if (connexity != vpImageMorphology::CONNEXITY_4) {
166  spanBelow = false;
167  spanAbove = false;
168  }
169 
170  x1++;
171  }
172  }
173 }
double get_i() const
Definition: vpImagePoint.h:203
double get_j() const
Definition: vpImagePoint.h:214
VISP_EXPORT void floodFill(vpImage< unsigned char > &I, const vpImagePoint &seedPoint, const unsigned char oldValue, const unsigned char newValue, const vpImageMorphology::vpConnexityType &connexity=vpImageMorphology::CONNEXITY_4)
Definition: vpFloodFill.cpp:85
unsigned int getHeight() const
Definition: vpImage.h:188
unsigned int getSize() const
Definition: vpImage.h:227
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
Definition: vpImagePoint.h:87
unsigned int getWidth() const
Definition: vpImage.h:246