圖象分割方法2006

圖像分割潘春洪,唐明{chpan,tangm}@圖像理解的基本構(gòu)成知識(shí)庫表示與描述預(yù)處理分割低級處理高級處理中級處理識(shí)別與解釋結(jié)果圖像獲取問題1.什么是圖像分割圖像分割是將圖像空間R劃分為n個(gè)互不重疊的區(qū)域其中P(Ri)為作用于Ri

中所有象素的相似性邏輯謂詞。定義實(shí)例1.2.3.4.2.圖像分割的重要性和難度計(jì)算視覺低層視覺高層視覺中層視覺圖像分割中層視覺：獲得圖像中物體的2.5維描述低層視覺：獲得要素圖（二維圖像中的邊緣點(diǎn)、直線段、曲線段、頂點(diǎn)、紋理等）高層視覺：獲得圖像中物體的三維描述計(jì)算機(jī)視覺的其他領(lǐng)域醫(yī)學(xué)圖像處理遙感圖像處理目標(biāo)跟蹤生物特征識(shí)別等等分割依賴于高層視覺分割依賴于低層視覺分割依賴于高層視覺（續(xù)）圖像分割是中層視覺中的最基本問題，也是計(jì)算視覺和圖像理解中的最基本問題之一。它還是該領(lǐng)域國際學(xué)術(shù)界公認(rèn)的將會(huì)長期存在的最困難的問題之一。圖像分割之所以困難的一個(gè)重要原因是其并不完全屬于圖像特征提取問題，它還涉及到各種圖像特征的知覺組織。從一般意義上來說，只有對圖像內(nèi)容的徹底理解，才能產(chǎn)生完美的分割。通過限制圖像的類型，可以降低圖像分割的難度。圖像分割的基本思路從簡到難，逐級分割；控制背景環(huán)境，降低分割難度；把焦點(diǎn)放在增強(qiáng)感興趣對象，縮小不相干圖像成分的干擾上。

從簡到難，逐級分割

分割矩形區(qū)域

定位牌照

定位文字

控制背景環(huán)境，降低分割難度背景環(huán)境:路面、天空

把焦點(diǎn)放在增強(qiáng)感興趣對象，縮小不相干圖像成分的干擾上感興趣的對象： 汽車牌照不相干圖像成分： 非矩形區(qū)域圖像分割的基本策略基于灰度值的兩個(gè)基本特性：不連續(xù)性——區(qū)域之間相似性——區(qū)域內(nèi)部

根據(jù)圖像像素灰度值的不連續(xù)性：先找到點(diǎn)、線（寬度為1）、邊（不定寬度）再確定區(qū)域。

根據(jù)圖像像素灰度值的相似性：通過選擇閾值，找到灰度值相似的區(qū)域區(qū)域的外輪廓就是對象的邊。對圖像特征空間做分類的方法分割算法的大致分類（共五類）基于區(qū)域的方法（區(qū)域生長等）

基于函數(shù)優(yōu)化的方法（Bayesian等）綜合考慮邊緣和區(qū)域信息的混合分割方法基于邊緣的方法（邊緣檢測/主動(dòng)邊緣）自動(dòng)閾值方法閾值方法的本質(zhì)

閾值方法并不要求直方圖必須同時(shí)包含峰和谷。Pixelh?3.1全局閾值方法

眾數(shù)法（J.M.S.Prewitt,etal.,1966,

Ann.NewYorkAcad.Sci.）已知圖像僅包含具有明顯灰度差別的目標(biāo)和背景。此時(shí)灰度直方圖通常為雙峰單谷型。取谷底點(diǎn)為閾值即可完成分割。

Otsu法（N.Otsu,1979,IEEET-SMC）在直方圖上定義類內(nèi)方差和類間方差其中，Pi為第

i類出現(xiàn)的概率，μi為第

