Discrete Geometry for Computer Imagery

We describe novel approaches to compute reliable solutions for many non-linear geometric problems that arise in geometric modeling, computer graphics and robotics. Specifically, we focus on problems that can be formulated as

surface extraction problems

. These include Boolean operations and Minkowski sums of polyhedral or higher models as well as reliable polygonization of general implicit surfaces. All these problems reduce to computing a topology preserving isosurface from a volumetric grid, i.e. the zero set of a scalar field. A common way of representing a scalar field is to discretize the continuous scalar field into discrete samples – to compute the value of the scalar field at the vertices of a volumetric grid. We refer to this step as a sampling of the scalar field. The grid is an approximate representation of the scalar field; the accuracy of the approximate representation depends on the rate of sampling – the resolution of the grid. An explicit boundary representation of the implicit surface can be obtained by extracting the zero-level isosurface using Marching Cubes or any of its variants. We refer to these isosurface extraction algorithms collectively as

MC-like algorithms

. The output of an MC-like algorithm is an approximation – usually a polygonal approximation – of the implicit surface. We refer to this step as reconstruction of the implicit surface.

Image analysis attempts to perceive properties of the continuous real world by means of digital algorithms. Since discretization discards an infinite amount of information, it is difficult to predict if and when digital methods will produce reliable results. This paper reviews theories which establish explicit connections between the continuous and digital domains (such as Shannon’s sampling theorem and a recent geometric sampling theorem) and describes some of their consequences for image analysis. Although many problems are still open, we can already conclude that adherence to these theories leads to significantly more stable and accurate algorithms.

Since several centuries Mathematics award the prominent position to continuous concepts and a secondary one to discrete objects and integers. On the contrary Computer Science and digital technologies lay integers and discrete structures at the heart of their concerns and recover continuous notions from them.

During the eighties some Strasbourg’s mathematicians (mainly G. Reeb and J. Harthong) showed, relying on Non Standard Analysis, how integers could be substituted to real numbers in areas like Analysis and Geometry.

Even if Strasbourg’s NSA researchers were not, at first, motivated by relationships between Mathematics and Computer Science, they soon realized the interest of this issue and started some work in that direction, mainly on the use of

all integers methods

to integrate differential equations.

It was only from 1987 that convergence with Digital Geometry arose (A. Troesch, J.-P. Reveillés) resulting in original definitions for discrete objects (lines, planes, circles...)

Work independently done since that time by digital geometers produced many results but, also, the need for new tools as one to treat

multiscale digital objects

.

We will briefly explain why mathematicians can be interested in Non Standard Analysis and some of the consequences this had in Strasbourg’s mathematics department, mainly Harthong’s Moiré theory and Reeb’s integration of equation

y

′ = 

y

by an

all integer

method.

This last one, called

Weak Rational Computing

, is a kind of abstract

Multiscale System

which will be detailed with the help of simple linear and non linear differential equations and iteration systems applied to geometric entities.

In this paper, we recall the origins of discrete analytical geometry developed by J-P. Reveillès [1] in the nonstandard model of the continuum based on integers proposed by Harthong and Reeb [2,3]. We present some basis on constructive mathematics [4] and its link with programming [5,6]. We show that a suitable version of this new model of the continuum partly fits with the constructive axiomatic of ℝ proposed by Bridges [7]. The aim of this paper is to take a first look at a possible formal and constructive approach to discrete geometry. This would open the way to better algorithmic definition of discrete differential concepts.

This paper extends, in a multi-dimensional framework, pattern recognition technics for generation or recognition of digital lines. More precisely, we show how the connection between chain codes of digital lines and continued fractions can be generalized by a connection between tilings and multi-dimensional continued fractions. This leads to a new approach for generating and recognizing digital hyperplanes.

In this paper we prove that the function giving the frequency of a class of patterns of digital planes with respect to the slopes of the plane is continuous and piecewise affine, moreover the regions of affinity are precised. It allows to prove some combinatorial properties of a class of patterns called (

m

,

n

)-cubes. This study has also some consequences on local estimators of area: we prove that the local estimators restricted to regions of plane never converge to the exact area when the resolution tends to zero for almost all slope of plane. Actually all the results of this paper can be generalized for the regions of hyperplanes for any dimension

d

 ≥ 3.

The proofs of some results used in this article are contained in the extended version of this paper [1].

