Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/4890
標題: 二維連通物件演算法之研究
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.
URI: http://hdl.handle.net/11455/4890
其他識別: U0005-1507201314122100
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-1507201314122100
Appears in Collections:通訊工程研究所

文件中的檔案:

取得全文請前往華藝線上圖書館



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