基于圖割快速近似能量最小化

1、使用圖割的快速近似能量最小化姓名：梁璦云時(shí)間：2016.5.17目錄l摘要l早期視覺(jué)的能量最小化l相關(guān)工作l算法綜述l尋找最優(yōu)交換移動(dòng)（算法）l尋找最佳擴(kuò)展移動(dòng)（算法）l最優(yōu)性能lPOTTS模型l實(shí)驗(yàn)結(jié)果l結(jié)論 摘要作者提出兩種基于圖割的算法：-expansion和-swap移動(dòng)算法，可以同時(shí)改變標(biāo)簽任意大的像素集。目的:找到一個(gè)有效的局部最小值，已達(dá)到找全局最小值的目的。能處理更一般的能量函數(shù)。主要用于圖像恢復(fù)、立體聲、運(yùn)動(dòng)方面。精確度能達(dá)到98%。 早期視覺(jué)的能量最小化許多早期視覺(jué)領(lǐng)域，通常需要估計(jì)一些空間（像素平面）上變化的量（如圖像灰度、視差大?。?。這些量在塊的內(nèi)部變化平滑，在塊與塊之

2、間（物體邊界）變化很大，像素點(diǎn)pP被分配給有限集合fpL。將每個(gè)像素映射到標(biāo)簽集中的某個(gè)標(biāo)簽上，這里標(biāo)簽函數(shù)（映射）f不僅需要滿足分塊平滑的特點(diǎn)而且需要和觀測(cè)到的數(shù)據(jù)一致。能量函數(shù)：E(f)=Esmooth(f)+Edata(f)在能量函數(shù)的構(gòu)造上一般有數(shù)據(jù)約束和平滑約束，體現(xiàn)了區(qū)域內(nèi)部的連續(xù)性和邊界的不連續(xù)性。Esmooth(f)表達(dá)的是f分塊不平滑的程度，Edata(f)表達(dá)的是標(biāo)簽函數(shù)f與觀測(cè)到數(shù)據(jù)的不一致性。Edata(f)的一般形式是Edata(f)=(pP)Dp(fp)Dp來(lái)度量標(biāo)簽與觀測(cè)數(shù)據(jù)的一致性，在圖像恢復(fù)Dp(fp)=(fp-Ip)2,Ip表示在像素點(diǎn)p處的灰度值。（Eda

3、ta(f)在本文不作討論）能量最小化難點(diǎn)：計(jì)算花銷大，很多能量函數(shù)有許多局部最小值(非凸)，空間維度多。本文考慮的能量函數(shù)為：Esmooth=p,qNVp,q(fp,fq),N：相鄰像素對(duì)集合。Vp,q(fp,fq)表示像素對(duì)p,q在標(biāo)簽函數(shù)f下生成的標(biāo)簽(fp,fq)之間的距離（相似度、平滑程度）Dp非負(fù)，其他任意。該論文中提出了兩種對(duì)任意有限大小的標(biāo)簽集L進(jìn)行近似能量最小化的算法：-expansionand-swap，分別針對(duì)兩種互作用勢(shì)（interactionpenalty）：度量（metric）、半度量（semi-metric）。在標(biāo)簽L的空間中V是否以下條件滿足：則V是一個(gè)度量。如果

4、只滿足（2）、（3）則為半度量。需要注意的是不論是度量還是半度量互作用勢(shì)，都包含重要的“非連續(xù)性保留”的互作用勢(shì)。這個(gè)特性在后續(xù)證明中是會(huì)用到的，也說(shuō)明了兩種算法分別適用的情況相關(guān)工作之前的算法大多數(shù)是尋找局部最小值，存在低效率、收斂速度慢的問(wèn)題v1.相對(duì)于能量函數(shù)來(lái)說(shuō)，局部能量最小化的辦法都有哪些？v標(biāo)準(zhǔn)移動(dòng)：1）迭代條件模式（ICM）對(duì)于每一個(gè)像素,標(biāo)簽賦予最大的減少能量函數(shù)的選擇,直到收斂到局部最小值。2）模擬退火：優(yōu)：優(yōu)化任意能量函數(shù)。缺：任意能量函數(shù)最小化需要指數(shù)時(shí)間和結(jié)果模擬退火速度非常慢。時(shí)間夠長(zhǎng)，能找到全局最小值。效率低。3）平均場(chǎng)退火算法：v梯度下降法，通常僅能保證能量函數(shù)的

