數位影像處理研究的重要目標之一是為圖像處理領域發展更有效率的運算方法。近年來，形態學的圖像處理技術受到了許多關注，因為它包含圖像數據的簡化、圖像對基本形狀特徵的保存及消除不必要的內容，更重要的是，可以基於基本的形態學運算來建構複雜且有效的圖像處理任務。儘管其理論非常簡單、易於理解及實現，但往往存在運算速度慢的缺點，不經改善難以實際使用。
在本論文中，我們提出了一種Run-Based的圖像表示法應用在二階形態學的運算當中，我們定義一個run為：在每一行(colomn)中連續像素值為1的像素序列，用來表示目標圖像以及結構元素，並實現了基於此表示法進行膨脹、侵蝕運算的技術和算法。 
原始方法的膨脹、侵蝕運算時間複雜度皆為O(N^2 M^2)；而本文所提出的Run-Based表示法時間複雜度為O(NM(log(M)))和O(NM)。實驗結果表明，使用本文所提出的方法可以加快運算的時間。

One of the important goals of digital image processing research is to develop robust and efficient algorithms for many image processing tasks. Over recent years, mathematical morphological image processing has received a lot of attention since it includes the simplification of the image data, the preservation of essential shape characteristics for image objects and the elimination of irrelevancies. More importantly, complex and useful image tasks can be constructed based on the basic morphological image operations. Although its theory is very simple, easy to understand and implement, it often has the disadvantage of slow operation speed. It is difficult to use it without improvement.
We propose a Run-Based image representation applied to binary morphology operations. Run-Based image representation is an alternative way of representing a binary image and the structure element using a run, which is a sequence of ‘1’ pixels on the columns. In this paper, techniques and algorithms for performing morphological image processing based on the proposed approach are presented.
The time complexity of the dilation and erosion calculations of the original algorithm is O(N^2 M^2); and the time complexity of the dilation and erosion calculations proposed in this paper is O(NM(log(M)) and O(NM). Experimental results demonstrate that a speed up in computation time can be obtained using the proposed method.

第一章 緒論 1
1.1 研究動機與目的 1
1.2 論文架構 3
第二章 相關研究 4
2.1 二階圖像 4
2.2 數學形態學 6
2.3 形態學的圖像處理技術 7
第三章 研究方法 12
3.1 Run-based的二階圖像表示法 12
3.2 兩個runs間的空間關係 15
3.3 Run-Based的膨脹運算 17
3.4 Run-Based的侵蝕運算 23
3.5 範例說明 30
3.5.1 膨脹運算 30
3.5.2 侵蝕運算 33
第四章 實驗與分析 37
4.1 時間複雜度比較 37
4.1.1 Run-Based的膨脹運算時間複雜度 37
4.1.2 Run-Based的侵蝕運算時間複雜度 38
4.2 實驗 39
第五章 結論 45
參考文獻 46



表目錄
表 3-1：13種空間關係類型變化表 15
表 3-2：圖3-10範例圖片膨脹後之runs集合 31
表 3-3：表 3 2排序後之runs集合 32
表 3-4：表 3 3進行合併運算後之runs集合 32
表 3-5：圖 3 12範例圖片侵蝕後之runs集合 34
表 3-6：表 3 5在每一行上產生的runs 35
表 3-7：表 3 6進行交集運算後之runs集合 35
表 4-1：各組實驗所需執行時間 44



圖目錄
圖 2-1：二階圖像於X、Y軸上的空間關係 5
圖 2-2：常見的結構元素 8
圖 2-3：膨脹運算示意圖 9
圖 2-4：侵蝕運算示意圖 9
圖 3-1：範例二階圖像X 13
圖 3-2：範例結構元素Q 14
圖 3-3：13種空間關係類型示意圖 16
圖 3-4：膨脹運算中runs的重疊情況範例圖 19
圖 3-5：8種空間關係類型 20
圖 3-6：8種空間關係類型與其合併之結果 23
圖 3-7：交集運算示意圖 26
圖 3-8：交集運算示意圖 28
圖 3-9：13種空間關係類型與其交集之結果 29
圖 3-10：範例圖片 30
圖 3-11：圖 3 10範例圖片膨脹後之結果 32
圖 3-12：範例圖片 33
圖 3-13：圖 3 12範例圖片侵蝕後之結果 36
圖 4-1：實驗二階圖像 40
圖 4-2：實驗結構元素 40
圖 4-3：膨脹運算結果 41
圖 4-4：侵蝕運算結果 42
圖 4-5：開運算、閉運算結果 43

[1].	Bovik, A. C. (2009). In Bovik A. (Ed.), Chapter 4 - basic binary image processing.
[2].	Guo, S., Zhou, W., Wen, H., & Liang, M. (2016). Fast binary image set operations on a run-based representation. Pattern Recognition Letters, 80, 216-223. 
[3].	Haas, A., Matheron, G., & Serra, J. (1967). Morphologie mathématique et granulométries en place. In Annales des mines(Vol. 11, No. 736-753, pp. 7-3).
[4].	Kim, S., Lee, J., & Kim, J. (1988). A new chain-coding algorithm for binary images using run-length codes.’’Computer Vision, Graphics, and Image Processing,’’41(1), 114-128.
[5].	Liang, J., Piper, J., & Tang, J. Y. (1989). Erosion and dilation of binary images by arbitrary structuring elements using interval coding. Pattern Recognition Letters, 9(3), 201-209. 
[6].	Lotufo, R. A., Audigier, R., Saúde, A. V., & Machado, R. C. (2008). In Wu Q., Merchant F. A. and Castleman K. R.(Eds.), Chapter 8 - morphological image processing.
[7].	Matheron, G. (1975). Random sets and integral geometry Wiley.
[8].	R. M. Haralick, S. R. Sternberg, & X. Zhuang. (1987). Image analysis using mathematical morphology. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(4), 532-550. 
[9].	Sánchez-Cruz, H., Bribiesca, E., & Rodrìguez-Dagnino, R. M. (2007). Efficiency of chain codes to represent binary objects. Pattern Recognition, 40(6), 1660-1674. 
[10].	Samet, H. (1984). The quadtree and related hierarchical data structures. ACM Computing Surveys (CSUR), 16(2), 187-260.
[11].	Serra, J. P. (1982). Image analysis and mathematical morphology Academic Press.
[12].	Sonka, M., Hlavac, V., & Boyle, R.Image processing, analysis, and machine vision. 
[13].	Tsai, Y., & Chung, K. (1999). Some image operations on S-tree-related spatial data structures.
[14].	Wu, J., & Chung, K. (1997). A new binary image representation: Logicodes. 
[15].	Yu, B., Lin, X., & Wu, Y. (1991). The tree representation of the graph used in binary image processing.