Résumé

The Tangent Earth Mover's Distance

Métriques

74
4
2.95 Mo
 application/pdf
bitcache://68f0cb9d9562edae6092a4a97fb75cc3a95436bb

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/5090</identifier><creators><creator><creatorName>Ofir Pele</creatorName></creator><creator><creatorName>Ben Taskar</creatorName></creator></creators><titles>
            <title>The Tangent Earth Mover's Distance</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 8 Oct 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Fri 20 Jul 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">68f0cb9d9562edae6092a4a97fb75cc3a95436bb</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25107</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

The Tangent Earth Mover’s Distance Ofir Pele Ben Taskar The Tangent Earth Mover’s Distance Ofir Pele Ben Taskar University of Washington The Tangent Earth Mover’s Distance Ofir Pele Ben Taskar Ariel University University of Washington Motivation • Computer Vision / Machine Learning problems with distances: – Image retrieval. – Descriptors matching. – K-nearest neighbor classification. – Support vector machines. – Clustering. – … • Motivation. • The Earth Mover’s Distance. • The Tangent Distance. • The Tangent Earth Mover’s Distance. • Experimental Results. • Future Work. Outline • Motivation. • The Earth Mover’s Distance. • The Tangent Distance. • The Tangent Earth Mover’s Distance. • Experimental Results. • Future Work. Outline The Earth Mover’s Distance ≠ The Earth Mover’s Distance = The Earth Mover’s Distance for Probability Distributions The Earth Mover’s Distance for Probability Distributions The Earth Mover’s Distance for Probability Distributions The Earth Mover’s Distance for Probability Distributions The Earth Mover’s Distance - Rubner, Tomasi, Guibas IJCV 2000 • Pele and Werman 08 – , a new EMD definition. The Earth Mover’s Distance The Earth Mover’s Distance Differences Between and EMD • EMD - scale invariant, - scale variant. Differences Between and EMD • EMD - scale invariant, - scale variant. Differences Between and EMD • EMD – partial match, not necessarily. Differences Between and EMD • EMD – partial match, not necessarily. Differences Between and EMD • If ground distance is a metric: • EMD shortcoming: – Does not differentiate between global transformation to local non-structured ones. The Earth Mover’s Distance • EMD shortcoming: – Does not differentiate between global transformation to local non-structured ones. • Our solution: – The Tangent Earth Mover’s Distance. The Earth Mover’s Distance • Motivation. • The Earth Mover’s Distance. • The Tangent Distance. • The Tangent Earth Mover’s Distance. • Experimental Results. • Future Work. Outline The Tangent Distance – Simard et al. 98 • What we want: a distance that is invariant to small global transformations: • What we want: a distance that is invariant to small global transformations. • Main idea: approximate transforms of a pattern by its tangent plane at the pattern: The Tangent Distance – Simard et al. 98 The Tangent Distance – Simard et al. 98 The Tangent Distance – Simard et al. 98 The Tangent Distance – Simard et al. 98 • Tangent distance shortcoming: – Not robust to small local deformations. The Tangent Distance – Simard et al. 98 • Tangent distance shortcoming: – Not robust to small local deformations. The Tangent Distance – Simard et al. 98 • Tangent distance shortcoming: – Not robust to small local deformations. • Our solution: – The Tangent Earth Mover’s Distance. • Motivation. • The Earth Mover’s Distance. • The Tangent Distance. • The Tangent Earth Mover’s Distance. • Experimental Results. • Future Work. Outline The Tangent Earth Mover’s Distance The Tangent part: small global movement for free. The Tangent Earth Mover’s Distance The Tangent part: small global movement for free. For example, to the right. The Tangent Earth Mover’s Distance The Tangent part: small global movement for free. For example, to the right. The EMD part: arbitrary movements that cost. The Tangent Earth Mover’s Distance The Tangent part: small global movement for free. For example, to the right. The EMD part: arbitrary movements that cost. $ The Tangent Earth Mover’s Distance The Tangent Earth Mover’s Distance The Tangent Earth Mover’s Distance The Tangent Earth Mover’s Distance The Tangent Earth Mover’s Distance The Tangent Earth Mover’s Distance – an Example of a Tangent Vector Features The Tangent Earth Mover’s Distance – an Example of a Tangent Vector Features Histogram 0 0 0 0 01 1 2 The Tangent Earth Mover’s Distance – an Example of a Tangent Vector Features Histogram 0 0 0 0 01 1 2 Tangent Vector 0 0 0 1 11 -1 -2 The Tangent Earth Mover’s Distance – an Example of a Tangent Vector Features Histogram 0 0 0 0 01 1 2 Transformed Histogram 0 0 0 1 12 0 0 Tangent Vector 0 0 0 1 11 -1 -2 The Tangent Earth Mover’s Distance • Previous works about the efficient computation of the EMD can be used to accelerate also the TEMD computation: The Tangent Earth Mover’s Distance • Previous works about the efficient computation of the EMD can be used to accelerate also the TEMD computation: – Ling and Okada 2007: Manhattan grids. The Tangent Earth Mover’s Distance • Previous works about the efficient computation of the EMD can be used to accelerate also the TEMD computation: – Ling and Okada 2007: Manhattan grids. – Pele and Werman 2009: Thresholded ground distances. The Tangent Earth Mover’s Distance • Previous works about the efficient computation of the EMD can be used to accelerate also the TEMD computation: – Ling and Okada 2007: Manhattan grids. – Pele and Werman 2009: Thresholded ground distances. – Combinations. • Motivation. • The Earth Mover’s Distance. • The Tangent Distance. • The Tangent Earth Mover’s Distance. • Experimental Results. • Future Work. Outline Experiments • 10 classes: – People in Africa – Beaches – Outdoor Buildings – Buses – Dinosaurs – Elephants – Flowers – Horses – Mountains – Food Experiments • 5 queries from each class. • Computed the distance of each image to the query and its reflection and chose the minimum. Experiments • 5 queries from each class. Experiments • Image representations: SIFT 32x48 L*a*b* Image Experiments - SIFT Why Thresholded ? The Earth Mover’s Distance • EMD shortcomings: – Poor performance with outliers. – Long computation time. The Earth Mover’s Distance • EMD shortcomings: – Poor performance with outliers. – Long computation time. • Our solutions: – Thresholded distances between bins. – Efficient algorithms. Robust Distances Robust Distances • Very high distances outliers same difference. Robust Distances • Very high distances outliers same difference. Robust Distances - Exponent • Usually a negative exponent is used: Robust Distances - Exponent • Usually a negative exponent is used: Robust Distances - Exponent • Exponent is used because it is (Ruzon and Tomasi 01): robust, smooth, monotonic, and a metric Robust Distances - Exponent • Exponent is used because it is (Ruzon and Tomasi 01): robust, smooth, monotonic, and a metric Input is always discrete anyway … Robust Distances - Thresholded Thresholded Distances • Color distance should be thresholded (robust). 0 50 100 150 distancefromblue Thresholded Distances 0 5 10 distancefromblue Exponent changes small distances Another Reason for Thresholded Distances FastEMD - Pele and Werman ICCV 2009 FastEMD - Pele and Werman ICCV 2009 • Any thresholded distance number of edges with cost different from the threshold The Flow Network Transformation Original Network The Flow Network Transformation Original Network Simplified Network The Flow Network Transformation Original Network Simplified Network The Flow Network Transformation Flowing between exact corresponding bins (Monge sequence for metrics) The Flow Network Transformation Removing Empty Bins and their edges The Flow Network Transformation We actually finished here…. Many Successful Applications of FastEMD Superpixel comparison Image retargetingOriginal image Object class Semantic Scene Surface Layout Image segmentation Image retargeting Results- Retrieval Curve using SIFT Averagenumberofcorrectimagesretrieved Number of nearest neighbors images retrieved (our ECCV 08) QF A2 c=2,D2 (our ICCV 09) c=1,D2 (our ICCV 09) c=2,D2 (our 13) c=1,D2 (our 13) c=1,2D1(our 13) (Simard et al. 98) L1 EMD-L1 (Ling & Okada 07) L2 Results- Normalized AUC using SIFT c=2,D2 (our ICCV 09) c=1,D2 (our ICCV 09) c=2,D2 (our 13) c=1,D2 (our 13) c=1, 2D1 (our 13) (Simard et al. 98) L1 EMD-L1 (Ling & Okada 07) QF A2 L2 (our ECCV 08) Experiments - Color Images Results- Retrieval Curve using Color Images Averagenumberofcorrectimagesretrieved Number of nearest neighbors images retrieved QF A20 D20 (our ICCV 09) D20 (our 13) Results- Normalized AUC using Color Images D20 (our ICCV 09) D20 (our 13) QF A20 • Faster Algorithms for the Tangent Earth Mover’s Distance: Near Future Work • Faster Algorithms for the Tangent Earth Mover’s Distance: – Greedy algorithms for quick hot-start. Near Future Work • Faster Algorithms for the Tangent Earth Mover’s Distance: – Greedy algorithms for quick hot-start. – Decomposition idea: break the problem into easy to solve “pieces” and then enforce consistency. Near Future Work • Faster Algorithms for the Tangent Earth Mover’s Distance: – Greedy algorithms for quick hot-start. – Decomposition idea: break the problem into easy to solve “pieces” and then enforce consistency. • Efficient and accurate segmentation of images using the Tangent Earth Mover’s Distance. Near Future Work • “Big Data” – need for complex non-linear models. Far Future Work • “Big Data” – need for complex non-linear models. • Complex distances are perfect fit for this. Far Future Work • “Big Data” – need for complex non-linear models. • Complex distances are perfect fit for this. • New research about how to learn efficiently with such distances (cascades, nearest neighbors, …). Far Future Work Papers & Code are / will be at my website: Or “Ofir Pele” http://www.seas.upenn.edu/~ofirpele/