The notion of convexity translates non-trivially from Euclidean geometry to discrete geometry, and detecting if a discrete region of the plane is convex requires analysis. In this paper we study digital convexity from the combinatorics on words point of view, and provide a fast optimal algorithm checking digital convexity of polyominoes coded by the contour word. The result is based on the Lyndon factorization of the contour word, and the recognition of Christoffel factors that are approximations of digital lines.

In this paper, we introduce a method to express a local linear operated in the neighbourhood of each point in the discrete space as a matrix transform. To derive matrix expressions, we develop a decomposition and construction method of the neighbourhood operations using algebraic properties of the noncommutative matrix ring. This expression of the transforms in image analysis clarifies analytical properties, such as the norm of the transforms. We show that the symmetry kernels for the neighbourhood operations have the symmetry matrix expressions.

We introduce in this paper a notion of continuity in digital spaces which extends the usual notion of digital continuity. Our approach uses multivalued maps. We show how the multivalued approach provides a better framework to define topological notions, like retractions, in a far more realistic way than by using just single-valued digitally continuous functions. In particular, we characterize the deletion of simple points, one of the most important processing operations in digital topology, as a particular kind of retraction.

This paper expands on previous work on relationships between digital lines and continued fractions (CF). The main result is a parsimonious description of the construction of the digital line based only on the elements of the CF representing its slope and containing only simple integer computations. The description reflects the hierarchy of digitization runs, which raises the possibility of dividing digital lines into equivalence classes depending on the CF expansions of their slopes. Our work is confined to irrational slopes since, to our knowledge, there exists no such description for these, in contrast to rational slopes which have been extensively examined. The description is exact and does not use approximations by rationals. Examples of lines with irrational slopes and with very simple digitization patterns are presented. These include both slopes with periodic and non-periodic CF expansions, i.e. both quadratic surds and other irrationals.

In this article, we present new results on simple points, minimal non-simple sets (MNS) and P-simple points. In particular, we propose new characterizations which hold in dimensions 2, 3 and 4, and which lead to efficient algorithms for detecting such points or sets. This work is settled in the framework of cubical complexes, and some of the main results are based on the properties of critical kernels.

Morse theory studies the relationship between the topology of a manifold

M

and the critical points of a scalar function

f

defined on

M

. The Morse-Smale complex associated with

f

induces a subdivision of

M

into regions of uniform gradient flow, and represents the topology of

M

in a compact way. Function

f

can be simplified by cancelling its critical points in pairs, thus simplifying the topological representation of

M

, provided by the Morse-Smale complex. Here, we investigate the effect of the cancellation of critical points of

f

in Morse-Smale complexes in two and three dimensions by showing how the change of connectivity of a Morse-Smale complex induced by a cancellation can be interpreted and understood in a more intuitive and straightforward way as a change of connectivity in the corresponding ascending and descending Morse complexes. We consider a discrete counterpart of the Morse-Smale complex, called a quasi-Morse complex, and we present a compact graph-based representation of such complex and of its associated discrete Morse complexes, showing also how such representation is affected by a cancellation.

Toric spaces being non-simply connected, it is possible to find in such spaces some loops which are not homotopic to a point: we call them

toric loops

. Some applications, such as the study of the relationship between the geometrical characteristics of a material and its physical properties, rely on three-dimensional discrete toric spaces and require detecting objects having a toric loop.

In this work, we study objects embedded in discrete toric spaces, and propose a new definition of loops and equivalence of loops. Moreover, we introduce a characteristic of loops that we call

wrapping vector

: relying on this notion, we propose a linear time algorithm which detects whether an object has a toric loop or not.

Hierarchical representations, such as irregular pyramids, are the bases of several applications in the field of discrete imagery. So,

n

-dimensional ”bottom-up” irregular pyramids can be defined as stacks of successively reduced

n

-dimensional generalized maps (

n

-G-maps) [11], each

n

-G-map being defined from the previous level by using removal and contraction operations defined in [8]. Our goal is to build a theoretical framework for defining and handling

n

-dimensional ”top-down” irregular pyramids. To do so, we propose in this paper to study the definition of both insertion and expansion operations that allow to conceive these kinds of pyramids.

This paper defines a theory of conformal parametrization of digital surfaces made of surfels equipped with a normal vector. The main idea is to locally project each surfel to the tangent plane, therefore deforming its aspect-ratio. It is a generalization of the theory known for polyhedral surfaces. The main difference is that the conformal ratios that appear are no longer real in general. It yields a generalization of the standard Laplacian on weighted graphs.

