圖形圖像處理圖像分割

1、第七章 圖像分割,一、引言圖像分割的目的——理解圖像的內(nèi)容，提取出我們感興趣的對象。 圖像分割按照具體應(yīng)用的要求和具體圖像的內(nèi)容將圖像分割成一塊塊區(qū)域。 圖像分割是模式識別和圖像分析的預(yù)處理階段。圖像分割的方法——通常采用聚類方法，假設(shè)圖像中組成我們所感興趣對象的像素具有一些相似的特征，如相同的灰度值、相同的顏色等。圖像分割技術(shù)——基于區(qū)域的分割技術(shù) ； 基于邊界的分割技術(shù) 。,圖像分割的數(shù)學(xué)描述,令集合R代表整個

2、區(qū)域，對R的分割可看作將R分成若干個滿足以下5個條件的非空子集(子區(qū)域)R1 ,R1 ,…Rn：,(1)所有子集構(gòu)成圖像；(2)各子集不重疊；(3)每個子集中的像素有某種共同的屬性；(4)不同的子集屬性不同；(5)每個子集中的所有像素應(yīng)該是連通的。,二、并行邊界技術(shù),1、邊緣檢測原理：利用邊緣灰度變換較劇烈的特點，根據(jù)灰度變換的情況，選擇不同的檢測方法使邊緣凸現(xiàn)-P181。2、具體算子模板：用梯度算子(一階差分)、Laplace算子(

3、二階差分)以及在圖像增強中所講的各類圖像銳化算子模板都可以對圖像進(jìn)行銳化——空域卷積。以點模板為例——對模板的另一種理解：,二階差分,一階差分,如果在模板區(qū)域內(nèi)所有圖像的象素有相同的值，則其和為零。如果模板中心位于某個灰度值不同于其8鄰域灰度值的點上，則其和不為零；如果該點在偏離模板中心的位置上，其和也不為零，但其響應(yīng)幅度比起這個點位于模板中心的情況要小一些。這時，可以采用閾值法清除這類較弱的響應(yīng)，如果其幅度值超過閾值，就意味著點檢測

4、出來了，如果低于閾值則忽略掉。,同樣道理，可以構(gòu)造線模板,3、邊界閉合算法邊界有一個特點：其梯度相似、梯度的方向角度的大小相似。將滿足這兩個條件的點賦予同等灰度，可構(gòu)成邊界。具體做法：求出f(x,y)鄰域內(nèi)所有像素的梯度和梯度角，將滿足下列關(guān)系的f(x,y)、f(s,t) “連接”起來(賦予特殊的灰度值，如最大值)。,4、哈夫變換,用哈夫變換可以檢測出某些已知形狀的目標(biāo)的邊界。前提條件是該目標(biāo)邊界的數(shù)學(xué)模型是已知的。哈夫變換具有較強的

5、抗干擾性。,某圖像中一條直線，使用某種檢測算子后有如圖所示的邊界提取結(jié)果。根據(jù)經(jīng)驗該邊界是一條真線，可以用直線方程表達(dá)。使用哈夫變換可直接得出該邊界的方程。實例：汽車大燈燈光截止線的測試。測試內(nèi)容——截止線與水平基線的夾角。,,圖像效果,1)、哈夫變換原理,如果對上述得到的圖像求導(dǎo)數(shù)，如圖所示。問題變成求導(dǎo)數(shù)值最大的點所共線的直線方程y=px+q。換句話說：在圖像f(x,y)中，求取那些最多的滿足方程y=px+q的點，并確

6、定p、q值。將方程改寫為q=-px+y，將x，y看成定數(shù)，則可以建立p，q直線方程。,,由圖可以看出：通過求取共線點，構(gòu)造直線方程y=px+q ，求取各直線的焦點即可確定點p，q值——點－線變換。,2)、哈夫變換的操作,1)、構(gòu)造一個P、Q空間的二維累加數(shù)組A(p,q)2)、從f(x,y)的指定區(qū)域中取(xi,yi)，按方程q=-pxi+yi在[pmin,pmax]中遍取可能的p值計算得到可能的q值。3)、在對應(yīng)的位置計算

7、A(p,q) =A(p,q)+14)、重復(fù)2)、3)直到將從f(x,y)的指定區(qū)域中的所有點取完。此時，A(p,q)數(shù)組中最大值所對應(yīng)的p，q就是方程y=px+q中的p、q值。5)、根據(jù)y=px+q繪出f(x,y)中的直線。,區(qū)域的選擇：來自確認(rèn)存在直線的區(qū)域。坐標(biāo)的選擇：來自對存在的直線參數(shù)的估測。,3)、存在的問題即解決方法,如果直線趨于垂直，則p→∞，為直線的描述帶來不方便。更一般的描述是用參數(shù)方程：λ=xcosθ+ysin

