[논문]3차원 그래픽 데이타베이스를 위한 시점기반의 방향관계 표현 기법

황종하; 백중환; 황수찬

3차원 그래픽 데이타베이스를 위한 시점기반의 방향관계 표현 기법
Representation Method of Viewpoint-based Directional Relationship for 3-Dimensional Graphic Databases 원문보기

정보과학회논문지. Journal of KIISE. 데이타베이스, v.30 no.2, 2003년, pp.157 - 167

황종하 (한국항공대학교 전자정보통신컴퓨터공학부) , 백중환 (한국항공대학교 전자정보통신컴퓨터공학부) , 황수찬 (한국항공대학교 전자정보통신컴퓨터공학부)

초록
AI-Helper

객체 사이에 존재하는 공간관계는 3차원 그래픽 이미지에 대한 내용기반 검색시 가장 자주 사용되는 조건 중의 하나이다. 그러나 기존 대부분의 공간관계에 대한 연구는 2차원 이미지에서 시점이 고정된 절대적인 방향관계에 패한 연구가 주를 이루고 있다. 따라서 본 논문에서는 3차원 공간에서 관측자의 시점을 기준으로 객체 사이의 방향관계를 검색할 수 있는 시점기반 방향관계 표현 기법을 제시하고 이를 이용한 검색 기법에 대해서 기술한다. 본 논문에서는 3차원 방향관계의 표현을 위해 절대시점 기반의 2차원 공간관계 표현 기법인 2D 스트링을 확장한 3D 스트링 기법을 정의하였다. 또한 관측자를 기준으로 한 객체들 간의 상대적인 방향관계를 효율적으로 추출하기 위한 기법을 제시한다. 본 논문에서 제시한 기법은 3D 스트링으로 표현된 3차원 객체의 공간관계를 2차원+1차원으로 분리하여 처리하도록 함으로서 차원의 감소를 통한 시점기반 방향관계 검색 과정을 단순화할 수 있다는 장점을 갖는다.

Abstract ▼ AI-Helper

Spatial relations among objects we one of the most frequently used searching criteria for a query based on the contents of 3-D images. However, the existing researches have mainly focused only the absolute directional relations based on a fixed viewpoint in 2-D images. So, this paper presents a representation method of viewpoint based directional relations that enables spatial relations among objects to be retrieved based on a viewpoint of an observer. The retrieval technique based on our method is a]so described. In this paper, the notion of 3D string is defined to express the spatial relations in a 3-D space. A retrieval method based on relative directional relations among objects from a viewpoint of an observer is also presented. The proposed method simplifies the retrieval of viewpoint-based directional relations because 2D+1D scheme reduces the dimension.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그러나 가상현실, 3차원 지리정보시스템 등과 같은 옹용[7, 8] 에서는 관측자의 시점이 동적으로 변할 수 있으며, 관측자의 시점이 변화함에 따라서 객체 사이의 방향관계는 서로 다르게 평가되어 지기 때문에 이러한 응용에서는 관측자의 현재 시점에 기반한 객체 사이의 방향관계 정보는 필수적인 요소이다. 따라서 본 논문에서는 3차원 공간에서 관측자의 시점을 기반으로 객체 사이의 방향관계를 검색할 수 있는 방향관계 표현기법과 검색 기법올 제시하고자한다.
본 논문에서는 2차원+1차원 공간에서 방향관계 검색을 위한 방향관계 표현 기법을 제시하였으며, 방향관계 질의 예제에 대해서 설명하였다. 그리고 Vorwerg 기법과 분석적인 성능 분석을 수행하여 본 논문에서 제시한 방향 관계 질의 기법이 우수함을 보였다.
본 논문에서는 기존 2차원 방향관계 표현 기법 가운데 하나인 2D 스트링을 확장해서 3차원 방향관계를 표현할 수는 3D 스트링 기법을 정의하였다. 또한 본 논문에서는 3차원 공간에 존재하는 객체를 각각 2차원과 1차원으로 투영하여 방향관계를 처리하였다.
본 논문에서는 기존의 2차원 방향관계 표현 기법 중 하나인 2D 스트링 기법 [9] 올 이용해서 시점기반의 3차원 방향 관계를 표현할 수 있도록 확장한 3D 스트링 기법을 제시하도록 한다. 3차원 공간에 존재하는 객체를 각각 2 차원과 1차원으로 분리 투영한 공간관계 정보를 이용하여 시점기반의 방향관계를 처리한다.
본 절에서는 관측자의 방향 벡터를 기반으로 xz-평면에서 객체 사이의 좌우, 전후 방향관계를 결정하는 기법에 대해 설명한다.

