Fast Contour Matching Using Approximate Earth Mover's Distance
Weighted graph matching is a good way to align a pair of shapes represented by a set of descriptive local features; the set of correspondences produced by the minimum cost of matching features from one shape to the features of the other often reveals how similar the two shapes are. However, due to t...
| Main Authors: | , |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/6733 |
| _version_ | 1826200908219809792 |
|---|---|
| author | Grauman, Kristen Darrell, Trevor |
| author_facet | Grauman, Kristen Darrell, Trevor |
| author_sort | Grauman, Kristen |
| collection | MIT |
| description | Weighted graph matching is a good way to align a pair of shapes represented by a set of descriptive local features; the set of correspondences produced by the minimum cost of matching features from one shape to the features of the other often reveals how similar the two shapes are. However, due to the complexity of computing the exact minimum cost matching, previous algorithms could only run efficiently when using a limited number of features per shape, and could not scale to perform retrievals from large databases. We present a contour matching algorithm that quickly computes the minimum weight matching between sets of descriptive local features using a recently introduced low-distortion embedding of the Earth Mover's Distance (EMD) into a normed space. Given a novel embedded contour, the nearest neighbors in a database of embedded contours are retrieved in sublinear time via approximate nearest neighbors search. We demonstrate our shape matching method on databases of 10,000 images of human figures and 60,000 images of handwritten digits. |
| first_indexed | 2024-09-23T11:43:35Z |
| id | mit-1721.1/6733 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:43:35Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/67332019-04-12T08:32:13Z Fast Contour Matching Using Approximate Earth Mover's Distance Grauman, Kristen Darrell, Trevor AI contour matching shape matching EMD image retrieval Weighted graph matching is a good way to align a pair of shapes represented by a set of descriptive local features; the set of correspondences produced by the minimum cost of matching features from one shape to the features of the other often reveals how similar the two shapes are. However, due to the complexity of computing the exact minimum cost matching, previous algorithms could only run efficiently when using a limited number of features per shape, and could not scale to perform retrievals from large databases. We present a contour matching algorithm that quickly computes the minimum weight matching between sets of descriptive local features using a recently introduced low-distortion embedding of the Earth Mover's Distance (EMD) into a normed space. Given a novel embedded contour, the nearest neighbors in a database of embedded contours are retrieved in sublinear time via approximate nearest neighbors search. We demonstrate our shape matching method on databases of 10,000 images of human figures and 60,000 images of handwritten digits. 2004-10-08T20:43:06Z 2004-10-08T20:43:06Z 2003-12-05 AIM-2003-026 http://hdl.handle.net/1721.1/6733 en_US AIM-2003-026 16 p. 7561935 bytes 7530316 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | AI contour matching shape matching EMD image retrieval Grauman, Kristen Darrell, Trevor Fast Contour Matching Using Approximate Earth Mover's Distance |
| title | Fast Contour Matching Using Approximate Earth Mover's Distance |
| title_full | Fast Contour Matching Using Approximate Earth Mover's Distance |
| title_fullStr | Fast Contour Matching Using Approximate Earth Mover's Distance |
| title_full_unstemmed | Fast Contour Matching Using Approximate Earth Mover's Distance |
| title_short | Fast Contour Matching Using Approximate Earth Mover's Distance |
| title_sort | fast contour matching using approximate earth mover s distance |
| topic | AI contour matching shape matching EMD image retrieval |
| url | http://hdl.handle.net/1721.1/6733 |
| work_keys_str_mv | AT graumankristen fastcontourmatchingusingapproximateearthmoversdistance AT darrelltrevor fastcontourmatchingusingapproximateearthmoversdistance |