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

1、 HYPERLINK /mulinb/article/details/8989205 图像处理中的全局优化技术(Global optimization techniques in image processing and computer vision) (一)2013-05-29 14:261659人阅读 HYPERLINK /mulinb/article/details/8989205 l comments 评论(1) HYPERLINK javascript:void(0); o 收藏 收藏 HYPERLINK /mulinb/article/details/8989205 l repo

2、rt o 举报 举报 HYPERLINK /tag/%e7%ae%97%e6%b3%95 t _blank 算法 HYPERLINK /tag/%e5%9b%be%e5%83%8f%e5%a4%84%e7%90%86 t _blank 图像处理 HYPERLINK /tag/%e8%ae%a1%e7%ae%97%e6%9c%ba%e8%a7%86%e8%a7%89 t _blank 计算机视觉 HYPERLINK /tag/image t _blank image HYPERLINK /tag/vision t _blank visionMulinB按：最近打算好好学习一下几种图像处理和计算机

3、视觉中常用的 global optimization (或 energy minimization) 方法，这里总结一下学习心得。分为以下几篇：1. Discrete Optimization: Graph Cuts and Belief Propagation (本篇) HYPERLINK /mulinb/article/details/9079645 t _blank 2. Quadratic Optimization : Poisson Equation and Laplacian Matrix HYPERLINK /mulinb/article/details/12005723 t _

4、blank 3. Variational Methods for Optical Flow Estimation4.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赋给

5、像素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的研究，比如 HYPERLINK http:/cms.brookes.ac.uk/staff/PhilipTorr/ t _blank 这位大牛的paper，这是题外话。这种ene

6、rgy 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等人

7、1989年发表的1，不过貌似没有引起太大的注意。真正使Graph Cuts在图像领域风靡起来的是两个俄罗斯人(貌似是在Cornell做出的成果)， HYPERLINK http:/www.csd.uwo.ca/yuri/ t _blank Yuri Boykov和 HYPERLINK http:/pub.ist.ac.at/vnk/ t _blank Vladimir Kolmogorov，以及他们的导师 HYPERLINK http:/www.cs.corne/rdz/index.htm t _blank Ramin Zabih。首先引起大家注意的是Boykov在ICCV 2001上的使用G

8、raph Cuts解决Interactive Image Segmentation的paper HYPERLINK http:/vision.stanf/teaching/cs231b_spring1213/papers/ICCV03_BoykovJolly.pdf t _blank 2，以及这篇paper提到的一个max-flow算法 HYPERLINK http:/www.csd.uwo.ca/yuri/Papers/pami04.pdf t _blank 3(该max-flow算法最早是发在2001年的一个CVPR Workshop上，后来扩展到TPAMI 3)。需要注意的是，这两篇pa

9、per里的Graph Cuts算法，只是针对只有两个label (待求变量是binary variable)的情况。而Boykov的2001 TPAMI paper HYPERLINK http:/www.csd.uwo.ca/yuri/Papers/pami01.pdf t _blank 4提出使用alpha expansion技术将多个label的问题转化成一系列的binary label问题去逼近，这使得Graph Cuts算法开始风靡起来。后来Kolmogorov的2004 TPAMI paper HYPERLINK http:/www.cs.corne/rdz/papers/kz-p

10、ami04.pdf t _blank 5进一步讨论了什么样的能量方程可以被Graph Cuts优化，并给出了一个简单清晰的根据能量方程构造相应graph的算法，该算法基本成为被大家广泛使用的Graph Cuts算法。Boykov和Kolmogorov的代码可以从 HYPERLINK http:/vision.csd.uwo.ca/code/ t _blank 这里找到。下面简单介绍一下Graph Cuts算法，先从binary label开始(见参考文献2 3)。顾名思义，Graph Cuts是将图像中的所有pixel以及两个label作为node，根据data cost和smoothness

11、 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中的

