1. 首页
  2. 文章中心
  3. Android

Android图像处理之泛洪填充算法

175 阅读 0 评论
我是靠谱客的博主 负责唇膏，这篇文章主要介绍Android图像处理之泛洪填充算法，现在分享给大家，希望可以做个参考。

泛洪填充算法(Flood Fill Algorithm)

泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法，最熟悉不过就是windows paint的油漆桶功能。算法的原理很简单，就是从一个点开始附近像素点，填充成新的颜色，直到封闭区域内的所有像素点都被填充新颜色为止。泛红填充实现最常见有四邻域像素填充法，八邻域像素填充法，基于扫描线的像素填充方法。根据实现又可以分为递归与非递归（基于栈）。

在介绍算法的三种实现方式之前，首先来看一下测试该算法的UI实现。基本思路是选择一张要填充的图片，鼠标点击待填充的区域内部，算法会自动填充该区域，然后UI刷新。完整的UI代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package com.gloomyfish.paint.fill; 
import java.awt.Color; 
import java.awt.Dimension; 
import java.awt.Graphics; 
import java.awt.Graphics2D; 
import java.awt.MediaTracker; 
import java.awt.event.MouseEvent; 
import java.awt.event.MouseListener; 
import java.awt.image.BufferedImage; 
import java.io.File; 
import java.io.IOException; 
import javax.imageio.ImageIO; 
import javax.swing.JComponent; 
import javax.swing.JFileChooser; 
import javax.swing.JFrame; 
public class FloodFillUI extends JComponent implements MouseListener{ 
 /** 
 * 
 */ 
 private static final long serialVersionUID = 1L; 
 private BufferedImage rawImg; 
 private MediaTracker tracker; 
 private Dimension mySize; 
 FloodFillAlgorithm ffa; 
 public FloodFillUI(File f) 
 { 
 try { 
  rawImg = ImageIO.read(f); 
 } catch (IOException e1) { 
  e1.printStackTrace(); 
 } 
 tracker = new MediaTracker(this); 
 tracker.addImage(rawImg, 1); 
 // blocked 10 seconds to load the image data 
 try { 
  if (!tracker.waitForID(1, 10000)) { 
  System.out.println("Load error."); 
  System.exit(1); 
  }// end if 
 } catch (InterruptedException e) { 
  e.printStackTrace(); 
  System.exit(1); 
 }// end catch 
 mySize = new Dimension(300, 300); 
 this.addMouseListener(this); 
 ffa = new FloodFillAlgorithm(rawImg); 
 JFrame imageFrame = new JFrame("Flood File Algorithm Demo - Gloomyfish"); 
 imageFrame.getContentPane().add(this); 
 imageFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
 imageFrame.pack(); 
 imageFrame.setVisible(true); 
 } 
 public void paint(Graphics g) { 
 Graphics2D g2 = (Graphics2D) g; 
 g2.drawImage(rawImg, 10, 10, rawImg.getWidth(), rawImg.getHeight(), null); 
 } 
 public Dimension getPreferredSize() { 
 return mySize; 
 } 
 public Dimension getMinimumSize() { 
 return mySize; 
 } 
 public Dimension getMaximumSize() { 
 return mySize; 
 } 
 public static void main(String[] args) { 
 JFileChooser chooser = new JFileChooser(); 
 chooser.showOpenDialog(null); 
 File f = chooser.getSelectedFile(); 
 new FloodFillUI(f); 
 } 
 @Override 
 public void mouseClicked(MouseEvent e) { 
 System.out.println("Mouse Clicked Event!!"); 
 int x = (int)e.getPoint().getX(); 
 int y = (int)e.getPoint().getY(); 
 System.out.println("mouse location x = " + x); // column 
 System.out.println("mouse location y = " + y); // row 
 System.out.println(); 
 long startTime = System.nanoTime(); 
 // ffa.floodFill4(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y)); 
 // ffa.floodFill8(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y)); 
 // ffa.floodFillScanLine(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y)); // 13439051 
 ffa.floodFillScanLineWithStack(x, y, Color.GREEN.getRGB(), ffa.getColor(x, y)); // - 16660142 
 long endTime = System.nanoTime() - startTime; 
 System.out.println("run time = " + endTime); 
 ffa.updateResult(); 
 this.repaint(); 
 } 
 @Override 
 public void mousePressed(MouseEvent e) { 
 // TODO Auto-generated method stub 
 } 
 @Override 
 public void mouseReleased(MouseEvent e) { 
 // TODO Auto-generated method stub 
 } 
 @Override 
 public void mouseEntered(MouseEvent e) { 
 // TODO Auto-generated method stub 
 } 
 @Override 
 public void mouseExited(MouseEvent e) { 
 // TODO Auto-generated method stub 
 } 
}

