Matching distance

In mathematics, the matching distanceMichele d'Amico, Patrizio Frosini, Claudia Landi, Using matching distance in Size Theory: a survey, International Journal of Imaging Systems and Technology, 16(5):154–161, 2006.Michele d'Amico, Patrizio Frosini, Claudia Landi, Natural pseudo-distance and optimal matching between reduced size functions, Acta Applicandae Mathematicae, 109(2):527-554, 2010. is a metric on the space of size functions.

Image:DistMatchWiki1.png

The core of the definition of matching distance is the observation that the

information contained in a size function can be combinatorially stored in a formal series of lines and points of the plane, called respectively cornerlines and cornerpoints.

Given two size functions $\backslash ell\_1$ and $\backslash ell\_2$, let $C\_1$ (resp. $C\_2$) be the multiset of

all cornerpoints and cornerlines for $\backslash ell\_1$ (resp. $\backslash ell\_2$) counted with their

multiplicities, augmented by adding a countable infinity of points of the

diagonal $\backslash \{(x,y)\backslash in\; \backslash R^2:\; x=y\backslash \}$.

The matching distance between $\backslash ell\_1$ and $\backslash ell\_2$ is given by

$d\_\backslash text\{match\}(\backslash ell\_1,\; \backslash ell\_2)=\backslash min\_\backslash sigma\backslash max\_\{p\backslash in\; C\_1\}\backslash delta\; (p,\backslash sigma(p))$

where $\backslash sigma$ varies among all the bijections between $C\_1$ and $C\_2$ and

: $\backslash delta\backslash left((x,y),(x\text{'},y\text{'})\backslash right)=\backslash min\backslash left\backslash \{\backslash max\; \backslash \{|x-x\text{'}|,|y-y\text{'}|\backslash \},\; \backslash max\backslash left\backslash \{\backslash frac\{y-x\}\{2\},\backslash frac\{y\text{'}-x\text{'}\}\{2\}\backslash right\backslash \}\backslash right\backslash \}.$

Roughly speaking, the matching distance $d\_\backslash text\{match\}$

between two size functions is the minimum, over all the matchings

between the cornerpoints of the two size functions, of the maximum

of the $L\_\backslash infty$-distances between two matched cornerpoints. Since

two size functions can have a different number of cornerpoints,

these can be also matched to points of the diagonal $\backslash Delta$. Moreover, the definition of $\backslash delta$ implies that matching two points of the diagonal has no cost.