[논문]구면좌표계 기반에서 3차원 모델 검색

송주환; 최성희

[국내논문] 구면좌표계 기반에서 3차원 모델 검색
3D Model Retrieval based on Spherical Coordinate System 원문보기

電子工學會論文誌. Journal of the institute of electronics engineers of Korea. IE. 산업전자, v.46 no.1, 2009년, pp.37 - 43

초록
AI-Helper

본 논문에서는 구면 좌표계 기반에서 3차원 모델을 검색하는 새로운 알고리즘을 제안한다. 3차원 모델 위의 임의의 점들의 좌표(x, y, z)를 구하고, 이 좌표들을 구면좌표계의 좌표로 변환한다. 이 샘플들의 위도(zenith)의 분포를 3차원 모델의 특징으로 정의한다. 임의의 샘플 좌표를 구하기 위해 우리는 Osada가 제안한 방법을 사용하였고, 좌표축을 정규화하기 위하여 PCA 알고리즘을 사용하였다. 데이터는 프린스턴 대학의 벤치마크 데이터를 사용하였으며 Vranic이 제안한 depth buffer-based feature vector 알고리즘과 비교하였고, 본 논문에서 제안한 방법이 정확도에서 12.6% 더 정확하게 모델을 검색하였다.

Abstract ▼ AI-Helper

In this paper, we propose a new algorithm for 3D model retrieval based on spherical coordinate system. We obtains sample points in a polygons on 3D model. We convert a point in cartesian coordinates(x, y, z) to it in spherical coordinate. 3D shape features are achieved by adopting distribution of zenith of sample point in spherical coordinate. We used Osada's method for obtaining sample points on 3D model and the PCA method for the pose standardization 3D model. Princeton university's benchmark data was used for this research. Experimental results numerically show the precision improvement of proposed algorithm 12.6% in comparison with Vranic's depth buffer-based feature vector algorithm.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

구현 및 평가, IV. 결론으로 기술하였다.
하나의 모델과 비교하기 위한 다른 모델이 크기(scaling)가 다르거나, 무게 중심의 위치 (translation)가 다르거나, 또는 회전(rotation)이 되어있는 경우에는 더더욱 검색확률이 낮아지게 된다 이문제를 극복하기 위해서 우리는 무게중심을 원점으로 이동하고, 모델을 (-1, -1, -1)에서 (1, 1, 1)사이에 옮기고, PCA 알고리즘을 적용하여 모델의 회전 문제를 해결하였지만 비교하기에는 어렵다. 이를 극복하기 위해서 우리는 모델을 1차원 형태로 표현하는 방법을 연구하였다.
본 논문은 3차원 오브젝트의 검색에 대한 알고리즘을 제안하였다. 3차원 모델의 특징 벡터를 구하는 과정은 각 모델을 구성하는 폴리곤 위에서 5000개의 샘플 좌표를 구하고 이 좌표들을 구면 좌표계로 변환한다.

가설 설정

본 논문은 모든 3차원 모델이 폴리곤으로 구성되었음을 가정으로 시작하였다. 3차원 모델에 대한 데이터는 프린스턴 대학(PRnceton University)의 벤치마크 모델刼에서 爲그룹의 600개의 모델을 활용하였다.
우리는 모델을 구성하는 폴리곤은 삼각형으로만 구성되어 있다고 가정한다. 만약 사각형이나 오각형의 폴리곤이 존재하면 각각을 2개, 3개로 분할하여 삼각형으로 만든 후에 사용한다.
2) 그 지점에서 xz 평면 안에 있으면서 z축에서부터 0만큼 회전한다.

제안 방법