首先介绍四邻域的泛洪填充算法，寻找像素点p(x, y)的上下左右四个临近像素点，如果没有被填充，则填充它们，并且继续寻找它们的四邻域像素，直到封闭区域完全被新颜色填充。

蓝色方格为四个邻域像素， p(x, y)为当前像素点。

基于递归实现代码很简单：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
public void floodFill4(int x, int y, int newColor, int oldColor) 
{ 
 if(x >= 0 && x < width && y >= 0 && y < height 
  && getColor(x, y) == oldColor && getColor(x, y) != newColor) 
 { 
 setColor(x, y, newColor); //set color before starting recursion 
 floodFill4(x + 1, y, newColor, oldColor); 
 floodFill4(x - 1, y, newColor, oldColor); 
 floodFill4(x, y + 1, newColor, oldColor); 
 floodFill4(x, y - 1, newColor, oldColor); 
 } 
}

  八邻域的填充算法，则是在四邻域的基础上增加了左上，左下，右上，右下四个相邻像素。

并递归寻找它们的八邻域像素填充，直到区域完全被新颜色填充。

 

蓝色方格为四个邻域像素，黄色为左上，左下，右上，右下四个像素， p(x, y)为当前像素点。

基于递归实现的代码也很简单：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void floodFill8(int x, int y, int newColor, int oldColor) 
{ 
 if(x >= 0 && x < width && y >= 0 && y < height && 
  getColor(x, y) == oldColor && getColor(x, y) != newColor) 
 { 
 setColor(x, y, newColor); //set color before starting recursion 
 floodFill8(x + 1, y, newColor, oldColor); 
 floodFill8(x - 1, y, newColor, oldColor); 
 floodFill8(x, y + 1, newColor, oldColor); 
 floodFill8(x, y - 1, newColor, oldColor); 
 floodFill8(x + 1, y + 1, newColor, oldColor); 
 floodFill8(x - 1, y - 1, newColor, oldColor); 
 floodFill8(x - 1, y + 1, newColor, oldColor); 
 floodFill8(x + 1, y - 1, newColor, oldColor); 
 } 
}

基于扫描线实现的泛洪填充算法的主要思想是根据当前输入的点p(x, y)，沿y方向分别向上

与向下扫描填充，同时向左p(x-1, y)与向右p(x+1, y)递归寻找新的扫描线，直到递归结束。

