基于圖割的能量最小化演示文稿

1、基于圖割的能量最小化v 基于圖割的能量最小化方法，在某些情況下可以提供能量的全局最小化;在其他一些情況下，即使產(chǎn)生的結(jié)果是局部最小值，這些最小值也是具有很強(qiáng)性質(zhì)的局部最小值。這種算法都包含兩個通常的約束：數(shù)據(jù)項約數(shù)據(jù)項約束束和平滑項約束平滑項約束。然而對于具體問題來說，我們可以在這兩項的基礎(chǔ)上加上符合自己問題的約束條件?；趫D割的能量最小化v它的基本原理是為能量函數(shù)構(gòu)造一個特定的圖圖，這樣在這個圖上的最小割就會最小化這個能量函數(shù)，而最小割可以有效地通過最大流最大流來計算出來。v算法總體思想和框架：圖像優(yōu)化拼接景深問題求解盡可能大的對比度求解盡可能小的拼合邊界差能量最小化方法化 圖分割最優(yōu)化 最

2、大流最小割算 基于圖割的能量最小化v 圖中的最小割也就可以最小化能量E。如果對于每一個問題，都需要針對其實際情況具體構(gòu)造一個圖，那么用圖割法來進(jìn)行能量最小化仍然是一個很復(fù)雜的問題。如果可以精確描述能通過圖割法進(jìn)行最小化的能量能量函數(shù)的特征函數(shù)的特征，并且對這些能量函數(shù)給出統(tǒng)一的構(gòu)造圖網(wǎng)絡(luò)構(gòu)造圖網(wǎng)絡(luò)的方法，那么在實際應(yīng)用中最小化問題就會變得非常簡單。基于圖割的能量最小化v利用圖分割方法快速近似地計算方程的最小能量利用圖分割方法快速近似地計算方程的最小能量v v在擴(kuò)展景深系統(tǒng)中 ，有 n幅預(yù)先載入的源景深圖像 S1 , , Sn。為了形成一幅合成圖像必須為每個像素 p選擇一幅源圖像映射Si ,代表

3、此像素點的顏色取自源圖像Si對應(yīng)位置的像素點。把像素點和源圖像之間的映射像素點和源圖像之間的映射叫做“標(biāo)記法標(biāo)記法”,并且將每個像素p的標(biāo)記指示為 約定：如果 則在合成圖像兩相鄰像素 p, q之間存在一條接縫。pfpqff基于圖割的能量最小化vBoykov提出了兩種計算局部最小量的圖分割算法：擴(kuò)張，對于一種標(biāo)記,此變動將任意一部分像素集的標(biāo)記賦為；另一種是-交換,對于一對標(biāo)記 , ,此變動將任意一部分標(biāo)記為的像素集與任意一部分標(biāo)記為的像素集之間相互交換標(biāo)記。這兩種算法都將最終生成能量最小的標(biāo)記法?；趫D割的能量最小化v標(biāo)記問題的能量函數(shù)標(biāo)記問題的能量函數(shù)一般形式為：v式中 為數(shù)據(jù)項， 表示對應(yīng)

4、像素匹配一致性程度， 為 平滑項，用于約束鄰接像素間具有一致視差。其中，p和q是像素位置，N代表某種鄰接關(guān)系， 是標(biāo)記，D是衡量標(biāo)記值與觀測值誤差的補(bǔ)償函數(shù)，V是衡量相鄰標(biāo)記不一致程度的相對勢能函數(shù)。能量最小化是一個迭代過程，在每一步，針對某個標(biāo)記或某對標(biāo)記建立相應(yīng)的圖，使得由對該圖的最小切割所得到的標(biāo)記能最小化能量。( )dataEf：, , ()()()(,)()datasmoothp qpqppp qNpPEfEfEfVffDf( )smoothEff基于圖割的能量最小化v 圖的知識圖的知識v雙終端圖雙終端圖：一個有向加權(quán)圖G=，由一個結(jié)點集合V和有向邊集合E組成。通常來說結(jié)點對應(yīng)像素、

5、立體像素或者其它特征。一個圖通常包含一些附加的被稱為“終端”的特殊結(jié)點。在立體視覺中，“終端”可以對應(yīng)于像素上的標(biāo)記集合。雙終端圖中，兩個終端分別稱為“源”s和“匯”t?；趫D割的能量最小化v邊和流邊和流：圖中所有的邊都被賦予一個權(quán)值或代價值，一個有向邊可能和有向邊的代價值不同。實際上，對于和分配不同邊的權(quán)值在基于圖像的視覺應(yīng)用方面是非常重要的。一般來說，在圖中有兩種類型的邊N-links和T-links。v N-links連接相鄰像素點或立體像素點，所以它們代表的是圖中的鄰接系統(tǒng)。其權(quán)值取決于像素之間的不連續(xù)性情況通常是由能量公式中的相對勢能繼承而來的。T-links連接圖的終端像素(或標(biāo)記

6、點)。T-link連接一個像素或者一個終端的權(quán)值取決于分配給像素點的標(biāo)記值。這些權(quán)值通常是由能量公式中的數(shù)據(jù)補(bǔ)償函數(shù)決定?；趫D割的能量最小化v割割：v 一個s-t切割(可以簡稱為割)C=S, T把圖分成兩個不相交的集合S和T，使得 , 。切割的代價為從集合S到集合T的所有邊的權(quán)值的和，即：v這樣，最小割的問題就歸結(jié)為找到包含最小代價的切割C。這個問題等同于計算從源點到匯點的最大流。,(,)(,)(,)uS vTu vEc S Tc u vsStT基于圖割的能量最小化v最大流最大流最小割算法的實現(xiàn)過程如下：最小割算法的實現(xiàn)過程如下：v 兩個不重疊的搜索樹，一條是以源s為根的S樹，一條是以匯t為

