Abstract:
Sampling is a fundamental operation that converts a continuous object into a discrete representation. Information theory provides some ways of characterizing the optimality of a discretization (quantization noise power). Centroidal Voronoi Tesselations are minimizers of the quantization noise power, and therefore can be used to compute an optimal discretization of an object. In this demo, we attempt to give an intuition of the mathematical concepts and algorithms to compute a Centroidal Voronoi Tesselation. Then we present several applications of Centroidal Voronoi Tesselations, to color quantization, meshing and remeshing in 2D and 3D. The demo will be presented using our Graphite software (alice.loria.fr/software/graphite) with a new technology that seamlessly integrates some slides and many software demonstrations. Some of the slides are available from:

• onCVT_slides.pdf
• LpCVT_slides.pdf

Some videos of the software that will be demonstrated can be seen from:

• A_xvid.avi
• B_xvid.avi
• C_xvid.avi
• D_xvid.avi

Abstract:
DGtal is a generic open source library for Digital Geometry programming whose main objective is to gather and structure different developments from the digital geometry and topology community. The benefits are numerous: to make easier the appropriation of our tools for a neophyte (new PhD students, researchers from other topics, ...), to permit better comparisons of new methods with already existing approaches, to construct a federative project. Furthermore we believe this is a necessary step for a better recognition of the efficiency of discrete geometry techniques by the important image analysis community. As a consequence, DGtal is designed so as to simplify the construction of effective demonstration tools. New results are thus easily shared to a vast audience.
On a more technical level, DGtal is developed in C++. Similarly to other classical libraries such as CGAL, it follows the paradigm of genericity with efficiency. This approach is made possible with the now well-known notion of concepts, implemented with templated types. The kernel of DGtal offers digital spaces of arbitrary dimension, with user-chosen integer types. Several digital topology algorithms are already implemented (Rosenfeld topology, connected components, simple points, homotopic thinning). The kernel manages generic images (standard raster images but also tree images), and arbitrary file formats with ImageMagick installed. Basic geometric primitives (digital lines and segments) are also available, as well as arbitrary dimensional volumetric distance transforms. A stream mechanism has been developed to display digital objects and export results in different vector formats.
DGtal is a collaborative effort --- for now --- of the French digital geometry community. It is still a work in progress but show already many promises to be the common basis for future developments made by the digital geometry community. The next milestone (DGCI) should include grid topology, geometric primitives and estimators, and other elements.
Visit the DGtal home page

Main participants:
D. Coeurjolly (LIRIS, Lyon), G. Damiand (LIRIS, Lyon), S. Fourey (GREYC, Caen), B. Kerautret (LORIA, Nancy), J.-O. Lachaud (LAMA, Chambéry), L. Provot (LORIA, Nancy), T. Roussillon (LIRIS, Lyon), I. Sivignon (Gipsa-lab, Grenoble).

(a) 3D homotopic thinning	(b) 2D euclidean distance transform	(c) Digital straight segment decomposition	(d) 2D image with a pointerless quadtree

Abstract:
Many image processing applications rely on a man machine cooperation to select relevant visual features such as straight lines. In this demonstration, we present a new interactive method to select and extract straight lines from gray-level images. It is based on the concept of blurred segment used to bound noisy image data within thick segments with controlable width. Estimated position and direction parameters are refined through a three-steps coarse to fine approach. An incremental digital straight segment recognition algorithm has been extended to cope with gray-level information. It implements quite simple criteria to provide a restricted list of candidate pixels to the recognition process. This algorithm ensures compatible response time with man machine cooperation requirements.

poster [pdf] Abstract:
A linear algorithm based on a discrete geometry approach is proposed for the detection of digital arcs and digital circles using a new representation of them. It is introduced by inspiring from the work of Latecki [Latecki00]. By utilizing this representation, we transform the problem of digital arc detection into a problem of digital straight line recognition. We then develop a linear method for the segmentation of curves into digital arcs. In addition, the proposed method can naturally work with disconnected or possibly noisy curves thanks to the notion of blurred segment [Debled05]. This simple and robust method can be applied to detect the arcs in images and technical documents.