代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public void floodFillScanLine(int x, int y, int newColor, int oldColor) 
{ 
 if(oldColor == newColor) return; 
 if(getColor(x, y) != oldColor) return; 
 int y1; 
 //draw current scanline from start position to the top 
 y1 = y; 
 while(y1 < height && getColor(x, y1) == oldColor) 
 { 
 setColor(x, y1, newColor); 
 y1++; 
 } 
 //draw current scanline from start position to the bottom 
 y1 = y - 1; 
 while(y1 >= 0 && getColor(x, y1) == oldColor) 
 { 
 setColor(x, y1, newColor); 
 y1--; 
 } 
 //test for new scanlines to the left 
 y1 = y; 
 while(y1 < height && getColor(x, y1) == newColor) 
 { 
 if(x > 0 && getColor(x - 1, y1) == oldColor) 
 { 
  floodFillScanLine(x - 1, y1, newColor, oldColor); 
 } 
 y1++; 
 } 
 y1 = y - 1; 
 while(y1 >= 0 && getColor(x, y1) == newColor) 
 { 
 if(x > 0 && getColor(x - 1, y1) == oldColor) 
 { 
  floodFillScanLine(x - 1, y1, newColor, oldColor); 
 } 
 y1--; 
 } 
 //test for new scanlines to the right 
 y1 = y; 
 while(y1 < height && getColor(x, y1) == newColor) 
 { 
 if(x < width - 1 && getColor(x + 1, y1) == oldColor) 
 {  
  floodFillScanLine(x + 1, y1, newColor, oldColor); 
 } 
 y1++; 
 } 
 y1 = y - 1; 
 while(y1 >= 0 && getColor(x, y1) == newColor) 
 { 
 if(x < width - 1 && getColor(x + 1, y1) == oldColor) 
 { 
  floodFillScanLine(x + 1, y1, newColor, oldColor); 
 } 
 y1--; 
 } 
}

基于递归实现的泛洪填充算法有个致命的缺点，就是对于大的区域填充时可能导致JAVA栈溢出错误，对最后一种基于扫描线的算法，实现了一种非递归的泛洪填充算法。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public void floodFillScanLineWithStack(int x, int y, int newColor, int oldColor) 
{ 
 if(oldColor == newColor) { 
 System.out.println("do nothing !!!, filled area!!"); 
 return; 
 } 
 emptyStack(); 
 int y1; 
 boolean spanLeft, spanRight; 
 push(x, y); 
 while(true) 
 { 
 x = popx(); 
 if(x == -1) return; 
 y = popy(); 
 y1 = y; 
 while(y1 >= 0 && getColor(x, y1) == oldColor) y1--; // go to line top/bottom 
 y1++; // start from line starting point pixel 
 spanLeft = spanRight = false; 
 while(y1 < height && getColor(x, y1) == oldColor) 
 { 
  setColor(x, y1, newColor); 
  if(!spanLeft && x > 0 && getColor(x - 1, y1) == oldColor)// just keep left line once in the stack 
  { 
  push(x - 1, y1); 
  spanLeft = true; 
  } 
  else if(spanLeft && x > 0 && getColor(x - 1, y1) != oldColor) 
  { 
  spanLeft = false; 
  } 
  if(!spanRight && x < width - 1 && getColor(x + 1, y1) == oldColor) // just keep right line once in the stack 
  { 
  push(x + 1, y1); 
  spanRight = true; 
  } 
  else if(spanRight && x < width - 1 && getColor(x + 1, y1) != oldColor) 
  { 
  spanRight = false; 
  } 
  y1++; 
 } 
 } 
 
}

运行效果：