Preserving topological properties of objects during thinning procedures is an important issue in the field of image analysis. This paper constitutes an introduction to the study of non-trivial simple sets in the framework of cubical 3-D complexes. A simple set has the property that the homotopy type of the object in which it lies is not changed when the set is removed. The main contribution of this paper is a characterisation of the non-trivial simple sets composed of exactly two voxels, such sets being called minimal simple pairs.

We show that determining whether or not a simplicial 2 − complex collapses to a point is deterministic polynomial time decidable. We do this by solving the problem of constructively deciding whether a simplicial 2 −complex collapses to a 1 −complex. We show that this proof cannot be extended to the 3D case, by proving that deciding whether a simplicial 3 −complex collapses to a 1 −complex is an

NP

 −complete problem.

Chamfer distances are discrete distances based on the propagation of local distances, or weights defined in a mask. The medial axis, i.e. the centers of the maximal disks (disks which are not contained in any other disk), is a powerful tool for shape representation and analysis. The extraction of maximal disks is performed in the general case with comparison tests involving look-up tables representing the covering relation of disks in a local neighborhood. Although look-up table values can be computed efficiently [1], the computation of the look-up table neighborhood tend to be very time-consuming. By using polytope [2] descriptions of the chamfer disks, the necessary operations to extract the look-up tables are greatly reduced.

Recently, a distance function was defined on the face- centered cubic and body-centered cubic grids by combining weights and neighbourhood sequences. These distances share many properties with traditional path-based distance functions, such as the city-block distance, but are less rotational dependent. We present conditions for metricity and algorithms to compute the distances.

The eccentricity transform associates to each point of a shape the geodesic distance to the point farthest away from it. The transform is defined in any dimension, for simply and non simply connected sets. It is robust to Salt & Pepper noise and is quasi-invariant to articulated motion. Discrete analytical concentric circles with constant thickness and increasing radius pave the 2D plane. An ordering between pixels belonging to circles with different radius is created that enables the tracking of a wavefront moving away from the circle center. This is used to efficiently compute the single source shape bounded distance transform which in turn is used to compute the eccentricity transform. Experimental results for three algorithms are given: a novel one, an existing one, and a refined version of the existing one. They show a good speed/error compromise.

We present a novel template matching framework for detecting geometrically transformed objects. A template is a simplified representation of the object of interest by a set of pixel groups of any shape, and the similarity between the template and an image region is derived from the F-test statistic. The method selects a geometric transformation from a discrete set of transformations, giving the best statistical independence of such groups Efficient matching is achieved using 1D analogue of integral images - integral lines, and the number of operations required to compute the matching score is linear with template size, comparing to quadratic dependency in conventional template matching. Although the assumption that the geometric deformation can be approximated from discrete set of transforms is restrictive, we introduce an adaptive subpixel refinement stage for accurate matching of object under arbitrary parametric 2D-transformation. The parameters maximizing the matching score are found by solving an equivalent eigenvalue problem. The methods are demonstrated on synthetic and real-world examples and compared to standard template matching methods.

In this article, we propose to investigate the extension of the E

$\textsuperscript{2}$

DT (squared Euclidean Distance Transformation) on irregular isothetic grids. We give two algorithms to handle different structurations of grids. We first describe a simple approach based on the complete Voronoi diagram of the background irregular cells. Naturally, this is a fast approach on sparse and chaotic grids. Then, we extend the separable algorithm defined on square regular grids proposed in [22], more convenient for dense grids. Those two methodologies permit to process efficiently E

2

DT on every irregular isothetic grids.

Rotation configurations for quadratic angles exhibit self-similar dynamics. Visually, it may be considered as quite evident. However, no additional details have yet been published on the exact nature of the arithmetical reasons that support this fact. In this paper, to support the existence of self-similar dynamic in 2d-configuration, we will use the constructive 1-d substitution theory in order to iteratively build quadratic rotation configurations from substitutive Sturmian words. More specifically : the self-similar rotation configurations are first shown to be an interlacing of configurations that are direct product of superposition of Sturmian words.

A novel method for segmenting simplified skeletons of 3D shapes is presented. The so-called simplified Y-network is computed, defining boundaries between 2D sheets of the simplified 3D skeleton, which we take as our skeleton segments. We compute the simplified Y-network using a robust importance measure which has been proved useful for simplifying complex 3D skeleton manifolds. We present a voxel-based algorithm and show results on complex real-world objects, including ones containing large amounts of boundary noise.

