Discrete geometry for image processing

Marchand-Maillet, Stéphane
Book chapter N°3 in "Advances in imaging and electron physics", Volume 106, Academic Press

Image processing operations typically involve processing of data indiscrete form. Information given by such data is mostly recovered via the study of inter-relationships between discrete points (i.e. pixels). There is therefore a need for developing a context in which concepts used are kept consistent with this kind of data. In this paper, we summarise and extend results known in discrete geometry from the construction of a discrete topological concept to the characterisation of geometrical properties of discrete sets of points. The context of binary image processing is taken as a support for illustrating this study. Emphasis is placed on characterising straightness and convexity is discrete spaces. This is done via the definition of discrete distances which are shown to be close to well-known concepts in graph theory. An extended neighbourhood space is also constructed and shown to provide us with more flexibility and compactness than classically used neighbourhood spaces while preserving the possibility of characterising analytically the main geometrical properties of discrete points. The study developed in this paper can form the basis for different extensions, both regarding the richness of the neighbourhood used and the quantity of information available at each pixel location.

Data Science
Eurecom Ref:
© Academic Press. Personal use of this material is permitted. The definitive version of this paper was published in Book chapter N°3 in "Advances in imaging and electron physics", Volume 106, Academic Press and is available at :

PERMALINK : https://www.eurecom.fr/publication/172