Boundary image matching supporting partial denoising using time-series matching techniques

Abstract

In this paper, we deal with the problem of boundary image matching which finds similar boundary images regardless of partial noise exploiting time-series matching techniques. Time-seris matching techniques make it easier to compute distances for similarity identification, and therefore it is feasible to perform boundary image matching even on a large image database. To solve this problem, we first convert all boundary images into times-series and derive partial denoising time-series. The partial denoising time-series is generated from an original time-series by removing partial noise; that is, it is obtained by changing a position of partial denoising from original time-series. We then introduce the partial denoising distance, which is the minimum distance from a query time-series to all possible partial denoising time-series generated from a data time-series, and propose partial denoising boundary image matching using the partial denoising distance as a similarity measure. Computing the partial denoising distance, however, incurs a severe computational overhead since there are a large number of partial denoising time-series to be considered. Thus, in order to improve its performance, we present a tight lower bound of the partial denoising distance and also optimize the computation of the partial denoising distance. We finally propose range and k-NN query algorithms according to a query processing method for partial denoising boundary image matching. Through extensive experiments, we show that our lower bound-based approach and the optimization method of the partial denoising distance improve search performance by up to an order of magnitude.