【文章內(nèi)容簡(jiǎn)介】 分割后得到的包含很多小區(qū)域的結(jié)果。 System分割的例子 區(qū)域的表示和相似性度量Mean Shift算法一般將圖像分割成一些區(qū)域，每個(gè)區(qū)域具有一定的特征。本文采用RGB顏色空間表示每個(gè)區(qū)域，當(dāng)然，其它顏色空間，如HsI和Lab等，也可用于對(duì)區(qū)域建模。將RGB顏色空間量化為16x16x16=4096箱格，然后計(jì)算每個(gè)區(qū)域的規(guī)范化直方圖。為了度量區(qū)域之間的相似性．選擇Bhatlacha系數(shù)測(cè)量區(qū)域R和Q的相似度： 式中，和分別表示區(qū)域R和Q的直方圖。上標(biāo)u表示直方圖的第u個(gè)箱格。 目標(biāo)和背景的標(biāo)記在交互式圖像分割，用戶(hù)需要指定目標(biāo)和背景的概念。用戶(hù)可以在圖像上通過(guò)繪制標(biāo)記，如直線(xiàn)，曲線(xiàn)和筆劃等來(lái)輸入上互動(dòng)信息。含有目標(biāo)標(biāo)記像素的區(qū)域因此被稱(chēng)為目標(biāo)標(biāo)記區(qū)域，而含有背景標(biāo)記像素的區(qū)域被稱(chēng)為背景標(biāo)記區(qū)域。（b）顯示了用簡(jiǎn)單的線(xiàn)條標(biāo)記目標(biāo)和背景的例子。我們用綠色標(biāo)記來(lái)標(biāo)示目標(biāo)而使用紅色標(biāo)記來(lái)表示對(duì)象的背景。請(qǐng)注意，通常只有一小部分的目標(biāo)區(qū)域和背景區(qū)域會(huì)被用戶(hù)標(biāo)記。實(shí)際上，用戶(hù)的必要輸入越少，交互式算法就越方便越強(qiáng)大。 (a)初始分割。（b）由用戶(hù)交互式的信息輸入。綠線(xiàn)是目標(biāo)標(biāo)記和紅線(xiàn)是背景標(biāo)記。 （c）區(qū)域分割的結(jié)果。 目標(biāo)標(biāo)記完后，每個(gè)區(qū)域?qū)⒈粯?biāo)記為三種類(lèi)型的地區(qū)之一：目標(biāo)標(biāo)記區(qū)域，背景標(biāo)記區(qū)域和未標(biāo)記的區(qū)域。要完全提取物體輪廓，我們需要將每個(gè)未標(biāo)記的區(qū)域自動(dòng)正確的標(biāo)記為目標(biāo)區(qū)域或背景區(qū)域。為了方便的后續(xù)討論，我們分別用和表示目標(biāo)標(biāo)記區(qū)域集和背景標(biāo)記區(qū)域集，用表示未標(biāo)記區(qū)域集。 基于最大相似度的區(qū)域合并機(jī)制經(jīng)過(guò)目標(biāo)/背景的標(biāo)記后，準(zhǔn)確地從背景中提的目標(biāo)輪廓仍然是一個(gè)具有挑戰(zhàn)性的問(wèn)題，因?yàn)橛脩?hù)只指示了一小部分目標(biāo)/背景的特征。傳統(tǒng)的方法中，只有鄰近區(qū)域的相似性超過(guò)預(yù)設(shè)的閾值[24]才將兩個(gè)區(qū)域合并。這些方法在自適應(yīng)閾值選取上存在困難。一個(gè)過(guò)大的閾值將導(dǎo)致目標(biāo)的區(qū)域的不完全合并，而過(guò)小的閾值可以很容易造成過(guò)合并，即一些目標(biāo)區(qū)域被合并為背景區(qū)域。此外，也很難判斷何時(shí)該停止區(qū)域合并進(jìn)程。 目標(biāo)和背景的標(biāo)記分別提供了對(duì)象和背景一些關(guān)鍵特征。在于基于標(biāo)記控制的分水嶺分割算法中，標(biāo)記是算法的種子和出發(fā)點(diǎn)。類(lèi)似的，提出的區(qū)域合并方法也將從初始標(biāo)記區(qū)域開(kāi)始，然后所有未標(biāo)記區(qū)域?qū)⒅饾u標(biāo)識(shí)為目標(biāo)區(qū)域或背景區(qū)域。這個(gè)懶惰的方法提出了對(duì)齊摳出方法[25] ，它結(jié)合了基于分水嶺初始分割的圖形切割，這實(shí)際上是一個(gè)采用最大流算法的區(qū)域合并方法。在本論文中，我們提出了一種自適應(yīng)地基于極大的相似性的合并機(jī)制，以辨別在目標(biāo)和背景標(biāo)記指導(dǎo)下所有未標(biāo)記區(qū)域。設(shè)表示的一個(gè)相鄰區(qū)域，表示的所有相鄰區(qū)域的集合。所以與它所有鄰域相似性表示為，顯然。如果和的相似性為中最大的，我們就將和合并。合并規(guī)則定義如下： 若，則合并與?！　　　　　? 　　 合并規(guī)則（2）非常簡(jiǎn)單，但它確立了該區(qū)域合并進(jìn)程的基礎(chǔ)。（2）一個(gè)重要的優(yōu)點(diǎn)是它避免了合并控制中相似性閾值的預(yù)置。雖然最值運(yùn)算操作對(duì)異常值敏感 ，但我們經(jīng)驗(yàn)發(fā)現(xiàn)算法工作良好。 這主要是因?yàn)椋狈綀D是對(duì)本地區(qū)全局描述，它具有很強(qiáng)的噪音和很小的變化。 　 但是，標(biāo)記區(qū)域僅覆蓋一部分的目標(biāo)和背景，那些目標(biāo)和背景中的非標(biāo)記區(qū)域也應(yīng)當(dāng)被自動(dòng)識(shí)別并正確標(biāo)記?？偟膩?lái)說(shuō)，標(biāo)記區(qū)域包含了相應(yīng)的主要特征，因此，未標(biāo)記的目標(biāo)區(qū)域與目標(biāo)標(biāo)記區(qū)域，以及未標(biāo)記的背景區(qū)域與背景標(biāo)記區(qū)域有著更高的自相似度。所以通常情況下，非標(biāo)記的目標(biāo)區(qū)域不會(huì)與背景區(qū)域相合并。類(lèi)似地，未標(biāo)記的背景區(qū)域同樣不會(huì)與目標(biāo)區(qū)域相合并。 區(qū)域合并算法基于最大相似度的區(qū)域合并算法(Maximal Similarity based Region Merging，簡(jiǎn)稱(chēng)MSRM)，分為兩個(gè)迭代地執(zhí)行的階段，直到?jīng)]有新的區(qū)域合并發(fā)生。合并策略是盡可能合并背景區(qū)域，而保持前景區(qū)域不被合并。一旦合并完所有的背景區(qū)域，等價(jià)于提取了目標(biāo)。對(duì)每一個(gè)區(qū)域，確定其鄰域集合。對(duì)每一個(gè)，如果，求其相應(yīng)的鄰域集合，顯然。然后計(jì)算和中的每一個(gè)區(qū)域的相似度。如果和，滿(mǎn)足下式：那么和，合并成一個(gè)區(qū)域，新的區(qū)域?qū)⒑虰有相同的標(biāo)記，即：否則，和將不臺(tái)并。以上的過(guò)程迭代進(jìn)行。在每一次迭代中，集合和將被更新．其中，膨脹、收縮。當(dāng)所有背景標(biāo)記找不到新的合并對(duì)象時(shí)，迭代結(jié)束。經(jīng)過(guò)第一階段，部分屬于背景的區(qū)域互相合并。但是，仍有一些背景區(qū)域因?yàn)楸舜碎g具有更大的相似度．因此它們不能和背景標(biāo)記區(qū)域合并。（a）所示。可以看出，經(jīng)過(guò)第一階段后，大多數(shù)屬于背景的區(qū)域己被合并，但仍有一些未標(biāo)記的背景區(qū)域未和背景標(biāo)記區(qū)域合并。為了完成目標(biāo)提取，第二階段將以第一階段剩下的未標(biāo)記區(qū)域N為處理對(duì)象，其中包含部分目標(biāo)特征，同時(shí)也包含部分背景特征。未標(biāo)記區(qū)域在最大相似度規(guī)則的指導(dǎo)下互相融合，即目標(biāo)部分互相融合，背景部分互相融合。經(jīng)過(guò)第一階段臺(tái)并之后，對(duì)每一個(gè)未標(biāo)記區(qū)域(屬于目標(biāo)或背景) ，構(gòu)成它的鄰域集合，接著，對(duì)每一個(gè)，如果其滿(mǎn)足和，構(gòu)成它的鄰域集臺(tái)。那么。計(jì)算和中每一個(gè)區(qū)域的相似度。如果P和，滿(mǎn)足下式：那么將P與H，合并成一個(gè)區(qū)域否則，它們不能合并。以上過(guò)程迭代至未標(biāo)記區(qū)域中不再發(fā)生合并為止。（b）表明，經(jīng)過(guò)第二階段的合并之后，一些未標(biāo)記目標(biāo)區(qū)域和未標(biāo)記背景區(qū)域分別互相融合。接著，重復(fù)地執(zhí)行第一階段和第二階段，直到?jīng)]有新的合并發(fā)生。最后，每個(gè)區(qū)域被標(biāo)記成兩類(lèi)：目標(biāo)或背景，（d）顯示了最終提取的目標(biāo)。在絕大部分實(shí)驗(yàn)中，算法將在23個(gè)回合結(jié)束。 區(qū)域合并過(guò)程（a）第一回合第一階段(b)第一回合第二階段(c)第二回合第一階段(d)第二回合第二階段MSRM算法 輸入：初始均值漂移分割結(jié)果。輸出：最后的分割圖。當(dāng)處于最后循環(huán)的區(qū)域合并中，第1階段。將未標(biāo)記區(qū)域N與背景標(biāo)記區(qū)域合并。輸入：初始分割結(jié)果或第二個(gè)階段的合并結(jié)果。 （11）對(duì)于每個(gè)區(qū)域，構(gòu)成其鄰域集合。（12）對(duì)于每個(gè)且，構(gòu)成其鄰域集合。（13）計(jì)算，如果，那么。否則B和不合并。（14）更新和N。 （15）如果的地區(qū)無(wú)法找到新的合并對(duì)象，第一階段合并結(jié)束。否則，返回到（11）。 第2階段。自適應(yīng)地合并未標(biāo)記區(qū)域。輸入：第一階段合并的結(jié)果。 （21）對(duì)于每個(gè)區(qū)域，構(gòu)成其鄰域集。（22）對(duì)于每個(gè)，且，構(gòu)成其鄰域集合，顯然。（23）計(jì)算。如果，那么，否則，P與不再合并。（24）更新N。（25）如果在區(qū)域N無(wú)法找到新的區(qū)域合并，第二階段停止。否則返回到（21）。 結(jié)束 收斂性分析該MSRM算法是一個(gè)迭代的方法。它逐步將未標(biāo)記背景區(qū)域N分配到，然后把所有剩下的區(qū)域分配到?？梢院苋菀椎乜闯鲈摲椒ㄊ諗俊Ｎ覀冇幸韵露ɡ?。 定理1 ，即所有的N區(qū)域經(jīng)過(guò)若干迭代會(huì)被標(biāo)記為目標(biāo)或著背景。證明如下：如果在第一個(gè)階段，一個(gè)未標(biāo)記區(qū)域在其鄰域中有最大相似度區(qū)域B()，那么P與B合并，即。如果和P有最大相似度的區(qū)域B在目標(biāo)標(biāo)記區(qū)域中，那么P將保留。如果P和另一個(gè)未標(biāo)記區(qū)域P’( P’∈N)有最大相似度，那么P與P’將在第二階段合并．即P= P’ P。根據(jù)以上分析，在迭代的下一個(gè)回合，P將與或其與另一個(gè)未標(biāo)記區(qū)域P’合并，或仍保持不變。如果在某次選代后．任一個(gè)未標(biāo)記區(qū)域P在或N中找不到相應(yīng)的合并對(duì)象，算法將停止。從上面過(guò)程可以看出，隨著合并的進(jìn)行，來(lái)標(biāo)記區(qū)域中的一部分與目標(biāo)標(biāo)記區(qū)域合并，一部分將與背景標(biāo)記區(qū)域臺(tái)并，因此未標(biāo)記區(qū)域N的個(gè)數(shù)將會(huì)逐漸減少。一旦N停止減少，整個(gè)算法將停止，N中所有剩下的區(qū)域?qū)⒈粯?biāo)記為。因此，N中所有的區(qū)域全部被標(biāo)記，算法收斂。 本章小結(jié)本章首先提出對(duì)彩色圖像進(jìn)行分割的算法，將以Mean Shift算法的分割結(jié)果作為基礎(chǔ)，提出一種新的交互式區(qū)域臺(tái)并算法，來(lái)提取自然圖像中的目標(biāo)。接著對(duì)MSRM算法的背景知識(shí)做了介紹，即區(qū)域的表示和相似度的度量，以及標(biāo)記的劃分等。然后詳細(xì)描述基于最大相似度的區(qū)域合并算法，MSRM分為兩個(gè)迭代地執(zhí)行的階段，直到?jīng)]有新的區(qū)域合并發(fā)生。合并策略是盡可能合并背景區(qū)域，而保持前景區(qū)域不被合并。一旦合并完所有的背景區(qū)域，等價(jià)于提取了目標(biāo)。最后本章指出了算法的收斂性，并進(jìn)行了證明。4 系統(tǒng)設(shè)計(jì)及實(shí)驗(yàn)結(jié)果 引言MATLAB是矩陣實(shí)驗(yàn)室（Matrix Laboratory）的簡(jiǎn)稱(chēng)，是美國(guó)MathWorks公司出品的商業(yè)數(shù)學(xué)軟件，用于算法開(kāi)發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算的高級(jí)技術(shù)計(jì)算語(yǔ)言和交互式環(huán)境，主要包括MATLAB和Simulink兩大部分。 圖像分割系統(tǒng)為了驗(yàn)證本文的算法，本文設(shè)計(jì)了一個(gè)自適應(yīng)圖像分割系統(tǒng)，該系統(tǒng)由3個(gè)模塊組成，預(yù)處理模塊、標(biāo)記模塊、和區(qū)域合并模塊。該系統(tǒng)的總體框架如圖所示， 圖像分割系統(tǒng)預(yù)處理模塊標(biāo)記模塊區(qū)域合并模塊 圖像分割系統(tǒng)框架預(yù)處理模塊的功能是：將原始的圖片進(jìn)行初始分割，這里采用的Mean Shift算法，初始分割后保存的文件名為‘’。由于本文著重于區(qū)域合并算法，這里采用EDISON System[23]，它基于邊緣信息對(duì)Mean Shift方法進(jìn)行了擴(kuò)展，區(qū)域性更好，可以識(shí)別微弱邊緣。標(biāo)記模塊的功能是：根據(jù)用戶(hù)鼠標(biāo)動(dòng)作所完成的輸入，在初始分割后的圖像上做好相關(guān)的標(biāo)記。其中目標(biāo)標(biāo)記為綠色，背景標(biāo)記為紅色。區(qū)域合并模塊是本文的核心部分，其功能是：根據(jù)目標(biāo)和背景的標(biāo)記結(jié)果和初始分割得到的小區(qū)域，按最大相似度規(guī)則進(jìn)行合并，最后提取目標(biāo)的輪廓。 實(shí)驗(yàn)結(jié)果與分析通過(guò)一些有代表性的例子測(cè)試提出的算法，然后進(jìn)行魯棒性分析以及介紹可能失敗的情況，最后分析了提出算法的局限性。 實(shí)驗(yàn)結(jié)果MSRM算法本質(zhì)上是一個(gè)自適應(yīng)區(qū)域合并方法。當(dāng)用戶(hù)輸入交互式信息之后，算法將自動(dòng)地進(jìn)行區(qū)域合并，將區(qū)域標(biāo)記為目標(biāo)或背景區(qū)域。（a）表示Mean Shift分割結(jié)果及交互式信息，其中綠色的標(biāo)記表示目標(biāo)，紅色的表示背景，標(biāo)記區(qū)域僅覆蓋了目標(biāo)和背景的一部分。算法效率很高，只需很少的標(biāo)記，經(jīng)過(guò)兩階段的區(qū)域合并之后，（d）顯示，目標(biāo)被成功地提取。（a）顯示，Mean Shift分割存在嚴(yán)重的過(guò)分割。目標(biāo)相對(duì)位于圖像的中央，但是背景區(qū)域的顏色差異很大，而且目標(biāo)和背景有混疊。（b）顯示，MSRM算法仍成功地從背景中提取目標(biāo)。該算法方法可容易推廣到多目標(biāo)提取。，目標(biāo)是提取草原場(chǎng)景中的若干只幼獅。幾只獅子的體色和背景類(lèi)似，該算法仍然能使用幾個(gè)簡(jiǎn)單的標(biāo)記，成功地將它們與背景分離。 （a）到(d)顯示了圖像分割的過(guò)程 一個(gè)多目標(biāo)提取例子 魯棒性分析和失敗情況MSRM算法是一種交互式的圖像分割方法，需要由用戶(hù)輸入標(biāo)記。因此，用戶(hù)輸入的標(biāo)記一定程度上會(huì)影響分割結(jié)果。根據(jù)大量的實(shí)驗(yàn)，發(fā)現(xiàn)只要標(biāo)記能夠覆蓋目標(biāo)的主要特征， MSRM通常能夠可靠地提取目標(biāo)。，MSRM算法執(zhí)行效果非常好。（b）顯示，用更少的標(biāo)記，仍可以提取天鵝的基本輪廓。．得到了相同的結(jié)果。但是，當(dāng)陰影出現(xiàn)、目標(biāo)和背景間存在著模糊區(qū)域或?qū)Ρ榷容^低時(shí)，MSRM算法分割性能會(huì)有所下降。例如，人物目標(biāo)和鮮艷的背景比較相似，在一些區(qū)域，提出算法的分割結(jié)果將目標(biāo)的一部分劃分為背景。其次，提出的算法以Mean Shift算法的分割結(jié)果作為基