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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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