가상순환기계 혈관모델 생성기술
박형욱, 이상민 (한국과학기술정보연구원), 박상진, 박형준 (조선대학교)
[목차]
1 주제
1.1 Parameter 기반 3D 가상혈관 모델 생성 2 의료영상을 이용한 3D 모델 생성 기술 개요
2.1 의료영상으로부터 3D 모델 생성 과정 2.2 대표적인 의료영상
2.3 의료영상 처리
2.4 볼륨 기반 3 차원 가시화 2.5 3 차원 삼각메쉬 생성 2.6 3 차원 자유곡면 생성
3 3D 가상 혈관 모델 생성을 위한 프레임워크 4 3D 모델의 골격모델 생성 방안
4.1 볼륨 데이터의 3D 세선화를 이용한 골격모델 생성 4.2 3D 메쉬 데이터의 축약을 이용한 골격모델 생성 4.3 3D 메쉬 축약 알고리즘 구현 및 적용
5 3D 가상혈관 모델의 자료구조 및 Parameter 5.1 자료구조 및 Parameter
5.2 노드점에서의 단면 정보
6 Parameter 를 이용한 영역별 메쉬 생성 방안 6.1 스킨 메쉬 생성 방법
6.2 브랜치 메쉬 생성 방법 6.3 캡 메쉬 생성 방법 7 가상 혈관 생성 사례 8 맺음말
1. 주제
의료영상으로부터 복원된 3D 모델은 다양한 의료 분야의 진단 및 시술 계획에 활용될 수 있다.
특히, 인체 순환기계 질환 관련 진단 및 치료 분야에서는 혈관의 협착 부위에 대한 정확한 위치를 파악하고, 스텐트(Stent) 장착이나 우회(Bypass) 수술을 대화식으로 계획하기 위해 혈관의 3차원 모델 생성 및 시각화 기능이 유용하게 활용된다. 그러나, 특정 환자의 장기를 측정하고, 해당 의료 영상을 처리 분석하여 이를 토대로 3차원 모델을 생성한 후, 시각화하여 진단 및 수술 계획에 활용하기까지는 상당한 시간이 소요된다. 따라서, 정확하고 빠른 진단 또는 수술 계획에 도움을 줄 수 있는 신속하고 자동화된 혈관모델 생성 방안이 요구된다. 이를 위해 본 보고서에서는 혈관의 형태학적 특징에 기반한 3차원 가상 혈관 모델 생성 방안을 도출하고자 한다.
1.1 Parameter 기반 3D 가상 혈관 모델 생성
혈관 구조의 3차원 모델 생성 및 시각화는 혈관의 이상(질병)에 대한 탐색 및 분석과 같은 진단 목적에 따라, 그리고 혈관 구조 자체가 병적이 아닌 경우의 치료 계획 시나리오에 따라 각기 달라지며, 혈관의 해부학적 정보뿐만 아니라 혈관 표면에 대한 부가적 데이터(혈관 트리(Tree)의 특성, 혈관 형태 등)가 요구된다. 본 컨설팅에서는 의료 영상으로부터 생성된 3차원 혈관 모델을 활용해 다음을 고려하여 정확하고 빠른 혈관 이상 진단 및 수술 계획을 위한 Parameter 기반 3차원 가상 혈관 모델 생성 방안을 모색하고자 한다.
의료영상을 이용한 인체 혈관의 3D 모델 생성 프레임워크 설계
획득된 3차원 혈관 모델로부터 골격(Skeleton) 모델 생성 방법에 대한 조사/분석
골격모델 특징(끝점, 분기점, 골격선 등) 분석 및 추출 방안 연구 및 사례 구현
가상혈관 모델 표현을 위한 자료구조 및 Parameter 설계
Parameter 도출 방안 및 Parameter 기반 가상혈관 모델 생성 방안 도출
2. 의료영상을 이용한 3 차원 모델 생성 기술 개요
최근 의료영상 측정 장비의 발달로 인해 인체 내부에 대한 정확한 촬영이 가능해지면서 의료영상을 이용한 인체 해부학적 구조 및 장기에 대한 3 차원 시각화 및 분석 기술이 의학/치의학/의공학 분야에 도입되어 생체역학 시뮬레이션, 의료진단 및 시술계획, 가상 수술 시뮬레이션, 원격 수술 로봇 등을 위해 널리 활용되고 있다. 이러한 의료영상 데이터의 삼차원 시각화 및 분석의 토대가 되는 기술이 바로 의료 영상을 이용한 삼차원 모델 생성 기술이다.
최근 의료분야에서는 수술 전/후의 영상을 실시간으로 촬영하여 관심 영역의 체내 장기를 3 차원으로 시각화 해주는 기술이 외과적인 수술 계획 및 수술에 보편화 되었으며, 중재적(interventional) 시술 또는 영상유도수술 (image guided surgery) 시에 효율적으로 사용될 수 있다[1]. 이러한 3 차원 모델은 의료용 교육, 법의학(forensics), CAE 기반의 생체역학 시뮬레이션 등 위한 기본 데이터로 활용될 수 있다.
2.1 의료영상 기반 3차원 모델 생성 과정
의료영상을 이용한 신체 특정 부위의 해부학적 구조 및 장기에 대한 3차원 시각화 및 모델 생성을 위해서는 CT 및 MRI 또는 SPECT/PET로부터 3차원 의료영상을 획득한 다음, 노이즈 제거, 영상 개선, 영역 분할 및 추출 등의 적절한 영상처리가 선행되어야 한다. 그런 다음, 추출된 볼륨 영역에 대해 볼륨 기반 또는 곡면 기반의 3차원 시각화 또는 모델 생성이 수행된다. (그림 1 참고)
그림 1. 의료영상을 이용한 3차원 모델 생성 및 응용 과정
볼륨 기반 3차원 응용의 경우, 주로 3차원 시각화에 초점이 맞추어진 경우로서 영상 획득, 영상처리, 볼륨 렌더링 과정이 요구된다. 곡면 기반 3차원 응용의 경우, 3차원 시각화뿐만 아니라 폭넓은 의/공학적 응용에 활용되는 명시적인 3D 모델의 생성 과정이 요구된다. 특정부위의 3차원 모델 생성을 하기 위해서는 영상획득, 영상처리, 삼각 메쉬(mesh) 생성, 자유곡면 생성 등의 과정을 통해 3차원 모델을 생성할 수 있다. 3차원 모델은 적용 범위 및 용도에 따라 삼각메쉬 형태로 충분한 경우도 있으나, 삼각메쉬 보다 부드럽고 간결한 형태를 갖는 자유곡면 모델 형태가 요구된다. 생성된 3차원 모델은 가시화뿐만 아니라 컴퓨터보조시술, 의료용 교육, 의공학, 법의학 등의 다양한 응용분야에서 요소 데이터로 활용이 가능하다.
2.2 대표적인 의료영상
대부분 의료영상은 여러 단면에서 촬영된 영상들이 적층된 형태로 단순한 2차원이 아닌 3차원 볼륨 데이터으로 주어진다. (그림 2 참조) 이러한 볼륨 데이터의 각 원소를 복셀(voxel)이라 하며,
볼륨 데이터는 복셀의 3차원 격자로 표현된다. 일반적으로 의료영상기기에서 얻어진 의료영상은 단면 내에서의 해상도에 비해 단면간의 z축 해상도가 낮다. CT의 경우 복셀 크기 0.5x0.5x2.0(mm)가 보편적이다[2].
그림 2. 의료영상 예: (좌) MRI 영상, (우) 단층영상들
의료영상은 여러 종류의 의료영상기기로부터 얻어지는데 촬영 원리 및 목적에 따라 다양한 영상을 획득할 수 있다. 의료영상은 해부학적 구조를 보여주는 영상과 인체기관의 기능을 보여주는 영상으로 분류할 수 있다. 해부학적 구조를 보여주기 위한 영상에는 컴퓨터 단층촬영 (CT, Computerized Tomography) 영상, 자기공명영상(MRI, Magnetic Resonance Imaging)등이 있다.
인체 기관의 기능을 보여주기 위한 영상에는 단일광전자방출단층촬영 (SPECT, Single Photon Emission Computerized Tomography) 영상, 양전자단층촬영(PET, Positron Emission Tomography) 영상 등이 있다[3].
2.2.1 컴퓨터단층영상촬영장치(CT)
1970년대 초 미국 터퍼츠대의 앨런 코맥(Allan Cormack)과 영국 EMI 연구소의 고드프리 하운스필드(Godfrey Hounsfield)에 의해 컴퓨터단층영상촬영장치(CT: Computerized Tomography)가 개발되었다. X-ray의 단점을 보완하고자 개발된 CT는 신체에 X선을 쏘았을 때 신체를 통과하는 X선 강도가 얼마나 감소했는가를 측정하여 신체 내부 영상을 얻는 것으로, 인체의 내부를 수평, 수직, 관상 면에서 단층으로 볼 수 있다. CT는 기존 X-ray보다 월등히 좋은 해상도와 대조도를 가지고 있으며, 검사 시간이 매우 짧아 움직임이 많은 장기도 촬영이 가능하다[4,5]. 초기의 CT는 화소가 매우 낮았고, 검사한 뒤 영상 재구성하는데 많은 시간이 소요되었으나, 컴퓨터 기술 발달로 인해 최근에는 1024x1024화소를 넘어 매우 정밀한 화소를 가지는 고해상도 영상의 획득이 가능하고 영상 재구성 또한 수십초 밖에 소요가 되지 않는다. 이러한 장점 때문에 오늘날 CT는 머리, 폐, 심장, 뼈, 혈관에 이르기까지 인체의 모든 부위 촬영에 사용되고 있다. (그림 3 참조)
그림 3. 인체 두부의 CT 영상들
2.2.2 자기공명영상(MRI)
자기공명영상(MRI: Magnetic Resonance Imaging)는 핵 자기공명(NMR: Nuclear Magnetic Resonance)이라 불리는 현상을 이용한다. 모든 물체는 자기장 안에 들어가면 자성을 갖게 되며, 자성을 갖게 된 물질은 외부에서 특정한 주파수의 전파를 가하면 전파의 에너지를 흡수하는데, 이를 공명현상이라고 한다. 미국의 폴 라우터버(Paul C. Lautenberg)는 NMR 현상을 의학적으로 이용할 수 있는 기초를 만들었으며, 물 분자에 가하는 자기장의 세기를 달리하면 물 분자에서 방출되는 전차가 신체의 어느 곳으로 방출됐는지 판단할 수 있다는 사실을 발견했다. 또한, 영국의 피터 맨스필드(Peter Mansfield)는 얻은 데이터를 빠르게 영상으로 만드는 기술을 개발했으며, 이 둘의 공로로 인체 내부를 정확히 영상으로 그리는 MRI가 개발되었다.
MRI는 자기장과 고주파를 이용하기 때문에 인체에 해가 적다는 장점이 있다. 근육이나 인대와 같은 연부조직의 해상도와 대조도가 CT보다 훨씬 좋으며, 조영제와 같은 특별한 약물 없이도 고해상도의 혈관 형상을 찍을 수 있다. 이러 장점은 특히 뇌신경계 영상에서 그 진가를 발휘해 뇌 경색과 같은 질환을 진단하고 경과를 관찰하는데 많이 활용된다. [4,5](그림 4 참조)
그림 4. 신체 주요 부위에 대한 MRI 영상
2.2.3 단일광전자방출단층촬영(SPECT)/양전자단층촬영(PET)
단일광전자방출단층촬영(SPECT: Single Photon Emission Computerized Tomography) / 양전자 단층촬영(PET: Positron Emission Tomography)는 양전자를 방출하는 방사성 의약품을 이용해 인체의 생화학적 상태를 3차원 영상으로 나타낼 수 있는 것으로, 1950년 미국의 브루엘이
양전자를 검출할 수 있는 기기를 개발해 SPECT/PET가 탄생할 수 있는 토대를 마련하였다. 이후, 1975년 CT의 개념을 이용해 개발되었다.
SPET/PET를 활용해 신체에 대한 여러 가지 진단을 할 수 있다. 예를 들어 포도당과 비슷한 방사성 의약품을 체내에 주입하면 에너지를 많이 쓰는 암 조직 같은 곳에 쌓인다. 이곳에서 방출된 양전자는 주변의 전자와 만나 사라지면서 방사선을 내는데, 이를 측정하고 영상으로 재구성하면 암 조직을 찾을 수 있다. 사용하는 방사성 의약품의 종류에 따라 쓰임새가 달라지며, 뇌 혈류량 측정, 심장근육의 혈류량 측정, 파킨슨병의 병태생리를 평가 등 최근에는 알츠하이머를 진단할 수 있는 가능성도 열리고 있다[4,5]. CT나 MRI는 체내 조직의 ‘해부학적 변화’를 보기 때문에 질병이 상당히 진전된 뒤에나 발견할 수 있는 반면, SPECT/PET 영상은 생체의 ‘생리화학적 변화’를 볼 수 있기 때문에 질병을 조기 발견할 수 있다. 분해능이 CT나 MRI에 비해 떨어지지만 분자 수준의 변화를 볼 수 있다는 장점 덕분에 SPECT/PET의 중요성은 더욱 커지고 있다. (그림 5 참조)
그림 5. 인체 두뇌에 대한 SPET/PET 영상
최근에는 SPECT/PET의 장점을 살리면서도 분해능을 높이고자 CT, MRI, SPECT/PET를 융합한 SPECT/PET-CT, SPECT/PET-MRI에 대한 연구 개발이 상당히 진행되어 의료진단 및 시술계획에 활용되고 있는 추세이다.
2.3 의료영상 처리
의료영상 처리는 전통적인 디지털 영상 처리분야와 밀접하게 관련되며, 기존 영상처리 및 컴퓨터 비전(computer vision) 기술들이 의료영상 처리를 위해 적용되고 있다. 의료영상 처리는 처리되는 정보 수준에 따라 크게 낮은 단계, 중간 단계, 높은 단계로 나눌 수 있다. 낮은 단계에서는 잡음 제거(noise filtering), 표준화(normalization), 이진화, 영상개선, 다운샘플링(down- sampling), 보간(interpolation) 등 정보처리가 영상 단위에서 정보처리가 이루어진다. 중간 단계에서는 경계 분할(boundary segmentation), 영역 추출(region extraction), 라벨링(labeling), 그룹화(grouping) 등 영상을 분석하여 기호적 표현(symbolic representation)에 대한 정보가 얻어진다. 높은 단계에서는 기호적 표현 정보를 이용하여 영역 특성(위치, 방향, 크기) 분석, 물체 인식 등과 같은 기능적 표현(functional representation)에 대한 정보가 얻어지는데, 흔히 영상이해 또는 패턴인식 과정이라고 한다[2].
그림 6은 전형적인 의료영상 처리 예를 나타낸다. 인체 머리 부위에 대한 MRI 영상으로부터 이진화, 경계추출, 다각형화를 거쳐 머리 외부 윤곽선(contour) 정보를 얻는 과정을 보여준다.
윤곽선은 단면 상에 정의되는 일정한 개수의 점들로 구성된 다각형을 의미한다.
그림 6. 의료영상 처리 예
의료영상 처리 과정에 대한 결과 품질은 3D 형상모델 생성 및 응용 과정의 품질에 큰 영향을 미친다. 다음에는 의료영상 처리 기법들 중 핵심에 해당하는 영상개선과 영역 분할 및 추출에 대해 기술한다.
2.3.1 영상개선
영상을 더욱 유용하게 하고 분석을 쉽게 하기 위한 영상 개선으로는 히스토그램 평균화, 비선형 마스크 처리, 영상여과 및 강조 등의 기법이 주로 활용되고 있으며, 이들은 모든 디지털 영상에서 적용되고 있다. 또한, 이들은 주로 삼차원 영상의 재구성에 필요한 영상처리 기법들이다.
2.3.2 히스토그램 평균화
히스토그램이란, 영상 내에서 각 레벨을 가지는 화소의 개수를 나타내는 함수로 이를 이용한 히스토그램 평균화는 종모양의 Gaussian 분포를 나타내는 원래 데이터의 강도분포를 시스템의 모든 부위에 걸쳐 넓게 분포시킨 후, 균일한 강도분포로 변화시켜 시각농도의 주파수를 균일하게 만드는 기법이다[6,7].
2.3.3 비선형 마스크 기법
비선형 마스크 기법이란 원래 영상에서 감산처리 기법을 이용하여 마스크 이미지를 얻고 이를 원래의 영상에서 감산하여 계면부위를 증강시키는 것으로, 평균 가중치를 활용하기 보다는 비선형적인 연산방법으로 이웃 화소들의 부정적인 요인을 해소 시키는 기법이다. 이는 전체 영상의 농도를 낮추기 보다는 잡음 감소의 경우 사용되며, 마스크내의 정렬 후 중간에 오는 값을 기준으로 영상의 잡음을 제거하는데 효과적이다[7]. (그림 7 참조)
그림 7. 비선형 마스크 기법에 의한 영상 개선 예
2.3.4 영상 보간(interpolation)
볼륨 데이터의 가시화를 위한 많은 알고리즘은 sampling density가 모든 삼차원 내에 동등한 방향성을 갖는 볼륨 데이터를 필요로 하다. 즉, 3차원 단면영상의 Z-축 해상력(정보)은 X, Y-축 방향에 비해 저하되는 것이 통상적인데, 이를 보상하기 위해 Z-축 방향의 데이터 사이에 주위의 데이터를 조합하여 삽입함으로써 Z-축 해상력을 증가시키는 것을 보간법(interpolation)이라 한다.
(그림 8 참조) 대표적인 보간법으로는 인접 영상 사이 강도의 불균일성을 거리의 차에 비례하는 값으로 삽입하여 균일하게 하는 선형 보간법(Linear Interpolation)이 있으며, 이외에도 평균 보간법과 형태 기반 보간법 등이 있다[6,8].
그림 8. 균등한 볼륨과 비균등한 볼륨
2.3.5 영역 분할 및 추출
영역 분할은 영역이나 물체를 구분하여 나누기 위한 것으로 명암도(intensity)에 의하여 수행된다. 의료영상에서 체내 특정 부위의 영역 분할 방법은 대부분 명암도의 두 가지 기본 성질인 불연속성 또는 유사성 중 하나를 기반으로 한다. 불연속성을 기반으로 한 방법은 영상의 윤곽선과 같은 명암도의 급격한 변화를 기반으로 하여 영상을 분할하는 기법으로 선 또는 에지와 같은 Boundary Feature의 분리에 이용된다. 유사성을 기반으로 한 주요 방법들은 유사한 명암도를 갖는 점들을 모아서 유사한 영역으로 분할하는 기법으로 Threshold 방법, Region-based 방법, Morphological watersheds 방법들이 있다[9].
Boundary-based 방법
Boundary 기반 방법은 픽셀 값들이 두 영역의 경계에서 기울기가 빠르게 변한다는 특성을 이용한다. 이 과정에서 대비가 높은 값들은 영역들 간의 경계를 표시하는 폐곡선(closed curve)을 구성하는 에지 후보가 된다. 모서리의 에지 후보 픽셀들을 영역의 경계로 바꾸는 Boundary 기반
방법은 비슷한 값의 분포가 많은 의료영상에서는 만족할 만한 처리 결과를 얻기 어렵다는 단점이 있다[9,10].
Threshold 방법
Threshold 기반 방법은 임계값을 기준으로 영역을 구분하는 단순한 방법이지만 영상 분할에 있어서 가장 많이 이용되는 방법 중의 하나로서 여전히 많은 연구가 진행되고 있다.
의료영상에서는 전역 또는 지역에서 임계값을 기준으로 구분하는 방법을 많이 이용한다. 이러한 방법은 영상의 공간적인 정보들을 무시하게 되며 임계값에 따라 원하는 결과보다 훨씬 작은 영역 또는 노이즈를 포함하는 영역으로 분리될 우려가 있다. 또한, 임계값이 낮은 경우 경계의 블러(blur) 현상에 대해서는 구분이 어렵다[9].
Region-based 방법
Region 기반 방법은 ‘한 영역에서 이웃한 픽셀 값들은 비슷한 값을 가진다’는 특성을 이용하는 것으로 ‘Seeded Region Growing’ 개념으로 불리는 평균값을 이용한 영역 확장 기법이 비교적 정확성이 높은 것으로 알려져 있다. 일반적인 동작 순서는 한 지점에서의 픽셀 값을 이웃 픽셀 값과 비교한 다음, 만약 동일성 측정(즉 비슷한 픽셀 값을 가지는)이 만족 되면, 해당 픽셀은 이웃 픽셀들과 함께 같은 분류에 속하게 된다. 여기에서 동일성 측정을 위한 시작 위치(Seed Point)와 측정값(비교 허용 값)의 선택은 정확한 영역 분리를 위하여 매우 중요하다[9,11]. (그림 9 참조)
그림 9. Region 기반 방법에 의한 영역 분할 예
Morphological Watersheds 방법
Morphological watersheds 방법은 3차원 공간상의 형태를 기반으로 한 분기점(watershed)에 대한 개념을 표현한 것으로 영상정보의 기울기에 적용하여 영역과 영역 간의 경계가 등고선의 형태 지형도로 보여진다. 분할은 시작점으로부터 다른 시작점에 이르는 영역 경계의 형태로 물 흐르듯이 지형도의 모양과 동일하게 이루어지는데, 이러한 watersheds 방식은 설령 여러 영역들 간에 여러 부분이 연결되어 있고 약하게 연결되어 있더라도 닫힌 영역을 생성한다. 그러나 영상 내 영역들에 노이즈가 있거나, 흐릿할 경우 경계를 구분하기 어려우므로 분리해내지 못하거나 실제 영역보다 더 큰 영역으로 분리한다는 문제점을 가지고 있다[12]. (그림 10 참조)
그림 10. Morphological watersheds 방법에 의한 영역 분할 예
이러한 의료영상 처리 기법들은 분할하고자 하는 체내 특정 부위에 특성을 고려하여 활용할 필요가 있다. 특정 부위가 유사한 값이 모여있는 특성을 가질 경우, 유사한 값을 가진 영역을 포함시키며 확장해가는 영역 확장 기법이 좋은 결과를 보이며, 해부학적으로 얇은 구조를 가지는 부위일 경우, 대부분의 기법들은 영역 분할을 실패하거나 원래 영역보다 훨씬 큰 영역으로 분할하는 경우가 자주 발생하므로 이들을 조합하여 보다 정교한 분할이 가능하도록 해야 한다.
2.4 볼륨 기반 3차원 가시화
의료영상의 가시화 방식은 크게 표면 렌더링(surface rendering)과 볼륨 렌더링(volume rendering)으로 구분된다. 표면 렌더링은 의료영상으로부터 원하는 객체의 표면을 추출한 후, 이를 표준 그래픽스 기법을 통해 시각화 한다. 객체 표면은 대부분 메쉬 또는 자유곡면 등으로 표현된다. 따라서, 표면 렌더링을 위해서는 의료영상으로부터 3차원 형상모델 생성이 선행되어야 한다[13].
볼륨 기반 3차원 가시화는 볼륨 렌더링에 의거한다. 객체 표면만 아니라 볼륨데이터 전체를 렌더링 과정에 이용하는 볼륨 렌더링은 원하는 객체에 해당하는 정도에 따라 각 복셀에 0-100 사이의 불투명도를 지정한 다음, 각 복셀에서 투과, 방사, 반사되는 빛이 화면 픽셀에 얼마나 도달하는 가를 계산하는 광선투영법(ray casting)을 바탕으로 한다. 그림 11은 볼륨 렌더링 원리와 적용 예를 나타낸다 [3,13].
그림 11. 볼륨 렌더링 원리 및 예제
볼륨 렌더링 방식은 한번에 많은 반투명 객체들은 가시화할 수 있으나, 시점이 변동되면 광선투영법이 반복 수행되어야 하므로 상당한 계산량을 요구한다. 보통 볼륨 렌더링을 대화적 속도로 수행하려면 상당한 하드웨어 자원이 요구되므로 전체 볼륨 데이터 중 관심 영역에 대해
광선투영법을 적용하여 계산적 효율성을 향상시키려는 노력이 시도되고 있다.
2.5 3차원 삼각메쉬 생성
의료영상으로부터 3차원 모델을 생성하기 위해서는 원하는 물체 표면에 해당하는 밝기 값을 갖는 복셀들을 이용하여 삼각메쉬 (Triangular Meshes)를 생성하는 방식이 주로 활용된다. 이러한 방식은 3차원 의료 데이터로부터 삼각메쉬를 직접 생성하는 것으로 정보의 손실이 없다는 장점이 있지만, 처리시간이 오래 걸리는 단점이 있다. 대표적인 삼각메쉬 생성 방식은 복셀 데이터 기반 방식과 2D 윤곽선 기반 방식이 있다.
2.5.1 복셀 데이터 기반 삼각메쉬 생성
마칭큐브
마칭큐브(Maching Cubes)는 표면을 시각화 하기 위해서 이용되는 대표적인 기법으로 널리 사용되는 기법으로 1987년 Lorensen과 Cline에 의해 개발되었다[14]. 이 방법은 볼륨 데이터를 이진 분할(binary segmentation)하여 표면의 안쪽과 바깥쪽으로 구분하는데, 이는 특정 경계값 (Threshold value)과의 비교로 이루어 지거나 복잡한 영상처리 기법으로 생성될 수 있다. 그런 다음, 인접한 8개의 복셀에 대해 하나의 셀을 이루고, 각 셀의 상태에 따라 객체 표면을 이루는 삼각형들을 차례로 생성한다.
셀의 상태는 8개의 복셀 안쪽과 바깥쪽 여부에 따라 총 256가지로 표현되며, 대칭성을 고려하여 15가지 경우로 축소될 수 있다. (그림 12 참조) 따라서, 이를 15개의 인덱스를 갖는 참조 테이블로 만들어 고속으로 개체 표면을 표현하는 삼각메쉬를 생성한다. 이렇게 생성된 표면을 단일값-표면(isosurface)라고 한다.
그림 12. 삼각형 생성을 위한 15가지 경우
생성된 삼각메쉬를 렌더링하기 위해서는 삼각메쉬의 각 정점에서의 법선벡터를 추정해야 하는데, 기본적인 방법은 식(1)에 의거하여 각 복셀에서의 그래디언트(Gradients) 기반 법선벡터
( , , )
N i j k 를 구한 후, 인접한 두 복셀의 법선벡터를 보간하여 정점에서의 법선벡터를 구하는
것이다. 여기서, F i j k( , , ) 는 복셀 ( , , )i j k 번째의 밝기 값에 해당한다. 그 외에도 각 정점을 공유하는 인접 삼각형들의 법선벡터에 대한 가중치 평균(weighted average)을 해당 정점의
법선벡터로 추정하는 방식이 있다[2]. (그림 13 참조) ( , , ) ( , , )
( , , ) N i j k N i j k
N i j k
(1)
( 1, , ) ( 1, , ) 2
( , 1, ) ( , 1, ) ( , , )
2
( , , 1) ( , , 1) 2
F i j k F i j k x
F i j k F i j k N i j k
y F i j k F i j k
z
그림 13. 마칭큐브 기법 적용 예
일반적으로 볼륨데이터를 다운샘플링하지 않고, 마칭큐브 기법을 적용하면 삼각메쉬를 이루는 삼각형의 개수가 매우 커져서 렌더링 및 후속 응용에 부담을 준다. 또한, 볼륨 데이터의 이진 분할이 부정확한 경우, 잡음이 포함되거나 유효하지 않은 삼각메쉬가 생성될 수 있다.
확장형 마칭큐브
확장형 마칭큐브(Extended Marchig Cubes)는 기존의 마칭큐브 방식에서 표현하지 못했던 꼭지점이나 모서리와 같은 날카로운 부분을 보다 잘 표현하기 위해 제안된 방법이다[15]. 기존의 마칭큐브 방식은 격자의 각 꼭지점에서 표현하고자 하는 곡면까지의 선형보간(Linear Interpolation)을 통해 격자의 각 모서리 위에 패턴 연결을 위한 정점의 위치를 결정하였다. 이때 선형 보간법은 정확성이 떨어지기 때문에 이를 보상하고자 확장 마칭큐브에서는 격자의 각 모서리에서 직접 샘플링된 점을 이용해 x, y, z-축 방향에 대한 거리 데이터를 생성하고 샘플링된 점의 법선벡터를 함께 저장한 다음, 이들을 이용해 날카로운 부분을 포함한 격자과 그렇지 않은 격자로 구분한다[16].
날카로운 부분을 포함하지 않은 격자의 경우 격자의 모서리에서 샘플링된 점과 법선 벡터를 이용해 기존의 마칭큐브 알고리즘과 동일한 방법으로 메쉬를 생성하고, 날카로운 부분을 포함하는 격자의 경우 다시 꼭지점을 포함하는 격자와 모서리를 포함하는 격자로 나누어 날카로운 부분을 포함하는 새로운 격자를 찾아 각 모서리에서 샘플링된 점과 법선벡터를 가지고 격자 내부에 새로운 정점의 위치를 결정한다. 꼭지점을 포함하는 격자와 모서리를 포함하는 격자로 구분하는 방법은 식(2)와 같다.
|
|
max
:
),
,
(
min
:
i,jn
iTn
j
in
iTn
*
(2)
는 격자의 모서리에서 샘플링된 법선 벡터들이 이루는 각의 코사인 값이며
thresh 인경우 날카로운 특징을 포함하는 격자로 분류 할 수 있다. n* 는 두 법선 벡터의 외적(Cross Product)을 뜻하며,
thresh 인 경우 최종적으로 날카로운 모서리를 포함하는 격자로 분류된다.(그림 14 참조)
그림 14. (좌)격자 모서리에서 샘플링된 점과 법선 벡터, (우)날카로운 부분으로 분류된 격자
날카로운 모서리를 포함하는 격자가 찾아지면 2차 에러 함수(Quadratic Error Function)를 이용하여 격자 내부에 새로운 정점의 위치를 결정한다. 이때
p
i 는 샘플링된 점의 위치이며,n
i는 그 점의 법선 벡터를 나타낸다.
i
i
i
x p
n
x
E ( ) ( ( ))
2 (3) 그런 다음, 각 정점을 삼감형 팬(Triangle Fan)의 형태로 잇고, 최종적으로 에지 플리핑(Edge Flipping)과정을 거쳐 날카로운 부분까지 보다 잘 표현된 모델을 얻는다. (그림 15 참조) 이 외에 확장형 마칭큐브를 개선한 듀얼 컨투어링 방식이 있는데, 이는 확장형 마칭큐브에서 수행되는 에지 플리핑 과정을 제거하여 보다 빠르게 삼각메쉬를 생성하는 방식이다.그림 15. 확장형 마칭큐브 결과: (좌)에지 플리핑 전, (우)에지 플링핑 후
2.5.2 2D 윤곽선 기반 삼각메쉬 생성
윤곽선 기반 삼각메쉬 생성 방식은 의료영상처리를 통해 각 단면에 존재하는 윤곽선을 추출하여 다각형으로 근사하고, 인접 단면 내의 다각형들간의 연결관계를 고려하여 표면을 정의하는 삼각메쉬를 생성하는 방식으로 볼륨 데이터 기반 삼각메쉬 생성에 비해 용량이 작으며, 적절한 영상처리를 거친 윤곽선들에 대해 비교적 양질의 결과를 얻을 수 있다는 장점이 있다.
그러나, 영상처리에 상당한 노력과 시간이 소요될 수 있으며, 생성에 있어 세가지 주요한 문제들이 존재한다[17]. (그림 16 참조)
그림 16. 세가지 주요 문제
첫째, 연결관계 결정 문제로서 인접한 단면 내에 존재하는 윤곽선들간의 관계를 결정하는 문제이다. 이 문제는 각 단면내에 여러 개의 윤곽선이 존재할 때 발생하는 것으로 두 윤곽선이 해당 단면위에서 근사적으로 동일한 위치에 놓인다는 가정하에 휴리스틱 기법을 통해 연결관계를 결정할 수 있다. 둘째, 타일링 문제로서 일대일 연결 유형으로 정의되는 표면을 삼각형들로 연결하는 문제이다. 이는 최단경로탐색 문제를 응용한 최적해 및 휴리스틱 기법을 통해 가능하다.
셋째, 블랜칭 문제로서 일대 다 또는 다대다 연결 유형(그림 17 참조)으로 정의되는 표면을 삼각형들로 연결하는 문제이다. 이 문제는 타일링 문제보다 모호함이 훨씬 많이 내재되어 있어 사용자 개입이 필요한 경우가 발생하지만, 일대다 연결 유형을 해결하기 위해 브랜치 유형을 말안장(saddle), 협곡(canyon), 마루(ridge)로 구분하여 각각을 삼각형화 하거나, 윤곽선 연결 그래프(Contour Connection Graph)를 이용하여 각 단면에 위치하는 복수개의 윤곽선들로부터 복합 윤곽선(composite contour)과 협곡 윤곽선(canyons)들을 생생한 후, 브랜칭을 타일링과 윤곽선 밀폐(contour closing)로 분할하는 등 자동화된 해를 제공하는 휴리스틱 기법들이 제시되어있다[18,19]. 그림 18은 인체 고관절 부위 MRI 영상에 대해 2D 윤곽선 기반 삼각메쉬 생성 기법을 적용하여 얻어진 삼각메쉬를 나타낸다[2].
그림 17. (좌)일대다 연결 유형과 (우)다대다 연결 유형에 대한 브랜칭
그림 18. 2D 윤곽선 기반 삼각메쉬 생성 예
2.5.3 삼각메쉬 개선
3차원 삼각메쉬 생성방법을 통해 얻어진 삼각메쉬는 삼각형 개수가 불필요하게 많거나, 잡음이 포함되거나, 유효하지 않은 삼각형들을 포함할 수 있다. 따라서, 삼각메쉬의 품질을 개선시키는 과정이 요구된다. 대표적인 메쉬 개선 기법들로는 잡음 제거, 부적절한 삼각형 처리, 불필요한 영역 제거, 구멍 채우기, 리메슁(remeshing), 데시메이션(decimation) 등이 있다. 이러한 기법들은 최근 삼차원 측정기술 및 역공학(reverse engineering) 기술의 발전과 함께 상당한 진보를 거두었다[20]. 그림 19은 데시메이션 기법의 적용 예를 나타낸다.
그림 19. 데이메이션 적용 예[2]
2.6 3차원 자유곡면 생성
삼각메쉬 자체만으로 3차원 형상모델로서 많은 분야에서 활용될 수 있지만, 보다 매끄러운 곡면을 갖는 형상모델을 얻고자 하는 경우가 있다. 이런 경우, 삼각메쉬로부터 자유곡면을 생성하는 기법을 적용할 수 있다. 자유곡면을 표현하는 방법은 CAGD 분야에서 널리 연구되어 왔는데, 크게 음함수(implicit equation)와 매개변수 함수(parametric equation)를 이용하는 방법으로 나눌 수 있다[21-23].
음함수를 이용한 곡면 표현 방법은 f x y z ( , , ) 0 와 같은 수식을 이용하여 물체의 경계를 표현하는데, 대표적으로 이차곡면(quadric surface)을 이용하는 방법이 있으며, 매개변수 함수를 이용한 곡면 표현 방법은 S u v( , )x u v( , ), ( , ), ( , )y u v z u v와 같은 형태로 물체의 표면을 표현하는데, Bezier 단위곡면, B-spline 곡면, NURBS 곡면 등을 이용한 방법이 대표적이다. 최근에는 분할곡면(subdivision surface)을 이용하는 방법이 많은 관심을 받고 있다. 분할곡면의 원리는 초기 성긴 메쉬(initial mesh)를 간단한 규칙에 따라 반복 분할함으로써 궁극적으로 부드러운 극한 곡면(limit surface)이 얻어진다는 것이다. 메쉬를 분할하는 규칙에 따라서 Doo-Sabin 분할곡면, Catmull-Clark 분할곡면, Loop 분할곡면 등의 여러 종류가 있으며, 각각 결과 곡면의 형태가 조금씩 다르게 나타난다[24-26]. 음함수를 이용하는 방법은 주로 컴퓨터 그래픽스 분야에서 일부 사용되고 있으며, 매개변수 함수를 이용한 방법은 산업계 전반적으로 널리 사용되고 있다. 현재 자유곡면 표현을 위한 산업계 표준으로 Bezier, B-spline, NURBS 기반 곡면들이 사용되고 있다[2].
2.6.1 고려사항
임의의 복잡한 형상을 표현하는 일반적인 단일 곡면식(single surface equation)을 찾는 일이 매우 어렵기 때문에 다루기 쉬운 형태의 단위곡면들을 서로 연결하여 전체 곡면을 표현하는 단위곡면 재단작업(patchwork) 방법들이 주로 연구되었다. 이러한 단위 곡면 재단작업은 다음과
같은 몇 가지 고려사항이 존재한다.
첫째, 재단작업에 사용될 단위곡면 종류의 결정이다. 단위곡면은 크게 삼각 및 사각 단위곡면으로 나누어지는데, 삼각 또는 사각 단위곡면을 사용할 것인가 혹은 두 가지를 병행할 것인가에 따라 각각 다른 방법이 적용된다. 그림 20는 3차 삼각 Bezier 단위곡면과 3x3차 사각 Bezier 단위곡면을 나타낸다[2,19,22,23].
그림 20. (좌)삼각 및 (우)사각 Bezier 단위곡면
둘째, 주어진 데이터(여기서는 삼각메쉬의 정점들)를 보간(interpolation)할 것인가 혹은 근사(approximation)할 것인가에 대한 결정이다. 곡면 보간의 경우, 삼각메쉬의 각 삼각형에 한 개 이상의 단위곡면을 정의하여 삼각메쉬의 모든 정점들을 지나는 곡면을 생성한다. 따라서, 결과 단위곡면의 수가 삼각메쉬의 삼각형 개수에 직접 비례하므로 윤곽선 근사 또는 삼각메쉬 데시메이션을 거친 삼각메쉬에 대해 곡면 보간을 적용하는 것이 바람직하다. 곡면 근사의 경우, 적은 수의 단위곡면들로 삼각메쉬 정점들을 근사하는 곡면을 생성한다. 근사과정에서 곡면 위상정보(topology)가 삼각메쉬의 것을 그대로 유지하도록 해야 하며, 근사 정확도(approximation accuracy)가 보장될 수 있어야 한다[2,19,21].
셋째, 단위곡면 재단 작업 시 요구되는 단위곡면들간의 연속성에 대한 결정이다. 삼각메쉬는 인접한 삼각형들간의 틈이 존재하지 않지만 공유하는 정점 및 변에서 법선벡터가 서로 다르므로 표면이 매끄럽지 않다. 즉, 삼각메쉬는 C0 연속성을 갖는다. 일반적으로, 공학적 또는 심미적 측면에서 부드러운 자유곡면을 언급할 때, 구성 단위곡면들간의 최소 G1 연속성을 갖는 곡면을 의미한다. 그림 21에서와 같이 경계곡선을 공유하는 두 단위곡면 L u v( , )와 R u v( , )가 G1 연속성을 유지하기 위해서는 식(4)를 만족해야 한다[2,19,27].
( ) ( ) ( ) ( ) ( ) ( ) 0
p v a v q v b v r v c v
(4) ( ) (0, )( ) (0, )
( ) (0, ) (0, )
a v L v u
b v R v u
c v L v v R v v
그림 21. 인접한 두 단위곡면간의 연속조건
인접한 단위곡면들간의 G1 연속성을 만족시키기 위해서는 모든 경계곡선마다 식 (2)와 같은 제약식을 만족하도록 단위곡면의 조정점들을 적절하게 조절해야 한다. 따라서, 단위곡면 간 연속성 유지를 위한 방법들이 많이 제시되었다[2].
2.6.2 자유곡면 생성 기법
삼각 복합곡면 생성
삼각 단위곡면들을 이용하여 주어진 삼각메쉬의 정점들을 보간 또는 근사하는 G1 복합곡면(composite surface)을 생성할 수 있다. 단위 곡면으로 삼각 Gregory 또는 Bezier 단위곡면이 이용된다. 최근에는 Loop 분할곡면을 이용한 방식이 제시되었다[28]. 삼각 Bezier 단위곡면을 이용하는 경우, 4차 Clough-Toucher 방식을 근간으로 한다. 이 방식은 관심 영역에 해당하는 삼각형 위에 3개의 4차 삼각 Bezier 단위곡면을 정의하여 영역 내의 정점들을 보간 또는 근사하며, 인접하는 단위곡면들간의 G1 연속성을 만족시키는 복합곡면을 생성하는 방식이다.
한편, 삼각형 위에 한 개의 3차 삼각 Gregory 단위곡면 또는 고차 삼각 Bezier 단위곡면을 사용할 수도 있다[2,18,19]. 그림 22는 그림 18의 삼각메쉬를 보간하는 삼각 Bezier 복합곡면을 나타낸다.
그림 22. 삼각 Bezier 복합곡면 생성 예
복합곡면 근사를 위해 적용할 수 있는 접근방식을 다음과 같다. 삼각메쉬의 모든 정점들을 지나는 복합곡면을 구한 후, 근사오차를 만족하며 위상정보가 유지될 때까지 삼각메쉬의 삼각형을 점차적으로 줄여나가면서 단위곡면들을 생성하는 것이다. 물론 반대 개념에 근거한 복합곡면 근사를 고려할 수 있다.
사각 복합곡면 생성
삼각 복합곡면 생성 방법들은 비교적 구현하기 쉽지만, 결과 곡면이 산업계 표준인 NURBS와 호환되지 않아 상용 CAX 시스템에서 사용할 수 없다는 단점이 있다. 따라서, NURBS와 호환이 용이한 사각 복합곡면 생성 방법들이 제시되었다. 삼각 복합곡면 생성과 비슷하게 사각 단위곡면들을 이용하여 주어진 삼각메쉬의 정점들을 보간 또는 근사하는 부드러운 복합곡면을 생성할 수 있다. 사각 단위곡면으로 사각 Gregory 또는 Bezier 단위곡면, 그리고 B-spline 곡면 등이 이용 가능하다[2, 19].
B-spline 곡면을 이용하여 삼각메쉬 근사 방법으로 Eck와 Hoppe[29]가 제안한 방법이
대표적이다. 이것은 삼각메쉬를 바탕으로 기저 사각메쉬(base mesh)를 구한 후, 사각메쉬를 바탕으로 정규 G1 곡선망(curve net)을 생성한다. 그런 다음, 곡선망의 각 사각 루프(quadrilateral loop)에 대해 4개의 경계곡선과 해당 영역에 속하는 정점들을 B-spline 곡면으로 근사하고, 동시에 이웃하는 B-spline 곡면들간의 G1 연속성을 만족시키는 복합 B-spline 곡면을 생성한다.
삼각메쉬와 복합곡면과의 오차가 허용오차보다 작을 때까지 사각메쉬 추가, 정규 곡선망의 개량, 그리고 복합곡면의 세밀화를 반복한다. 이 방법에서는 기저 사각메쉬를 생성하는 일이 쉽지 않은 단점이 있다[2]. 그림 23은 B-spline 곡면을 이용한 삼각메쉬 근사 예를 나타낸다.
삼각메쉬 기저메쉬 복합곡면
그림 23. 삼각 Bezier 복합곡면 생성 예
혼합 복합곡면 생성
사각 복합곡면 생성 방식은 NURBS와의 호환 용이성이란 큰 장점을 갖고 있으나. 기저 사각메쉬 생성의 복잡성, 특이 정점(extraordinary vertex)에서의 G1 연속성 위배 등의 문제점이 있다. 한편, Park [30]은 삼각 및 사각 Bezier 단위곡면들을 혼합하여 객체 표면을 근사하는 복합곡면을 생성하는 방법을 제시하였다. 이는 윤곽선 데이터 편집(contour compilation), 영역 검출(region detection), 스킨(skin) 영역의 사각곡면 근사, 그리고 브랜치(branch) 와 캡(cap) 영역의 삼각곡면 생성 등의 4가지 작업을 통해서 복합곡면을 생성한다[2]. (그림 24 참조)
스킨곡면 브랜치 곡면
캡 곡면 복합곡면
그림 24. 혼합 복합곡면 근사 예
3. 3D 가상 혈관모델 생성을 위한 프레임워크
그림 25 는 Parameter 기반 3D 가상 혈관 모델 생성 프래임워크를 나타낸다. 먼저, 의료측정장치(CT, MRI)로부터 3 차원 의료영상을 획득한 다음, 적절한 의료영상처리(노이즈 제거, 영역 분할 및 추출 등)를 거쳐 관심 혈관의 3D 데이터를 생성해야 한다. 3D 데이터는 골격 모델 생성을 위한 기본 데이터로서 혈관 영역에 해당하는 복셀 데이터와 메쉬 데이터로 구분할 수 있다. 복셀 데이터는 의료영상 영역화 및 관심 영역 추출을 통해 얻어지는 것으로 복셀 세선화(thinning) 과정을 거친 후, 골격(skeleton) 생성을 위한 노드 및 분기점 탐색 과정을 통해 혈관에 대한 골격 모델 생성이 이루어 진다. 메쉬 데이터는 메쉬 생성 알고리즘(마칭큐브) 으로부터 얻어지는 것으로서 메쉬 개선 과정을 거친 다음, 메쉬 축약 및 골격 생성을 통해 혈관 골격 모델 생성이 가능하다.
그림 25. Parameter 기반 3D 가상 혈관 모델 생성 프레임워크
그런 다음, 가상 혈관 자료구조와 Parameter 에 대한 설계를 수행하고, 형태학적 분석 및 혈관 parameter 추출 과정을 거친다. 혈관의 삼각메쉬 모델과 골격 모델을 이용하여 혈관의 형태학적 구조를 지배하는 혈관 parameter 를 설계하고, 골격 모델을 분석하여 가상 혈관모델 생성에 필요한 Parameter 를 추출한다. 추줄된 혈관 Parameter 를 이용하여 최종 결과물인 가상 혈관모델 생성한다. 이러한 Parameter 기반 가상혈관 모델을 의료용 교육, 법의학(forensics), CAE 기반의 생체역학 시뮬레이션 등 다양한 분야에 활용한다.
4. 3D 모델의 골격모델 생성 방안
3D 골격 모델 생성은 3D pattern matching, 3D recognition, 3D database retrieval 등 다양한 분야에 응용이 가능한 매우 유용한 기술이다. 이러한 3D 골격 모델은 3D 기하학 공간 측면에서 medial axis 로 정의 할 수 있으며, medial axis 종류로는 medial line 과 medial surface 가 있다.
대부분의 연구에서는 간편하고 다루기 쉬운 medial line 을 선호하는 편이며[31], 이러한 골격 모델 생성에 활용되는 3D 정보로는 3D 볼륨 데이터와 3D 메쉬 데이터가 주로 이용 된다.
3D 볼륨 데이터는 일정한 3 차원 공간에서 정의된 복셀들의 집합을 나타내며, 각 복셀(voxel = volume pixel)은 지정된 크기의 3 차원 공간 요소로서 0 또는 1 로 매핑된다. 복셀 값이 1 일 경우 검정색 점(관심 물체), 0 일 경우 흰색 점(배경)으로 정의된다. 골격 모델 생성 과정에서 관심 물체에 해당하는 검정색 점은 조건 및 상황에 따라 삭제되며, background 에 해당하는 흰색 점은 영향을 받지 않는다. 이러한 3D 볼륨 데이터에서는 medial lines/surface 추출이 가능하다[32-34].
3D 메쉬 데이터는 다각형들로 구성되며, 각 다각형의 모서리는 다른 인접한 다각형과 최대 1 번 공유된다. 다각형이 삼각형인 경우, 삼각 메쉬라고 한다. 3D 메쉬를 입력데이터로 이용한 몇몇 연구에서는 골격 모델을 생성하기 위해 medial surface 를 얻는 방안을 제시하였으며[35-37], 최근 지속적인 연구를 통해 medial surface 단점을 보완한 curve-skeleton 추출 방안이 제시되었다[38-39].
4.1 볼륨 데이터의 3D 세선화를 이용한 골격모델 생성
일반적으로 세선화(thinning)는 2 차원 문자인식, 지문인식에 사용되며 위상의 특성을 이용하여 대상을 의미 있는 정보만으로 간소화는 기법이다. 3D 세선화는 3D 의료영상의 복셀 데이터로부터 모델의 골격이 드러날 때까지 복셀 데이터의 최외각에서부터 일정 단위만큼 조금씩 줄여나가는 식으로 수행된다. 즉, 외각 복셀이 어떤 조건을 만족 할 경우 그 복셀을 없애고 다음 반복 단계에서 새로 생긴 외각 복셀에 대해 조건의 만족여부를 확인해 나가는 것이다. 만약 특정 반복 단계에서 한 개의 복셀도 없어지지 않는다면 반복되던 세선화 과정이 중단되고, 이때 남은 복셀이 골격요소가 되며, 이들을 연결하여 해당 3 차원 모델의 골격 모델을 생성하게 된다[40].
3 차원 모델의 세선화를 위해서는 다음의 몇 가지 개념이 필요하다.
서로 다른 위치에 있는 점p(px, py, pz)와 점q(qx, qy, qz)가 있을 때, 두 점 사이의 유클리드 거리는 식 5와 같다.
2 2
2 ( ) ( )
)
(px qx py qy pz qz
dis (5)
k-adjacent는 다음과 같이 정의된다.
그림 26. 점 P에 대한 k-adjacent - 6-neighbors : e, w, n, s, u, d
- 18-neighbors : 6-neighbors + (nu, nd, ne, nw, su, sd, se, sw, wu, sd, eu, ed) - 26-neighbors : 18-neigbors + 꼭지점
6-adjacent 경우 dis ≤ 1, 18-adjacent 경우 dis ≤ sqrt(2), 26-adjacent 경우 dis ≤ sqrt(3)
이는 3D 모델의 연결성에 있어 매우 중요한 요소로 만약 세선화 과정에서 연결을 유지하지 못한다면, 제대로 연결이 되지 않은 골격 모델을 추출하게 된다. 일반적인 순차적 세선화 방식으로 오직 단순한 점들만 제거하여 연결성을 유지할 수 있으나 대부분의 연구[32-34]에서는 정확한 골격 추출을 위해 병렬적 세선화 방식을 활용하며, 이로 인해 연결성에 대한 문제가 종종 발생하게 된다. 이를 해결하게 위해 Ma and Sonka [41]는 fully 3D thinning algorithm 을 제안하였으며, 이는 많은 의료 영상 처리와 3D 복원에 활용 되고 있다. Ma and Sonka’s algorithm 은 미리 정해진 탬플릿을 기반(class A, B, C and D)으로 수행되는데, 이웃하는 점이 어느 하나의 탬플릿과 같을 경우 제거해나가는 방식을 취한다. 그림 27 은 Ma and Sonka’s algorithm 에서 활용한 4 가지 기본적인 탬플릿을 나타낸다.
그림 27. 4 가지 템플릿 (class A, B, C and D)
여기서, 검정색 점은 모델에 해당하는 object 를 나타내며, 흰색 점은 background 를 나타낸다.
그리고, 표시가 되지 않은 점은 검정색 또는 흰색이 될 수 있는 점으로 탬플릿 비교에 포함되지 않는다. 이밖에 class A, B, C and D 는 각각 6 개, 12 개, 8 개, 12 개의 탬플릿을 포함하고 있다.
이러한 세선화 방안은 대부분의 모델에 대해 연결성을 유지한 골격을 추출할 수 있지만 여러 개의 작은 세그먼트로 절단하는 경우가 종종 발생하며[12], 그림 28 과같이 a-b-c-d-e-f-g 가 연결되어야 하는 경우, 탬플릿에 의해 c,d,e 가 제거되어 원하는 결과를 얻기 어렵다는 단점을 가지고 있다
그림 28. 점 A-b-c-d-e-f 연결 예제
Wang[31]은 Ma and Sonka’s algorithm 에서 활용한 템플릿에서 검정색 또는 흰색이 될 수 있는 표시되지 않는 인접한 2 개의 점을 템플릿 비교에 포함하게 함으로써 세선화 과정에서 절단되는 문제를 해결할 수 있는 방안을 제시하였다. 제시된 방안은 인접한 표시되지 않은 두 점의 상태에 대한 제약이 포함된 탬플릿을 기존 템플릿에 추가하여 활용하는 것으로 점 p 와 인접한 표시되지 않은 두 점 p1, p2 를 정의하고, 각 점이 검정색인지, 흰색인지를 확인하는 것이다. 그림 29 는 점 p1 과 p2 를 포함하여 추가 생성한 템플릿 일부를 나타내며, 그림 30 은 Ma and Sonka’s algorithm 과 Wang algorithm 의 골격 추출 결과를 나타낸다.
그림 29. 추가된 템플릿 일부
그림 30. (a) 3D 모델; (b) Ma and Sonka’s algorithm; (c) Wang algorithm
3D 볼륨 데이터로부터 골격 모델을 생성하는 또 다른 방식으로 Lee[42]는 Euler characteristic labeling 을 활용하여 연결성을 고려한 세선화 방안을 제안하였다. 세선화 과정에 있어 모델에 구멍(hole)이 존재하는 경우, 표면을 분할하지 않고 인접한 점을 제거하는 것은 골격의 연결성을 유지하는데 어려움이 있으며, 복셀의 흰색 점(background)으로부터 hole 을 구별하는 것 또한
매우 어려운 일이다[42]. 따라서, Lee 는 이를 구별하고자 Euler characteristic 공식을 이용해 복셀을 라벨링함으로써 hole 에 포함되는 복셀의 경우, 이에 해당하는 점을 제외하고 그렇지 않은 점만을 인접한 점으로 고려하여 이를 복셀 세선화에 활용하였다. Euler characteristic 공식은 모델에서 빈 부분(cavities)과 구멍(hole)에 대한 구별을 가능하게 한다. 그림 31 은 Euler characteristic labeling 결과를 나타내는 것으로 (a)는 점 v 와 인접한 26 개의 점으로 기본적인 복셀을 나타내며, (b)는 Euler characteristic 을 적용한 라벨링 결과를 (c)는 라벨링를 통해 재 정의된 인접 점의 tree 를 나타낸다. 그림 31 의 (b)는 정의된 tree (c)에 의해 얻어진다.
(a) 기본 복셀 (b) Euler characteristic 라벨링 결과
(c) 인접 점 tree
그림. 31 복셀에 대한 Euler characteristic labeling 결과
복셀에 대한 인접 점의 tree 가 생성되면 그림 26 에서와 같이 6 가지 인접 점(6- adjacent)으로부터 조건을 만족하는 점을 제거하여 골격을 추출할 수 있다. 즉, 그림 31(a)와 같이 점 v 와 인접하는 점 12, 13, 10, 15, 4, 21 이 있을 때 ‘0’의 값을 가지는 점을 ‘border point’로 간주하여 제거하는 것이다. 그러나, 이러한 1 차적인 조건을 활용한 복셀 세선화는 특정 형상을 가지는 모델에는 적합하지 않다. Lee 는 이를 해결하기 위해 인접한 점에서 border point 를 지정하고, 지정된 border point 중에서 다음 조건까지 만족하는 경우, 해당 인접 점을 제거하도록 하였다.
Q=S-R
If v∈R, if [R∩N(v)] ∪ [Q∩N(v)]
여기서, R 은 제거 가능한 인접 점인 border point 이며, S 는 복셀을 의미하고, N(v)는 이웃하는 점을 의미한다. 이 과정은 해당 복셀에서 6 가지 인접 점에 대해서 반복 되며, 이를 통해 medial surface/axis 를 추출한다. 그림 32 는 골격 모델 추출 결과를 나타낸다.
(a) 복셀 모델 (b) medial surface (c) medial axis 그림. 32 골격 추출 결과
4.2 3D 메쉬 데이터의 축약을 이용한 골격 모델 생성
3D 메쉬 데이터의 골격 모델 생성은 물체의 표면을 이루는 3차원 메쉬 모델을 축약(간략화)시킨 다음, 이를 토대로 3차원 모델의 형상을 커브로 근사하는 방식이며, 골격 모델을 curve skeleton 이라고도 한다. 골격 모델(curve skeleton)는 3차원 모델의 기하학적 구조와 토폴로지를 간략화하여 표현하는 1차원 구조로 되어있는데, 이들은 형상 분석, 에니메이션, 모핑(norphing), 형상 정합, 형상 복원 등 다양한 분야에서 유용하게 활용되는 것으로 컴퓨터 그래픽스 및 시각화 분야에서 기본적인 문제로 인식되고 있다. 이로 인해 오랜 기간 동안 주목을 받아 오고 있으며, 간단하고 강건한 curve skeleton 생성을 위한 많은 연구가 진행 되고 있다[43].
Au[38]는 메쉬로 표현된 모델 공간에서 curve skeleton 을 추출하는 방안을 제안하였다. 골격 추출 방안이 적용되는 입력 모델은 메쉬가 변형되면서 볼륨이 ‘0’에 가까워 질 때까지 반복적으로 축약되는데, 축약 과정 중에 원래 모델의 연결성(topology 및 connectivity)은 바뀌지 않는다. 이 방식은 원래의 형상을 유지하면서 안정적인 축약을 달성하기 위해 두 가지 weight function 을 활용한다. 하나는 contraction term 으로 Laplace operator 를 기반으로 메쉬를 축약하기 위해 사용되며, 다른 하나는 attraction term 으로 모델의 기하학적 정보를 활용하여 축약 동안 원래의 형태를 유지하기 위해 사용된다. 이들은 약간의 반복만으로 강건하고 노이즈에 둔감한 골격 형태의 생성을 가능하게 하며, 메쉬 축약 과정은 식 6 과 같다.
Solve
t t H t
t H
t t L
V V W
W L
W 1 0
for Vt1
Update WLt1 sLWLt and WHt1 WH0 Ai0 /Ait (6)
Compute the new Laplace operator Lt1
여기서, t는 반복 횟수이며,
V
는 입력 모델 정점들이다.A
it 와A
i0는 현재 one-ring areas와 초기 one-ring areas며[15], WL과 WH는 각각 앞서 언급한 contraction term과 attraction term을의미하는 것으로 초기 WH0 1.0와
W
L0 10
3A
로 정의된다.A
는 입력 모델의 평균 표면 면적이다. 또한, sL 2.0이며, Laplace operatorL
은 식 7와 같이 정의된다.
otherwise
0
if
)
,
(
if
cot
cot
) ,
(
i j
E
j
i
L
kE k
i ik
ij ij
ij
ij
(7)
E
는 입력 모델의 edge들이며,
ij 와
ij 는
,
가 이루는 edge의 맞은편 각들을 의미한다 [44]. 메쉬를 축약하는 과정은 볼륨이 ‘0’에 가까워질 때까지 반복되며, 그림 33은 입력 모델의 축약 결과를 나타낸다.
그림. 33 골격 추출 결과: (왼쪽)입력 모델; (오른쪽)축약 결과
메쉬의 축약은 입력 모델의 메쉬를 변형(모양을 바꾸거나 특정 방향으로 이동)하는 것으로 그림 33 의 오른쪽과 같이 메쉬를 제거하지 않고 변형만 하게 된다. 이러한 결과는 1 차원 구조로 정의되는 curve skeletons 에 부합되지 않는다. 따라서, 축약된 메쉬를 curve 로 변환하는 과정이 요구되는데, 이를 위해 뭉개지거나 겹쳐진 메쉬를 정리하고자 edge 병합을 수행하는 connectivity surgery operation 을 적용한다. 수행되는 connectivity surgery operation 에서는 QEM simplification 방법[45]을 응용한 shape cost 를 정의하여 edge 를 병합하고, sampling cost 를 적용하여 골격 노드(nodes)를 샘플링 하게 된다[5]. 이를 통해 1 차원 구조의 curve skeleton 을 얻을 수 있다. 그림 34 는 connectivity surgery operation 이 적용된 결과를 나타낸다.
그림. 34 Connectivity surgery operation 적용 결과
또한, 그림 34 에서와 같이 골격 노드가 입력 모델 형상의 중앙에 위치하지 않거나 분기가 제대로 이루어 지지 않는 것을 해결하기 위해 축약된 메쉬 모델의 경계 점을 활용하여 골격
노드를 형상의 중심으로 근사 이동하는 embedding refinement[5]를 수행하여 그림 35 와 같이 최종 골격 모델을 생성하였다.
그림. 35 Embedding refinement 적용 결과
Wang[39]는 혈관 모델에 초점을 맞추어 혈관 메쉬 데이터로부터 curve skeleton 을 추출하는 방안을 제시하였다. 입력된 혈관 메쉬 모델을 축약하는 과정은 Au[38]의 메쉬 축약 방식을 적용하였으며, 축약된 메쉬로부터 curve skeleton 을 추출하는 과정은 Au 의 복잡한 과정을 간소화하고, 다양한 분기 형태를 가지는 혈관의 특성을 고려하여 정확한 분기점(joint points) 탐색 및 골격을 추출할 수 있는 방안을 적용하였다. 이를 위해 Au 의 connectivity surgery operation 과 embedding refinement 과정을 대신해 subdivision 을 활용하여 축약된 메쉬를 세분화하고, point cloud 로 변환한 다음, local PCA 및 point clustering, 그리고 joint handling 을 활용하여 골격 모델을 생성하였다.
혈관 모델의 경우, 일반적인 모델에 비해 표면을 표현하는 메쉬가 적어 축약된 메쉬 정보를 그대로 활용할 경우 해당 분기 영역에 골격 후보 노드가 드물게 형성된다. 이로 인해 추출하고자 하는 골격이 혈관의 분기 중심을 벗어는 경우가 빈번히 발생하게 된다[46,47]. 따라서, Wang 은 축약된 메쉬를 더 세분화하여 보다 정확한 분기점의 추출이 가능하도록 하였다. 메쉬 세분화는 subdivision 을 활용하는데, 일반적인 loop-subdivision 의 경우, 세분화 과정 중에 축약된 메쉬 모델의 형태를 바꾼다는 단점이 있어 edge 를 분할하고 중간에 새로운 점을 추가하여 형상에 영향을 주지 않으면서 메쉬를 세분화하는 subdivision 방식을 활용하였다. 또한, curve skeleton 의 노드를 찾기 위해 세분화된 메쉬를 point cloud 로 변환하였다. 그림 36 은 혈관 모델의 축약된 결과와 세분화한 결과를 나타낸다.
그림. 36 (a) 입력 혈관 모델, (b) 메쉬 축약 결과, (c) subdivision 결과
변환된 point cloud 에서 분기점(joint points) 및 가지점(branch points)의 식별은 curve skeleton 추출을 위한 토대가 되는데, Wang 은 변환된 point cloud 의 가지점들이 분기점들에 비해 더 강한 선형 경향을 띈다는 것을 고려하여 local PCA 를 적용해 분기점과 가지점을 식별하였다. 이을 위해 linear coefficient l(pi)를 활용하였으며, l(pi)는 식 8 과 같이 정의할 수 있다.
3 3 1
)
1(
p
il
p p
p p
p p
p p p C
k T
k
i
1 1
)
( (8)
여기서,
i( i 1,2,3) 는 3x3 공분산행렬 C(pi) 의 i 번째로 큰 고유값으로 정의되며, p 는 식별을 위한 현재 점이고, k=25 로 정의하여 활용하였다. 이를 통해 식별하기 위한 점 pi 가 정해지면 pi 에 대한 linear coefficient 를 계산하고, 계산된 값이 기준치(0.8)보다 작으면 분기점으로, 크면 가지점으로 식별하게 된다. 그러나, point cloud 에 적용된 local PCA 는 분기점과 가지점의 정확한 식별을 제공해 주지 못한다. 따라서, neighbor joints ratio
(pi) (식 9)를 추가하여 local PCA 의 식별에서 발생할 수 있는 오류를 최소화 하였다. 분기점에 해당하는) (pi
는 local PCA 와는 반대로 기준치보다 큰 값은 갖고, 가지점은 작은 값을 갖는다. 따라서, local PCA 값이 기준치보다 작고
(pi)값이 기준치(0.2)보다 크면 분기점으로 분류하고, 그렇지 않을 경우 가지점으로 분류하게 된다. neighbor joints ratio
(pi) 다음과 같이 정의 되며)
( N
j
와 (Ni) 는 각각 분기점 수와 25 로 정의되어 활용 되었다. 그림 37 은 분기점과 가지점을 분류한 결과를 나타낸다. (왼쪽은 local PCA 를 적용한 결과로 식별이 제대로 이루어지지 않은 결과를 나타내며, 오른쪽은 local PCA 와 neighbor joints ratio 의 적용 결과로 식별이 잘 이루어진 결과를 나타낸다. ( )
) ) (
(
i j
i N
p N
(9)
그림. 37 분기점 및 가지점 분류 결과
분류된 분기점은 cluster
C
에 포함되며, 다음을 통해 얻어지는 cluster centerc
*i (식 10)는 혈관이 분기되는 골격 노드가 된다.p
와 pl은C
에 포함되어 있는 분기점들을 의미한다.
i
l C
p
l R
p
i p p
c* argmin || ||2 (10) 또한,
c
*i 와 clusterC
에 포함된 분기점들간의 가장 긴 거리 값을 활용하여 이를 반경으로 하는 원을 생성한 후, 반경을 r만큼 증가시켜 분기가 시작되는 가지(branches)의 끝점이 원안에 포함되도록 한다(그림 38(a) 참조). 그런 다음,c
i*와 거리가 가장 먼 가지 끝점을 연결하여 그림 38(b)와 같이 분기 구조를 생성한다. 가지에 대한 골격 노드 탐색 및 골격 생성은 분기 골격 노드와 가지 끝점을 연결하는 방법과 유사하게 수행된다. 분기 골격 노드와 가지 끝점이 연결되면, 가지 끝점은 해당 가지의 골격 생성을 위한 시작점이 되며 시작점을 기준으로 일정 크기의 반경을 가지는 원을 생성하고, 시작점의 고유벡터 정보를 활용하여 고유벡터 방향으로 원안에 포함되며 거리가 가장 먼 점을 다음 골격 노드로 선택하는 과정으로 반복된다(그림 38(c) 참조)[48]. 모든 분기 및 가지에 대하여 반복과정이 끝나면 그림 39 과 같이 혈관 골격 모델이 생성된다.
그림. 38 골격 노드 샘플링 및 골격 생성 예제
그림. 39 추출된 혈관 골격 모델
