This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Search for Publication

Year(s) from:  to 
Keywords (separated by spaces):

Exploiting spatial overlap to efficiently compute appearance distances between image windows

Bogdan Alexe, Viviana Petrescu and Vittorio Ferrari
NIPS 2011
Granada, Spain, December 2011


We present a computationally efficient technique to compute the distance of high-dimensional appearance descriptor vectors between image windows. The method exploits the relation between appearance distance and spatial overlap. We derive an upper bound on appearance distance given the spatial overlap of two windows in an image, and use it to bound the distances of many pairs between two images. We propose algorithms that build on these basic operations to efficiently solve tasks relevant to many computer vision applications, such as finding all pairs of windows between two images with distance smaller than a threshold, or finding the single pair with the smallest distance. In experiments on the PASCAL VOC 07 dataset, our algorithms accurately solve these problems while greatly reducing the number of appearance distances computed, and achieve larger speedups than approximate nearest neighbour algorithms based on trees [18] and on hashing [21]. For example, our algorithm finds the most similar pair of windows between two images while computing only 1% of all distances on average.

Link to publisher's page
Download in pdf format
  author = {Bogdan Alexe and Viviana Petrescu and Vittorio Ferrari},
  title = {Exploiting spatial overlap to efficiently compute appearance distances between image windows},
  booktitle = {NIPS 2011},
  year = {2011},
  month = {December},
  keywords = {}