AI 助理
备案控制台
开发者社区 人工智能 文章 正文

图像处理之泛洪填充算法(Flood Fill Algorithm)

2013-05-10 1479
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 泛洪填充算法(Flood Fill Algorithm) 泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法，最熟悉不过就是 windows paint的油漆桶功能。算法的原理很简单，就是从一个点开始附近像素点，填充成新 的颜色，直到封闭区域内的所有像素点都被填充新颜色为止。

泛洪填充算法(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;
	}

}
转载文章请务必注明
文章标签：
算法
Java
计算机视觉
Go
图形学
Windows
关键词：
算法填充
算法algorithm
图像处理算法
算法图像处理
图像处理算法algorithm
贾志刚
目录
相关文章
aliyun1792367740-35101
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题（C/C++）
【动态规划算法】蓝桥杯填充问题（C/C++）
aliyun1792367740-35101
40 0
opencv学堂
|
5月前
|
算法 计算机视觉
图像处理之积分图应用四（基于局部均值的图像二值化算法）
图像处理之积分图应用四（基于局部均值的图像二值化算法）
opencv学堂
530 0
opencv学堂
|
5月前
|
监控 算法 图计算
图像处理之积分图应用三（基于NCC快速相似度匹配算法）
图像处理之积分图应用三（基于NCC快速相似度匹配算法）
opencv学堂
73 0
BetterBench
|
3月前
|
机器学习/深度学习 算法 网络性能优化
【博士每天一篇文献-算法】A brain-inspired algorithm that mitigates catastrophic forgetting of
本文提出了一种受大脑启发的神经调节辅助信用分配（NACA）算法，该算法通过模拟大脑中的神经调节机制，有效减轻了人工神经网络（ANNs）和脉冲神经网络（SNNs）在学习过程中的灾难性遗忘问题，并具有较低的计算成本。
BetterBench
47 1
Deephub
|
5月前
|
机器学习/深度学习 算法 测试技术
如何应对缺失值带来的分布变化？探索填充缺失值的最佳插补算法
该文探讨了缺失值插补的不同方法，比较了它们恢复数据真实分布的效果。文章指出，处理插补尤其在小样本或复杂数据时是个挑战，需要选择能适应数据分布变化的方法。文中介绍了完全随机缺失（MCAR）、随机缺失（MAR）和非随机缺失（MNAR）三种机制，并以一个简单的例子展示了数据分布变化。文章通过比较均值插补、回归插补和高斯插补，强调了高斯插补在重现数据分布方面更优。评估插补方法时，不应仅依赖于RMSE，而应关注分布预测，使用如能量距离这样的指标。此外，即使在随机缺失情况下，数据分布也可能因模式变化而变化，需要考虑适应这些变化的插补方法。
Deephub
133 2
数据分析螺丝钉
|
5月前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
数据分析螺丝钉
69 5
opencv学堂
|
5月前
|
算法 Java 计算机视觉
图像处理之积分图算法
图像处理之积分图算法
opencv学堂
61 2
opencv学堂
|
5月前
|
资源调度 算法 计算机视觉
图像处理之积分图应用二(快速边缘保留滤波算法)
图像处理之积分图应用二(快速边缘保留滤波算法)
opencv学堂
35 0
opencv学堂
|
5月前
|
算法 BI 计算机视觉
图像处理之积分图应用一(半径无关的快速模糊算法)
图像处理之积分图应用一(半径无关的快速模糊算法)
opencv学堂
42 0
简简单单做算法
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中，通过游戏理论优化动态频谱访问，提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本：Matlab 2022a。完整代码包含详细中文注释和操作视频。
简简单单做算法
33 2

热门文章

最新文章

  • 1
    SEO深度解读之HITS链接分析算法
  • 2
    算法训练 筛选号码
  • 3
    秒懂算法 | 最大网络流的增广路算法
  • 4
    算法学习之C语言基础
  • 5
    泛型KMP算法
  • 6
    [干货]基础机器学习算法
  • 7
    18 回归算法 - Softmax回归 - 信贷审批案例
  • 8
    【算法】算法之美—Fire Net
  • 9
    A* + 弗洛伊德 算法 打造 360 向寻路 - [ActionScript3.0]
  • 10
    MapReduce的模式，算法以及用例
  • 1
    算法：位运算
    33
  • 2
    算法：双指针
    48
  • 3
    基于harris角点和RANSAC算法的图像拼接matlab仿真
    85
  • 4
    m基于遗传优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
    71
  • 5
    深入浅出JVM（十三）之垃圾回收算法细节
    50
  • 6
    深入浅出JVM（十二）之垃圾回收算法
    42
  • 7
    常见的算法排序（2）
    43
  • 8
    数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
    87
  • 9
    数据结构与算法 回溯
    32
  • 10
    数据结构与算法 分治
    35

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    DataWorks智能数据建模全面公测开始啦！