Please use this identifier to cite or link to this item:
DC FieldValueLanguage
dc.contributorJan-Ray Liaoen_US
dc.contributor.authorTang, Wei-Shinen_US
dc.identifier.citation[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。en_US
dc.description.abstract連通物件標記(Connected-Component Labeling)在影像處理中是一個基本的演算法,在二元影像中像素分為前景像素與背景像素,連通物件標記的主要目的是將相連的前景像素合併成為一個區域,將前景像素給定標記,當中不同區域所給定的標記值都不相同。 在演算法的類型中分為規則存取類以及不規則存取類,其中不規則存取類的傳播標籤過程中影像的存取是無界的,這會造成執行效率低落,而規則存取類為了解決無界問題大部分的方法都使用了兩次以上的柵狀掃描。 本論文的方法在整張影像的標記過程中只使用一次柵狀掃描,從演算法的類型以及考量存取物件的方式,我們使用單向鏈結串列儲存每塊區域內的線段,在演算法類型中我們的方法是屬於規則存取類型,考慮掃描當中過於龐大的線段存取以及區域連結所造成的無界問題,加入額外的指標來讓每個區域劃分出三個區間,透過指標去改變存取線段的方式,藉此解決無界問題。在實驗結果中我們觀察到執行時間受到影像大小與線段數量最重,區域合併的次數反而影響比較少,證明了掃描區域時所花費的時間能夠有效的減少。zh_TW
dc.description.abstractConnected-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.en_US
dc.description.tableofcontents誌謝 i 摘要 ii Abstract iii 目次 iv 圖目次 v 第一章 緒論 1 1.1 動機與目的 1 1.2 論文架構 2 第二章 背景介紹 3 2.1連通物件標記(Connected-Component Labeling) 3 2.2演算法類型簡介 4 2.2.1規則存取類 4 2.2.2不規則存取類 5 2.3鏈結串列(Linked list) 6 第三章 二維連通物件演算法 8 3.1演算法架構 8 3.2線段連接以及合併 10 3.3程式主體流程 12 3.4確保是有界的行存取(Bounded row access) 13 3.4.1有界的行存取 13 3.4.2實際例子運行 16 第四章 實驗結果與數據 16 4.1實驗環境 24 4.2 實驗結果 24 第五章 結論 33 5.1 結論 33 參考文獻 34zh_TW
dc.subjectConnected-component labelingen_US
dc.subjectlinked listen_US
dc.titleThe Study of 2-D Connected Component Algorithmen_US
dc.typeThesis and Dissertationzh_TW
item.openairetypeThesis and Dissertation-
item.fulltextno fulltext-
Appears in Collections:通訊工程研究所
Show simple item record

Google ScholarTM


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