i類的均值，μ為混合分布的均值?？傮w方差為三個(gè)方差的關(guān)系為求使類間方差(分離度)盡量大而類內(nèi)方差盡量小的閾值t。三者等價(jià)。取計(jì)算量最小的η(t)：定義如下函數(shù)Otsu法可以應(yīng)用于多維特征空間中?；陟氐姆椒ā狵SW法（J.N.Kapur,etal.,1985,CVGIP）設(shè)直方圖上閾值t兩側(cè)的分布分別為pi、qi，以及選擇滿足下式的t*作為分割閾值上述熵的理論分析十分困難，分割意義也不十分明確。正因?yàn)槿绱?，我們也可以基于矩不變的方法（W.Tsai,1985,CVGIP）設(shè)圖像f的第i階矩為（i=1,2,3）其中zj為灰度直方圖中的第j個(gè)灰度值。設(shè)分割后圖象f’的第i階矩為其中zj為分割后灰度直方圖中的第j個(gè)灰度值。此時(shí)只有兩個(gè)灰度級。設(shè)，i=1,2,3,有解上述方程組即得。從而可以確定劃分目標(biāo)和背景的閾值。

最小誤分閾值法（Frank,etal.,1995）假設(shè)概率密度為混合Guassian：最小均方擬合：用優(yōu)化方法（如共軛梯度法或牛頓法）求得Pi，μi，σi，即得pi(g)。求交點(diǎn)t：取對數(shù)，整理得：去掉一個(gè)不適當(dāng)?shù)慕饧纯傻玫浇狻?/p>

近似最小誤分閾值法（J.Kittler,etal.,1986,PR）利用相對熵的概念定義Gaussian函數(shù)與直方圖之間的距離：設(shè)為第i類的Guassian擬合函數(shù)。去掉常數(shù)項(xiàng)，整理得新的表達(dá)式這里J(T)越小，則兩個(gè)Guassian函數(shù)的重疊面積就越小。于是求τ，使得其他方法1)概率松弛法（A.Rosenfeld,etal.,1981）這里，m是類數(shù)，r為已迭代次數(shù)，pij表示第i個(gè)象素屬于第j類的概率，qij是根據(jù)其它象素所屬類別對pij的調(diào)整量。這里，n是象素個(gè)數(shù)，c(i,j;h,k)是相容性函數(shù)，表示第

i

個(gè)象素屬于第

j類與第h個(gè)象素屬于第k類的相容程度。體現(xiàn)了其它象素所屬區(qū)域?qū)Φ趇個(gè)象素屬于第j個(gè)區(qū)域的綜合影響。的設(shè)置（以兩分分割為例）設(shè)d和l分別為原始圖象中最黑和最亮的灰度，zi為第i個(gè)象素的灰度，則相容性的設(shè)計(jì)？相容性函數(shù)的例子：染色體圖象海面＋云層圖象坦克紅外圖象2)直方圖變換法a.依據(jù)各個(gè)象素的局部特征對各象素灰度加權(quán)（如1/(1+△2),D.Mason,etal.,1975）。b.利用四分樹法對目標(biāo)和背景的灰度平滑后再建立直方圖（A.Y.Wu,etal.,1982）。目的：獲得具有更深的谷和更尖銳的峰的直方圖。3)引入二階灰度統(tǒng)計(jì)量灰度共生矩陣中元素的含義mij表示在圖象中灰度為

i

和

j、間距為

d

個(gè)象素、與水平方向夾角為φ的象素對的數(shù)目。如

M(1,φ)

中的元素

mij表示4-鄰域相鄰象素中灰度分別為

i

和

j

的象素對的個(gè)數(shù)。a.N.Ahuja,etal,1975構(gòu)造兩個(gè)新直方圖：h1：對M對角線附近的元素，h2：對非M對角線附近的元素。在h1

和h2

的谷峰重疊處選擇一個(gè)閾值。b.F.Deravi,etal,1983這里，x為h或v或vh，Tij是Tx的元素。最優(yōu)閾值τ：可以認(rèn)為，圖像邊緣附近（其灰度大多位于灰度直方圖的谷底附近）應(yīng)當(dāng)具有最多的4-相鄰的不同類象素對。于是有目標(biāo)函數(shù)：全局閾值方法比較大量實(shí)驗(yàn)表明，基于簡單統(tǒng)計(jì)量的方法往往可以獲得較好的分割結(jié)果。而基于熵的方法應(yīng)用于有噪聲圖象時(shí)結(jié)果一般較差。c.利用灰度和均值構(gòu)造二維直方圖，并在其上定義統(tǒng)計(jì)量。3.2局部閾值方法將圖像分塊，分別用全局閾值方法分割，最后再綜合。3.3遞歸閾值方法（R.Ohlander,1975）3.4動(dòng)態(tài)K-L變換閾值分割方法（Y.Ohta,etal,1980）以RGB三基色的K-L變換為特征，采用遞歸閾值方法分割彩色圖像。設(shè)S為待分割區(qū)域，對其RGB做K-L變換，得到新的特征x1,x2,x3。利用它們對S分割。

