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

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

2024-06-07 353
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 图像处理之泛洪填充算法(Flood Fill Algorithm)

泛洪填充算法(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)为当前像素点。

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

1.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);
    }   
}

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


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

20130510011440796.png


蓝色方格为四个邻域像素，黄色为左上，左下，右上，右下四个像素， 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
Windows
关键词：
算法填充
算法algorithm
图像处理算法
算法图像处理
算法flood algorithm
opencv学堂
目录
相关文章
aliyun1792367740-35101
|
3月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题（C/C++）
【动态规划算法】蓝桥杯填充问题（C/C++）
aliyun1792367740-35101
62 0
opencv学堂
|
7月前
|
算法 计算机视觉
图像处理之积分图应用四（基于局部均值的图像二值化算法）
图像处理之积分图应用四（基于局部均值的图像二值化算法）
opencv学堂
565 0
opencv学堂
|
7月前
|
监控 算法 图计算
图像处理之积分图应用三（基于NCC快速相似度匹配算法）
图像处理之积分图应用三（基于NCC快速相似度匹配算法）
opencv学堂
93 0
opencv学堂
|
7月前
|
文字识别 算法 计算机视觉
图像处理之Zhang Suen细化算法
图像处理之Zhang Suen细化算法
opencv学堂
157 0
BetterBench
|
5月前
|
机器学习/深度学习 算法 网络性能优化
【博士每天一篇文献-算法】A brain-inspired algorithm that mitigates catastrophic forgetting of
本文提出了一种受大脑启发的神经调节辅助信用分配（NACA）算法，该算法通过模拟大脑中的神经调节机制，有效减轻了人工神经网络（ANNs）和脉冲神经网络（SNNs）在学习过程中的灾难性遗忘问题，并具有较低的计算成本。
BetterBench
69 1
Deephub
|
7月前
|
机器学习/深度学习 算法 测试技术
如何应对缺失值带来的分布变化？探索填充缺失值的最佳插补算法
该文探讨了缺失值插补的不同方法，比较了它们恢复数据真实分布的效果。文章指出，处理插补尤其在小样本或复杂数据时是个挑战，需要选择能适应数据分布变化的方法。文中介绍了完全随机缺失（MCAR）、随机缺失（MAR）和非随机缺失（MNAR）三种机制，并以一个简单的例子展示了数据分布变化。文章通过比较均值插补、回归插补和高斯插补，强调了高斯插补在重现数据分布方面更优。评估插补方法时，不应仅依赖于RMSE，而应关注分布预测，使用如能量距离这样的指标。此外，即使在随机缺失情况下，数据分布也可能因模式变化而变化，需要考虑适应这些变化的插补方法。
Deephub
229 2
数据分析螺丝钉
|
7月前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
数据分析螺丝钉
102 5
opencv学堂
|
7月前
|
算法 Java 计算机视觉
图像处理之积分图算法
图像处理之积分图算法
opencv学堂
84 2
opencv学堂
|
7月前
|
资源调度 算法 计算机视觉
图像处理之积分图应用二(快速边缘保留滤波算法)
图像处理之积分图应用二(快速边缘保留滤波算法)
opencv学堂
48 0
opencv学堂
|
7月前
|
算法 BI 计算机视觉
图像处理之积分图应用一(半径无关的快速模糊算法)
图像处理之积分图应用一(半径无关的快速模糊算法)
opencv学堂
54 0

热门文章

最新文章

  • 1
    Python-OpenCV学习（十）用GrabCUt算法进行图片前景的提取
  • 2
    [PAL规范]SAP HANA PAL 数据处理装箱算法Binning编程规范BINNING
  • 3
    编码算法－Base64
  • 4
    WPF 心形线算法
  • 5
    【20160924】GOCVHelper MFC增强算法（5）
  • 6
    索引【数据挖掘算法】
  • 7
    《算法技术手册》一第3章 算法基础
  • 8
    插入排序(insertion sort)算法实现
  • 9
    计算某年某月的某一天是星期几的算法
  • 10
    算法起步之Prim算法
  • 1
    【Paddle】PCA线性代数基础 + 领域应用：人脸识别算法（1.1w字超详细：附公式、代码）
    131
  • 2
    BASE64的算法说明
    72
  • 3
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    123
  • 4
    理解并应用机器学习算法：决策树
    153
  • 5
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    462
  • 6
    【机器学习】为什么K-means算法使用欧式距离度量？
    448
  • 7
    【机器学习】描述K-means算法的步骤
    164
  • 8
    【机器学习】K-means和KNN算法有什么区别？
    714
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    65
  • 10
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    68

    • 相关课程

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

    • 相关电子书

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

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