|
終于寫完數(shù)字圖像分割這部分內(nèi)容了,，由于內(nèi)容比較多，因此做一個小的內(nèi)容提要,，有利于更有調(diào)理的閱讀,，如下：
1.數(shù)字圖像分割方法概要
2.基于邊界分割
2.1邊緣檢測
2.2邊界提取（簡單連接,，啟發(fā)式搜索,，曲線擬合）
3.基于區(qū)域分割
3.1閥值分割（直方圖雙峰，迭代法,，Ostu(大律）法,，基于熵的二值方法）
3.2區(qū)域生長
3.3區(qū)域分裂與合并
4.總結(jié)與實驗實現(xiàn)（Java語言）
提供最佳閥值分割迭代算法，Otsu閥值分割算法,，基于熵的二值方法的實現(xiàn)
§1 數(shù)字圖像分割處理根據(jù)不同特征,，分為兩類：基于邊界分割和基于區(qū)域分割,，主要方法有：
灰度閥值分割
邊界分割法
基于紋理的分割
區(qū)域生長法
§2 基于邊界分割
§2.1 邊緣檢測
§2.2 邊界獲取
使用邊緣檢測算子檢測處理的都是孤立的一些點,，需要進(jìn)行邊界獲取將孤立點連接成線,。
邊緣檢測的結(jié)果得到許多梯度大的點，還必須進(jìn)一步處理：
原因：物體邊界一般是線,，而非孤立的點,。必須把邊緣點連接成邊緣鏈，形成直線,、曲線,、各種輪廓線等，直到能表示圖像中物體的邊界,。邊界表示可以使圖像的表示簡潔,，可以用來完成一定的文字識別任務(wù)或高層次的理解創(chuàng)造前提。邊緣形成線特征包括二個過程：抽取可能的邊緣點,；將慮出的邊緣連接成直線,、曲線、輪廓線,，或用一定的直線,、曲線去擬合它們。
困難：
梯度大的點,、不一定真正是邊緣點,。
邊緣點的梯度也有可能小于周圍其它點。
分岔和缺損,。
對于一階算子,，需要對得到的邊緣圖進(jìn)行細(xì)化，理想情況時,，細(xì)化成單象素寬的閉合連通邊界圖,。非理想情況下，邊緣圖像會有間隙存在,，需要加以填充,。對于二階算子，過零點一般是單線,，不需要細(xì)化,，仍然需要補充間隙點。
細(xì)化算法見數(shù)學(xué)形態(tài)學(xué),。
邊界跟蹤
連點成線
例如,，一個簡單的算法：e(x,y)邊緣強度,，ф(x,y)邊緣方向，兩邊緣點滿足以下條件時可以連接：
|e(xi,yi)－e(xj,yj)|<T1
|ф(xi,yi)－ф(xj,yj)|mod 2π<T2
|e(xi,yi)|>T, |e(xj,yj)|>T
條件3 使小的干擾避免被誤認(rèn)為邊緣,。
從滿足|e(xA,yA)|>T 的A 點出發(fā),，如果找不到滿足以上條件的相鄰點，算法停止,。如果有多個滿足條件的鄰點,，選邊緣強度差和角度差小的點。再不斷從新的起始點出發(fā)繼續(xù)搜索,。
啟發(fā)式搜索
人工智能中的概念,，是一種從多種可能的路徑中選優(yōu)的方法。搜索需要有評價函數(shù),，為每一條路徑打分,，以便于選擇路徑。邊緣質(zhì)量評價函數(shù)可以包括各點的邊緣強度,，也可以利用邊緣的方向信息,。
當(dāng)有多條可能路徑時，可以用全搜索（窮舉法）,，找到評價指標(biāo)最 優(yōu)的路徑作為結(jié)果。然而,，全搜索運算太大,，組合爆炸。啟發(fā)式搜索是在搜索的過程中設(shè)定一些啟發(fā)性規(guī)則,，當(dāng)規(guī)則滿足時就認(rèn)為某一段路經(jīng)合理,，不再比較其它候 選路經(jīng)。例如：如果邊緣方向上出現(xiàn)大的邊緣點,，則認(rèn)為方向正確,。邊界的點稀疏或有長缺口時可以采用此方法。該技術(shù)對相對簡單的圖像效果很好,，啟發(fā)式搜索比
全搜索減少了運算量,，但不一定能找到兩端點間連接的全局最優(yōu)路徑。
圖：啟發(fā)性規(guī)則的例子,，只有滿足圖中形式的連接被認(rèn)為可能,。
曲線擬合
如果邊緣點很稀疏，可以用分段線性或高階樣條曲線來擬合這些點,，從而形成邊界,。
圖：多邊形擬合
我們都學(xué)過最小二乘法作直線擬合，更復(fù)雜的二次曲線,，高斯擬合等也不難實現(xiàn),。數(shù)學(xué)上是某種準(zhǔn)則下的最優(yōu)參數(shù)估計問題,。所用準(zhǔn)則多為均方誤差最小準(zhǔn)則，所估計的參數(shù)是曲線方程中的未知參數(shù),。具體的擬合方法參考各種參考書,。
其它邊界抽取方法
Hough 變換
圖搜索
動態(tài)規(guī)劃
使用閥值進(jìn)行圖像分割
閾值分割法是一種簡單的基于區(qū)域的分割技術(shù)，是一種廣泛使用的 圖像分割技術(shù),，它利用圖像中要提取的目標(biāo)和背景在灰度特性上的差異,，把圖像視為具有不同灰度級的兩類區(qū)域的組合，選取一個合適的閾值,，以確定圖像中每個像 素點是屬于目標(biāo)還是屬于背景,。它不僅可以極大的壓縮數(shù)據(jù)量，而且也大大簡化了圖像信息的分析和處理步驟,。閾值法是首先確定一個處于圖像灰度級范圍內(nèi)的灰度
閾值T,，然后將圖像中每個像素的灰度值都與這個閾值T比較，根據(jù)它是否超過閾值T而將該像素歸于兩類中的一類,。常用的方法就是設(shè)定某一閾值T,，用T將圖像 分割成大于閾值T的像素群(目標(biāo))和小于閾值T(背景)的像素群兩部分。這兩類像素一般屬于圖像中的兩類區(qū)域,，所以對像素根據(jù)閾值分類達(dá)到了區(qū)域分割的目 的,。輸入圖像是F（x，y）,，輸出圖像是B（x,，y），則:
§3.1 閾值化分割方法
根據(jù)圖像本身的特點,，可分為單閾值分割方法（全局）和多閾值分 割方法（局部）;也可分為基于像素值的閾值分割方法,、基于區(qū)域性質(zhì)的閾值分割方法和基于坐標(biāo)位置的閾值分割方法。若根據(jù)分割算法所具有的特征或準(zhǔn)則,，還可 以分為直方圖峰谷法,、最大類空間方差法、最大墑法,、模糊集法,、特征空間聚類法、基于過渡區(qū)的閾值選取法等,。
§3.1.1直方圖閾值的雙峰法
該閾值化方法的依據(jù)是圖像的直方圖,，通過對直方圖進(jìn)行各種分析 來實現(xiàn)對圖像的分割。圖像的直方圖可以看作是像素灰度值概率分布密度函數(shù)的一個近似,，設(shè)一幅圖像僅包含目標(biāo)和背景,，那么它的直方圖所代表的像素灰度值概率 密度分布函數(shù)實際上就是對應(yīng)目標(biāo)和背景的兩個單峰分布密度函數(shù)的和。圖像二值化過程就是在直方圖上尋找兩個峰,、一個谷來對一個圖像進(jìn)行分割,，也可以通過用
兩級函數(shù)來近似直方圖,。
若灰度圖像的直方圖，其灰度級范圍為i=0,1,…,，L-1,當(dāng)灰度級為k時的像素數(shù)為 ,，則一幅圖像的總像素數(shù)N為:
灰度級 i出現(xiàn)的概率為：
當(dāng)灰度圖像中畫面比較簡單且對象物的灰度分布比較有規(guī)律時，背景和對物象在圖像的灰度值方圖上各自形成一個波峰,，由于每兩個波峰間形成一個低谷,，因而選擇雙峰間低谷處所對應(yīng)的灰度值為閾值，可將兩個區(qū)域分離,。
把這種通過選取直方圖閾值來分割目標(biāo)和背景的方法稱為直方圖閾值雙峰法,。如下圖所示，在灰度級t1和t2兩處有明顯的波峰,，而在t處是一個谷點
具體實現(xiàn)的方法先做出圖像f(x,y)的灰度直方圖,，若出現(xiàn)背 景目標(biāo)物兩區(qū)域部分所對應(yīng)的直方圖呈雙峰且有明顯的谷底，則可以將谷底點所對應(yīng)的灰度值作為閾值t,，然后根據(jù)閾值進(jìn)行分割就可以將目標(biāo)從圖像中分割出來,。 這種方法適用于適用于目標(biāo)和對景的灰度差較大，直方圖有明顯谷底的情況,。
將原始圖像和閾值分割后的圖像比較,，可以發(fā)現(xiàn)有些前景圖像和背 景圖像的灰度值太接近，導(dǎo)致有些前景圖像沒有從背景中分離出來,，圖像失真了,。雙峰法比較簡單，在可能情況下常常作為首選的閾值確定方法,，但是圖像的灰度直 方圖的形狀隨著對象、圖像輸入系統(tǒng),，輸入環(huán)境等因素的不同而千差萬別,，當(dāng)出現(xiàn)波峰間的波谷平坦、各區(qū)域直方圖的波形重疊等情況時,，用直方圖閾值難以確定閾
值,，必須尋求其他方法來選擇適宜的閾值。
§3.1.2迭代法（最佳閥值分割迭代法）
迭代法也是聚類方法中的 K-means算法,，當(dāng)然下面演示的K=2的情況,。
迭代式閾值選取的基本思路是:首先根據(jù)圖像中物體的灰度分布情況，選取一個近似閾值作為初始閾值,，一個較好的方法就是將圖像的灰度均值作為初始閾值,；然后通過分割圖像和修改閾值的迭代過程獲得認(rèn)可的最佳閾值。迭代式閾值選取過程可描述如下,。
(1)選取一個初始閾值T,。
(2)利用閾值T把給定圖像分割成兩組圖像,，記為 和 。
(4)選取新的閾值T,且
(5)重復(fù)第(2)~(4)步,，直至 和 均值 和 不再變化為止。
具體實現(xiàn)時,，首先根據(jù)初始開關(guān)函數(shù)將輸入圖逐個圖像分為前景和 背景,，在第一遍對圖像掃描結(jié)束后，平均兩個積分器的值以確定一個閾值,。用這個閾值控制開關(guān)再次將輸入圖分為前景和背景,，并用做新的開關(guān)函數(shù)。如此反復(fù)迭帶 直到開關(guān)函數(shù)不在發(fā)生變化,，此時得到的前景和背景即為最終分割結(jié)果,。迭代所得的閾值分割的圖像效果良好?；诘拈撝的軈^(qū)分出圖像的前景和背景的主要區(qū)
域所在,，但在圖像的細(xì)微處還沒有很好的區(qū)分度。對某些特定圖像,，微小數(shù)據(jù)的變化卻會引起分割效果的巨大改變,，兩者的數(shù)據(jù)只是稍有變化，但分割效果卻反差極 大,。對于直方圖雙峰明顯,，谷底較深的圖像，迭代方法可以較快地獲得滿意結(jié)果,，但是對于直方圖雙峰不明顯,，或圖像目標(biāo)和背景比例差異懸殊，迭代法所選取的閾 值不如其它方法,?；诘拈撝的軈^(qū)分出圖像的前景的主要區(qū)域所在，但在圖像的細(xì)微處還沒有很好的區(qū)分度,?？偟膩碚f迭代法比雙峰法分割的效果有很大的提 高。
§3.1.3大律法(Otsu閥值分割算法）
圖像記t為前景與背景的分割閾值,，前景點數(shù)占圖像比例為 ,，平均灰度為 ,；背景點數(shù)占圖像比例為 ,，平均灰度為 ，則圖像的總平均灰度為：
從最小灰度值到最大灰度值遍歷t,，當(dāng)t使得值
最大時的t即為分割的最佳閾值。
大津法可作如下理解：該式實際上就是類間方差值,，閾值t 分割出的前景和背景兩部分構(gòu)成了整幅圖像,，而前景取值
，概率為 ,，背景取值,，概率為 ，
總均值為u,，根據(jù)方差的定義即得該式,。因方差是灰度分布均勻性的一種度量,方差值越大,說明構(gòu)成圖像的兩部分差別越大,當(dāng)部分目標(biāo)錯分為背景或部分背景錯 分為目標(biāo)都會導(dǎo)致兩部分差別變小，因此使類間方差最大的分割意味著錯分概率最小,。直接應(yīng)用大津法計算量較大,，因此在實現(xiàn)時采用了等價的公式
在測試中發(fā)現(xiàn)，大津法選取出來的閾值非常理想,，表現(xiàn)較為良好,。雖然它在很多情況下都不是最佳的分割，但分割質(zhì)量通常都有一定的保障,，可以說是最穩(wěn)定的分割,。
§3.1.4 類內(nèi)方差最小方差法
對Otsu閥值分割做下變形，就可以得到類內(nèi)最小方差法,。對于每個可能的閾值,，分成兩類，分別計算類內(nèi)方差：
使類內(nèi)方差最小,。
§3.1.5 最小錯誤概率分類法
已知前景和背景的概率分布的情況下：
例如：假設(shè)背景與前景的灰度都是正態(tài)分布,，分布參數(shù)已知時可以推導(dǎo)出最小錯誤概率的門限值。假設(shè)圖像上前景點的灰度值概率分布是
,，背景點是,，選取閾值T
作為分割點。
則背景判為前景的錯誤：
則前景判為背景的錯誤：
總錯誤：
總錯誤最小,，則對T 導(dǎo)數(shù)為零,。得到：
如果前景背景都是正態(tài)分布：
是前景與背景點數(shù)量的比例，如果方差相同,，比例也相同
則：
§3.1.6 基于熵的二值化方法
假設(shè)以閥值T分割圖像，圖像中低于閥值T的灰度的像素點構(gòu)成目標(biāo)物體（O）,，高于閥值T的像素點構(gòu)成背景（B）,，則各個灰度級在本區(qū)的分布概率如下：
O區(qū)：
B區(qū)：
其中，L是圖像灰度級總數(shù),，并且
目標(biāo)和背景區(qū)域的熵分別為
對圖像每個灰度級分別計算
選取使w最大的灰度級作為分割圖像的閥值T,。
局部自適應(yīng)
當(dāng)照明或透射不均勻時，整幅圖像分割將沒有合適 的單一門限。這時,，可對圖像分塊,，對每一塊分別選一門限進(jìn)行分割，如果某塊內(nèi)有目標(biāo)和背景,，則直方圖呈雙峰,。如果塊內(nèi)只有目標(biāo)或背景，則直方圖沒有雙峰,，可根據(jù)鄰居諸塊得到的參數(shù)通過內(nèi)插進(jìn)行分割,。
§3.2 基于區(qū)域的圖像分割
基于邊緣的圖像分割：尋找區(qū)域之間的邊界
基于區(qū)域的圖像分割：直接創(chuàng)建區(qū)域
基于邊緣的方法得到的結(jié)果通常不會與區(qū)域生長方法得到的分割完全一致。
二種方法結(jié)合,，會是一個好辦法,。區(qū)域生長的方法在噪聲干擾、邊緣不易提取的情況下,，效果更好,。區(qū)域內(nèi)部的一致性描述是區(qū)域生長法的基本準(zhǔn)則。一般是其灰度,，也可以考慮顏色,、紋理、形狀等,?；陂撝档姆椒ǎ夯趩蝹€點的特點?；趨^(qū)域的方法考慮到相鄰點的一致性,。
§3.2.1 區(qū)域生長和區(qū)域合并
區(qū)域生長的原理和步驟
區(qū)域生長的基本思想是將具有相似性質(zhì)的像素集合起來構(gòu)成區(qū)域。具體先對每個需要分割的區(qū)域找一個種子像素作為生長的起點,，然后將種子像素周圍鄰域中 與種子像素有相同或相似性質(zhì)的像素(根據(jù)某種事先確定的生長或相似準(zhǔn)則來判定)合并到種子像素所在的區(qū)域中,。將這些新像素當(dāng)作新的種子像素繼續(xù)進(jìn)行上面的 過程，直到再沒有滿足條件的像素可被包括進(jìn)來,。這樣一個區(qū)域就長成了,。
思路：從一些種子點生長，直到充滿整個圖像,。種子點有監(jiān)督選取,。每個目標(biāo)區(qū)域中至少有一個點。
需要確定：
如何選擇一組能正確代表所需要區(qū)域的種子像素,，如果計算結(jié)果可以看出聚類的情況,，那么可以選擇聚類中心作為種子像素。
生長的方法
和每次生長后的一致性準(zhǔn)則,，如灰度差小于閾值,。
簡單的生長方法,，區(qū)域的所有8 鄰域點。
如果該點加入后滿足一致性準(zhǔn)則,，則加入,。兩個區(qū)域滿足一定準(zhǔn)則，可以合并,，該準(zhǔn)則可以考慮兩個區(qū)域分別的均值和方差,。如果沒有預(yù)先確定的種子點，可采用一般步驟
1. 用某種方法把圖像分割成許多小區(qū)域,。
2. 定義合并相鄰區(qū)域的準(zhǔn)則,。
3. 按照合并準(zhǔn)則合并所有相鄰的區(qū)域，如果沒有再能夠合并的塊后停止,。
采用不同的初始分割方法和合并準(zhǔn)則,，可以得到適應(yīng)不同情況的算法。另外,，區(qū)域合并得結(jié)果通常還依賴于區(qū)域合并的順序,。
相鄰區(qū)域的特征值之間的差異是計算邊界強度的一個尺度。如果給定邊界兩側(cè)的特征值差異明顯,，那么這個邊界很強,，反之則弱。強邊界允許繼續(xù)存在,，而弱邊界被消除,，相鄰區(qū)域被合并。計算是一個迭代過程,，每一步重新計算被擴(kuò)大的區(qū)
域成員隸屬關(guān)系,，并消除弱邊界。沒有弱邊界可消除時,，合并過程結(jié)束,。
過程看起來象一個物體內(nèi)部區(qū)域不斷增長，直到到達(dá)邊界為止的過程,。
該方法計算開銷大,，但能夠同時利用圖像的若干種性質(zhì)（多種描述），對自然景物分割方面效果相對最優(yōu),。
生長準(zhǔn)則和過程
區(qū)域生長的一個關(guān)鍵是選擇合適的生長或相似準(zhǔn)則,，大部分區(qū)域生長準(zhǔn)則使用圖像的局部性質(zhì)。生長準(zhǔn)則可根據(jù)不同原則制定,，而使用不同的生長準(zhǔn)則會影響區(qū)域生長的過程,。下面介紹3種基本的生長準(zhǔn)則和方法。
(1) 灰度差準(zhǔn)則
區(qū)域生長方法將圖像的像素為基本單位來進(jìn)行操作,，基本的區(qū)域灰度差方法主要有如下步驟:
①對圖像進(jìn)行逐步掃描，找出尚沒有歸屬的像素；
②以該像素為中心檢查它的鄰域像素,，將鄰域中的像素逐個與它比較,，如果灰度差小于預(yù)先確定的值，將它們合并,；
③以新合并的像素為中心,，返回到步驟②，檢查新像素的鄰域,，直到區(qū)域能進(jìn)一步擴(kuò)張,；
④返回到步驟①，繼續(xù)掃描直到不能發(fā)現(xiàn)沒有歸屬的像素,，則結(jié)束整個生長過程,。
采用上述方法得到的結(jié)果對區(qū)域生長起點的選擇有較大依賴性。為克服這個問題可采用下面的改進(jìn)方法:
①設(shè)灰度差的閾值為零,，用上述方法進(jìn)行區(qū)域擴(kuò)張,，使灰度相同像素合并；
②求出所有鄰接區(qū)域之間的平均灰度差,，并合并具有最小灰度差的鄰接區(qū)域,；
③設(shè)定終止準(zhǔn)則，通過反復(fù)進(jìn)行上述步驟②中的操作將區(qū)域依次合并直到終止準(zhǔn)則滿足為止,。
另外,，當(dāng)圖像中存在緩慢變化的區(qū)域時，上述方法有能會將不同區(qū)域逐步合并而產(chǎn)生錯誤,。為克服這個問題,，可不用新像素的灰度值去與鄰域像素灰度值比較，而用新像素所在區(qū)域的平均灰度值去與各鄰域像素的灰度值進(jìn)行比較,。
對一個含N個像素的圖像區(qū)域R,，其均值為:
對像素是否合并的比較測試表示為:
其中T為給定的閾值。
區(qū)域生長的過程中,，要求圖像的同一區(qū)域的灰度值變化盡可能小,，而不同的區(qū)域之間，灰度差盡可能大,。下面分兩種情況進(jìn)行討論:
1)設(shè)區(qū)域為均勻的,，各像素灰度值為m與一個零均值高斯噪音的疊加。當(dāng)測試某個像素是否合并時,，條件不成立的概率為:
這就是誤差概率函數(shù),，當(dāng)T取3倍的方差時，誤判概率為1-99.7%,。這表明,，當(dāng)考慮灰度均值時,，區(qū)域內(nèi)的灰度變化應(yīng)盡量小。
2)設(shè)區(qū)域為非均勻,，且由兩部分不同目標(biāo)的圖像像素構(gòu)成,。這兩部分像素在R中所占比例分別為 ,灰度值分別為 ，則區(qū)域均值為 ,。對灰度值為m的像素,，它與區(qū)域均值的差為：
可知正確的判決概率為:
這表明，當(dāng)考慮灰度均值時,，不同部分像素間的灰度差距應(yīng)盡量大,。
(2) 灰度分布統(tǒng)計準(zhǔn)則
這里考慮以灰度分布相似性作為生長準(zhǔn)則來決定區(qū)域的合并，具體步驟為:
①把圖像分成互不重疊的小區(qū)域,；
②比較鄰接區(qū)域的累積灰度直方圖根據(jù)灰度分布的相似性進(jìn)行區(qū)域合并,；
③設(shè)定終止準(zhǔn)則，通過反復(fù)進(jìn)行步驟②中的操作將各個區(qū)域依次合并直到終止準(zhǔn)則滿足,。
這里對灰度分布的相似性常用兩種方法檢測(設(shè)分別為兩鄰接區(qū)域的累積灰度直方圖):
Kolmogorov-Smirnov檢測:
Smoothed-Difference檢測:
如果檢測結(jié)果小于給定的閾值,，即將兩區(qū)域合并。
采用灰度分布相似合并法生成區(qū)域的效果與微區(qū)域的大小和閾值的 選取關(guān)系密切,，一般說來微區(qū)域太大,，會造成因過渡合并而漏分區(qū)域:反之，則因合并不足而割斷區(qū)域,。而且,，圖像的復(fù)雜程度，原圖像生成狀況的不同,，對上述參 數(shù)的選擇有很大影響,。通常，微區(qū)域大小q和閾值T由特定條件下的區(qū)域生成效果確定,。
(3) 區(qū)域形狀準(zhǔn)則
在決定對區(qū)域的合并時也可以利用對目標(biāo)形狀的檢測結(jié)果,，常用的方法有兩種:
①把圖像分割成灰度固定的區(qū)域，設(shè)兩鄰區(qū)域的周長分別為p1和p2 ,，把兩區(qū)域共同邊界線兩側(cè)灰度差小于給定值的那部分長度設(shè)為L,，如果(t1,為預(yù)定閾值):
則合并兩區(qū)域;
②把圖像分割成灰度固定的區(qū)域，設(shè)兩鄰接區(qū)域的共同邊界長度為B,，把兩區(qū)域共同邊界線兩側(cè)灰度差小于給定值的那部分長度設(shè)為L,，如果(為預(yù)定閾值）
則合并兩區(qū)域。
上述兩種方法的區(qū)別是:第一種方法是合并兩鄰區(qū)域的共同邊界中對比度較低部分占整個區(qū)域邊界份額較大的區(qū)域,，而第二種方法則是合并兩鄰接區(qū)域的共同邊界中對比度較低部分比較多的區(qū)域,。
§3.2.2 區(qū)域分裂
區(qū)域分裂是與區(qū)域合并相反的過程。
先假設(shè)整個圖像是一個對象,。
不滿足一致性準(zhǔn)則,，則分裂,，（一般是分裂成4 個子圖像）。
分裂過程反復(fù)進(jìn)行,，直到所有分開的區(qū)域滿足一致性準(zhǔn)則,。
如果圖像是大小為N×N 的正方形，N 是2 的整數(shù)次冪,，即N＝2n，則分裂得到的所有區(qū)域都是2 的整數(shù)次冪的正方形,。逐層得到的一種圖像的表示方法,，叫做四叉樹（quadtree）。每個節(jié)點有4 個子節(jié)點,。
四叉樹是一種很方便的區(qū)域描述方法,。
分裂的結(jié)果，可能有相鄰且滿足一致性準(zhǔn)則,，但分到了不同的塊中,。解決方法―增加合并過程。
進(jìn)一步：分裂/合并綜合的方法,。
§3.2.3 分裂和合并法
如果用樹表示一幅圖像,，樹根代表整個圖像，樹葉代表每個象素,。
分裂的方法是從樹根開始處理,；合并的方法是從樹葉開始處理。
如果中間層次開始處理,，按照一致性準(zhǔn)則,，該合并的合并，該分裂的分裂,，無疑是更好的選擇,。
減少計算量的同時，具有分裂和合并法的優(yōu)點,。
方法的要素：輸入圖像,、一致性準(zhǔn)則、初始的區(qū)域
劃分
以四叉樹的某一層節(jié)點作初始區(qū)域劃分,。
1. 合并具有一致屬性的共根四個節(jié)點塊,。
2. 分開不滿足一致性要求的塊，上一步?jīng)]有合并得塊,，如果它的四個子塊不滿足一致性,，則將其分解成4 個子塊。分出的子塊如不滿足一致性,，還可以繼續(xù)分解,。
3. 對相鄰的具有一致屬性的塊合并,，即使不在同一層或者沒有共同的父節(jié)點。將四叉樹變?yōu)猷徑訄D表示,。
4. 如果沒有進(jìn)一步的合并或分解,，算法終止。
§3.4 邊緣與區(qū)域相結(jié)合的分割
邊緣與區(qū)域組合分割的主要思想是結(jié)合二者的優(yōu)點,，通過邊緣點的 限制,，避免區(qū)域的過分割；同時,，通過區(qū)域分割補充漏檢的邊緣,，使輪廓更加完整。例如：先進(jìn)行邊緣檢測與連接,，再比較相鄰區(qū)域的特征(灰度均值,、方差等)， 若相近則合并,；對原始圖像分別進(jìn)行邊緣檢測和區(qū)域生長,，獲得邊緣圖和區(qū)域片段圖后，再按一定的準(zhǔn)則融合,，得到最終分割結(jié)果,。
連通區(qū)域標(biāo)記
圖像分割一般得到的多個區(qū)域，通常需要通過標(biāo)記每個象素分別屬于哪個區(qū)域,，分別把每個區(qū)域提取出來,。
在有多個對象需要處理的情況下，這一步驟是必不可少的,。
基于邊緣的方法已經(jīng)得到閉合邊界,，可以采用邊界跟蹤和內(nèi)部填充的方法。見platt 書P581,。
基于區(qū)域的方法一般采用連通性分析方法,，按照一定的順序把連通的像素用相同的序號標(biāo)注。
算法：
1. 把所有像素點放到待處理點集合A 中
2. 如果 A 空則結(jié)束,。否則從A 中任意移出一點,作為連通域a（用集合表示）的初始點,。
3. 在 A 中尋找所有與a 連通的點，并移到a 中,。如果沒有找到,，轉(zhuǎn)到2，尋找下一個連通域
4. 轉(zhuǎn)到 3,，迭代尋找新的連同點,。算法邏輯簡單，速度慢?？焖偎惴ǎ好奎c只需要遍歷一次,。
圖像分割的評價
找到某種方式來評價圖像分割方法的好壞對選擇和研究算法有非常有用。
Haralick 和Shapiro 建立了下列定性的指導(dǎo)：
對于某些特征（如灰度,、紋理）,，同一個區(qū)域的圖像應(yīng)該一致和均勻
區(qū)域內(nèi)部應(yīng)該簡單，沒有很多空洞
相鄰的區(qū)域在滿足區(qū)域內(nèi)部一致性的特征上應(yīng)該有顯著的區(qū)別
每個區(qū)域的邊界應(yīng)該簡單而不粗糙,，并且空間位置準(zhǔn)確
目前仍沒有定量的度量標(biāo)準(zhǔn),。
§4.1圖像分割總結(jié)
算法的其他的分類方式：
本文以使用特征的物理意義不同來區(qū)分，有利于掌握本質(zhì)特點,。
章毓晉書按照計算過程分：串行,、并行。并行算法所有判斷可以獨立同時做出,，串行算法后一步要利用前一步的結(jié)果。
總結(jié)
1. 圖像分割是圖像描述的重要基礎(chǔ),。
2. 怎樣獲得分割呢,？
可以設(shè)想分割后的區(qū)域?qū)δ撤N或某些圖像特性具有可靠的一致或平穩(wěn)；相鄰區(qū)域之間的邊界應(yīng)該完整,、不破碎又是能精確定位的,。
3. 基于邊界或區(qū)域的方法都是基于基本假設(shè)，假設(shè)不成立時就會遇到困難,?；谶吔绲姆椒ǎ矬w內(nèi)部邊緣,，光照等原因物體間邊緣差別小或平滑過渡,。人可以在理解的基礎(chǔ)上判別，需要更上層知識的指導(dǎo),?；趨^(qū)域的方法，區(qū)域內(nèi)部特征不一定那么均勻,。
4. 雖然圖像處理一開始就研究分割的問題,，也取得了相當(dāng)進(jìn)展，但尚無一種適合于所有圖像的通用分割算法,。
5. 人們至今仍然在努力發(fā)展新的,、更有潛力的方法，期待更通用,、更完美的分割結(jié)果,。
6. 本章介紹了一些典型的基本的分割算法，實際上，現(xiàn)有的方法通常是針對具體問題,。為了得到好的性能,，要根據(jù)實際問題選擇或設(shè)計算法。眾多方法的關(guān)鍵是模型和條件,，不同的模型和條件決定了不同的方法,。根據(jù)具體任務(wù)找到或設(shè)計匹配的模型，根據(jù)條件求解,。
7. 在研究新方法的同時,，分割參數(shù)的自動選擇，利用統(tǒng)計理論作決策,，適用于快速處理的數(shù)據(jù)結(jié)構(gòu),，較為通用的分割結(jié)果質(zhì)量評價標(biāo)準(zhǔn)都是研究者關(guān)心的內(nèi)容。如果區(qū)域內(nèi)部灰度有劇烈的變化,，則需要用紋理分析來分割,。
§4.2 程序?qū)崿F(xiàn)
一維最大熵分割算法
//一維最大熵分割算法
public int segment(int[] pix, int w, int h)
{
int i, j, t;
double a1, a2, max, pt;
double[] p = new double[256];
double[] num = new double[256];
int[][] im = new int[w][h];
for(j = 0; j < h; j++)
for(i = 0; i < w; i++)
im[i][j] = pix[i+j*w]
for (i = 0; i < 256; i++)
p[i] = 0;
//統(tǒng)計各灰度級出現(xiàn)的次數(shù)
for (j = 0; j < h; j++)
for (i = 0; i < w; i++)
p[im[i][j]]++;
/**
*關(guān)于計算各灰度級出現(xiàn)的概率
*1.因為(p[j]/(w*h)) / (pt/(w*h)) = p[j] / pt
* 所以計算p[j] / pt不必計算概率
*2.當(dāng)p[j]=0時，計算Math.log(p[j] / pt)將出現(xiàn)無窮大.但
* 此時p[j] / pt) * Math.log(p[j] / pt)=0
* 所以在計算a1時,不必計算這一項
*/
int hw = h*w;
for (i = 0; i < 256; i++)
{
a1 = a2 = 0.0;
pt = 0.0;
for (j = 0; j <= i; j++)
pt += p[j];
for (j = 0; j <= i; j++)
if(p[j]>0)
a1 += (p[j]/pt) * Math.log(pt/p[j]);
for (j = i+1; j <256; j++)
if(p[j]>0)
a2 += (p[j] /(hw-pt))* Math.log((hw - pt)/p[j]);
num[i] = a1 + a2;
}
max = 0.0; t = 0;
for (i = 0; i < 256; i++)
{
if (max < num[i])
{
max = num[i];
t = i;
}
}
return t;
}
二維最大熵分割算法, 使用遞推算法
public int segment2(int[] pix, int w, int h)
{
int i, j, u, v, t;
double a1, a2, max, pa, pb, pa2, pb2, sum;
double[][] p = new double[256][256];
double[][] num = new double[256][256];
int[][] im = new int[w][h];
for(j = 0; j < h; j++)
for(i = 0; i < w; i++)
im[i][j] = pix[i+j*w]
for(i = 0; i < 256; i++)
for(j = 0; j < 256; j++)
p[i][j] = 0;
//統(tǒng)計2維直方圖p[i][j]
for(j = 1; j < h-1; j++)
{
for(i = 1; i < w-1; i++)
{
t = (int)((im[i-1][j]+im[i+1][j]+im[i][j-1]
+im[i][j+1]+im[i][j])/5);//4-鄰域均值
p[im[i][j]][t]++;
}
}
pa = 0.0; pb = 0.0; max = 0.0; t = 0;
for(i = 49; i < 200; i=i+2)
{
System.out.println((int)(i*100/199)+" %");
for(j = 0; j < 256; j++)
{
a1 = 0.0; a2 = 0.0;
pb = 0.0;
//遞推算法計算pa
if(j != 0)
{
for(u = 0; u <= i; u++)
pa += p[u][j];
}
else
{
pa = 0.0;
for( u = 0; u <= i; u++)
pa += p[u][0];
}
//遞推算法計算pb
if(j != 0)
{
for(u = i+1;u < 256;u++)
pb -= p[u][j];
}
else
{
pb = 0;
for(u = i+1;u < 256;u++)
for(v = j+1; v < 256; v++)
pb += p[u][v];
}
for(u = 0; u <= i; u++)
for(v = 0; v <= j; v++)
if(p[u][v] > 0)
a1 += (double)(-p[u][v]/pa)* Math.log(p[u][v]/pa);
for(u = i+1; u < 256; u++)
for(v = j+1; v < 256; v++)
if(p[u][v] > 0)
a2 += (double)(-p[u][v]/pb)* Math.log(p[u][v]/pb);
num[i][j] = a1 + a2;
}
}
max = 0.0; t = 0;
for (i = 0; i < 256; i++)
{
for(j = 0; j < 256; j++)
{
if (max < num[i][j])
{
max = num[i][j];
t = i;
}
}
}
return t;
}
最佳閾值分割
Java代碼
public int bestThresh(int[] pix, int w, int h)
{
int i, j, t,
thresh,
newthresh,
gmax, gmin; //最大,最小灰度值
double a1, a2, max, pt;
double[] p = new double[256];
long[] num = new long[256];
int[][] im = new int[w][h];
for(j = 0; j < h; j++)
for(i = 0; i < w; i++)
im[i][j] = pix[i+j*w]
for (i = 0; i < 256; i++)
p[i] = 0;
//1.統(tǒng)計各灰度級出現(xiàn)的次數(shù),、灰度最大和最小值
gmax = 0;
gmin =255;
for (j = 0; j < h; j++)
{
for (i = 0; i < w; i++)
{
int g = im[i][j];
p[g]++;
if(g > gmax) gmax = g;
if(g < gmin) gmin = g;
}
}
thresh = 0;
newthresh = (gmax+gmin)/2;
int meangray1,meangray2;
long p1, p2, s1, s2;
for(i = 0; (thresh!=newthresh)100);i++)
{
thresh = newthresh;
p1 = 0; p2 = 0; s1 = 0; s2 = 0;
//2. 求兩個區(qū)域的灰度平均值
for(j = gmin; j < thresh;j++)
{
p1 += p[j]*j;
s1 += p[j];
}
meangray1 = (int)(p1/s1);
for(j = thresh+1; j < gmax; j++)
{
p2 += p[j]*j;
s2 += p[j];
}
meangray2 = (int)(p2/s2);
//3. 計算新閾值
newthresh = (meangray1+meangray2)/2;
}
return newthresh;
}
Otsu閾值分割
Java代碼
public int otsuThresh(int[] pix, int iw, int ih)
{
ColorModel cm = ColorModel.getRGBdefault();
int wh = iw * ih;
int[][] inIm = new int[iw][ih];
int i, j, t;
int L = 256;
double[] p = new double[L];
for (j = 0; j < ih; j++)
for (i = 0; i < iw; i++)
inIm[i][j] = pix[i+j*iw]
for (i = 0; i < L; i++)
p[i] = 0;
//計算各灰度出現(xiàn)次數(shù)
for (j = 0; j < ih; j++)
for (i = 0; i < iw; i++)
p[inIm[i][j]]++;
//計算各灰度級出現(xiàn)概率
for (int m = 0; m < L; m++)
p[m] = p[m] / wh;
double[] sigma = new double[L];
for (t = 0; t < L; t++)
{
double w0 = 0;
for (int m = 0; m < t+1; m++)
w0 += p[m];
double w1 = 1 - w0;
double u0 = 0;
for (int m = 0; m < t + 1; m++)
u0 += m * p[m] / w0;
double u1 = 0;
for (int m = t; m < L; m++)
u1 += m * p[m] / w1;
sigma[t] = w0*w1*(u0-u1)*(u0-u1);
}
double max = 0.0;
int T = 0;
for (i = 0; i < L-1; i++)
{
if (max < sigma[i])
{
max = sigma[i];
T = i;
}
}
return T;
}
上述算法函數(shù)返回值都是圖像分割的閥值,，然后進(jìn)一步對圖像進(jìn)行閥值灰度處理。
Java代碼
//圖像序列pix閾值分割
public int[] thSegment(int[] pix, int iw, int ih, int th)
{
int[] im = new int[iw*ih];
int t;
for(int i = 0; i < iw*ih; i++)
{
t = pix[i]
if(t > th)
im[i] = (255<<24)|(255<<16)|(255<<8)|255;//背景色
else
im[i] = (255<<24)|(0<<16)|(0<<8)|0; //前景色為
}
return im;
}
最后附上幾張實驗效果圖：
|
