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

图像处理中的全局优化技术(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

Marching[20] (在[19]中使用的算法，是Sethian的Fast Marching Method的快速实现)，或者更适用于并行计算的Parallel Marching [21](在[22]中使用的算法，这里可以找到代码)，计算复杂度都可以达到O(N)。跟Random Walker相比，基于Geodesic Distance的方法速度更快，不过对seeds的位置依赖比较严重，而且在weak boundary表现也不会好，比如下面的例子。

提到Fast Marching Method，就不得不提另一个在图像领域影响很大的方法：Level Set Method。Level Set Method最早提出是为了解决boundary evolve的问题，比如用户在一个图像上画一个圈，然后这个圈根据图像内容进行演化，最终将一个物体圈出来，比如下图：

这种boundary evolve的问题最原始的方法是explicitly去跟踪boundary上的一些control points，而如果boudanry变化的过程中发生topological结构变化时(比如一个圈圈分裂成两个圈圈)，这种跟踪方式会很变得很难。Level Set Method就是为了解决这种难题。简单来讲，Level Set Method大概思路就是把原来二维的boundary evolve问题重新参数化为三维的surface evolve问题，新参数为笛卡尔坐标x-y以及时间t，这样新的问题成为一个在笛卡尔grid(即pixel grid)中的PDE，一般称为Hamilton-Jacob Equation，可以使用数值解法求出。其原理介绍可以参考Coursera上Guillermo Sapiro的Image and Video Processing，个人认为他讲的非常清晰易懂(可以直接看Section 6: Geometric PDEs)。

最后，再提一下Fast Marching Method。当上面的boundary evolve中曲线法向速度符号不变时(比如说boundary一直朝外扩张)，我们可以用更快速的方法来求解这个PDE：从boundary出发，在其所在的笛卡尔grid里计算并记录从boundary到每个pixel的距离(即到达时间)，如此得到一个类似于等高线图的map，而从这个map上，其实可以得到任意t时的boundary (取记录了某一个相同时间/距离的pixels)，如下图所示。这种map可以使用类似于Dijkstra最短路径算法的方法计算(一般称之为weve-front propagation方法)，或者用raster-scan的方法计算(更易于并行化)。Sethian的Fast Marching Method以及上文提到的Yatziv的快速实现[20]属于前者，而并行算法[21]属于后者。

1.4 Reference

[1] D. Greig, B. Porteous, and A. Seheult, “Exact Maximum A Posteriori Estimation for Binary Images,” J. Royal Statistical Soc., 1989.

[2] Y. Boykov and M.-P. Jolly, “Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images,” ICCV, 2001.

[3] Y. Boykov and V. Kolmogorov, “An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision,” TPAMI, 2004.

[4] Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” TPAMI, 2001.

[5] V. Kolmogorov and R. Zabih, “What Energy Functions can be Minimized via Graph Cuts,” TPAMI, 2004.

[6] C. Rother, S. Kumar, V. Kolmogorov, and A. Blake, “Digital Tapestry,” CVPR, 2005. [7] V. Kolmogorov and C. Rother, “Minimizing Nonsubmodular Functions with Graph Cuts—A Review,” TPAMI, 2007.

[8] M. Tappen and W. Freeman, “Comparison of Graph Cuts with Belief Propagation for Stereo, Using Identical MRF Parameters,” ICCV, 2003.

[9] R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, and C. Rother. “A comparative study of energy minimization methods for markov random fields with smoothness-based priors.” TPAMI, 2008

[10] P. Felzenszwalb and D. Huttenlocher, “Efficient Belief Propagation for Early Vision,” IJCV, 2006.

[11] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.

[12] Weiss, Y. and Freeman,W.T. 2001. “On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs.” IEEE Transactions on Information Theory, 2001.

[13] C. Rother, V. Kolmogorov, and A. Blake, “?GrabCut?—Interactive Foreground Extraction Using Iterated Graph Cuts,” SIGGRAPH, 2004.

[14] A. Agarwala,M. Dontcheva, M. Agrawala, S. Drucker, A. Colburn, B. Curless, D. Salesin, and M. Cohen, “Interactive Digital Photomontage,” SIGGRAPH, 2004. [15] Y. Li, J. Sun, C.-K. Tang, and H.-Y. Shum, “Lazy snapping,” SIGGRAPH, 2004. [16] L. Grady, “Random Walks for Image Segmentation,” TPAMI, 2006.

[17] R.R. Coifman, S. Lafon, A.B. Lee, M. Maggioni, B. Nadler, F. Warner, and S.W. Zucker, “Geometric Diffusions as a Tool for Harmonic Analysis and Structure Definition of Data: Diffusion Maps,” Proc. Nat?l Academy of Sciences USA, 2005.

[18] A.K. Sinop and L. Grady, “A Seeded Image Segmentation Framework Unifying Graph Cuts and Random Walker Which Yields a New Algorithm,” ICCV, 2007.

[19] X. Bai and G. Sapiro, “A Geodesic Framework for Fast Interactive Image and Video Segmentation and Matting,” ICCV, 2007.

[20] L. Yatziv, A. Bartesaghi, and G. Sapiro, “O(n) implementation of the fast marching algorithm,” Journal of Computational Physics, 2006.

[21] O. Weber, Y. Devir, A. Bronstein, M. Bronstein, and R. Kimmel,“Parallel algorithms for approximation of distance maps on parametric surfaces,” SIGGRAPH, 2008. [22] A. Criminisi, T. Sharp, and C. Rother, “Geodesic Image and Video Editing,” TOG, 2010.

图像处理中的全局优化技术(Global optimization techniques in image processing and computer vision) (二)

2013-06-12 16:36 1556人阅读 评论(0) 收藏 举报

算法图像处理计算机视觉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)