Abstract: During a recent study about discrete rotation based on hinge angles for digital images, we had the problem of comparing quadratic irrationals when we wanted to partition the parameter space. Most existing techniques approximate the real (or numerical) value of a quadratic irrational. However, these techniques have the following two problems: (1) Computers normally use the IEEE representation for real numbers; this standard represents a floating point number up to some precision as supported by the computing hardware. However, irrational numbers, such as $\sqrt{2}$, or even many rational numbers cannot be expressed exactly in this format. They must be approximated. (2) An algorithm must terminate at some point when a sufficient approximation is reached; as a result, only an approximation of quadratic irrational is provided. For these reasons, the comparison of two quadratic irrationals is true only within some precision. In our case, we would like to compare two quadratic irrationals exactly. Thus, we need to find out another representation altogether for quadratic rationals. Our approach is based on the relationship between quadratic irrationals and continued fractions. Indeed, quadratic irrationals can be represented exactly using periodic continued fractions, and this representation is unique. This provides an exact method because it is possible to employs only integers to represent such continuing fractions, and to compare them we can avoid numerical errors. In this demo, we show that the exact comparison of quadratic irrationals by using continued fractions is efficient and flexible, and that using only limited precision can lead to errors and imprecisions on actual examples.

Abstract:
We present an image processing framework centered on the Generic Programming paradigm in which an algorithm on the paper can be turned into a single code, written once and usable with various input types. The core of this project is a generic C++ library, Milena, which is part of a Free Software image processing platform, Olena. Milena can be used to implement algorithms on various data structures (subsets of Zn, graphs, cubical and simplicial complexes) and can be extended to support more data structures. We demonstrate the effectiveness of our approach by applying morphological and discrete geometry operators to various image types.

Abstract:
Component-trees associate to a discrete grey-level image a descriptive data structure induced by the inclusion relation between the binary components obtained at successive level-sets. This demonstration presents a software that performs an interactive segmentation of an image based on the concept of component-trees. The method is based on the extraction of a subset of the component-tree of an image enabling to fit at best a given binary target (manual marker) selected interactively in the image.



Outline of the method:

• [Step 1.] Interactive drawing of marker set.
• [Step 2.] Automatic computation of component-tree.
• [Step 3.] Interactive choice of $\alpha$ parameter, whiche defines the distance between marker set and component-tree nodes.
• [Step 4.] To refine the result: go to Step 1.

Abstract:
Since three years, I am using the software Sage to visualize and to do research in Discrete Geometry. Sage is great for its capacity of viewing objects in 2d (Matplotlib Python Library), 3d (Jmol, Tachyon and other 3d viewers) as well as its strong link with latex (the SageTex package). The code I developed allows to represent discrete planes, discrete lines and polyominoes with an approach based on combinatorics on words. For example, each figure of the paper "An Arithmetic and Combinatorial Approach to three-dimensional Discrete Lines" accepted in DGCI 2011 was generated using Sage code. The demonstration will give an idea of what can be done in Sage about Discrete Geometry. Sage is a free open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based interface. Its mission is to create a viable free open source alternative to Magma, Maple, Mathematica and Matlab. http://sagemath.org

Abstract:
This demonstration presents a method of circular arc reconstruction given from a maximal Hausdorff error between the digital shape and its reconstruction. The method exploits the recent curvature estimators and the proposed algorithm approximate a digital shape with as few arcs as possible at a given scale, specified by a maximal admissible Hausdorff distance. We show the potential of our reconstruction method with numerous experiments and we also compare our results with some recent promising approaches. Last, all these algorithms are available online for comparisons on arbitrary shapes.

Abstract:
Blurred segments were introduced in discrete geometry to address possible noise along discrete contours. The noise is not really detected but is rather canceled out by thickening digital straight segments. The thickness is tuned by a user and set globally for the contour, which requires both supervision and non-adaptive contour processing. To overcome this issue, we propose an original strategy to detect locally both the amount of noise and the meaningful scales of each point of a digital contour. Based on the asymptotic properties of maximal segments, it also detects curved and flat parts of the contour. From a given maximal observation scale, the proposed approach does not require any parameter tuning and is easy to implement. This demonstration presents the detection of the meaningful scale through a on line demonstration website allowing to perform extraction on any gray level image.