제안 방법

처리한다. 2차원의 xz-평면에 투영된 객체의 X-축과 z-축의 1D 스트링을 이용하여 좌우, 전후 방향 관계를 처리한다. 상하 방향관계는 1차원의 y-축 선분에 투영된 객체의 y-축 1D 스트링을 이용하여 처리한다.
한다. 3차원 공간에 존재하는 객체를 각각 2 차원과 1차원으로 분리 투영한 공간관계 정보를 이용하여 시점기반의 방향관계를 처리한다. 3차원의 공간관계를 2 차원H차원으로 표현하는 것은 차원올 줄여주기 때문에보다 쉽게 방향관계 검색올 수행할 수 있다는 장점이 있다.
1(a)와 같이 기준 객체를 중심으로 78개 분할 영역이 존재한다. 따라서 목적 객체의 방향관계를 식별하기 위해 78번 반복 수행하며 관측자의 시선에 따른 기준 객체에 대한 목적 객체의 방향관계를 계산한다. 따라서 Vorwerg 기법을 이용하여 두 객체 사이의 방향관계를 식별할 경우。(定) 의시간이 필요하다.
3D 스트링 기법을 정의하였다. 또한 본 논문에서는 3차원 공간에 존재하는 객체를 각각 2차원과 1차원으로 투영하여 방향관계를 처리하였다. 3차원의 공간을 2차원 +1차원으로 투영하여 방향관계를 처리하는 것은 차원을 줄여주기 때문에 보다 쉽게 방향관계 검색을 수행할 수 있으며, 또한 기존 2차원의 방향관계 연구를 쉽게 적용할 수 있다.
본 논문에서 제안한 기법에서 모든 객체 사이의 좌우, 전후, 상하 방향관계 추출은 주어진 관측자의 시점에 동일한 방향관계를 갖는 영역을 찾아서 방향관계를 단순히 반환한다. 따라서 두 객체 사이의 방향관계를 추출하는 과정이 생략된다.
14(a)의 예를 이용하여 설명한다. 본 논문에서 제안한 기법올 이용하여 방향관계를 추출하기 위해서는 2차원 공간에서 좌우, 전후 방향관계, 1차원 공간에서 상하 방향 관계를 각각 추출해야 한다.
본 논문에서는 3차원 공간에 존재하는 객체를 각각 2 차원의 xz-평면과 1 차원의 y-축 선분에 투영하여 방향 관계를 처리한다. 2차원의 xz-평면에 투영된 객체의 X-축과 z-축의 1D 스트링을 이용하여 좌우, 전후 방향 관계를 처리한다.
오른손 좌표계에서는 서로 수직하는 세 직선을 좌표축으로 사용하여 원점에서부터 떨어진 거리로 좌표값을 설정한다. 본 논문에서는 3차원 그래픽 객체의 위치 정보를 표현하기 위해서 3차원 직각 좌표계를 사용하였다
본 논문에서는 각각의 view, right, up-축올 가리켜 방향 벡터라고 한다. view-축은 仇ei夙시선) 벡터라 하고 right-축은 right 벡터 그리고 皿-축은 up 벡터라고 한다.
본 논문에서는 그림 4와 같은 3차원 그래픽 이미지 내의 각 객체를 MBR의 중심점으로 근사화해서 표현하였다. 그림 4(a)는 3차원 그래픽 이미지의 예이고 그림 4(b)는 그림 4(a)의 각 객체를 점으로 근사화한 예이다.
본 논문의 기법에서는 모든 객체 쌍의 수직 선분에 의해서 분할된 각 영역에 대해서 객체 사이의 방향 관계를 저장하고 있다. 그림 14(a)에서 만약 동일한 수직 선분을 갖지 않는 다면 최대 10개 분할 영역을 갖는다.
따라서 질의에 관련된 영역 찾기 위한 반복 수행 횟수는 최대 n(n-l)/2가 돤다. 여기서 질의에 관련된 두 객체 사이의 방향관계를 추출종I는 위한 최대 반복 횟수는 n이 되므로 본 논문에서 제안한 기법을 이용하여 2차원 공간에서 두 객체 사이의 좌우, 전후 방향관계를 식별할 경우 0(子)이 시간이 필요하다. 1차원 공간에서 두 객체 사.

