国立中山大学机械与机电工程研究所.pdf

國立中山大學機械與機電工程研究所 碩士論文 指導教授嚴成文 教授 彩色影像的半自動切割方法 A Semiautomatic Segmentation for Color Images 研究生林岡品 撰 中華民國 九十一 年 六 月 摘要摘要 本論文以互動的方式發展一套影像切割方法，透過手動描繪出影 像的粗略邊界，再利用多邊形近似邊界的方法，將影像邊界分為片段 線段所組成的多邊形邊界，再以多邊形頂點作為動態規劃階段的起點 與終點，找尋最佳邊界。 多邊形近似邊界Polygonal Approximation是利用動態規劃，將原 來的邊界以一個多邊形取代，其中並包含了三種有效率的計算方法， 以節省計算量。 動態路徑規劃Dynamic Programming是最佳路徑搜尋的一種方 式，可以在起點與終點間建立一條最佳路徑。為建立影像像素點與其 鄰近像素點的相互值，以為路徑規劃的依據。結合三種能夠突顯影像 邊界的方法包括 Laplacian Zero Crossing、Gradient Magnitude 和 Gradient Magnitude，計算最小累積平均耗費值作為最佳邊界。 另外為了增加使用者的便利性，在找尋到最佳邊界後尚可利用增 加、刪除轉折點、改變影像耗費值權重等方法微調出理想的邊界。 I 目錄目錄 第一章 緒論...1 1.1 前言 ..1 1.2 研究動機2 1.3 論文架構4 第二章 影像區域耗費值..6 2.1 彩色影像特性 ..7 2.2 拉普拉斯交零點值Laplacian zero-crossing cost ...7 2.3 梯度量值Gradient magnitude cost11 2.4 梯度方向值Gradient direction cost...12 第三章 以多邊形近似邊界法處理初始邊界.15 3.1 手繪產生初始邊界.......15 3.2 多邊形近似邊界法...17 3.3 動態規劃找尋多邊形頂點...18 3.4 有效率的計算法...20 3.4.1 累積與重複利用誤差估測值20 3.4.2 起始點的決定21 3.5 測試結果...22 第四章 動態規劃前期處理26 4.1 刪除過多轉折點...27 4.2 擴散化與骨幹化....28 4.3 標定搜尋區域31 4.4 轉折點修正32 4.5 利用夾角限制搜尋範圍34 II 第五章 以動態規劃求解最佳路徑36 5.1 平均耗費值的概念37 5.2 多階段決策問題38 5.3 如何決定階段39 5.4 階段與階段間之動態規劃搜尋步驟40 5.5 同一階段內，點與點間之搜尋42 5.6 第一階段流程圖43 第六章 使用者互動介面..46 6.1 手動增加、刪除轉折點46 6.2 改變影像耗費值權重48 第七章 測試效果..50 7.1 基本圖形測試50 7.2 一般影像測試53 7.3 與 PhotoImpact 之比較57 第八章 結論...61 參考文獻.62 III 圖表目錄圖表目錄 圖 1.1 實際灰階影像圖...........................................................................2 圖 2.1 具有一階微分功能的核 a水平往右 b垂直往下.................8 圖 2.2 邊界微分的示意圖.......................................................................9 圖 2.3 時，0yx對的函數圖形..................................................10 LoG 圖 2.4 不同寬度值所對應的核.............................................................10 圖 2.5 具計算梯度功能的核.................................................................12 圖 2.6 p與其鄰居、、、的正交梯度關係圖.....................13 1234 qqqq 圖 3.1 像素 P 與鄰居的位置關係圖 ................................................16 圖 3.2 像素 P 與鄰居的位置關係圖....................................................16 圖 3.3 去毛邊的結果.............................................................................16 圖 3.4 動態規劃搜尋示意圖.................................................................19 圖 3.5 多邊形近似邊界的結果.............................................................21 圖 3.6 測試圖形 1..................................................................................22 圖 3.7 測試圖形 2..................................................................................23 圖 3.8 測試圖形 3..................................................................................23 圖 3.9 測試圖形 4..................................................................................24 圖 3.10 測試圖形 5..................................................................................24 圖 4.1 本章流程圖.................................................................................26 IV 圖 4.2 比較不同角度門檻值結果 ........................................................28 圖 4.3 擴散化的結構元件.....................................................................29 圖 4.4 擴散化結果 a原始影像 b擴散化後結果........................29 A 圖 4.5 像素 P 與鄰居的位置關係圖....................................................30 圖 4.6 標定區域必須去除骨幹.............................................................32 圖 4.7 比較保留與去除骨幹化末端差異性 ........................................35 圖 5.1 動態規劃搜尋方法示意圖 ........................................................37 圖 5.2 在轉折點前後的兩個多階段決策問題 ....................................39 圖 5.3 水平及垂直階段示意圖.............................................................40 圖 5.4 轉折點之間的多階段決策問題 ................................................40 圖 5.5 階段間搜尋示意圖.....................................................................41 圖 5.6 a 點可能的最佳路徑方向 .........................................................41 圖 5.7 方向的設定.................................................................................42 圖 5.8 同一階段內之搜尋.....................................................................42 圖 5.9 使用手繪邊界44 圖 5.10 利用直線構成邊界 ...45 圖 6.1 增加轉折點示意圖.....................................................................47 圖 6.2 增加 Corner 點之後所產生的邊界通過新增 Corner 點之範例.....................................................................................47 V 圖 6.3 增加 Corner 點之後所產生的邊界沒有通過新增 Corner 點之範例.........................................................................48 圖 6.4 比較 IZC 權重的影響................................................................49 圖 7.1 基本圖形測試-三角形...............................................................51 圖 7.2 基本圖形測試-矩形...................................................................51 圖 7.3 基本圖形測試-圓形...................................................................52 圖 7.4 彩色圖形測試-鸚鵡...................................................................54 圖 7.5 彩色圖形測試-鴨拓草...............................................................55 圖 7.6 彩色圖形測試-樹葉...................................................................56 圖 7.6 切割效果比較-鸚鵡圖58 圖 7.6 切割效果比較-手 1.59 圖 7.6 切割效果比較-手 2.60 表 2.1 影像特徵值對應符號與加權值 ..................................................6 表 3.1 圖 3.6 近似多邊形的果22 表3.2 圖3.7近似多邊形的結果23 表3.3 圖3.8近似多邊形的結果23 表3.4 圖3.9近似多邊形的結果24 表3.5 圖3.10近似多邊形的結果..24 表 7.1 基本圖形影像切割性能比較表 ................................................53 VI 表 7.2 彩色圖形影像切割性能比較表 ................................................56 VII 第一章第一章 緒論緒論 1.1 前言前言 影像，比起同樣大小的文字，能顯示更多的訊息。這是以人類的視覺 和思考方式為基礎的比較結果。當我們欣賞一張張的圖片時，會感覺到有 些比較柔和、有些比較尖銳，這是影像對比和影像邊界明顯程度不同所導 致的感覺。然而，以電腦來處理這樣的影像時，很難有一個準確的依據， 到底該影像是屬於尖銳的影像，或者是柔和的影像。實體容易形容，感覺 就很難有精準的標準了。甚至於有人表示，電腦影像由電腦來處理時，猶 如以井觀天，因為電腦總是以一個個的像素 p i x e l 來分析及記錄影像。如 何用簡單的模式去處理與表達複雜的訊息，這就是影像處理的難處了。 姑且不論上述的問題，單純地只要求電腦可以在圖片中，正確地指出 我們所要處理的影像，能達到這簡單的要求，對我們在影像處理上，也會 有非常大的助益。比方說，要從圖 1. 1 a 中指出「叉子」 ，直覺的想法就是 將 「叉子」 的邊界以一個個像素連接成 如圖 1. 1 b 的封閉區域記錄下來， 稱這塊區域就是「叉子」 。雖然這也不能說明什麼但是只要有這樣的記錄 資料，我們就可以萃取一些特徵變數，而靠電腦即可判定它就是「叉子」 。 因此，影像的邊界萃取，是作電腦影像辨識的前期關鍵技術，初步的辨 識必須將欲辨識物體的特徵變數萃取出來。影像中，特徵變數包括影像的 形狀、大小、顏色、色調深淺. . . 等。其中形狀和大小直接就和該影像的邊 界有絕對的關係。在影像處理的領域中，已經有很多成熟的邊界擷取技術。 經由這些方法的計算，可以對應到整張圖像的所有像素，顯示那些像素是 邊界，那些像素不是邊界，由於影像的像素在拍攝時，或者掃描時，甚至 於圖形儲存格式的轉換時，在這些情況下，都很容易使影像受到干擾和失 真，所以除了用可以突顯出邊界的方式使邊界的訊息產生出來之外，必須 要再經過消除雜訊，或者彌補失真的處理，才能得到可用的結果。而且 1 a 284 b 196 圖 1. 1 實際灰階影像圖 a 原始影像 b 叉子的邊界 縱使將該圖片中的所有影像邊界均正確地找出之後，到底那個影像邊界是 我們所需要的，這仍須由使用者來決定。例如圖 1. 1 a 中，我們只要找 到「叉子」就好了，可是用上述的方式找到的邊界，是所有的邊界，單純 從「邊界」的角度來看，這完全正確，但卻不是我們想要的。所以最後還 是需要由人從這些已經處理好的邊界中，挑出屬於「叉子」的邊界。基本 上，人善長於從影像中辨識出物體的位置，以及物體的大致形狀，而電腦 善長明確定義邊界。這就是為什麼我們必須使用半自動影像切割的主要原 因。 本篇論文是承襲葉清松學長論文 「以動態規劃為基礎的自動化腫瘤影像 切割方法」 ，以動態規劃為主要精神，並針對系統的穩定性做更進一步的改 良。 1. 2 研究動機 1. 2 研究動機 本實驗室有一個計畫︰「肺腫瘤檢測」 。該計劃是為協助醫師判斷醫療 影像 肺部電腦斷層掃瞄 上的腫瘤良、惡性而發展的系統。藉由肺部電腦 斷層掃瞄影像，採用類神經網路方法辨識肺腫瘤的良惡性是主要的研究問 題。一些重要的辨識特徵變數，如毛邊的情形、腫瘤的大小和腫瘤的形狀 均需先找出腫瘤的影像邊界，處理之後方能得到這些變數。葉清松學長碩 2 士論文即是根據此此目的，找出腫瘤的邊界。 198 9 年，Udupa 向 Barrett 提及作即時 live 邊界搜尋的想法，這是一個 創例。當時的構想是如何從一個設定的起始點，以即時顯示的方式，顯示 任意點到達該起始點的最佳影像邊界，經由人的判斷與修正，以與電腦互 動的方式，確定正確的影像邊界。此二人所屬的研究群同時於 1998 年分別 發表以此構想為基礎的研究報告 Mortensen and Barrett, 1998;Falcao et al., 1998 。 Barrett 所提的方法是一種無限制的影像搜尋 unrestricted graph search 。只要選擇一個起始點，當游標移到影像中任何一點，便可立即搜 尋而建立該點與起始點間的最佳路徑。若確定該最佳路徑是正確的邊界 時，可令滑鼠指標位置為起始點，然後再繼續搜尋。如此一段段地確定片 段的邊界，最後可以將邊界找出，此稱為活線方法 live wire 。 Udupa 則選擇在活動軌道 live lane 的範圍內作搜尋，限制了搜尋的範 圍，並且不以像素為最小的搜尋單位，而選擇用以兩個像素組成邊界元件 boundary element 為最小單位，為配合這樣的搜尋單位，其所計算的耗費 值 cost 與 Barrett 所採用的有一些差異，但搜尋的方法是一樣的。 這兩種方法都是很不錯的處理方式，也都很有特色。不過往往優點便 是缺點。Barrett 的方法可以無限制範圍進行搜尋，這樣會花很多的搜尋時 間。Udupa 的方法使用邊界元件，會造成搜尋結果呈現齒狀等不平順情形。 以上兩者均須由使用者選擇正確的起始點，然後依次搜尋與建立正確片 段邊界。本論文採用像素為搜尋的最小單位，配合限制特定的搜尋範圍， 使搜尋結果更為迅速和精確。此外，我們搜尋的起始點不必由使用者決定， 在搜尋過程中會自動決定。這樣的方式方便使用者，不用因為擔心影響往 後的搜尋工作，而刻意地要找出正確的起始點。 黃金璋學長碩士論文[ 1999] 的研究以此二篇為基礎，採取 Barrett 的影 3 像區域耗費值 image local cost 的計算方式，同時應用 Udupa 所提之活動軌 道 Live Lane 的概念。並且依需要，針對動態規劃 dynamic programming 用於影像搜尋的演算法作應用與改良。原論文中的演算法，是以帶頭點為 主，每一個點，在每一次搜尋會產生新的最多八個帶頭點，是以帶頭點會 愈來愈多，雖然限定了搜尋範圍，但還是造成搜尋速度上的障礙。 葉清松學長碩士論文[ 2 0 0 1] 的研究針對上列問題提出兩個改善辦法。 一、自動化產生初始邊界。二、提出了改良動態規劃的方法，使得整個邊 界搜尋的時間能有效的減少，而且還能保有良好的搜尋結果。而論文中是 針對腫瘤問題所提出的邊界搜尋方法，因此對於影像型態方面做了一些限 制，若將之使用在彩色且一般影像則並不適用。因此在影像邊界的產生仍 是採用手繪邊界 本研究的重點有二。一、利用多邊形近似邊界的方法，將手繪邊界分為 片段線段所組成的多邊形邊界，並以多邊形頂點為轉折點。二、提供使用 者良好互動介面，即時修正邊界。 1. 3 論文架構 1. 3 論文架構 本論文共分為八個章節，二個階段。一、以動態規劃為基礎的影像切 割方法 第二章 第五章 。二、 使用者互動介面 第六章 。 第一章 說明研究的問題與簡介採用的方法。 第二章 說明三個影像特徵值，使像素具有依據的指標，以為搜尋時的 重要指標。 第三章 以多邊形近似邊界法取代初始邊界。 第四章 動態規劃之前期處理所用到的工具。 第五章 簡述動態規劃的基本概念。 第六章 說明修正邊界的方法。 4 第七章 測試切割後的效果。 第八章 結論。 5 第二章 影像區域耗費值第二章 影像區域耗費值 影像區域耗費值Image Local Cost ， 以下簡稱 ILC 值是影像邊界擷取的 依據，Martensen 和 Barrett 以六個影像特徵值的加權和作為 ILC，這六項 特徵值分別是拉普拉斯交零點值Laplacian zero-crossing、梯度量值 Gradient magnitude、梯度方向值Gradient direction、邊界像素灰階值Edge pixel value、內部像素灰階值“Inside” pixel value和外部像素灰階值 “Outside” pixel value。 本論文依需要取其前三個影像特徵值，亦透過加權的方式，結合為新 的 ILC 值。加權的作用主要是為結合各種影像特徵值萃取的優點，避免其 單獨使用時產生的缺點。 定義和 是兩個相鄰的像素，pqqp,l是指從到 的影像區域耗費值。 pq 表 2.1 影像特徵值對應符號與加權值 影像特徵值 符號 加權值 拉普拉斯交零點值 Laplacian zero-crossing，簡稱 LZC 值 Z f Z w 梯度量值 Gradient magnitude，簡稱 GM 值 G f D w 梯度方向值 Gradient direction，簡稱 GD 值 D f D w ILC 值是表 2.1 所列三種影像特徵值的加權和，關係如下 qpfwqfwqfwqpl DDGGZZ ,,⋅⋅⋅ 而三個特徵值的權重程度，初始設定2 . 0 Z w、、，目前預 設值均採用此組參數，但並非硬性規定。由以上的關係式可以替每個像素 建立與其鄰近的八個像素的相互關係值。若和 兩點都是屬於邊界上的 點，則對而言，往 的方向會有較小的 ILC 值。具有這種特性，才能視影 6 . 0 G w q 2 . 0 D w p pq 6 像切割問題為一搜尋的問題，而用搜尋的方法處理。 2.1 彩色影像特性彩色影像特性 彩色影像相對於灰階影像包含了更多的資訊，而在日常生活中，我們 所接觸到的影像大部分也都是彩色影像，因此本論文將葉清松學長碩士論 文針對灰階像作處理的部分，擴展為對彩色影像處理。彩色影像有兩個主 要的好處，第一，在自動化影像分析中，彩色是一種有效的描述，例如可 以簡化目標辨識和從背景中的抽離。第二，人的眼睛能分辨幾千種的彩色 色調和強度，但能檢測的灰階只有二十幾級Gonzalez/Woods Digital Image Processing pp.221。 在彩色影像的處理中，最基本的模型就是紅、綠、藍RGB模型，但是 RGB 系統的主要缺點就是每一個成分之間有很高的關聯性，因此我們將影 像 由 RGB 的 維 度 轉 換 到 YUV 的 維 度 連 國 珍 數 位 影 像 處 理 pp.10-7,10-8，Y 代表亮度向量，U 和 V 代表色差向量，YUV 和 RGB 的關 係如下 Y 0.299R0.587G0.114B 2.1 U 0.493*B-Y 0.493*-0.299R-0.587G0.886B2.2 V 0.877*0.701R-0.587G-0.114B 2.3 U 和 V 所在的平面又稱為色差平面，且 U 和 V 正交。因此當求取影像的耗 費值時，我們將 Y、U、V 分別正規化至 0255，求取個別的影像耗費值再 取平均，作為最後的影像耗費值。 2.2 拉普拉斯交零點值拉普拉斯交零點值Laplacian zero-crossing cost 影像灰階值隱藏很多訊息。相互像素間的灰階值差異越大，越可能是 邊界。因此，對影像的任一方向作一階微分處理，出現極值的地方，可能 7 就是影像的邊界。透過圖 2.1 中的核函數kernel function處理影像後，即可 分別將影像作水平和垂直的一階微分。 a b 1 0 -1 10 -1 圖 2.1 具有一階微分功能的核 a水平往右 b垂直往下 rossing圖 2.2c。如此，通過的零點稱為交 零點 糊而形成 真。在此，採用Fleck, 1992多寬度值處理multiple widths。 影像邊緣是指物體和背景之間的邊界，相互重疊物體間的邊界也可視 為影像邊緣。基本上，當像素間的灰階值持續變大，或者持續變小，如圖 2.2a所示所示的情況，就可以視為影像邊界，這也是一般實際影像邊界的 灰階值變化情況。上面提到，一階微分可以使影像邊界處出現極值圖 2.2b，為使極值處更容易界定，對影像作二階微分，將可驅使一階微分極 值處，產生交零點效應zero-c ，該處即可視為邊界。 使用核處理影像時，核的大小決定周遭像素對處理結果的影響程度。 使用高斯函數Gauss function作為核心函數的優點，在於我們可以透過高斯 函數寬度值的調整及與距中心點距離不同來調整影響的能力，這樣可以加 強靠近中心點像素主導的影響力，同時抑制微分後雜訊的影響。不過，寬 度值過度時，雖然會處理掉許多雜訊，但相伴地也會使結果因模 失 8 a b 圖 2.2 意圖a正交於邊界的灰階值變化情形 b圖a的一次微分 c圖a 的二次微分 合理的設定，本文採取 Marr 於 1980 所提供的計算方式 Parker, 1997 c 邊界微分的示 寬度值必須作 33 . 0 35. 3σW 2.4 12WSize 2.5 Kernel 上式中，σ是指高斯函數的寬度值，W是指在使用高斯函數時，會受到 高斯函數響的像素中距中的距離。令核的大小為 設定二維度高斯函數為 足夠影心點最遠 KernSizeKernelSizeel。        − 2 2 2 exp σ σ σ r G 2.6 22 yxr 核與影像的 convolution 為 ,yxI ∑ ∑ −− KxKy yjxiGjiIGI,,* −− 2.7 KxiKyj σ 9 對作二階微分，定義為Laplacian of Gauss。 σ GLoG        −        − ∇ 2 2 4 22 2 2 exp 2 σσ σ σ rr GLoG -4.000.004.00 -4.00 0.00 4.00 2.8 形如圖 2.3 所示。依不同高 函數寬度值，得到的核函數如圖 2.4 所示。 圖2.3 透過以上的處理過程，寬度值為 1 的函數圖 斯 0y時，x對的函數圖形 0.13 1.17 0.13 0 0.020.050.080.05 0.02 0 LoG 1.17 -12.5 1.17 0.020.110.250.270.25 0.11 0.02 0.13 1.17 0.13 0.050.250 -0.61 0 0.25 0.05 a 0.08027-0.61-2 -0.61 0.27 0.08 0.050.250 -0.61 0 0.25 0.05 1.08 0.020.110.250.270.25 0.11 0.02 0 0 0.02 0 0 0 0.020.050.080.05 0.02 0 0 0.44 1.08 0.440 c 0.02 1.08 -8 1.080.02 0 0.44 0.440 0 0 0.02 0 0 b 圖2.4 不同寬度值所對應的核 a4 . 0σ b5 . 0σ c0 . 1σ 透過核處理完的影像，邊界將出現在由正變負者由負變正的交零 點處，而且並不一定正好為 0。因此，利用四結 ，或 連 pN4是指第p個像素的 10 四個正向鄰居來判斷像素是否為邊界。定義是指處理過後的二位元影像 ry image。 Z B p . . bina ∈ 水平階段 水平階段 垂直階段 圖 5 . 3 水平及垂直階段示意圖 圖 5 . 4