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

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

圖分割最優(yōu)化

最大流∕最小割算

基于圖割的能量最小化圖中的最小割也就可以最小化能量E。如果對(duì)于每一個(gè)問(wèn)題，都需要針對(duì)其實(shí)際情況具體構(gòu)造一個(gè)圖，那么用圖割法來(lái)進(jìn)行能量最小化仍然是一個(gè)很復(fù)雜的問(wèn)題。如果可以精確描述能通過(guò)圖割法進(jìn)行最小化的能量函數(shù)的特征，并且對(duì)這些能量函數(shù)給出統(tǒng)一的構(gòu)造圖網(wǎng)絡(luò)的方法，那么在實(shí)際應(yīng)用中最小化問(wèn)題就會(huì)變得非常簡(jiǎn)單?；趫D割的能量最小化Boykov提出了兩種計(jì)算局部最小量的圖分割算法：α擴(kuò)張，對(duì)于一種標(biāo)記α,此變動(dòng)將任意一部分像素集的標(biāo)記賦為α；另一種是α-β交換,對(duì)于一對(duì)標(biāo)記{α,β},此變動(dòng)將任意一部分標(biāo)記為α的像素集與任意一部分標(biāo)記為β的像素集之間相互交換標(biāo)記。這兩種算法都將最終生成能量最小的標(biāo)記法?；趫D割的能量最小化標(biāo)記問(wèn)題的能量函數(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è)迭代過(guò)程，在每一步，針對(duì)某個(gè)標(biāo)記或某對(duì)標(biāo)記建立相應(yīng)的圖，使得由對(duì)該圖的最小切割所得到的標(biāo)記能最小化能量。：基于圖割的能量最小化圖的知識(shí)雙終端圖：一個(gè)有向加權(quán)圖G=<V，E>，由一個(gè)結(jié)點(diǎn)集合V和有向邊集合E組成。通常來(lái)說(shuō)結(jié)點(diǎn)對(duì)應(yīng)像素、立體像素或者其它特征。一個(gè)圖通常包含一些附加的被稱為“終端”的特殊結(jié)點(diǎn)。在立體視覺(jué)中，“終端”可以對(duì)應(yīng)于像素上的標(biāo)記集合。雙終端圖中，兩個(gè)終端分別稱為“源”s和“匯”t?；趫D割的能量最小化邊和流：圖中所有的邊都被賦予一個(gè)權(quán)值或代價(jià)值，一個(gè)有向邊可能和有向邊的代價(jià)值不同。實(shí)際上，對(duì)于和分配不同邊的權(quán)值在基于圖像的視覺(jué)應(yīng)用方面是非常重要的。一般來(lái)說(shuō)，在圖中有兩種類型的邊N-links和T-links。基于圖割的能量最小化割：一個(gè)s-t切割(可以簡(jiǎn)稱為割)C=S,T把圖分成兩個(gè)不相交的集合S和T，使得,。切割的代價(jià)為從集合S到集合T的所有邊的權(quán)值的和，即：這樣，最小割的問(wèn)題就歸結(jié)為找到包含最小代價(jià)的切割C。這個(gè)問(wèn)題等同于計(jì)算從源點(diǎn)到匯點(diǎn)的最大流。基于圖割的能量最小化算法迭代地重復(fù)以下3個(gè)步驟:(1)生長(zhǎng)階段：搜索樹(shù)S和T逐漸擴(kuò)展，直到它們相交給出一條從s到t的路徑。(2)增廣擴(kuò)展階段：已尋找到的路徑被增廣擴(kuò)展,搜索S樹(shù)被分割為s森林。(3)“采用”階段：搜索樹(shù)S和T被存儲(chǔ)下來(lái)。在生長(zhǎng)階段，搜索樹(shù)是擴(kuò)展的主動(dòng)結(jié)點(diǎn)搜索鄰近的非飽和邊，接收自由結(jié)點(diǎn)集合中的新的子結(jié)點(diǎn)。最新加入的結(jié)點(diǎn)變?yōu)橄鄳?yīng)搜索樹(shù)中主動(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ù)時(shí)增長(zhǎng)階段結(jié)束。由此找到了一個(gè)從源到匯的路徑，如圖所示?；趫D割的能量最小化在擴(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ì)使搜索樹(shù)S和T分裂為森林。這時(shí)源s和匯t仍然是兩棵搜索樹(shù)的根，而孤兒結(jié)點(diǎn)則變?yōu)槠渌阉鳂?shù)的根節(jié)點(diǎn)?；趫D割的能量最小化

采用階段的主要目標(biāo)就是存儲(chǔ)以源s和匯t為根節(jié)點(diǎn)的兩棵單樹(shù)結(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è)非飽和邊界連接。如果沒(méi)有這樣的父結(jié)點(diǎn)，那么就把它從S或T中移除，讓它變成自由結(jié)點(diǎn)，孤兒節(jié)點(diǎn)的所有前子結(jié)點(diǎn)都變成孤兒結(jié)點(diǎn)。沒(méi)有孤兒結(jié)點(diǎn)留下后這個(gè)階段就停止，然后保存搜索樹(shù)S和T的結(jié)構(gòu)?；趫D割的能量最