알고리즘: 재귀함수(4) 예제 Counting cells in a Blob

Counting cells in a Blob

 

 - 입력으로 하나의 Binary 이미지가 주어짐

 - 각 픽셀은 Background pixel이거나 image pixel임

 - blob : 서로 연결된 image pixel들의 집합을 blob이라고 부름

 - 상하좌우, 대각방향으로도 연결된 것으로 간주함

 - 색칠된 background pixel을 우리의 기준으로 잡는 것임

 

 - 이미지상 좌표가 주어졌을 때, 그 점이 속해있는 blob의 크기를 계산하는 것임

 - 만약 blob에 속하지 않을 때 0을 반환함

 

입력

    N*M 크기의 2차원 그리드(grid)가 주어짐

    하나의 좌표는 ( x, y )임

 

출력

    픽셀 ( x, y )가 포함된 blob의 크기를 출력함

    ( x, y )가 어떤 blob에도 속하지 않는 경우는 0을 반환함

 

Recursive Thinking

 

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

    만약 x와 y가 유효한 좌표가 아니라면

         return 0

    현 픽셀이 image color가 아니거나, 이미 카운트 된 pixel일 경우

         return 0

     현 픽셀이 image color라면

        먼저 현 픽셀을 count ( count = 1 )

        현 픽셀의 중복 카운트를 방지하기 위해 다른 색으로 칠함

        현 픽셀에 이웃한 모든 픽셀에 대해

                그 픽셀이 속한 blob의 크기를 카운트해 카운트에 더해줌

        카운터를 반환함

 

 

코드