图像处理中的全局优化技术(经典至极)

图像处理中的全局优化技术(Globaloptimizationtechniquesinimageprocessingandcomputervision)(一)2013-05-2914:261659人阅读评论(1)收藏举报算法图像处理计算机视觉imagevisionMulinB按：最近打算好好学习一下几种图像处理和计算机视觉中常用的globaloptimization(或energyminimization)方法，这里总结一下学习心得。分为以下几篇：1.DiscreteOptimization:GraphCutsandBeliefPropagation(本篇)2.QuadraticOptimization:PoissonEquationandLaplacianMatrix3.VariationalMethodsforOpticalFlowEstimation4.TODO:LikelihoodMaximization(e.g.,BlindDeconvolution)1.DiscreteOptimization:GraphCutsandBeliefPropagation很多图像处理和视觉的问题可以看成是pixel-labeling问题，用energyminimizationframework可以formulate成以下能量方程：其中第一项叫dataterm(或叫unaryterm)，是将labell_p赋给像素p时的cost，第二项叫smoothnessterm(或叫pairwiseterm)，是每两个相邻pixel的labeling不同时产生的cost(w_pq是spatialvaryingweight，比如跟p和q的difference相关)。传统的smoothnessterm一般只考虑两两(pairwise)相邻的pixel，最近几年的CVPR和ICCV上开始出现很多higher-orderMRF的研究，比如这位大牛的paper，这是题外话。这种energyminimizationframework其实从概率的角度看，等价于求MarkovRandomField(MRF)的maximumaposteriori(MAP)概率。求解这类energyminimization的方法，最流行的有两个，GraphCuts和BeliefPropagation。1.1GraphCuts刚开始学习GraphCuts时，不知道到底这方法是从哪篇paper最早提出来的，因为在后来的paper里引用的参考文献一般指向好几个来源，这里先大致梳理一下参考文献。一般认为，将GraphCuts引入图像处理领域的先驱paper是Greig等人1989年发表的[1]，不过貌似没有引起太大的注意。真正使GraphCuts在图像领域风靡起来的是两个俄罗斯人(貌似是在Cornell做出的成果)，YuriBoykov和VladimirKolmogorov，以及他们的导师RaminZabih。首先引起大家注意的是Boykov在ICCV2001上的使用GraphCuts解决InteractiveImageSegmentation的paper[2]，以及这篇paper提到的一个max-flow算法[3](该max-flow算法最早是发在2001年的一个CVPRWorkshop上，后来扩展到TPAMI[3])。需要注意的是，这两篇paper里的GraphCuts算法，只是针对只有两个label(待求变量是binaryvariable)的情况。而Boykov的2001TPAMIpaper[4]提出使用alphaexpansion技术将多个label的问题转化成一系列的binarylabel问题去逼近，这使得GraphCuts算法开始风靡起来。后来Kolmogorov的2004TPAMIpaper[5]进一步讨论了什么样的能量方程可以被GraphCuts优化，并给出了一个简单清晰的根据能量方程构造相应graph的算法，该算法基本成为被大家广泛使用的GraphCuts算法。Boykov和Kolmogorov的代码可以从这里找到。下面简单介绍一下GraphCuts算法，先从binarylabel开始(见参考文献[2][3])。顾名思义，GraphCuts是将图像中的所有pixel以及两个label作为node，根据datacost和smoothnesscost建立node之间的edge，这样构造一个(无向)graph，然后通过cut算法将整个graph切成两个分离的部分。如下图所示：注意，图中的cut会切断它经过的所有edge(包括蓝色、红色、和土黄色的edge)。如果将两个label的node看成两个特殊的terminal，这样的一个cut会阻断所有s连往t的路径(edge)。在Boykov的ICCV2001paper[2]中，他证明了通过简单的方式构造这样的一个graph，如果能找到一个min-cut(即该cut经过的edgecost加起来在所有possible的cut中最小)，其实就是上面的能量方程的最小解(见paper中的Theorem1)。那么如何找到min-cut呢？在图论里，有证明找到min-cut其实等价于找到max-flow，即从s流往t的最大流量。其实，min-cut等价于max-flow的intuition很简单，从一个terminal流往另一个terminal的最大流量，其瓶颈肯定是min-cut的位置。这里有个有意思的介绍，关于网络里s-tflow的计算。计算max-flow的经典算法主要有两种，一种是基于augmenting-path，一种是基于push-relabeling。在Boykov和Kolmogorov的TPAMI2004paper[3]里，介绍了一种基于augmenting-path，为了图像这种扁平graph量身定制的max-flow算法，通过实验证明了其效率，这里有他们的代码。在解决multi-labeling问题时(其实是更为普遍和常见的问题)，在能量方程满足某些特定的条件下(注意：该限定条件其实挺难满足，后面讨论！)，可以使用alphaexpansion算法将其转化为一系列binary-labeling问题来逼近，参见BoykovTPAMI2001paper[4]。见下图：这种alphaexpansion思路很简单，当处理每一个label时(假设其为a)，将其他所有的label看成一个labelpackage(假如称之为b)，这时问题就变成了binary-labeling。此时在进行cut时，如果一个原来是a的pixel被cut给b，将无法确定到底给该pixel具体哪一个label(由于b是个大杂烩)。所以在进行cut时，只允许原来是b的pixel被cut给a，也就是标记为a的pixel在expanding，这就是算法名字的来源。需要注意的是，为了使得这样的一次alphaexpansion可以被max-flow算法计算出来，graph的构造比之前的binary-labeling要稍微复杂一些(比如仅仅允许alphaexpansion的话，有些跟b相连的edgeweight要设成无穷大)。使用alphaexpansion算法的步骤很简单，如下：[cpp]viewplaincopy1.//alphaexpansionalgorithmpseudo-code2.initializelabeling;3.4.whilenotconverged5.{6.foreachlabelainL7.{8.constructagraph;9.domax-flowcut;10.ifenergyissmallerthanbefore,acceptit;11.elsedeclineit;12.}13.}值得注意的是，这种alphaexpansion只是multi-labeling问题的近似求解，而之前的max-flow算法是binary-labeling问题的exact求解方法。而且，为了使得这种alphaexpansion时的graph可以被构造出来，能量方程需要满足一定的限定条件，具体来说，是能量方程中的pairwiseterm函数V_pq需要满足某些限定条件。在BoykovTPAMI2001paper[4]中称之为V_pq必须是一个metric(类似于满足“距离”的定义，比如：可交换、满足三角不等式)。在KolmogorovTPAMI2004paper[5]中将其推广为V_pq必须是一个submodular函数(文中称之为regular，其实后来都称之为submodular)，即函数V_pq必须满足V(0,0)+V(1,1)=V(0,1)+V(1,0)条件。该条件乍一看貌似很容易满足，特别是对于binary-labeling来说。然而，注意，在alphaexpansion中，该条件变成了如下，注意，其中l_p和l_q可能不一样。这样一来其实该条件没那么容易满足！比如常用的quadraticcost就不满足！常用的pairwiseterm的V_pq函数如下表所示(PottsModel中delta函数是unitimpulse函数)：例如，quadraticcost时，l_p=3,l_q=10,a=5,这时，上面条件里左侧第一项的值是49，第二项是0，不等式右侧第一项是4，第二项是25，显然不等式不成立！另外需要一提的是，其实即使上述的条件不成立，仍然可以使用alphaexpansion，使用的时候可以对一些不满足条件的项进行修改，这种技术在CVPR05的一篇paper里提出[6]，叫做truncating，在这里的代码(文件energy.h，函数add_term2里)可以找到例子，代码非常简单：[cpp]viewplaincopy1.//Truncatingfornon-submodualrterm,codebyKolmogorov2.//A,D,C,B分别是上述不等式的四项3.if(A+DC+B)4.{5.Valuedelta=A+D-C-B;6.ValuesubtrA=delta/3;7.8.A=A-subtrA;9.C=C+subtrA;10.B=B+(delta-subtrA*2);11.}这种truncating之后的算法其实并不能保证最终结果是stronglocalminimum(注意，没有truncating的alphaexpansion只是能保证找到stronglocalminimum，不能保证是globalmininum)，但是实际使用中效果不错。另外专门针对non-submodular进行优化的算法有QBPO，见KolgoromovTPAMI2007paper[7]。1.2BeliefPropagationBeliefPropagation是GraphCuts的一个强劲对手，其渊源可以追溯到MIT在ICCV2003上的paper[8]，比较这两种方法在stereo上的性能，结果貌似不分上下，GraphCuts略胜一点点。后来大牛RichardSzeliski联合一堆MRF的experts搞了一个benchmark评测这些方法，见TPAMI2008paper[9]，和这个benchmark，上面有code可以下载，集成了很多算法，非常值得研究。结论是，GraphCuts(alphaexpansion)算法表现比较出色，另外BeliefPropagation的一个改进算法叫TreeReWeightedMessagePassing(TRW-S)也表现出色，而BeliefPropagation似乎表现不那么理想。不过其实其中除了Photomontage之外的其他比较中，基本都难分高下(在Photomontage中，alphaexpansion完爆其他算法)。在实际使用中，至少在stereo的Middleburybenchmark上，BeliefPropagation还是占了大多数席位。跟GraphCuts相比，BeliefPropa