Fast implementation of completely and incompletely specified Boolean functions used in 2D binary image processing
by
C. J. Gau
Queens College, The City University of New York
Coauthors: T. Y. Kong

2D binary image processing algorithms frequently require the computation, for a pixel p, of some Boolean function of the values of a few pixels near p (e.g., the pixels in p's 8-neighborhood). For any such Boolean function over a given probability distribution on the space of its possible argument values, we present a method of generating a C implementation of the function that is, in a sense, optimally efficient. We then discuss a possible extension of this work to incompletely specified Boolean functions. The efficiency of the implementations obtained using our methods can be regarded as a measure of the complexity of the Boolean functions being implemented. Robert and Malandain have done related work. However, they only considered function implementations that can be represented as ordered binary decision diagrams --i.e., implementations that evaluate the input arguments in the same order regardless of their values. Keywords: Boolean function, incompletely specified Boolean function, probability distribution, binary decision diagram, optimally efficient implementation and digital topology

Date received: July 23, 1999

Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cacl-98.