12、Theorem 1)。那么如何找到min-cut呢？在图论里，有证明找到min-cut其实等价于找到max-flow，即从s流往t的最大流量。其实，min-cut等价于max-flow的intuition很简单，从一个terminal流往另一个terminal的最大流量，其瓶颈肯定是min-cut的位置。 HYPERLINK .tw/u91029/Flow.html t _blank 这里有个有意思的介绍，关于网络里s-t flow的计算。计算max-flow的经典算法主要有两种，一种是基于augmenting-path，一种是基于push-relabeling。在Boykov和Kolmogo

13、rov的TPAMI 2004 paper 3里，介绍了一种基于augmenting-path，为了图像这种扁平graph量身定制的max-flow算法，通过实验证明了其效率， HYPERLINK http:/vision.csd.uwo.ca/code/maxflow-v3.01.zip t _blank 这里有他们的代码。在解决multi-labeling问题时 (其实是更为普遍和常见的问题)，在能量方程满足某些特定的条件下(注意：该限定条件其实挺难满足，后面讨论！)，可以使用alpha expansion算法将其转化为一系列binary-labeling问题来逼近，参见Boykov TPA

14、MI 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算法计

15、算出来，graph的构造比之前的binary-labeling要稍微复杂一些 (比如仅仅允许alpha expansion的话，有些跟b相连的edge weight要设成无穷大)。使用alpha expansion算法的步骤很简单，如下：cpp HYPERLINK /mulinb/article/details/8989205 o view plain view plain HYPERLINK /mulinb/article/details/8989205 o copy copy/alphaexpansionalgorithmpseudo-codeinitializelabeling;whil

16、enotconvergedforeachlabelainLconstructagraph;domax-flowcut;ifenergyissmallerthanbefore,acceptit;elsedeclineit;值得注意的是，这种alpha expansion只是multi-labeling问题的近似求解，而之前的max-flow算法是binary-labeling问题的exact求解方法。而且，为了使得这种alpha expansion时的graph可以被构造出来，能量方程需要满足一定的限定条件，具体来说，是能量方程中的pairwise term函数V_pq需要满足某些限定条件。在B

17、oykov TPAMI 2001 paper 4中称之为V_pq必须是一个metric(类似于满足“ HYPERLINK http:/en.wikip/wiki/Distance l General_case t _blank 距离”的定义，比如：可交换、满足三角不等式)。在Kolmogorov TPAMI 2004 paper 5 中将其推广为V_pq必须是一个submodular函数(文中称之为regular，其实后来都称之为submodular)，即函数V_pq必须满足V(0,0) + V(1,1) C+B)Valuedelta=A+D-C-B;ValuesubtrA=delta/3;A

18、=A-subtrA;C=C+subtrA;B=B+(delta-subtrA*2);这种truncating之后的算法其实并不能保证最终结果是strong local minimum (注意，没有truncating的alpha expansion只是能保证找到strong local minimum，不能保证是global mininum)，但是实际使用中效果不错。另外专门针对non-submodular进行优化的算法有QBPO，见Kolgoromov TPAMI 2007 paper HYPERLINK http:/pub.ist.ac.at/vnk/papers/KR-PAMI07.pd

19、f t _blank 7。1.2 Belief PropagationBelief Propagation是Graph Cuts的一个强劲对手，其渊源可以追溯到MIT在ICCV 2003上的paper HYPERLINK http:/people.csail./billf/tappenIccv.pdf t _blank 8，比较这两种方法在stereo上的性能，结果貌似不分上下，Graph Cuts略胜一点点。后来大牛Richard Szeliski联合一堆MRF的experts搞了一个benchmark评测这些方法，见TPAMI 2008 paper HYPERLINK http:/visi

