Efficient Rotation-Invariant Boundary Image Matching Using the Envelope-based Lower Bound

본 논문에서는 윤곽선 이미지 매칭에서 회전-불변 거리 계산의 효율적 방법을 제안한다. 회전-불변 거리 계산은 이미지 시계열을 한 칸씩 회전하면서 매번 유클리디안 거리를 계산해야 하는 고비용의 연산이다. 본 논문에서는 엔빌로프 기반 하한을 사용하여 회전-불변 거리 계산을 크게 줄이는 획기적인 해결책을 제시한다. 이를 위해, 먼저 질의 시퀀스 대상의 단일 엔빌로프 작성과 이의 하한 개념을 제시하고, 이를 회전-불변 거리 계산에 사용하면 많은 수의 회전-불변 거리 계산을 줄일 수 있음을 보인다. 그런데, 단일 엔빌로프 기법은 하나의 엔빌로프가 가능한 모든 회전 시퀀스를 포함하기 때문에 하한이 커지고, 이에 따라 매칭 성능이 저하되는 문제점이 있다. 이러한 문제점을 해결하기 위하여, 본 논문에서는 회전 구간의 개념을 도입하여 단일 엔빌로프 기반 하한을 다중 엔빌로프 기반 하한 개념으로 확장한다. 또한, 다중 엔빌로프 기법에서 회전 구간을 결정하기 위한 방법으로 동일-너비 기법과 엔빌로프 최소화 기법을 제안한다. 실험 결과, 제안한 엔빌로프 기반 매칭 기법은 기존 기법에 비해 최대 수 배에서 수십 배까지 매칭 성능을 향상시킨 것으로 나타났다. In this paper we present an efficient solution to rotation?invariant boundary image matching. Computing the rotation-invariant distance between image time-series is a time-consuming process since it requires a lot of Euclidean distance computations for all possible rotations. In this paper we propose a novel solution that significantly reduces the number of distance computations using the envelope-based lower bound. To this end, we first present how to construct a single envelope from a query sequence and how to obtain a lower bound of the rotation-invariant distance using the envelope. We then show that the single envelope-based lower bound can reduce a number of distance computations. This approach, however, may cause bad performance since it may incur a larger lower bound by considering all possible rotated sequences in a single envelope. To solve this problem, we present a concept of rotation interval, and using the rotation interval we generalize the envelope-based lower bound by exploiting multiple envelopes rather than a single envelope. We also propose equi-width and envelope minimization divisions as the method of determining rotation intervals in the multiple envelope approach. Experimental results show that our envelope-based solutions outperform existing solutions by one or two orders of magnitude.