高阶能量函数优化的并行实现

张道贵

（四川大学计算机学院，成都 610065）

高阶能量函数优化的并行实现

张道贵

（四川大学计算机学院，成都 610065）

在机器视觉领域中，例如图像分割、视频处理和图像存储等问题都可以建模成能量方程优化问题。然而为了追求高性能建模出来的能量方程一般都是高次能量方程，对于这种高次能量方程直接求解极其困难。最近的方法中Ishikawa提出对高次能量方程的降为二次的方法，这种降次方法没有加入新的变量。基于这种算法的流程，对这种算法的降次结果进行分析，从而对其并行化处理，没有改变其效果的基础上在时间上达到较快的改进。

能量方程；机器视觉；优化

0 引言

在如今的机器领域发展中，马尔科夫随机场（MRF）在其领域中起到了很大的作用。很多涉及机器视觉领域问题可以建模成一种关于MRF的最优化问题。特别是最近几年，由于图割理论的发展和健全，其很多拓展算法极大地提高了对于所建立的优化问题模型的求解的质量，例如，图割算法很好地求解出二次的MRF模型。可惜的是这些算法很少涉及到更复杂的模型了。这种复杂的模型一般会被建模成高次的MRF，也称为高次能量方程。如今高次能量方程通常有二种思路求解。第一是通过某种等价变化，将高次能量方程等价为低次能量方程（一般为二次能量方程），然后使用成熟的二次能量方程算法例如图割算法对其求解。另一种是利用近似求解的思路，对这些高次能量方程进行近似逼近。得到的近似式子满足凸性。对于上两种思路，最近研究比较多的是第一种思路[1-7]，同时也取得了一定的成果。Kolmogorov提出将三次的能量方程转为二次的能量方程[6-7]。同时给出了这种转化方式的充要条件。在此基础上Freedman给出了能量方程的代数表示形式[4]，从而简化了一系列关于能量方程的结论和表达方式。同时在代数表达形式上对这种代数式的能量方程的单个项进行了降次。但是这种高次单项降为二次单项的条件是它的系数是为负。对于系数为正项的单项却没有给出降为二次单项的方法。直到最近Ishikawa填补了这个鸿沟。让任何系数为正的高次单项可以转换为二次单项。总之上述的高次能量方程转为二次能量方程的方法都是通过增加新的变量。然而对于转化后的二次能量方程如果新加的变量太多会产生另一个问题，现如今的成熟的对于二次能量方程求解的方法不能完全处理变量过多的能量函数。因此催生了近几年来的不加任何新的变量的降低高次能量方程的研究。对于不加入任何新的变量去降低能量方程的次数一般需要一些额外的计算。学者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