본 논문은 3차원 검색에 대한 정확도에 초점을 맞추어 알고리즘을 구현하였다. 즉, 정확한 샘플추출을 위하여 폴리곤의 넓이에 비례하여 난수를 발생하여 샘플을 추출하였다.
알고리즘을 구현하였다. 즉, 정확한 샘플추출을 위하여 폴리곤의 넓이에 비례하여 난수를 발생하여 샘플을 추출하였다. 추출된 샘플을 구면 좌표계로 변환.
추출된 샘플을 구면 좌표계로 변환. 특징벡터를 추출하여 데이터베이스에 저장한 후 3차원 모델을 검색하여 보다 정확한 모델을 검색하게 되었다. 논문의 구성으로는 n.
첫째는 전처리과정으로 샘플 데이터를 추출하여 구면좌표계로 변환으로 특징 벡터를 추출하여 데이터베이스에 저장하는 과정이다. 둘째는 검색하고자 하는 쿼리 모델이 들어오면 첫 번째 과정과 동일한 방법으로 특징 벡터를 추출하여 데이터베이스에 저장된 데이터와 비교하여 유사한 모델을 검색하는 과정을 도식화 하였다.
첫 번째 난수를 사용하여 폴리곤을 선택하는 과정에서 서로 다른 면적을 가진 폴리곤이 선택될 확률이 그 면적에 비례하도록 하기 위하여 전체 폴리곤의 면적을 구하고, 그 면적이 최대가 될 수 있는 난수를 발생하고' 그 난수가 포함되는 폴리곤을 선택한다. 나머지 2개의 난수는 삼각형 위의 임의의 점을 균등한 확률로 선택되도록 하기 위해서 식(1)에 대입하여 임의의 샘플 좌표를 구한다.
각 모델에 대한 샘플 데이터를 구한 후 특징 벡터를 추출하기 위해 3차원의 좌표계를 구면 좌표계로 변환하였다. 구면좌표계(spherical coordinate system)는 3차원 공간상의 점들을 구 형태로 나타내는 좌표계로, 일반적으로 侦, 们</>)로 나타내며, r = 1의 단위원을 표현하기 때문에 구면좌표계라고 하였다.
이를 해결하기 위하여 X, z축에 대해서도 각 축을 구면좌표계의 극으로 지정하여 샘플의 개수 분포를 구해 총 180(60 * 3)개의 값특징 벡터로터로 사용한다.<그림 5>는 임의의 한 모델을 3개의 축에 대해서 각각 특징 벡터를 구한 결과를 나타낸 것이다.
값들로 표현된다. 쿼리 모델의 특징벡터와 데이터베이스에 저장된 모델의 특징 벡터를 비교하기 위하여 우리는 각 그룹 단위로 3회씩 총 9회의 값의 차이를 비교를 하게 되고, 그 값이 가장 작은 값을 가지는 순서로 검색하게 된다.
3차원 모델의 특징 벡터를 구하는 과정은 각 모델을 구성하는 폴리곤 위에서 5000개의 샘플 좌표를 구하고 이 좌표들을 구면 좌표계로 변환한다. 위도에 따라 균등 분할하여 각 범위에 포함되는 샘플의 분포를 이 모델의 특징 벡터로 정의하고, 그 특징 벡터를 이용하여 검색하는 방법을 제안한다. 본 논문의 성능을 평가하기 위해 VraNc이 연구한 깊이기반 특징벡터 (depth buffer-based feature vector) 알고리즘과 비 교해본 결과 본 논문의 결과가 Vranic의 알고리즘보다 검색 결과가 우수함을 알 수 있었다.

대상 데이터

가정으로 시작하였다. 3차원 모델에 대한 데이터는 프린스턴 대학(PRnceton University)의 벤치마크 모델刼에서 爲그룹의 600개의 모델을 활용하였다.
이를 해결하기 위하여。에서 7T 사이를 동일한 크기의 여러 개의 범위(버킷이라 명명)로 나누어각 버킷에 해당하는 샘플의 개수의 분포를 특징 벡터로 결정한다. 버킷의 개수를 180개(1° 간격), 90개(2° 간격), 60개(3° 간격), 36개(5° 간격), 18개(10° 간격)로 분할하여 테스트하였더니 60개가 가장 검색률이 좋아 본 논문에서는 60개를 사용하였다.
프린스턴 벤치마크 데이터는 웹에서 수집된 3차원 폴리곤 구조로 이루어졌다. 각 모델은 기하학적 정보를 가진 오브젝트 파일 포맷(Object File Format; .
1. 600 3D models.

데이터처리

Net 2005로 알고리즘을 구현하였다. 검색을 위한 특징 벡터는 데이터베이스 Microsoft SQL Server 2000을 사용하였으며, 검색 데이터는 프린스턴(Princeton) 대학의 벤치마크 데이터를 이용하여 3차원 오브젝트 검색알고리즘을 평가하였다.
제안한 알고리즘과 Vranic回의 Depth Buffer-Based Feature Vector 알고리즘과 비교 평가하였다.<그림 6>, <그림 7>, <그림 8>, <그림 9>에 각각 fish, biplane, race_car, sports_car를 검색한 결과를 나타내었다.

이론/모형

이렇게 다른 3차원 모델에 대해 동일한 규칙으로 검색하기 위하여 우리는 3차원 모델의 각 폴리곤위의 임의의 좌표를 추출하여 사용한다. 폴리곤 위의 임의의 점들을 샘플로 추줄하는 방법으로 Osada闾가 제안한 방법을 사용하였다.
3차원 모델들이 임의의 방향을 향해 구성되어있어, 이것들을 모두 같은 방향으로 정규화하기 위하여 우리는 FCACprincipal conponent analysis)# 사용하였다. 추출한 샘플 데이터를 PCA 알고리즘을 적용하여 3개의 주축이 만들어지고, 그 축을 좌표축으로 하는 공간에 각 샘플들이 위치하게 된다.
2GHz의 Pentium 4 CPU를 가진 개인용 컴퓨터에서Microsoft 사의의 Visual C#.Net 2005로 알고리즘을 구현하였다. 검색을 위한 특징 벡터는 데이터베이스 Microsoft SQL Server 2000을 사용하였으며, 검색 데이터는 프린스턴(Princeton) 대학의 벤치마크 데이터를 이용하여 3차원 오브젝트 검색알고리즘을 평가하였다.

