티스토리 뷰

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

2-5. Recursion의 응용 2 - Counting Cells in a Blob

Counting cells in a Blob

  • 입력으로 Binary 이미지가 주어진다.

  • 각 픽셀은 background pixel(흰색)이거나 혹은 imagepixel(파란색)이다.

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

  • 상하좌우 및 대각방향으로도 연결된 것을 Blob으로 간주한다.

  • 따라서 위의 그림에서는 아래와 같은 Blob 집합이 존재한다.

    • 총 4개의 Blob 존재

특정 좌표가 속한 Blob의 크기 count

  • 입력

    • N * N 크기의 2차원 그리드(grid)

    • 하나의 좌표 (x, y)

  • 출력

    • 픽셀 (x,y)가 포함된 blob의 크기,

    • (x,y)가 어떤 blob에도 속하지 않는 경우에는 0

Recursive Thinking

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

    • 현재 픽셀이 image color가 아니라면

      • 0을 반환한다.

    • 현재 픽셀이 image color라면

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

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

      • 현재 픽셀에 이웃한 모든 픽셀들(8개 픽셀들) 각각에 대해서

        • 그 픽셀이 속한 Blob의 크기를 카운트하여 카운터에 더해준다.

      • 카운터를 반환한다.

순환적 알고리즘 - 1

  • x=5, y=3이라고 가정, 즉 이 픽셀이 포함된 blob의 크기를 계산하는 것이 목적이다.

  • count=0에서 시작.

  • 다음으로 현재 cell을 다른색으로 칠하고 count를 1증가한다. 이렇게 색칠하는 것은 이 픽셀이 중복 count 되는 것을 방지하기 위해서 이다.

  • 현재 count=1

  • 그 다음 (5, 3)픽셀에 인접한 8개의 픽셀에 대해서 순서대로 그 픽셀이 포함된 Blob의 크기를 count한다. 북, 북동, 동, 동남, .. 순으로 고려한다.

  • 가장 먼저 북쪽인(5,2) 픽셀이 포함된 Blob의 크기는 0이다. 따라서 count 값은 변화없이 1이다.

  • 다음으로 북동쪽인(6,2) 픽셀이 속한 Blob을 count하고, count된 픽셀들을 빨간색으로 색칠한다.

    • 여기서 보면(6,2) 픽셀을 포함한 Blob의 count는 3이다. (6,2), (6,2)의 북서쪽인 (5,1), (5,1)의 남서쪽인 (4,2) 총 3개이다.

    • 현재 count = 1 + 3 = 4

    • 카운트 된 모든 픽셀들은 빨간색으로 칠해져서 중복카운트 방지

  • 동일한 방법으로 다음 순서에 해당하는 남쪽 픽셀(5,4)이 속한 Blob의 크기는 9이다. 카운트 하고 색칠한다.

    • count = 4 +9 = 13

  • 남서, 서, 북서 방향은 픽셀이 속한 Blob이 없거나 혹은 이미 카운트 되었기 때문에 count에 영향을 주지 않는다.

  • 결과적으로 count 값 13 return.

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 already 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 neighbour;

Java Code 구현

  • x = 열, y = 행

public class CountingCellsBlob {
 private static int BACKGROUND_COLOR = 0;
 private static int IMAGE_COLOR = 1;
 private static int ALREADY_COUNTED = 2;
 private static int N = 8;
 private static int[][] grid = {
    {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},
};

 public static int countCells(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] = ALREADY_COUNTED;
     return 1 + countCells(x, y + 1) + countCells(x + 1, y + 1)
         + countCells(x + 1, y) + countCells(x + 1, y - 1)
         + countCells(x, y - 1) + countCells(x - 1, y - 1)
         + countCells(x - 1, y) + countCells(x - 1, y + 1);
  }
}

 public static void main(String[] args) {
   printGrid();
   int blobCount = countCells(3, 5);
   System.out.println();
   System.out.println("BlobCount : " + blobCount);
   printGrid();
}

 private static void printGrid() {
   for (int x = 0; x < N; x++) {
     System.out.print("[");
     for (int y = 0; y < N; y++)
       System.out.print(grid[x][y] + ", ");
     System.out.println("]");
  }
}
}


[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, ]

BlobCount : 13
[1, 0, 0, 0, 0, 0, 0, 1, ]
[0, 1, 1, 0, 0, 2, 0, 0, ]
[1, 1, 0, 0, 2, 0, 2, 0, ]
[0, 0, 0, 0, 0, 2, 0, 0, ]
[0, 1, 0, 2, 0, 2, 0, 0, ]
[0, 1, 0, 2, 0, 2, 0, 0, ]
[1, 0, 0, 0, 2, 0, 0, 2, ]
[0, 1, 1, 0, 0, 2, 2, 2, ]

Process finished with exit code 0







댓글
댓글쓰기 폼