Android中怎么利用泛洪填充算法對圖像進行處理

這篇文章將為大家詳細講解有關Android中怎么利用泛洪填充算法對圖像進行處理，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

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

關于Android中怎么利用泛洪填充算法對圖像進行處理就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。