2. Quadratic Optimization: Poisson Equation and Laplacian Matrix

Quadratic Optimization (Least Squares Minimization)在图像处理中的魅力要从

SIGGRAPH 02和03年的两篇Gradient Domain Image Editing文章说起：Fattal的HDR Compression[1] 和Perez的Poisson Image Editing [2]。 其后，Levin的两篇文章Colorization [3]和Closed-Form Matting [4]更是将其魅力展现的淋漓尽致。而Farbman的基于Weighted Least Squares的WLS filter [5]也是在Edge-preserving Filter领域名声大噪。由于目标函数是quadratic, 这类问题的求解一般比较容易，大多都可以最终归结为求解一个大型稀疏线性方程组。而数值求解大型线性方程组是一个由来已久的问题，有着各种现成的solver，更是有着为以上这类问题量身定做的solver，见下文solver小节。

题外话：以色列的耶路撒冷希伯来大学(The Hebrew University of Jerusalem)的Lischinski教授貌似很偏爱这类方法，上面提到的这些文章大多有他的署名。

2.1 Problem I: Gradient Domain Image Editing

有心理学为证(见Poisson Image Editing [2]文章的introduction部分)，对图像的gradient进行修改可以产生比较不容易感知到的artifacts，这使得很多图像编辑的工作可以放到gradient domain使得效果很逼真，比如下图的图像拼合例子(图例来自[2])：

其实对gradient domain进行修改而获得逼真的编辑效果由来已久，最早见于1983年Burt-Adelson的Laplacian Pyramid [6]图像融合(这里有个简洁的中文介绍)，这是题外话。在gradient domain进行图像编辑的pipeline一般如下(图例修改自ICCV 2007 Course -- Gradient Domain Manipulation Techniques，顺便赞一个，nice ppt!)：

其中第一步的gradient processing根据不同的需求有具体的操作，比如HDR Compression里是将较大的gradient value进行削弱，而上面的图像拼合例子(Seamless Clone)则是将源图像的gradient拷贝到目标区域。而其中第二步中由gradient重建出新图像并非那么容易，因为经过编辑后的gradient一般是不可积分的，这时Quadratic Optimization粉墨登场。

假设待求图像为I，修改后的已知gradient是G，则通过Least Squares Minimization可以将问题formulate成如下(使得待求图像I的gradient在L2 norm下尽量接近G)：

