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

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.).
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.
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.
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.
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.
Two example applications of the eccentricity transform are presented.
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.