Approximate Correspondences in High Dimensions
Pyramid intersection is an efficient method for computing an approximate partial matching between two sets of feature vectors. We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains ac...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2006
|
| Online Access: | http://hdl.handle.net/1721.1/33002 |
| _version_ | 1811084788897939456 |
|---|---|
| author | Grauman, Kristen Darrell, Trevor |
| author2 | Trevor Darrell |
| author_facet | Trevor Darrell Grauman, Kristen Darrell, Trevor |
| author_sort | Grauman, Kristen |
| collection | MIT |
| description | Pyramid intersection is an efficient method for computing an approximate partial matching between two sets of feature vectors. We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains accurate even for sets with high-dimensional feature vectors. The matching similarity is computed in linear time and forms a Mercer kernel. We also show how the matching itself (a correspondence field) may be extracted for a small increase in computational cost. Whereas previous matching approximation algorithms suffer from distortion factors that increase linearly with the feature dimension, we demonstrate thatour approach can maintain constant accuracy even as the feature dimension increases. When used as a kernel in a discriminative classifier, our approach achieves improved object recognition results over a state-of-the-art set kernel. |
| first_indexed | 2024-09-23T12:57:36Z |
| id | mit-1721.1/33002 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:57:36Z |
| publishDate | 2006 |
| record_format | dspace |
| spelling | mit-1721.1/330022019-04-12T08:26:35Z Approximate Correspondences in High Dimensions Grauman, Kristen Darrell, Trevor Trevor Darrell Vision Pyramid intersection is an efficient method for computing an approximate partial matching between two sets of feature vectors. We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains accurate even for sets with high-dimensional feature vectors. The matching similarity is computed in linear time and forms a Mercer kernel. We also show how the matching itself (a correspondence field) may be extracted for a small increase in computational cost. Whereas previous matching approximation algorithms suffer from distortion factors that increase linearly with the feature dimension, we demonstrate thatour approach can maintain constant accuracy even as the feature dimension increases. When used as a kernel in a discriminative classifier, our approach achieves improved object recognition results over a state-of-the-art set kernel. 2006-06-15T21:37:00Z 2006-06-15T21:37:00Z 2006-06-15 MIT-CSAIL-TR-2006-045 http://hdl.handle.net/1721.1/33002 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 10 p. 14140112 bytes 5515480 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Grauman, Kristen Darrell, Trevor Approximate Correspondences in High Dimensions |
| title | Approximate Correspondences in High Dimensions |
| title_full | Approximate Correspondences in High Dimensions |
| title_fullStr | Approximate Correspondences in High Dimensions |
| title_full_unstemmed | Approximate Correspondences in High Dimensions |
| title_short | Approximate Correspondences in High Dimensions |
| title_sort | approximate correspondences in high dimensions |
| url | http://hdl.handle.net/1721.1/33002 |
| work_keys_str_mv | AT graumankristen approximatecorrespondencesinhighdimensions AT darrelltrevor approximatecorrespondencesinhighdimensions |