›› 2013,Vol. 28 ›› Issue (3): 468-478.doi: 10.1007/s11390-013-1348-y

所属专题： Computer Graphics and Multimedia

• Special Section on Selected Paper from NPC 2011 • 上一篇    下一篇

一种用于连通域标记,孔洞标记和计算欧拉数的算法

Li-Feng He1,2 (何立风), Senior Member, IEEE, Yu-Yan Chao1,3 (巢宇燕) and Kenji Suzuki4, Senior Member, IEEE   

  1. 1. Artificial Intelligence Institute, College of Electrical and Information Engineering, Shaanxi University of Science and Technology, Xi'an 710021, China;
    2. Faculty of Information Science and Technology, Aichi Prefectural University, Aichi 4801198, Japan;
    3. Faculty of Environment, Information and Business, Nagoya Sangyo University, Aichi 4888711, Japan;
    4. Department of Radiology, The University of Chicago, IL 60637, U.S.A.
  • 收稿日期:2012-03-07 修回日期:2013-01-07 出版日期:2013-05-05 发布日期:2013-05-05
  • 作者简介:Li-Feng He received his B.E. degree from the Northwest Institute of Light Industry, Xianyang, China, in 1982, the second B.E. degree from Xi'an Jiaotong University, China, in 1986, and the M.S. and the Ph.D. degrees in artificial intelligence and computer science from Nagoya Institute of Technology, Japan, in 1994 and 1997, respectively. From 1998 to 2011, he was an associate professor at the Aichi Prefectural University, Japan. From 2006 to 2007, he worked in the University of Chicago (USA) as a research associate. He is currently a professor, director of Artificial Intelligence Institute, and academic dean of the College of Electrical & Information Engineering at Shannxi University of Science and Technology, China, and a professor at Aichi Prefectural University, Japan. His research interests include intelligent image processing, computer vision, automated reasoning, and artificial intelligence. He is a senior member of IEEE.
  • 基金资助:

    This work was supported in part by the Grant-in-Aid for Scientific Research (C) of the Ministry of Education, Science, Sports and Culture of Japan under Grant No. 23500222.

An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing

Li-Feng He1,2 (何立风), Senior Member, IEEE, Yu-Yan Chao1,3 (巢宇燕), and Kenji Suzuki4, Senior Member, IEEE   

  1. 1. Artificial Intelligence Institute, College of Electrical and Information Engineering, Shaanxi University of Science and Technology, Xi'an 710021, China;
    2. Faculty of Information Science and Technology, Aichi Prefectural University, Aichi 4801198, Japan;
    3. Faculty of Environment, Information and Business, Nagoya Sangyo University, Aichi 4888711, Japan;
    4. Department of Radiology, The University of Chicago, IL 60637, U.S.A.
  • Received:2012-03-07 Revised:2013-01-07 Online:2013-05-05 Published:2013-05-05
  • Contact: 10.1007/s11390-013-1348-y
  • Supported by:

    This work was supported in part by the Grant-in-Aid for Scientific Research (C) of the Ministry of Education, Science, Sports and Culture of Japan under Grant No. 23500222.

PDF (PC)

2124

二值图像的,孔洞标记和欧拉数计算这些图像分析、模式识别和计算机(机器)视觉等领域不可或缺的处理通常是独立地进行的。本论文提出了一个利用共同的数据结构可以同时标记连通域和孔洞的两次扫描算法。运用本论文提出的算法,可以计算连通域和孔洞的数目和面积以及图像的欧拉数。本论文的算法的原理非常简单。实验结果显示对于各种类型的图像,在需要同时进行连通域标记和欧拉数计算的场合,本论文的算法比传统算法的效率要好得多。

Abstract: Labeling connected components and holes and computing the Euler number in a binary image are necessary for image analysis, pattern recognition, and computer (robot) vision, and are usually made independently of each other in conventional methods. This paper proposes a two-scan algorithm for labeling connected components and holes simultaneously in a binary image by use of the same data structure. With our algorithm, besides labeling, we can also easily calculate the number and the area of connected components and holes, as well as the Euler number. Our method is very simple in principle, and experimental results demonstrate that our method is much more efficient than conventional methods for various kinds of images in cases where both labeling and Euler number computing are necessary.

[1] Gonzalez R C, Woods R E. Digital Image Processing (3rd edition). Addison-Wesley, 1992.

[2] Ronsen C, Denjiver P A. Connected Components in Binary Images: The Detection Problem. New York, USA: John Wiley & Sons. Inc., 1984.

[3] Hashizume A, Suzuki R, Yokouchi H et al. An algorithm of automated RBC classification and its evaluation. Bio. Medical Engineering, 1990, 28(1): 25-32. (In Japanese)

[4] Srihari S N. Document image understanding. In Proc. ACM Fall Joint Computer Conference, November 1986, pp.87-95.

[5] Rosin P L, Ellis T. Image di?erence threshold strategies and shadow detection. In Proc. British Machine Vision Conference, September 1995, pp.347-356.

[6] Nayar S K, Bolle R M. Reflectance-based object recognition. International Journal of Computer Vision, 1996, 17 (3): 219240.

[7] Horn B K P. Robot Vision. New York: McGraw-Hill Higher Education, 1986, pp.73-77.

