Android 이미지 처리 의 홍수 충전 알고리즘

17872 단어 android영상 처리범 홍 충전 알고리즘
범 홍 충전 알고리즘(Flood Fill Algorithm)
범 홍 충전 알고리즘 은 홍수 충전 알고리즘 이 라 고도 부 르 는데 많은 그래 픽 그리 기 소프트웨어 에서 자주 사용 하 는 충전 알고리즘 으로 windows paint 의 페인트 통 기능 에 가장 익숙 하 다.알고리즘 의 원 리 는 간단 합 니 다.한 점 에서 부터 근처 의 픽 셀 점 을 새로운 색 으로 채 우 고 닫 힌 구역 안의 모든 픽 셀 점 이 새로운 색 으로 채 워 질 때 까지 채 우 는 것 입 니 다.범 홍 충전 은 가장 흔히 볼 수 있 는 4 인접 도 메 인 픽 셀 충전 법,8 인접 도 메 인 픽 셀 충전 법,스캐닝 라인 을 바탕 으로 하 는 픽 셀 충전 방법 이 있 습 니 다.실현 에 따라 재 귀 와 비 재 귀 로 나 눌 수 있다.
알고리즘 의 세 가지 구현 방식 을 소개 하기 전에 이 알고리즘 을 테스트 하 는 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); 
 } 
}
  8 인접 도 메 인의 충전 알고리즘 은 4 인접 도 메 인 을 바탕 으로 왼쪽 위,왼쪽 아래,오른쪽 위,오른쪽 아래 네 개의 인접 픽 셀 을 추가 한 것 입 니 다.
영역 이 완전히 새 색 으로 채 워 질 때 까지 8 인접 도 메 인 픽 셀 을 재 귀적 으로 찾 습 니 다.
 
파란색 칸 은 네 개의 인접 픽 셀 이 고 노란색 은 왼쪽 위,왼쪽 아래,오른쪽 위,오른쪽 아래 네 개의 픽 셀 이 며 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; 
 } 
 
}
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
C\#디자인 모델 시리즈 튜 토리 얼-프 록 시 모드
C\#디자인 모델 시리즈 튜 토리 얼-브리지 모드

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage