삼각 부등식을 이용한 효율적인 회전-불변 윤곽선 이미지 매칭 = Efficient Rotation-Invariant Boundary Image Matching Using the Triangular Inequality

국문 초록 (Abstract)

윤곽선 이미지 매칭에서 두 이미지 시계열 간 회전-불변 거리는 많은 유클리디안 거리 계산을 필요로 하는 고비용의 연산이다. 본 논문에서는 삼각 부등식(triangular inequality)을 사용하여 유클리디안 거리 계산을 크게 줄이는 획기적인 해결책을 제시한다. 이를 위해, 먼저 질의 시퀀스의 자체 회전 거리의 개념을 제시하고, 이를 삼각 부등식과 함께 사용하면 많은 수의 거리 계산을 줄일 수 있음을 보인다. 다음으로, 자체 회전 거리 하나만으로 모든 가능한 자체 회전 거리를 대신할 수 있음을 정형적으로 증명한다. 실험 결과, 제안한 기법은 기존 기법에 비해 최대 수 배까지 성능을 향상시킨 것으로 나타났다.

다국어 초록 (Multilingual Abstract)

Computing the rotation-invariant distance between image time-series is a time-consuming process that incurs a lot of Euclidean distances for all possible rotations. In this paper we propose an innovative solution that significantly reduces the number of Euclidean distances using the triangular inequality. To this end, we first present the notion of self rotation distance and show that, by using the self rotation distance with the triangular inequality, we can prune many unnecessary distance computations. We next present that only one self-rotation is enough for all self-rotation distances required. Experimental results show that our self rotation distance-based methods outperform the existing methods by up to an order of magnitude.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구 및 기존 알고리즘
• 3. 삼각 부등식 기반 회전-불변 매칭 알고리즘
• 4. 성능 평가
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 김범수, "시계열 이동평균 변환을 이용한 노이즈 제어 윤곽선 이미지 매칭" 한국정보과학회 36 (36): 327-340, 2009

2 E. J. Keogh, "Supporting Exact Indexing of Arbitrarily Rotated Shapes and Periodic Time Series under Euclidean and Warping Distance Measures" 18 (18): 611-630, 2009

3 "SQUID"

4 M. Vlachos, "Rotation Invariant Indexing of Shapes and Line Drawings" 131-138, 2005

5 W.-K. Loh, "Fast Recognition of Asian Characters Based on Database Methodologies" 37-48, 2007

6 E.Keogh, "Exact Indexing of Dynamic Time Warping" 406-417, 2002

7 W. K. Pratt, "Digital Image Processing, 4th Ed." Eastman Kodak Company 2007

8 R. C. Gonzalez, "Digital Image Processing, 2nd Ed" Prentice Hall 2002

9 원정임, "DNA 시퀀스 데이타베이스를 위한 실용적인 유사 서브 시퀀스 검색 기법" 한국정보과학회 34 (34): 119-132, 2007