图像处理------泛洪填充算法(Flood Fill Algorithm) 油漆桶功能

2021-12-24 01:01:10

泛洪填充算法(Flood Fill Algorithm)

泛洪填充算法又称洪水填充算法是在很多图形绘制软件中常用的填充算法，最熟悉不过就是

windows paint的油漆桶功能。算法的原理很简单，就是从一个点开始附近像素点，填充成新

的颜色，直到封闭区域内的所有像素点都被填充新颜色为止。泛红填充实现最常见有四邻域

像素填充法，八邻域像素填充法，基于扫描线的像素填充方法。根据实现又可以分为递归与

非递归（基于栈）。

在介绍算法的三种实现方式之前，首先来看一下测试该算法的UI实现。基本思路是选择一

张要填充的图片，鼠标点击待填充的区域内部，算法会自动填充该区域，然后UI刷新。完

整的UI代码如下：

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

首先介绍四邻域的泛洪填充算法，寻找像素点p(x, y)的上下左右四个临近像素点，如果没有

被填充，则填充它们，并且继续寻找它们的四邻域像素，直到封闭区域完全被新颜色填充。

图像处理------泛洪填充算法(Flood Fill Algorithm) 油漆桶功能蓝色方格为四个邻域像素， p(x, y)为当前像素点。

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

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

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

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

图像处理------泛洪填充算法(Flood Fill Algorithm) 油漆桶功能

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

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

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

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

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

代码如下：

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

基于递归实现的泛洪填充算法有个致命的缺点，就是对于大的区域填充时可能导致JAVA栈溢出

错误，对最后一种基于扫描线的算法，实现了一种非递归的泛洪填充算法。

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

; // 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;
  • }
  • }
    • 上一篇：LR使用流程简介之录制方式说明


    下一篇：Swift UIImageView和UISlider组合