其中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