서 론
인간은 외부 환경에 대한 정보를 다양한 감각기관을 통해 얻 어낸다. 이중에서 시각은 감각정보의 70~80%를 차지한다.
이는 시각만 가지고도 활동에 필요한 정보를 어느 정도 얻을 수 있음을 의미한다. 따라서 컴퓨터에 시각기능을 구현한다면 인간과 비슷한 수준의 동작이 가능해질 수 있기 때문에 컴퓨터 를 이용한 영상처리에 대한 연구가 활발히 진행되고 있다.
인간이 물체를 인지하는 것은 물체의 외형을 다른 물체들과 구분하는 것에서부터 시작하기 때문에 영상처리에서도 물체의 외형, 즉 윤곽선을 검출하는 것이 중요하다. 이에 윤곽선 검출 에 대한 다양한 이론과 알고리듬이 나왔다. 하지만 다양한 상 황과 노이즈 등의 이유로 항상 정확한 결과를 얻을 수 있는 방 법은 아직 나오지 않았기 때문에 물체를 구분하는 것이 쉽지 않은 상황이다. 특히 영상의학에서 신체 장기를 촬영한 이미지 의 경우 해상도가 낮고 대부분 흑백으로 나타나며 명확히 구분 되지 않는 부분이 많아 컴퓨터를 이용한 처리가 더 어렵다.
이 런 문 제 를 해 결 하 기 위 한 방 법 으 로 Live-Wire Segmentation 기법이 등장했다. Live-Wire 기법은 사람이 마우스를 이용해 지정한 특정 지점을 기준으로 현재 마우스 포 인터의 위치까지의 최단경로를 이미지의 윤곽선을 따라 구하 는 방식으로 사람이 원하는 경로의 몇몇 위치를 선택해주면 이 들을 연결하는 최단경로로 segmentation을 하는 것이다. 사 람의 노력을 최소화 하면서 세밀하게 원하는 윤곽선 검출이 가 능하기 때문에 영상의학을 비롯한 다양한 분야에서 사용되고 있다.
Live-Wire Segmentation
Live-Wire 기법은 두 지점 사이의 최단경로를 구하는 Dijkstra 알고리듬을 기반으로 하고 있다. Dijkstra 알고리듬 은 노드들 사이에 음수가 아닌 가중치를 갖는 유향 그래프에서 두 지점 사이의 최단 경로를 구하는 알고리듬으로 임의의 지점 에 연결된 모든 노드들에 대해 시작점부터 각 노드까지 갈 수 있는 여러 경로 중에서 가장 작은 값을 갖는 경로만을 남겨가 면서 끝점까지의 경로를 확인하고 최소값을 갖는 경로를 결정 하게 된다 [4].
Dijkstra 알고리듬을 적용하기 위해서는 가중치를 가진 유 향 그래프가 있어야 하는데 Live-Wire 기법에서는 다음과 같 은 방식으로 이미지 픽셀들의 local cost function을 이용한다 [2].
대한의학영상정보학회지 2015;21:9-11
- 9 -
LiveWire 알고리즘을 적용한 영상 분할 기법
*이 윤 주・유 선 국
*전자부품연구원, 연세대학교 의과대학 의학공학교실
통신저자: 유선국, (120-752) 서울시 서대문구 연세로 35 연세대학교 의과대학 의학공학교실
그림 1. Local cost matrix
점 p에서 점 q로 가기 위한 local cost가 l(p,q)일 때 이 값 은 Gradient magnitude, Laplacian zero-crossing, Gradient direction 값에 가중치를 곱한 결과를 합산해서 구 할 수 있는데 Laplacian과 Gradient는 이미지 상에서 윤곽선 을 중심으로 값의 차이를 갖는 필터로 동작하기 때문에 구해진 local cost값이 주변부와 윤곽선을 구분하는 값을 가지게 된 다. 따라서 이를 이미지 전체에 적용하면 그림 1과 같이 local cost matrix를 구할 수 있으며 각 픽셀의 값들을 이용해 최단 경로를 구하기 위해 Dijkstra 알고리듬을 적용해 윤곽선을 검 출할 수 있다.
그림 2는 전체 Live-Wire 알고리듬에 대한 pseudo code를 보여준다 [3].
시작점을 s, 임의의 점 q에서 점 r까지의 local cost를 l(q,r), 시작점부터 임의의 점 q까지의 total cost를 g(q), 확 인하지 않은 주변 픽셀의 리스트를 L, 임의의 점에서 주변 점 으로 갈 수 있는 방향 중 시작점으로 가기 위한 cost가 가장 작
은 방향을 가리키는 포인터를 p라고 했을 때, 시작점부터 이미 지 전체에 대해 각 픽셀에서 시작점까지 cost가 최소가 되는 경로를 모두 구할 때까지 알고리듬을 반복하는 형태이다.
임의의 점 q에 대해 다음으로 갈 수 있는 지점 r은 주변의 8 개 픽셀들이고 각 픽셀로 넘어가기 위한 cost는 기준점에 대해 상하좌우 방향에 있는 픽셀들은 local cost 값을 가지고 대각 선 방향에 있는 픽셀들은 local cost에 배를 한 값을 가지고 이를 이용해 시작점부터 점 r까지 가는데 필요한 total cost의 값이 작은 경로를 구하고 이를 포인터 p를 이용해 저장한다.
이때 점 r까지 가는데 인접한 점 q를 거쳐 가는 것이 total cost가 더 작다면 돌아가는 길로 포인터 p를 변경하고 이전 경 로를 지우는 방식으로 반복 확인하며 이미지 전체를 확인하게 된다.[1]
그림 3은 그림 2의 local cost matrix에 대해 시작점이 지정 되고 알고리듬이 5번 반복할 때까지의 이런 동작 모습을 보여
대한의학영상정보학회지 2015;21:9-11
- 10 -
그림 2. Live-Wire algorithm pseudo code
그림 3. 알고리듬의 동작방식
그림 4. 알고리듬을 통해 구한 전체 경로
준다.
첫 번째 상황과 두 번째 상황을 비교해보면 시작점에서 오른 쪽 대각선 방향에 있는 두 픽셀의 값이 처음 11, 7에서 9, 6으 로 변한 것을 볼 수 있는데 이는 시작점의 오른쪽 픽셀을 거쳐 서 가는 것이 더 적은 cost가 들기 때문에 돌아가는 경로를 기 억하도록 한 것이다. 이는 포인터의 방향이 바뀐 것을 통해 확 인할 수 있다. 이러한 과정을 통해 이미지 전체를 검사하면 그 림 4와 같은 전체 경로 지도를 구할 수 있고 사람이 마우스 포 인터를 움직이면 이 경로 지도를 이용해 최단 경로를 바로 보 여줘 원하는 경로를 선택할 수 있도록 한다.
모의실험
알고리듬 검증을 위해 MATLAB을 이용해 실험을 진행하였 다. Live-Wire 알고리듬을 구현한 MATLAB 함수[5]를 이용 해 실제 DICOM 이미지에 적용해 결과를 확인하였다[6].
그림 5에서 왼쪽 두 개의 사진은 원본 DICOM 이미지이고 오른쪽 두 개의 사진은 각 이미지에 Live-Wire 함수를 적용해 segmentation한 결과이다. 각 결과는 마우스를 이용해 3~4
개의 지점을 지정해 얻을 수 있었다. 이를 통해 Live-Wire 알 고리듬이 제대로 동작하는 것을 확인할 수 있고 적은 노력으로 세밀한 segmentation이 가능하다는 것을 확인할 수 있었다.
결 론
Live-Wire 기법은 사람이 마우스를 이용해 이미지 상의 특 정 지점들을 선택해주면 각 지점들을 연결하는 최단경로를 구 해 윤곽선을 검출하는 방법이다. 이로써 이미지의 상태나 물체 의 형상에 관계없이 빠르고 정확하게 윤곽선을 검출해 낼 수 있다. 비록 컴퓨터가 완전히 자동으로 윤곽선을 검출해내는 방 식은 아니지만 어떤 상황에서도 정확한 윤곽선을 검출할 수 있 는 방법이 나오지 않은 상황에서 적은 노력으로 좋은 결과를 얻을 수 있는 최선의 방식이라고 볼 수 있다.
Acknowledgment
“본 연구는 미래창조과학부의 ICT유망기술개발지원사업의 연구결과로 수행되었음”(R07581510560002003, 웨어러블 산소포화도 측정장치 및 빅데이터 의료 플랫폼 개발)
참 고 문 헌
1. Eric Mortensen, Bryan Morse, William Barrett&Jayaram Udupa, “Adaptive Boundary Detection Using “Live-Wire”
Two-Dimensional Dynamic Programming”, Computers in Cardiology, pp. 635-638, Oct. 1992.
2. William A. Barrett, Eric N. Mortensen, “Interactive Live-Wire Boundary Extraction”, Medical Image Analysis Vol.1 Issue4, pp. 331-341, Sep. 1997.
3. Livewire Segmentation Technique, Wikipedia, 2015.06.09, http://en.wikipedia.org/wiki/Livewire_Segmentation_Techniq ue
4. Dijkstra`s algorithm, Wikipedia, 2015.06.09, http://en.
wikipedia.org/wiki/Dijkstra’s_algorithm
5. MATLAB Live-Wire code, MATLAB Central, 2015.06.09, http://www.mathworks.com/matlabcentral/fileexchange/41084- livewire--intelligent-scissors--roi-creation/content/livewire.zip 6. DICOM image, google image search, 2015.06.09, http://pacspro- fessor.com/what-is-a-dicom-image/#.VT8zXSHtlBd, http://
www.softpedia.com/get/Multimedia/Graphic/Graphic-Viewers/
Agnosco-DICOM-Viewer.shtml
이윤주 외: LiveWire 알고리즘을 적용한 영상 분할 기법
- 11 -
그림 5. DICOM 이미지에 Live-Wire 알고리듬 적용
