Please use this identifier to cite or link to this item:
標題: 二維連通物件演算法之研究
The Study of 2-D Connected Component Algorithm
作者: 唐偉訓
Tang, Wei-Shin
關鍵字: 連通物件標記;Connected-component labeling;鏈結串列;linked list
出版社: 通訊工程研究所
引用: [1] R. Haralick and L. Shapiro, Computer and Robot Vision (Volume I). Reading, MA: Addison-Wesley, 1992. [2] R. Gonzalez and R.Woods, Digital Image Processing, 3rd ed. Upper Saddle River, NJ: Prentice-Hall, 2008. [3] 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. [4] A. Rosenfeld and J. Pfaltz, “Sequential operations in digital picture processing,” J. ACM, vol. 13, no. 4, pp. 471–494, 1966. [5] 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. [6] K. Wu, E. Otoo, and A. Shoshani, “Optimizing connected component labeling algorithms,” in Proc. SPIE Conf. Med. Imag., 2005, vol. 5747, pp. 1965–1976. [7] 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. [8] 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. [9] 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. [10] 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. [11] 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. [12] 陳惠貞 著作,資料結構C語言實作,碁峰資訊,初版,2008。
連通物件標記(Connected-Component Labeling)在影像處理中是一個基本的演算法,在二元影像中像素分為前景像素與背景像素,連通物件標記的主要目的是將相連的前景像素合併成為一個區域,將前景像素給定標記,當中不同區域所給定的標記值都不相同。

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.
其他識別: U0005-1507201314122100
Appears in Collections:通訊工程研究所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.