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

泛洪填充算法(Flood Fill Algorithm)

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

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

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)为当前像素点。

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

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)为当前像素点。

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

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)递归寻找新的扫描线,直到递归结束。

代码如下:

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栈溢出错误,对最后一种基于扫描线的算法,实现了一种非递归的泛洪填充算法。

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++;
 }
 } 

} 

运行效果:

算法类源代码如下:

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 Studio使用小技巧:布局预览时填充数据
  • 基于Android中的 AutoCompleteTextView实现自动填充
  • Android矢量图之VectorDrawable类自由填充色彩
  • Android ListView填充数据的方法
  • Android ScrollView无法填充满屏幕的解决办法
  • Android图片等比例缩放和填充屏幕效果
  • Android不规则图像填充颜色小游戏
  • Android多边形区域递归种子填充算法
  • Android不规则封闭区域填充色彩的实例代码
  • Android扫描线种子填充算法的示例
(0)

相关推荐

  • Android不规则封闭区域填充色彩的实例代码

    一.概述 在上一篇的叙述中,我们通过图层的方式完成了图片颜色的填充(详情请戳:Android不规则图像填充颜色小游戏),不过在着色游戏中更多的还是基于边界的图像的填充.本篇博客将详细描述. 图像的填充有2种经典算法. 一种是种子填充法. 种子填充法理论上能够填充任意区域和图形,但是这种算法存在大量的反复入栈和大规模的递归,降低了填充效率. 另一种是扫描线填充法. 注意:实际上图像填充的算法还是很多的,有兴趣可以去Google学术上去搜一搜. ok,下面先看看今天的效果图: ok,可以看到这样的颜

  • Android多边形区域扫描线种子填充算法的示例

    1.3扫描线种子填充算法 1.1和1.2节介绍的两种种子填充算法的优点是非常简单,缺点是使用了递归算法,这不但需要大量栈空间来存储相邻的点,而且效率不高.为了减少算法中的递归调用,节省栈空间的使用,人们提出了很多改进算法,其中一种就是扫描线种子填充算法.扫描线种子填充算法不再采用递归的方式处理"4-联通"和"8-联通"的相邻点,而是通过沿水平扫描线填充像素段,一段一段地来处理"4-联通"和"8-联通"的相邻点.这样算法处理过程

  • 基于Android中的 AutoCompleteTextView实现自动填充

    现在我们上网会用百度或者谷歌搜索信息,当我们在输入框里输入一两个字后,就会自动提示我们想要的信息,这种效果在Android 是通过Android 的AutoCompleteTextView Widget 搭配ArrayAdapter 设计同类似Google 搜索提示的效果. 先在Layout 当中布局一个AutoCompleteTextView Widget ,然后通过预先设置好的字符串数组,将此字符串数组放入ArrayAdapter ,最后利用AutoCompleteTextView.setA

  • Android ScrollView无法填充满屏幕的解决办法

    Android ScrollView无法填充满屏幕的解决办法 ScrollView滚动视图是指当拥有很多内容.屏幕显示不完时.需要通过滚动跳来显示的视图.Scrollview的一般用法如下 以下代码在Scrollview里面放了一个RelativeLayout.并且是设置为Android:layout_height="match_parent"填充全屏的和RelativeLayout里面放置了一个TextView背景设为了一张图片.按照代码理解.图片应该是居于屏幕的最下方的 <S

  • Android多边形区域递归种子填充算法的示例代码

    平面区域填充算法是计算机图形学领域的一个很重要的算法,区域填充即给出一个区域的边界(也可以是没有边界,只是给出指定颜色),要求将边界范围内的所有象素单元都修改成指定的颜色(也可能是图案填充).区域填充中最常用的是多边形填色,本文中我们就讨论几种多边形区域填充算法. 一.种子填充算法(Seed Filling) 如果要填充的区域是以图像元数据方式给出的,通常使用种子填充算法(Seed Filling)进行区域填充.种子填充算法需要给出图像数据的区域,以及区域内的一个点,这种算法比较适合人机交互方式

  • Android矢量图之VectorDrawable类自由填充色彩

    2014年6月26日的I/O 2014开发者大会上谷歌正式推出了Android L,它带来了全新的设计语言Material Design,新的API也提供了这个类VectorDrawable .也就是android支持SVG类型的资源也就是矢量图.想到矢量图,自然就会想到位图,何为矢量图,何为位图?先来说说位图吧,我们经常用的png,jpg就是位图了,他是由一个单元一个单元的像素组成的.当小icon遇到大屏幕手机的时候,icon如果被撑开那就是马赛克一样啦.这可不是我们想要的.而矢量图正式和它相

  • Android Studio使用小技巧:布局预览时填充数据

    我们都知道Android Studio用起来很棒,其中布局预览更棒.我们在调UI的时候基本是需要实时预览来看效果的,在Android Studio中只需要切换到Design就可以看到,而且我们需要在布局上填充数据预览效果更好,比如我们在TextView中设定text属性来看下字体大小与布局是否正确,但是呢正式环境我们又需要移除这些额外的数据,不然看着很不舒服,这个时候就用到了本篇博客介绍的一个技巧. 废话不多说,直接上图: 上述示例中只需要在xml布局文件中添加tools命名空间的text属性就

  • Android ListView填充数据的方法

    Android ListView填充数据的方法 因为多人开发,为了是自己开发的模块方便融合到主框架中,同时也为了减小apk的大小,要求尽可能少的使用xml的布局文件,开发中需要在ListView中显示数据,网上查到的几乎所有的示例,都是通过xml文件来为ListView的Item提供布局样式,甚是不方便. 能不能将自己通过代码创建的布局(如View,LinearLayout)等动态的布局到ListView呢?当然可以. 为了给ListView提供数据,我们需要为其设置一个适配,我们可以从Base

  • Android图片等比例缩放和填充屏幕效果

    本文实例为大家分享了Android图片等比例缩放和填充屏幕的具体代码,供大家参考,具体内容如下 第一种方法:在ImageView的t同事设置两个属性 android:adjustViewBounds="true" android:scaleType="fitXY 第二中方法:用IamgeView的 android:scaleType  设置属性的时候  填充屏幕出现的各种问题 /** * 将图片等比例缩放 setAdjustViewBounds setMaxWidth set

  • Android不规则图像填充颜色小游戏

    一.概述 近期群里偶然看到一哥们在群里聊不规则图像填充什么四联通.八联通什么的,就本身好学务实的态度去查阅了相关资料.对于这类着色的资料,最好的就是去搜索些相关app,根据我的观察呢,不规则图像填充在着色游戏里面应用居多,不过大致可以分为两种: 基于层的的填充 基于边界的填充 那么针对上述两种,我们会通过两篇博文来讲解,本篇就是叙述基于层的填充方式,那么什么基于层的填充方式呢?其实就是一张图实际上是由多个层组成的,每个层显示部分图像(无图像部分为透明),多层叠加后形成一张完整的图案,图层间是叠加

随机推荐