重要現(xiàn)象

問題思考

找出上述方法中你認(rèn)為缺陷最大的一個(gè)，并提出修改意見；

比較各方法的優(yōu)缺點(diǎn)，并指出各適合哪類圖像的分割；

提出自己基于直方圖的分割方法。4.基于邊緣的方法4.1邊緣檢測算子4.2主動(dòng)邊緣模型

經(jīng)典主動(dòng)邊緣模型（M.Kass,etal,1988）

測地線主動(dòng)邊緣模型（V.Caselles,etal,ICCV,1995）一些其它的手工交互方法：LevelSetIntelligentPaintIntelligentScissorsMatting(Poisson,Bayesian,etc.)ImageContourEditingGraphCut(GrabCut)Lazysnapping一些手工交互方法的比較ActiveContourIntelligentScissorsGraphCutNURBS-HMM5.基于區(qū)域的方法

區(qū)域生長

a|b-------------------------c|da）原始X線探傷圖象b）種子區(qū)域c）生長結(jié)果d）缺陷區(qū)邊緣上頁圖a的直方圖。種子區(qū)域由灰度為255的象素構(gòu)成。從種子區(qū)域開始以8-鄰域方式向外生長，只要一個(gè)象素的灰度g與種子點(diǎn)的灰度差小于65(即g≥191)，即將該象素歸入目標(biāo)區(qū)。

分裂與合并

R1R2R3R41R42R43R44RR1R2R3R4R41R42R43R44

分水嶺分割法標(biāo)準(zhǔn)步驟：1）將圖象看作地形圖；2）在每一個(gè)極小點(diǎn)處“打一個(gè)孔”；3）以一致的速率從小孔向外“噴水”，并始終保持地形中所有的水位一致；4）不同盆地的水相遇時(shí)則筑壩，并且隨著水位的不斷升高，壩也升高；5）當(dāng)水位達(dá)到地形的最高點(diǎn)時(shí)算法終止。缺陷：可能出現(xiàn)“過度分割”問題。a|b

圖a為原始電泳圖象，圖b為標(biāo)準(zhǔn)分水嶺分割法分割圖a的梯度圖象的結(jié)果。帶標(biāo)記的分水嶺算法－“泉眼”的位置是(自動(dòng)或手工)指定的，而不是由極小點(diǎn)確定的。這樣可以避免“過度分割”問題。電泳圖象的分割方法1）濾波；2）選擇平緩的“盆地”底部作為標(biāo)記(紅斑)；3）調(diào)用分水嶺算法確定分水線(黃線)；4）在每個(gè)分水線分出的小區(qū)域內(nèi)，利用前述閾值法或分水嶺法等完成分割。6.基于函數(shù)優(yōu)化的方法基于成對方式聚類的紋理圖像分割（T.Hofmann,etal,ICIP’96,T-PAMI,1998）需優(yōu)化的函數(shù)：其中，M={Miv}(N×K)為標(biāo)記矩陣，Miv

表示象素i

用v

標(biāo)記，Dij

為一對象素

i、j間的紋理不相似性度量，N為象素個(gè)數(shù)，K

為標(biāo)號(hào)個(gè)數(shù)（分類數(shù)），Ni

為象素

i

