快捷導(dǎo)航

Android圖像處理之泛洪填充算法

更新時(shí)間：2018年05月08日 16:40:36 作者：gloomyfish

這篇文章主要介紹了泛洪填充算法,工作原理是從一個(gè)點(diǎn)開(kāi)始附近像素點(diǎn)，填充成新的顏色，直到封閉區(qū)域內(nèi)的所有像素點(diǎn)都被填充新顏色為止，分享給大家供大家參考

泛洪填充算法(Flood Fill Algorithm)

泛洪填充算法又稱洪水填充算法是在很多圖形繪制軟件中常用的填充算法，最熟悉不過(guò)就是windows paint的油漆桶功能。算法的原理很簡(jiǎn)單，就是從一個(gè)點(diǎn)開(kāi)始附近像素點(diǎn)，填充成新的顏色，直到封閉區(qū)域內(nèi)的所有像素點(diǎn)都被填充新顏色為止。泛紅填充實(shí)現(xiàn)最常見(jiàn)有四鄰域像素填充法，八鄰域像素填充法，基于掃描線的像素填充方法。根據(jù)實(shí)現(xiàn)又可以分為遞歸與非遞歸（基于棧）。

在介紹算法的三種實(shí)現(xiàn)方式之前，首先來(lái)看一下測(cè)試該算法的UI實(shí)現(xiàn)?；舅悸肥沁x擇一張要填充的圖片，鼠標(biāo)點(diǎn)擊待填充的區(qū)域內(nèi)部，算法會(huì)自動(dòng)填充該區(qū)域，然后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 
 } 
}

首先介紹四鄰域的泛洪填充算法，尋找像素點(diǎn)p(x, y)的上下左右四個(gè)臨近像素點(diǎn)，如果沒(méi)有被填充，則填充它們，并且繼續(xù)尋找它們的四鄰域像素，直到封閉區(qū)域完全被新顏色填充。

藍(lán)色方格為四個(gè)鄰域像素， p(x, y)為當(dāng)前像素點(diǎn)。

基于遞歸實(shí)現(xiàn)代碼很簡(jiǎn)單：

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

八鄰域的填充算法，則是在四鄰域的基礎(chǔ)上增加了左上，左下，右上，右下四個(gè)相鄰像素。

并遞歸尋找它們的八鄰域像素填充，直到區(qū)域完全被新顏色填充。

藍(lán)色方格為四個(gè)鄰域像素，黃色為左上，左下，右上，右下四個(gè)像素， p(x, y)為當(dāng)前像素點(diǎn)。

基于遞歸實(shí)現(xiàn)的代碼也很簡(jiǎn)單：

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

基于掃描線實(shí)現(xiàn)的泛洪填充算法的主要思想是根據(jù)當(dāng)前輸入的點(diǎn)p(x, y)，沿y方向分別向上

與向下掃描填充，同時(shí)向左p(x-1, y)與向右p(x+1, y)遞歸尋找新的掃描線，直到遞歸結(jié)束。

代碼如下：

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

基于遞歸實(shí)現(xiàn)的泛洪填充算法有個(gè)致命的缺點(diǎn)，就是對(duì)于大的區(qū)域填充時(shí)可能導(dǎo)致JAVA棧溢出錯(cuò)誤，對(duì)最后一種基于掃描線的算法，實(shí)現(xiàn)了一種非遞歸的泛洪填充算法。

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

運(yùn)行效果：

算法類源代碼如下：

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: