[Algorithm] 순환 ⑤

<Counting Cells in a Blob> : 좌표가 위치하는 곳이 속한 Blob의 크기를 찾는 것

조건) Binary 이미지가 주어지고 각 픽셀은 background pixel이거나 혹은 image pixel이 됨. 

       서로 연결된 image pixel들의 집합을 blob이라고 부르며 상하좌우 및 대각방향으로도 연결된 것으로 간주함.

       입력: N * N 크기의 2차원 그리드(grid)와 하나의 좌표 ( x, y )

       출력: 픽셀 ( x, y )가 포함된 Blob의 크기 그러나 ( x, y)가 어떤 Blob에도 속하지 않는 경우에는 0

=> Recursive Thinking: 현재 픽셀이 속한 Blob의 크기를 카운트하려면 1) 현재 픽셀이 image color가 아니라면 0을 반환함. 2) 현재 픽셀이 image color라면 먼저 현재 픽셀을 카운트(count = 1)하고 현재 픽셀이 중복 카운트 되는 것을 방지하기 위해 다른 색으로 칠함. 현재 픽셀에 이웃한 모든 픽셀들에 대해서 그 픽셀이 속한 Bolb의 크기를 카운트하여 카운터(count)에 더해줌. 카운터를 반환함.

 

- countCells ( x, y )를 위한 알고리즘

if the pixel ( x, y ) is outside the grid

    the result is 0 ; // x와 y좌표가 0보다 작거나 N보다 커서 유효한 좌표가 아니라면 0을 return

else if pixel ( x, y ) is not an image pixel or already counted

    the result is 0 ; // image pixel이 아니거나 이미 카운트 되었다면 0을 return

else

     set the colour of the pixel ( x, y ) to a red colour; // 이미 카운트되었다는 것을 red로 표시

     the result is 1 plus the number of cells in each piece of the blob that includes a nearest neighbour ; // 카운트 함

 

Ex) private static int BACKGROUND_COLOR = 0 ;

     private static int IMAGE_COLOR = 1 ;

     private static int ALREADY_COUNTED_COLOR = 2 ;

 

     public int countCells ( int x , int y ) {

          int result ;

          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-1 , y+1 ) + countCells ( x, y+1 ) + countCellls ( x+1, y+1 )

                         + countCells ( x-1, y ) + countCells ( x+1, y ) + countCells ( x-1 , y-1 )

                         + countCells ( x, y-1 ) +  countCells ( x+1 , y-1 ) ;

          }

    }