注意其中的约束条件，比如，在图像拼合例子中，非编辑区域的像素是已知的，在求解编辑区域的像素时，边界上的像素值是约束条件。上面的formulation是假设图像I是定义在x-y连续空间的函数，所以其实上述目标函数是关于I的functional(泛函，也就是“函数的函数”)。使用calculus of variation(变分法)中的Euler-Lagrange Equation (one unknown function, two variables)可以将其转化为一个非常经典的偏微分方程形式，这就是Poisson Equation：

注意其中G是已知的，I是未知的，Δ是Laplacian operator，div是divergence operator。当已知边界像素值时，该偏微分方程具有第一类边界条件(Dirichlet boundary condition)，比如图像拼合；当处理整个图像时，该偏微分方程具有第二类边界条件(Neumann boundary condition)，即已知边界导数值(设为0)，比如HDR Compression。

上面的formulation是在x-y连续空间(像素坐标是连续的)，而用于图像处理时，一般需要将其离散化(因为事实上像素坐标(x,y)是整数)，上面相应的偏微分形式可以使用有限差分(finite difference)形式近似代替。具体来讲，离散化的discrete Laplacian operator如下，

而divergence operator中的一阶偏导可以用前向或者后向差分近似(由于G本身是由gradient得来，一般如果之前计算gradient使用前向差分，那么这里计算div就使用后向差分，这样使得两次差分的结果等价于一次二阶中心差分，具体参考[1])，比如这里的divG可以由以下后向差分近似，

于是，整个Poisson Equation离散化之后，每个pixel都有一个线性方程，假设图像有N个pixel，那么整个Poisson Equation就成了一个包含N个方程的大型方程组。如果将这个大型方程组写成矩阵形式(假设将待求图像I拉成一个长的vector，用x表示，将已知的divG也拉成一个长的vector，用b表示)，离散化的Poisson Equation变成了经典的Ax=b形式。以5×5的图像为例，假设待求图像I为如下形式(每个pixel的值都是未知)：

将其拉成列向量x(按列展开)，则整个Discrete Poisson Equation (with Neumann boundary condition)写成Ax=b形式即，

该矩阵A可以直接从Laplacian operator得来，一般称为Laplacian Matrix(其实如果将图像看成graph，该矩阵即为graph theory中的Laplacian Matrix)。注意，对角线上值为2和3的元素是对应在图像边界上的pixel(因为其discrete Laplacian operator无法完整展开，包含了一些不存在的neighboring pixel)，如果将边界条件改为Dirichlet boundary condition并且未知区域周边的pixle都是已知的话，对角线上的元素就全为4，比如下面的例子。假设待求图像I为如下形式(未知pixel的周边pixel是已知)：

则未知向量x包含9个元素，整个Discrete Poisson Equation (with Dirichlet boundary condition)变成以下形式，

注意等式右侧包含了边界已知pixel的值。这里的Laplacian Matrix较为规整，主要是因为所有的未知pixel处的discrete Laplacian operator可以完整的展开。

总之，上面的discrete Poisson Equation都可以归结为求解一个大型线性方程组，其中的Laplacian Matrix具有以下特点： 1. 对角线元素为non-negative； 2. 非对角线元素为non-positive； 3. 对称(symmetric)；

4. 正定或半正定(positive semidefinite)； 5. 属于分块对角阵。

下面的solver小节再讨论如何求解这样的线性方程组。另外，其实如果直接对上面Least Squares Minimization的目标函数进行离散化，也可以得到相同的方程组(省去了应用Euler-Lagrange Equation的步骤)，参见文章[2]的推导过程。

其中alpha是所有pixel的alpha value组成的列向量，其中L是可以由输入图像计算出的已知矩阵，Levin称之为Matting Laplacian Matrix，与前面介绍的Poisson Equation中的Laplacian Matrix有着很一致的形式和功能(propagation user input)。假设图像有N个pixel，Matting Laplacian是一个N×N的矩阵，其中在(i,j)处的元素为：