[8] Lumia R, Shapiro L, Zungia O. A new connected components algorithm for virtual memory computers. Comput. Vision, Graphics and Image Processing, 1983, 22(2): 287-300.

[9] Rosenfeld A, Pfalts J L. Sequential operations in digital picture processing. Journal of ACM, 1996, 13(4): 471-494.

[10] Rosenfeld A, Kak A C. Digital Picture Processing (2nd edition), Vol. 2. San Diego, USA: Academic Press, 1982.

[11] Naoi S. High-speed labeling method using adaptive variable window size for character shape feature. In Proc. IEEE Asian Conf. Computer Vision, December 1995, pp.408-411.

[12] Suzuki K, Horiba I, Sugie N. Linear-time connectedcomponent labeling based on sequential local operations. Computer Vision and Image Understanding, 2003, 89(1): 123.

[13] Wu K, Otoo E, Suzuki K. Optimizing two-pass connectedcomponent labeling algorithms. Pattern Analysis & Applications, 2009, 12(2): 117-135.

[14] He L, Chao Y, Suzuki K, Wu K. Fast connected-component labeling. Pattern Recognition, 2009, 42(9): 1977-1987.

[15] He L, Chao Y, Suzuki K. An efficient first-scan method for label-equivalence-based labeling algorithms. Pattern Recognition Letters, 2010, 31(1): 28-35.

[16] Ballard D H, Brown C M. Computer Vision. Prentice-Hall, 1982.

[17] Chang F, Chen C J, Lu C J. A linear-time component-labeling algorithm using contour tracing technique. Computer Vision and Image Understanding, 2004, 93(2): 206-220.

[18] Hu Q, Qian G, Nowinski W L. Fast connected-component labeling in three-dimensional binary images based on iterative recursion. Computer Vision and Image Understanding, 2005, 99(3): 414-434.

[19] Shima Y, Murakami T, Koga M, Yashiro H, Fujisawa H. A high-speed algorithm for propagation-type labeling based on block sorting of runs in binary images. In Proc. the 10th Int. Conf. Pattern Recognition, June 1990, pp.655-658.

[20] Wolfe C, Nicholas Graham T C, Pape J A. Seeing through the fog: An algorithm for fast and accurate touch detection in optical tabletop surfaces. In Proc. ACM International Conference on Interactive Tabletops and Surfaces, November 2010, pp.73-82.

[21] Abramov A. Kulvicius T, Wörgötter F, Dellen B. Real-time image segmentation on a GPU. In Lecture Notes in Computer Science 6310, Keller R, Kramer D, Weiss J P (eds.), Springer-Verlag, 2011, pp.131-142.

[22] Chen M H, Yan P F. A fast algorithm to calculate the Euler number for binary image. Pattern Recognition Letters, 1988, 8(5): 295-297.

[23] Díaz-De-León S J L, Sossa-Azuela J H. On the computation of the Euler number of a binary object. Pattern Recognition, 1996, 29(3): 471-476.

[24] Di Zenzo S, Cinque L, Levialdi S. Run-based algorithms for binary image analysis and processing. IEEE Transactions on PAMI, 1996, 18(1): 83-89.

[25] Gray S B. Local properties of binary images in two dimensions, IEEE Transactions on Computers, 1971, 20(5): 551561.

[26] Pratt W K. Digital Image Processing. New York: John Wiley & Sons, Inc., 1991, p.633.

[27] Otsu N. A threshold selection method from gray-level histograms. IEEE Trans. Syst., Man and Cybernet, 1979, 9(1): 62-66.

[28] Dey S, Bhattacharya B B, Kundu M K, Acharya T. A fast algorithm for computing the Euler number of an image and its VLSI implementation. In Proc. the 13th Int. Conf. VLSI Design, January 2000, pp.330-335.

[29] Ito Y, Nakano K. Optimized component labeling algorithm for using in medium sized FPGAs. In Proc. the 9th Int. Conf. Parallel and Distributed Computing, Applications and Technologies, Dec. 2008, pp.171-176.

[30] Udupa J K, Ajjanagadde V G. Boundary and object labeling in three-dimensional images. Comput. Vision, Graphics, and Image Processing, 1990, 51 (3): 355-369.

[31] He L, Chao Y, Suzuki K. Two efficient label-equivalence-based connected-component labeling algorithms for 3-dimensional binary images. IEEE Transactions on Image Processing, 2011, 20(8): 2122-2134.

[32] Niknam M, Thulasiraman P, Camorlinga S. A parallel algorithm for connected component labeling of gray-scale images on homogeneous multicore architectures. Journal of Physics: Conference Series 256, 2010, 012010: 1-7.

[33] Dey S, Bhattacharya B, Kundu M, Bishnu A, Acharya T. A co-processor for computing the Euler number of a binary image using divide-and-conquer strategy. Fundamental Informaticae, 2007, 76(1/2): 75-89.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] 陈世华;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] 高庆狮; 张祥; 杨树范; 陈树清;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] 陈肇雄; 高庆狮;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] 黄河燕;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] 闵应骅; 韩智德;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] 唐同诰; 招兆铿;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] 闵应骅;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] 朱鸿;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] 李明慧;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：