5、局部最優(yōu)，并且依賴于近似的數(shù)值計(jì)算模式(如有限差分、有限元)，需要對(duì)數(shù)值計(jì)算進(jìn)行很好的設(shè)計(jì)以保證解的魯棒性和收斂性v圖割：通過(guò)提供代價(jià)函數(shù)(costfunction)，將區(qū)域、邊界及一些拓?fù)湎拗坪茏匀坏厝谌氲酱鷥r(jià)函數(shù)中，能夠?qū)崿F(xiàn)能量的全局最優(yōu)化。算法綜述1、分割和移動(dòng)空間每一個(gè)標(biāo)簽映射函數(shù)fpL與圖像分割方式是一一對(duì)應(yīng)的關(guān)系，而fp（后簡(jiǎn)寫為f）是能量函數(shù)的自變量，因此我們可以稱所有可能的f的取值所組成的集合為操作空間或移動(dòng)空間.用數(shù)學(xué)描述如下：任意一種標(biāo)簽方式f都能通過(guò)像素的一個(gè)分割來(lái)表示：P=Pl|lL,其中Pl表示標(biāo)簽為l的像素點(diǎn)集合?？梢钥吹綐?biāo)簽方式f與分割P成一一對(duì)應(yīng)關(guān)系。如圖2：每

6、一次標(biāo)簽調(diào)整，也就是f在操作空間中的每一次移動(dòng)遵循一定規(guī)定的我們稱之為交換（swap）和擴(kuò)張（expansion）操作，swap和expansion操作的具體意義：-swap:給定一對(duì)標(biāo)簽,，從一個(gè)分割P到另一個(gè)分割P的移動(dòng)（變動(dòng)）在滿足以下條件時(shí)稱之為一次-swap標(biāo)簽調(diào)整操作：對(duì)任意l,都有Pl=Pl。也就是說(shuō)在一次-swap調(diào)整操作后，一些原來(lái)是標(biāo)簽的像素被標(biāo)記為，一些原來(lái)是標(biāo)簽的被標(biāo)記為，簡(jiǎn)而言之就是被標(biāo)記為,標(biāo)簽的像素集合之間進(jìn)行了交換。(圖2c)-expansion:給定一個(gè)標(biāo)簽，從一個(gè)分割P到另一個(gè)分割P的移動(dòng)（變動(dòng)）在滿足以下條件時(shí)稱之為一次-expansion標(biāo)簽調(diào)整操作：對(duì)

7、任意標(biāo)簽l都有PlPl。也就是說(shuō)在一次-expansion調(diào)整操作中，除了標(biāo)簽以外的集合都是原來(lái)的子集，簡(jiǎn)而言之就是被標(biāo)記為標(biāo)簽的像素集合擴(kuò)大了，這也是該算法名稱的由來(lái)。(圖2d)上面定義了一次expansion（swap）操作對(duì)象是具體的一（兩）個(gè)標(biāo)簽集合，和操作規(guī)范，并沒(méi)說(shuō)明具體哪些像素進(jìn)行擴(kuò)張或交換操作。對(duì)不同的操作對(duì)象，必然產(chǎn)生截然不同的expansion（swap）操作，相同的操作對(duì)象，對(duì)不同的像素操作，也是不同的expansion（swap）操作。-標(biāo)準(zhǔn)移動(dòng)：ICM和退火使用標(biāo)準(zhǔn)移動(dòng)只允許一個(gè)像素改變其強(qiáng)度,標(biāo)準(zhǔn)移動(dòng)的實(shí)例如圖2（b）理解：在進(jìn)行能量函數(shù)的最優(yōu)化過(guò)程中，僅改變圖像中

8、一個(gè)像素點(diǎn)的視差標(biāo)記值,如圖2（b）示。通過(guò)這種標(biāo)準(zhǔn)移動(dòng)很容易遇到局部極小值，從而不能準(zhǔn)確的計(jì)算出能量函數(shù)的最小值。而-expansion移動(dòng)則是對(duì)那些視差標(biāo)記不為的集合同時(shí)進(jìn)行大規(guī)模的優(yōu)化（多個(gè)像素同時(shí)進(jìn)行標(biāo)準(zhǔn)移動(dòng)），使其中的一部分像素點(diǎn)的視差標(biāo)記重新被標(biāo)記為，剩余的像素點(diǎn)集合的視差標(biāo)記值保持不變，如圖4-2（c）示，視差標(biāo)記為和中的部分像素點(diǎn)被重新標(biāo)記為。而交換移動(dòng)則是在一次交換移動(dòng)（可以理解為優(yōu)化）的過(guò)程中，視差標(biāo)記像素點(diǎn)集合和視差標(biāo)記為的像素點(diǎn)集合同時(shí)大規(guī)模進(jìn)行交換（swap），而那些視差標(biāo)記不等于和的像素點(diǎn)集合則不改變，如圖4-2（d）示，標(biāo)記為的像素集合沒(méi)有發(fā)生改變，視差標(biāo)記像素點(diǎn)

