高階能量函數優化的并行實現

張道貴

（四川大學計算機學院，成都 610065）

高階能量函數優化的并行實現

張道貴

（四川大學計算機學院，成都 610065）

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

能量方程；機器視覺；優化

0 引言

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

1 高次能量方程

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

在很多文獻中，一般的能量方程都可以用統一的代數形式表示為如下：

其中V是{1，2，…，n}集合，S是V的子集。然而最高次單項的次數被定義為這個函數的度：

如果度數大于等于3時候，這個函數就被定義為高次能量方程。

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

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

（2）如果αC＜0并且|C|為奇數，則需要找一個ELC，并且其含奇數個1。如果αC＞0并且|C|為奇數，尋找一個ELC，并且其含有偶數個1。如果|C|為偶數，直接需要運動相反的方式找出對應的ELC。

（3）如果ELC已找到，設為u。我們將加上如下多項式到這個高次能量函數中，

得到新的能量函數

（4）如果上面的高次單項沒有找到對應的ELC，我們將不管這個單項，直接用傳統的引入新的變量的方法，將其等價為二次多項式。

對于上述的方法，我們將其應用于專家場去噪的實驗。這算法表現出較好的性能，其中最主要的是時間的加速。但是我們發現，在尋找ELC的過程盡然占去98%的時間。我們則需要研究上面的尋找ELC的方法，對其進行改進，尋找其中一些規律，發現其非常適合用并行算法來實驗。因為對于高次能量函數中的同等的次數的單項之間，用ELC的方法去降次是相互之間不會影響，也不會對最小值有任何影響。將給出相應的證明。在給出相應的證明之前需要理解尋找ELC的原理。我們同樣用（3）式為例，進行介紹。

Ishikawa已經給出了關于ELC的充要條件，即如果u是一個ELC，它必須滿足如下公式：

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

（1）對于任意高次能量函數，區分將同次的單項分別聚集起來成幾組。首先對最高次組任意選擇四個，轉為（2），如果沒有四個相同高次項，將減少并行度。當遇到較低次的單項時，用類似較高次的方法。

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

（3）對于已經找到ELC的單項，設其中之一為u。將加4個如下多項式到這個高次能量函數中，

得到新的能量函數：

（4）如果上面的高次單項沒有找到對應的ELC，我們將不管這個單項，直接用傳統的引入新的變量的方法，將其轉為二次多項式。

經過改進后，本文算法發現，在沒有影響質量的條件下，從理論上極大地縮短了算法的執行時間。

2 時間結果

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

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

從算法對比發現，在沒有影響質量的條件下，極大地縮短了算法的執行時間：

圖1 紅色線條表示原始算法的時間效果，藍色線條表示改成并行后的時間效果

我們發現對于相同的時間內，我們并行算法的能量函數值的大小明顯小于原來的算法。這些減少的時間效率極大的提高原有算法的應用范圍。

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

從上圖可以看出來，用并行的時候對原始函數值的求解幾乎沒有任何影響，也表明了，這種算法是很適合用并行算法來實現的。

圖3 紅色折線表示原始算法迭代和時間的對應關系，藍色是并行算法中迭代和時間對應關系

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

3 結語

在本文，我們通過并行的思路提高了算法的執行時間。但是還是沒有從根本上解決尋找ELC問題。原始算法中尋找ELC是通過完全搜索EC（X）的定義域空間。從傳統意義上說復雜度依然是指數型的，對于不是特別高度數的能量方程，這算法還能表現出較好的時間效率。但是對于更高度數的能量方程，其時間復雜度反而沒有傳統的能量方程有優勢。因此未來可能將對于尋找ELC的方法，需要從理論上減少其復雜度。鑒于原來的充要條件是一個NP問題，故可能是將給出尋找ELC的充分條件而不是充要條件。這樣將原來的NP問題轉為較為簡單的判斷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-），男，安徽蕪湖人，在讀碩士研究生，研究方向為計算機圖形學、數字圖像處理

2016-12-27

2017-02-20