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

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

圖分割最優(yōu)化

最大流∕最小割算

基于圖割的能量最小化它的基本原理是為能量函數(shù)構(gòu)造一個(gè)特定的圖2基于圖割的能量最小化圖中的最小割也就可以最小化能量E。如果對(duì)于每一個(gè)問題，都需要針對(duì)其實(shí)際情況具體構(gòu)造一個(gè)圖，那么用圖割法來進(jìn)行能量最小化仍然是一個(gè)很復(fù)雜的問題。如果可以精確描述能通過圖割法進(jìn)行最小化的能量函數(shù)的特征，并且對(duì)這些能量函數(shù)給出統(tǒng)一的構(gòu)造圖網(wǎng)絡(luò)的方法，那么在實(shí)際應(yīng)用中最小化問題就會(huì)變得非常簡(jiǎn)單?；趫D割的能量最小化圖中的最小割也就可以最小3基于圖割的能量最小化利用圖分割方法快速近似地計(jì)算方程的最小能量

在擴(kuò)展景深系統(tǒng)中，有n幅預(yù)先載入的源景深圖像S1,…,Sn。為了形成一幅合成圖像必須為每個(gè)像素p選擇一幅源圖像映射Si,代表此像素點(diǎn)的顏色取自源圖像Si對(duì)應(yīng)位置的像素點(diǎn)。把像素點(diǎn)和源圖像之間的映射叫做“標(biāo)記法”,并且將每個(gè)像素p的標(biāo)記指示為約定：如果則在合成圖像兩相鄰像素p,q之間存在一條接縫。基于圖割的能量最小化4基于圖割的能量最小化Boykov提出了兩種計(jì)算局部最小量的圖分割算法：α擴(kuò)張，對(duì)于一種標(biāo)記α,此變動(dòng)將任意一部分像素集的標(biāo)記賦為α；另一種是α-β交換,對(duì)于一對(duì)標(biāo)記{α,β},此變動(dòng)將任意一部分標(biāo)記為α的像素集與任意一部分標(biāo)記為β的像素集之間相互交換標(biāo)記。這兩種算法都將最終生成能量最小的標(biāo)記法。基于圖割的能量最小化Boykov提出了兩種計(jì)算局部最小量的圖5基于圖割的能量最小化標(biāo)記問題的能量函數(shù)一般形式為：式中為數(shù)據(jù)項(xiàng)，表示對(duì)應(yīng)像素匹配一致性程度，為平滑項(xiàng)，用于約束鄰接像素間具有一致視差。其中，p和q是像素位置，N代表某種鄰接關(guān)系，是標(biāo)記，D是衡量標(biāo)記值與觀測(cè)值誤差的補(bǔ)償函數(shù)，V是衡量相鄰標(biāo)記不一致程度的相對(duì)勢(shì)能函數(shù)。能量最小化是一個(gè)迭代過程，在每一步，針對(duì)某個(gè)標(biāo)記或某對(duì)標(biāo)記建立相應(yīng)的圖，使得由對(duì)該圖的最小切割所得到的標(biāo)記能最小化能量。：基于圖割的能量最小化標(biāo)記問題的能量函數(shù)一般形式為：：6基于圖割的能量最小化圖的知識(shí)雙終端圖：一個(gè)有向加權(quán)圖G=<V，E>，由一個(gè)結(jié)點(diǎn)集合V和有向邊集合E組成。通常來說結(jié)點(diǎn)對(duì)應(yīng)像素、立體像素或者其它特征。一個(gè)圖通常包含一些附加的被稱為“終端”的特殊結(jié)點(diǎn)。在立體視覺中，“終端”可以對(duì)應(yīng)于像素上的標(biāo)記集合。雙終端圖中，兩個(gè)終端分別稱為“源”s和“匯”t。基于圖割的能量最小化圖的知識(shí)7基于圖割的能量最小化邊和流：圖中所有的邊都被賦予一個(gè)權(quán)值或代價(jià)值，一個(gè)有向邊可能和有向邊的代價(jià)值不同。實(shí)際上，對(duì)于和分配不同邊的權(quán)值在基于圖像的視覺應(yīng)用方面是非常重要的。一般來說，在圖中有兩種類型的邊N-links和T-links。基于圖割的能量最小化8N-links連接相鄰像素點(diǎn)或立體像素點(diǎn)，所以它們代表的是圖中的鄰接系統(tǒng)。其權(quán)值取決于像素之間的不連續(xù)性情況通常是由能量公式中的相對(duì)勢(shì)能繼承而來的。T-links連接圖的終端像素(或標(biāo)記點(diǎn))。T-link連接一個(gè)像素或者一個(gè)終端的權(quán)值取決于分配給像素點(diǎn)的標(biāo)記值。這些權(quán)值通常是由能量公式中的數(shù)據(jù)補(bǔ)償函數(shù)決定?；趫D割的能量最小化-演示文稿ppt課件9基于圖割的能量最小化割：一個(gè)s-t切割(可以簡(jiǎn)稱為割)C=S,T把圖分成兩個(gè)不相交的集合S和T，使得,。切割的代價(jià)為從集合S到集合T的所有邊的權(quán)值的和，即：這樣，最小割的問題就歸結(jié)為找到包含最小代價(jià)的切割C。這個(gè)問題等同于計(jì)算從源點(diǎn)到匯點(diǎn)的最大流。基于圖割的能量最小化割：10基于圖割的能量最小化最大流∕最小割算法的實(shí)現(xiàn)過程如下：兩個(gè)不重疊的搜索樹，一條是以源s為根的S樹，一條是以匯t為根的T樹。S樹中從父節(jié)點(diǎn)到子節(jié)點(diǎn)的邊都是不飽和的，而T樹中從父節(jié)點(diǎn)到子節(jié)點(diǎn)的邊也都是不飽和的。不在S和T中的節(jié)點(diǎn)稱為自由節(jié)點(diǎn)。主動(dòng)節(jié)點(diǎn)代表S或T的外部節(jié)點(diǎn)（葉子節(jié)點(diǎn)），被動(dòng)節(jié)點(diǎn)代表S或T的內(nèi)部節(jié)點(diǎn)（非葉子節(jié)點(diǎn)）。關(guān)鍵區(qū)別就是主動(dòng)結(jié)點(diǎn)可以從自由結(jié)點(diǎn)集合中接收新的子結(jié)點(diǎn)來擴(kuò)展，當(dāng)然條件是沿著非飽和路徑。被動(dòng)結(jié)點(diǎn)無法擴(kuò)展，因?yàn)樗鼈儽槐舅阉鳂鋬?nèi)的其它結(jié)點(diǎn)封鎖著。還有一點(diǎn)很重要的是主動(dòng)結(jié)點(diǎn)可以和另一個(gè)搜索樹中的結(jié)點(diǎn)連接，當(dāng)一個(gè)搜索樹中的主動(dòng)結(jié)點(diǎn)發(fā)現(xiàn)它的鄰接結(jié)點(diǎn)是屬于另一棵搜索樹時(shí)，就獲得了一條連接兩個(gè)搜索樹的增廣路徑?；趫D割的能量最小化最大流∕最小割算法的實(shí)現(xiàn)過程如下：11基于圖割的能量最小化算法迭代地重復(fù)以下3個(gè)步驟:(1)生長(zhǎng)階段：搜索樹S和T逐漸擴(kuò)展，直到它們相交給出一條從s到t的路徑。(2)增廣擴(kuò)展階段：已尋找到的路徑被增廣擴(kuò)展,搜索S樹被分割為s森林。(3)“采用”階段：搜索樹S和T被存儲(chǔ)下來。在生長(zhǎng)階段，搜索樹是擴(kuò)展的主動(dòng)結(jié)點(diǎn)搜索鄰近的非飽和邊，接收自由結(jié)點(diǎn)集合中的新的子結(jié)點(diǎn)。最新加入的結(jié)點(diǎn)變?yōu)橄鄳?yīng)搜索樹中主動(dòng)結(jié)點(diǎn)集合的成員。當(dāng)給定主動(dòng)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)都被搜索完成后，該結(jié)點(diǎn)變?yōu)楸粍?dòng)結(jié)點(diǎn)。當(dāng)主動(dòng)結(jié)點(diǎn)遇到一個(gè)它的鄰接結(jié)點(diǎn)屬于另一個(gè)樹時(shí)增長(zhǎng)階段結(jié)束。由此找到了一個(gè)從源到匯的路徑，如圖所示?；趫D割的能量最小化算法迭代地重復(fù)以下3個(gè)步驟:12基于圖割的能量最小化圖：算法結(jié)束時(shí)搜索樹和結(jié)點(diǎn)的狀態(tài)如圖所示，這是兩個(gè)搜索樹S(紅色結(jié)點(diǎn))和T(藍(lán)色結(jié)點(diǎn))增長(zhǎng)的最后階段，即當(dāng)一個(gè)從源到匯的路徑(黃色線)被找到后的情況。主動(dòng)結(jié)點(diǎn)和被動(dòng)結(jié)點(diǎn)分別用字母A和P來表示，自由結(jié)點(diǎn)用黑色圓圈表示?；趫D割的能量最小化13基于圖割的能量最小化在擴(kuò)展階段對(duì)增長(zhǎng)階段所找到的路徑進(jìn)行擴(kuò)張。我們將最大可能的流從源沿路徑推向匯，則路徑中的一些邊就會(huì)變成飽和的。因而一些S和T中的結(jié)點(diǎn)會(huì)變成孤兒結(jié)點(diǎn)，因?yàn)檫B接它們到其父結(jié)點(diǎn)的邊將不再有效(因?yàn)檫@些邊已經(jīng)飽和了)。實(shí)際上，擴(kuò)展階段會(huì)使搜索樹S和T分裂為森林。這時(shí)源s和匯t仍然是兩棵搜索樹的根，而孤兒結(jié)點(diǎn)則變?yōu)槠渌阉鳂涞母?jié)點(diǎn)。基于圖割的能量最小化14基于圖割的能量最小化

采用階段的主要目標(biāo)就是存儲(chǔ)以源s和匯t為根節(jié)點(diǎn)的兩棵單樹結(jié)構(gòu)。我們?cè)噲D為每個(gè)孤兒結(jié)點(diǎn)找一個(gè)有效的父結(jié)點(diǎn)。一個(gè)孤兒結(jié)點(diǎn)的新找到的父結(jié)點(diǎn)應(yīng)該和該孤兒結(jié)點(diǎn)一樣屬于同一個(gè)集合S或者T，這個(gè)新的父結(jié)點(diǎn)還應(yīng)該與一個(gè)非飽和邊界連接。如果沒有這樣的父結(jié)點(diǎn)，那么就把它從S或T中移除，讓它變成自由結(jié)點(diǎn)，孤兒節(jié)點(diǎn)的所有前子結(jié)點(diǎn)都變成孤兒結(jié)點(diǎn)。沒有孤兒結(jié)點(diǎn)留下后這