Binary 이미지

각 픽셀은 background pixel 이거나 혹은 image pixel

서로 연결된 image pixel 들의 집합을 blob 이라고 부른다

상하좌우 및 대각선으로 연결된 것으로 간주

Solve

현재 픽셀이 속한 blob의 크기를 카운트 하려면

현재 픽셀이 image color 가 아니라면 0을 반환한다.

현재 픽셀이 image color 이라면

먼저 현재 픽셀을 카운트한다. \(count=1\)

현재 픽셀이 중복 카운트되는 것을 방지하기 위해 다른색으로 변경한다.

현재 픽셀이 이웃한 모든 픽셀들에 대하여 그 픽셀이 속한 blob 의 크기를 카운트하여 카운트에 더해 준다.

카운트를 반환한다.

Algorithm

Algorithm for countCells (x, y)
if the pixel (x, y) is outside the grid
    the result is 0;
else if pixel (x, y) is not an image pixel or alread counted
    the result is 0;
else
    set the color of the pixel (x, y) to a red color;
    the result is 1 plus the number of cells in each piece of the blob that includes a nearest neigbour;

Code

private static int BACKGROUND_COLOR = 0;
private static int IMAGE_COLOR = 1;
private static int VISITED_COLOR = 2;

private int countCell(int x, int y) {
    if (x<0 || x>=N || y<0 || y>=N)
        return 0;
    else if (grid[x][y] != IMAGE_COLOR)
        return 0;
    else {
        grid[x][y] = VISITED_COLOR;
        return 1+countCell(x-1, y+1) + countCell(x, y+1)
            + countCell(x+1, y+1) + countCell(x-1, y)
            + countCell(x+1, y) + countCell(x-1, y-1)
            + countCell(x, y-1) + countCell(x+1, y-1);
    }
}