Envelope-based boundary image matching for smart devices under arbitrary rotations

摘要

Recently, a variety of smart devices have been introduced for entertainment or industrial purposes, and there have been a lot of needs for image matching applications exploiting a large number of images stored in those smart devices. Boundary image matching identifies similar boundary images using their corresponding time-series, and supporting the rotation invariance is crucial to provide more intuitive matching results not only in conventional computing devices but also in smart devices such as smart-phones, smart pads, and smart cameras. Computing, the rotation-invariant distance between image time-series, however, is a very time-consuming process since it requires a lot of Euclidean distance computations for all possible rotations. We here note that, for smart devices, a very efficient mechanism of computing rotation-invariant distances is required. For this purpose, in this paper we use a novel notion of envelope-based lower bound proposed by Keogh et al. (VLDB J 18:611-630, 2009) to reduce the number of distance computations dramatically. With the help of Keogh et al.'s prior work (Keogh in Proceedings of the 28th International Conference on Very Large Data Bases, 406-417,2002; Keogh et al. in VLDB J 18:611-630, 2009), we first explain 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 explain that the single envelope lower bound can reduce a number of distance computations. This single envelope approach, however, may cause bad performance since it may incur a larger lower bound due to considering all possible rotated sequences in a single envelope. To solve this problem, we present a concept of rotation interval, and using the concept of multiple envelopes proposed by Keogh et al. (VLDB J 18:611-630, 2009) with these rotation intervals, we then 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 multi-envelope approach. We further present an advanced multi-step matching algorithm that progressively prunes search spaces by dividing the rotation interval in half. Experimental results show that our envelope-based solutions outperform naive solutions by one to three orders of magnitude. We believe that this performance improvement makes our algorithms very suitable for smart devices.