8、θ。根據(jù)這個方程，圖像中直線上的點，被映射成為(λ,θ)空間中的正弦曲線——點－曲線變換。例：某N×N圖像中有點1、2、3、4、5，設(shè)θ在[-900,900]中取值，畫出它的哈夫變換圖。,從曲線上可以看出：,2、3、4交于一點——共線1、5、3交于一點——共線4、1 交于一點——共線4、5 交于一點——共線1、2 交于一點——共線2、5 交于一點——共線實際上，哈夫變換不僅可

9、以對直線方程的共線點進(jìn)行檢測，也可以對曲線方程的共線點進(jìn)行檢測，道理是一樣的。所不同的是隨著未知參數(shù)的增加，所構(gòu)造的數(shù)組維數(shù)會上升，計算量增加。,在λ,θ數(shù)組中數(shù)值較高的單元所對應(yīng)的λ,θ值構(gòu)成 的λ=xcosθ+ysinθ為圖像中的一條直線。,,例如：根據(jù)經(jīng)驗，圖像中的某目標(biāo)一定是一個圓，其方程可以用(x-a)2+(y-b)2=r2來描述，其中有三個未知數(shù)a、b、r。通過哈夫變換可以求得：給定x、y，遍取a、b的可能值計算出r。并使對

10、應(yīng)的三維累加數(shù)組的對應(yīng)位置增1。,r、a、b的取值范圍事先應(yīng)有一個估測。,給定xi、yi后，r=f(a,b)的方程是一個圓的方程；遍取可能的a、b值…改變xi、yi，重復(fù)操作…,如此往復(fù)，可得參數(shù)a、b、r。,給定xi、yi后，r=f(a,b)的方程仍是一個圓的方程。因此，用任何一個R=r平面來切割三維數(shù)組，看到的“截面”都是圓的集合。累加值最高的a、b值，就是共圓的x、y點的個數(shù)，此時的r就是圓的半徑。同理，用哈夫變換可以檢測橢圓

11、、拋物線、指數(shù)曲線等可以用方程表達(dá)的各類曲線。未知參數(shù)越多，數(shù)組的維數(shù)越大。,,三、串行邊界技術(shù),圖搜索定義代價函數(shù)c(p,q) ：c(p,q)=H-|f(p)-f(q)|。其中，H為圖像中的最大灰度值， f(p)、f(q)為像素p、q的灰度值。顯然，代價函數(shù)的取值反比于像素間的灰度差值的絕對值。由此可得，代價大對應(yīng)梯度?。环粗鷥r小對應(yīng)梯度大。如果能夠發(fā)現(xiàn)一條累計代價最小的通路，這條通路就有可能是一個邊界。,灰度圖,代價圖,累積代價

12、最小通道,可能邊界,搜索決策圖,,,,,,,,,,,,,,,,,,,,,,,,,,,四、并行區(qū)域技術(shù)——灰度閾值分割法,灰度閾值分割法是最古老的分割技術(shù)，常應(yīng)用于圖像中組成感興趣對象的灰度值是較均勻的，并且和背景的灰度值不一樣。事先決定一個閾值，當(dāng)一個像素的灰度值超過這個閾值，我們就說這個像素屬于我們所感興趣的對象；反之則屬于背景部分。 適合這種分割法的圖像的直方圖應(yīng)是雙峰模式，我們可以在兩個峰值之間的低谷處找到一個合適

13、的閾值。單一閾值方法不適合于由許多不同紋理組成一塊塊區(qū)域的圖像。,灰度閾值分割法圖像分割技術(shù)的數(shù)學(xué)模型,灰度閾值分割法的關(guān)鍵是求出合適的閾值。于是產(chǎn)生出各種各樣求閾值的方法。,1、極小值點閾值利用了被分割對象灰度與非被分割對象灰度之間的差異進(jìn)行分割，可以用單閾值分割，也可用多閾值分割。其主要問題是如何選擇最佳閾值。,2、最優(yōu)閾值,絕大部分圖像的背景與目標(biāo)的灰度值有重疊部分，如何才能選擇最優(yōu)閾值，減小誤分割的概率？設(shè)背景與目標(biāo)的概率

