A Co-processor for Computing the Euler Number of a Binary Image using Divide-and-Conquer Strategy

• Autorzy: Dey S. , Bhattacharya Bhargab.B. , Kundu M.K. , Bishnu A. , Acharya T.
• Języki publikacji: EN

Abstrakty

EN

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-and-conquer 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.

Słowa kluczowe

EN

binary image; digital imaging; Euler number; VLSI

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 1-2
• Strony: 75--89
• Opis fizyczny: bibliogr. 13 poz., tab., wykr.

Twórcy

autor

Dey S.

autor

Bhattacharya Bhargab.B.

autor

Kundu M.K.

autor

Bishnu A.

autor

Acharya T.

• Indian Statistical Institute, 203 B.T. Road, Calcutta, 700 108 India,

Bibliografia

• [1] Gonzalez R.C. and Woods R.F. Digital Image Processing. Addison-Wesley, Reading, Massachusetts, 1993, pp. 504-506.
• [2] Greanis E.C. et al., "The Recognition of Handwritten Numerals by Contour Analysis", IBM J. Res. Dev., Vol. 7, No. 1, Jan. 1963, pp.14-21.
• [3] Dyer C. R. "Computing the Euler number of an Image from its Quadtree", Comput. Graphics Image Processing, Vol. 13, No. 3, pp.270-276, July 1980.
• [4] Samet H. and TamminenM. "Computing Geometric Properties of Images Represented by Linear Quadtrees", IEEE Trans. Pattern Anal. Mach. Intell., Vol. PAMI-7, No. 2, March 1985.
• [5] Gray S.B. "Local Properties of Binary Images in Two Dimension", IEEE Trans. Computers, Vol. 20, no. 5, May 1971, pp. 551-561.
• [6] Minsky M. and Papert S. Perceptrons. M. I. T. Press, Cambridge, USA, 1968.
• [7] Pratt W.K. Digital Image Processing. John Wiley & Sons., 1978.
• [8] Thompson C.M. and Shure L. Image Processing Toolbox. The Math Works Inc.
• [9] Thompson C.D. A Complexity Theory for VLSI. Ph.D. dissertation, Dept. of Comp. Sc., CMU, Aug. 1990.
• [10] Dey S. VLSI for Image Processing. M.Tech. (CS) Thesis, Indian Statistical Institute, Calcutta 700 035, India, July 1999.
• [11] Jain A.K. and Vailaya A. "Shape-based Retrieval: A Case Study with Trademark Databases", Pattern Recognition, Vol. 31, No. 9, pp. 1369-1390, 1998.
• [12] Bishnu A., Bhattacharya B.B., Kundu M.K, Murthy C.A., and Acharya T. "A Pipeline Architecture for Computing Euler number of a Binary Image", Journal of Systems Architecture, vol. 51, pp. 470-487, 2005.
• [13] Bishnu A., Bhattacharya B.B., Kundu M.K, Murthy C.A., and Acharya T. "Euler Vector for Search and Retrieval of Gray-Tone Images", IEEE Trans. SMC, Part B, vol. 35, pp. 801-812, Aug., 2005.