張道貴

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

高階能量函數(shù)優(yōu)化的并行實(shí)現(xiàn)

張道貴

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

在機(jī)器視覺領(lǐng)域中，例如圖像分割、視頻處理和圖像存儲等問題都可以建模成能量方程優(yōu)化問題。然而為了追求高性能建模出來的能量方程一般都是高次能量方程，對于這種高次能量方程直接求解極其困難。最近的方法中Ishikawa提出對高次能量方程的降為二次的方法，這種降次方法沒有加入新的變量。基于這種算法的流程，對這種算法的降次結(jié)果進(jìn)行分析，從而對其并行化處理，沒有改變其效果的基礎(chǔ)上在時(shí)間上達(dá)到較快的改進(jìn)。

能量方程；機(jī)器視覺；優(yōu)化

0 引言

在如今的機(jī)器領(lǐng)域發(fā)展中，馬爾科夫隨機(jī)場（MRF）在其領(lǐng)域中起到了很大的作用。很多涉及機(jī)器視覺領(lǐng)域問題可以建模成一種關(guān)于MRF的最優(yōu)化問題。特別是最近幾年，由于圖割理論的發(fā)展和健全，其很多拓展算法極大地提高了對于所建立的優(yōu)化問題模型的求解的質(zhì)量，例如，圖割算法很好地求解出二次的MRF模型?？上У氖沁@些算法很少涉及到更復(fù)雜的模型了。這種復(fù)雜的模型一般會被建模成高次的MRF，也稱為高次能量方程。如今高次能量方程通常有二種思路求解。第一是通過某種等價(jià)變化，將高次能量方程等價(jià)為低次能量方程（一般為二次能量方程），然后使用成熟的二次能量方程算法例如圖割算法對其求解。另一種是利用近似求解的思路，對這些高次能量方程進(jìn)行近似逼近。得到的近似式子滿足凸性。對于上兩種思路，最近研究比較多的是第一種思路[1-7]，同時(shí)也取得了一定的成果。Kolmogorov提出將三次的能量方程轉(zhuǎn)為二次的能量方程[6-7]。同時(shí)給出了這種轉(zhuǎn)化方式的充要條件。在此基礎(chǔ)上Freedman給出了能量方程的代數(shù)表示形式[4]，從而簡化了一系列關(guān)于能量方程的結(jié)論和表達(dá)方式。同時(shí)在代數(shù)表達(dá)形式上對這種代數(shù)式的能量方程的單個(gè)項(xiàng)進(jìn)行了降次。但是這種高次單項(xiàng)降為二次單項(xiàng)的條件是它的系數(shù)是為負(fù)。對于系數(shù)為正項(xiàng)的單項(xiàng)卻沒有給出降為二次單項(xiàng)的方法。直到最近Ishikawa填補(bǔ)了這個(gè)鴻溝。讓任何系數(shù)為正的高次單項(xiàng)可以轉(zhuǎn)換為二次單項(xiàng)?？傊鲜龅母叽文芰糠匠剔D(zhuǎn)為二次能量方程的方法都是通過增加新的變量。然而對于轉(zhuǎn)化后的二次能量方程如果新加的變量太多會產(chǎn)生另一個(gè)問題，現(xiàn)如今的成熟的對于二次能量方程求解的方法不能完全處理變量過多的能量函數(shù)。因此催生了近幾年來的不加任何新的變量的降低高次能量方程的研究。對于不加入任何新的變量去降低能量方程的次數(shù)一般需要一些額外的計(jì)算。學(xué)者Ishikawa給出了一種新的方法[7]，對于每個(gè)單個(gè)高次的能量項(xiàng)力求將其等價(jià)轉(zhuǎn)化為二次項(xiàng)的多項(xiàng)式。但是其方法對于有一些局限性。時(shí)間因?yàn)轭~外的計(jì)算導(dǎo)致會表現(xiàn)甚至不如傳統(tǒng)的加新的變量方法。但是對于Ishikawa提出的方法很適合并行計(jì)算。

1 高次能量方程

由于最近幾年機(jī)器視覺領(lǐng)域的發(fā)展，原來的二次能量方程已經(jīng)不能滿足對于復(fù)雜模型的建模。對于高次能量方程的研究也越來越多。在介紹高次能量方程之前我們必須知道一些概念。

在很多文獻(xiàn)中，一般的能量方程都可以用統(tǒng)一的代數(shù)形式表示為如下：

其中V是{1，2，…，n}集合，S是V的子集。然而最高次單項(xiàng)的次數(shù)被定義為這個(gè)函數(shù)的度：

