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