图像处理中的全局优化技术(Global optimization techniques in image processing and computer vision) (一)
2013-05-29 14:26 1659人阅读 评论(1) 收藏 举报
算法图像处理计算机视觉imagevision
MulinB按：最近打算好好学习一下几种图像处理和计算机视觉中常用的 global optimization (或 energy minimization) 方法，这里总结一下学习心得。分为以下几篇： 1. Discrete Optimization: Graph Cuts and Belief Propagation (本篇) 2. Quadratic Optimization : Poisson Equation and Laplacian Matrix 3. Variational Methods for Optical Flow Estimation
4. TODO: Likelihood Maximization (e.g., Blind Deconvolution)
1. Discrete Optimization: Graph Cuts and Belief Propagation
很多图像处理和视觉的问题可以看成是pixel-labeling问题，用energy minimization framework可以formulate成以下能量方程：
其中第一项叫data term (或叫unary term)，是将label l_p赋给像素p时的cost，第二项叫smoothness term (或叫pairwise term)，是每两个相邻pixel的labeling不同时产生的cost (w_pq是spatial varying weight，比如跟p和q的difference相关)。传统的smoothness term一般只考虑两两(pairwise)相邻的pixel，最近几年的CVPR和ICCV上开始出现很多higher-order MRF的研究，比如这位大牛的paper，这是题外话。这种energy minimization framework其实从概率的角度看，等价于求Markov Random Field (MRF) 的maximum a posteriori (MAP) 概率。求解这类energy minimization的方法，最流行的有两个，Graph Cuts和Belief Propagation。
1.1 Graph Cuts
刚开始学习Graph Cuts时，不知道到底这方法是从哪篇paper最早提出来的，因为在后来的paper里引用的参考文献一般指向好几个来源，这里先大致梳理一下参考文献。一般认为，将Graph Cuts引入图像处理领域的先驱paper是Greig等人1989年发表的[1]，不过貌似没有引起太大的注意。真正使Graph Cuts在图像领域风靡起来的是两个俄罗斯人(貌似是在Cornell做出的成果)，Yuri Boykov和Vladimir Kolmogorov，以及他们的导师Ramin Zabih。首先引起大家注意的是Boykov在ICCV 2001上的使用Graph Cuts解决Interactive Image Segmentation的paper[2]，以及这篇paper提到的一个max-flow算法[3] (该max-flow算法最早是发在2001年的一个CVPR Workshop上，后来扩展到TPAMI [3])。需要注意的是，这两篇paper里的Graph Cuts算法，只是针对只有两个label (待求变量是binary variable)的情况。而Boykov的2001 TPAMI paper[4]提出使用alpha expansion技术将多个label的问题转化成一系列的binary label问题去逼近，这使得Graph Cuts算法开始风靡起来。后来Kolmogorov的2004 TPAMI paper[5] 进一步讨论了什么样的能量方程可以被Graph Cuts优化，并给出了一个简单清晰的根据能量方程构造相应graph的算法，该算法基本成为被大家广泛使用的Graph Cuts算法。Boykov和Kolmogorov的代码可以从这里找到。
下面简单介绍一下Graph Cuts算法，先从binary label开始(见参考文献[2] [3])。顾名思义，Graph Cuts是将图像中的所有pixel以及两个label作为node，根据data cost和smoothness cost建立node之间的edge，这样构造一个(无向)graph，然后通过cut算法将整个graph切成两个分离的部分。如下图所示：
注意，图中的cut会切断它经过的所有edge(包括蓝色、红色、和土黄色的edge)。如果将两个label的node看成两个特殊的terminal，这样的一个cut会阻断所有s连往t的路径(edge)。在Boykov的ICCV 2001 paper [2]中，他证明了通过简单的方式构造这样的一个graph，如果能找到一个min-cut (即该cut经过的edge cost加起来在所有possible的cut中最小)，其实就是上面的能量方程的最小解 (见paper中的Theorem 1)。那么如何找到min-cut呢？
在图论里，有证明找到min-cut其实等价于找到max-flow，即从s流往t的最大流量。其实，min-cut等价于max-flow的intuition很简单，从一个terminal流往另一个terminal的最大流量，其瓶颈肯定是min-cut的位置。这里有个有意思的介绍，关于网络里s-t flow的计算。计算max-flow的经典算法主要有两种，一种是基于augmenting-path，一种是基于push-relabeling。在Boykov和Kolmogorov的TPAMI 2004 paper [3]里，介绍了一种基于augmenting-path，为了图像这种扁平graph量身定制的max-flow算法，通过实验证明了其效率，这里有他们的代码。
在解决multi-labeling问题时 (其实是更为普遍和常见的问题)，在能量方程满足某些特定的条件下(注意：该限定条件其实挺难满足，后面讨论！)，可以使用alpha expansion算法将其转化为一系列binary-labeling问题来逼近，参见Boykov TPAMI 2001 paper [4]。见下图：
这种alpha expansion思路很简单，当处理每一个label时(假设其为a)，将其他所有的label看成一个label package(假如称之为b)，这时问题就变成了binary-labeling。此时在进行cut时，如果一个原来是a的pixel被cut给b，将无法确定到底给该pixel具体哪一个label(由
于b是个大杂烩)。所以在进行cut时，只允许原来是b的pixel被cut给a，也就是标记为a的pixel在expanding，这就是算法名字的来源。需要注意的是，为了使得这样的一次alpha expansion可以被max-flow算法计算出来，graph的构造比之前的binary-labeling要稍微复杂一些 (比如仅仅允许alpha expansion的话，有些跟b相连的edge weight要设成无穷大)。使用alpha expansion算法的步骤很简单，如下：
[cpp] view plaincopy
1. // alpha expansion algorithm pseudo-code 2. initialize labeling; 3.
4. while not converged 5. {
6. for each label a in L 7. {
8. construct a graph; 9. do max-flow cut;
10. if energy is smaller than before, accept it; 11. else decline it; 12. } 13. }
值得注意的是，这种alpha expansion只是multi-labeling问题的近似求解，而之前的max-flow算法是binary-labeling问题的exact求解方法。而且，为了使得这种alpha expansion时的graph可以被构造出来，能量方程需要满足一定的限定条件，具体来说，是能量方程中的pairwise term函数V_pq需要满足某些限定条件。在Boykov TPAMI 2001 paper [4]中称之为V_pq必须是一个metric(类似于满足“距离”的定义，比如：可交换、满足三角不等式)。在Kolmogorov TPAMI 2004 paper [5] 中将其推广为V_pq必须是一个submodular函数(文中称之为regular，其实后来都称之为submodular)，即函数V_pq必须满足V(0,0) + V(1,1) <= V(0,1) + V(1,0)条件。该条件乍一看貌似很容易满足，特别是对于binary-labeling来说。然而，注意，在alpha expansion中，该条件变成了如下，
注意，其中l_p和l_q可能不一样。这样一来其实该条件没那么容易满足！比如常用的quadratic cost就不满足！常用的pairwise term的V_pq函数如下表所示 (Potts Model中delta函数是unit impulse函数)：
例如，quadratic cost时，l_p=3, l_q=10, a=5, 这时，上面条件里左侧第一项的值是49，第二项是0，不等式右侧第一项是4，第二项是25，显然不等式不成立！
另外需要一提的是，其实即使上述的条件不成立，仍然可以使用alpha expansion，使用的时候可以对一些不满足条件的项进行修改，这种技术在CVPR 05的一篇paper里提出[6]，叫做truncating，在这里的代码(文件energy.h，函数add_term2里)可以找到例子，代码非常简单：
[cpp] view plaincopy
1. //Truncating for non-submodualr term, code by Kolmogorov 2. //A, D, C, B分别是上述不等式的四项 3. if ( A+D > C+B) 4. {
5. Value delta = A+D-C-B; 6. Value subtrA = delta/3; 7.
8. A = A-subtrA; 9. C = C+subtrA;
10. B = B+(delta-subtrA*2); 11. }
这种truncating之后的算法其实并不能保证最终结果是strong local minimum (注意，没有truncating的alpha expansion只是能保证找到strong local minimum，不能保证是global mininum)，但是实际使用中效果不错。另外专门针对non-submodular进行优化的算法有QBPO，见Kolgoromov TPAMI 2007 paper[7]。
1.2 Belief Propagation