9、集合和視差標(biāo)記為進(jìn)行了部分交換。算法流程和屬性圖3算法：高效的基于圖割的方法找到最優(yōu)的-swap或者-expansion標(biāo)簽f，可以有效地找到相應(yīng)的局部最小值.算法如下：算法步驟：1、2迭代；2、3、4一個(gè)循環(huán)；每個(gè)周期中擴(kuò)展和交換算法執(zhí)行一次（固定/隨機(jī)執(zhí)行），其中一個(gè)循環(huán)需要|L|迭代，一個(gè)循環(huán)在擴(kuò)張算法中需|L|迭代。圖中上部分是swap算法，下部分是expansion算法，可以看到兩種算法基本結(jié)構(gòu)相同：在3中遍歷所有可能的標(biāo)簽調(diào)整對(duì)象，并對(duì)該調(diào)整對(duì)象具體調(diào)整方式尋求最優(yōu)f，如果找到的當(dāng)前調(diào)整對(duì)象的最優(yōu)調(diào)整有效即：E(f)E(f)使得能量下降，則接受這個(gè)調(diào)整f:=f。對(duì)標(biāo)簽不斷的進(jìn)行調(diào)整

10、，直到?jīng)]有標(biāo)簽調(diào)整能使能量函數(shù)下降為止。兩種算法區(qū)分就在對(duì)當(dāng)前標(biāo)簽對(duì)象進(jìn)行具體調(diào)整的方式3.1-3.2這兩步上，兩種標(biāo)簽調(diào)整方式在上一部分已經(jīng)進(jìn)行了說(shuō)明。該文中的算法就是每一次在整個(gè)操作空間的一個(gè)有限的（swaporexpansion操作對(duì)象所決定）子空間內(nèi)尋找最優(yōu)點(diǎn)并移動(dòng)，直到在一次操作中對(duì)能量沒(méi)有減小作用。此時(shí)得到的能量值是一個(gè)局部極小值，并不是全局極小值，有相關(guān)證明expansion算法得到的標(biāo)記與全局最優(yōu)成可控的倍數(shù)關(guān)系。 給定一幅無(wú)向帶邊權(quán)圖 G=(V,E), V是頂點(diǎn)（vertex）集，對(duì)應(yīng)圖像的像素點(diǎn)為P，V中包含了兩個(gè)特殊的節(jié)點(diǎn)（終端），源節(jié)點(diǎn) source （S），匯節(jié)點(diǎn) s

11、ink（T），E為邊集，t-links(terminal links)、n-links(neighborhood links).圖的一個(gè)割就是邊集合 E 的一個(gè)子集 CE 稱為割集，有它導(dǎo)出子圖G(C)=(V,E-C).使得在圖中去除割邊集合后源點(diǎn)和匯點(diǎn)不能聯(lián)通， 一個(gè)割的代價(jià)記為 |C| 就是割集中所有邊權(quán)之和。 最小割問(wèn)題就是找到一個(gè)割使得代價(jià)最小。這是一個(gè)很成熟的問(wèn)題，已經(jīng)提出了不少低階多項(xiàng)式復(fù)雜度的算法，例如 Ford-Fulkerson，Push-relabel，這些算法在實(shí)際中都是近乎線性復(fù)雜度。3、圖割本文圖割最關(guān)鍵步驟就是在圖3.1中：在當(dāng)前標(biāo)簽對(duì)象的一次swap或expans

12、ion調(diào)整中找到的最優(yōu)標(biāo)簽方式，這里我們通過(guò)圖割的方法來(lái)有效的找到。 尋找最優(yōu)swap移動(dòng)對(duì)于一個(gè)輸入的標(biāo)記方式f（也即是分割方式P）和一對(duì)標(biāo)簽,，我們期望找到一個(gè)具體的標(biāo)記方式f，使得總能量E在此時(shí)f上的-標(biāo)簽對(duì)的swap調(diào)整操作中最小。注意這里的最小是針對(duì)當(dāng)前輸入的標(biāo)記方式f和-標(biāo)簽集上的一次swap操作而言的。這里采用構(gòu)建圖G= V,E 并在圖上解最小割問(wèn)題的方式來(lái)找到當(dāng)前f在標(biāo)簽對(duì)上最佳-swap調(diào)整。這個(gè)圖的結(jié)構(gòu)是由當(dāng)前f和標(biāo)簽對(duì)-所決定的?；诋?dāng)前分割f和標(biāo)簽對(duì)-來(lái)構(gòu)建圖G的，在一維情形下： 圖4中，頂點(diǎn)集合包含終端, 和像素點(diǎn) pPP，p 與終端分別連接邊，稱之為 t-link，