We present in this paper robust geometric feature estimators on the border of a possibly noisy discrete object. We introduce the notion of patch centered at a point of this border. Thanks to a width parameter, attached to a patch, the noise on the border of the discrete object can be considered, and an extended flat neighborhood of a border point is computed. Stable geometric features are then extracted around this point. A normal vector estimator is proposed as well as a detector of convex and concave parts on the border of a discrete object.

In this paper, we present a method that we call

on-surface convolution

which extends the classical notion of a 2D digital filter to the case of digital surfaces (following the

cuberille

model). We also define an averaging mask with local support which, when applied with the iterated convolution operator, behaves like an averaging with large support. The interesting property of the latter averaging is the way the resulting weights are distributed: they tend to decrease following a “continuous” geodesic distance within the surface. We eventually use the iterated averaging followed by convolutions with differentiation masks to estimate partial derivatives and then normal vectors over a surface. We provide an heuristics based on [14] for an optimal mask size and show results.

We analyze the moment of inertia

, relative to the center of gravity, of finite plane lattice sets

S

. We classify these sets according to their roundness: a set

S

is rounder than a set

T

if

. We show that roundest sets of a given size are strongly convex in the discrete sense. Moreover, we introduce the notion of quasi-discs and show that roundest sets are quasi-discs. We use weakly unimodal partitions and an inequality for the radius to make a table of roundest discrete sets up to size 40. Surprisingly, it turns out that the radius of the smallest disc containing a roundest discrete set

S

is not necessarily the radius of

S

as a quasi-disc.

The aim of the paper is to define an algorithm for computing preimages - roughly the sets of naive digital planes containing a finite subset

S

of ℤ

3

. The method is based on theoretical results: the preimage is a polytope that vertices can be decomposed in three subsets, the upper vertices, the lower vertices and the intermediary ones (equatorial). We provide a geometrical understanding (as facets on

S

or

S

 ⊝ 

S

) of each kind of vertices. These properties are used to compute the preimage by gift-wrapping some regions of the convex hull of

S

or of

S

 ⊝ 

S

 ∪ {(0,0,1)}.

This paper presents a hybrid two-step method for segmenting a 3D grid-point cloud into planar surfaces by using discrete-geometry results. Digital planes contain a finite number of local geometric patterns (LGPs). Such a LGP possesses a set of normal vectors. By using LGP properties, we first reject non-linear points from a point cloud (edge-based step), and then classify non-rejected points whose LGPs have common normal vectors into a planar-surface-point set (region-based step).

In this paper we introduce a new curvature estimator based on global optimisation. This method called Global Min-Curvature exploits the geometric properties of digital contours by using local bounds on tangent directions defined by the maximal digital straight segments. The estimator is adapted to noisy contours by replacing maximal segments with maximal blurred digital straight segments. Experimentations on perfect and damaged digital contours are performed and in both cases, comparisons with other existing methods are presented.

This paper introduces a method for the digital naive plane recognition problem. This method is a revision of a previous one. It is the only method which guarantees an

O

(

n

log

D

) time complexity in the worst-case, where (

D

 − 1) represents the size of a bounding box that encloses the points, and which is very efficient in practice. The presented approach consists in determining if a set of

n

points in ℤ

3

corresponds to a piece of digital naive hyperplane in

$\lfloor 4\log_{9/5}D \rfloor + 10$

iterations in the worst case. Each iteration performs

n

dot products. The method determines whether a set of 10

6

voxels corresponds to a piece of a digital plane in ten iterations in the average which is five times less than the upper bound. In addition, the approach succeeds in reducing the digital naive plane recognition problem in ℤ

3

to a feasibility problem on a two-dimensional convex function. This method is especially fitted when the set of points is dense in the bounding box, i.e. when

$D=O(\sqrt{n})$

.

The recognition of digital shapes is a deeply studied problem. The arithmetical framework, initiated by J.P. Reveillès in [1], provides a great theoretical basis, as well as many algorithms to deal with discrete objects. Among the many available tools, the tangential cover is a powerful one. First presented in [2], it computes the set of all maximal segments of a digital curve and allows either to obtain minimal length polygonalization, or asymptotic convergence of tangent estimations. Nevertheless, the arithmetical approach does not tolerate the introduction of irregularities, which are however inherent to the acquisition of digital shapes. In this paper, we propose a new definition for a class of so-called ”thick digital curves” that applies well to a large class of discrete objects boundaries. We then propose an extension of the tangential cover to thick digital curves and provide an algorithm with a

