淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


系統識別號 U0002-2607201802042600
中文論文名稱 一個有效率的二階形態學運算方法
英文論文名稱 An efficient method for binary morphology operations
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 106
學期 2
出版年 107
研究生中文姓名 伍珞琳
研究生英文姓名 Lo-Lin Wu
學號 604630243
學位類別 碩士
語文別 中文
口試日期 2018-05-31
論文頁數 47頁
口試委員 指導教授-梁恩輝
委員-梁恩輝
委員-謝禎冏
委員-廖賀田
中文關鍵字 二階圖像  數學形態學  膨脹  侵蝕 
英文關鍵字 Binary image  Mathematical morphology  Dilation  Erosion 
學科別分類
中文摘要 數位影像處理研究的重要目標之一是為圖像處理領域發展更有效率的運算方法。近年來,形態學的圖像處理技術受到了許多關注,因為它包含圖像數據的簡化、圖像對基本形狀特徵的保存及消除不必要的內容,更重要的是,可以基於基本的形態學運算來建構複雜且有效的圖像處理任務。儘管其理論非常簡單、易於理解及實現,但往往存在運算速度慢的缺點,不經改善難以實際使用。
在本論文中,我們提出了一種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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2023-07-26公開。
  • 同意授權瀏覽/列印電子全文服務,於2023-07-26起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信