14、密度之和p(z)是兩個單峰密度函數(shù)p1(z)、 p2(z)之和，且p1(z)、 p2(z)已知；背景的象點數(shù)占圖像總點數(shù)的百分比為P1，目標(biāo)點占P2，且P1＋P2＝1則混合概率密度為,誤判概率：,目標(biāo)誤判為背景的概率,背景誤判為目標(biāo)的概率,,,p1(z),p2(z),T,,,目標(biāo),背景,總的誤判概率之和為：,為了使其最小，對T求導(dǎo)數(shù)，令導(dǎo)數(shù)等于0。,解出最優(yōu)閾值為：,3、按幅度設(shè)置閾值分割,T1,T2,T3,K,p(k),在實際工作中，

15、概率密度的求取是一件非常困難的事情。,3、依賴區(qū)域的閾值選取,對于具有明顯雙峰的直方圖可以方便的選擇閾值T。但有一些圖像，物體和背景的灰度差異不大或由于噪聲的原因使峰谷被填平等原因，使得選擇T值變得困難。為此得尋找其它的方法來確定T值。1)、直方圖變換解決的問題是如何將原來峰谷差異不大的直方圖，變成便于選擇T的峰谷差異較大的直方圖。具體方法：對圖像求梯度；做出梯度圖像灰度的直方圖，選擇T。,基本原理,,,,,x,f(x),h[f(

16、x)],,,x,f’(x),h[f’(x)],,,,,,,,,,空間坐標(biāo),空間坐標(biāo),灰度坐標(biāo),梯度坐標(biāo),灰度直方圖,梯度直方圖,,,取雙峰間梯度最小點所對應(yīng)的灰度值為閾值,低梯度值直方圖與高梯度值直方圖,如果雙峰特性仍不明顯，在進(jìn)行直方圖統(tǒng)計時對像素點的灰度值根據(jù)該點的梯度g做加權(quán)處理。低梯度值直方圖的像素加權(quán)值為1/(1+g)2；高梯度值直方圖的像素加權(quán)值為g。2)、灰度值和梯度值散射圖對圖像求梯度后，根據(jù)原圖像的灰度分布和梯度圖

17、像的數(shù)值構(gòu)造灰度值和梯度值散射圖——選擇T。,,,,,,x,x,對高于某一個梯度值的像素進(jìn)行統(tǒng)計,對低于某一個梯度值的像素進(jìn)行統(tǒng)計,h[f(x,y)|f’(x,y)>low],h[f(x,y)|f’(x,y)≤high],空間坐標(biāo),空間坐標(biāo),頻度坐標(biāo),頻度坐標(biāo),取該點的灰度值為T,,3)、基于過渡區(qū)的方法,過渡區(qū)的特點：任何背景與目標(biāo)的過渡至少存在一個像素寬的過渡區(qū)。因此，過渡區(qū)是可以觀察到的。設(shè)f(i,j)為數(shù)字圖像， g(

18、i,j)為f(i,j)的梯度圖，Z為圖像的灰度集合；定義圖像有效平均梯度EAG。,,,,,,背景灰度范圍,,,,目標(biāo)灰度范圍,,,T,L,TG為梯度圖的總梯度值TP為非零梯度像素的總數(shù)可見EGA為梯度的總值被有效梯度(非零梯度像素)所平均——有效平均梯度。如果設(shè)置分割閾值L對圖像進(jìn)行分割，有兩種分法。,對分割后的圖像求梯度，而后求EAG， EAG應(yīng)是閾值L的函數(shù)EAG(L)。對應(yīng)兩種分割方法，應(yīng)有兩種EAG(L)：

19、 可以證明，它們都是單峰曲線。設(shè)當(dāng)L=Lhigh和L=Llow時取得，可以證明這兩個極值點有三個重要性質(zhì)：,對每個過渡區(qū)， Lhigh和Llow總是存在，并且只存在一個；Lhigh和Llow所對應(yīng)的灰度值都具有明顯的像素特性區(qū)別能力；對于同一個過渡區(qū)， Lhigh不會比Llow小，在實際圖像中Lhigh總大于Llow。顯然，在介于Lhigh和Llow之

20、間取一個值作為分割閾值即可對圖像進(jìn)行分割。,LMAX,4、依賴坐標(biāo)的閾值選取,對一幅圖像中的物體，有時可以采用統(tǒng)一的一個閾值進(jìn)行分割。而有時，由于圖像的內(nèi)容以及得到圖像的方式導(dǎo)致不能采用統(tǒng)一的一個閾值進(jìn)行分割，就需要將圖像分成若干個子圖像，對每個子圖像采用不同的閾值進(jìn)行目標(biāo)與背景的分割。然后再將各子圖像拼接起來。具體做法：將整幅圖像分成一系列互相之間有50％重疊的子圖像；做出每個子圖像的直方圖；檢測各個子圖像的直方圖是否為雙峰