如果度數(shù)大于等于3時(shí)候，這個(gè)函數(shù)就被定義為高次能量方程。

將上面的能量函數(shù)改寫成另一個(gè)形式：E（X）=EC（X）+EC（X），其中：

能量函數(shù)的ELC。如果我們找到這個(gè)高次單項(xiàng)的ELC，我們可以根據(jù)它設(shè)計(jì)一個(gè)唯一（易證明）的多項(xiàng)式加入高次能量方程中以抵消這個(gè)高次單項(xiàng)而不會引入新的變量。下面給出關(guān)于這個(gè)算法的具體步驟。

（2）如果αC＜0并且|C|為奇數(shù)，則需要找一個(gè)ELC，并且其含奇數(shù)個(gè)1。如果αC＞0并且|C|為奇數(shù)，尋找一個(gè)ELC，并且其含有偶數(shù)個(gè)1。如果|C|為偶數(shù)，直接需要運(yùn)動(dòng)相反的方式找出對應(yīng)的ELC。

（3）如果ELC已找到，設(shè)為u。我們將加上如下多項(xiàng)式到這個(gè)高次能量函數(shù)中，

得到新的能量函數(shù)

（4）如果上面的高次單項(xiàng)沒有找到對應(yīng)的ELC，我們將不管這個(gè)單項(xiàng)，直接用傳統(tǒng)的引入新的變量的方法，將其等價(jià)為二次多項(xiàng)式。

對于上述的方法，我們將其應(yīng)用于專家場去噪的實(shí)驗(yàn)。這算法表現(xiàn)出較好的性能，其中最主要的是時(shí)間的加速。但是我們發(fā)現(xiàn)，在尋找ELC的過程盡然占去98%的時(shí)間。我們則需要研究上面的尋找ELC的方法，對其進(jìn)行改進(jìn)，尋找其中一些規(guī)律，發(fā)現(xiàn)其非常適合用并行算法來實(shí)驗(yàn)。因?yàn)閷τ诟叽文芰亢瘮?shù)中的同等的次數(shù)的單項(xiàng)之間，用ELC的方法去降次是相互之間不會影響，也不會對最小值有任何影響。將給出相應(yīng)的證明。在給出相應(yīng)的證明之前需要理解尋找ELC的原理。我們同樣用（3）式為例，進(jìn)行介紹。

Ishikawa已經(jīng)給出了關(guān)于ELC的充要條件，即如果u是一個(gè)ELC，它必須滿足如下公式：

我們已經(jīng)得到并行的可行性。我們簡單對上面算法的第（2）步驟，改為如下：

（1）對于任意高次能量函數(shù)，區(qū)分將同次的單項(xiàng)分別聚集起來成幾組。首先對最高次組任意選擇四個(gè)，轉(zhuǎn)為（2），如果沒有四個(gè)相同高次項(xiàng)，將減少并行度。當(dāng)遇到較低次的單項(xiàng)時(shí)，用類似較高次的方法。

（2）對四個(gè)多項(xiàng)式采用如下約束去找ELC：如果αC＜0并且|C|為奇數(shù)，則需要找一個(gè)ELC，其值中含奇數(shù)個(gè)1。如果αC＞0并且|C|為奇數(shù)，尋找一個(gè)ELC，其值中含偶數(shù)個(gè)1。如果|C|為偶數(shù)，直接按相反的方式找對應(yīng)的ELC。在并行算法中，我們將生成最多4個(gè)ELC。

（3）對于已經(jīng)找到ELC的單項(xiàng)，設(shè)其中之一為u。將加4個(gè)如下多項(xiàng)式到這個(gè)高次能量函數(shù)中，

得到新的能量函數(shù)：

（4）如果上面的高次單項(xiàng)沒有找到對應(yīng)的ELC，我們將不管這個(gè)單項(xiàng)，直接用傳統(tǒng)的引入新的變量的方法，將其轉(zhuǎn)為二次多項(xiàng)式。

經(jīng)過改進(jìn)后，本文算法發(fā)現(xiàn)，在沒有影響質(zhì)量的條件下，從理論上極大地縮短了算法的執(zhí)行時(shí)間。

2 時(shí)間結(jié)果

為了比較兩種算法的實(shí)驗(yàn)效果，我們用一直沿用的專家場模型給圖像去噪的實(shí)驗(yàn)。專家場模型是將圖像的先驗(yàn)分布表示為幾個(gè)學(xué)生分布的積：

