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 matching between two shapes' features often reveals how similar the 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 with locality-sensitive hashing (LSH). We demonstrate our shape matching method on a database of 136,500 images of human figures. Our method achieves a speedup of four orders of magnitude over the exact method, at the cost of only a 4% reduction in accuracy.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Fast contour matching using approximate earth mover's distance


    Beteiligte:
    Grauman, K. (Autor:in) / Darrell, T. (Autor:in)


    Erscheinungsdatum :

    01.01.2004


    Format / Umfang :

    2031176 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Fast Contour Matching Using Approximate Earth Mover's Distance

    Grauman, K. / Darrell, T. / IEEE Computer Society | British Library Conference Proceedings | 2004


    Tensor-SIFT Based Earth Mover’s Distance for Contour Tracking

    Li, P. | British Library Online Contents | 2013


    TEXT CATEGORIZATION USING EARTH MOVER'S DISTANCE AS SIMILARITY MEASURE

    Yanagimoto, H. / Omatu, S. | British Library Conference Proceedings | 2007



    EMD (earth mover's distance) algorithm based individual trip mobile phone switching sequence road matching method

    YANG FEI / YAO ZHENXING / ZENG DAKUN et al. | Europäisches Patentamt | 2015

    Freier Zugriff