이론/모형

3차원 객체 사이의 공간관계를 표현하기 위해 본 논문에서는 3D 스트링 기법을 정의하였다. 3D 스트링은 절대 시점에 대해서 객체들의 상하, 좌우, 전후 방향관계를 표현하는 기법으로 2차워 공간관계를 표현하는데 사용되는 2D 스트링 기법을 확장한 것이다.
3차원 그래픽 데이타의 방향관계 모델링을 위해 본 논문에서는 XML 기반의 3차원 그래픽 데이타 모델인 3DGML을 이용한다[14, 15]. 3DGML에서는 객체지향 개념을 이용하여 하나의 의미 단위로서 3차원 객체를 표현하고 이들간의 3차원적인 공간관계를 첨가함으로써 복잡한 3차원 그래픽 이미지를 체계적이며 간단히 모델링 할 수 있는 기능을 제공하고 있다.

성능/효과

1(a) 와 같이 객체를 직육면체로 근사화 시키고 직육면체의 각 면에 인접한 평면에 의해서 공간이 78개로 분할된다. 여기서는 설명을 쉽게 하기 위해서 2차원 공간상의 객체에 대해서 설명한다.
대해서 설명하였다. 그리고 Vorwerg 기법과 분석적인 성능 분석을 수행하여 본 논문에서 제시한 방향 관계 질의 기법이 우수함을 보였다.
따라서 2차원 공간에서 두 객체 사이의 조*, 卜 전후 방향 관계 식별은 두 기법 모두 O(r?)으로 동일하고 상하 방향 관계의 식별은 제안된 기법에서는 O(n)이다. 모는 객체 사이의 방향관계는 객체 사이의 모든 방향관계 정보를 유지하는 3D 스트링의 특성상 별도의 처리가 필요 없기 때문에 Vorwerg 기법보다 성능이 우수함을 알 수 있다.
투영기반의 모델은 원뿔기반의 공간 분할 기법에 비해서 간략한 공간 추론울 통해 보다 다양한 추론 결과를얻올 수 있으며, 또한 공간 데이타베이스에서 원뿔 기반의 공간 분할 기법보다 구현하기 쉽다는 장점올 갖는다. 반면에 원뿔기반의 공간 분할 기법은 투영기반의 공간 분할기법에 비해 16개, 32개 등과 같이 보다 높은 수의 정성적인 방향으로 확장하기 쉽다.

후속연구

있을 것이다. 그리고 향후 연구로는 데이타베이스에저장된 방대한 양의 3차원 그래픽 이미지를 효율적으로 검색하기 위한 방향관계 인덱스 기법에 대한 연구가 필요하다
본 논문에서 제시한 시점기반의 방향관계 표현 기법은 3차원 지리정보시스템, 회전된 2차원 이미지의 방향관계, 로봇 네비게이션 등과 같은 응용에서 효율적으로 적용될 수 있을 것이다. 그리고 향후 연구로는 데이타베이스에저장된 방대한 양의 3차원 그래픽 이미지를 효율적으로 검색하기 위한 방향관계 인덱스 기법에 대한 연구가 필요하다