其中C表示圖像中2×2的像素塊的所有的集合。Ji是2×2的濾波。其中Ji和αi是通過從自然圖像數(shù)據(jù)庫中學(xué)習(xí)得到的。如果大家對專家場不熟悉且比較感興趣，請查閱文獻(xiàn)[7]。這模型是四次能量方程，專家場的算法是一種迭代算法。用融合的思路將原始圖像的賦值和高次能量函數(shù)最小值的賦值進(jìn)行融合。我們分別用原始論文算法和用并行的思路分別去求解上述能量方程最小值的賦值。

從算法對比發(fā)現(xiàn)，在沒有影響質(zhì)量的條件下，極大地縮短了算法的執(zhí)行時(shí)間：

圖1 紅色線條表示原始算法的時(shí)間效果，藍(lán)色線條表示改成并行后的時(shí)間效果

我們發(fā)現(xiàn)對于相同的時(shí)間內(nèi)，我們并行算法的能量函數(shù)值的大小明顯小于原來的算法。這些減少的時(shí)間效率極大的提高原有算法的應(yīng)用范圍。

圖2 紅色折線表示原始算法在每次迭代的函數(shù)值，藍(lán)色星花表示用并行算法后每次迭代的函數(shù)值

從上圖可以看出來，用并行的時(shí)候?qū)υ己瘮?shù)值的求解幾乎沒有任何影響，也表明了，這種算法是很適合用并行算法來實(shí)現(xiàn)的。

圖3 紅色折線表示原始算法迭代和時(shí)間的對應(yīng)關(guān)系，藍(lán)色是并行算法中迭代和時(shí)間對應(yīng)關(guān)系

從上述圖我們發(fā)現(xiàn)并行算法在每次迭代花的時(shí)間要小于原來的算法，但是得到的結(jié)果和原來的算法一樣。所以對于原來的算法用并行算法是很有效果的。

3 結(jié)語

在本文，我們通過并行的思路提高了算法的執(zhí)行時(shí)間。但是還是沒有從根本上解決尋找ELC問題。原始算法中尋找ELC是通過完全搜索EC（X）的定義域空間。從傳統(tǒng)意義上說復(fù)雜度依然是指數(shù)型的，對于不是特別高度數(shù)的能量方程，這算法還能表現(xiàn)出較好的時(shí)間效率。但是對于更高度數(shù)的能量方程，其時(shí)間復(fù)雜度反而沒有傳統(tǒng)的能量方程有優(yōu)勢。因此未來可能將對于尋找ELC的方法，需要從理論上減少其復(fù)雜度。鑒于原來的充要條件是一個(gè)NP問題，故可能是將給出尋找ELC的充分條件而不是充要條件。這樣將原來的NP問題轉(zhuǎn)為較為簡單的判斷ELC條件具有凸性的問題。這將是未來的研究工作。

[1]C.Arora，S.Banerjee，P.Kalra，S.N.Maheshwari.Generic Cuts:An Efficient Algorithm for Optimal Inference in Higher Order MRFMAP.In:ECCV2012，V:17-30，2012.

[2]Y.Boykov，O.Veksler，R.Zabih.Fast Approximate Energy Minimization via Graph Cuts.IEEE Trans.PAMI 23:1222-1239，2001.

[3]D.Freedman and P.Drineas.Energy Minimization Via Graph Cuts:Settling What is Possible.In CVPR2005 II:939-946，2005.

[4]V.Kolmogorov，R.Zabih.What Energy Functions Can Be Minimized via Graph Cuts?IEEE Trans.PAMI 26（2）:147-159，2004.

[5]H.Ishikawa.Higher-Order Clique Reduction Without Auxiliary Variables.In Proc.of CVPR，pages 1362-1369，2014.

[6]H.Ishikawa.Transformation of General Binary MRF Minimization to the First Order Case.IEEE Trans.Patt.Anal.Mach.Intell.，33（6）: 1234-1249，2011.

Higher-Order Energy Function Optimization in Parallel

ZHANG Dao-gui
（College of Computer Science，Sichuan University，Chengdu 610065）

In computer vision fields,many problems such as the image segmentation,video processing and image storage can be formulated as the optimization of energy functions.The energy function is always the higher-order which is extremely difficult to solve.Fortunately, Ishikawa provides a method that reduces the higher-order energy functions as quadratic one without add new variables.Analyzes the procession of the algorithm and translate it into parallel mode.The algorithm in parallel manifests the relative good efficient performance without affect the solution.

Energy Function;Computer Vision;Optimization

1007-1423（2017）08-0022-04

10.3969/j.issn.1007-1423.2017.08.005

張道貴（1990-），男，安徽蕪湖人，在讀碩士研究生，研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、數(shù)字圖像處理

2016-12-27

2017-02-20