臺灣博碩士論文加值系統

為了使連通區域標記更有效率，本論文提出一種新的基於長度編碼之連通區
域標記演算法，此方法在搜尋連通區域時，只需單向搜尋，改進原方法在搜尋連
通區域時，需要雙向搜尋，減少總搜尋次數。在搜尋連通區域過程中，將有連通
的區域，利用鏈結串列(Linked List)結構串起，當要提取物件時，只需讀取物件
串列，即可將物件提取出。實驗結果證明，本論文將搜尋方向改為單向搜尋，減
少搜尋次數，進而提高連通區域標記的效率。

In order to improve the efficiency of connected components labeling, this paper presents a new connected components labeling method by unidirectional run-length table searching. Instead of searching the run-length table up and down, this method only needs to search the table in one direction. The number of run-length code searching in the labeling algorithm is reduced with our method, thus, our method increases the efficiency of connected components labeling. Also in our method the run-length code of each connected components are stored as a linked list. When extracting the blobs, it only need to read the linked list of each blobs. The result of experiments demonstrates that our method reduces the total searching times, compared with the previous algorithm.

摘要............................................I
Abstract.......................................II
目錄...........................................III
圖目錄..........................................V
表目錄..........................................VI
第1章 緒論....................................1
1.1 研究動機與目的...........................1
1.2 相關工作與研究方法 ........................1
1.3 論文架構 ................................4
第2章 研究背景知識.............................5
2.1 連通類型.................................5
2.1.1 4-連通..................................5
2.1.2 8-連通..................................6
2.2 長度編碼(Run-Length Code)................6
2.3 長度編碼表(Run-Length Table).............7
2.3.1 長度編碼表中長度編碼連通特性...............8
第3章 Yunfeng演算法簡介 .......................10
3.1 Yunfeng演算法 .......................10
3.1.1 長度編碼資料結構 .......................10
3.1.2 演算法步驟 .......................11
3.1.3 長度編碼搜尋方向 .......................12
3.2 演算法模擬 .......................14
3.3 本論文之目的 .......................18
第4章 單向長度編碼表之連通區域標記演算法 .......19
4.1 資料結構定義說明 .......................19
4.1.1 RunLength資料結構 ...............19
4.1.2 Node資料結構 .......................20
4.2 長度編碼表(RunLength Table).............20
4.3 參數定義說明 .......................21
4.3.1 HeadTable .......................21
4.3.2 TailTable .......................22
4.4 Node連通特性 .......................22
4.5 搜尋方向 ...............................23
4.6 演算法介紹 .......................23
4.7 演算法模擬 .......................26
4.8 演算法效能分析 .......................32
第5章 實驗結果 ...............................36
5.1 實驗環境 ...............................36
5.2 實驗一 ...............................36
5.2.1 測量執行時間的方式 .......................37
5.3 實驗二 ...............................40
5.4 實驗三 ...............................41
5.4.1 實驗圖片 ...............................41
5.4.2 實驗結果 ...............................42
第6章 結論 ...............................44
參考文獻 .......................................45

[1]R.M. Haralick, “Some Neighborhood Operations,” In Real Time/Parallel Computing Image Analysis, New York, Plenum Press, pp. 11-35, 1981.
[2]A. Hashizume and et al., “An Algorithm Of Automated RBC Classification And its Evaluation,” Bio Medical Engineering, Vol. 28, No 1, pp. 25-32, 1990.
[3]L. He, Y. Chao and K. Suzuki, “A Linear-Time Two-Scan Labeling Algorithm,” IEEE, International Conference on Image Processing (ICIP), pp.V-241-V-244, Antonio, Texas, USA, 2007.
[4]A. Rosenfeld and J. L. Pfalts, “Sequential Operations In Digital Picture Processing,” J. ACM, Vol. 13, No. 4, pp. 471–494, 1966.
[5]A. Rosenfeld and A. C. Kak, “Digital Picture Processing, 2^nd San Diego,” CA: Academic, Vol.2, 1982.
[6]L. He, Y. Chao, K. Suzuki and H. Itoh, “A Run-Based Two-Scan Labeling Algoritm,” IEEE, Transaction On Image Processing, Vol.17, No. 5, pp. 749-756 , 2008.
[7]G. Yunfeng, W. Feiyang and H. Xizotian, “Connected Components Labeling Algorithm Based On Run-length Table Searching,” IEEE, Computer Science & Education, pp. 22-24, 2014.
[8]F. Chang, C. J. Chen and C. J. Lu, “A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique,” Comput. Vis. Image Understand., Vol.93, pp. 206–220, 2004.
[9]G. L. Zhang, Y. X. Chen, W. X. Cao and et al., “A Connected Components Labeling Algorithm Using the Run-length Code,” J. Journal of Huazhong University of Science and Technology, Vol.22, pp. 11-14 , 1994.
[10]W. Q. Yun and T. W. Zhang, “A Counter Method For The Image of Blood Cell,” J.Computer Application And Software, Vol.5, pp. 61-64, 2000.
[11]S. S. Zhang, “A Method of Detecting Connected Components of Binnary Image Based On Transmission Label of Wire, ”J.Computer Research and Development, Vol.31, pp.41-54, 1994.
[12]G. S. Liu, J. W. Lv, J. G. Xu and et al., “A New Algorithm For Fast Pixel Labeling in Binary Images,” J. Computer Engineer and Applications, Vol.38, pp. 57-59, 2002.
[13]T.Jiang, M.Qiu, J. Chen and et al., “A Connected Components Labeling Algorithm In Grid-based Clustering,” Proc. of the 1^stInternational Workshop on Databased Technology and Applications, pp. 213-216, 2009.