Catálogo de publicaciones - libros

In this paper, we address the problem of vectorization of binary images on irregular isothetic grids. The representation of graphical elements by lines is common in document analysis, where images are digitized on (sometimes very-large scale) regular grids. Regardless of final application, we propose to first describe the topology of an irregular two-dimensional object with its associated Reeb graph, and we recode it with simple irregular discrete arcs. The second phase of our algorithm consists of a polygonal reconstruction of this object, with discrete lines through the elementary arcs computed in the previous stage. We also illustrate the robustness of our method, and discuss applications and improvements.

Duality applied to geometrical problems is widely used in many applications in computer vision or computational geometry. A classical example is the Hough Transform to detect linear structures in images. In this paper, we focus on two kinds of duality/polarity applied to geometrical problems: digital straightness detection and envelope computation.

This paper explores proofs of the isoperimetric inequality for 4-connected shapes on the integer grid ℤ^2, and its geometric meaning. Pictorially, we discuss ways to place a maximal number unit square tiles on a chess board so that the shape they form has a minimal number of unit square neighbors. Previous works have shown that “digital spheres” have a minimum of neighbors for their area. We here characterize all shapes that are optimal and show that they are all close to being digital spheres. In addition, we show a similar result when the 8-connectivity metric is assumed (i.e. connectivity through vertices or edges, instead of edge connectivity as in 4-connectivity).

In this paper, we provide an unified view of two definitions of digital lines in 3D via the use of lattice theory and specific projections of the lattice ℤ^3. We use this unified vision to explain the extension of the definition of Voss [1] to an arbitrary dimension and we show how to extend the definition of Figueiredo and Reveillès [2] to an arbitrary dimension.

In this paper we study the relationship between the Euclidean and the discrete world thru two operations based on the Euclidean scaling function: the discrete smooth scaling and the discrete based geometrical simplification.

In this paper the nodes of the hexagonal grid are used as points. Three types of neighbors are used on this grid, therefore neighborhood sequences contain values 1, 2 and 3. The grid is coordinatized by three coordinates in a symmetric way. Digital circles are classified based on digital distances using neighborhood sequences. They can be triangle, hexagon, enneagon and dodecagon. The corners of the convex hulls of these polygons are computed.

We introduce a new discrete primitive, the blurred piece of a discrete plane, which relies on the arithmetic definition of discrete planes. It generalizes such planes, admitting that some points are missing and then permits to adapt to noisy discrete data. Two recognition algorithms of such primitives are proposed: the first one is a geometrical algorithm and minimizes the Euclidean distance and the second one relies on linear programming and minimizes the vertical distance.

The number of line-convex directed polyominoes with given horizontal and vertical projections is studied. It is proven that diagonally convex directed polyominoes are uniquely determined by their orthogonal projections. The proof of this result is algorithmical. As a counterpart, we show that ambiguity can be exponential if antidiagonal convexity is assumed about the polyomino. Then, the results are generalised to polyominoes having convexity property along arbitrary lines.

Tomography deals with the reconstruction of images from their projections. In this paper we focus on tomographic reconstruction of binary images (i.e., black-and-white) that do not have an intrinsic lattice structure from a small number of projections. We describe how the reconstruction problem from only two projections can be formulated as a network flow problem in a graph, which can be solved efficiently. When only two projections are used, the reconstruction problem is severely underdetermined and many solutions may exist. To find a reconstruction that resembles the original image, more projections must be used. We propose an iterative algorithm to solve the reconstruction problem from more than two projections. In every iteration a network flow problem is solved, corresponding to two of the available projections. Different pairs of projection angles are used for consecutive iterations. Our algorithm is capable of computing high quality reconstructions from very few projections. We evaluate its performance on simulated projection data and compare it to other reconstruction algorithms.

Filling operations are procedures which are used in Discrete Tomography for the reconstruction of lattice sets having some convexity constraints. In [1], an algorithm which performs four of these filling operations has a time complexity of O ( N ^2log N ), where N is the size of projections, and leads to a reconstruction algorithm for convex polyominoes running in O ( N ^6 log N )-time. In this paper we first improve the implementation of these four filling operations to a time complexity of O ( N ^2), and additionally we provide an implementation of a fifth filling operation (introduced in [2]) in O ( N ^2log N ) that permits to decrease the overall time-complexity of the reconstruction algorithm to O ( N ^4log N ). More generally, the reconstruction of Q-convex sets and convex lattice sets (intersection of a convex polygon with ℤ^2) can be done in O ( N ^4log N )-time.