的鄰域。思考：Dij的定義？公式中的Σ()表示象素i的鄰域中和i具有相同標(biāo)號(hào)的象素與i之間的平均不相似性。于是H(M)就表示整幅圖象上的不相似性。這種不相似性自然是越小越好。即求標(biāo)記矩陣M，使得:上式需要復(fù)雜的尋優(yōu)算法來優(yōu)化。實(shí)驗(yàn)結(jié)果2)基于Bayesian的圖象分割方法設(shè)有定義在離散網(wǎng)格Λ上的標(biāo)量離散隨機(jī)場為隨機(jī)變量。定義離散網(wǎng)格Λ上的鄰域系：為x的鄰域：定義象素團(tuán)(clique)：

鄰域和象素團(tuán)(clique)的例子如果是單網(wǎng)格點(diǎn)，或是由兩兩相鄰的網(wǎng)格點(diǎn)組成，則

C是定義在Λ上的一個(gè)象素團(tuán)。

Markov隨機(jī)場（MRF）一個(gè)隨機(jī)場被稱為關(guān)于鄰域系N的Markov隨機(jī)場，如果即只由xi的鄰域決定。用局部條件概率描述Markov隨機(jī)場很不方便。

Gibbs隨機(jī)場（GRF）一個(gè)隨機(jī)場被稱為關(guān)于鄰域系N的Gibbs隨機(jī)場，如果其中，這里，T為溫度參數(shù)，U為Gibbs能量，VC為象素團(tuán)C的能量，O為象素團(tuán)集合。

Markov隨機(jī)場和Gibbs隨機(jī)場的等價(jià)性Hammersley-Clifford(H-C)定理：設(shè)N是鄰域系。z(x)是關(guān)于N的Markov隨機(jī)場，當(dāng)且僅當(dāng)z(x)是關(guān)于N的Gibbs隨機(jī)場。希望得到一個(gè)分割標(biāo)號(hào)隨機(jī)場z，z(x)=l表示象素x屬于l-th類。這里，l=1,…,K?；贐ayesian的分割方法

maximumaposterioriprobability(MAP)設(shè)有含加性噪音的圖象：根據(jù)Bayes公式，希望下式左邊取極大：要求p(z|g)極大，就要求條件概率p(g|z)和先驗(yàn)概率p(z)的積為極大。采用4-鄰域來估計(jì)兩個(gè)概率。假設(shè)圖象服從卡片紙模型。1)先驗(yàn)概率模型p(z)的估計(jì)：對于單個(gè)網(wǎng)格點(diǎn)的象素團(tuán)，如果z(x)=l，pl

是l-th類區(qū)域出現(xiàn)的先驗(yàn)概率，它反映了我們對于不同類區(qū)域出現(xiàn)概率的先驗(yàn)知識(shí)。pl越小，先驗(yàn)概率越大。對于雙網(wǎng)格點(diǎn)象素團(tuán)，以如下方式強(qiáng)加象素團(tuán)能量其中β>0。β越大，平滑性約束就越強(qiáng)。2)條件概率模型p(g|z)的估計(jì)：設(shè)μl

(x)（l=1,2,…,K）是l-th類區(qū)域的灰度均值，則有：對上式利用模擬退火算法優(yōu)化，求出最優(yōu)分割標(biāo)號(hào)集z和μl

(x)，這里

l=1,2,…,K。綜合1)、2)所述，得后驗(yàn)概率2)基于“均值移動(dòng)”的圖象分割方法(D.Comaniciuet.al,ICCV’99,T-PAMI,2002)a)均值移動(dòng)（MeanShift）思想核函數(shù)b)均值移動(dòng)濾波實(shí)驗(yàn)結(jié)果c)均值移動(dòng)分割實(shí)驗(yàn)結(jié)果1)通過區(qū)域均勻性和類不確定性最小化求取最優(yōu)閾值(MHUE)（P.K.Saha,etal,T-PAMI,2001）7.綜合考慮邊緣和區(qū)域的方法假設(shè)A：在任何具有模糊邊界的圖像中，在利用最優(yōu)閾值得到的區(qū)域劃分中，類不確定性高的象素出現(xiàn)在物體的邊緣附近。a)基于灰度的類不確定性的確定設(shè)Fo,t和

Fb,t分別是閾值為t時(shí)的物體和背景象素集。假設(shè)物體和背景的灰度都服從Gaussian分布，c為一個(gè)象素，C為圖象空間，|X|表示集