Theses

Ph.D. thesis : Matching Shapes with a Reference Point

Oliver Klein

Field of Research

The topic of my research can be summarized as the analysis of reference points and their usage for shape matching under classes of transformations, like translations, rigid motions (translations and rotations) and similarity operations (rigid motions and scalings).

Let ${\cal K}$ be a set of shapes in $\mathbb{R}^d$ and $\delta$ be a distance measure on ${\cal K}$ . Then, a $\delta$ -reference point for ${\cal K}$ is defined as a Lipschitz-continuous mapping $r:{\cal K}\to \mathbb{R}^d$ which is equivariant under the considered class of transformations ${\cal T}$ .

The Lipschitz-continuity of can be expressed by

$\begin{displaymath} \forall A,B \in {\cal K}\;: \;\vert\vert r(A) - r(B)\vert\vert \le c \cdot \delta(A,B).\end{displaymath}$

In this context, the Lipschitz constant is called the quality of the reference point.

The first problem arising is to find reference points for different sets of shapes ${\cal K}$ and distance measures $\delta$ .

The second challenge is to find ways of using these referencepoints to construct approximation algorithms based on them. In particular, this means to find algorithms which find a transformation $\Phi^*$ , such that

$\displaystyle \delta(A,\Phi^*(B)) \le \alpha \cdot \min_{\Phi \in {\cal T}} \delta(A,\Phi(B)),$

(1)

where $\alpha \in \mathbb{R}^+$ is some constant independent from the concrete choice of $A, B \in {\cal K}$ . If inequality (1) is fulfilled, $\alpha$ is called theapproximation factor of the algorithm.

The research is mainly based on a paper by Alt, Aichholzer and Rote ([1]). In this paper the case of ${\cal K}= {\cal C}^2$ , the set of compact convex subsets of $\mathbb{R}^2$ , and $\delta$ as the Hausdorff distance $\delta_H$ is considered. This distance measureis defined as the smallest $\varepsilon$ such that the Euclidean distance from every point of to its nearest point of is at most $\varepsilon$ and vice versa.

Exact algorithms to determine the optimal transformation minimizing the Hausdorff distance under translations, rigid motions and similarity operations are known, but unfortunately the running time of these algorithms is not satisfactory for most applications. The authors of [1] develop approximation algorithms using reference points for matching under translations, rigid motions and similarity operations with approximation factors , and , respectively, where is the quality of any $\delta_H$ -reference point.

Furthermore, it is shown that the Steiner point (Steiner Curvature Centroid) is a $\delta_H$ -reference point for ${\cal C}^2$ of quality $\frac{4}{\pi}$ . It is also shown, that this quality is optimal, which means that there cannot exist any $\delta_H$ -reference point for shapes in $\mathbb{R}^2$ with a smaller Lipschitz constant. This is shown using strong functional-analytic tools and the axiom of choice. Therefore the proof is nonconstructive.

Summarizing the lower bound on the quality of a reference point of $\frac{4}{\pi}$ and the upper bound of the algorithm using reference points of quality with respect to translations, it seems reasonable that there are shapes which cannot be matched in a way that

$\displaystyle \forall i \not= j \;:\; \delta_H(A_i + t_i, A_j + t_j)\le (1 + \frac{4}{\pi} - \beta) \cdot \delta_H^{opt}(A_i,A_j),$

(2)

where $\delta_H^{opt}(A,B)$ is the optimal Hausdorff distance under translations, $\beta \in \mathbb{R}^+$ is any constant and $t_i \in \mathbb{R}^2$ are translation vectors. Observe that under these assumptions the vectors can be interpreted as the reference points of the given shapes. Unfortunately, those shapes , or even their existence, are not known so far. More knowledge about the nature of these shapes would lead to a better understanding of the approximation algorithms and, eventually, to even better algorithms.

Alt, Behrends and Blömer ([2]) follow a slightly different approach. They define reference points as an equivariant mapping $r:\mathcal{K} \to \mathbb{R}^d$ which leads, by making the two reference points coincide, to a constant factor approximation (1). We will call these mappings pseudo-reference points.

In October 2004, in the early beginning of my time in Utrecht, Remco Veltkamp and I had the idea of applying the reference point approach to weighted point sets with respect to the Earth Mover's Distance (EMD). The Earth Mover's Distance on weighted point sets is a useful distance measure for e.g. shape matching and colour-based image retrieval, see [4], [5] and [6] for more information. The EMD between two weighted point sets and can be interpreted as follows: Imagine the weighted points of as piles of earth and those of as holes. Basically, the EMD is the physical work needed to move the piles of earth of into the holes of , scaled by the minimum total weight of the two sets. Let now denote the EMD, when we are regarding the EMD defined on the ground set $\mathbb{R}^d$ with distance measure , $1 \le p \le \infty$ .

