A Multi-step Strategy for Approximate Similarity Search in Image Databases

Abstract

Many strategies for similarity search in image databases assume a metric and quadratic form-based similarity model where an optimal lower bounding distance function exists for filtering. These strategies are mainly two-step, with the initial 'filter' step based on a spatial or metric access method followed by a 'refine' step employing expensive computation. Recent research on robust matching methods for computer vision has discovered that similarity models behind human visual judgment are inherently non-metric. When applying such models to similarity search in image databases, one has to address the problem of non-metric distance functions that might not have an optimal lower bound for filtering. Here, we propose a novel three-step 'prune-filter-refine' strategy for approximate similarity search on these models. First, the 'prune' step adopts a spatial access method to roughly eliminate improbable matches via an adjustable distance threshold. Second, the 'filter' step uses a quasi lower-bounding distance derived from the non-metric distance function of the similarity model. Third, the 'refine' stage compares the query with the remaining candidates by a robust matching method for final ranking. Experimental results confirmed that the proposed strategy achieves more filtering than a two-step approach with close to no false drops in the final result.