Abstract:
Given a digital curve and a maximum error, we propose an algorithm that computes a simplification of the curve such that the Fréchet distance between the original and the simplified curve is less than the error. Contrary to other classical metrics like L norms or Hausdorff distance, the Fréchet distance does not consider the curves as sets of points but takes into account the course of the curves. As a result, it nicely measures the similarity between two curves.
The algorithm uses an approximation of the Fréchet distance, but a guarantee over the quality of the simplification is proved. The algorithm is greedy and simply consists in defining shortcuts such that the distance between the shortcut and the curve is lower than the error. The approximation is based on the computation of two quantities: the width of the curve in the direction of the shortcut, and the length of the backpathes in this direction (see fig.1 (a)).
Even if the theoretical complexity of the algorithm is in O(n log(n)), experiments show a linear behaviour in practice. This demonstration is twofold: we propose a library written in C++ which implements the algorithm (see fig.2), and we also present an ipelet of this algorithm (to be used with the IPE drawing editor, see fig.1 (b)).

(a)	(b)
Fig 1. (a) Illustration of the width and backpath length used in the approximated Fréchet distance. (b) A digital curve (red), its simplification with the approximated Fréchet distance (green) and its simplification using the width parameter only (blue).

(a)	(b)
Fig 2. Result of the simplification algorithm on Plants images with an error equal to 6.

Abstract:
This demonstration presents a denoising and smoothing transform of two-dimensional discrete shapes. The transform consists of three steps: at first, a discrete contour analysis is performed. For each pixel of the shape contour, a meaningful scale (size) corresponding to the local nature on the contour is identified (see Demonstration 10). This scale is then used in the second step of the transform, as a scale parameter in an adaptive pixel size reconstruction. Finally, a digitization of the Euclidean reconstructed contour forms the last step of the proposed transform. This transform combines an adaptive denoising and a smoothing effect. We show with numerous experiments that this transform handles nicely most types of noise that may affect discrete shapes.

Abstract:
For pedagogical and artistic use, I have developed, together with Bilal Piot, a series of image filters that are applied in a real time pipeline fed by a webcam. The filters are based on mathematical concepts and help demonstrate notions like complex analytic functions, radius of convergence of a series, vector fields, ordinary differential equations, geometry of surfaces, Fourier transform, anamorphosis and tilings.

Abstract:

Morph-M is an image processing library implemented on C++, following the principles of generic programming. This library contains most of the operators offered by mathematical morphology, from basic operations, such as dilations and erosions, up to the most powerful operators, such as the hierarchical watershed. The library also contains more classical functions of image processing.

We present a simple graphical user interface dedicated to X-ray microtomographic images. Based on Morph-M, this software uses a graph-based version of the stochastic watershed to achieve a content-driven unsupervised segmentation.

The stochastic watershed segmentation was first introduced by Angulo and Jeulin in [1]. The approach is based on using a large number of realizations of random markers to build a probability density function (pdf) of contours, starting from a standard watershed algorithm producing oversegmentations. The stochastic watershed was proved to be efficient for unsupervised segmentation [2]. The two parameters used for its construction are K, the numbers of random markers used in each realization, and R, the numbers of realizations.

By construction, the pdf converges when increasing R. The parameter K needs to be proportional to the numbers of desired regions in the segmented image. Therefore, in the case of granular materials, K needs to be proportional to the number of grains contained in the image, that can be automatically estimated. In [2], the authors use the covariance for this estimation, deduced from the average radius of the grains, and a Boolean model assumption.

[1] Angulo, J., Jeulin, D.: Stochastic watershed segmentation. Proceedings of ISMM'2007, 8th International Symposium on Mathematical Morphology.
[2] Faessel, M., Jeulin, D.: Segmentation of 3D microtomographic images of granular materials with the stochastic watershed. Journal of Microscopy, Volume 239, Issue 1, 2010.