21、；是，選最優(yōu)閾值；否，不進(jìn)行處理；根據(jù)得到的最優(yōu)閾值通過插值的方法得到所有子圖像的閾值；根據(jù)各子圖像的閾值，通過差值得到所有像素的插值；對圖像進(jìn)行分割。,示例,將這四個閾值作為四個頂點像素的閾值；采用線性插值得方法，得到所有像素的閾值，對圖像進(jìn)行分割，例如：,,待分割圖像,6×6子圖像各重疊50％,,插值后每個子圖像有4個閾值,,5、連通區(qū)域標(biāo)記,像素標(biāo)記：定義連通；“從左到右，從上到下”掃描；進(jìn)入一個像素后，考慮左、

22、上方元素的連通性(先左后上)；不同的連通域，賦予不同的灰度值Ti。標(biāo)記完成后，進(jìn)行第二次掃描分割。4-連通定義：V表示定義連接的灰度值集合；4-連通：2個象素p和r在V中取值且r在N4(p) 中。例：定義連通域為4-連通，4-鄰域像素值之差的絕對值小于5； 灰度集合為V={[V-5,V+5]} ；連通域不同，V的取值范圍不同。用連通區(qū)域標(biāo)記法對下面的圖像進(jìn)行分割。,五、串行區(qū)域技術(shù),什么是區(qū)域?——一般用以下性質(zhì)來定義區(qū)域：在同一

23、區(qū)域的像素點必須相連。這就意味著我們可以從現(xiàn)在所處的像素點出發(fā)，按照某種連接方式到達(dá)任何一個鄰近的像素點。常用的有兩種各向同性連通方式：四連通和八連通。 區(qū)域之間不能重疊，也就是說一個像素只能有一個“標(biāo)記”。 在區(qū)域Ri中每一個像素點必須遵從某種規(guī)則P(Ri)。例如我們說P(Ri)為真，當(dāng)區(qū)域Ri中所有像素具有相似的灰度(相似性在一定的范圍內(nèi))。 兩個不同的區(qū)域Ri和Rj具有的規(guī)則不同。,1、區(qū)域生長法,最簡單的區(qū)域生長法是將

24、像素聚類，為了達(dá)到這一目的，可以從一個種子像素點出發(fā)，按照某種連通(如8連通)方式和規(guī)則P來檢查周圍鄰近的像素點，如果具有和種子像素點相似的性質(zhì)，就說明它們屬于同一區(qū)域，怎樣獲得初始的種子像素點和制定生長規(guī)則是區(qū)域生長法的關(guān)鍵。 例如：生長規(guī)則的連通性為8連通；連通鄰域的差值為T。,2、區(qū)域分割與合并,任何一幅圖像都可以用多層四叉樹來表示。若圖像大小為N×N，且N=2m 時，其層數(shù)為m+1。例如：m=2，層數(shù)＝2+1=3,

25、… …,具體步驟1)、對任何一區(qū)域Ri，如果區(qū)域內(nèi)某種特征的均勻性不符合設(shè)定的準(zhǔn)則，就按四叉樹原則繼續(xù)分割；2)、相鄰的工作區(qū)域Ri、Rj符合設(shè)定的準(zhǔn)則，就合并；3)、如果進(jìn)一步的合并和分裂都不可能了，則結(jié)束。,例：用分割與合并法對下圖進(jìn)行處理,分割與合并的準(zhǔn)則為(準(zhǔn)則是多種多樣的)：例如，Ri內(nèi)的平均灰度與Ri內(nèi)各像素之間的差的絕對值有超過5的像素，則分割；反之合并且合并區(qū)域的灰度以合并后的平均值取代。,,,,,,六、分割評價

26、,分割方法多種多樣，什么樣的分割技術(shù)分割的效果更好一些——分割技術(shù)的評價。1、對分割方法的基本要求應(yīng)具有通用性應(yīng)采用定量的和客觀的性能評價準(zhǔn)則應(yīng)選取通用的圖像進(jìn)行測試儀評價以具有可比性2、評價方法分類分析法——直接研究分割算法的原理特性，通過分析推理得到算法性能。實驗法——用待平價的算法去分割圖像，然后借助一定的質(zhì)量測度來判斷分割結(jié)果的優(yōu)劣。,3、評價準(zhǔn)則——最終測量精度UMA,分割的目的是將感興趣的目標(biāo)分離出來，因此，通