Until now we got a couple of interesting results on this. First, we have shown that there is an -reference point for weighted point sets with equal total weight, namely the centers of mass of these sets. The quality of this reference point is . Second, we have shown that there is also no reference point for weighted point sets with unequal total weights and, even worse, that there is no pseudo-reference point for those sets. We have further shown, that the center of mass is an optimal -reference point in the sence that there is no reference with a smaller Lipschitz constant. Furthermore we have developed approximation algorithms for translations, rigid motions and similarity operations with approximation factors , $2^{d-1}\sqrt{d}^{d-1}(c+1)$ and $2^d\sqrt{d}^{d-1}(c+1)$ , respectively. The running time of these algorithms are $O(T^{EMD_p}(n,m))$ for translations and $O(n^{d-1}m^{d-1} T^{EMD_p})$ for rigid motions and similarity operations, where and are the number of points of and , and $T^{EMD_p}(n,m)$ denotes the time needed to compute the between those two sets.

In the important case of the EMD defined on the Euclidean distance in the plane, the approximation factors reduce to , and and can be calculated in $O(T^{EMD_2}(n,m))$ for translations and $O(nmT^{EMD_2}(n,m))$ for rigid motions and similarity operations. An upper bound on $T^{EMD_p}(n,m)$ is $O(n^2m^2\log(\max\{n,m\}))$ using a strongly polynomial minimum cost flow algorithm by Orlin ([8]). In practice, of course, using the simplex algorithm to solve the flow problem or a $(1+\varepsilon)$ -approximation given by Cabello et al. ([3]) will be much faster.

Quite recently, Cabello et al. ([3]) have been working on similar problems. The advantage of our approach is that the results given can be applied to arbitrary dimension and distance measure on the ground set, even to more than the here mentioned -distances. Therefore the results are widely applicable.

The EMD, as defined above for weighted point sets, is an instance of a more general distance function defined on arbitrary subsets of $\mathbb{R}^d$ , the so-called Monge-Kantorovich-Distance, see [9] for more details. We have generalized the reference point method to work on subsets of $\mathbb{R}^d$ with respect to this distance measure.

Future Work

In the last semester I got some additional results on various reference points for different distance measures and classes of shapes. In the upcoming semester, I plan to elaborate on these new insights, especially on the case of the -distance and the relation between reference and pseudo-reference points.

Bibliography

H. Alt, O. Aichholzer, G. Rote.
Matching Shapes with a Reference Point, in Int. J. of Comp. Geom. and Appl., Volume 7, pages 349-363, August 1997
H. Alt, B. Behrends, J. Blömer
Approximate matching of polygonal shapes, in Proc. 7th Ann. Symp. on Comp. Geom., 1991, 186-193
S. Cabello, P. Giannopoulos, C. Knauer, G. Rote.
Matching Point Sets with respect to the Earth Mover's Distance.
In Proceedings of the European Symposium on Algorithms, 2005.
S. Cohen.
Finding Color and Shape Patterns in Images.
PhD thesis, Stanford University, Department of Compute Science, 1999.
P. Giannopoulos, R. Veltkamp.
A pseudo-metric for weighted point sets.
In Proc. 7th European Conf. Comp. Vision, LNCS 2352, pages 715-731, 2002.
K. Graumann, T. Darell.
Fast contour matching using approximate Earth Mover's Distance.
In Proc. of the IEEE Conf. Comp. Vision and Pattern Recognition, LNCS 2352, pages I: 220-227, 2004.
O. Klein, R. C. Veltkamp.
Approximation Algorithms for the Earth Mover's Distance Under Transformations Using Reference Points.
Technical Report UU-CS-2005-003, ftp.cs.uu.nl/pub/RUU/CS/techreps/CS-2005/2005-003.pdf, 2005.
J. B. Orlin.
A Faster Strongly Polynomial Minimum Cost Flow Algorithm.
In Operations Research, vol.41,no.2, pages 338-350, 1993.
S. Rachev.
The Monge-Kantorovich mass transference problem and its stochastic applications.
In Th. of Prob. and Appl., 29, pages 647-676, 1985.