성능/효과

이 차트에서 굵은 선으로 그려진 그래프는 본 논문에서 제안한 방법이며, 나머지는 Vranic이 제안한 방법이다. 본 논문에서 제안한 방법이 성능 비교에서 더 우수함을 알 수 있었다.
위도에 따라 균등 분할하여 각 범위에 포함되는 샘플의 분포를 이 모델의 특징 벡터로 정의하고, 그 특징 벡터를 이용하여 검색하는 방법을 제안한다. 본 논문의 성능을 평가하기 위해 VraNc이 연구한 깊이기반 특징벡터 (depth buffer-based feature vector) 알고리즘과 비 교해본 결과 본 논문의 결과가 Vranic의 알고리즘보다 검색 결과가 우수함을 알 수 있었다.
쿼리 모델 검색 시 유사 모델이 처음 발견되는 정확도 (precision)는 Vranic의 알고리즘은 평균 0.4382이고, 제안한 알고리즘은 0.4934로 12.6%의 효율이 있음을 알 수 있었다. 향후에는 특징 벡터의 개수를 줄이면서도 3 차원 모델을 더 정확히 표현할 수 있는 알고리즘에 대한 연구를 할 계획이다.

후속연구

6%의 효율이 있음을 알 수 있었다. 향후에는 특징 벡터의 개수를 줄이면서도 3 차원 모델을 더 정확히 표현할 수 있는 알고리즘에 대한 연구를 할 계획이다.

참고문헌 (14)

B. Bustos, D. A. Keim, D. Saupe, T. Schreck, and D. V. Vrani'c, 'Feature-Based Similarity Search in 3D Object Databases,' ACM Computing Surveys, Vol. 37, No. 4, pp.345-387, 2005

상세보기
J. D. Wolter, T. C. Woo, and R. A. Volz, 'Optimal Algorithms for Symmetry Detection in Two and Three Dimensions,' The Visual Computer, Vol. 1, No. 1, pp.37-48, 1985

상세보기
X. Y. Jiang and H. Bunke, 'Determination of the Symmetries of Polyhedra and an Application to Object Recognition,' Lecture Note in Computer Science, Vol. 553, pp.113-121, 1991
C. Sun and D. Si, 'Fast Reflectional Symmetry Detection Using Orientation Histograms,' Real-Time Imaging, Vol. 5, pp.63?74, 1999

상세보기
S. Biasotti, S. Marini, M. Mortara, and G. Patan'e, 'An Overview of Properties and Efficacy of Topological Skeletons in Shape Modeling,' International Conference on Shape Modeling and Application, pp.245-256, 2003
D. Chen, X. Tian, Y. Shen, and M. Ouhyoung, 'On Visual Similarity Based 3D Model Retrieval,' Computer Graphics Forum, pp.223-232, 2003.
J. Song and F. Golshani, '3D Object Feature Extraction Based on Shape Similarity,' International Journal on Artifical Intelligence Tools, Vol. 12, pp.37-56, 2003

상세보기
R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin, 'Shape Distributions,' Transaction on ACM Graphics, Vol. 21, No. 4, pp.807-832, 2002

상세보기
송주환, 최성희, 권오봉, '반사 대칭을 이용한 3차원 오브젝트 검색에 관한 연구,' 대한전자공학회논문지, 제 44권, 제 4호, 48-54쪽, 2007년

원문보기 상세보기
박기태, 황혜정, 문영식, '형태 인덱스와 정규 곡률을 이용한 3차원 모델 검색,' 대한전자공학회논문지, 제 44권, 제 2호, 33-41쪽, 2007년

원문보기 상세보기
이선임, 김재협, 문영식, '개선된 레이 캐스팅을 이용한 3차원 객체 검색 기법,' 대한전자공학회논문지, 제 43권, 제 2호, 72-80쪽, 2006년

원문보기 상세보기
송주환, 최성희, 권오봉, '판별분석을 이용한 효율적인 3차원 모델 검색,' 대한전자공학회논문지, 제 45권, 제 2호, 98-103쪽, 2008년

원문보기 상세보기
P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser, 'The Princeton Shape Benchmark,' Shape Modeling Applications, 2004. Proceedings , pp.167-178, 2004
D. V. Vranic, '3D Model Retrieval,' Ph. D. Thesis, University of Leipzig, Germany, 2004

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증