7、根的T樹。S樹中從父節(jié)點到子節(jié)點的邊都是不飽和的，而T樹中從父節(jié)點到子節(jié)點的邊也都是不飽和的。不在S和T中的節(jié)點稱為自由節(jié)點。主動節(jié)點代表S或T的外部節(jié)點（葉子節(jié)點），被動節(jié)點代表S或T的內(nèi)部節(jié)點（非葉子節(jié)點）。關(guān)鍵區(qū)別就是主動結(jié)點可以從自由結(jié)點集合中接收新的子結(jié)點來擴(kuò)展，當(dāng)然條件是沿著非飽和路徑當(dāng)然條件是沿著非飽和路徑。被動結(jié)點無法擴(kuò)展，因為它們被本搜索樹內(nèi)的其它結(jié)點封鎖著。還有一點很重要的是主動結(jié)點可以和另主動結(jié)點可以和另一個搜索樹中的結(jié)點連接一個搜索樹中的結(jié)點連接，當(dāng)一個搜索樹中的主動結(jié)點發(fā)現(xiàn)它的鄰接結(jié)點是屬于另一棵搜索樹時，就獲得了一條連接兩個搜索樹的增廣路徑?；趫D割的能量最小化v算

8、法迭代地重復(fù)以下3個步驟:v(1)生長階段：搜索樹S和T逐漸擴(kuò)展，直到它們相交 給出一條從s到t的路徑。v(2)增廣擴(kuò)展階段：已尋找到的路徑被增廣擴(kuò)展,搜索 S樹被分割為s森林。v(3)“采用”階段：搜索樹S和T被存儲下來。v 在生長階段，搜索樹是擴(kuò)展的主動結(jié)點搜索鄰主動結(jié)點搜索鄰近的非飽和邊近的非飽和邊，接收自由結(jié)點集合中的新的子結(jié)點。最新加入的結(jié)點變?yōu)橄鄳?yīng)搜索樹中主動結(jié)點集合的成員。當(dāng)給定主動結(jié)點的所有鄰接結(jié)點都被搜索完成后，該結(jié)點變?yōu)楸粍咏Y(jié)點。當(dāng)主動結(jié)點遇到一個它的鄰接結(jié)點屬于另一個樹時增長階段結(jié)束。由此找到了一個從源到匯的路徑，如圖所示?；趫D割的能量最小化v圖：算法結(jié)束時搜索樹和結(jié)點

9、的狀態(tài)v 如圖所示，這是兩個搜索樹S(紅色結(jié)點)和T(藍(lán)色結(jié)點)增長的最后階段，即當(dāng)一個從源到匯的路徑(黃色線)被找到后的情況。主動結(jié)點和被動結(jié)點分別用字母A和P來表示，自由結(jié)點用黑色圓圈表示?；趫D割的能量最小化v 在擴(kuò)展階段對增長階段所找到的路徑進(jìn)行擴(kuò)張。我們將最大可能的流從源沿路徑推向我們將最大可能的流從源沿路徑推向匯，則路徑中的一些邊就會變成飽和的匯，則路徑中的一些邊就會變成飽和的。因而一些S和T中的結(jié)點會變成孤兒結(jié)點，因為連接它們到其父結(jié)點的邊將不再有效(因為這些邊已經(jīng)飽和了)。實際上，擴(kuò)展階段會使搜索樹S和T分裂為森林。這時源s和匯t仍然是兩棵搜索樹的根，而孤兒結(jié)點則變?yōu)槠渌阉鳂涞母?jié)點。 基于圖割的能量最小化v v采用階段的主要目標(biāo)就是存儲以源s和匯t為根節(jié)點的兩棵單樹結(jié)構(gòu)。我們試圖為每個孤兒結(jié)點找一個有效的父結(jié)點。一個孤兒結(jié)點的新找到的父結(jié)點應(yīng)該和該孤兒結(jié)點一樣屬于同一個集合S或者T，這個新的父結(jié)點還應(yīng)該與一個非飽和邊界連接。如果沒有這樣的父結(jié)點，那么就把它從S或T中移除，讓它變成自由結(jié)點，孤兒節(jié)點的所