엔빌로프 기반 하한을 사용한 효율적인 회전-불변 윤곽선 이미지 매칭
Efficient Rotation-Invariant Boundary Image Matching Using the Envelope-based Lower Bound
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 윤곽선 이미지 매칭에서 회전-불변 거리 계산의 효율적 방법을 제안한다. 회전-불변 거리 계산은 이미지 시계열을 한 칸씩 회전하면서 매번 유클리디안 거리를 계산해야 하는 고비용의 연산이다. 본 논문에서는 엔빌로프 기반 하한을 사용하여 회전-불변 거리 계산을 크게 줄이는 획기적인 해결책을 제시한다. 이를 위해, 먼저 질의 시퀀스 대상의 단일 엔빌로프 작성과 이의 하한 개념을 제시하고, 이를 회전-불변 거리 계산에 사용하면 많은 수의 회전-불변 거리 계산을 줄일 수 있음을 보인다. 그런데, 단일 엔빌로프 기법은 하나의 엔빌로프가 가능한 모든 회전 시퀀스를 포함하기 때문에 하한이 커지고, 이에 따라 매칭 성능이 저하되는 문제점이 있다. 이러한 문제점을 해결하기 위하여, 본 논문에서는 회전 구간의 개념을 도입하여 단일 엔빌로프 기반 하한을 다중 엔빌로프 기반 하한 개념으로 확장한다. 또한, 다중 엔빌로프 기법에서 회전 구간을 결정하기 위한 방법으로 동일-너비 기법과 엔빌로프 최소화 기법을 제안한다. 실험 결과, 제안한 엔빌로프 기반 매칭 기법은 기존 기법에 비해 최대 수 배에서 수십 배까지 매칭 성능을 향상시킨 것으로 나타났다.
Abstract
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.
참고문헌 (21)
- Agrawal, R, "Efficient Similarity Search in Sequence Databases In Proc. the 4th Int'l Conf. on Foundations of Data Organization and Algorithms", pp.69~94 (1993), Illinois
- Faloutsos, C, "Fast Subsequence Matching in Time‐Series Databases", In Proc. Int'l Conf. on Management of Data, ACM SIGMOD, pp.419~429 (1994)
- Keogh, E, "Exact Indexing of Dynamic Time Warping", In Proc. the 28th Int’l Conf. on Very Large Data Bases, pp.406~417 (2002)
- Moon, Y.-S, "General Match: A Subsequence Matching Method in Time‐Series Databases Based on Generalized Windows", In Proc. Int’l Conf. on Management of Data, ACM SIGMOD, pp.382~393 (2002)
- 노웅기, "Fast Recognition of Asian Characters Based on Database Methodologies", British National Conference on Databases (BNCOD), pp.37~48 (2007), BNCOD
- Vlachos, M, "Rotation Invariant Indexing of Shapes and Line Drawings", In Proc. of ACM Conf. on Information and Knowledge Management, pp.131~138 (2005)
- Kim, B.-S, "Noise Control Boundary Image Matching Using Time-Series Moving Average Transform", In Proc. of the 19th Int’l Conf. on Database and Expert Systems Applications (DEXA 2008) (2008)
- Lee, A. J. T, "A Novel Filtration Method in Biological Sequence Databases", Pattern Recognition Letters, 28(4), pp.447~458 (2007)
- Keogh, E. J, "Supporting Exact Indexing of Arbitrarily Rotated Shapes and Periodic Time Series under Euclidean and Warping Distance Measures", The VLDB Journal, 18(3), pp.611~630 (2009)
- Han, W.-S, "Ranked Subsequence Matching in Time-Series Databases", In Proc. the 33rd Int’l Conf. on Very Large Data Bases, pp.423~434 (2007)
- Chan, K.-P, "Haar Wavelets for Efficient Similarity Search of Time-Series: With and Without Time Warping", IEEE Trans. on Knowledge and Data Engineering, 15(3), pp.686~705 (2003)
- Gonzalez, R. C, "Digital Image Processing, 2nd Ed" (2002), Prentice Hall
- Pratt, W. K, "Digital Image Processing, 4th Ed" (2007), Eastman Kodak Company
- Theoharatos, C, "A Generic Scheme for Color Image Retrieval Based on the Multivariate Wald-Wolfowitz Test", IEEE Trans. on Knowledge and Data Engineering, 17(6), pp.808~819 (2005)
- Do, M. N, "Wavelet-Based Texture Retrieval Using Generalized Gaussian Density and Kullback–Leibler Distance", IEEE Trans. on Image Processing, 11(2) (2002)
- Wang, Z, "Leaf Image Retrieval with Shape Features", In Proc. 4th Int’l Conf. on Advances in Visual Information Systems, pp.477~487 (2000), Lyon, France
- Zhang, D. Z, "Review of Shape Representation and Description Techniques", Pattern Recognition, 37(1), pp.1~19 (2003)
- Chen, y.-W, "The C-Chain Code – A New Method For Coding 3D Curves", In Proc. The 25th Asilomar Conf. on Signals, Systems and Computers, pp.472~476 (1991)
- Grosky, W. I, "Index-Based Object Recognition in Pictorial Data Management", Computer Vision, Graphics, and Image Processing, 52(3), pp.416~436 (1990)
- Bebis, G, "Curvature Scale‐space‐driven Object Recognition with an Indexing Scheme Based on Artificial Neural Networks", Pattern Recognition, 32(7), pp.1175~1201 (1999)