Affiliations: Texas Instruments Pvt. Ltd., Bangalore – 560 017,
India. E-mail: [email protected] | Indian Statistical Institute, 203, B. T. Road,
Calcutta – 700 108, India. E-mail: {bhargab,malay}@isical.ac.in | Indian Institute of Technology, Kharagpur – 721 302,
India. E-mail: [email protected] | Avisere, Chandler, AZ 85226, USA.
E-mail: [email protected]
Abstract: Euler number is a fundamental topological feature of an image. The
efficiency of computation of topological features of an image is critical for
many digital imaging applications such as image matching, database retrieval,
and computer vision that require real time response. In this paper, a novel
algorithm for computing the Euler number of a binary image based on
divide-andconquer paradigm, is proposed, which outperforms significantly the
conventional techniques used in image processing tools. The algorithm can be
easily parallelized for computing the Euler number of an N × N
image in O(N) time, with O(N) processors. Using a simple architecture, the
proposed method can be implemented as a special purpose VLSI chip to be used as
a co-processor.
Keywords: Binary image, digital imaging, Euler number, VLSI
