Exploiting spatial overlap to efficiently compute appearance distances between image windows.

Bogdan Alexe, Viviana Petrescu, Vittorio Ferrari

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 24
Number of pages9
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Exploiting spatial overlap to efficiently compute appearance distances between image windows.'. Together they form a unique fingerprint.

Cite this