O

(

n

log

n

) complexity, where

n

is the number of points of specific subparts of the thick digital curve.

We present a new method to estimate derivatives of digitized functions. Even with noisy data, this approach is convergent and can be computed by using only the arithmetic operations. Moreover, higher order derivatives can also be estimated. To deal with parametrized curves, we introduce a new notion which solves the problem of correspondence between the parametrization of a continuous curve and the pixels numbering of a discrete object.

Segmentation is an important step to obtain quantitative information from tomographic data sets. To this end, global thresholding is often used in practice. However, it is usually not possible to obtain an accurate segmentation based on a single, global threshold. Instead, local thresholding schemes can be applied that use a varying threshold, depending on local characteristics of the tomogram. Selecting the best local thresholds is not a straightforward task, as local image features often do not provide sufficient information for choosing a proper threshold. Recently, the concept of

projection distance

was proposed as a new criterion for evaluating the quality of a tomogram segmentation. In this paper, we describe how Projection Distance Minimization (PDM) can be used to select local thresholds, based on the available projection data from which the tomogram was initially computed. By reprojecting the segmented image, a comparison can be made with the measured projection data. This yields a quantitative measure of the quality of the segmentation. By minimizing the difference between the computed and measured projections, optimal local thresholds can be computed.

Simulation experiments have been performed, comparing our local thresholding approach with an alternative local thresholding method and with optimal global thresholding. Our results demonstrate that the local thresholding approach yields segmentations that are significantly more accurate, in particular when the tomogram contains artifacts.

This paper deals with the reconstruction of binary matrices having

exactly

 − 1 − 4 − 

adjacency

constraints from the horizontal and vertical projections. Such a problem is shown to be non polynomial by means of a reduction which involves the classic NP-complete problem 3-color. The result is reached by bijectively mapping all the four different cells involved in 3-color into maximal configurations of 0s and 1s which show the adjacency constraint, and which can be merged into a single binary matrix.

Mojette projections of discrete pixel arrays form good approximations to experimental parallel-beam x-ray intensity absorption profiles. They are discrete sums taken at angles defined by rational fractions. Mojette-like projections form a “half-way house” between a conventional sinogram and fully digital projection data. A new direct and exact image reconstruction technique is proposed here to invert arbitrary but sufficient sets of Mojette data. This new method does not require iterative, statistical solution methods, nor does it use the efficient but noise-sensitive “corner-based” inversion method. It instead exploits the exact invertibility of the prime-sized array Finite Radon Transform (FRT), and the fact that all Mojette projections can be mapped directly into FRT projections. The algorithm uses redundant or “calibrated” areas of an image to expand any asymmetric Mojette set into the smallest symmetric FRT set that contains all of the Mojette data without any re-binning. FRT data will be missing at all angles where Mojette data is not provided, but can be recovered exactly from the “ghost projections” that are generated by back-projecting all the known data across the calibrated regions of the reconstructed image space. Algorithms are presented to enable efficient image reconstruction from any exact Mojette projection set, with a view to extending this approach to invert real x-ray data.

We study the problem of reconstructing hv-convex binary matrices from few projections. We solve a polynomial time case and we determine some properties of the hv-convex matrices. Since the problem is NP-complete, we provide an iterative approximation based on a longest path and a min-cost/max-flow model. The experimental results show that the reconstruction algorithm performs quite well.

The concept of constrained connectivity [Soille 2008, PAMI] is summarised. We then introduce a variety of measurements for characterising connected components generated by constrained connectivity relations. We also propose a weighted mean for estimating a representative value of each connected component. Finally, we define the notion of spurious connected components and investigate a variety of methods for suppressing them.

We recently introduced the watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, we propose a new thinning paradigm to compute them. More precisely, we introduce a new transformation, called border thinning, that lowers the values of edges that match a simple local configuration until idempotence and prove the equivalence between the cuts obtained by this transformation and the watershed cuts of a map. We discuss the possibility of parallel algorithms based on this transformation and give a sequential implementation that runs in linear time whatever the range of the input map.