其中w_k是local window，|w_k|是local window内pixel的个数，注意I_i是3×1的vector(即rgb三个channel的pixel值)，I_3表示3×3单位矩阵，其他几个符号如下表示：

可以看出，只有当i和j代表的pixel处于同一个local window时，元素(i,j)才不为0。将δ_ij单独提出来(其实只有对角线上的元素有这一项)，令

Levin称之为Matting Affinity，跟前面colorization中用到的affinity相似，只是这里的affinity值可能为负。如果将local window size为2×2(只是为了方便直观显示，事实上一般用奇数边长的window size)，以5×5的图像为例，Matting Laplacian可以表示成如下形式(注意：

只要两个相邻的pixel能放入一个2×2的window，其affinity就不为空，因此事实上每个pixel周围8邻域的pixel的affinity都不为空)：

注意其中形如的元素表示的是输入图像中pixel(3,3)和pixel(3,4)的affinity。由上可

见，Matting Laplacian的形式与colorization中的Laplacian Matrix形式基本一致(如果colorization也用8邻域，那么形式一模一样)。考虑进去目标函数的constraint(即input scribbles)，可以使用跟上面colorization类似的mask列出方程组，或者使用Levin的TPAMI文章里介绍的方法。这里有Levin提供的Matlab代码。需要注意的是：这里的对角线元素不一定非负(non-negative)，非对角线元素也不一定非正(non-positive)，但是整个矩阵仍然是半正定(positive semidefinite)(Levin的paper [4]里有证明)，当然也是对称阵。(注意有些为前面的Laplacian Matrix特别定制的解线性方程组的算法不一定适用于这里的Matting Laplacian Matrix，比如[13]，针对的是非对角元素必须non-positive)。

另外值得一提的是，使用和这里同样的Local Linear Model，假设alpha matte是一个给定的guidance图像，将目标改成要计算出从原始图像到guidance图像的local linear transformation(即求出a和b的值)，将global optimization变为local window内的optimization，可以导出一个计算起来非常快的edge-preserving filter，这就是guided filter [12]。该filter由于其计算速度快，可以作为经典的bilateral filter的近似，很受欢迎。

2.3 Solvers: Solving Large Sparse Linear System

解大型稀疏线性方程组是一个很well-studied的问题，一般来讲，解法分为两大类：直接法(direct solver)和迭代法(iterative solver)。直接解法一般指高斯消元法(Gaussian

Elimination)，比如对于普通矩阵用LU Decomposition，对于对称正定阵用Cholesky Decomposition。这类算法的问题是，计算的过程中稀疏矩阵会变成稠密矩阵，如果矩阵规模较大(对于图像处理来讲很正常，比如对于1000×1000的图像，矩阵规模达到

1000000×1000000)，存储计算过程中的稠密矩阵都是问题，这就是文献中经常提到的fill-in问题[14]。这类方法的另一个问题是不太容易并行化。当然，也有很多新的direct算法克服了这些问题，参见Tim Davis的大作Direct Methods for Sparse Linear Systems [15](貌似Matlab里的backslash用的就是direct算法)。不过在computer vision中较受欢迎的还是iterative算法，推荐一本很棒的教科书，就是Yousef Saad的Iterative Methods for Sparse Linear Systems [16]。在ICCV 2007 gradient course中，有一个很棒的总结(section3 ppt)。这里也有个不错的总结。这里有个很棒的介绍Jacobi/Gauss-Seidel/SOR的ppt。

先将上述涉及到的方程组的系数矩阵及可以使用的算法进行一个分类，注意有些算法是对所有矩阵通用的，有些算法只能用于一些特定矩阵。以下分类基本是从上往下呈包含关系： 1. 普通矩阵(general)：LU Decomposition，Multigrid method；

2. 对角优势阵(diagonal dominant)：Jacobi/Gauss-Seidel/SOR(在diagonal dominant的情况下才收敛)；

2. 对称正定阵(symmetric positive-definite, SPD)：Cholesky Decomposition，Conjugate Gradient，Hierarchical Preconditioning (ABF) [14][17]；

