圖形圖像處理圖像分割

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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