[發(fā)明專利]一種基于對偶分解的三維相位解纏方法

在審

• 申請?zhí)枺?/td>: 201810437147.5
• 申請日: 2018-05-09
• 公開（公告）號: CN108615264A
• 公開（公告）日: 2018-10-02
• 發(fā)明（設(shè)計(jì)）人: 董建武;余肇飛;孫波;司成祥;姜棟;張建松;胡曉旭;張騰;劉健;毛蔚軒;劉云昊
• 申請（專利權(quán)）人: 國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心;北京大學(xué)
• 主分類號: G06T19/20
• 分類號: G06T19/20;G06T17/00
• 代理公司: 北京久維律師事務(wù)所 11582
• 代理人: 邢江峰

1.一種基于對偶分解的三維相位解纏方法，包括問題定義(1)和子問題并行求解(2)。

2.根據(jù)權(quán)利要求書1所述一種基于對偶分解的三維相位解纏方法，其特征在于：

問題定義(1)如下：

將能量函數(shù)E(x)分解為N個(gè)子問題{Eⁱ}

其中xⁱ是子問題Eⁱ的輔助變量，x|_i是x子向量，x|_i包含的變量為子問題Eⁱ對應(yīng)的變量。為了求解優(yōu)化問題，引入拉格朗日乘子

對上式關(guān)于x求最小化，得到以下對偶函數(shù)

其中，N(p)為包含節(jié)點(diǎn)p的子問題集合。原能量函數(shù)E(x)被分解為N個(gè)可以并行求解的獨(dú)立子問題，其中每一個(gè)子問題為

。

3.根據(jù)權(quán)利要求書1所述一種基于對偶分解的三維相位解纏方法，其特征在于：

子問題并行求解(2)如下：

由于子問題的能量勢函數(shù)滿足次模性不等式，采用圖切法求解子問題。能量最小化問題包含節(jié)點(diǎn)勢函數(shù)和邊勢函數(shù)，為了簡化符號，依然用Eⁱ(xⁱ)表示引入節(jié)點(diǎn)勢函數(shù)后的第i個(gè)子問題的能量函數(shù)

為了利用圖切法求解上述能量函數(shù)，需要構(gòu)造一個(gè)帶有權(quán)重的有向圖G(V,E)，假設(shè)子問題Eⁱ對應(yīng)的MRF含有N個(gè)節(jié)點(diǎn)，則圖G包含有N+2個(gè)節(jié)點(diǎn)，圖G的N個(gè)非終端節(jié)點(diǎn)與MRF一一對應(yīng)，另外兩個(gè)終端節(jié)點(diǎn)為源節(jié)點(diǎn)s和匯節(jié)點(diǎn)t，圖G邊的權(quán)重根據(jù)能量函數(shù)賦值，將能量函數(shù)的每一個(gè)節(jié)點(diǎn)勢函數(shù)和邊勢函數(shù)通過一定的規(guī)則依次賦值到圖G，然后將賦值后的邊的權(quán)重累加，最終得到帶權(quán)重的圖G。

4.根據(jù)權(quán)利要求書3所述一種基于對偶分解的三維相位解纏方法，其特征在于：子問題并行求解(2)包括節(jié)點(diǎn)勢函數(shù)的權(quán)重賦值(21)和邊勢函數(shù)的權(quán)重賦值(22)。

5.根據(jù)權(quán)利要求書3所述一種基于對偶分解的三維相位解纏方法，其特征在于：

節(jié)點(diǎn)勢函數(shù)的權(quán)重賦值(21)如下：

考慮節(jié)點(diǎn)勢函數(shù)需要圖G上增加一條邊。當(dāng)時(shí)，邊(s,p)的權(quán)重設(shè)為當(dāng)時(shí)，邊(p,t)的權(quán)重設(shè)為

6.根據(jù)權(quán)利要求書3所述一種基于對偶分解的三維相位解纏方法，其特征在于：

邊勢函數(shù)的權(quán)重賦值(22)如下：

考慮邊勢函數(shù)需要在圖G增加三條邊，邊(p,q)的權(quán)重設(shè)為由于邊的函數(shù)滿足次模性條件，因此邊(p,q)的權(quán)重大于0。

當(dāng)時(shí)，邊(s,p)的權(quán)重設(shè)為

當(dāng)時(shí)，邊(p,t)的權(quán)重設(shè)為

當(dāng)時(shí)，邊(s,q)的權(quán)重設(shè)為

當(dāng)時(shí)，邊(q,t)的權(quán)重設(shè)為

根據(jù)上述規(guī)則將能量函數(shù)的所有節(jié)點(diǎn)和邊的勢函數(shù)賦值到圖G，原能量最小化問題轉(zhuǎn)化為在圖G上找一個(gè)最小權(quán)重s-t切分，s-t切分定義為將節(jié)點(diǎn)集合V劃分為兩個(gè)不連通的子集合S和T，其中源節(jié)點(diǎn)s在集合S，匯節(jié)點(diǎn)t在集合T中，最小切分問題，即找到一個(gè)切分使得所有切邊權(quán)重之和最小，當(dāng)一個(gè)節(jié)點(diǎn)u∈S，則該節(jié)點(diǎn)的標(biāo)簽為0，當(dāng)該節(jié)點(diǎn)u∈T，則標(biāo)簽為1。