Design and Analysis of Application Oriented Geometric Algorithms
Deutsche Forschungsgemeinschaft (DFG)
In collaboration with
A project within the DFG Priority Program 1307 Algorithm Engineering.
The goal of this project is to close a gap between theoretically designed and studied algorithms and the methods that are widely used in practice, especially heuristics. We consider primarily but not exclusively the problem of the geometric shape matching.
There are many algorithms and heuristic methods that work well and are widely used in practice but lack theoretical analysis. We analyze some of such heuristics with respect to the following questions:
- What is computed by the method? The quality of the computed results is often not known or even not clearly defined.
- What is the running time of the method? In many cases there is a certain trade-off between the running time and the quality of results.
It might be necessary to constraint the inputs of the methods and to characterize the cases that occur in practice in order to be able to perform the analysis.
Besides these theoretical studies we also plan to do prototype implementations of the designed algorithms to verify their practicability. The research focuses on the following problems:
Patterns and shapes
Probabilistic shape matching
We designed and analyzed a generic probabilistic approach for the shape matching problem. The studied approach is based on an intuitive definition of the shape matching task: Given two shapes A and B find that transformation within the class of allowable transformations which maps B to A in a best possible way. A mapping is considered to be good if large parts of the two shapes coincide within some tolerance distance δ.
The main idea of the probabilistic algorithm is to take random samples of points from both shapes and give a "vote" for that transformation matching one sample with the other. If that experiment is repeated frequently, we obtain by the votes a certain probability distribution in the space of transformations. Maxima of this distribution indicate which transformations give the best match between the two figures. The matching step of the algorithm is, therefore, a voting scheme.
Related methods in the image processing community are the generalized Hough transform, the generalized Radon transform, and the RANSAC algorithm. In contrast to those methods we do not consider a discrete set of features that describe shapes, but work with continuous objects, e.g., curves, regions, and surfaces in 3D. Our method is independent of the choice of the parameterization and the discretization grid in the transformation space.
Our important contribution is the theoretical analysis since it leads to a better understanding of this kind of heuristic techniques. We studied this probabilistic method for several types of shapes in combination with different classes of transformations. We developed and analyzed exactly probabilistic shape matching for two dimensional shapes modeled as sets of line segments and various classes of transformations, such as translations, rigid motions, similarity maps, and affine transformations in general. Prototype implementations experimentally confirmed our results. We showed that the technique can be extended to matching regions instead of curves and to matching higher dimensional volumes.
We started to create a software package for shape matching that has a graphic user interface and can be made publicly available.
The ongoing Ph.D. thesis of Claudia Dieckmann investigates algorithms for the detection of approximate symmetries in point sets. Here, probabilistic matching can be applied successfully, as implementations show, and also under certain assumptions on the input other efficient algorithms can be found.
Application oriented methods
In the Ph.D. thesis of Fabian Stehn, geometric hybrid registration problems are studied. Registration problems are closely related to geometric matching problems. The term geometric registration problem describes the task of mapping points from one space (pattern space) to their corresponding points in a deformed copy of that space called model space.
This research is motivated by a real world application: navigated surgery. Here, the goal is to register an operation theatre space (pattern space) to the internal coordinate system (model space) of a medical navigation system. The purpose of a medical navigation system is to support surgeons by visualizing the used surgical instruments at their correct position in a 3D-model of a patient. The models are generated beforehand based on CT or MRT scans.
Hybrid registration is a novel strategy to compute solutions for this alignment problem. Geometric hybrid registrations reduce the spatial synchronization problem to a series of (at least two) geometric matching problems that are solved interdependently. Usually, a computationally involved point-to-surface matching is combined with a comparably simpler but underdefined point-to-point matching. The point-to-surface matching is computed for a sufficiently large and suitably distributed set of points (called surface points) measured in the pattern space to a geometric surface in the model space. For the point-to-point matching, a small set of (one to three) characteristic points are measured in the pattern space and are defined in the model space. In the context of the intended application, these points are called anatomic landmarks - anatomically exposed spots within the field of interest.
In the Ph.D. thesis of Sven Scholz the ideas of probabilistic shape matching are applied to a real world question in collaboration with AKTOR KNOWLEDGE TECHNOLOGY NV in Antwerp, Belgium: automatically determining the similarity between trademarks of companies. In particular, after some preprocessing shapes are extracted from the images of trademarks and compared using probabilistic shape matching enhanced with further heuristics. In order to demonstrate the usability of this approach in practice, all these algorithms have been implemented and tested on various sets of figurative images and real-world trademark images. The results of the experiments carried out show a large conformity with human perception of similarity and the operating figures obtained are clearly better than the ones of other existing systems.
Packing and stacking geometric objects
One topic connected with shape matching, which we plan to address, are efficient algorithms for packing and stacking geometric objects. In the plane geometric objects would be, e.g., simple polygons which can be transformed by translations or rigid motions. The objective is to find transformations placing the objects such that some cost function is minimized, for example the area or the perimeter of the convex hull of the union of all transformed figures. The objects may either be overlapping (stacking) or overlapping is not allowed (packing).
Optimal packing of an arbitrary number of objects, even axes-parallel rectangles under translations, can easily shown to be NP-hard. This is an important practical problem in textile or steel industry, namely, cutting out given parts from a large cloth or sheet metal and minimizing the waste. Therefore, numerous heuristic approaches exist from the optimization community. Rigorously analyzed methods with a guaranteed performance have been found so far in the computational geometry community only in special cases.
Realistic input models
Geometric shape matching
For many other distance measure (e.g., the Hausdorff-distance or the area of the symmetric difference) the situation is similar. For the Earth-Mover's-distance (a distance measure for weighted point sets which is very popular in multimedia-retrieval no exact algorithmic solutions are known for the shape matching problem (even for translations in the plane). Again one is forced to turn to approximation methods - unfortunately, even these turn out to be fairly complicated and are not useful for real applications.
The goal is to investigate if and how restrictions to the structure of the input data can be exploited to develop more efficient and conceptually simpler algorithms for this kind of problems.
Geometric search structures
Many search structures for geometric objects are based on the following general (heuristic) approach: For each object a (high-dimensional) feature vector is determined and the similarity of two objects is simply determined by the distance (in some Lp-metric) of the corresponding feature vectors. The vantage-point methods suggest to use the distance (w.r.t. a suitable geometric distance measure δ, like, e.g., the Hausdorff distance) to a small set of fixed so-called vantage-objects from the data set as a feature vector. These methods seem to work very well in practice, but they have not been fully analyzed from a theoretical point of view.
Worst-case time bounds are known only in special cases (like when δ is "close" to the Euclidean metric) and in existing applications the vantage-objects are chosen according to some ad-hoc heuristic.
We aim to analyze this approach in a broader context by first identifying and formalizing the appropriate theoretical questions and concepts, like, e.g., "What is the relation between δ and the Lp-distance of the feature vectors?", "What is a good set of vantage-objects?", or "What is the algorithmic complexity of finding such a good set (approximately)?". In a second step we will try to answer these questions for selected scenarios (geometric objects and distance measures δ) again with the emphasis on appropriate assumptions about realistic input models.
Principal component analysis (PCA)is one of the oldest and best known techniques of multivariate analysis. Numerous applications of PCA can be found in data compression, visualization, image processing, pattern and image recognition, time series prediction, detecting symmetry, or dimension detection. Most of the applications of PCA are non-geometric in their nature. However, there are also few purely geometric applications like estimation of the undirected normals of the point sets or computing PCA bounding boxes (bounding boxes determined by the principal components of the point set).
We presented closed-form solutions for efficiently updating the principal components of a set of n points, when m points are added or deleted from the point set. For both operations performed on a discrete point set in Rd, we can compute the new principal components in O(m) time for fixed d. This is a significant improvement over the commonly used approach of recomputing the principal components from scratch, which takes O(n + m)time. An important application of the above result is the dynamical computation of bounding boxes based on principal component analysis. We have implemented and evaluated several algorithms for computing dynamically PCA bounding boxes in R3. In addition, we present closed-form solutions for computing dynamically principal components of continuous point sets in R2 and R3. In both cases, discrete and continuous, to compute the new principal components, no additional data structures or storage are needed.
Computing the Discrete Fréchet Distance with Imprecise Input
In Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), Lecture Notes in Computer Science, Volume 6507, Pages 422–433, Editor(s) Cheong, Otfried and Chwa, Kyung-Yong and Park, Kunsoo, Springer-Verlag, Berlin/Heidelberg, Germany, 2010.
Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, Antoine Vigneron
Probabilistic Matching of Planar Regions
Computational Geometry, Theory and Applications (CGTA), Volume 43 (2), Pages 99–114, 2010.
Helmut Alt, Ludmila Scharf, Daria Schymura
Special Issue on the 24th European Workshop on Computational Geometry (EuroCG'08)
view at ScienceDirect
Matching point sets with respect to the Earth Mover's Distance
Computational Geometry, Theory and Applications, Volume 39, Pages 118–133, 2008.
Sergio Cabello, Panos Giannopoulos, Christian Knauer, Günter Rote
Measuring the Similarity of Geometric Graphs
In Proc. 8th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science, Volume 5526, Pages 101–112, Springer, Dortmund, Germany, 2009.
Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura, Fabian Stehn
Closed-Form Solutions for Continuous PCA and Bounding Box Algorithms
A. Ranchordas et al. (Eds.): VISIGRAPP 2008, CCIS , Springer, Volume 2, Pages 26–40, 2009.
Darko Dimitrov, Mathias Holst, Christian Knauer, Klaus Kriegel
Efficient Dynamical Computation of Principal Components
In Proceedings of International Conference on Computer Graphics Theory and Applications - GRAPP, Pages 85–93, Vilamoura, Portugal, 2011.
Darko Dimitrov, Mathias Holst, Christian Knauer, Klaus Kriegel
Shortest Inspection-Path Queries in Simple Polygons
In Proceedings of the 24th European Workshop on Computational Geometry (EuroCG), Pages 153–156, Nancy, France, March 2008.
Christian Knauer, Günter Rote, Lena Schlipf
Probabilistic matching of solids in arbitrary dimension
In Proceedings of the 27th European Workshop on Computational Geometry (EuroCG), Morschach, Switzerland, March 2011.