Fuzzy sets theory constitutes a poweful tool, that can lead to more robustness in problems such as image segmentation and recognition. This robustness results to some extent from the partial recovery of the continuity that is lost during digitization. Here we deal with fuzzy connectivity notions. We show that usual fuzzy connectivity definitions have some drawbacks, and we propose a new definition, based on the notion of hyperconnection, that exhibits better properties, in particular in terms of continuity. We illustrate the potential use of this definition in a recognition procedure based on connected filters. A max-tree representation is also used, in order to deal efficiently with the proposed connectivity.

In the present paper a morphological approach for segmenting directional structures is proposed. This approach is based on the concept of the line-segment and orientation functions. The line-segment function is computed from the supremum of directional erosions. This function contains the sizes of the longest lines that can be included in the structure. To determine the directions of the line segments, the orientation function which contains the angles of the line segments it is built when the line-segment function is computed. Next, by combining both functions, a weighted partition is built using the watershed transformation. Finally, the elements of the partition are merged according to some directional and size criteria for computing the desired segmentation of the image using a RAG structure.

The discrete epipolar line, a discrete version of the epipolar line, is recently proposed to give geometric relationships between pixels in two different views so that we can directly deal with pixels in digital images. A method is then proposed to determine the discrete epipolar line providing that fully calibrated images are available. This paper deals with weakly calibrated digital images and proposes a method for determining the discrete epipolar line using only weakly calibrated images. This paper also deepens the work further, presenting a method for identifying the corresponding region in a third view from a given pair of corresponding pixels in two views.

We aim to model and visualize the evolution of the surface structure of a cultivated soil surface during rainfall. In this paper, we briefly present our model, based on an Extended Cellular Automaton, and the different simulated processes. Among these processes, we focus on runoff which is of high relevance as it drives the evolution of the soil surface structure by transporting and depositing the detached fragments of soil and thus inducing an evolution in the granulometry of the surface material. We propose a simple algorithm to model, in a discrete way, runoff and also the transport and deposition of soil fragments according to their size. In that way we are able to derive information about the evolution of soil surface granulometry. A validation of the runoff model is proposed, based on the comparison of the results obtained with results from a numerical solution of the Saint Venant’s equations. Although no validation was attempted for transport, simulations yielded visually promising results.

Differential operators are essential in many image processing applications. Previous work has shown how to compute derivatives more accurately by examining the image locally, and by applying a difference operator which is optimal for each pixel neighborhood. The proposed technique avoids the explicit computation of fitting functions, and replaces the function fitting process by a function classification process. This paper introduces a new criterion to select the best function class and the best template size so that the optimal difference operator is applied to a given digitized function. An evaluation of the performance of the selection criterion for the computation of the Laplacian for digitized functions shows better results when compared to our previous method and the widely used Laplacian operator.

This paper presents the first segmentation operation defined within the 3D topological map framework. Firstly we show how a traditional segmentation algorithm, found in the literature, can be transposed on a 3D image represented by a topological map. We show the consistency of the results despite of the modifications made to the segmentation algorithm and we study the complexity of the operation. Lastly, we present some experimental results made on 3D medical images. These results show the process duration of this method and validate the interest to use 3D topological map in the context of image processing.

In this paper, we introduce a novel image-dependent filtering approach derived from concepts known in mathematical morphology. Like other adaptive methods, it assumes that the local neighbourhood of a pixel contains the essential process required for the estimation of local properties. Indeed, it performs a local weighted averaging by combining both spatial and tonal information in a single similarity measure based on the local calculation of discrete geodesic time functions. Therefore, the proposed approach does not require the definition of any initial spatial window but determines adaptively, directly from the input data, the neighbouring sample points and the associated weights. The resulting adaptive filters are consistent with the content of the image and, therefore, they are particularly designed for the purpose of denoising and smoothing of digital images.

For book scanner technologies projective distortions are the main problem. In general, the use of 3d measurements of a warped surface is the best way to remove the projective distortions. But if the quality of the 3d measurements is very low, it is difficult to get satisfying dewarping results. In our paper we present a new technique handling this problem by introducing a simplified surface model. We use this model as a basis to compute a linear approximation parallel to the geometrical position of the book crease. The resulting method leads to a robust and fast computation. It provides us with a reliable dewarping output even for weak measurements given by a light sectioning method of top view scanners.

In this paper, we present a new representation model for the topology and the geometry of a 3D segmented image. This model has been designed to provide main features and operations required by a 3D image segmentation library. It is mainly devoted to region based segmentation methods such as split and merge algorithms but is also convenient for contour based approaches. The model has been fully implemented and tested both on synthetic and real 3D images.