3차원 모델의 형상 유사성 평가는 의학, 기계 공학, 분자 생물학 등의 많은 분야에서 매우 중요하다. 더욱이 3차원 모델이 웹 상에 보편화됨에 따라 3차원 모델들의 분류와 검색에 관한 연구들이 활발하게 이루어지고 있다. 본 논문에서는 3차원 형상 표현 방법들과 유사성 평가에 대한 주요 개념들을 기술하고, 최근의 형상 비교에 관한 연구들을 다해상도, 위상 기하학, 2차원 영상, 통계학 기반 방법들로 분류하여 그 특징들을 분석하였다. 또한 논문에서 채택한 유일성, 강인성, 불변성, 다해상도, 효율성, 비교범위와 같은 기준을 사용하여 그 성능을 비교 평가하였다. 다해상도 기반 방법은 비교를 위한 계산 시간은 감소시킨 반면 전처리 시간은 증가시켰다. 기하 및 위상 정보를 이용한 방법은 보다 다양한 형태의 모델들을 비교할 수 있었고 부분적인 형상 비교에도 강인하였다. 2차원 영상을 이용한 방법들은 시간 및 공간 복잡도가 높게 나타났다. 통계학 기반 방법들은 포즈 정규화 작업 없이 형상 비교가 가능하였고, 어파인 변환 및 잡음에도 강인한 결과를 보였다.
3차원 모델의 형상 유사성 평가는 의학, 기계 공학, 분자 생물학 등의 많은 분야에서 매우 중요하다. 더욱이 3차원 모델이 웹 상에 보편화됨에 따라 3차원 모델들의 분류와 검색에 관한 연구들이 활발하게 이루어지고 있다. 본 논문에서는 3차원 형상 표현 방법들과 유사성 평가에 대한 주요 개념들을 기술하고, 최근의 형상 비교에 관한 연구들을 다해상도, 위상 기하학, 2차원 영상, 통계학 기반 방법들로 분류하여 그 특징들을 분석하였다. 또한 논문에서 채택한 유일성, 강인성, 불변성, 다해상도, 효율성, 비교범위와 같은 기준을 사용하여 그 성능을 비교 평가하였다. 다해상도 기반 방법은 비교를 위한 계산 시간은 감소시킨 반면 전처리 시간은 증가시켰다. 기하 및 위상 정보를 이용한 방법은 보다 다양한 형태의 모델들을 비교할 수 있었고 부분적인 형상 비교에도 강인하였다. 2차원 영상을 이용한 방법들은 시간 및 공간 복잡도가 높게 나타났다. 통계학 기반 방법들은 포즈 정규화 작업 없이 형상 비교가 가능하였고, 어파인 변환 및 잡음에도 강인한 결과를 보였다.
Evaluation of shape similarity for 3D models is essential in many areas - medicine, mechanical engineering, molecular biology, etc. Moreover, as 3D models are commonly used on the Web, many researches have been made on the classification and retrieval of 3D models. In this paper, we describe methods...
Evaluation of shape similarity for 3D models is essential in many areas - medicine, mechanical engineering, molecular biology, etc. Moreover, as 3D models are commonly used on the Web, many researches have been made on the classification and retrieval of 3D models. In this paper, we describe methods for 3D shape representation and major concepts of similarity evaluation, and analyze the key features of recent researches for shape comparison after classifying them into four categories including multi-resolution, topology, 2D image, and statistics based methods. In addition, we evaluated the performance of the reviewed methods by the selected criteria such as uniqueness, robustness, invariance, multi-resolution, efficiency, and comparison scope. Multi-resolution based methods have resulted in decreased computation time for comparison and increased preprocessing time. The methods using geometric and topological information were able to compare more various types of models and were robust to partial shape comparison. 2D image based methods incurred overheads in time and space complexity. Statistics based methods allowed for shape comparison without pose-normalization and showed robustness against affine transformations and noise.
Evaluation of shape similarity for 3D models is essential in many areas - medicine, mechanical engineering, molecular biology, etc. Moreover, as 3D models are commonly used on the Web, many researches have been made on the classification and retrieval of 3D models. In this paper, we describe methods for 3D shape representation and major concepts of similarity evaluation, and analyze the key features of recent researches for shape comparison after classifying them into four categories including multi-resolution, topology, 2D image, and statistics based methods. In addition, we evaluated the performance of the reviewed methods by the selected criteria such as uniqueness, robustness, invariance, multi-resolution, efficiency, and comparison scope. Multi-resolution based methods have resulted in decreased computation time for comparison and increased preprocessing time. The methods using geometric and topological information were able to compare more various types of models and were robust to partial shape comparison. 2D image based methods incurred overheads in time and space complexity. Statistics based methods allowed for shape comparison without pose-normalization and showed robustness against affine transformations and noise.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
및 복잡도를 분석한 논문은 소개되지 않았다. 본 논문에서는 3차원 모델의 사용이 보편화되고 데이터베이스화 되어가는 이 시점에서 3차원 모델의 형상 유사성 평가와 관련된 전반적인 지식들을 정리하고, 최근 연구 동향을 분석및 비교하여 관련 연구들의 성능을 평가하고자 한다.
또한 그래픽스시스템을 통하여 3차원 모델을 자동적이며 빠르게 표현하고, 주어진 모델 표현에 대한 여러 조작들(변환 및 변형)이 가능한가도 형상 비교 시스템에서 중요하게 고려되어야 한다. 본 장에서는 일반적인 3차원 모델의 표현 방법들을 알아 보고, 3차원 모델의 형상 유사성 평가에 주로 이용되는 3차원 표현들이 갖춰야 할 특성들을 살펴 본다.
전반적인 구조를 살펴 본다. 또한 이를 기반으로하여 최근의 3차원 모델의 형상 유사성 평가 시스템들의 성능을 비교 분석하기 위한 기준을 제시한다.
본 절에서는 형상 비교를 위한 기본적인 특성들을 알아보고, Veltkamp[l기가 소개한 형상 평가에 대한 기하학적 특성들을 토대로 하여 최적의 유사성 평가 결과를 얻기 위한 조건들을 살펴 본다.
본절에서는 Marr, Brady, Grimson[23, 28, 29]이 제시한 2차원 영상 기반의 형상 표현 방법에 대한 기준들을 토대로, 3차원 모델간의 형상 유사성을 비교하는 시스템 구성에 필수적인 모델의 표현 방법과 측정 방법 등의 종합적인 성능 평가 기준을 제시하고자 한다. 본 논문에서는 기존의 평가 기준에 포함되는 유일성, 강인성, 불변성에 최근에 개발된 3 차원 형상 비교 시스템에 포함된 특징들을 반영하여 세 가지 추가 기준을 제시한다.
이러한 시스템들의 성능 평가를 위하여 본 논문에서는 다해상도를평가 기준으로 채택하였다. 둘째, 효율성은 비교할 3차원 모델 데이터의 수가 많아짐에 따라 그 정보들을 얼마나 빠르고 정확하게 처리할 수 있는지를 평가하기 위한 기준이다. 마지막으로 비교 범위는 형상 비교를 위해 채택한 모델 표현 형태의 범위에 대한 기준이다.
즉 형상 비교의 속도 향상을 위해서는 형상 특징들의 개수를 줄여야 한다. 본 절에서는 시간 및 공간 복잡도를 줄이기 위하여 다양한 레벨에서의 유사성 평가를 지원하는 다해상도 (multi-resolution) 기반의 방법을 이용한 Vranic[32]과 Su~ zuld[33]의 방법을 살펴본다.
두번째 개선 사항은 상기에서 추가한 세 가지 D2 함수 형태에 의해 구해진 형상 분포들의 총 합이 100%가 되도록 각 분포들에 가중치를 부여한 것이다. 이렇게 함으로써 가중치를 부여한 형상 비교가 가능해졌고 단순한 전반적인 형상비교 결과에 대한 조절을 가능케 하였다,
본 논문에서는 3차원 형상 비교 방법들의 성능을 평가하기 위하여 여섯 가지의 평가 기준으로 유일성, 강인성, 불변성, 다해상도, 효율성, 비교 범위를 제시하였다. 4장에서 소개했던 대부분의 연구들은 유일성, 강인성, 불변성, 비교범위, 그리고 효율성을 만족시키는 유사성 평가 결과를 보여주었다.
제안 방법
표현한 형상 비교 연구들도 발표되고 있다. 이 방법들은 우선 3차원 물체를 특징 정보들의 집합으로 구성한 후, 물체의 공간적 관계나 특징 사이의 차이점에 기반하여 모델간의 유사성을 평가하였다. 그 대표적인 방법들로는 gen eralized cylinders[ll], shock graphs[12], medial axes[13], skeletons[14] 등이 있다.
Arkin [26]은 다각형들의 형상 비교의 측도로 터닝 함수를 사용하였다. 우선 비교 대상이 되는 다각형들이 동일한 주변 길이를 갖도록 크기 정규화를 하고, 다각형 A와 B에 대한 비유사 정도를 와 G)b를 적용한 함수 공간에 대한 Lp 측도를 통하여 구한다. 식 ⑸는 두 다각형 A와 B의 터닝 함수거리를 구하는 계산식을 나타낸다.
본절에서는 Marr, Brady, Grimson[23, 28, 29]이 제시한 2차원 영상 기반의 형상 표현 방법에 대한 기준들을 토대로, 3차원 모델간의 형상 유사성을 비교하는 시스템 구성에 필수적인 모델의 표현 방법과 측정 방법 등의 종합적인 성능 평가 기준을 제시하고자 한다. 본 논문에서는 기존의 평가 기준에 포함되는 유일성, 강인성, 불변성에 최근에 개발된 3 차원 형상 비교 시스템에 포함된 특징들을 반영하여 세 가지 추가 기준을 제시한다. 첫째, 다해상도 방법은 대량의 3 차원 모델을 웹 상에서 점진적으로 처리하기 위하여 많이사용된다.
본 장에서는 3차원 모델의 형상 유사성 평가에 대한 최근 연구들을 다해상도 기반, 위상 기하학 기반, 2차원 영상기반, 통계학 기반의 네 가지 접근 방법으로 분류하여 XI 특징들을 살펴 본다.
다해상도 형상 표현자를 제안하였다. Vranic은 3차원 다각형 메쉬 모델을 입력으로 하여 3차원 DFT 기반의 헁상 특징을 추출하였다. 3차원 DFT는 일반적인 형상 특징들이 갖는 이동, 회전, 스케일 등에 불변적이며, 게다가 다양한 단계의 형상 특징을 표현하는데 유용하다.
3차원 DFT는 일반적인 형상 특징들이 갖는 이동, 회전, 스케일 등에 불변적이며, 게다가 다양한 단계의 형상 특징을 표현하는데 유용하다. LOD를 지원하는 형상 특징 추출을 위하여 Vranic은 bounding cube 를 사용하여 3차원 형상 모델을 N3(N은 2의 거듭제곱)개의 동일한 셀(cell)들로 복셀화(voxelization)하여 계층적인 헁상 표현 구조인 8진 트리(octree)로 구성하고, 8진 트리로구성된 모델에 대한 정보들을 공간 도메인(spatial domain) 에서 모든 N3개의 셀들에 대하여 11이나 12 Norm 함수를 이용하거나, 주파수 도메인(frequency domain)에서 N보다큰 셀들에 대하여 3D DFT를 적용하는 작업을 수행하였다. Vranic은 3차원 형상 모델의 8진 트리의 해상도를 결정하고 형상 특징의 LOD를 설정하기 위하여 주파수 도메인에서의 3차원 DFT의 적용 대상을 결정하는 값 N을 사용하였다.
최종적으로 데이터베이스로부터 이용 가능한 모든 모델들에서 입력 모델과 유사한 모델들을 검색하는 과정은 생성된 형상 특징들간의 거리인 h이나 h Norm 함수를 이용하여 수행된다. Vranic은 설계한 시스템의 성능 측정을 위하여 우선 채택한 형상 특징들의 차원을 172로 결정한후, 모델 검색 요청에 대한 평균 정확도와 결과 산출 정도를 계산하였다. 그 결과 공간적인 도메인을 이용한 복셀 기반의 형상 표현자보다 주파수 도메인의 3차원 DFT 기반의형상 표현자들을 이용한 검색 시스템이 검색 요청에 대한 평균 정확도와 결과 산출 정도 면에서는 훨씬 좋은 성능을 보인 반면에 계산 수행 시간 복잡도는 높게 나타났다.
3차원 모델의 유사한 형상 검색을 위한 알고리즘은 총 다섯 단계를 거치게 된다. 첫째, PCA(Principal Component Anal ysis) 알고리즘을 사용하여 모델의 방위를 정규화(normal ization) 한다. 둘째, 정규화된 모델을 구성하는 다각형 면들을 삼각화하고, 셋째, 삼각화된 모델을 단일 입방체로 전환한 후 그 단일 입방체를 정해진 동일 크기의 그리드 셀들로 나누어서 각 셀들에 포함된 정점들의 개수를 계산한다.
첫째, PCA(Principal Component Anal ysis) 알고리즘을 사용하여 모델의 방위를 정규화(normal ization) 한다. 둘째, 정규화된 모델을 구성하는 다각형 면들을 삼각화하고, 셋째, 삼각화된 모델을 단일 입방체로 전환한 후 그 단일 입방체를 정해진 동일 크기의 그리드 셀들로 나누어서 각 셀들에 포함된 정점들의 개수를 계산한다. 넷째, 등가 등급에 따라서 그리드 셀들을 그룹화하고, 최종적으로 3차원 형상 모델의 특징 표현자들을 계산한다.
둘째, 정규화된 모델을 구성하는 다각형 면들을 삼각화하고, 셋째, 삼각화된 모델을 단일 입방체로 전환한 후 그 단일 입방체를 정해진 동일 크기의 그리드 셀들로 나누어서 각 셀들에 포함된 정점들의 개수를 계산한다. 넷째, 등가 등급에 따라서 그리드 셀들을 그룹화하고, 최종적으로 3차원 형상 모델의 특징 표현자들을 계산한다. Suzuki 가 제시한 알고리즘은 형상 검색 시에 사용되는 특징 표현자들의 수를 감소시킴으로써 비교적 높은 정확도와 신속한질의 처리 속도를 유지하였고, 메모리의 사용을 줄임으로써 공간 복잡도를 줄일 수 있었다.
그래서 어떠한 연속 함수를 사용하느냐에 따라서 MFQ의 구조가 변화될 수 있다. 보통 사용상의 편리함으로 높이 함수(height function)7} 연속 함수로 사용되지만, Hila- ga는 유사성 평가에 있어서 어파인 변환에 불변적 특성을 보이는 측지적 거리 (geodesic distance)를 연속 함수로 사용하였다.
Ip은 Osada가 제안한 D2 함수 형태 외에도 모델의 내부에 존재하는 정점쌍으로 구해지는 D2 함수 형태와 모델의 외부에 존재하는 정점쌍으로 구해지는 D2 함수 형태 그리고 모델의 내부점과 외부점으로 이루어지는 정점쌍으로 구해지는 D2 함수 형태를 도입하였다. 두번째 개선 사항은 상기에서 추가한 세 가지 D2 함수 형태에 의해 구해진 형상 분포들의 총 합이 100%가 되도록 각 분포들에 가중치를 부여한 것이다. 이렇게 함으로써 가중치를 부여한 형상 비교가 가능해졌고 단순한 전반적인 형상비교 결과에 대한 조절을 가능케 하였다,
형상 비교는 크게 두 단계로 이루어 진다. 첫째로 3차원 형상 모델에 대한 MRG를 생성하는 것이고, 둘째로 생성된 MRG를 이용하여 3차원 모델에 대한 유사성을 평가하는 것이다. MRG를 표현하는 기본 요소들은<표 6>에 제시되어 있다.
유사성 평가는 구축된 MRG를 최상위 부모 단계로부터 최하위 자식 단계까지 순회하면서 다단계로 이루어진다. 각 MRG 노드들은 넓이와 길이 특성들을 포함하고 있고, 비교대상이 되는 모델들의 이러한 특성들에 대한 차이를 계산하여 유사성 평가를 수행하게 된다. Hilaga가 제안한 형상비교 시스템은 모델에 대한 정규화가 필요없고, 비교적 정확한 위상 기하학적 특성을 반영한 형상 비교를 수행하지만 모델의 오른쪽과 왼쪽을 구별하지 못하며, 형상 표현자를 생성하고 비교 작업을 수행하는데 소요되는 시간이 기존의 형상 비교 시스템들에 비하여 오래 걸린다는 단점이있다.
첫째 형상 함수를 채택하고, 둘째 수행하는 작업은 3차원 형상 모델들의 표면 정점들을 임의로 샘플링한다. 셋째, 샘플링된 정점 집합들로부터 형상 분포 히스토그램을 계산하고, 마지막으로 민코스키(Minkowski) Ln, earth mover의 거리함수를 사용하여 형상 분포 히스토그램들을 비교함으로써 형상간의 유사 정도를 평가하게 된다. Ip이 제안한 형상 분포 기반의 3차원 솔리드 모델 비교 시스템은 상용 CAD 시스템에 의해 생성된 모델에도 좋은 결과를 보였다.
aspect graph의 생성은 세 단계로 진행된다. 첫째로 역투영(back projection)을 이용하여 3차원 형상에 대한 투영 영상 집합을 구성하고, 둘째로 유사성 측도를 사용하여 유사한 형태를 갖는 영상들을 그룹화한다. 마지막으로 유사하다고 표시된 영상들을 결합함으로써 aspect graph를 생성하게 된다.
Funkhouser는 2차원 스케치 인터페이스를 통하여 2차원의 스케치 영상을 획득하였다. Funkhouser는 총 3개의 2차원 뷰(front, side, top)들을 스케치 인터페이스로 제공하여 2차원 스케치 질의를 얻고, 그 질의와 3차원 모델들을 투영하여 얻은 영상들간의 유사 정도를 계산하여 가장 일치하는 모델들을 검색하도록 하였다. 하지만 투영된 3차원 모델들의 외곽선 정보는 자주 사용자 입력에 의하여 끊어지는 현상이 발생한다.
된다. 첫 번째 Crawler를 통하여 웹 상의 3차원 모델 데이터베이스를 구축하고, 두 번째로 3차원 모델들을 효과적으로 검색하기 위한 텍스트와 형상 질의 기반의 색인을 구성한다. 세 번째로 텍스트 키워드와 2차원 스케치 영상그리고 3차원 스케치 등을 이용한 질의 인터페이스(query interface)를 이용하여 질의를 수행하고, 마지막으로 각각의 사용자 질의에 대하여 데이터베이스에 존재하는 모델들 중에서 가장 일치하는 16개의 모델들을 찾는 매칭 작업을 수행한다.
첫 번째 Crawler를 통하여 웹 상의 3차원 모델 데이터베이스를 구축하고, 두 번째로 3차원 모델들을 효과적으로 검색하기 위한 텍스트와 형상 질의 기반의 색인을 구성한다. 세 번째로 텍스트 키워드와 2차원 스케치 영상그리고 3차원 스케치 등을 이용한 질의 인터페이스(query interface)를 이용하여 질의를 수행하고, 마지막으로 각각의 사용자 질의에 대하여 데이터베이스에 존재하는 모델들 중에서 가장 일치하는 16개의 모델들을 찾는 매칭 작업을 수행한다. Funkhouser가 사용한 영상 매칭 알고리즘은 기존의 형상 매칭 방법들에 비하여 precision 및 recall 수치면에서 46〜245%정도의 높은 성능을 보여 주었다.
Ankerst가 제안한 유사성 평가 시스템에서는 3차원 모델들의 형상 히스토그램을 생성한 후, quadratic form 거리함수를 측도로 유사성을 측정하였다. 유클리드 거리 함수는 Ankerst가 제안한 섹터 모델로부터 생성된 형상 히스토그램에서 이웃하는 섹터에 대한 인접성을 유사성 평가에 반영할 수 없다는 문제점이 있었다.
본 절에서는 3.3절에서 제시한 평가 기준을 근거로, 최근의 형상 비교 시스템들간의 성능을 비교, 분석하고 그 결과들을 정리한다.
또한 스케일과 방위에 대한 불변성에서는 모든 시스템들에서 만족스런 결과를 보였다. 그리고 Vranic과 Suzuki, Hilaga의 시스템에서는 다해상도 표현을 채택하여 형상 유사성 계산을 위한 다양한 표현들을 적용하였다. 효율성의 경우 비교 대상이 되었던 시스템들 대부분이 정확성과 속도, 그리고 메모리 부분에서 나름대로의 기준을 통하여 실험 결과를 제시하고 있어서, 공통적인 성능 비교가 어려웠다.
본 장에서는 3차원 모델간의 형상 유사성 평가에 사용되는 기본적인 특성들과 측도들, 그리고 유사성 평가를 위한 시스템의 전반적인 구조를 살펴 본다. 또한 이를 기반으로하여 최근의 3차원 모델의 형상 유사성 평가 시스템들의 성능을 비교 분석하기 위한 기준을 제시한다.
첫째는 모델링을 위한 3차원 형상 모델의 검색이고, 둘째는 웹 환경을 통한 자동적인 3차원 형상 모델의 검색이며, 세 번째는 전자 상거래에 사용되는 3차원 형상 모델의 분류이다. 이러한 목적을 위하여 3차원 형상 표현자로서 MRG를 채택하였고, 유사성 평가의 계산적인 부분을 처리하기 위하여 측지적 거리를 측도로 채택하였다. Hilaga는 계산 비용이 높은 측지적 거리에 Dijkstra 알고리즘을 적용한 근사 방법을 제안하였다.
대상 데이터
Funkhouser는 2차원 스케치 인터페이스를 통하여 2차원의 스케치 영상을 획득하였다. Funkhouser는 총 3개의 2차원 뷰(front, side, top)들을 스케치 인터페이스로 제공하여 2차원 스케치 질의를 얻고, 그 질의와 3차원 모델들을 투영하여 얻은 영상들간의 유사 정도를 계산하여 가장 일치하는 모델들을 검색하도록 하였다.
이론/모형
최근의 3차원 형상 비교 시스템들이 웹을 기반으로 구현되고 있어 다해상도 방법을 채택하고 있다. 이러한 시스템들의 성능 평가를 위하여 본 논문에서는 다해상도를평가 기준으로 채택하였다. 둘째, 효율성은 비교할 3차원 모델 데이터의 수가 많아짐에 따라 그 정보들을 얼마나 빠르고 정확하게 처리할 수 있는지를 평가하기 위한 기준이다.
다해상도로 표현되는 MRG의 인접한 레벨의 Reeb Graph 노드들은 서로 부모-자식간의 관계를 형성하며, 또한 특정단계의 reeb graph는 그것보다 상위 단계의 reeb graph의모든 정보들을 포함한다. 따라서 이러한 특성을 보이는 MRG 를 이용한 유사성 평가는 Coarse-to-Fine 방법으로 수행된다. MRG는 3차원 형상 모델에 대한 연속 함수를 사용하여 생성된다.
이렇게 분할된 각 셀들은 히스토그램의 저장공간(bin)에 해당한다. Ankerst는 3차원 형상 히스토그램을 생성하기 위하여 3개의 공간 분할 기법인 쉘 모델(shell model), 섹터 모델(se ctor model), 스파이더웹 모델(spiderweb model)을 채택하였다. 히스토그램 생성 이전에 모델의 위치 정규화가 수행된다.
비교 범위에 있어서는 대부분의 시스템들이 닫혀진 메쉬 형태의 모델들을 비교 범위로 삼고 있었다. 다만 Hilaga, Ip, Funkhouser, Osada 의 시스템에서는 구멍이 있는 닫혀진 형태의 모델들을 유사성 평가에 사용하였다.<표 7>은 형상 유사성 평가 방법들의 자세한 비교 결과를 보여 준다.
성능/효과
대표적으로 위상 매칭(topology matching)[15], 형상 분포(shape distribution)[16] 등이 있다. 이러한 연구들은 구멍이 있거나 메쉬들이 첨가, 삭제된 메쉬 조작이나 스케일링(scaling), 회전(rotating), 기울임 (shearing), ^^Hmirror-ing) 등의 변형이 가해진 모델들의 유사성 평가에서 비교적좋은 결과를 보였다.
Vranic은 설계한 시스템의 성능 측정을 위하여 우선 채택한 형상 특징들의 차원을 172로 결정한후, 모델 검색 요청에 대한 평균 정확도와 결과 산출 정도를 계산하였다. 그 결과 공간적인 도메인을 이용한 복셀 기반의 형상 표현자보다 주파수 도메인의 3차원 DFT 기반의형상 표현자들을 이용한 검색 시스템이 검색 요청에 대한 평균 정확도와 결과 산출 정도 면에서는 훨씬 좋은 성능을 보인 반면에 계산 수행 시간 복잡도는 높게 나타났다. Vranic 이 제안한 3차원 DFT 기반의 형상 표현자는 삼각 메쉬 구조를 갖는 3차원 모델들의 공간적인 특성을 표현하는데 적합하고, 검색 시스템이 갖춰야 할 어파인 변환(이동, 회전, 스케일)등에 불변적이었으며, 형상 특징에 대한 다해상도 표현에 강인함을 보였다.
그 결과 공간적인 도메인을 이용한 복셀 기반의 형상 표현자보다 주파수 도메인의 3차원 DFT 기반의형상 표현자들을 이용한 검색 시스템이 검색 요청에 대한 평균 정확도와 결과 산출 정도 면에서는 훨씬 좋은 성능을 보인 반면에 계산 수행 시간 복잡도는 높게 나타났다. Vranic 이 제안한 3차원 DFT 기반의 형상 표현자는 삼각 메쉬 구조를 갖는 3차원 모델들의 공간적인 특성을 표현하는데 적합하고, 검색 시스템이 갖춰야 할 어파인 변환(이동, 회전, 스케일)등에 불변적이었으며, 형상 특징에 대한 다해상도 표현에 강인함을 보였다. 하지만 Vranic의 형상 표현자는 바운딩 입방체(bounding cube)를 사용하기 때문에 심한 굴곡을 갖는 모델들에 대하여 잘못된 결과가 나타날 수 있다는문제점을 가졌다.
하지만 Vranic의 형상 표현자는 바운딩 입방체(bounding cube)를 사용하기 때문에 심한 굴곡을 갖는 모델들에 대하여 잘못된 결과가 나타날 수 있다는문제점을 가졌다. 또한 Vranic이 형상 비교를 위하여 사용한 h이나 12 Norm 함수는 3차원 DFT를 기반으로 한 형상 표현자에는 적합한 측도는 아니었다. 그래서 Vranic은 h이나 h Norm 함수 대신에 하우스도르프 거리 함수나 유사측도를 위한 절충의 방법들을 사용한 측도 모델을 향후 과제로 제시하였다.
셋째, 샘플링된 정점 집합들로부터 형상 분포 히스토그램을 계산하고, 마지막으로 민코스키(Minkowski) Ln, earth mover의 거리함수를 사용하여 형상 분포 히스토그램들을 비교함으로써 형상간의 유사 정도를 평가하게 된다. Ip이 제안한 형상 분포 기반의 3차원 솔리드 모델 비교 시스템은 상용 CAD 시스템에 의해 생성된 모델에도 좋은 결과를 보였다. 하지만 계산 복잡도와 같은 시스템의 성능 뿐석 결과를 제공하지는 않고 있다.
가져왔다. 하지만 실험을 통하여 예외적인 유사성 평가 결과가 나오기도 하였으며, Shock Graph 측도 계산에 있어서의 시간 복잡도가 높았다.
세 번째로 텍스트 키워드와 2차원 스케치 영상그리고 3차원 스케치 등을 이용한 질의 인터페이스(query interface)를 이용하여 질의를 수행하고, 마지막으로 각각의 사용자 질의에 대하여 데이터베이스에 존재하는 모델들 중에서 가장 일치하는 16개의 모델들을 찾는 매칭 작업을 수행한다. Funkhouser가 사용한 영상 매칭 알고리즘은 기존의 형상 매칭 방법들에 비하여 precision 및 recall 수치면에서 46〜245%정도의 높은 성능을 보여 주었다. 이 알고리즘을 통하여 2만개의 모델을 포함한 데이터베이스로부터 약 1초 안에 원하는 모델 질의 결과를 얻을 수 있을 만큼의 검색 성능을 얻을 수 있었다.
Funkhouser가 사용한 영상 매칭 알고리즘은 기존의 형상 매칭 방법들에 비하여 precision 및 recall 수치면에서 46〜245%정도의 높은 성능을 보여 주었다. 이 알고리즘을 통하여 2만개의 모델을 포함한 데이터베이스로부터 약 1초 안에 원하는 모델 질의 결과를 얻을 수 있을 만큼의 검색 성능을 얻을 수 있었다.
메쉬의 삽입, 삭제 및 잡음 등에 대한 강인성에서는 Hilaga와 Osada의 시스템이 좋은 성능을 보였다. 또한 스케일과 방위에 대한 불변성에서는 모든 시스템들에서 만족스런 결과를 보였다.
메쉬의 삽입, 삭제 및 잡음 등에 대한 강인성에서는 Hilaga와 Osada의 시스템이 좋은 성능을 보였다. 또한 스케일과 방위에 대한 불변성에서는 모든 시스템들에서 만족스런 결과를 보였다. 그리고 Vranic과 Suzuki, Hilaga의 시스템에서는 다해상도 표현을 채택하여 형상 유사성 계산을 위한 다양한 표현들을 적용하였다.
하지만 대부분의 시스템들이 웹 기반의 검색 인터페이스와 데이터베이스를 시스템의 기본 컴포넌트들로 포함하고 있어, 비교적 정확하고, 빠른 유사성 평가 결과를 보였다. 특히 Funkhouser의 시스템은 효율적인 3차원 모델 검색을 위하여 텍스트와 2D 스케礼 3D 스케치, 그리고 3차원 모델로부터 추출하게 되는 spherical harmonics 등의 다양한 키워드를 사용하는 특징과 함께, 1초에 약 2만개의 모델로부터 유사성 평가를 할수 있을 정도의 빠른 속도를 보여주었다. 비교 범위에 있어서는 대부분의 시스템들이 닫혀진 메쉬 형태의 모델들을 비교 범위로 삼고 있었다.
후속연구
또한 Vranic이 형상 비교를 위하여 사용한 h이나 12 Norm 함수는 3차원 DFT를 기반으로 한 형상 표현자에는 적합한 측도는 아니었다. 그래서 Vranic은 h이나 h Norm 함수 대신에 하우스도르프 거리 함수나 유사측도를 위한 절충의 방법들을 사용한 측도 모델을 향후 과제로 제시하였다.
하지만 이 시스템은 데이터베이스에 등록된 모델들의 특성에 의존적이기 때문에, 기존의 다른 시스템들과의 비교평가가 어렵다는 점이 있다. Osada는 추후 연구로 다른 형상 비교 시스템들과의 성능 비교 분석을 통한 시스템의 벤치마킹(benchmarking)을 수행하고, 그에 따른 결과를 통하여 좀 더 효과적인 시스템 개발을 제시하였다.
셋째, 3차원 모델의 전체적 형상 유사성에 초점을 두고 있다. 이러한 주요 경향으로 볼 때, 향후 연구들에서는 첫째, 3차원 모델의 전체적 형상뿐만 아니라 부분적 형상에 대한 유사성 계산을 위한 알고리즘과 일반적인 모델들을 대상으로 하여 기하학적, 위상학적 형상 특징 이외에도 색상, 텍스쳐 등을고려한 비교 방법이 필요하다, 둘째, 일 대 일 모델간 형상 비교의 정확성을 향상시키는 방향과 더불어 그룹 대 그룹에 대한 형상 비교 시스템으로의 확장 또한 필요하다. 마지막으로 분자 생물학에서 신약 개발을 위한 분자간 결합 구조의 규명, 의학 분야에서 인체 장기의 변형 정도를 기반으로 한 질환 정도의 측정, 웹 상의 대량의 3차원 모델 데이터베이스 검색 등의 새로운 응용 분야에의 적용이 향후 연구로 제시되어야 한다.
이러한 주요 경향으로 볼 때, 향후 연구들에서는 첫째, 3차원 모델의 전체적 형상뿐만 아니라 부분적 형상에 대한 유사성 계산을 위한 알고리즘과 일반적인 모델들을 대상으로 하여 기하학적, 위상학적 형상 특징 이외에도 색상, 텍스쳐 등을고려한 비교 방법이 필요하다, 둘째, 일 대 일 모델간 형상 비교의 정확성을 향상시키는 방향과 더불어 그룹 대 그룹에 대한 형상 비교 시스템으로의 확장 또한 필요하다. 마지막으로 분자 생물학에서 신약 개발을 위한 분자간 결합 구조의 규명, 의학 분야에서 인체 장기의 변형 정도를 기반으로 한 질환 정도의 측정, 웹 상의 대량의 3차원 모델 데이터베이스 검색 등의 새로운 응용 분야에의 적용이 향후 연구로 제시되어야 한다.
참고문헌 (37)
Helen M. Berman and John Westbrook and Zukang Feng and Gary Gilliland and T. N. Bhat and Helge Weissig and Ilya N. Shindyalov and Philip E. Bourne, 'The Protein Data Bank,' Nucleic Acids Research, 28, pp.235-242, 2000
M. Crudele and G. J. Clapworthy and M. A. Krokos and G. Salcito and N. Vasilonikolidakis, 'A Distributed Database on the INTERNET of 3D Models of Human Pathological Organs,' 10th IEEE Symposium on Computer Based Medical Systems Slovenia 1997, pp.256-260, 1997
C. Dorai and A. K. Jain, 'COSMOS-A Representation Scheme for 3D Free-Form Objects,' IEEE Trans. PAMI, Vol.19, pp.1115-1130, 1997
Longin Jan Latecki and Rolf Lakarnper and Ulrich Eckhardt, 'Shape Descriptors for Non-rigid Shapes with a Single Closed Contour,' IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp.424-429, 2000
Seema Jaggiy and W. Clem Karlz and Stephane G. Mallatx and Alan S. Willsky, 'Silhouette Recognition using High Resolution Pursuit,' journal Pattern Recognition, Vol. 23, No.5, pp.753-771, May, 1999
Niblack W. et al., 'QBIC Project: querying images by content, using colour, texture, and shape,' Proceedings of Conference on Storage and Retrieval for Image and Video Databases, 1-3, San Jose, California, US, SPIE Vol.1908, pp.1908-1920, Feb., 1993
Chen, G. and T. D. Bui, 'Invariant Fourier-wavelet descriptor for pattern recognition,' Pattern Recognition, Vol. 32, No.7, pp.1083-1088, 1999.
D. Zhang and M. Hebert, 'Harmonic maps and their applications in surface matching,' IEEE Conf. on Computer Vision and Pattern Recognition (CVPR '99), 1999
T. Binford, 'Visual perception by computer,' IEEE Conference on Systems Science and Cybernetics, 1971
S. Skiena and W. Smith and P. Lemke, 'Reconstructing sets from interpoint distances,' Proc. of Sixth Annual Symp. on Computational Geometry, pp.332-339, 1990
E. Bardinet and S. F. Vidal and S. D. Arroyo and G. Malandain and N. P. de la Blanca Capilla, 'Structural object matching,' Technical Report DECSAI-000303, Dept. of Computer Science and AI, University of Granada, Spain, February, 2000
J. Bloomenthal and C. Lim, 'Skeletal methods of shape manipulation,' Shape Modeling and Applications, pp.44-47, 1999
Masaki Hilaga et al., 'Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes,' The proceeding of SIGGRAPH 2001, pp.203-212, 2001
R. Osada and T. Funkhouser and B. Chazelle and D. Dobkin, 'Matching 3D Models with Shape Distribution,' Proc. Shape Modeling Int'l, 2001
Remco C. Veltkamp and, Michiel Hagedoorn, 'Shape Similarity Measures, Properties and Constructions,' VISUAL 2000, pp.467-476, 1999
Arthur R. Pope, 'Model-based object recognition: A survey of recent research,' Technical Report TR-94-04, University of British Columbia, January, 1994
Loncaric, S., 'A survey of shape analysis techniques,' Pattern recognition, Vol.31(8), pp.983-1001, 1998
Christopher M. Cyr and Benjamin B. Kimia, '3D Object Recognition Using Shape Similarity-Based Aspect Graph,' ICCV 2001, pp.254-261, 2001
Grimson, W. E. L., 'Object Recognition by Computer: The Role of Geometric Constraints,' MIT Press, 1990
Christopher M. Cyr and Ahmed F. Kamal and Thomas B. Sebstian and Benjamin B. Kirnja, '2D-3D Registration Based on Shape Matching,' Mathematical Methods of Biomedical Image Analysis (MMBIA), pp.198-203, 2000
M. Teodoro and G. N. Phillips, Jr. and L. Kavraki, 'Molecular Docking : A Problem with Thousands of Degrees of Freedom,' IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, pp.960-900, 2001
Esther Arkin and Paul Chew and Daniel Huttenlocher and KIara Kedem and Joseph Mitchel, 'An efficiently corriputable metric for comparing polygonal shapes,' IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(3), pp.209-215, 1991
Veltkamp, R. C., 'Shape matching: Similarity measures and algorithms,' In Shape Modelling International (Genova), pp.188-197, 2001
D. Marr and H. Nishihara, 'Representation and recognition of the spatial organization of three-dimensional shapes,' Proceedings of the Royal Society of London, B200, pp.269-294, 1978
M. Brady, 'Criteria for representations of shape,' In J. Beck, B. Hope, and A. Rosenfeld, editors, Human and Machine Vision, Academic Press, pp.39-84, 1983
Thomas Funkhouser and Patrick Min and Michael Kazhdan and Joyce Chen and Alex Halderman and David Dobkin and David Jacobs, 'A Search Engine for 3D Models,' to appear in ACM Transactions on Graphics, pp. 83-105, January, 2003
I. Kolonias and D. Tzovaras and S. Malassiotis and M. G. Strintzis, 'Content-Based Search of VRML Models Using Shape Descriptors,' Proc. Euroimage ICAV 3D 2001 Conference, Mykonos, Greece, May, 2001
D. V. Vranic and D. Saupe, '3D Shape Descriptor Based on 3D Fourier Transform,' In Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services (ECMCS 2001) (editor K. Fazekas), Budapest, Hungary, pp.271-274, September, 2001
Suzuki, M. T., 'Web-based retrieval system for 3D polygonal models,' Joint Ninth IFSA World Congress and Twentieth NAFIPS International Conference (IFSN NAFIPS 2001), pp.2271-2276, 2001
Silvia Biasotti, 'Topological techniques for shape understanding,' CESCG 2001, 2001
G. Reeb, 'Sur les points singuliers d'une forme de Pfaff completement integrable ou dune fonction numerique [On the Singular Points of a Completely Integrable Pfaff Form or of a Numerical Function],' Comptes Randus Acad. Sciences Paris, Vol.222, pp.847-849, 1946
Cheuk Yiu Ip and Daniel Lapadat and Leonard Sieger and William C. Regli, 'Using Shape Distributions to Compare Solid Models,' 7th ACM Symposium on Solid Modeling and Applications, Saarbrken, Germany, Jun., 2002
M. Ankerst and G. Kastenmuller and H.-P. Kriegel and T. Seidl, '3D Shape Histograms for Similarity Search and Classification in Spatial Databases,' Symposium on Large Spatial Databases, pp.207-226, 1999
이 논문을 인용한 문헌
저자의 다른 논문 :
활용도 분석정보
상세보기
다운로드
내보내기
활용도 Top5 논문
해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다. 더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.