Catálogo de publicaciones - libros

In this article the homology of simploidal sets is studied. Simploidal sets generalize both simplicial complexes and cubical complexes, more precisely cells of simplicial sets are cartesian products of simplices. We define one homology for simploidal sets and we prove that this homology is equivalent to the homology usually defined on simplicial complexes.

The intrinsic volumes – in 3d up to constants volume, surface area, integral of mean curvature, and Euler number – are a very useful set of geometric characteristics. Combining integral and digital geometry we develop a method for efficient simultanous calculation of the intrinsic volumes of sets observed in binary images. In order to achieve consistency in the derived intrinsic volumes for both foreground and background, suitable pairs of discrete connectivities have to be used. To make this rigorous, the concepts discretization w.r.t. an adjacency system and complementarity of adjacency systems are introduced.

In this paper, we compare two different definitions of distance transform for gray level images: the Gray Weighted Distance Transform (GWDT), and the Weighted Distance Transform On Curved Space (WDTOCS). We show through theoretical and experimental comparisons the differences, the strengths and the weaknesses of these two distances.

Chordal Axis (CA) is a new representation of planar shapes introduced by Prasad in [1], useful for skeleton computation, shape analysis, characterization and recognition. The CA is a subset of chord and center of discs tangent to the contour of a shape, derivated from Medial Axis (MA). Originally presented in a computational geometry approach, the CA was extracted on a constrained Delaunay triangulation of a discretely sampled contour of a shape. Since discrete distance transformations allow to efficiently compute the center of distance balls and detect discrete MA, we propose in this paper to redefine the CA in the discrete space, to extract on distance transforms in the case of chamfer norms, for which the geometry of balls is well-known, and to compare with MA.

Although widely used for image processing, Distance Transforms have only recently started to be used in computer graphics. This paper proposes a new mesh simplification technique based on Distance Transforms that allows taking into account the proximity of a mesh element to the focus of attention for adapting the approximation error which will be tolerated during the simplification process to the relative importance of that mesh element. Experimental results show the feasibility of this approach.

A sequential algorithm for computing the distance map using distances based on neighbourhood sequences (of any length) in the 2D square grid; and 3D cubic, face-centered cubic, and body-centered cubic grids is presented. Conditions for the algorithm to produce correct results are derived using a path-based approach. Previous sequential algorithms for this task have been based on algorithms that compute the digital Euclidean distance transform. It is shown that the latter approach is not well-suited for distances based on neighbourhood sequences.

A modification of the hierarchical chamfer matching algorithm (HCMA) with the effect that no binarisation of the edge information is performed is investigated. HCMA is a template matching algorithm used in many applications. A distance transform (DT) from binarised edges in the search image is used to guide the template to good positions. Local minima of a function using the distance values hit by the template correspond to potential matches. We propose to use distance weighted propagation of gradient magnitude information as a cost image instead of a DT from the edges. By this we keep as much information as possible until later in the matching process and, hence, do not risk to discard good matches in the edge detection and binarisation process.

Discrete Euclidean distance transforms, both exact and approximate, have been studied for some time, in particular by the Discrete Geometry community. In this paper we extend the notion of Euclidean distance transform (EDT) to elliptical distance transform (LDT). The LDT takes an additional two fixed parameters (eccentricity and orientation) in 2-D and an additional four in 3-D (two ratios and two angles) in 3-D, instead of 1 for the EDT in all cases . We study first how the LDT can be computed efficiently with good approximation in the case where all parameters are constant. We provide an application to binary object segmentation as motivation for this work.

This paper introduces a new method for the naive digital plane recognition problem. As efficient as existing alternatives, it is the only method known to the author that also guarantees a quasi linear time complexity in the worst case. The approach presented can be used to determine if a set of n points is a naive digital hyperplane in ℤ^ d in O ( n log^2 D ) worst case time where D represents the size of a bounding box that encloses the points. In addition, the approach succeeds in reducing the naive digital plane recognition problem to a two-dimensional convex optimization program. Thus, the solution space is planar and only simple two-dimensional geometrical methods need to be applied during the recognition process. The algorithm is a composite of simple techniques based on one-dimensional optimization: Megiddo Oracle for linear programming and two-dimensional discrete geometry.

Region merging methods consist of improving an initial segmentation by merging some pairs of neighboring regions. We consider a segmentation as a set of connected regions, separated by a frontier. If the frontier set cannot be reduced without merging some regions then we call it a watershed. In a general graph framework, merging two regions is not straightforward. We define four classes of graphs for which we prove that some of the difficulties for defining merging procedures are avoided. Our main result is that one of these classes is the class of graphs in which any watershed is thin. None of the usual adjacency relations on ℤ^2 and ℤ^3 allows a satisfying definition of merging. We introduce the perfect fusion grid on ℤ^ n , a regular graph in which merging two neighboring regions can always be performed by removing from the frontier set all the points adjacent to both regions.