Using matching distance in Size Theory: a surveyMichele d’AmicoARCES, Universit`a di Bolognavia Toffano 2/2, I-40135 Bologna, [email protected] Frosini∗Dipartimento di Matematica, Universit`a di BolognaP.zza di Porta San Donato 5, I-40127 Bologna, Italia, and [email protected] LandiDISMI, Universit`a di Modena e Reggio EmiliaI-42100 Reggio Emilia, Italia, and [email protected] this survey we illustrate how the matching distance between reducedsize functions can be applied for shape comparison.We assume that each shape can be thought of as a compact connectedmanifold with a real continuous function defined on it, that is a pair(M, ϕ : M → R), called size pair. In some sense, the function ϕ fo-cuses on the properties and the invariance of the problem at hand. Inthis context, matching two size pairs (M, ϕ) and (N , ψ) means lookingfor a homeomorphism between M and N that minimizes the differenceof values taken by ϕ and ψ on the two manifolds. Measuring the dissimi-larity between two shapes amounts to the difficult task of computing thevalue δ = inffmaxP ∈M|ϕ(P ) − ψ(f(P ))| where f varies among all thehomeomorphisms from M to N .From another point of view, shapes can be described by reduced sizefunctions associated with size pairs. The matching distance between re-duced size functions allows for a robust to perturbations comparison ofshapes.The link between reduced size functions and the dissimilarity measureδ is established by a theorem stating that the matching distance providesan easily computable lower bound for δ.Throughout this paper we illustrate this approach to shape comparisonby means of examples and experiments.∗Corresponding authorKeywords: Shape comparison, shape representation, reduced size function,natural pseudo-distanceA.M.S. Classification: Primary: 68T10; Secondary: 58C05, 49Q101 IntroductionShape matching plays an important role in a number of Computer Vision prob-lems, such as, e.g., shape retrieval, shape recognition and shape classification.Various techniques have been proposed to deal with the shape matching problem(see, e.g., (Veltkamp and Hagedoorn 2001)). A possible approach to this subjectis to compare shapes by solving some minimization problem (see, e.g., (Hancockand Pelillo 1999)). This research line includes the natural pseudo-distance.We assume that shapes can be described by pairs (M, ϕ), where M is acompact connected manifold, and ϕ : M → R is a continuous function focusingon the properties and the invariance of the matching problem at hand. Inour setting, comparing two shapes represented by (M, ϕ) and (N , ψ), withM and N homeomorphic, means considering all the possible homeomorphismsf : M → N and computing the number inffmaxP ∈M|ϕ(P ) − ψ(f(P ))|. Thelatter is a measure of the dissimilarity between the shapes represented by (M, ϕ)and (N , ψ), called natural pseudo-distance (see, e.g. (Frosini and Landi 1999),(Donatini and Frosini 2004b)).In order to compute this dissimilarity measure, one must deal with an opti-mization problem and look for the transformation that minimizes the differencebetween two pairs (M, ϕ), (N , ψ) (in case it exists). This optimization problemis intrinsically difficult. In order to obviate this difficulty we rather estimate thedissimilarity by looking for a lower bound for the natural pseudo-distance.A result recently proved in (d’Amico et al. 2003) states that a lower boundfor the natural pseudo-distance is provided by a suitable matching distancebetween reduced size functions. These are (easily computable) functions, definedto describe shapes: the reduced size function ℓ∗(M,ϕ): {(x, y) ∈ R2: x < y} → Nis defined by setting ℓ∗(M,ϕ)(x, y) equal to the number of connected componentsof the lower level set {P ∈ M : ϕ(P ) ≤ y} which contain at least a point of{P ∈ M : ϕ(P ) ≤ x}.A matching distance dmatchbetween reduced size functions can be easilyintroduced. When M and N are homeomorphic, the following inequality holds:inff:M→NmaxP ∈M|ϕ(P ) − ψ(f(P ))| ≥ dmatch(ℓ∗(M,ϕ), ℓ∗(N ,ψ)),where f varies among all possible homeomorphisms. This yields an easily com-putable lower bound for the dissimilarity measure problem. This and otherrelated results are examined in detail in (d’Amico et al. 2005).This paper is devoted to illustrate all the previous concepts and relatedproperties, and to point out the usefulness of this approach to shape comparison.In Section 2 we shall recall the definitions of natural pseudo-distance betweensize pairs and of reduced size function. In Section 3 the definition of match-ing distance between reduced size functions will be given together with sometheoretical results, and exemplified. Section 4 and Section 5 will be devoted toexperiments and conclusions, respectively.2 Natural pseudo-distance and reduced size func-tionsWe begin with the definition of a pseudo-distance that allows us to measure theextent to which two shapes are similar to each other.We stress the fact that when we think to the concept of shape, we have inmind a compact connected n-manifold M with a continuous real-valued func-tion ϕ defined on it (no assumption is made about the regularity of M). Themanifold represents the object whose shape we are interested in (e.g., a silhou-ette), whereas the continuous function is chosen arbitrarily, usually accordingto the properties and the invariance of interest for the problem at hand (see,e.g., (Kaczynski et al. 2004), (Verri and Uras 1994), (Landi and Frosini 2002)).The pair (M, ϕ) is called an n-dimensional size pair.Hereafter, M and N will denote compact connected n-manifolds, and ϕ :M → R, ψ : N → R will be continuous functions, called measuring functions.We point out that there is no limitation on the dimension of M. Therefore,although so far most of the experiments in this field have been carried out for2-D objects, the theory holds in general for any dimension.The assumption on the connectedness of M can easily be weakened to anyfinite number of connected components, without much affecting the followingresults. More serious problems would derive from considering an infinite numberof connected components.Definition 2.1 Let (M, ϕ), (N , ψ) be two size pairs and let H (M, N ) be theset of all the homeomorphisms from M onto N . If H (M, N ) 6= ∅, let usconsider the function Θ that takes each homeomorphism f ∈ H (M, N ) to thereal number Θ(f )