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])：