Java - Blob 넓이 구하기

1. 문제

Example of problem

• 0(Background pixel)과 1(Image pixel)로 구성된 Binary 이미지에서 서로 인접한 Image pixel의 집합을 Blob라 한다.
• 상하좌우 + 이웃한 대각선까지 인접한 것으로 간주
• 문제) Binary 이미지에서 Blob의 집합과 그의 크기를 구하기

---

2. 생각(Recursion Thinking)

본 문제는 하나의 Image pixel를 기준으로 이웃한 Image pixel의 갯수를 반복적으로(?) 세야하기 때문에 재귀 함수(Recursion)를 이용하였다. Recursion Think를 이용하여 단계별로 나누면 다음과 같이 나눌 수 있다.

 

2.1. 첫 번째 Recursion

• Base Case)
  Binary image에서 [0, 0]부터 시작해서 [N-1, N-1]까지 Recursion하는데,
  if) row == N-1 && column == N-1 성립하면 Escape한다.
• Recursion Case)
  if) pixel 값이 1이면 해당 pixel 값을 기준으로 두 번째 Recursion를 실행
  else) 다음 pixel로 이동

2.2. 두 번째 Recursion

• Base Case)
  if) pixel [row, column] 값이 1이 아니면 Retrun한다.
• Recursion Case)
  - 지나온 pixel에 Marking하여 지나온 pixel에 되돌아가는 것을 방지한다.
  - Blob 면적에 1를 더한다.
  - 상하좌우 + 대각선, 총 8개의 방향에 대해서 Recursion한다.

 

Recursion Thinking을 이용하여 코드를 작성하면 다음과 같이 작성할 수 있다.

private void getBlobInfo(int row, int column, int nameOfBlob) 
    // ** Base Case
    if 현재 셀의 위치가 [N-1, N-1]인지
    	return;
    else
    // ** Recursion Case
        if 현재 셀의 값이 1인지
           // * 현재 셀은 새로운 Blob의 기준점이 된다.
           getBlob(row, column, nameOfBlob);
        
        // * 다음 셀로 이동한다.
        x++;
        if(x==size) 
        	y++; x=0;
        
        // * Recursion
        getBlobInfo(row, column, nameOfBlob);

private void getBlob(int y, int x, int name) 
	// ** 첫 번째 Base case : Binary image 영역 밖인지
    if(x<0 || x>=size || y<0 || y>=size)
    	return;
   	// ** 두 번째 Base case : 해당 셀의 값이 1인지 
    else if(pixels[y][x] != 1)
    	return;
    // ** Recursion Case
    else 
    	// * 현재의 셀을 1이 아닌 값으로 Marking하여 다시 가는 것을 방지
        pixels[y][x] = name
        // * 현재 카운트하고 있는 blob의 면적에 1을 더하기
        
        // * 상하좌우 + 대각선에 대해서 Recursion
        getBlob(y+1, x, newBlob, name);
        getBlob(y, x+1, newBlob, name);
        getBlob(y-1, x, newBlob, name);
        getBlob(y, x-1, newBlob, name);
        getBlob(y+1, x-1, newBlob, name);
        getBlob(y+1, x+1, newBlob, name);
        getBlob(y-1, x+1, newBlob, name);
        getBlob(y-1, x-1, newBlob, name);

---

3. 풀이 및 코드 분석

public class Test {	
    private static int[][] pixels = {{1, 0, 0, 0, 0, 0, 0, 1},
                                     {0, 1, 1, 0, 0, 1, 0, 0},
                                     {1, 1, 0, 0, 1, 0, 1, 0},
                                     {0, 0, 0, 0, 0, 1, 0, 0},
                                     {0, 1, 0, 1, 0, 1, 0, 0},
                                     {0, 1, 0, 1, 0, 1, 0, 0},
                                     {1, 0, 0, 0, 1, 0, 0, 1},
                                     {0, 1, 1, 0, 0, 1, 1, 1}};
	private static int size = pixels.length;
	private static ArrayList<Blob> blobs = new ArrayList<>();
	