3. M-matrix(非对角元素是non-positive的Laplacian Matrix，包括上述的Poisson Equation，colorization以及WLS filter中的Laplacian Matrix，但是不包括matting中的矩阵)：Hierarchical Preconditioning (HSC)[13]；

4. Spatially homogeneous Laplacian Matrix in Poisson Equation(在[13]中被如此称呼，注意跟homogeneous Poisson Equation不同)：FFT-based Poisson Solver (or see Chapter 2.2.6, Saad [16])；

这些涉及到的算法的复杂度如下(参见这里)(N是未知元素的个数，即图像像素个数)：

算法 LU Decomposition时间复杂度 N^3 适用矩阵类型 General Jacobi/Gauss-SeidelSORN^2 N^(3/2) Diagonal dominant Diagonal dominant Symmetric positive-definite Symmetric positive-definite M-matrix (off-diagonal non-positive) General Poisson Equation Conjugate GradientABF[17]N^(3/2) N^(3/2) HSC[13]N Multigrid methodN FFT-based methodNlogN 由上面可以看出，一般想要速度快的solver都会用Multigrid method，只是对于irregular的矩阵，quality不是很好。另外由于computer vision中的problem一般都是对称正定阵(甚至大多都是M-matrix)，Preconditioned Conjugate Gradient和SOR也很受欢迎。对于M-matrix，今年SIGGRAPH出现的HSC[13]算法也值得一试。

2.4 Reference

[1] R. Fattal, D. Lischinski, and M. Werman, \Gradient Domain High Dynamic Range Compression,\

[2] P. Perez, M. Gangnet, and A. Blake, \Poisson Image Editing,\[3] A. Levin, D. Lischinski, and Y. Weiss, “Colorization Using Optimization,” SIGGRAPH, 2004.

[4] A. Levin, D. Lischinski, and Y. Weiss, “A Closed-Form Solution to Natural Image Matting,” CVPR, 2006. ->TPAMI2008 extension.

[5] Z. Farbman, R. Fattal, D. Lischinski, and R. Szeliski, “Edge-Preserving Decompositions for Multi-Scale Tone and Detail Manipulation,” SIGGRAPH, 2008. [6] P. Burt and E. Adelson, \A Multiresolution Spline with Application to Image Mosaics,\TOG, 1983.

[7] P. Bhat, C.L. Zitnick, M. Cohen, and B. Curless, \GradientShop: A Gradient-Domain Optimization Framework for Image and Video Filtering,\

[8] D. Lischinski, Z. Farbman, M. Uyttendaelem, and R. Szeliski, “Interactive Local Adjustment of Tonal Values,” SIGGRAPH, 2006.

[9] A. Orzan, A. Bousseau, H. Winnem?ller, P. Barla, J. Thollot, and D. Salesin, \Diffusion Curves: A Vector Representation for Smooth-Shaded Images,\[10] J. McCann and N. Pollard, \Real-Time Gradient-Domain Painting,\2008.

[11] S. Paris, S.W. Hasinoff, J. Kautz, \Local Laplacian Filters: Edge-aware Image Processing with a Laplacian Pyramid,\

[12] K. He, J. Sun, and X. Tang, \Guided Image Filtering,\TPAMI 2012 extension.

[13] D. Krishnan, R. Fattal, and R. Szeliski, \Efficient Preconditioning of Laplacian Matrices for Computer Graphics,\

[14] R. Szeliski, \Locally Adapted Hierarchical Basis Preconditioning,\[15] T. Davis, \Direct Methods for Sparse Linear Systems,\

[16] Y. Saad, \Iterative Methods for Sparse Linear Systems,\[17] D. Krishnan and R. Szeliski, \Multigrid and Multilevel Preconditioners for Computational Photography,\

图像处理中的全局优化技术(Global optimization techniques in image processing and computer vision) (三)

2013-09-25 11:22 1083人阅读 评论(1) 收藏 举报

算法图像处理计算机视觉imagevision

本文来源：https://www.bwwdw.com/article/vdkg.html