Please use this identifier to cite or link to this item:
The Study of 2-D Connected Component Algorithm
|引用:|| R. Haralick and L. Shapiro, Computer and Robot Vision (Volume I). Reading, MA: Addison-Wesley, 1992.  R. Gonzalez and R.Woods, Digital Image Processing, 3rd ed. Upper Saddle River, NJ: Prentice-Hall, 2008.  L. He, Y. Chao, and K. Suzuki, “A run-based two-scan labeling algorithm,” IEEE Trans. Image Process., vol. 17, no. 5, pp. 749–756, 2008.  A. Rosenfeld and J. Pfaltz, “Sequential operations in digital picture processing,” J. ACM, vol. 13, no. 4, pp. 471–494, 1966.  C. Fiorio and J. Gustedt, “Two linear time union-find strategies for image processing,” Theor. Comput. Sci., vol. 154, no. 2, pp. 165–181, 1996.  K. Wu, E. Otoo, and A. Shoshani, “Optimizing connected component labeling algorithms,” in Proc. SPIE Conf. Med. Imag., 2005, vol. 5747, pp. 1965–1976.  R. Lumia, L. Shapiro, and O. Zuniga, “A new connected components algorithm for virtual memory computers,” Comput. Vis. Graph. Image Process., vol. 22, no. 2, pp. 287–300, 1983.  M. Dillencourt, H. Samet, and M. Tamminen, “A general approach to connected-component labeling for arbitrary image representations,” J. ACM, vol. 39, no. 2, pp. 253–280, 1992.  K. Suzuki, I. Horiba, and N. Sugie, “Linear-time connected-component labeling based on sequential local operations,” Comput. Vis. Image Understand.,vol. 89, no. 1, pp. 1–23, 2003.  Y. Shima, T. Murakami, M. Koga, H. Yashiro, and H. Fujisawa, “A high speed algorithm for propagation-type labeling based on block sorting of runs in binary images,” in Proc. 10th Int. Conf. Pattern Recognit., 1990, vol. 90, pp. 655–658.  J. De Bock, and W. Philips, “Fast and Memory Efficient 2-D Connected Components Using Linked Lists of Line Segments,” IEEE Trans. Image Process., vol. 19, no. 12, pp. 3222–3231, 2010.  陳惠貞 著作，資料結構C語言實作，碁峰資訊，初版，2008。|
Connected-component labeling is a fundamental algorithm in image processing. In a binary image which has been classified as foreground and background pixels, the purpose of the connected-component labeling is to find all the connected regions of the foreground pixels and give distinct labels to each of the different connected regions. Generally, we can classify the algorithm into two types according to its memory access strategy: regular access and irregular access. For the type of irregular access, the propagation of label causes unbounded access to the image. This causes low execution efficiency. For the type of regular access, it usually uses two or more raster scan to circumvent the unbounded access problem. The connected-component labeling method proposed in this thesis uses only one raster scan and can be classified as a regular access type. We use a single-direction linked list to store the line segments in each connected region. To prevent unbounded access to the line segments, three additional pointers are introduced to separate the connected region into three parts. These pointers are then used to merge connected regions and prevent potential unbounded access during the merging process. From experimental results, we can see that the execution time of the algorithm depends mainly on image size and the number of line segments. The effect of region merging is significantly reduced. This proves that the new algorithm can effectively reduce the execution time of connected-component labeling.
|Appears in Collections:||通訊工程研究所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.