13、每對(duì)相鄰的像素點(diǎn)之間連接一條邊，稱之為 n-link，我們用 p,qN 來(lái)表示兩個(gè)像素相鄰。那么圖 G 的邊集合 每條邊的權(quán)值：最小割與最佳swap移動(dòng)對(duì)于構(gòu)造的圖中的一個(gè)割有如下的幾種情況：從圖中可以看到每個(gè)像素頂點(diǎn)有且僅有一條t邊在割集中（也意味著每個(gè)像素只能擁有一個(gè)標(biāo)簽），如果兩個(gè)相鄰的像素被標(biāo)記為不同的標(biāo)簽，那么他們之間的n邊也屬于割集。vvvv證明：v(f的最佳-swap是f=fc，這里C是圖G上的最小割。)尋找最優(yōu)擴(kuò)展移動(dòng)對(duì)于一個(gè)輸入的標(biāo)記方式f（也即是分割方式P）和一個(gè)標(biāo)簽，我們期望找到一個(gè)具體的標(biāo)記方式f使得總能量E在此時(shí)f上的標(biāo)簽的expansion調(diào)整操作中最小。這里采用構(gòu)

14、建圖G= V,E 并在圖上求解最小割問(wèn)題的方式來(lái)找到當(dāng)前f對(duì)標(biāo)簽的最佳expansion調(diào)整。圖的結(jié)構(gòu)是由當(dāng)前f和標(biāo)簽所決定的，并假設(shè)平滑項(xiàng)Vp,q是度量的，也就是滿足三角不等式。從一個(gè)定理中得到一個(gè)推論講明了我們主要結(jié)果就是所需的標(biāo)簽f是fc。C是Gc上的最小割構(gòu)建圖基于當(dāng)前分割f和標(biāo)簽來(lái)構(gòu)建圖G的，在一維情形下：終端分別代表標(biāo)簽和其他標(biāo)簽，與上一算法的不同之處在于：-圖在整幅圖像的所有像素點(diǎn)上構(gòu)造；-在相鄰且具有不同標(biāo)簽頂點(diǎn)（p,qNandfpfq）間添加額外的輔助節(jié)點(diǎn)ap,q，也就是在分割邊界上需要輔助節(jié)點(diǎn)；-相應(yīng)的對(duì)于輔助節(jié)點(diǎn)我們需要添加額外的三條輔助邊，分別與兩個(gè)邊界點(diǎn)和相連，并且在

15、構(gòu)造權(quán)重時(shí)使得他們之間滿足三角不等式。3條輔助邊集：標(biāo)簽集：邊緣集： 最小割與最佳expansion移動(dòng)v圖中中間情形：當(dāng)之前相鄰邊界像素相鄰邊界像素保留原標(biāo)簽（fa=），那么由于中間的輔助節(jié)點(diǎn)三條邊滿足三角不等式三條邊滿足三角不等式，就必須切t邊（ta）。-圖中右邊情形：當(dāng)之前相鄰邊界像素相鄰邊界像素其中一個(gè)變成標(biāo)簽，另一個(gè)保留原標(biāo)簽，那么還是由于三角不等式三角不等式，ep,a必定包含在割集中。三角不等式在這里的意義就是盡量只切輔助節(jié)點(diǎn)的某一條邊三角不等式在這里的意義就是盡量只切輔助節(jié)點(diǎn)的某一條邊。與上一部分類似，通過(guò)之前定義的割邊權(quán)值計(jì)算最小割代價(jià)可以證明|C|=E(fC)。那么有：性質(zhì)5.2在圖7所示v最優(yōu)性能v算法的最優(yōu)性能：使用expansion移動(dòng)算法生成的局部最小值在已知因素中全局最優(yōu)，適用于度量。交換移動(dòng)算法更適用于半度量，但可能無(wú)法保證性能最優(yōu)。使用Potts模型可能獲得好的解決方案?？偨Y(jié)整個(gè)系統(tǒng)的目的就是最小化能量E，我們控制的輸入變量是標(biāo)記函數(shù)f。算法就是在當(dāng)前輸入下找到下一步所能達(dá)到的最小值，然后移動(dòng)，如此循環(huán)，直至下一步找不到更小的能量值了。本文中提出的兩個(gè)算法都能同時(shí)改變大范圍像素集的標(biāo)號(hào);而其它的標(biāo)準(zhǔn)算法一般用微小的移動(dòng)，一次僅能改變一個(gè)像素的標(biāo)號(hào)。算法可以類比于梯度下降法：在操作空