算法类源代码如下：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
package com.gloomyfish.paint.fill; 
import java.awt.image.BufferedImage; 
import com.gloomyfish.filter.study.AbstractBufferedImageOp; 
public class FloodFillAlgorithm extends AbstractBufferedImageOp { 
 private BufferedImage inputImage; 
 private int[] inPixels; 
 private int width; 
 private int height; 
 // stack data structure 
 private int maxStackSize = 500; // will be increased as needed 
 private int[] xstack = new int[maxStackSize]; 
 private int[] ystack = new int[maxStackSize]; 
 private int stackSize; 
 public FloodFillAlgorithm(BufferedImage rawImage) { 
 this.inputImage = rawImage; 
 width = rawImage.getWidth(); 
 height = rawImage.getHeight(); 
 inPixels = new int[width*height]; 
 getRGB(rawImage, 0, 0, width, height, inPixels ); 
 } 
 public BufferedImage getInputImage() { 
 return inputImage; 
 } 
 public void setInputImage(BufferedImage inputImage) { 
 this.inputImage = inputImage; 
 } 
 public int getColor(int x, int y) 
 { 
 int index = y * width + x; 
 return inPixels[index]; 
 } 
 public void setColor(int x, int y, int newColor) 
 { 
 int index = y * width + x; 
 inPixels[index] = newColor; 
 } 
 public void updateResult() 
 { 
 setRGB( inputImage, 0, 0, width, height, inPixels ); 
 } 
 /** 
 * it is very low calculation speed and cause the stack overflow issue when fill 
 * some big area and irregular shape. performance is very bad. 
 * 
 * @param x 
 * @param y 
 * @param newColor 
 * @param oldColor 
 */ 
 public void floodFill4(int x, int y, int newColor, int oldColor) 
 { 
 if(x >= 0 && x < width && y >= 0 && y < height 
  && getColor(x, y) == oldColor && getColor(x, y) != newColor) 
 { 
  setColor(x, y, newColor); //set color before starting recursion 
  floodFill4(x + 1, y, newColor, oldColor); 
  floodFill4(x - 1, y, newColor, oldColor); 
  floodFill4(x, y + 1, newColor, oldColor); 
  floodFill4(x, y - 1, newColor, oldColor); 
 } 
 } 
 /** 
 * 
 * @param x 
 * @param y 
 * @param newColor 
 * @param oldColor 
 */ 
 public void floodFill8(int x, int y, int newColor, int oldColor) 
 { 
 if(x >= 0 && x < width && y >= 0 && y < height && 
  getColor(x, y) == oldColor && getColor(x, y) != newColor) 
 { 
  setColor(x, y, newColor); //set color before starting recursion 
  floodFill8(x + 1, y, newColor, oldColor); 
  floodFill8(x - 1, y, newColor, oldColor); 
  floodFill8(x, y + 1, newColor, oldColor); 
  floodFill8(x, y - 1, newColor, oldColor); 
  floodFill8(x + 1, y + 1, newColor, oldColor); 
  floodFill8(x - 1, y - 1, newColor, oldColor); 
  floodFill8(x - 1, y + 1, newColor, oldColor); 
  floodFill8(x + 1, y - 1, newColor, oldColor); 
 } 
 } 
 /** 
 * 
 * @param x 
 * @param y 
 * @param newColor 
 * @param oldColor 
 */ 
 public void floodFillScanLine(int x, int y, int newColor, int oldColor) 
 { 
 if(oldColor == newColor) return; 
 if(getColor(x, y) != oldColor) return; 
 int y1; 
 //draw current scanline from start position to the top 
 y1 = y; 
 while(y1 < height && getColor(x, y1) == oldColor) 
 { 
  setColor(x, y1, newColor); 
  y1++; 
 } 
 //draw current scanline from start position to the bottom 
 y1 = y - 1; 
 while(y1 >= 0 && getColor(x, y1) == oldColor) 
 { 
  setColor(x, y1, newColor); 
  y1--; 
 } 
 //test for new scanlines to the left 
 y1 = y; 
 while(y1 < height && getColor(x, y1) == newColor) 
 { 
  if(x > 0 && getColor(x - 1, y1) == oldColor) 
  { 
  floodFillScanLine(x - 1, y1, newColor, oldColor); 
  } 
  y1++; 
 } 
 y1 = y - 1; 
 while(y1 >= 0 && getColor(x, y1) == newColor) 
 { 
  if(x > 0 && getColor(x - 1, y1) == oldColor) 
  { 
  floodFillScanLine(x - 1, y1, newColor, oldColor); 
  } 
  y1--; 
 } 
 //test for new scanlines to the right 
 y1 = y; 
 while(y1 < height && getColor(x, y1) == newColor) 
 { 
  if(x < width - 1 && getColor(x + 1, y1) == oldColor) 
  {  
  floodFillScanLine(x + 1, y1, newColor, oldColor); 
  } 
  y1++; 
 } 
 y1 = y - 1; 
 while(y1 >= 0 && getColor(x, y1) == newColor) 
 { 
  if(x < width - 1 && getColor(x + 1, y1) == oldColor) 
  { 
  floodFillScanLine(x + 1, y1, newColor, oldColor); 
  } 
  y1--; 
 } 
 } 
 public void floodFillScanLineWithStack(int x, int y, int newColor, int oldColor) 
 { 
 if(oldColor == newColor) { 
  System.out.println("do nothing !!!, filled area!!"); 
  return; 
 } 
 emptyStack(); 
 int y1; 
 boolean spanLeft, spanRight; 
 push(x, y); 
 while(true) 
 { 
  x = popx(); 
  if(x == -1) return; 
  y = popy(); 
  y1 = y; 
  while(y1 >= 0 && getColor(x, y1) == oldColor) y1--; // go to line top/bottom 
  y1++; // start from line starting point pixel 
  spanLeft = spanRight = false; 
  while(y1 < height && getColor(x, y1) == oldColor) 
  { 
  setColor(x, y1, newColor); 
  if(!spanLeft && x > 0 && getColor(x - 1, y1) == oldColor)// just keep left line once in the stack 
  { 
   push(x - 1, y1); 
   spanLeft = true; 
  } 
  else if(spanLeft && x > 0 && getColor(x - 1, y1) != oldColor) 
  { 
   spanLeft = false; 
  } 
  if(!spanRight && x < width - 1 && getColor(x + 1, y1) == oldColor) // just keep right line once in the stack 
  { 
   push(x + 1, y1); 
   spanRight = true; 
  } 
  else if(spanRight && x < width - 1 && getColor(x + 1, y1) != oldColor) 
  { 
   spanRight = false; 
  } 
  y1++; 
  } 
 } 
 } 
 private void emptyStack() { 
 while(popx() != - 1) { 
  popy(); 
 } 
 stackSize = 0; 
 } 
 final void push(int x, int y) { 
 stackSize++; 
 if (stackSize==maxStackSize) { 
  int[] newXStack = new int[maxStackSize*2]; 
  int[] newYStack = new int[maxStackSize*2]; 
  System.arraycopy(xstack, 0, newXStack, 0, maxStackSize); 
  System.arraycopy(ystack, 0, newYStack, 0, maxStackSize); 
  xstack = newXStack; 
  ystack = newYStack; 
  maxStackSize *= 2; 
 } 
 xstack[stackSize-1] = x; 
 ystack[stackSize-1] = y; 
 } 
 final int popx() { 
 if (stackSize==0) 
  return -1; 
 else 
  return xstack[stackSize-1]; 
 } 
 final int popy() { 
 int value = ystack[stackSize-1]; 
 stackSize--; 
 return value; 
 } 
 @Override 
 public BufferedImage filter(BufferedImage src, BufferedImage dest) { 
 // TODO Auto-generated method stub 
 return null; 
 } 
 
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持靠谱客。

最后

以上就是负责唇膏最近收集整理的关于Android图像处理之泛洪填充算法的全部内容，更多相关Android图像处理之泛洪填充算法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(116)

相关文章

Android不规则图像填充颜色小游戏
Android不规则图像填充颜色小游戏
Kotlin学习笔记之const val与val
Kotlin学习笔记之const val与val
Android不规则封闭区域填充色彩的实例代码
Android不规则封闭区域填充色彩的实例代码
Android实现调用系统分享功能示例的总结
Android实现调用系统分享功能示例的总结
Android图像处理之泛洪填充算法
Android图像处理之泛洪填充算法
Android自定义view实现输入控件
Android自定义view实现输入控件
Android多边形区域递归种子填充算法的示例代码
Android多边形区域递归种子填充算法的示例代码
Android使用Intent.ACTION_SEND分享图片和文字内容的示例代码
Android使用Intent.ACTION_SEND分享图片和文字内容的示例代码

评论列表共有 0 条评论

立即
投稿
返回
顶部