A progressive approach for similarity search on matrix

We study a similarity search problem on a raw image by its pixel values. We call this problem as matrix similarity search; it has several applications, e.g., object detection, motion estimation, and superresolution. Given a data image D and a query q, the best match refers to a sub-window of D that is the most similar to q. The state-of-theart solution applies a sequence of lower bound functions to filter subwindows and reduce the response time. Unfortunately, it suffers from two drawbacks: (i) its lower bound functions cannot support arbitrary query size, and (ii) it may invoke a large number of lower bound functions, which may incur high cost in the worst-case. In this paper, we propose an efficient solution that overcomes the above drawbacks. First, we present a generic approach to build lower bound functions that are applicable to arbitrary query size and enable trade-offs between bound tightness and computation time. We provide performance guarantee even in the worst-case. Second, to further reduce the number of calls to lower bound functions, we develop a lower bound function for a group of sub-windows. Experimental results on image data demonstrate the efficiency of our proposed methods.