    // ** Main method
	public static void main(String[] args) {
		getBlobInfo(0, 0, 2);
		
		// * Binary image에서 같은 Blob끼리 묶어서 표시하고, 출력
		printPixels();
		// * 확인된 Blob에 대해서 면적 출력
		printBlobsInfo();
	}
	
    // ** Inner class
	private static class Blob{	
		private int nameOfBlob;
		private int size;
		
		public Blob(int name) {
			nameOfBlob = name;
			size = 0;
		}
		
		public int getName() {
			return nameOfBlob;
		}
		
		public int getSize() {
			return size;
		}
		
		public void setName(int newName) {
			nameOfBlob = newName;
		}
		
		public void setSize(int newSize) {
			size = newSize;
		}
	}
	
	private static void getBlobInfo(int y, int x, int name) {
		if(y==size-1 && x==size-1)
			return;
		else {
			if(pixels[y][x]==1) {
				Blob newBlob = new Blob(name);
				getBlob(y, x, newBlob, name);
				blobs.add(newBlob);
				name++;
			}
			
			x++;
			if(x==size) {
				y++;
				x=0;		
			}
			getBlobInfo(y, x, name);
		}
		
	}
	
	private static void getBlob(int y, int x, Blob newBlob, int name) {
		if(x<0||x>=size||y<0||y>=size)
			return;
		else if(pixels[y][x]!=1)
			return;
		else {
			pixels[y][x] = name;
			int blobArea = newBlob.getSize();
			newBlob.setSize(++blobArea);
			
			getBlob(y+1, x, newBlob, name);
			getBlob(y, x+1, newBlob, name);
			getBlob(y-1, x, newBlob, name);
			getBlob(y, x-1, newBlob, name);
			getBlob(y+1, x-1, newBlob, name);
			getBlob(y+1, x+1, newBlob, name);
			getBlob(y-1, x+1, newBlob, name);
			getBlob(y-1, x-1, newBlob, name);
		}
	}
	
	private static void printPixels() {
		System.out.println("Pixel image: ");
		
		for(int row=0; row<size; row++) {
			for(int column=0; column<size; column++) {
				if(pixels[row][column]!=0)
					System.out.printf(" %d", pixels[row][column]-1);
				else
					System.out.printf(" %d", pixels[row][column]);
			}
			System.out.println();
		}
	}
	
	private static void printBlobsInfo() {
		if(blobs.size()==0)
			System.out.println("There is no blob.");
		else {
			System.out.println("\nBlob information: ");
			for(int i=0; i<blobs.size(); i++) 
				System.out.printf("Blob[%d]'s size = %d\n", blobs.get(i).getName()-1, blobs.get(i).getSize());
		}
	}
}

 

Pixel image: 
 1 0 0 0 0 0 0 2
 0 1 1 0 0 3 0 0
 1 1 0 0 3 0 3 0
 0 0 0 0 0 3 0 0
 0 4 0 3 0 3 0 0
 0 4 0 3 0 3 0 0
 4 0 0 0 3 0 0 3
 0 4 4 0 0 3 3 3

Blob information: 
Blob[1]'s size = 5
Blob[2]'s size = 1
Blob[3]'s size = 13
Blob[4]'s size = 5

---

4. 메모

• 코드를 작성하기 전에 대략적인 알고리즘에 대해서 생각하자. 
  - 처음에 알고리즘을 생각하지 않고, 무작정 코드를 작성했지만, 중간에 예상치 못한 문제와 오류가 발생하여 혼란스
    러웠다. 하지만, 전체적인 알고리즘을 생각하고, 정리한 뒤, 다시 한 번 작성하자 쉽게 해결할 수 있었다.
• Recursion의 Base structure를 꼭 생각하고, 이용하자.
  1) Recursion은 Base case와 Recursion Case로 나눈다.
  2) Recursion case는 반드시 Base case로 수렴해야한다. 
  3) Implicit parameter보다 Explicit parameter를 사용하자. (대신 생략할 수 있으면 생략하자.)
  - 어떠한 Recursion 문제도 위 규칙들을 크게 벗어나지 않는다. 그러니 위 규칙을 반드시 명심하자.