(재귀)Blob(Labeling) 알고리즘

Blob Labeling 알고리즘(Connected-component labeling (alternatively connected-component analysis, blob extraction, region labeling, blob discovery, or region extraction) )은 영상처리 분야에서 Labeling을 할 때 주로 쓰는 알고리즘인데, N*N 크기의 2차원이미지에서 인접한(상,하,좌,우,대각선모두포함) 화소에 모두 같은 번호(Label)을 붙이고 연결되지 않은 다른 성분(component)에는 다른 번호를 붙이는 알고리즘인데 주로 이미지 안에 연결되어 있는 객체가 몇개 인지 알아낼 때 사용하는 것이다.

 

 

문제는 픽셀 (x,y)가 포함된 blob의 크기를 알아내기 위해서 어떻게 해야 할까?

 

8x8 이미지가 그림1 처럼 주어진다고 하였을때  픽셀(x=5, y=3)이 속한 blob의 크기를 어떻게 카운트할지 생각해보자.

그림1, 8x8 이미지

 

먼저 현재 cell이 0과 같지 않다면 다른 색으(여기서는 2로 하겠다)로 칠하고 count를 1증가한다. 
이렇게 색칠하는 것은 이 픽셀이 중복 count되는 것을 방지하기 위해서 이다.
현재 셀을 기준으로 북 -> 북동 -> 동, -> 동남 -> 남 ... 이런 순서로 검사하다가 인접한 픽셀이 1이면 count를 +1 씩 증가하고 방문한 픽셀은 2로 변경한다. 만약 인접한 픽셀 검사시 2로 되어 있다면 count를 증가할 필요 없다.

그림2. 재귀적으로 순환하는 순서

이처럼 현재 픽셀 기준 -> 북쪽 검사하였는데 이미지 픽셀이라면 그 픽셀의 북쪽을 또 검사하고 .... 반복적으로 검사하다가
만약 인접한 픽셀이 이미지픽셀이 아니라면(base case = 픽셀값이 0인경우) 재귀를 빠져나오면 된다.

이걸 수식으로 표현하면 다음과 같다.

 

f(x,y) count = 0, if image[x][y] != 0 <- base case
f(x,y) count = 1 + count(↑) + count(↗) + count(→) + count(↘) + count(↓) + count(↙) + count(←) + count(↖), if(image[x,y] == 1)

 

 
public class BlobAlgorithmMain {
 
    static  final int IMAGE_COLOR = 1;
    static  final int VISITED_COLOR = 2;
    static  final int BACKGROUND_COLOR = 0;
 
 
    public static void main(String[] args) {
        int [][]image = {
                {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}
        };
 
        int count = blobCount(image, 5, 3, 8) ;
        System.out.println(count);
    }
 
 
    public static int blobCount(int [][]image, int x, int y,  int N) {
 
 
        if(x < 0 || y < 0 || x > N-1 || y > N-1) {
            return 0;
        }
 
        if(image[x][y] == VISITED_COLOR ||
                image[x][y] == BACKGROUND_COLOR) {
            return 0;
        }
 
 
        image[x][y] = VISITED_COLOR;
 
        return 1 + blobCount(image, x, y-1, N)  // 북쪽
        + blobCount(image, x+1, y-1, N) // 북동쪽
        + blobCount(image, x+1, y, N) // 동쪽
        + blobCount(image, x+1, y+1, N) // 동남쪽
        + blobCount(image, x, y+1, N) // 남쪽
        + blobCount(image, x-1, y+1, N) // 남서쪽
        + blobCount(image, x-1, y, N) // 서쪽
        + blobCount(image, x-1, y-1, N); // 서북쪽
        
    }
    
}