선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문은 삼차원 볼륨 영상으로부터 개별 등위면 요소를 선택하고 추출할 수 있는 컨투어 트리 기반의 대화형 시각화 기법 및 프로그램의 개발을 기술하였다. 복잡한 형태의 컨투어 트리를 단순화하고, 사용자가 이해하고 조작하기 쉽도록 배치하는 알고리즘을 제시하여 컨투어 트리 인터페이스의 사용성을 높였다.
- 본 논문은 위에서 기술한 기존 시각화 기법들의 문제점을 극복하고 컨투어 트리를 이용한 대화형 볼륨 영상 시각화 기법을 개발하는 것에 관하여 기술한다. 이 기법을 통해 볼륨 영상을 입력으로 읽은 뒤, 찾고자 하는 등위면 요소를 선택하고 효율적으로 추출하여 대화형 시각화의 기능을 향상시켰다.
제안 방법
- (i) 컨투어 트리를 사용자가 이해하고 조작하기 쉬운 형태로 2차원 평면상에 배치하는 새로운 알고리즘을 제안하였다.
- (iii) 컨투어 트리를 이용하여 등위면 요소를 선택하고 추출하는 새로운 사용자 인터페이스와 기존의 등위면 및 볼륨 렌터링 기능이 융합된 대화형 볼륨 시각화 프로그램을 개발하였다.
- <그림 3>과 <그림 5> 그리고 <그림 6>은 헤모글로빈 볼륨 영상, 머리 MRI 볼륨 영상 그리고 무릎 볼륨 영상으로부터 각각 폴리펩타이드 체인을 나타내는 등위면 요소와 뇌실을 나타내는 등위면 요소 그리고 대퇴골을 나타내는 등위면 요소를 추출한 결과를 보여준다. 각 볼륨 영상으로부터 계산된 컨투어 트리는 그 원래 형태가 매우 복잡하기 때문에 그려주기 전에 단순화 과정을 수행하였다. 컨투어 트리상의 간선 위에 있는 점을 마우스로 클릭하면, 해당하는 등위면 요소의 표면이 우리의 전이 알고리즘을 통해 재빨리 추출되었다.
- 우리는 [20]에서 제안한대로 간선의 중요성을 그 간선의 지속성(persistence) 즉 두 정점의 함수값 차이로 간주하여, 지속성 값이 작은 간선을 우선적으로 제거하는 정책을 수행하였다. 또한, 사용자가 원하는 단순화 정도를 한계값(threshold)으로 사용하여 그 한계값보다 지속성 값이 작은 간선들을 모두 제거하였다. 단순화된 컨투어 트리는 다음과 같이 배치된다.
- 본 논문은 삼차원 볼륨 영상으로부터 개별 등위면 요소를 선택하고 추출할 수 있는 컨투어 트리 기반의 대화형 시각화 기법 및 프로그램의 개발을 기술하였다. 복잡한 형태의 컨투어 트리를 단순화하고, 사용자가 이해하고 조작하기 쉽도록 배치하는 알고리즘을 제시하여 컨투어 트리 인터페이스의 사용성을 높였다. 또한 다중코어 GPU의 병렬계산 기능을 이용하여 선택된 등위면 요소의 표면을 추출하는 속도를 향상시켰다.
- 본 논문에서 제안하는 방법을 이용하여 컨투어 트리를 이용한 대화형 볼륨 시각화 프로그램을 개발하였다. 이 프로그램은 볼륨 데이터 파일을 선택하면, 그 데이터에 대하여 다음과 같은 볼륨 시각화 기능을 수행한다.
- 알고리즘 1. 본 논문에서 제안하는 전이 알고리즘. 순수 전이와 삼각화 과정으로 분리됨.
- 본 연구에서 제안하는 전체 전이 알고리즘은 과 같이 순수 전이 알고리즘과 삼각화 알고리즘으로 분리되어 실행된다.
- <그림 5>는 본 연구의 결과로서 개발된 볼륨 시각화 프로그램의 화면을 나타내며, 입력으로 주어진 머리MRI 볼륨 영상의 컨투어 트리와 선택된 등위면 요소인 뇌실의 표면을 보여준다. 볼륨 구조를 보여주고 단일 등위면 요소를 대화형으로 선택하고 추출하는 기능을 볼륨 렌더링과 등위면 시각화 기능과 융합하여 주어진 볼륨 영상을 대화형으로 분석할 수 있게 하였다. 기존의 볼륨 시각화 프로그램은 볼륨 렌더링과 등위면 시각화에 제한되어 있어 한계성을 가진다.
- 이러한 방식으로 컨투어 트리의 모든 간선에 대한 경로 씨드가 계산된다. 사용자가 컨투어 트리의 간선위에 있는 임의의 점을 선택하여 그에 해당하는 등위면 요소를 추출하고자 할 때, 그 간선의 경로 씨드로부터 인접한 정점들 중 값이 가장 작은 정점을 방문하는 과정을 반복하면 선택된 등위면 요소와 교차하는 씨드셀을 찾아 전이 과정을 수행하여 등위면 요소 표면을 추출한다.
- 순수 전이 알고리즘에 의해 계산된 활성셀, 즉 선택된 등위면 요소와 교차하는 셀의 목록이 얻어진 후, 우리는 GPU상에서 CUDA를 이용하여 각 활성셀안의 등위면 요소 표면을 삼각화한다. 삼각화 구현을 최적화하기 위해서 우리는 nVidia사의 Marching Cubes 샘플 코드[8]에 있는 generateT riangles2 라는 CUDA 커널 함수를 수정하여 사용하였다. CUDA에서 생성되는 각 GPU 쓰레드는 각 활성셀을 목록으로부터 하나씩 얻어서 등위면 요소 표면의 정점 위치, 법선정보, 삼각형 연결 정보 등의 기하 정보를 Marching Cubes 방식에 기반하여 계산한다.
- 본 연구에서 제안하는 전체 전이 알고리즘은 <알고리즘 1>과 같이 순수 전이 알고리즘과 삼각화 알고리즘으로 분리되어 실행된다. 순수 전이 알고리즘에 의해 계산된 활성셀, 즉 선택된 등위면 요소와 교차하는 셀의 목록이 얻어진 후, 우리는 GPU상에서 CUDA를 이용하여 각 활성셀안의 등위면 요소 표면을 삼각화한다. 삼각화 구현을 최적화하기 위해서 우리는 nVidia사의 Marching Cubes 샘플 코드[8]에 있는 generateT riangles2 라는 CUDA 커널 함수를 수정하여 사용하였다.
- <그림 5>(b)와 (c)에서 볼 수 있듯이, 머리 MRI의 등위면은 뇌실뿐만 아니라 안구, 뇌조직 등을 나타내는 많은 개수의 등위면 요소를 포함한다. 우리 방법을 이용하여, 우리는 그 데이터의 주요 특징 부분인 뇌실의 등위면 요소만을 추출하여 시각화하였다. 이는 다른 특징 부분들에 의하여 방해되는 것 없이 뇌실 부분만 시각화하고 분석할 수 있도록 해주는 장점을 가진다.
- 단순화 과정의 목적은 트리의 중요하지 않은 부분을 제거하여 중요한 부분을 강조하여 보여주는 것이다. 우리는 [20]에서 제안한대로 간선의 중요성을 그 간선의 지속성(persistence) 즉 두 정점의 함수값 차이로 간주하여, 지속성 값이 작은 간선을 우선적으로 제거하는 정책을 수행하였다. 또한, 사용자가 원하는 단순화 정도를 한계값(threshold)으로 사용하여 그 한계값보다 지속성 값이 작은 간선들을 모두 제거하였다.
- 우리는 경로 씨드 계산에 있어 단순성을 가지는 이점을 얻기 위해, 컨투어 트리의 계산에 [14]의 방법을 확장하여 적용하였다. 최대값을 가지는 정점부터 함수값의 내림차순으로 정점들을 방문하면서 정점들과 간선들을 Union-Find구조를 이용하여 차례로 추가한다.
- 우리는 기존 방식[1]과 GPU를 통해 가속화된 우리 방식을 이용한 등위면 요소 추출 시간을 측정하였으며 실험 결과는 에 요약되어 있다.
- 우리는 이러한 기존 전이 알고리즘[1]을 더욱 가속화하기 위하여 GPU의 병렬 계산 기능을 이용하였다. 본 연구에서 제안하는 전체 전이 알고리즘은 <알고리즘 1>과 같이 순수 전이 알고리즘과 삼각화 알고리즘으로 분리되어 실행된다.
- 본 논문은 위에서 기술한 기존 시각화 기법들의 문제점을 극복하고 컨투어 트리를 이용한 대화형 볼륨 영상 시각화 기법을 개발하는 것에 관하여 기술한다. 이 기법을 통해 볼륨 영상을 입력으로 읽은 뒤, 찾고자 하는 등위면 요소를 선택하고 효율적으로 추출하여 대화형 시각화의 기능을 향상시켰다. 본 논문이 고유하게 기여하는 바는 다음과 같다.
대상 데이터
- 우리는 컨투어 트리 사용자 인터페이스를 이용하여 위에서 언급된 특징 부위를 나타내는 등위면 요소를 선택하고 효율적으로 추출할 수 있었다 (<그림 3> 참조). 두 번째 데이터는 뇌척수액(Cerebro Spinal Fluid) 부위를 강조하여 보여주는 머리 MRI로부터 생성되었다[24]. 세 번째 데이터는 무릎 뼈의 거리 함수(Distance Function)를 나타내는 볼륨 영상이다.
- 두 번째 데이터는 뇌척수액(Cerebro Spinal Fluid) 부위를 강조하여 보여주는 머리 MRI로부터 생성되었다[24]. 세 번째 데이터는 무릎 뼈의 거리 함수(Distance Function)를 나타내는 볼륨 영상이다.
- 이 장에서는 본 논문에서 제안한 전이 알고리즘을 구현한 결과를 보고한다. 실험 결과는 인텔 i7(2.66GHz) CPU와 2GB 메인메모리, 그리고 nVidia GeForce 480GTX 그래픽스 카드를 갖춘 데스크톱 PC에서 측정되었다.
- <표 1>에서 볼 수 있듯이 실험을 위하여 세 개의 데이터를 사용하였다. 첫 번째 데이터는 헤모글로빈 분자의 전자 밀도 근사 볼륨이다.
- <표 1>에서 볼 수 있듯이 실험을 위하여 세 개의 데이터를 사용하였다. 첫 번째 데이터는 헤모글로빈 분자의 전자 밀도 근사 볼륨이다. 헤모글로빈은 4개의 폴리펩타이드 체인으로 구성된 단백질이다.
이론/모형
- 삼각화 구현을 최적화하기 위해서 우리는 nVidia사의 Marching Cubes 샘플 코드[8]에 있는 generateT riangles2 라는 CUDA 커널 함수를 수정하여 사용하였다. CUDA에서 생성되는 각 GPU 쓰레드는 각 활성셀을 목록으로부터 하나씩 얻어서 등위면 요소 표면의 정점 위치, 법선정보, 삼각형 연결 정보 등의 기하 정보를 Marching Cubes 방식에 기반하여 계산한다. 계산된 기하 정보는 선택된 등위면 요소의 삼각형 목록을 저장하는 결과 배열에 쓰여진다.
- 셋째, 컨투어 트리를 이용하여 개개의 등위면 요소나 전체 등위면을 효율적으로 추출하기 위한 씨드(seed) 집합[2]을 생성할 수 있다. 그 추출 과정은 주어진 씨드셀(seed cell)에 등위면 요소 표면으로 연결된 셀들을 점진적으로 방문하고 삼각화(triangulation)하는 전이 알고리즘[2]을 사용한다.
- 우리는 선처리 과정에서 경로 씨드 방법[1]을 이용하여 컨투어 트리의 각 간선에 대한 씨드 집합을 계산한다. 경로 씨드는 사용자가 선택한 등위면 요소와 교차하는 씨드셀을 생성하고 그 씨드셀로부터의 전이가 이루어져 등위면 요소 표면을 효율적으로 추출하는데 사용된다.
- 우리는 경로 씨드 계산에 있어 단순성을 가지는 이점을 얻기 위해, 컨투어 트리의 계산에 [14]의 방법을 확장하여 적용하였다. 최대값을 가지는 정점부터 함수값의 내림차순으로 정점들을 방문하면서 정점들과 간선들을 Union-Find구조를 이용하여 차례로 추가한다. 이 과정을 통하여 영역 M 위에서 연결 집합인 X(w) = {v∈M|F(v) ≧ w}을 점진적으로 만들어나간다.
성능/효과
- 또한 다중코어 GPU의 병렬계산 기능을 이용하여 선택된 등위면 요소의 표면을 추출하는 속도를 향상시켰다. 구현 및 실험 결과는 이러한 기능들이 대화형 볼륨 시각화 프로그램으로 통합되어 사용자가 쉽고 빠르게 원하는 등위면 요소를 시각화할 수 있음을 보여준다.
- <그림 5>는 본 연구의 결과로서 개발된 볼륨 시각화 프로그램의 화면을 나타내며, 입력으로 주어진 머리MRI 볼륨 영상의 컨투어 트리와 선택된 등위면 요소인 뇌실의 표면을 보여준다. 볼륨 구조를 보여주고 단일 등위면 요소를 대화형으로 선택하고 추출하는 기능을 볼륨 렌더링과 등위면 시각화 기능과 융합하여 주어진 볼륨 영상을 대화형으로 분석할 수 있게 하였다.
- 첫째, 컨투어 트리는 일반적인 렌더링 기법으로부터 직접적으로 얻어질 수 없는 볼륨 영상의 위상학적 구조를 제공해 준다. 둘째, 컨투어 트리는 개별 등위면 요소를 선택 및 분할하고 그려주는 것을 가능하게 해준다. 셋째, 컨투어 트리를 이용하여 개개의 등위면 요소나 전체 등위면을 효율적으로 추출하기 위한 씨드(seed) 집합[2]을 생성할 수 있다.
- 사용자는 대화형으로 그 점을 옮기거나 삭제함으로써 원하는 등위면 요소들을 선택하여 시각화 할 수 있다. 등위면 요소의 추출 및 시각화 과정에서 다중코어 GPU의 병렬 계산 기능이 이용되어 대화형 시각화가 가능할 정도로 처리 속도가 매우 향상되었다.
- 복잡한 형태의 컨투어 트리를 단순화하고, 사용자가 이해하고 조작하기 쉽도록 배치하는 알고리즘을 제시하여 컨투어 트리 인터페이스의 사용성을 높였다. 또한 다중코어 GPU의 병렬계산 기능을 이용하여 선택된 등위면 요소의 표면을 추출하는 속도를 향상시켰다. 구현 및 실험 결과는 이러한 기능들이 대화형 볼륨 시각화 프로그램으로 통합되어 사용자가 쉽고 빠르게 원하는 등위면 요소를 시각화할 수 있음을 보여준다.
- 이를 통해 우리는 전이 알고리즘의 수행 속도를 약 3배 향상시켰다. <표 1>의 시간 측정 결과에서 볼 수 있듯이 기존 전이 알고리즘 전체 수행시간의 2/3~3/4정도의 비중을 차지하는 삼각화 과정을 우리가 제안한 전이 알고리즘에서는 GPU를 이용하여 무시할만한 매우 짧은 시간으로 수행을 완수하였다. 이는 삼각화 과정이 다중코어 GPU를 이용하여 최적화하기 매우 좋은 성질을 가지고 있으며, 전체 전이 과정에서 삼각화 과정을 분리하여 최적화하는 우리 방식이 전이 알고리즘의 속도를 향상시키는데 매우 적절함을 암시한다.
- 컨투어 트리(Contour Tree) [1]는 <그림 1>에서 볼 수 있듯이 등위값 변화에 따른 등위면의 위상 변화를 나타냄으로써 볼륨 영상의 구조를 보여주는 자료 구조이며 등위면을 시각화하는데 매우 유용한 툴이다. 첫째, 컨투어 트리는 일반적인 렌더링 기법으로부터 직접적으로 얻어질 수 없는 볼륨 영상의 위상학적 구조를 제공해 준다. 둘째, 컨투어 트리는 개별 등위면 요소를 선택 및 분할하고 그려주는 것을 가능하게 해준다.
후속연구
- 최근에는 GPU의 높은 병렬 처리 능력을 이용한 실시간 등위면 추출 방법 [8][9]이 개발되었으나, 본 논문의 주제중 하나인 등위면 요소의 효율적인 추출을 위해서는 전이 알고리즘의 순차적 특성 때문에 적용되지 못하는 한계가 있다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.