20、/MRF/pdf/MRF-PAMI.pdf t _blank 9，和这个 HYPERLINK /MRF/ t _blank benchmark，上面有code可以下载，集成了很多算法，非常值得研究。结论是，Graph Cuts (alpha expansion)算法表现比较出色，另外Belief Propagation的一个改进算法叫Tree ReWeighted Message Passing (TRW-S)也表现出色，而Belief Propagation似乎表现不那么理想。不过其实其中除了Photom

21、ontage之外的其他比较中，基本都难分高下(在Photomontage中，alpha expansion完爆其他算法)。在实际使用中，至少在stereo的 HYPERLINK /stereo/eval/ t _blank Middlebury benchmark上，Belief Propagation还是占了大多数席位。跟Graph Cuts相比，Belief Propagation至少有以下几个优点：(1). 对能量方程不存在submodular限制;(2). implement非常简单 (虽然理论比较难懂，但是算法implement非

22、常之简单);(3). 快速算法很快 (比如Hierarchical Belief Propagation，见Pedro Felzenszwalb的IJCV 2006 paper HYPERLINK /pff/bp/ t _blank 10，有代码 HYPERLINK /pff/bp/ t _blank 在此).下面简单介绍一下Belief Propagation算法，其背景知识可以参考Coursera上Daphne Koller的 HYPERLINK https:/www.cours/course/pgm t _blank

23、 Probabilistic Graphical Model。Belief Propagation (BP)算法最早可以追溯到Pearl的书 11，该算法最初是设计在tree或者graph without cycles上通过message passing的方式计算MAP的(也就是上面提到的energy minimization)，在这种情况下，BP可以计算出exact的结果(其实等价于dynamic programming算法)。而在更为普遍的情况下，即graph中有cycle时，BP并不能保证可以converge，但是在很多情况下，可以converge到strong local minimu

24、m (有点类似alpha expansion)，见MIT大牛的TIT 2001 paper HYPERLINK http:/www.cs.huji.ac.il/yweiss/maxprodieee2.pdf t _blank 12。在这种情况下，BP一般被称为Loopy Belief Propagation，即graph中存在cycle使得message passing存在loop。另外，一般提到BP有两种，一种是max-product，一种是sum-product，前者是用来计算MAP的(max of probability product)，后者是用来计算marginal propabil

