Visual Servoing Platform version 3.5.0
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
85void 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}
Class that defines a 2D point in an image. This class is useful for image processing and stores only ...
Definition: vpImagePoint.h:88
double get_j() const
Definition: vpImagePoint.h:214
double get_i() const
Definition: vpImagePoint.h:203
unsigned int getWidth() const
Definition: vpImage.h:246
unsigned int getSize() const
Definition: vpImage.h:227
unsigned int getHeight() const
Definition: vpImage.h:188
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