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

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

2013-05-10 1484
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 泛洪填充算法(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
|
2月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题（C/C++）
【动态规划算法】蓝桥杯填充问题（C/C++）
aliyun1792367740-35101
49 0
opencv学堂
|
6月前
|
算法 计算机视觉
图像处理之积分图应用四（基于局部均值的图像二值化算法）
图像处理之积分图应用四（基于局部均值的图像二值化算法）
opencv学堂
547 0
opencv学堂
|
6月前
|
监控 算法 图计算
图像处理之积分图应用三（基于NCC快速相似度匹配算法）
图像处理之积分图应用三（基于NCC快速相似度匹配算法）
opencv学堂
80 0
BetterBench
|
4月前
|
机器学习/深度学习 算法 网络性能优化
【博士每天一篇文献-算法】A brain-inspired algorithm that mitigates catastrophic forgetting of
本文提出了一种受大脑启发的神经调节辅助信用分配（NACA）算法，该算法通过模拟大脑中的神经调节机制，有效减轻了人工神经网络（ANNs）和脉冲神经网络（SNNs）在学习过程中的灾难性遗忘问题，并具有较低的计算成本。
BetterBench
64 1
Deephub
|
6月前
|
机器学习/深度学习 算法 测试技术
如何应对缺失值带来的分布变化？探索填充缺失值的最佳插补算法
该文探讨了缺失值插补的不同方法，比较了它们恢复数据真实分布的效果。文章指出，处理插补尤其在小样本或复杂数据时是个挑战，需要选择能适应数据分布变化的方法。文中介绍了完全随机缺失（MCAR）、随机缺失（MAR）和非随机缺失（MNAR）三种机制，并以一个简单的例子展示了数据分布变化。文章通过比较均值插补、回归插补和高斯插补，强调了高斯插补在重现数据分布方面更优。评估插补方法时，不应仅依赖于RMSE，而应关注分布预测，使用如能量距离这样的指标。此外，即使在随机缺失情况下，数据分布也可能因模式变化而变化，需要考虑适应这些变化的插补方法。
Deephub
174 2
数据分析螺丝钉
|
6月前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
数据分析螺丝钉
87 5
opencv学堂
|
6月前
|
算法 Java 计算机视觉
图像处理之积分图算法
图像处理之积分图算法
opencv学堂
72 2
opencv学堂
|
6月前
|
资源调度 算法 计算机视觉
图像处理之积分图应用二(快速边缘保留滤波算法)
图像处理之积分图应用二(快速边缘保留滤波算法)
opencv学堂
36 0
opencv学堂
|
6月前
|
算法 BI 计算机视觉
图像处理之积分图应用一(半径无关的快速模糊算法)
图像处理之积分图应用一(半径无关的快速模糊算法)
opencv学堂
47 0
软件算法开发
|
8天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法（GA）优化PID控制器参数，通过空间状态方程构建控制对象，自定义GA的选择、交叉、变异过程，以提高PID控制性能。与使用通用GA工具箱相比，此方法更灵活、针对性强。MATLAB2022A环境下测试，展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程，最终通过适应度函数评估并选择了最优PID参数，显著提升了系统响应速度和稳定性。
软件算法开发
51 15

热门文章

最新文章

  • 1
    Flink---13、容错机制（检查点（保存、恢复、算法、配置）、状态一致性、端到端精确一次）
  • 2
    openssl中算法的组织方式
  • 3
    JVM内存模型及垃圾回收算法
  • 4
    【算法研究】Bresenham画线算法
  • 5
    九连环的递归算法（C和C++）
  • 6
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 7
    判断一个数字是否为素数的基于C语言的算法
  • 8
    OpenCV 1 图像分割--分水岭算法代码
  • 9
    希尔排序(shellsort)算法实现
  • 10
    缓存、缓存算法(转)
  • 1
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    111
  • 2
    理解并应用机器学习算法：决策树
    136
  • 3
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    396
  • 4
    【机器学习】为什么K-means算法使用欧式距离度量？
    381
  • 5
    【机器学习】描述K-means算法的步骤
    149
  • 6
    【机器学习】K-means和KNN算法有什么区别？
    622
  • 7
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    49
  • 8
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    53
  • 9
    图搜索算法详解
    128
  • 10
    R语言实现蒙特卡洛模拟算法
    301

    • 相关课程

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

    • 相关电子书

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

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月