WaterShed(워터쉐드)

몇일전 영상 분할 알고리즘중 watershed 라는 알고리즘을 접하고, 세미나를 준비하기위해 자료를 찾고 공부를 시작.

1979년 "Use of Watershed in Contour Detection" 이란 논문을 통해 처음 나온 WaterShed는 영상의 픽셀값을 2차원 지형으로 생각하고 위, 아래에서 물을 채워가는 방식이다.

영상분할은 크게 Edge-based 와 Region-based 로 크게 나눌수 있는데, 

Edge-based 같은 경우는 경계선을 바탕으로 의미있는 영역들을 추출하는 방법으로, 잡음에 민감하고 폐곡선의 형태의 경계선을 얻기 어려운 단점이 있다.
Region-based 같은 경우는 명암도의 유사성이 근거하는 방법으로 잡음이 많은 환경에서 물체를 분할하기 좋다. 잡음이나 경계선부근에서의 번짐에 약한 단점이 있다.

Watershed algorithm은 Region-based 의 형태로 볼수있는데, 요즘에 나온 논문들은 Edge 정보를 이용하여 외곽선의 정보를 추출한후 Region-based의 방법으로 알고리즘을 꾸리고 있다.
 

 

Watershed는  "영상의 픽셀값을 높이로 생각하고 영상을 2차원 지형으로 가정, 물을 채웠을때 하나의 윤곽선으로 둘러싸여진 웅덩이 분할된 영역으로 분할하는 기술로 볼수 있다."

•높은값을 갖는 픽셀들은 봉우리(peak) 또는 워터세드 라인(watershed line)으로 표현

•낮은값을 갖는 픽셀들은 골짜기(valley)또는 국부 최소값(regionalminimum)으로 표현

•영상내의 픽셀들의 집합을 하나의 지형으로 간주하고 높낮이를 분석하는 방법

  

Watershed은 크게 Rainfall, Flooding의 두가지 방법으로 나눌수 있다.  (뒤에서 다시 설명)

§ Rainfall

ü 지형의 고도가 높은 지점에서부터 물방울을 떨어뜨려 고도가 낮은 골짜기에물 웅덩이를 형성시키는 방법

§ Flooding
       ü 물을 떨어뜨리지 않고 고도가 낮은 골짜기부터 물을 채워 물웅덩이를 형성시키는 방법

   전체적인 흐름을 살펴보면 영상을 입력받고, 일련의 전처리 과정을 거친후에 Watershed 알고리즘을 적용시키게 된다. 
 

 

전처리 과정부터 살펴보면,
 

• 색상공간 변환 & 잡음제거 : anisotropic filter(Weight, 원거리의 사물들을 좀 더 깨끗하고 자세하게 표현)

                                        Isotropic filter : 마스크내의 가중치가 고르게, anisotropic filter : 마스크내의 가중치가 다르다.

 

• 비선형 확산 : Erosion, Dilation -> Reconstruction

 

                 • 거리변환 : Euclidean Distance 

 

기울기 값을 구하는 방법은, 

 

위의 사진은 어렵게 수식으로 설명이 되어있으나 우리가 알고있는 것처럼 미적을 통하여 기울기 획득

기울기를 값을 통하여 기준값을 잡고 이진화 수행, 여기서 워터쉐드(WaterShed)의 핵심인 watershed 와 minima 지역으로 나뉘게 된다.

여기서 λ는 기준값(Threshold)를 의미하고 R 은 일정 지역의 반경(즉, 마스크 값의 범위). 
이걸 그림으로 다시 표현해보자면,

이런 일련의 과정을 거쳐 Watersheds 와 Minima 지역이 분리되게 되면 Rainfall 과 Flooding 알고리즘을 선택하여 수행하게 되면 waterfall 알고리즘이 완성된다. 

먼저 Rainfall 부터 설명해보자면, 폭포수에서 물이 떨어지는 즉. 높은곳에서 물이 떨어지는 현상을 이용한 것이다.
물방울이 떨어뜨리기 전에 영상내의 모든 국부 최소지점은 특정 태그를 할당 받게 되고 결과적으로 생성된 각각의 물 웅덩이는 태그값으로 구분되게 된다. 

ㄱfFlooding 기법은 각각의 물 웅덩이의 국부 최소지점에 구멍을 뚫고 이 구멍으로부터 서서히 물을 채우는 기법이다.

이과정을 수행하게 되면 수면이 상대적으로 고도가 낮은 봉우리의 고도와 같아지고 이때 댐을 세워 다른 웅덩이로 물이 흘러 넘치는 것을 막아준다.
갖아 높은 높우리에 댐이 건설되는 순간까지 수면을 상승시켜 주면서 반복한다.

 

위의 과정을 모두 수행하고 나면 워터쉐드의 알고리즘은 완성!
두번에 걸쳐 올려서 내용 설명이 많이 부족하긴 했지만, 많이 얻어가셨으면 합니다.

추가적인 질문사항 주시면 알려드리거나 자료 보내드릴께요~!


 

별첨(참고자료)