Distance de correspondance

En mathématiques , la distance de correspondance est une métrique sur l'espace des fonctions de taille .

Le cœur de la définition de la distance de correspondance est l'observation selon laquelle les informations contenues dans une fonction de taille peuvent être stockées de manière combinatoire dans une série formelle de lignes et de points du plan, appelés respectivement lignes d'angle et points d'angle .

Étant données deux fonctions de taille et , soit (resp. ) l'ensemble de tous les points et lignes d'angle pour (resp. ) comptés avec leurs multiplicités, augmenté en ajoutant une infinité dénombrable de points de la diagonale . ${\displaystyle \ell _{1 <semantics> <mrow> <mstyle> <msub> <mi>ℓ</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \ell _{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle \ell _{2 <semantics> <mrow> <mstyle> <msub> <mi>ℓ</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \ell _{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle C_{1 <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle C_{2 <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle \ell _{1 <semantics> <mrow> <mstyle> <msub> <mi>ℓ</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \ell _{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle \ell _{2 <semantics> <mrow> <mstyle> <msub> <mi>ℓ</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \ell _{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle \{(x,y)\in \mathbb {R} ^{2}:x=y\ <semantics> <mrow> <mstyle> <mo>{</mo> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>et</mi> <mo>)</mo> <mo>∈</mo> <msup> <mrow> <mi>R</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msup> <mo>:</mo> <mi>x</mi> <mo>=</mo> <mi>et</mi> <mo>}</mo> </mstyle> </mrow> <annotation>{\displaystyle \{(x,y)\in \mathbb {R} ^{2}:x=y\}}</annotation> </semantics> </math><img src=$

La distance de correspondance entre et est donnée par où varie parmi toutes les bijections entre et et ${\displaystyle \ell _{1 <semantics> <mrow> <mstyle> <msub> <mi>ℓ</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \ell _{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle \ell _{2 <semantics> <mrow> <mstyle> <msub> <mi>ℓ</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \ell _{2}}</annotation> </semantics> </math><img src=$ ${\displaystyle d_{ ext{match}}(\ell _{1},\ell _{2})=\min _{\sigma }\max _{p\in C_{1}}\delta (p,\sigma (p)) <semantics> <mrow> <mstyle> <msub> <mi>d</mi> <mrow> <mtext>correspondre</mtext> </mrow> </msub> <mo>(</mo> <msub> <mi>ℓ</mi> <mrow> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>ℓ</mi> <mrow> <mn>2</mn> </mrow> </msub> <mo>)</mo> <mo>=</mo> <munder> <mo>min</mo> <mrow> <mi>σ</mi> </mrow> </munder> <munder> <mo>max</mo> <mrow> <mi>p</mi> <mo>∈</mo> <msub> <mi>C</mi> <mrow> <mn>1</mn> </mrow> </msub> </mrow> </munder> <mi>δ</mi> <mo>(</mo> <mi>p</mi> <mo>,</mo> <mi>σ</mi> <mo>(</mo> <mi>p</mi> <mo>)</mo> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle d_{ ext{match}}(\ell _{1},\ell _{2})=\min _{\sigma }\max _{p\in C_{1}}\delta (p,\sigma (p))}</annotation> </semantics> </math><img src=$ ${\displaystyle \sigma <semantics> <mrow> <mstyle> <mi>σ</mi> </mstyle> </mrow> <annotation>{\displaystyle \sigma }</annotation> </semantics> </math><img src=$ ${\displaystyle C_{1 <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{1}}</annotation> </semantics> </math><img src=$ ${\displaystyle C_{2 <semantics> <mrow> <mstyle> <msub> <mi>C</mi> <mrow> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle C_{2}}</annotation> </semantics> </math><img src=$

{\displaystyle \delta \left((x,y),(x',y') ight)=\min \left\{\max\{|x-x'|,|y-y'|\},\max \left\{{\frac {y-x}{2}},{\frac {y'-x'}{2}} ight\} ight\}. <semantics> <mrow> <mstyle> <mi>δ</mi> <mrow> <mo>(</mo> <mrow> <mo>(</mo> <mi>x</mi> <mo>,</mo> <mi>et</mi> <mo>)</mo> <mo>,</mo> <mo>(</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> <mo>,</mo> <msup> <mi>et</mi> <mo>′</mo> </msup> <mo>)</mo> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>min</mo> <mrow> <mo>{</mo> <mrow> <mo>max</mo> <mo>{</mo> <mrow> <mo>|</mo> </mrow> <mi>x</mi> <mo>−</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> <mrow> <mo>|</mo> </mrow> <mo>,</mo> <mrow> <mo>|</mo> </mrow> <mi>et</mi> <mo>−</mo> <msup> <mi>et</mi> <mo>′</mo> </msup> <mrow> <mo>|</mo> </mrow> <mo>}</mo> <mo>,</mo> <mo>max</mo> <mrow> <mo>{</mo> <mrow> <mrow> <mfrac> <mrow> <mi>et</mi> <mo>−</mo> <mi>x</mi> </mrow> <mn>2</mn> </mfrac> </mrow> <mo>,</mo> <mrow> <mfrac> <mrow> <msup> <mi>et</mi> <mo>′</mo> </msup> <mo>−</mo> <msup> <mi>x</mi> <mo>′</mo> </msup> </mrow> <mn>2</mn> </mfrac> </mrow> </mrow> <mo>}</mo> </mrow> </mrow> <mo>}</mo> </mrow> <mo>.</mo> </mstyle> </mrow> <annotation>{\displaystyle \delta \gauche((x,y),(x',y')\droite)=\min \gauche\{\max\{|xx'|,|yy'|\},\max \gauche\{{\frac {yx}{2}},{\frac {y'-x'}{2}}\droite\}\droite\}.}</annotation> </semantics> </math></span><img src=

En gros, la distance de correspondance entre deux fonctions de taille est le minimum, sur toutes les correspondances entre les points d'angle des deux fonctions de taille, du maximum des α-distances entre deux points d'angle correspondants. Étant donné que deux fonctions de taille peuvent avoir un nombre différent de points d'angle, ceux-ci peuvent également correspondre à des points de la diagonale . De plus, la définition de implique que la correspondance de deux points de la diagonale n'a aucun coût. ${\displaystyle d_{ ext{match <semantics> <mrow> <mstyle> <msub> <mi>d</mi> <mrow> <mtext>correspondre</mtext> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle d_{ ext{correspondance}}}</annotation> </semantics> </math><img src=$ ${\displaystyle L_{\infty <semantics> <mrow> <mstyle> <msub> <mi>L</mi> <mrow> <mi>∞</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle L_{\infty }}</annotation> </semantics> </math><img src=$ ${\displaystyle \Delta <semantics> <mrow> <mstyle> <mi>Δ</mi> </mstyle> </mrow> <annotation>{\displaystyle \Delta }</annotation> </semantics> </math><img src=$ ${\displaystyle \delta <semantics> <mrow> <mstyle> <mi>δ</mi> </mstyle> </mrow> <annotation>{\displaystyle \delta }</annotation> </semantics> </math><img src=$