거리지로를 이용한 MDCT 영상에서의 기관지 중심선 자동 추출:
COPD 환자에 대한 예비연구
김양욱1・박상준2,3・이규화4・김종효2,3,5・박 준1
1홍익대학교 컴퓨터공학과, 2서울대학교 의과대학 방사선응용생명과학 전공
3 서울대학교 병원 방사선의학연구소
4Georgia Institute of Technology, Department of Computer Science
5서울대학교 병원 영상의학과
Automatic Center-line Extraction for Intrathoraic Airway Trees in MDCT using Distance Map: Preliminary Study with COPD Patients
Yang Wook Kim1, Sang Joon Park2,3, Kyu Hwa Lee4, Jong Hyo Kim2,3,5, Jun Park1
1Department of Computer Science, Hongik University, Seoul, Korea
2Interdisciplinary Program in Radiation Applied Life Science Major, Seoul National University College of Medicine, Seoul, Korea
3Institute of Radiation Medicine, Seoul National University Medical Research Center, Seoul, Korea
4Department of Computer Science, Georgia Institute of Technology, Georgia, USA
5Department of Radiology, Seoul National University Hospital, Seoul, Korea
= Abstract =
Nowadays computer tomography (CT) technology is developed rapidly. Due to the recent technical development improving resolution and scan velocity, CT can obtain detailed images of the anatomy.
Currently, endoscopy is generally used as a tool for clinical diagnosis in the hospital. If we diagnose through quantitative measurement and virtual endoscopy using CT scan images, we can solve the cost problem and pains for patients. Center-line data can be used as an atlas of qualitative analysis and path of virtual exploration. In this reason, we have developed an automated three-dimensional center-line extraction technique using airways in MDCT. Center-line dataset consists of same pattern with voxels which have maximum distance from the boundary. We can obtain a center-line of airway trees with calculating from distance from the boundary and source using euclidean distance. In addi- tion, we made a data structure for analyzing node, branch, and generation of airways. In this paper, we can get detailed information for analyzing the airway structure.
Key words: Center-line extraction, distance mapping, airway data structure, virtual endoscopy
This work was supported by Seoul R&BD Program(10888).
통신저자: 박 준, (121-791) 서울시 마포구 상수동 72-1 홍익대학교 컴퓨터공학과
Tel: 02-320-3032, Fax: 02-332-1653 E-mail: [email protected]
1. 서 론
가상 내시경 방법은 의료 영상처리와 컴퓨터 그래픽 기술의 통합기술로 기존의 내시경을 대체하는 방법으로서 개발되었다.
이 방법은 기존의 방법에 비해 많은 장점을 가지는데 비침습성 (noninvasive)으로 인해 환자의 고통이 없고, 비용이 적게 들 며, 높은 정확도를 가지고, 부작용이 적다는 점 등의 장점이 있 다. 이런 가상 내시경을 위해서는 해당 기관(organ)의 중심선 추출 과정이 선행되어야 한다. 이러한 중심선은 가상 내시경의 카메라 경로로 사용될 수 있고, 그 구조는 기관의 구조와 기능 을 분석하는데 도움이 된다. 기관지(airway) 구조의 생리학적 인 측정은 기관지의 기하학적 구조와 형태에 달려 있기 때문에 건강한 폐와 병을 질환을 동반한 폐를 구분하기위해 그 구조를 정확하게 측정하는 것은 중요하며 중심선은 이러한 분석의 척 도로 사용될 수 있다 [1]. 이런 가상 내시경을 위한 중심선 추 출 알고리즘은 이전부터 많이 연구되어 왔다. 중심선 추출 방 법 알고리즘은 크게 3가지로 분류되는데 수동추출, 위상 세선 화(topological thinning), 그리고 거리지도(distance map)를 이 용하는 방법 등이다 [2].
먼저, 수동추출 방법은 사용자가 직접 수백 개의 영상에 표 시하는 것으로 충분한 점들을 선택한 후 선형 혹은 높은 차수 의 보간법을 사용해 중심선을 얻을 수 있다 [3]. 그러나 이 방 법은 시간이 오래 걸리는 지루한 방법이며 그 결과가 다른 방 법들에 비해 정확하지 않은 단점을 가진다.
두 번째 방법은 위상 세선화방법이다. 이 방법은 오래전부터 정확한 결과가 나온다고 알려져 있다. 볼륨을 각 층(layer)마다 반복하면서 층을 벗겨 유일한 중심층이 남을 때까지 반복하면 물체의 뼈대(skeleton)를 얻을 수 있다. 비록 이 아이디어는 간 단할지라도 이러한 반복 과정은 많은 시간이 소요된다. 예를 들 어, Hong 등은 크기 데이터의 중심선을 추출하는데 수십 분이 걸렸다 [4]. 이 방법은 계산시간이 지나치게 오래 걸리기 때문 에 실제로 사용하기 힘들다는 단점이 있다.
마지막 방법은 거리지도 방법으로 세 방법 중 가장 빠른 방 법으로 알려져있다. 이 방법은 두 가지 요소를 갖는데, 첫 번째 과정은 사용자가 지정한 시작부분에서 각 복셀(voxel)까지의 거리를 구하는 것이다. DFS(Distance-From-the-Starting point 또는 Distance-From-Source)라고 하는 이 거리는 직 선거리가 아니고 시작점부터 어떤 복셀까지의 경로가 가지는 거리이다. 그리고 두 번째 과정은 시작점으로부터 각 복셀 거 리지도의 기울기를 감소시키는 방향의 최단경로를 구하는 것 이다. 그 결과 최단 경로를 간단한 역추적을 통해 빠르게 추출
할 수 있다. 이런 중심선 추출 알고리즘은 수직, 2D 대각선, 그리고 3-D 대각선에서 이웃하는 복셀의 거리를 어떻게 정의 하느냐에 따라 달라진다. 가장 정확한 거리 측정 방법은 1 -
√
2 -√
3 유클리디언 거리(euclidean distance)방법이다. 이런 거리지도 방법의 가장 큰 장점은 계산이 효율적이고 최단경로 가 물체의 내부에 있도록 보장한다는 점이다. 만약 중심선이 물 체의 내부에 있도록 고려하지 않는다면, 중심선이 물체 밖으로 빠져나갈 수 있다. 그 경우 가상 내시경에서는 큰 문제가 될 수 있기 때문에 중심선이 물체 안에 있도록 하는 것은 중요하다.그래서 최근의 중심선 추출 알고리즘은 추가적으로 각 복셀에 서 벽 까 지 의 거 리 를 고 려 한 다 . 벽 까 지 의 거 리 는 DFB(Distance-From-Boundary)라고 하고, 최단 경로가 보다 중심에 가까이 있도록 해준다. Chen 등은 중심선을 구하기 위 해 DFB값이 최대가 되도록 최단거리를 재배치하였다. 그러나 수정 단계에서 2D 평면 상 최적의 중심선을 찾을 수 없으며, 반복과정에서 전체 경로의 최적화를 보장하지 못하는 단점을 내포하고 있다 [5]. 이러한 단점을 보완하기 위해 Ming 등은 DFB에 기반을 두고, DFS를 동시에 사용하여 중심선을 추출하 였다 [6]. DFS와 DFB를 같이 사용한 이 방법은 대장(colon) 의 데이터에서 빠르고 정확한 중심선을 찾을 수 있었다.
본 논문에서는 기관지 구조의 분석을 위한 중심선 추출과 자 료 구조화의 방법을 제안한다. 이 방법에서는 먼저 중심선의 추 출을 위해 DFS와 DFB를 사용하여 시작점으로부터 가장 거리 가 먼 경로를 찾는다. 그 후, 각 복셀들의 거리 지도를 만들고, 이를 기반으로 가지를 찾는다. 마지막으로 잔가지가 생기는 것 을 방지하기 위해 가지의 수준에 따라 가지치기를 해주며, 기 관지의 구조를 자료구조화 한다. 그리고 이를 3명의 정상 및 3 명의 만성 폐쇄성 폐질환 (chronic obstructive pulmonary dis- ease, COPD) 환자의 증례에 대해 적용하고 속도와 정확성을 분석한다. 이와 같은 본 논문의 구현 사항을 통해 CT 영상에 서의 정확하고 빠른 중심선을 추출할 수 있으며, 기관지 구조 의 정보 분석을 통해 정략적인 측정의 가능성을 볼 수 있다.
2. 본 문
중심선의 개념은 Blum이“어떤 모양에 들어갈 수 있는 가장 큰 공의 중심궤적이다”라고 처음으로 정의하였다 [7]. 즉, 어떠 한 통로의 중심선이라고 할 수 있다. 직장과 같은 튜브 형태를 가지는 물체의 경우, 일반적으로 한 개의 중심선을 가지지만 기 관지나 혈관 등과 같이 보다 복잡한 물체는 여러 개의 복잡한 중심선을 가진다. 이런 복잡한 중심선을 서로 연결해주기 위해 뼈대화(skeletonize)와 같은 과정이 필요하다. 이 과정을 거치
면 보다 간결한 중심선을 얻을 수 있다. 이러한 중심선을 구하 는 방법은 많이 연구되었는데 그에 따르면 중심선은 다음과 같 은 특성을 지녀야 한다 [6].
1) 연결성 (connectivity)
연결성은 중심선이 시작부터 모든 끝지점까지 연결되어 있 어야 한다는 것을 의미한다. 3차원 공간의 경우, 26-연결도를 가지고 모든 중심선이 연결되어 있어야 한다. 연결성은 주어진 모델을 D라 하고, D의 내부영역을 R, 그리고 R을 지나는 중심 선을 C라고 할 때 식 1. 로 나타난다.
∀v0∈EXIST → v1∈C ∧ v1∈δ(v0)... (1) δ(v0)는 v0과 v1을 직접 연결하는 복셀의 집합이고, δ(v0)는 v0
과 v1을 연결하는 복셀의 집합이다.
2) 중심성 (centrictiy)
중심성은 중심선이 3차원 공간에서 각 외벽과 가능한 멀리 떨어진 곳으로만 지나야 한다는 것을 의미한다. 이것은 경로를 찾을 때 벽에 부딪치거나 뚫고 가지 않게 하고, 날카로운 코너 를 지날 때에도 벽에 닿지 않게 해준다.
3) 단일성 (singularity)
단일성은 중심선이 하나의 복셀 크기로 연결되어 있음을 의 미한다. 이것은 내시경의 경로 설정을 할 때 중요하게 작용한 다. 그리고 이를 위해서는 식 2의 조건을 만족시켜야 한다.
∀v2∈R ∧ v2∈δ(v2) ∈δ(v1) → v2∉C... (2)
4) 인지성 (detectability)
인지성은 만약 벽에 구멍이 있거나 가지가 있는 경우 무한루 프에 빠지거나 구조가 복잡해 질 수 있는데 이런 루프를 발견 하고 적절한 조치를 취해줄 수 있어야 하는 것을 의미한다.
5) 강력함 (robustness)
강력함은 중심선 추출 알고리즘은 어떤 데이터라 하더라도 안정적인 결과를 내야 한다는 것을 의미한다.
6) 자동성 (automation)
자동성은 중심선 양 끝 점들의 위치가 자동으로 결정될 수 있어야 한다는 것을 의미한다. 기관지의 경우 시작점은 하나이 지만 끝은 여러개로 갈라지므로 여러개의 끝점이 존재하게 된 다.
7) 효율성 (efficiency)
효율성은 중심선 추출 알고리즘이 PC(Personal Computer) 플랫폼에서 돌아갈 수 있을 정도로 효율적인 것을 의미한다.
이 논문에서는 위와 같은 특성을 가지는 중심선을 찾기위해 Ming 등이 제안한 알고리즘을 사용하여 기관지의 중심선을 추 출하였다 [6].
2.1 중심선 추출 알고리즘
중심선은 시작점으로부터 길이가 가장 긴 가지로 시작점으 로부터 가장 멀리 떨어진 지점까지의 경로로 정한다. 시작점으 로부터 각 복셀까지의 거리는 DFS라고 하는데 이것은 시작점 으로부터의 유클리디언 거리이다. 그리고 중심선은 벽으로부터 가장 멀리 떨어져야 하기 때문에 DFB가 가장 큰 값을 가지는 복셀들로 이루어진다. DFB를 사용해 각 복셀의 가중치 그래프 를 만든다. 복셀의 가중치는 1/DFB로 이루어지며 그림1과 같 다.
이 1/DFB값을 가지고 최소비용 신장트리 (Minimum cost Spanning Tree:MST)를 만들고 DFB값이 커지는 방향으로 진 행하게 한다. DFB가 커지는 방향은 1/DFB가 가장 작은 값을 가지는 방향으로 진행하는 것과 같기 때문에 1/DFB를 사용하 여 시작점으로부터 모든 복셀들을 한번씩 방문하면서 아래의 알고리즘을 통해 각 복셀의 가중치 그래프를 사용하여 다음과 같이 발생가능한 모든 경로를 만든다.
1) 시작점 S를 표시하고, S를 현재노드로 정의한다. 이것의 경로를 빈 경로 (NULL)로 설정하고 이것의 DFS를 0으로 설 장한다. DFS(V)는 시작점 S로부터 해당 복셀 V까지의 누적 거 리를 의미한다.
2) 현재노드 C 주변의 표시되지 않은 26개의 이웃들 B를 정 렬된 힙에 넣고, 이것의 경로를 C로 향하게 한 후, 이것의 DFS(B)를 DFS(C)+DIS(B,C)로 계산한다. DIS(B,C)는 B와 C
그림 1. 각 복셀의 가중치 그래프(refer to [6])
의 유클리디언 거리이다.
3) 힙(heap)의 첫 번째 원소를 꺼내 DFS와 DFB를 설정한 후 현재 노드(C)로 설정한다.
4) 힙이 완전히 빌 때까지 2, 3의 과정을 반복한다.
본 논문에서는 시작점을 자동으로 설정하기 위해 3-D 데이 터의 Z축 상의 처음과 마지막에서부터 검색하여 기관지의 두 께가 두꺼운(단면의 너비가 넓은) 슬라이스의 무게중심점에서 부터 시작한다. 구역화 등의 처리과정에서 Z축 방향에 대한 저 장 순서가 바뀌는 경우가 있으므로 기관지를 촬영한 마지막 슬 라이드와 첫 번째 슬라이드를 같이 비교한다.
이러한 과정을 통해 DFB가 큰 경로를 따라 시작점을 향하 도록 자료구조가 만들어진다. 이를 이용해 가장 멀리 떨어진 점 (DFS가 가장 큰 점)에서 시작점으로 연결시키면 중심선의 경 로를 구할 수 있다.
2.2 가지 (branch) 구하기
가지의 경우 2.1에서 생성한 자료구조를 바탕으로 다음의 순 서를 따른다. 그림 2에서는 가지 추출 알고리즘을 대략적으로 보여주고 있다.
1) 중심선의 마지막 점 E에서 시작점 S까지의 경로를 따라 검색한다.
2) 각각의 중심선 복셀 C마다 24개의 이웃들(즉, 중심선의 양 끝 두 이웃은 제외하고)을 검사하고, C를 향하는 경로를 가
지고 있는 복셀들Bi를 찾는다.
3) 직접적 혹은 간접적으로 경로가 각각의 복셀Bi로 설정되 어 있는 모든 주변 복셀들을 찾고, 복셀 C를 이들과 가장 가까 운 중심선 복셀로 기록한다. 그리고Ti, 즉 가장 큰 DFS을 갖 는 복셀을 찾아낸다. 만약 DFS(Ti)가 사용자가 정한 가지 길 이의 기본 임계치 L보다 크다면, 이Ti를 중심선 복셀 C로부터 이것의 이웃Bi를 통해 자라나는 가지의 끝점으로 표시한다. 이 가지의 길이는 DFS(Ti)-DFS(C)로 계산된다.
이를 이용하면 1차 수준의 가지를 찾아낼 수 있는데 전체 가 지를 찾아내기 위해서는 기존에 찾았던 가지를 중심선으로 하 여 위 알고리즘을 수행한다. 이 과정을 반복하면 중심선에 연 결된 가지들을 찾아낼 수 있다. 이 때 가지의 길이에 대한 임
그림 2. 중심선과 가지추출방법
그림 3. 중심선과 가지의 정보 저장 방법(refer to [1])
계치를 두어 잔가지가 생기는 것을 방지한다. 임계치를 설정 할 때, 각 노드의 수준에 따라 다르게 주어 보다 효율적인 가지치 기를 하도록 한다.
2.3 중심선과 가지의 정보저장
중심선과 가지를 찾는 과정에서 시작점, 가지가 나누어지는 점, 그리고 중심선이 끝나는 점들에 대한 정보를 저장한다. 이 정보는 생성된 순서를 가지는 노드 번호, 해당 노드의 레벨, 부
모 노드의 번호, 해당 노드의 위치, 자식노드의 수, 노드의 종 류(시작, 가지, 끝), 거리(직선거리, 시작점부터의 거리) 등을 가진다. 이 정보는 간단하게 각 가지가 얼마나 많은 자식을 가 지고 있는지 알게 해주고, 부모노드에 대한 정보도 제공한다.
만약 어떤 노드가 한 개의 자식을 가진다면, 그것은 일반 노드 이다. 만약 두 개 혹은 그 이상의 자식을 가진다면, 그것은 분 기가 이루어지는 노드이다. 그리고 만약 자식 노드가 존재하지 않는다면, 그것은 마지막 노드이다. 이러한 정보를 통해 트리를 보다 간략하게 할 수 있고, 필요 없는 노드에 대해 가지치기 할
표 1. 6개 기관지 데이터의 실험 결과(시간은 초 단위)
데이터 Airway 1(normal) Airway 2(normal) Airway 3(normal) Airway 4(COPD) Airway 5(COPD) Airway 6(COPD) 유효Data size 512×512×335 512×512×334 512×512×171 512×512×354 512×512×341 512×512×177
중심선 길이 466.10 485.39 285.09 524.37 482.88 294.99
중심선추출시간 3.22 2.8 0.64 3.58 2.91 0.92
노드의 수 41 38 34 68 56 12
최대 노드레벨 6 5 5 7 7 3
가지추출시간 2.02 2.63 0.66 3.39 2.81 0.92
총 시간 6.28 5.49 1.31 7.05 5.78 1.86
A B C
D E F
그림 4. 기관지의 중심선 추출 결과. (A)~(F)는 순서대로 데이터1~6이다.
수 있다. 그림 3는 중심선과 가지들에 대한 정보를 보여준다.
3. 실험 결과
본 연구의 성능을 평가하기 위한 실험대상으로 흉부 CT 영 상을 이용한 환자 6명의 증례로 남녀 및 나이에 구분 없이 정 상 3명, COPD 환자로 의심되는 3명의 증례에 대해 분석하였 다. 중심선을 찾고, 중심선 노드들의 정보를 저장하는 과정에서 INTEL Q6600 CPU, 2GB 메모리에서 평균적으로 14.07초가 소요되었다. 데이터들 중 네 개의 데이터는 512×512×380의 볼륨데이터이고 나머지 2개는 512×512×280의 볼륨 데이터 이다. 380장의 경우에는 평균 17.47초가 소요되었고, 280장의 경우 7.27초가 소요되었다. 이 모든 시간은 파일 입출력, 메모 리 할당과 해제, 중심선 추출, 가지 추출 등을 하는데 소비된 시간을 통합한 것이다. 표 1은 기관지의 중심선 추출 결과와 추 출하는데 걸린 시간을 보여준다.
각 기관지의 추출 결과는 그림 4와 같다.
실험 결과 모든 데이터에서 중심선과 가지의 경로가 적절히 추출되었다. 알고리즘의 수행에 걸리는 시간은 데이터의 크기 에 따라 차이를 보였고, 중심선의 길이가 길수록 오랜 시간이 소요되는 것을 확인하였다.
4. 결 론
본 논문에서는 거리지도 방식의 알고리즘을 기반으로 하여 기관지의 중심선을 추출하고 트리 구조의 자료형을 분석해 보 았다. 중심선의 추출을 위해 DFS와 DFB를 이용하여 시작점으 로부터 가장 멀리 떨어진 경로를 찾고, 각 복셀들의 거리지도 를 만든다. 그리고 이 과정에서 가지를 찾고, 잔가지가 생기는 것을 방지하기 위해서 각 노드의 수준에 따라 임계치를 적용하
여 가지치기 해주었다. 이때 임계치는 기관지 세대의 수준에 따 라 다른 임계치를 가지도록 적응적으로 적용하였고, 그 결과 보 다 세밀한 가지들을 추출할 수 있었다. 그 후 중심선 추출과정 에서 얻어진 자료를 갖고 자료구조화 하였다. 우리는 이를 통 해 각 복셀을 노드, 가지, 세대 등으로 구분할 수 있었고, 각 노 드들의 정보를 통해 시작점으로부터의 거리에 대한 상세한 정 보를 탐지할 수 있었다. 이와 같은 본 논문의 방법을 이용해 기 관지 벽두께 측정 혹은 가상 내시경과 같은 분석의 전처리 단 계로서 정확한 기관지의 구조의 정보를 획득할 수 있으며, 형 태학적 분석을 통해 질환을 정확히 진단, 예측할 수 있을 것이 라고 기대한다.
참 고 문 헌
1. Chaturvedi A, Lee Z. Three-dimensional segmentation and skeletonization to build an airway tree data structure for small animals. Phys. Med. Biol. 2005;50:1405-1419
2. Bitter I, Sato M, Bender M, McDonnel K, Kaufman A, and Wan M. CEASAR: A smooth, accurate and robust centerline extration algorithm. in Proc. Visualization 2000:45-52
3. Ge Y, Stelts D, and Vining D. 3-D skeleton for virtual colonoscopy. in Proc. 4th Int. Conf. Visualization in Biomedical Computing(Lecture Notes in Computer Science) 1996:449-454
4. Hong L, Muraki S, Kaufman A, Bartz D, and He T. Virtual voyage: Interactive navigation in the human colon. in Proc.
SIGGRAPH 1997:27-34
5. Chen D, Li B, Liang Z, Wan M, Kaufman A, and Wax M. A tree-branch searching multiresolution approach to skeletoniza- tion for virtual endoscopy. Proc. SPIE Med. Imag.
2000;3979:726-734
6. Wan M, Liang Z, Ke Q, BItter I, and Kauffman A. Automatic Centerline Extraction for Virtual Colonoscopy. IEEE Trans Med. Imag. 2002;21:1450-1460
7. Blum H. A transformation for extracting new parameter of shape. In Models for the Perception of Speech and Visual Form, Cambridge. 1967;MA:MIT press
대한의학영상정보학회지 2007;13:12-18
=초 록=
CT (Computed tomography) 기술은 근래에 들어 비약적으로 큰 발전을 이룩하였다. 이렇듯 발전된 기술은 의료 영상의 획득에 있어 높은 해상도(resolution)의 영상을 얻을 수 있게 함과 동시에 보다 정확한 장기의 해 부학적 정보를 얻을 수 있게 해 주었다. 현재 병원에서는 진단의 한 도구로서 내시경 검사법을 사용하고 있는 데, CT를 통해 얻은 영상으로 정량적인 측정 및 가상 내시경(virtual endoscopy)을 통한 검사가 가능하다면, 기존의 내시경 검사법이 갖는 여러 단점, 즉 환자의 고통 및 비용적인 측면 등을 해소할 수 있다. 이러한 컴퓨 터를 이용한 처리를 위한 기법의 하나로서 먼저 해당 기관(organ)의 데이터를 통한 중심선 획득이 선행되어야 한다. 이러한 중심선은 정질적인 분석의 척도로 삼을 수 있으며, 가상 내시경의 카메라 경로로도 사용될 수 있 다. 이와 같은 이유로 본 논문에서는 기관지(airway) 영상에 적용한 빠르고 정확한 중심선 추출 기법에 관해 아래와 같은 방식으로 제안한다. 우선, 중심선은 해당 기관의 벽으로부터 안쪽으로 거리가 최대가 되는 복셀 (voxel)들의 패턴으로 이루어져있다. 중심선은 이 복셀들의 시작점을 기준으로 유클리디언 거리(euclidean dis- tance)를 이용해 가장 먼 복셀까지의 거리와 각 복셀들 간의 외곽 거리의 비교를 통해 구할 수 있다. 그리고 획득한 중심선 데이터를 노드, 가지, 세대 등으로 분석하여 자료 구조화 하였다. 이와 같은 본 논문의 구현사 항을 통해 CT 영상에서의 정확하고 빠른 중심선 추출에 관한 알고리즘을 이해할 수 있으며, 자동화된 처리 절 차를 통해 정략적인 분석이 가능하다 할 수 있다.
