Catálogo de publicaciones - libros

This paper investigates binary homotopic 2D thinning in view of its independence of the order of processing image pixels. Pixel removal conditions are provided leading to an order independent thinning. They are introduced for various types of connectivity. Two kinds of pixels to be removed are considered: simple and b-simple. Use of each of those pixels yields to different types of order independent thinnings: homotopic marking and local-SKIZ.

The notion of skeleton plays a major role in shape analysis. Some usually desirable characteristics of a skeleton are: sufficient for the reconstruction of the original object, centered, thin and homotopic. The Euclidean Medial Axis presents all these characteristics in a continuous framework. In the discrete case, the Exact Euclidean Medial Axis (MA) is also sufficient for reconstruction and centered. It no longer preserves homotopy but it can be combined with a homotopic thinning to generate homotopic skeletons. The thinness of the MA, however, may be discussed. In this paper we present the definition of the Exact Euclidean Medial Axis on Higher Resolution which has the same properties as the MA but with a better thinness characteristic, against the price of rising resolution. We provide an efficient algorithm to compute it.

We propose a fast method for computing distance transforms and skeletons of 3D objects using programmable Graphics Processing Units (GPUs). We use an efficient method, called distance splatting, to compute the distance transform, a one-point feature transform, and 3D skeletons. We efficiently implement 3D splatting on GPUs using 2D textures and a hierarchical bi-level acceleration scheme. We show how to choose near-optimal parameter values to achieve high performance. We show 3D skeletonization and object reconstruction examples and compare our performance with similar state-of-the-art methods.

We prove that the boundary of a polycube (finite union of integer unit cubes) has always a tiling by foldable dominoes (two edge-adjacent unit squares on the boundary). Moreover, the adjacency graph of the unit squares in the boundary of a spherical polycube has a Hamiltonian cycle.

A new digital hyperplane recognition method is presented. This algorithm allows the recognition of Standard and Supercover hyperplanes by incrementally computing in a dual space the generalized preimage of a given hypervoxel set. Each point in this preimage corresponds to a Euclidean hyperplane which intersects all given hypervoxels. An advantage of the generalized preimage is that it does not depend on the hypervoxel locations. Moreover, the proposed recognition algorithm does not require the hypervoxels to be connected or ordered in any way.

The Distance Transform on Curved Space (DTOCS) calculates distances along a gray-level height map surface. In this article, the DTOCS is generalized for surfaces represented as real altitude data in an anisotropic grid. The distance transform combined with a nearest neighbor transform produces a roughness map showing the average roughness of image regions in addition to one roughness value for the whole surface. The method has been tested on profilometer data measured on samples of different paper grades. The correlation between the new method and the arithmetic mean deviation of the roughness surface, S _ a , for small wavelengths was strong for all tested paper sample sets, indicating that the DTOCS measures small scale surface roughness.

Designing interactive segmentation methods for digital volume images is difficult, mainly because efficient 3D interaction is much harder to achieve than interaction with 2D images. To overcome this issue, we use a system that combines stereo graphics and haptics to facilitate efficient 3D interaction. We propose a new method, based on the 2D live-wire method, for segmenting volume images. Our method consists of two parts: an interface for drawing 3D live-wire curves onto the boundary of an object in a volume image, and an algorithm for connecting two such curves to create a discrete surface.

This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPS for short). We prove that the decision problem (does there exist a decomposition with less than k DPS?) is NP-complete, and thus that the optimisation problem (finding the minimal number of DPS) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed.