Visual Servoing Platform version 3.6.0
Loading...
Searching...
No Matches
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
69namespace vp
70{
71void 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 = (unsigned int)current_seed.get_j();
90 unsigned int y = (unsigned int)current_seed.get_i();
91 int x1 = (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 < (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 < (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 < (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 ...
double get_j() const
double get_i() const
Definition of the vpImage class member functions.
Definition vpImage.h:135
unsigned int getWidth() const
Definition vpImage.h:242
unsigned int getSize() const
Definition vpImage.h:223
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)