Block-based watershed segmentation

제안된 방법은 이미지를 블록으로 나누고 각각의 블록을 독립적으로 처리 한다. 따라서, 하드웨어 구현에 적합하도록 되어 있고, 병렬 처리를 위한 확 장이 가능하다. 이미지 단위로 segmentation 을 처리시에는 전체 이미지에 대한 smoothing 과정이 완료된 이후에 gradient 계산이 가능하고, 전체 이 미지에 대한 gradient 가 완료된 이후에 watershed 알고리즘의 시작이 가능 하다. 또한 이미지 크기에 해당하는 이전 결과들이 저장이 되어야 한다. 따 라서 이에 해당하는 저장 공간이 필요하게 된다. 반면 블록 단위로 처리시 에는 블록의 크기에 해당하는 저장 공간만을 가지고 처리하고 다음 블록을 처리하거나, 또는 동시에 동일한 모듈을 여러 개 두어 동시에 처리가 가능 하기 때문에, distributed memory system 에도 적용이 가능하게 된다.

하지만 블록 단위로 watershed 를 수행했기 때문에 같은 영역이 여러 블 록에 걸쳐 있을 때 블록 경계에서 영역이 분할되며, 그에 따라 이미지 단위 의 watershed 보다 매우 많은 영역으로 나누어진다. 이미지 기반 watershed 와 동일한 수의 영역으로 분할하기 위해서는 블록의 경계에서 분할된 영역 이 실제 object 의 경계인지 혹은 블록 단위 연산에 기인한 것인지를 조사 해야 한다. 만약 블록 경계에서 인접한 두 영역이 실제로는 하나의 영역인 경우에는 두 영역의 label 을 같은 값이 되도록 해야 한다.

그림 5.7 는 하나의 object가 2개의 블록 (Block I, Block II) 에 나뉘어 위 치하고, 그에 따라 블록의 경계에서 2개의 영역으로 분할된 예를 보인다.

그림 5.7 Region across the block boundary

제안된 방법에서는 블록 단위의 연산을 위해 각 블록별로 Vincent-Soille watershed 알고리즘을 수행하고 그 결과를 각 블록마다 독립적으로 저장한 다. Block I 에서 watershed 를 수행하면, region A 가 생성되는데 이 region A의 root의 gradient 값을 Root_A 라 한다. 그 다음 block II 에 대한 watershed 를 수행하는데, 이 때 이전 블록의 1 픽셀폭만큼의 픽셀들을 포 함하여 watershed를 수행한다. 그 결과로 region C 가 분할되면 이 영역의 root 값을 Root_C 로 표시한다. 두 영역 경계에서는 1 픽셀폭만큼의 중첩 된 영역이 발생하는데, 이 영역을 boundary area 라고 나타낸다. 그림 5.7 에서는 boundary 영역에서의 gradient 값을 Grad_B 로 표시하였다. 이 boundary area 에서는 두 개 sub-block 에서 수행한 watershed 결과를 동 시에 가지게 된다.

이전의 연구에서는 블록 경계를 처리하기 위해 블록 경계에서의 추가 1 픽셀의 정보만을 사용할 경우, 이전 절에서 살펴본 바와 같이 over-segment 결과를 생성하게 된다.

본 연구에서는 블록의 경계에서 merge/split 판단을 하기 위해서, region 의 root 정보를 함께 사용하였다. Region 의 root 정보를 사용하는 것은 이 를 저장하기 위한 추가적인 공간이 필요하고, merge/split 판단을 위한 추가 적인 연산이 필요하지만, root 의 정보를 사용함으로써, 정확한 merge/split 판단이 가능하게 된다. Watershed 알고리즘에서 root 의 수는 label 의 수와 일치한다. 그림 5.8 은 Vincent-Soille watershed 알고리즘의 pseudo-code 를 설명하고 있다. Watershed 알고리즘은 입력으로 gradient 이미지를 사용 하며, output 으로 픽셀 단위의 label 을 부여하는 동작을 수행한다. 이를 위 해 영상내에 gradient 값을 sorting 하여, 낮은 gradient 값으로부터 순차적 으로 주변 영역을 비교하는 과정을 수행하게 된다. 이때, local minimum 에 는 새로운 label 을 부여하게 되는데, 이때의 local minimum 의 값이 root 값이 되게 된다. 따라서, 그림 5.8 에서와 같이 영역 label 에 대한 root 값 은 watershed 연산 과정에서 저장이 가능하다.

그림 5.8 Root information in Vincent-Soille watershed algorithm

Root 의 값은 그림 5.8 과 같이 표현된 Vincent-Soille 알고리즘에서 새 로운 label 을 부여하는 과정에서 저장이 가능하다. 이와 같이 저장된 값을 가지고, 그림 5.7 과 같은 경계에서 root 의 gradient 값과 boundary 에서 의 gradient 값을 가지고 발생하는 모든 경우에 대해 조사하게 된다. 그림 5.9 와 같은 경우의 수가 발생한다.

그림 5.9 Four possible relationship among Root_A, Grad_B and Root_C

Case I 은 Root_A, Grad_B, Root_C 의 값이 모두 같은 경우를 나타낸다.

Case II 는 동일한 값을 가지는 Grad_B 와 Root_C 보다 Root_A 값이 작 은 경우를 나타낸다. Case III 는 Root_A 와 Grad_B 가 동일하고 이 값이 Root_C 보다 큰 경우를 나타낸다. Case IV 는 Grad_B 의 값이 Root_A 와 Root_C 보다 큰 경우를 나타낸다. 이때, Root_A 와 Root_C 간의 크기는 관계가 없다. 왜냐하면 이것은 Root_A 와 Root_B 는 watershed 알고리즘 의 특성상 식(5.2) 와 같이 항상 Grad_B 보다 작거나 같기 때문이다.

_ _

_ _ (5.2)

그림 5.9 에서 보이는 4 가지 경우는 경계면에서 발생하는 모든 경우를

over-segment 문제 해결이 가능하다. 표 5.1 은 위와 같은 경우에 대해서, 판단하는 방법을 정리해서 보여준다. Case I, II, III 는 다른 블록내에 있는 두 개의 영역이 합쳐져야 하는 경우를 나타낸다. Case IV 는 두 개의 영역이 분 리되어야 하는 경우를 보여준다. 이때, Case II, III 는 각각 두 개의 영역을 하나로 합치면서, root 의 값은 해당 영역의 가장 작은 값 Root_A, Root_C 로 update 가 필요하게 된다. 그림 5.10 은 이와 같은 블록간 region merge/split 을 수행하기 위한 pseudo-code 를 나타낸다. 이 과정은 입력으 로 블록간 segmentation 된 결과를 사용하고, output 으로 병합되어야 하는 label 간 lookup table 을 생성하게 된다.

표 5.1 Decision for region merge/split

Case Condition Decision Updated root I Grad_B = Root_C

Grad_B = Root_A Merge Root_A or Root_C II Grad_B = Root_C

Grad_B > Root_A Merge Root_A III Grad_B > Root_C

Grad_B = Root_A Merge Root_C IV Grad_B > Root_C

Grad_B > Root_A Split -

그림 5.10 Region merging algorithm flow