The eccentricity transform of n-dimensional shapes with and without boundary

Abstract

Form (engl. shape) ist eine Eigenschaft von Objekten. Sie charakterisiert die räumliche Ausdehnung des Objektes und identifiziert die Punkte die Teil des Objektes sind. Form ist sowohl komplex als auch strukturiert und ermöglicht es Objekte zu identifizieren (erkennen). Die Form eines Objektes kann als binäres Bild repräsentiert werden, z.B. ein Bild in dem jedes Element (Pixel, Voxel) entweder Teil des Objektes ist oder nicht. Bildtransformationen extrahieren aus einem Eingabebild Informationen einer höheren Abstraktionsebene (z.B. die Anzahl der verbundenen Komponenten, das Skeleton einer Form, etc.).<br />Die Exzentrizitätstransformation (engl. eccentricity transform) assoziiert zu jedem Punkt einer Form die geodätische Distanz zu dem am weitesten entfernten Punkt. Das heißt sie assoziiert zu jedem Punkt die Länge des längsten, kürzesten Pfades der innerhalb der Form liegt und den berücksichtigten Punkt mit einem der anderen Punkte der Form verbindet. Die Exzentrizitätstransformation gehört zu einer Klasse von Bildtransformationen die jedem Punkt einer Form eine Funktion der Distanz zu den anderen Punkten der Form zuweisen.<br />Diese Arbeit präsentiert die Exzentrizitätstransformation, ihre Eigenschaften und ihre Berechnung, und zeigt zwei Anwendungsbeispiele aus dem Bereich Computer Vision. Die Definition der Transformation wird in einem metrischen Raum formuliert und vereint die Konzepte von Exzentrizität (engl. eccentricity) aus der Graphentheorie, vom weitest entfernten Punkt (engl. furthest point) in "Computational Geometry" und von der Ausbreitungsfunktion (engl. propagation function) in der mathematischen Morphologie. Die Exzentrizitätstransformation ist robust gegenüber Rauschen (z.B.: Salz- und Pfefferrauschen - zufällig fehlende Punkte in der Form, und kleine Segmentierungsfehler). Sie ist außerdem quasi-invariant gegenüber den Artikulationen einer Form. Die exzentrischen Punkte einer Form (Punkte die am weitesten entfernt zu einem anderen Punkt der Form sind) werden immer an ihrem Rand gefunden, wenn die Form planar ist und nicht mehr als zwei Löcher hat. Bei planaren, einfach verbundenen Formen liegen diese Punkte auf den konvexen Teilen des Randes. Das geodätische Zentrum (der Punkt mit der kleinsten Exzentrizität) einer planaren, einfach verbundenen Form ist ein einzelner Punkt. Bei Formen mit Löchern oder einer nicht planaren 2D Mannigfaltigkeit, kann das Zentrum eine nicht verbundene Menge sein.<br />Die Exzentrizitätstransformation wird an einem Satz von Grundformen mit steigender Komplexität studiert (z.B.: Linien, konvexe, planare Formen, nicht konvexe, einfach verbundene Formen, planare Formen mit einem Loch, etc.). Eigenschaften, wie die Position des geodätischen Zentrums, die exzentrischen Punkte und die Möglichkeiten eine Form zu zerlegen, um eine effizientere Berechnung zu ermöglichen, werden analysiert. Diese Eigenschaften motivierten die präsentierten Berechnungsalgorithmen und -aspekte. Methoden zur genauen Berechnung der Exzentrizitätstransformation und effiziente Approximationen werden vorgestellt und evaluiert. Zusätzlich werden weitere Verbesserungen dieser Methoden und mögliche Parallelisierungen der Berechnungen diskutiert.<br />Zwei Anwendungsbeispiele für die Exzentrizitätstransformation werden vorgestellt. Ein Beispiel ist der Einsatz zum Beschreiben und Vergleichen von Formen. Dazu werden Histogramme der Exzentrizitätstransformation von 2D und 3D Formen erzeugt und als Deskriptoren verwendet. Die Anwendbarkeit der Exzentrizitätstransformation auf diesem Gebiet wird durch experimentelle Resultate und eine detaillierte Studie analysiert. Das zweite Anwendungsbeispiel ist die Verwendung von Exzentrizitätstransformation als Basis für ein formabhängiges Koordinatensystem für einfach verbundene, planare Formen. Der Zweck ist die Adressierung korrespondierender oder nahe beieinander liegender Punkte in unterschiedlich artikulierten Posen derselben Form.<br />

Shape is a property of an object. It characterizes an objects' spatial form and identifies the points that are part of the object. It is both complex and structured, and allows an object to be identified. A shape can be represented as a binary image i.e. an image where each picture element (pixel, voxel) is either part of the shape or not. Image transforms take as input an image and extract higher abstraction level information from it (e.g. count the number of connected components, compute the skeleton of a shape in the image, etc.).<br />The eccentricity transform associates to each point of a shape the geodesic distance to the point which is furthest away from it i.e. it associates to each point the length of the longest of the shortest paths that are contained in the shape and that connect the considered point with any other point of the shape. The eccentricity transform is part of a class of image transforms that associate to each point a function of the distance to other points of the shape.<br />This thesis presents the eccentricity transform, important properties, considers its computation, and gives two example applications in the context of computer vision. The definition unifies the concepts of eccentricity from graph theory, furthest point from computational geometry, and propagation function from mathematical morphology. The transform is robust with respect to noise (Salt and Pepper i.e. random missing points in the shape, and minor segmentation errors). It is quasi invariant with respect to articulation of the shape. For planar shapes with less than two holes, eccentric points (points which are furthest away for at least one other point of the shape) are always located on the boundary of the shape. For planar simply-connected shapes they lie on convex parts of the boundary. The geodesic center (points with minimum eccentricity) of a planar simply connected shape is a single point. For shapes with holes, or non planar 2D manifolds, it can be a disconnected set.<br />A study of the eccentricity transform of a set of basic shapes of increasing complexity (e.g. line, convex planar shapes, non-convex simply-connected shapes, planar shapes with a hole) is presented.<br />Properties like the position of the geodesic center and eccentric points, as well as the possibility to decompose the shapes for a more efficient computing are studied. These properties have motivated the presented algorithms and aspects. Precise computation and efficient approximation methods are given and evaluated. Further improvement and parallelisation possibilities are discussed.<br />Two example applications of the eccentricity transform are presented.<br />First, histograms of the eccentricity transform of 2D and 3D shapes are used as shape descriptors in a shape matching scenario. Experimental results and a detailed study are given. Following is the application of the eccentricity transform as a basis for a shape centered coordinate system for simply-connected planar shapes. The purpose is to address corresponding or nearby points in different articulated poses of the same shape.<br />