참고문헌 (17)

Guting., R. H., 'An Introduction to Spatial Database Systems,' Vary Large Data Bases Journal, Vol. 3, pp. 357-399, Oct., 1994

상세보기
Egenhofer, M. J. and Franzosa, R, 'Point-Set Topological Spatial Relations,' International Journal of Geographic Information Systems, Vol. 5, No.2, pp. 160-174, 1991

상세보기
Egenhofer, M. J. and Franzosa, R, 'One the Equivalence of Topological Relations,' International Journal of Geographic Information Systems, Vol. 9, No.2, pp. 133-152, 1992
Papadias, D., Egenhofer, M. J. and Sharma, J., 'Hierarchical Reasoning about Direction Relations,' Proceedings of the 4th ACM Workshop on Advances in Geographic Information Systems, pp. 105-112, Nov., 1996
Shashi, S. and Xuan, L. 'Direction as a Spatial Object: a Summary of Results,' Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems, pp. 69-75, Nov., 1998
Xuan, L., Shashi, S., and Sanjay, C., 'Processing Object-orientation-based Direction Queries: A summary of Results,' Proceedings of the 8th ACM International Symposium on Advances in Geographic Information Systems, pp. 69-76, Nov., 2000
Jie, S., 'Visualizing 3-D Geographiccal Data with VRML,' IEEE Proceedings of the Computer Graphics International Conferences, pp. 108-110, 1998
Menendez, R. G. and Bernard, J. E., 'Flight Simulation in Synthetic Environments,' IEEE Proceedings of the Digital Avionics Systems Conferences, Vol. 1, pp. 2.A.5_1-2.A.5_6, 2000
Chang, S. K., Shi, Q. Y, and Yan, C. W., 'Iconic Indexing by 2-D Strings,' IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 9, No.3, pp. 413-428, May, 1987
Frank, A. U., 'Qualitative Spatial Reasoning: Cardinal Directions as an Example,' International Journal of Geographic Information Systems, Vol. 10, No.3, pp. 269-290, 1996

상세보기
Hong, J. H., Qualitative Distance and Direction Reasoning in Geographic Space, Ph. D. Thesis, Department of Surveying Engineering, University of Main, 1994
Peuquet, D. and Zhan, C. X., 'An Algorithm to Determine the Directional Relationship Between Arbitarily-Shaped Plygons in the Plane,' Pattern Recognition, Vol. 20, No.1, pp. 65-74, 1987

상세보기
Vorwerg, C., Socher, G., Fuhr, T., Sagerer, G., and Rickheit, G., 'Projective relations for 3D space: Computational model, application, and psychological evaluation,' In AAAI'97, Providence, Rhode Island, pp. 159-164, 1997
Jongha, H., Keunghea, L., and Soochan, H., '3DGML: A 3-Dimensional Graphic Information Retrieval System,' Web Intelligence: Reasearch and Development, Vol. 2198, pp. 282-291, Lecture Notes in Artificial Intelligence, 2001
황종하, 황수찬, '3차원 그래픽 이미지를 위한 XML 데이타베이스 시스템,' 정보과학회논문지:데이타베이스, 29권 2호, pp.110-118, 2002.4

원문보기 상세보기
Schlieder, C, 'Representing Visible Locations for Qualitative Navigation,' In Piera, N., and Singh, M. G., editors, Qualitative Reasoning and Decision Technologies, pp. 523-532, 1993
Schlieder, C., 'Ordering Information and Symbolic Projection,' In Chang, S. K., Jungert, E., and Tortora, G., editors, Intelligent Image Database Systems, pp. 115-140, 1996

저자의 다른 논문 :

표제어: 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

연합인증