<p></p>
<p><em>MulinB按：最近打算好好学习一下几种图像处理和计算机视觉中常用的 global optimization (或 energy minimization) 方法，这里总结一下学习心得。分为以下几篇：</em></p>
<p><em><a href="http://blog.csdn.net/mulinb/article/details/8989205" rel="noopener noreferrer" target="_blank"><u></u></a></em></p>
<p><em><a href="http://blog.csdn.net/mulinb/article/details/8989205" rel="noopener noreferrer" target="_blank"><u>1. Discrete Optimization: Graph Cuts and Belief Propagation</u></a><br> </em></p>
<p><em>2. Quadratic Optimization: Poisson Equation and Laplacian Matrix<em> (本篇)</em><br> </em></p>
<p><em><a href="http://blog.csdn.net/mulinb/article/details/12005723" rel="noopener noreferrer" target="_blank"><u>3. Variational Methods for Optical Flow Estimation</u></a><br> </em></p>
<em><u>4. <em>TODO: Likelihood Maximization</em> (e.g., Blind Deconvolution)</u></em>
<p><br> </p>
<p><span style="font-size:24px"><strong>2. Quadratic Optimization: Poisson Equation and Laplacian Matrix<br> </strong></span></p>
<p>Quadratic Optimization (Least Squares Minimization)在图像处理中的魅力要从SIGGRAPH 02和03年的两篇Gradient Domain Image Editing文章说起：Fattal的HDR Compression<a href="http://www.cs.huji.ac.il/%7Edanix/hdr/hdrc.pdf" rel="noopener noreferrer" target="_blank">[1]</a> 和Perez的Poisson Image Editing <a href="http://www.irisa.fr/vista/Papers/2003_siggraph_perez.pdf" rel="noopener noreferrer" target="_blank"> [2]</a>。 其后，Levin的两篇文章Colorization <a href="http://www.cs.huji.ac.il/~yweiss/Colorization/" rel="noopener noreferrer" target="_blank"> [3]</a>和Closed-Form Matting <a href="http://www.wisdom.weizmann.ac.il/~levina/papers/Matting-Levin-Lischinski-Weiss-CVPR06.pdf" rel="noopener noreferrer" target="_blank"> [4]</a>更是将其魅力展现的淋漓尽致。而Farbman的基于Weighted Least Squares的WLS filter <a href="http://www.cs.huji.ac.il/~danix/epd/index.html" rel="noopener noreferrer" target="_blank"> [5]</a>也是在Edge-preserving Filter领域名声大噪。由于目标函数是quadratic, 这类问题的求解一般比较容易，大多都可以最终归结为求解一个大型稀疏线性方程组。而数值求解大型线性方程组是一个由来已久的问题，有着各种现成的solver，更是有着为以上这类问题量身定做的solver，见下文solver小节。<br> </p>
<p>题外话：以色列的耶路撒冷希伯来大学(The Hebrew University of Jerusalem)的<a href="http://www.cs.huji.ac.il/~danix/" rel="noopener noreferrer" target="_blank">Lischinski</a>教授貌似很偏爱这类方法，上面提到的这些文章大多有他的署名。</p>
<br>
<p><span style="font-size:18px"><strong>2.1 Problem I: Gradient Domain Image Editing</strong></span></p>
<p>有心理学为证(见<a href="http://www.irisa.fr/vista/Papers/2003_siggraph_perez.pdf" rel="noopener noreferrer" target="_blank">Poisson Image Editing [2]</a>文章的introduction部分)，对图像的gradient进行修改可以产生比较不容易感知到的artifacts，这使得很多图像编辑的工作可以放到gradient domain使得效果很逼真，比如下图的图像拼合例子(图例来自<a href="http://www.irisa.fr/vista/Papers/2003_siggraph_perez.pdf" rel="noopener noreferrer" target="_blank">[2]</a>)：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-7b983720a59eb089bdd1ecd26664ebd6"><br> </p>
<p>其实对gradient domain进行修改而获得逼真的编辑效果由来已久，最早见于1983年Burt-Adelson的Laplacian Pyramid <a href="http://www.ics.uci.edu/~majumder/vispercep/burtadelson.pdf" rel="noopener noreferrer" target="_blank"> [6]</a>图像融合(<a href="http://hi.baidu.com/jiamn/item/1a8249b93e4dc3d585dd7952" rel="noopener noreferrer" target="_blank">这里</a>有个简洁的中文介绍)，这是题外话。在gradient domain进行图像编辑的pipeline一般如下(图例修改自<a href="http://www.umiacs.umd.edu/~aagrawal/ICCV2007Course/" rel="noopener noreferrer" target="_blank">ICCV 2007 Course -- Gradient Domain Manipulation Techniques</a>，顺便赞一个，nice ppt!)：</p>
<p><img alt="" height="333" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-292a7b23fa0ef4591272fe9b1356fc85" width="887"><br> </p>
<p>其中第一步的gradient processing根据不同的需求有具体的操作，比如HDR Compression里是将较大的gradient value进行削弱，而上面的图像拼合例子(Seamless Clone)则是将源图像的gradient拷贝到目标区域。而其中第二步中由gradient重建出新图像并非那么容易，因为经过编辑后的gradient一般是不可积分的，这时Quadratic Optimization粉墨登场。<br> </p>
<p><br> </p>
<p>假设待求图像为<span style="font-family:Times New Roman">I</span>，修改后的已知gradient是<span style="font-family:Times New Roman">G</span>，则通过Least Squares Minimization可以将问题formulate成如下(使得待求图像<span style="font-family:Times New Roman">I</span>的gradient在L2 norm下尽量接近<span style="font-family:Times New Roman">G</span>)：</p>
<p><img |
|
转播
