FAST BINARY IMAGE-PROCESSING USING BINARY DECISION DIAGRAMS

Citation
L. Robert et G. Malandain, FAST BINARY IMAGE-PROCESSING USING BINARY DECISION DIAGRAMS, Computer vision and image understanding (Print), 72(1), 1998, pp. 1-9
Citations number
31
Categorie Soggetti
Computer Science Software Graphycs Programming","Computer Science Software Graphycs Programming
ISSN journal
10773142
Volume
72
Issue
1
Year of publication
1998
Pages
1 - 9
Database
ISI
SICI code
1077-3142(1998)72:1<1:FBIUBD>2.0.ZU;2-G
Abstract
Many classical image processing tasks can be realized as evaluations o f a boolean function over subsets of an image. For instance, the simpl icity 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 pro duce automatically very efficient and compact code for such functions. The total number of operations performed bq a generated function is a t most one test and one branching for each input value (e.g., in the c ase of 3D thinning, 26 tests and branchings). At each stage, the funct ion is guaranteed to examine only the pertinent input data, i.e., the values which affect the result. As an example, we consider the 3D simp licity test in digital topology, and thinning processes. We produce fu nctions much faster than our previously optimized implementations [19, 4] and than ally other implementation we know of. In the case of 3D s implicity test, on average, at each voxel only 8.7 neighboring voxel v alues are examined, (C) 1998 Academic Press.