A Progressive Approach For Similarity Search On Matrix

Abstract

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.

Publication Date

1-1-2015

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

9239

Number of Pages

373-390

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/978-3-319-22363-6_20

Socpus ID

84984608884 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84984608884

This document is currently not available here.

Share

COinS