1. 서 론
내시경 시스템은 환자의 인체 내부 기관을 들여다보며 검사 하는 시스템을 말한다. 이러한 내시경 시스템은 인체의 내부를 들여다보기 위해 반드시 필요한 시스템이나, 환자의 거부감과 고통이 극심할 뿐만 아니라 내시경을 이용하여 검사할 수 있는 부위가 한정되어 있다. 이를 보완하기 위해 간접적으로 인체 내 부를 검진할 수 있는 다양한 방법들이 개발되었다. 우리가 일반 적으로 접하는 X-Ray나 CT, MRI 등은 모두 간접적인 방법이 다. 하지만 이러한 의학영상은 이차원의 평면적인 단면 영상만
을 제공함으로써 사실감이 떨어질 뿐만 아니라 인체 내부를 시 각적으로 확인하고 이해하는 데에는 한계가 있다.
이러한 단점을 보완하기 위해 여러 연구에서 인간이 느끼고 지각하는 오감을 인위적인 조작을 통해 마치 현실 같은 착각이 들 정도로 사실감을 높이는 기술인 가상현실 기술을 이용하여 가상 내시경 시스템이 개발되고 있다[1, 2, 3]. 이 시스템은 환 자의 의학영상을 가상환경에서 체험할 수 있는 삼차원 모델로 구성한 후, 의사의 조작에 의해 환자의 내부를 탐험할 수 있는 시스템을 말한다. 이러한 가상 내시경 시스템은 환자에게 고통 을 전혀 주지 않을 뿐만 아니라, 일반 내시경 시스템으로는 검 사할 수 없는 부분, 예를 들어, 심장, 심장 혈관, 뇌혈관 등의 기 관들도 검사를 할 수 있고, 의료영상 데이터만 있으면 언제나 내 시경 검사가 가능하다는 장점이 있다. 하지만 임상의가 관심을
가상내시경 시스템에서의 최적의 경로 추적
윤은진・장동표・구정훈・안희범・신민보・조항준・이재민・김재석・김인영・김선일 한양대학교 의과대학 의공학교실
Optimal Path Planning in Virtual Endoscopy System
Eunjin Youn, Dongpyo Jang, Jeonghun Ku, Heebum Ahn, Minbo Shin, Hangjoon Jo, Jaemin Lee, Jaeseok Kim,
Inyoung Kim, Sun I. Kim
Dept. of Biomedical Engineering, College of Medicine. Hanyang University
= Abstract =
3D Virtual Endoscopy is a method to inspect the inner surface of organs which are visualized by Surface Rendering or Volume Rendering technique. Unlike a real endoscopy, it provides an easy way to investigate the inner surface of very narrow hollow organs, which might be difficult or impossible with real endoscopy. It also provides comfortable and safe way without exposing a patient to infection by foreign substance. In order to guide a viewer to navigate properly with virtual endoscopy, a camera should be confined inside the hollow organ. In this study we used the surface rendering for real time visualization and a collision detection algorithm using a ray and surface intersection. We propose a path planning method which finds an optimal path when starting and target positions are specified.
This method was applied to navigate thin blood vessel of brain and showed that it found the optimal(shortest) path among several possible paths to the target position.
Key words: Virtual Endoscopy, Volume Rendering
이 논문은 1998년 한양대학교 교내연구비 지원으로 연구 되었음
두는 환부의 경로를 삼차원 모델에서 찾아내고 탐험하기 위해 가상 내시경 시스템을 조작하는 것은 상당히 어렵다. 이러한 단 점을 극복하기 위해서 가상 내시경시스템에 MR/CT 등의 단면 영상을 카메라의 위치와 동기화하여 보이도록 하는 방법이 제 안되고 있으나 이는 근본적인 해결책이 되지 못한다. 따라서 본 연구에서는 출발점과 목적지를 지정해주면 자동으로 탐험 시에 적용이 가능한 최적 경로를 탐색하여 제시해주는 방법을 제안 하였다.
2. 방 법
본 연구에서는 Open Inventor와 Visual C++를 이용하여 가 상내시경 시스템을 제작하였다. 이 가상내시경 시스템은 좌측의 단면 영상을 보여주는 창, 위쪽에는 전체 혈관 모델에서 카메라 의 위치를 나타내는 창, 그리고 카메라의 뒤쪽을 보여주는 창으 로 구성되어 있다. 단면 영상을 나타내는 창에서는 현재의 카메 라 위치에 해당하는 영상을 보여주게 되며, 단면영상에서 원하 는 부위를 마우스를 이용하여 지정하게 되면 삼차원 모델에서 의 위치이동이 일어나도록 하여 임상의가 원하는 부위로 쉽게 이동할 수 있도록 하였다. 또한 3차원 모델의 탐험은 마우스의 조작 뿐 만 아니라 아래쪽에 부착되어 있는 스크롤 버튼을 사용 하여 더욱 정교한 탐험할 수 있도록 하였다. 또한 혈관벽을 투 과하지 않도록 하기 위해 충돌 검사를 수행하였으며, 뇌혈관 탐 험 등 복잡한 경로를 가지는 부위의 탐색을 돕기 위해 단면영상 에서 출발점과 목적지를 선택하면 두 점을 잇는 최적의 경로를
자동으로 탐색할 수 있도록 하였다 [4-8]. Fig. 1은 본 연구에 서 개발한 가상 내시경 시스템의 화면 구성이다.
2.1. 충돌 회피 검사
CT 영상 데이터로부터 얻어낸 뇌혈관의 모델은 많은 폴리곤 으로 이루어져 있으며 이들의 면은 화면에 나타나는 뇌혈관의 벽이 된다. 그리고 화면의 시점, 즉 가상 내시경의 가상 카메라 는 위치 벡터와 이동 벡터를 갖고, 충돌 회피 검사는 카메라의 위치 벡터에서 이동 벡터를 더한 위치에 뇌혈관의 폴리곤 유무 를 검사하여 폴리곤이 없을 경우에만 카메라의 이동을 허가함 으로써 충돌과 투과를 회피할 수 있게 한다.
Fig. 2에서 보는 것과 같이 가상 카메라의 위치에서 화살표 방 향으로 이동하기 위해서는 우선 위치 벡터에 이동 벡터를 더한 위치가 폴리곤을 통과하게 되는지 검사한다. Fig. 2의 (a)와 같 이 폴리곤을 통과하지 않는다면 이동이 허가되고 (b)처럼 충돌
Fig. 1. 가상 내시경 시스템 Fig. 2. 가상 카메라의 위치 벡터와 이동 벡터
(a) 이 동 (b) 충 돌
이 발생하면 이동이 허가되지 않는다.
2.2. 자동 경로 추적
경로 추적이란 임의의 고정된 공간에서, 하나의 개체가 초기 위치에서 원하는 최종 위치까지 충돌 없이 연속적으로 이어지 는 경로를 찾는 것이다.
자동 경로 추적을 위해, Fig. 3과 같이 우선 CT 뇌혈관 영상 데이터를 경로가 생길 수 있는 부위와 그렇지 않은 장애물 부분 으로 구분하여 자동 경로를 추적할 수 있는 가상의 구성 공간 (configuration space)을 생성한 다음, 경로가 생길 수 있는 부 분을 선으로 변환한다. 이 단계에서 모든 가능 경로는 그물 구 조의 복잡한 연결구조로 표현되고 경로는 기관의 중심축에 위 치하게 된다. 이러한 그물 구조로 표현된 경로들 중에서 각각의 경로에 대한 거리를 분석하여 최적의 경로를 찾는다.
1) 구성공간 만들기
구성 공간(configuration space)은 경로 추적을 위해 CT 볼 륨으로 된 영상 데이터를 경로가능 여부에 따라 구분하여L`×
M×N 매트릭스로 재구성한 레퍼런스 데이터이다. 이러한 구성 공간을 생성하는 이유는 가상 내시경이 탐색하는 공간은 가상 의 공간이기 때문에 임의의 모든 공간으로 이동이 가능하기 때 문이다. 즉, 내시경은 기관의 내부를 보는 것이 목적이기 때문 에, 경로가 될 수 없는 부분은 처음부터 경로 추적에서 제외시 킨다.
구성 공간에서 경로 생성이 가능한 구간을 오브젝트라 하고, 경로가 되지 못하는 구간을 장애물로 표시한다. 여기서 오브젝 트는 내시경 카메라가 되고, 모든 경로는 오브젝트가 지나갈 수 있는 구성으로 나타내게 된다.
모든 오브젝트는 임의의 시점에서 위치와 방향으로 표현할 수 있으며 크기와 부피를 지닌다. 따라서 위치가 장애물 내에 있지 않더라도 장애물과의 거리가 일정 수준 이하로 줄어 들게되면 장애물과 충돌하게 되는데, 이것을 방지하기 위해 민코브스키 합(minkowski sum)이라는 방법을 이용하여 장애물의 크기를 일정수준 확장시켜 오브젝트의 레퍼런스 포인트가 구성 공간의 확장된 장애물 밖에 존재하게 하였다. 이렇게 함으로서 오브젝 트는 물리적 공간에서 장애물의 밖에 존재하게 된다.
2) 구성공간을 경로 구조 데이타로 바꾸기
경로가 생성될 수 있는 자유 공간에서 경로가 중심 축을 따라 서 생성되기 위해서는 자유 영역을 선형 구조로 표현해야 한다.
볼륨인 자유 공간을 3차원공간에서의 선형 구조로 변환하기 위 해서는 skeleton과 thinning의 두 가지 알고리즘 중의 하나를 사 용한다. skeleton은 가장 가까운 외곽선까지의 거리가 최고인 점 들의 집합으로 정의되고, thinning은 중심축 상의 점들이 존재하 는 디지털 호의 합으로 정의된다. 이 두 가지 알고리즘은 개념 적으로 차이가 날 뿐, 다른 큰 차이는 없다. 이 방법을 적용할 경 우, 가상 카메라의 다중 경로를 구할 수 있다. Fig. 4는 2차원에 서 Thinning 방법을 이용하여 가능 경로를 선으로 나타낸 결과 이다.
Fig. 4. Thinning방법을 이용하여 가능 경로를 선으로 나타낸 결과
오브젝트(cells)
장애물
선형화된 오브젝트 Fig. 3. 자동 경로 추적도
3) 포텐셜 필드
Thinning 방법을 통해 찾은 가능 경로들 중 최적의 경로를 찾 기 위해서 포텐셜 필드 방법을 사용한다. 포텐셜 필드 방법은 구 성공간의 오브젝트와 장애물과의 거리를 계산하여 저장한 후 시 작 위치에서 저장된 값들 중 낮은 값을 가진 위치를 취함으로서 최단 경로를 구하는 방법이다. 다음 수식은 obstacle 혹은 object 를 0-레벨 표면값으로 시작하는 분석 함수를 나타낸다.
P(x,`y,`z)= α/ f(x, y, z)2
f(x, y, z) ≤ f
0Eq. 1.
0
f(x, y, z) ＞ f
0P(x, y, z)는 장애물 혹은 오브젝트의 표면에서의 포텐셜 필 드 값이다. 이 값은 표면 등의 기준과 x, y, z 위치의 셀과의 거 리에 비례/반비례하는 값으로 설정된다. 자동 경로 추적에서는 자유 공간의 셀만을 대상으로 하고, 목적 위치를 제로 레벨로 한 다. 모든 free 셀에 포텐셜 필드 값을 설정하면, 목적 위치에서 멀리 떨어진 셀일수록 더 큰 포텐셜 필드 값을 갖게 된다. Fig.
5는 포텐셜 필드의 값을 그레이 레벨로 나타낸 것이다.
3. 결과 및 토의
가상 내시경을 이용하여 환자의 내부를 검사하는 경우, 충돌 회피 검사를 적용하여 가상 내시경을 통해 보이는 영상이 뇌혈 관 벽을 통해 외부로 벗어나는 일이 없어져 쉽게 내부를 검사 할 수 있게 되었다. 자동 경로 추적을 통해 찾아낸 경로는 원하 는 부위를 지나가는 최적의 경로였으며, 이를 통해 오퍼레이터 의 부담을 덜 수 있게 되었다.
Fig. 6은 제안한 방법을 이용하여 2차원에서 시뮬레이션한 결 과이다.
Fig. 7은 실제 CT 뇌혈관 데이터 영상의 구성공간을 thinning 한 결과를 나타낸 영상이다. 장애물은 희게 나타내었으며, 뇌혈 관 부분이 검은 부분이다. 뇌혈관 내부의 붉은 부분이 thinning 을 통해 뇌혈관을 선형화 한 부분이다. Fig. 8은 Fig. 7의 붉은 부분 중 최적의 경로에 해당하는 부분을 찾아내어 가상 내시경
Fig. 6. Thinning방법과 Potential field방법을 이용하여 구한 2차원 최적 경로
Fig. 7. Thinning방법을 사용한 결과
Fig. 5. 포텐셜 필드 방법 도착위치
출발위치
Fig. 8. 최적 경로 출력결과
의 화면에 그 위치를 출력한 그림이다.
자동 경로 추적을 통해 구한 최적의 경로는 정수형 좌표의 값 으로 경로 리스트에 저장되었으며 사용된 데이터는 뇌혈관 CT 영상이어서 혈관의 크기가 작았다. 이것으로 인해 오차율은 커 졌으나 그 크기는 1 픽셀 이하로 제한되었다.
4. 결 론
본 연구에서 제안한 가상 내시경 시스템은 실제 환자를 이용 하여 만든 삼차원 모델에 가상의 카메라를 설치하여 환자 내부 를 여러 방향에서 동시에 볼 수 있었다. 이것은 현재 내시경이 보는 방향뿐만 아니라 측면과 배면을 동시에 볼 수 있음을 의미 하는 것이다. 가상 내시경 시스템은 내시경이 지나간 부분을 보 여주기 위해 가상의 백미러 카메라를 설치하여 이미 지나쳐간 부분을 보여줄 수 있다. 그리고 현재의 카메라의 위치를 나타내 는 다른 창을 화면에 출력하여 임상의가 현재 내시경의 위치를 잊지 않도록 보조하였다. 일반 내시경을 사용할 경우, 한번 지나 간 자리를 다시 보기 위해 내시경을 다시 그 위치로 옮겨야 하 는 경우나, 임상의가 현재 위치를 잊는 경우가 발생할 수 있기 때문에 이 기능은 매우 유용하게 사용될 수 있다. 또한 혈관벽 을 그대로 통과하여 카메라가 외부로 벗어나지 않도록 하기 위
해 충돌 검사를 수행하였으며, 임상의의 뇌혈관 탐험을 돕기 위 해 단면영상에서 출발점과 목적지를 선택하면 두 점을 잇는 최 적의 경로를 탐색할 수 있도록 하였다.
참 고 문 헌
1. Lichan Hong, Arie Kaufman, Yi-Chih Wei, Ajay Viswambhran, Mark Wax, “3D Virtual Colonoscopy”
2. Richard A. Robb, “Virtual Endoscopy: Evaluation Using the visible Human Datasets and Comparison with Real Endoscopy in Patients”IOS Press, 1997
3. D.P. Jang, Moon H. Han, Sun I. Kim, “Virtual endoscopy us- ing Surface Rendering and Perspective Volume Rendering”, MMVR, 1999Jed Lengyel, Mark Reichert,
4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
“Introduction to Algorithms”, The MIT Press, 1996
5. Rafael C. Gonzales, Richard E. Woods, “Digital Image Processing”, Addison Wesley, 1993
6. Bruce R. Donald, Donald P. Greenberg, “Real-Time Robot Motion PLanning Using Rasterizing COmputer Graphics Hardware”, 1997
7. Marc-Emmanuel Bellemare, Pascal Haigron, Antonie Lucas Coatrieux, “Depth Map Based Scene Analysis for Active Navigation”, SPIE 1999, Paper 3660-24,Session 6.
8. Daniel J. Blezek, Richard A. Robb, “Centerline algorithm for virtual endoscopy based on chamfer distance transform and Dijkstra’s single source shortest path algorithm”, SPIE 1999, Paper 3660-26, Session 6.
