Fast Binary Image Processing Using Binary Decision Diagrams

Luc Robert 1 Grégoire Malandain 2
1 ROBOTVIS - Computer Vision and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
2 EPIDAURE - Medical imaging and robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Many classical image processing tasks can be realized as evaluations of a boolean function over subsets of an image. For instance, the simplicity test used in 3D thinning requires examining the 26 neighbors of each voxel and computing a single boolean function of these inputs. In this article, we show how Binary Decision Diagrams can be used to produce automatically very efficient and compact code for such functions. The total number of operations performed by a generated function is at most one test and one branching for each input value (e.g., in the case of 3D thinning, 26 tests and branchings). At each stage, the function is guaranteed to examine only the pertinent input data, i.e., the values which affect the result. As an example, we consider the 2D and 3D simplicity tests in digital topology, and thinning processes. We produce functions much faster than our previously optimized implementations \cite{malandain92,bertrand-al94}, and than any other implementation we know of. In the case of 3D simplicity test, on average, at each voxel only 8.7 neighboring voxel values are examined.
Type de document :
Rapport
RR-3001, INRIA. 1996
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00073695
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:33:06
Dernière modification le : samedi 27 janvier 2018 - 01:31:30
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:55:10

Fichiers

Identifiants

  • HAL Id : inria-00073695, version 1

Collections

Citation

Luc Robert, Grégoire Malandain. Fast Binary Image Processing Using Binary Decision Diagrams. RR-3001, INRIA. 1996. 〈inria-00073695〉

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

789