A new run-based algorithm for Euler number computing
Tóm tắt
The Euler number of a binary image is an important topological feature for many image processing, image analysis, pattern recognition, and computer vision applications. This paper proposes a new run-based Euler number computation algorithm. The conventional run-based algorithm processes rows of the given image one-by-one from top to bottom in a single phase. For each row, it finds the runs in the row and records the start and end locations of each run to compute neighbor runs. In contrast, our algorithm calculates the Euler number of an image in two phases. In the first phase, we process odd rows alternately to find runs and only record its end location. In the second phase, we process each of the remaining even rows to find runs and calculate neighboring runs between the current row and the rows immediately above and below using the recorded run data. Using this method, the number of accesses required to compute the Euler number decreases in almost all cases. Analysis of the time complexity and experimental results demonstrate that our algorithm outperforms conventional Euler number computation algorithms.
Tài liệu tham khảo
Gonzalez RC, Woods RE (2008) Digital image processing. 3rd edn. Pearson Prentice Hall, Upper Saddle River, p 07458
Hashizume A, Suzuki R, Yokouchi H (1990) An algorithm of automated RBC classification and its evaluation. Bio Med Eng 28(1):25–32
Moraru L, Cotoi O, Szendrei F (2011) Euler number: a method for statistical analysis of ancient pottery porosity. Eur J Sci Theol 7(3):99–108
Srihari SN (1986) Document image understanding. In: Proceedings ACM/IEEE Joint Fall Computer Conference, Dallas, pp 87–95
Rosin PL, Ellis T (1995) Image difference threshold strategies and shadow detection. In: Proceedings British Machine Vision Conference, London, England pp 347–356
Nayar SK, Bolle RM (1996) Reflectance-based object recognition. Int J Comput Vis 17(3):219–240
Horn B (1986) Robot vision. McGraw-Hill, New York, pp 73–77
Pogue BW, Mycek MA, Harper D (2000) Image analysis for discrimination of cervical neoplasia. J Biomed Opt 5(1):72–82
Diaz-de-Leon SJL, Sossa-Azuela JH (1996) On the computation of the Euler number of a binary object. Pattern Recogn 29(3):471–476
Gray SB (1971) Local properties of binary images in two dimensions. IEEE Trans Comput 20: 551–561
Thompson CM, Shure L Image processing toolbox. The Math Works Inc., USA
Bishnu A, Bhattachary BB, Kundu MK, Murthy CA, Acharya T (2005) A pipeline architecture for computing the Euler number of a binary image. J Syst Architect 51(8):470–487
He L, Chao Y, Suzuki K (2013) An algorithm for connected-component labeling, hole labeling and Euler number computing. J Comput Sci Technol 28(3):469–479
Chen MH, Yan PF (1988) A fast algorithm to calculate the Euler number for binary images. Pattern Recog Lett 8(5):295–297
Chiavetta F, Gesu V (1993) Parallel computation of the Euler number via connectivity graph. Pattern Recog Lett 14:849–859
Dey S, Bhattacharya BB, Kundu MK, Acharya T (2000) A fast algorithm for computing the Euler number of an image and its VLSI implementation. In: VLSI Design. Thirteenth International Conference on IEEE. Calcutta, India, pp 330–335
Dyer CR (1980) Computing the Euler number of an image from its quadtree. Comput Graphics Image Process 13(3):270–276
Samet H, Tamminen H (1985) Computing geometric properties of images represented by linear quadtrees. IEEE Trans PAMI 7(2):229–240
He L, Chao Y, Suzuki K (2010) An efficient first-scan method for label-equivalence-based labeling algorithms. Pattern Recogn Lett 31(1):28–35
Ohta A (2013) On the derivation of the Euler number based on graph theory. Technical report. Aichi Prefectural University Aichi, Japan. (in Japanese)