25、ity的，我们这里只讨论max-product (其实sum-product算法类似，只是计算message时稍有不同)。BP算法非常简单，流程如下：cpp HYPERLINK /mulinb/article/details/8989205 o view plain view plain HYPERLINK /mulinb/article/details/8989205 o copy copy/BeliefPropagationAlgorithmpseudo-code,supposerunTiterationsfor(intt=0;t HYPERLINK http:/www.wisdom.we

26、izmann.ac.il/levina/papers/Matting-Levin-Lischinski-Weiss-PAMI.pdf t _blank TPAMI2008 extension.5 Z. Farbman,R. Fattal, D. Lischinski, and R. Szeliski, “ HYPERLINK http:/www.cs.huji.ac.il/danix/epd/index.html t _blank Edge-Preserving Decompositions for Multi-Scale Tone and Detail Manipulation,” SIGG

27、RAPH, 2008.6 P. Burt and E. Adelson, HYPERLINK /majumder/vispercep/burtadelson.pdf t _blank A Multiresolution Spline with Application to Image Mosaics, TOG, 1983.7 P. Bhat, C.L. Zitnick, M. Cohen, and B. Curless, HYPERLINK /projects/gradientshop/ t _blank GradientShop: A

28、 Gradient-Domain Optimization Framework for Image and Video Filtering, TOG, 2009.8 D. Lischinski,Z. Farbman, M.Uyttendaelem, and R. Szeliski, “ HYPERLINK http:/www.cs.huji.ac.il/danix/itm/itm.pdf t _blank Interactive Local Adjustment of Tonal Values,” SIGGRAPH, 2006.9 A. Orzan, A. Bousseau, H. Winne

29、mller, P. Barla, J. Thollot, and D. Salesin, HYPERLINK http:/maverick.inria.fr/Publications/2008/OBWBTS08/ t _blank Diffusion Curves: A Vector Representation for Smooth-Shaded Images, SIGGRAPH, 2008.10 J. McCann and N. Pollard, HYPERLINK http:/graph/projects/gradient-paint/ t _blank Real-Time Gradie

30、nt-Domain Painting, SIGGRAPH, 2008.11 S. Paris, S.W. Hasinoff, J. Kautz, HYPERLINK http:/people.csail./sparis/publi/2011/siggraph/ t _blank Local Laplacian Filters: Edge-aware Image Processing with a Laplacian Pyramid, SIGGRAPH, 2011.12 K. He, J. Sun, and X. Tang, HYPERLINK http:/research.micro/en-u

31、s/um/people/kahe/eccv10/index.html t _blank Guided Image Filtering, ECCV, 2010. - HYPERLINK http:/research.micro/en-us/um/people/kahe/publications/pami12guidedfilter.pdf t _blank TPAMI2012 extension.13 D. Krishnan, R. Fattal, and R. Szeliski, HYPERLINK http:/www.cs.huji.ac.il/raananf/projects/hsc/ t

32、 _blank Efficient Preconditioning of Laplacian Matrices for Computer Graphics, SIGGRAPH, 2013.14 R. Szeliski, HYPERLINK http:/research.micro/pubs/75694/Szeliski-SG06.pdf t _blank Locally Adapted Hierarchical Basis Preconditioning, SIGGRAPH, 2006.15 T. Davis, HYPERLINK /research/sparse/CSparse/ t _bl

33、ank Direct Methods for Sparse Linear Systems, 2006.16 Y. Saad, HYPERLINK http:/www-users./saad/IterMethBook_2ndEd.pdf t _blank Iterative Methods for Sparse Linear Systems, Second Edition, 2003.17 D. Krishnan and R. Szeliski, HYPERLINK /dilip/research/abf/ t _blank Multigrid and Multilevel Preconditi

34、oners for Computational Photography, SIGGRAPH Asia, 2011. HYPERLINK /mulinb/article/details/12005723 图像处理中的全局优化技术(Global optimization techniques in image processing and computer vision) (三)2013-09-25 11:221083人阅读 HYPERLINK /mulinb/article/details/12005723 l comments 评论(1) HYPERLINK javascript:void(0

35、); o 收藏 收藏 HYPERLINK /mulinb/article/details/12005723 l report o 举报 举报 HYPERLINK /tag/%e7%ae%97%e6%b3%95 t _blank 算法 HYPERLINK /tag/%e5%9b%be%e5%83%8f%e5%a4%84%e7%90%86 t _blank 图像处理 HYPERLINK /tag/%e8%ae%a1%e7%ae%97%e6%9c%ba%e8%a7%86%e8%a7%89 t _blank 计算机视觉 HYPERLINK /tag/image t _blank image HYPER

36、LINK /tag/vision t _blank visionMulinB按：最近打算好好学习一下几种图像处理和计算机视觉中常用的 global optimization (或 energy minimization) 方法，这里总结一下学习心得。分为以下几篇： HYPERLINK /mulinb/article/details/8989205 t _blank 1. Discrete Optimization: Graph Cuts and Belief Propagation HYPERLINK /mulinb/article/details/9079645 t _blank 2. Qu

37、adratic Optimization : Poisson Equation and Laplacian Matrix3. Variational Methods for Optical Flow Estimation(本篇)4.TODO: Likelihood Maximization(e.g., Blind Deconvolution)3. Variational Methods for Optical Flow EstimationOptical Flow(光流法)这个词乍一看很能唬住人，啥东东这么高级，是追踪光的流动轨迹吗？没这么玄乎。其实optical flow是一个很朴实的low

38、-level vision的东西，就是每个pixel从一帧图像到另一帧图像的位置偏移(displacement)。如下图所示， Two Input Frames Optical Flow (Vector Plot) Optical Flow (Color Plot)上面的color plot，其实是通过一个二维的color wheel将2D的motion vector用颜色show出来，常用的color wheel如下所示(中心点表示横向和纵向的位移都为0，用白色表示)：在上面的例子中，可以看出背景中大多数pixel是往左上方偏移一点(相对于镜头)，因此在optical flow中，背景呈现浅

39、蓝色(在color wheel的第二象限)。至于计算optical flow这个东东到底有啥用途，可以说绝对是视频编辑的基石，参见 HYPERLINK http:/hammerbchen.blogspot.hk/2011/10/art-of-optical-flow.html t _blank 这里(Art of Optical Flow，被墙的可以参看 HYPERLINK http:/www.fxgui/featured/art_of_optical_flow/ t _blank 这里的英文原版)有一篇有趣的介绍optical flow在电影编辑中的作用(比如合成黑客帝国中的超级慢镜头)。正

40、是由于其重要的作用，如何计算optical flow从1980s就开始成为计算机视觉的研究热门。早期的计算主要focus在计算subpixel级的displacement，随着视频分辨率的增加，最近的很多算法开始考虑较大的displacement，通常需要先计算帧与帧之间pixel级别的correspondence，然后进行warping后再使用传统算法计算subpixel精度的optical flow结果。至于评测optical flow算法的accuracy，最经典的一个benchmark是 HYPERLINK /flow/eval/

41、t _blank Middlebury，但其用于排名的dataset只有12张图，比较容易overfitting，最近两年又出现两个比较popular的benchmark， HYPERLINK http:/sintel.is.tue.mpg.de/results t _blank Sintel和 HYPERLINK http:/www.cvlib/datasets/kitti/eval_stereo_flow.php?benchmark=flow t _blank KITTI。3.1 Classic Framework我们先从optical flow算法的目的说起。令I(x,y,t)表示在t时

42、刻frame上像素(x,y)处的亮度(或颜色)，那么optical flow的目的就是求出在t+1时刻的frame上，该像素相对于原来(x,y)的位移量(u,v)，用方程表示即：其中u和v是未知量。这就是optical flow中著名的Brightness Constancy Model。不过，数字图像毕竟是离散化pixel by pixel的，如果只给出两帧图像，如何计算出每个pixel的subpixel级的displacement(位移)呢？如果从correspondence的角度去考虑，在frame1中的某个pixel，只能找到其在frame2中对应的pixel整数位置，这样只能得到pi

43、xel级的displacement，而无法精确到subpixel精度。在经典的optical flow算法中，一般利用 HYPERLINK http:/en.wikip/wiki/Taylor_series t _blank 一阶泰勒展开作为工具来建立图像gradient和displacement之间的关系，这一步骤通常被称为Linearization。具体原理如下( HYPERLINK http:/www.cs.toron/fleet/research/Papers/flowChapter05.pdf t _blank 这里有个不错的tutorial介绍的也很详细，by David Flee

44、t and Yair Weiss)：假设图像的intensity是连续的，如下图所示(1D case)，黑色的曲线表示frame1中的图像，蓝色的曲线表示frame2中的图像，待求的displacement是深蓝色的箭头dx/dt。对曲线进行一阶泰勒展开，其实就是假设曲线的局部是线性的，这样可以考察如图的红绿蓝组成的三角形。注意，dI/dx并非是红色线段的长度，而是其斜率。这样可以得到图中所示的关系，注意负号是因为斜率其实表示的是钝角的tan。这样一来就建立了图像的derivative和displacement之间的关系，注意dI/dx是图像在spatial上的derivative，dI/dt

45、是图像在temporal上的derivative。将上面的这个方程用在2D的图像上，对于每个pixel，可以写出以下方程：其中，I_x和I_y是图像沿spatial的x和y两个方向的derivative(即图像gradient的两个分量)，I_t是图像沿temporal的derivative(可以用两帧图像的difference来近似)，u和v是该pixel沿x和y方向的位移，也就是待求的optical flow未知量。这其实就是对上面的Brightness Constancy Model的Lineariazation的结果，也就是optical flow中著名的Gradient Constr

46、aint Equation。需要注意的是，上面这个模型是建立在两个假设基础上：第一，图像变化是连续的；第二，位移不是很大。如果这两点假设不成立，那么泰勒展开的近似是很差的。直觉想象一下，如果图像不是连续的，而且displacement很大，无论如何是无法将displacement和图像gradient联系起来的。不过在实际中，上述两个假设可以很容易使其成立。关于第一点，一般可以预先对图像进行Gaussian Smoothing，使其变化较为平缓；关于第二点，一般是对图像降分辨率建立金字塔，通过Coarse-To-Fine的方式一步一步去求解。基于上面的方程，最经典的两个optical flow

47、算法，Lucas-Kanade方法 HYPERLINK /pub_files/pub3/lucas_bruce_d_1981_2/lucas_bruce_d_1981_2.pdf t _blank 1和Horn-Schunck方法 HYPERLINK http:/people.csail./bkph/papers/Optical_Flow_OPT.pdf t _blank 2，分别从不同的角度增加了求解该方程的稳定性。Lucas-Kanade方法是将每个pixel周围的一些pixels考虑进来，但每个pixel的未知量是单独求解的，所以是一种local方法；而Horn-Schunck方法是将上

48、面的方程纳入到一个regularization的framework中，加入optical flow是locally smooth的prior，所有的pixel的未知量之间相互依赖，需要用global optimization的方法求解。目前state-of-the-art的方法，一般都是基于Horn-Schunck的framework做的，这里要介绍的经典optical flow算法也是基于这个framework经过几次改良得到的。石器时代：令小写的u和v分别表示每个pixel处沿x和y方向的displacement，大写的U和V分别表示由所有pixel的u和v组成的map，那么Horn-Sc

49、hunck的目标函数可以写作如下形式：可以看出，第一项data term其实就是Brightness Constancy Model的Least Square形式，第二项regularization term目的是令结果的U和V较为smooth。对该目标函数进行minimization即可求出U和V。由于该目标函数是quadratic，根据calculus of variation(变分法)中的 HYPERLINK http:/en.wikip/wiki/Euler%E2%80%93Lagrange_equation l Several_functions_of_several_variabl

50、es t _blank Euler-Lagrange Equation (two unknown function - U and V, two variables - x and y)可以将其转化为偏微分方程形式，再进行离散化，最终可以归结为求解一个大型线性方程组，利用Conjugate Gradient或者SOR可以很容易求解，参见 HYPERLINK /mulinb/article/details/9079645 t _blank 上一篇文章。青铜时代：根据robust statistics理论，quadratic的目标函数对outlier太敏感。而其实在locally smooth a

51、ssumption下，最理想的情况是一个场景中只有一种motion。如果有多种motion，那么就相互构成outlier，会严重影响结果，这显然是quadratic目标函数的软肋。而这种情况恰恰是现实中最常发生的。因此，Michael J. Black和P. Anandan HYPERLINK /black/Papers/cviu.63.1.1996.pdf t _blank 3提出了将上述目标函数中的L2 norm换成更为robust的函数(比如L1 norm或者truncated L1 norm)，形成了目前较为常用的形式：目前最常用的robust函数是

52、Charbonnier函数psi(x2)=sqrt(x2+1e-6)，即L1 norm (增加了一个很小的数字1e-6为了使其convex，容易求解optimization)。这样一来，data term是L1 norm，regularization term使用了L1 norm后其实就成了Total Variation，因此这个目标函数又被称为TV-L1formulation。另外，目前流行的coarse-to-fine、warping的framework也是在这篇paper里基本定形的。白银时代：为了避免光照对Brightness Constancy Model的影响，Thomas Bro

53、x等人 HYPERLINK rmatik.uni-freiburg.de/Publications/2004/Bro04a/brox_eccv04_of.pdf t _blank 4提出在data term里引入Gradient Constancy Model(不妨看做在原来的3个color channel之外多加两个gradient channel)，大大提高了算法的精确度。值得一提的是，这篇paper里提到的fixed point iteration解法( HYPERLINK http:/people.csail./celiu/OpticalFlow/ t _blank 这里有Ce Liu

54、的C+ code)比之前的graduated non-convexity算法( HYPERLINK /dqsun/code/ijcv_flow_code.zip t _blank 这里有Deqing Sun的Matlab code)貌似速度要快不少(或许是implementation的区别)。另外值得一提的是，在 HYPERLINK /flow/eval/results/results-e1.php t _blank Middlebury上有个叫improved TV-L1 HYPERLINK http:

55、/vision.in.tum.de/_media/spezial/bib/dagstuhlopticalflowchapter.pdf t _blank 6的算法，速度貌似很快，效果也不错。其实之前的很多算法都是基于TV-L1 formulation的，不过这篇paper 6 主要是介绍一种快速算法的。其实，该文的主要contribution在于：第一，该文提出用texture decomposition的方式先提取image的texture，然后用texture作为data term，旨在避免光照等的影响，跟前面的加入gradient data term思路类似。第二，该文提出对每一个ite

56、ration求解出的flow进行median filter去掉outlier，后来这个小trick被证实是很有效的一步 7。另外，该文 HYPERLINK http:/vision.in.tum.de/_media/spezial/bib/dagstuhlopticalflowchapter.pdf t _blank 6中对implementation的描述也比较细致，如果要实现optical flow算法，这篇paper很值得一看(可以直接忽略其之前的版本5)。黄金时代：对经典算法中使用的各种trick进行总结的集大成者是Deqing Sun等人的 HYPERLINK http:/cs.br

57、/dqsun/pubs/cvpr_2010_flow.pdf t _blank CVPR 2010 paper 7及其扩展 HYPERLINK /dqsun/pubs/Sun2013QAP.pdf t _blank IJCV 2013 paper 8。该猛人将之前paper中五花八门的trick统统试了一遍，总结出哪些是精华，哪些是糟粕。最难能可贵的是，他将所有的 HYPERLINK /dqsun/code/ijcv_flow_code.zip t _blank matlab代码公布于众，使得后来者省去了不少

58、揣测如何做implementation的时间，强赞一个。美中不足的是，这些实验是在Middlebury的training data上完成的，但是Middlebury的dataset有点小，只有几张图，难免让人觉得有可能overfitting，调查的trick是否真的如paper中得出的结论那般，值得商榷(在其IJCV 2013 paper 8中也发现，算法在 HYPERLINK http:/www.cvlib/datasets/kitti/eval_stereo_flow.php?benchmark=flow t _blank KITTI的benchmark上和在 HYPERLINK http

59、://flow/eval/results/results-e1.php t _blank Middlebury上performance很不一样)。3.2 Algorithm and Implementation Details这里简单地对求解上述framework的算法理一理，主要参考Thomas Brox的paper HYPERLINK rmatik.uni-freiburg.de/Publications/2004/Bro04a/brox_eccv04_of.pdf t _blank 4以及Ce Liu的 HYPERLINK http:/peopl

60、e.csail./celiu/OpticalFlow/ t _blank Implementation及他对Brox算法的重新推导 HYPERLINK http:/people.csail./celiu/Thesis/CePhDThesis.pdf t _blank 9(Appendix A)。为了简化推导过程，下面假设图像I是由3个color channel加上2个gradient channel组成的5个channel的图像(paper 4中推导时将gradient channel显式的表示了出来，看起来过于复杂)。由上面的TV-L1 formulation，经过Linearization