圖像處理中的全局優(yōu)化技術(shù)(經(jīng)典至極)

1、 HYPERLINK /mulinb/article/details/8989205 圖像處理中的全局優(yōu)化技術(shù)(Global optimization techniques in image processing and computer vision) (一)2013-05-29 14:261659人閱讀 HYPERLINK /mulinb/article/details/8989205 l comments 評(píng)論(1) HYPERLINK javascript:void(0); o 收藏 收藏 HYPERLINK /mulinb/article/details/8989205 l repo

2、rt o 舉報(bào) 舉報(bà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 計(jì)算機(jī)視覺 HYPERLINK /tag/image t _blank image HYPERLINK /tag/vision t _blank visionMulinB按：最近打算好好學(xué)習(xí)一下幾種圖像處理和計(jì)算機(jī)

3、視覺中常用的 global optimization (或 energy minimization) 方法，這里總結(jié)一下學(xué)習(xí)心得。分為以下幾篇：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成以下能量方程：其中第一項(xiàng)叫data term (或叫unary term)，是將label l_p賦給

5、像素p時(shí)的cost，第二項(xiàng)叫smoothness term (或叫pairwise term)，是每兩個(gè)相鄰pixel的labeling不同時(shí)產(chǎn)生的cost (w_pq是spatial varying weight，比如跟p和q的difference相關(guān))。傳統(tǒng)的smoothness term一般只考慮兩兩(pairwise)相鄰的pixel，最近幾年的CVPR和ICCV上開始出現(xiàn)很多higher-order MRF的研究，比如 HYPERLINK http:/cms.brookes.ac.uk/staff/PhilipTorr/ t _blank 這位大牛的paper，這是題外話。這種ene

6、rgy minimization framework其實(shí)從概率的角度看，等價(jià)于求Markov Random Field (MRF) 的maximum a posteriori (MAP) 概率。求解這類energy minimization的方法，最流行的有兩個(gè)，Graph Cuts和Belief Propagation。1.1 Graph Cuts剛開始學(xué)習(xí)Graph Cuts時(shí)，不知道到底這方法是從哪篇paper最早提出來的，因?yàn)樵诤髞淼膒aper里引用的參考文獻(xiàn)一般指向好幾個(gè)來源，這里先大致梳理一下參考文獻(xiàn)。一般認(rèn)為，將Graph Cuts引入圖像處理領(lǐng)域的先驅(qū)paper是Greig等人

7、1989年發(fā)表的1，不過貌似沒有引起太大的注意。真正使Graph Cuts在圖像領(lǐng)域風(fēng)靡起來的是兩個(gè)俄羅斯人(貌似是在Cornell做出的成果)， HYPERLINK http:/www.csd.uwo.ca/yuri/ t _blank Yuri Boykov和 HYPERLINK http:/pub.ist.ac.at/vnk/ t _blank Vladimir Kolmogorov，以及他們的導(dǎo)師 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提到的一個(gè)max-flow算法 HYPERLINK http:/www.csd.uwo.ca/yuri/Papers/pami04.pdf t _blank 3(該max-flow算法最早是發(fā)在2001年的一個(gè)CVPR Workshop上，后來擴(kuò)展到TPAMI 3)。需要注意的是，這兩篇pa

9、per里的Graph Cuts算法，只是針對(duì)只有兩個(gè)label (待求變量是binary variable)的情況。而Boykov的2001 TPAMI paper HYPERLINK http:/www.csd.uwo.ca/yuri/Papers/pami01.pdf t _blank 4提出使用alpha expansion技術(shù)將多個(gè)label的問題轉(zhuǎn)化成一系列的binary label問題去逼近，這使得Graph Cuts算法開始風(fēng)靡起來。后來Kolmogorov的2004 TPAMI paper HYPERLINK http:/www.cs.corne/rdz/papers/kz-p

10、ami04.pdf t _blank 5進(jìn)一步討論了什么樣的能量方程可以被Graph Cuts優(yōu)化，并給出了一個(gè)簡單清晰的根據(jù)能量方程構(gòu)造相應(yīng)graph的算法，該算法基本成為被大家廣泛使用的Graph Cuts算法。Boykov和Kolmogorov的代碼可以從 HYPERLINK http:/vision.csd.uwo.ca/code/ t _blank 這里找到。下面簡單介紹一下Graph Cuts算法，先從binary label開始(見參考文獻(xiàn)2 3)。顧名思義，Graph Cuts是將圖像中的所有pixel以及兩個(gè)label作為node，根據(jù)data cost和smoothness

11、 cost建立node之間的edge，這樣構(gòu)造一個(gè)(無向)graph，然后通過cut算法將整個(gè)graph切成兩個(gè)分離的部分。如下圖所示：注意，圖中的cut會(huì)切斷它經(jīng)過的所有edge(包括藍(lán)色、紅色、和土黃色的edge)。如果將兩個(gè)label的node看成兩個(gè)特殊的terminal，這樣的一個(gè)cut會(huì)阻斷所有s連往t的路徑(edge)。在Boykov的ICCV 2001 paper 2中，他證明了通過簡單的方式構(gòu)造這樣的一個(gè)graph，如果能找到一個(gè)min-cut (即該cut經(jīng)過的edge cost加起來在所有possible的cut中最小)，其實(shí)就是上面的能量方程的最小解 (見paper中的

12、Theorem 1)。那么如何找到min-cut呢？在圖論里，有證明找到min-cut其實(shí)等價(jià)于找到max-flow，即從s流往t的最大流量。其實(shí)，min-cut等價(jià)于max-flow的intuition很簡單，從一個(gè)terminal流往另一個(gè)terminal的最大流量，其瓶頸肯定是min-cut的位置。 HYPERLINK .tw/u91029/Flow.html t _blank 這里有個(gè)有意思的介紹，關(guān)于網(wǎng)絡(luò)里s-t flow的計(jì)算。計(jì)算max-flow的經(jīng)典算法主要有兩種，一種是基于augmenting-path，一種是基于push-relabeling。在Boykov和Kolmogo

13、rov的TPAMI 2004 paper 3里，介紹了一種基于augmenting-path，為了圖像這種扁平graph量身定制的max-flow算法，通過實(shí)驗(yàn)證明了其效率， HYPERLINK http:/vision.csd.uwo.ca/code/maxflow-v3.01.zip t _blank 這里有他們的代碼。在解決multi-labeling問題時(shí) (其實(shí)是更為普遍和常見的問題)，在能量方程滿足某些特定的條件下(注意：該限定條件其實(shí)挺難滿足，后面討論！)，可以使用alpha expansion算法將其轉(zhuǎn)化為一系列binary-labeling問題來逼近，參見Boykov TPA

14、MI 2001 paper 4。見下圖：這種alpha expansion思路很簡單，當(dāng)處理每一個(gè)label時(shí)(假設(shè)其為a)，將其他所有的label看成一個(gè)label package(假如稱之為b)，這時(shí)問題就變成了binary-labeling。此時(shí)在進(jìn)行cut時(shí)，如果一個(gè)原來是a的pixel被cut給b，將無法確定到底給該pixel具體哪一個(gè)label(由于b是個(gè)大雜燴)。所以在進(jìn)行cut時(shí)，只允許原來是b的pixel被cut給a，也就是標(biāo)記為a的pixel在expanding，這就是算法名字的來源。需要注意的是，為了使得這樣的一次alpha expansion可以被max-flow算法計(jì)

15、算出來，graph的構(gòu)造比之前的binary-labeling要稍微復(fù)雜一些 (比如僅僅允許alpha expansion的話，有些跟b相連的edge weight要設(shè)成無窮大)。使用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時(shí)的graph可以被構(gòu)造出來，能量方程需要滿足一定的限定條件，具體來說，是能量方程中的pairwise term函數(shù)V_pq需要滿足某些限定條件。在B

17、oykov TPAMI 2001 paper 4中稱之為V_pq必須是一個(gè)metric(類似于滿足“ HYPERLINK http:/en.wikip/wiki/Distance l General_case t _blank 距離”的定義，比如：可交換、滿足三角不等式)。在Kolmogorov TPAMI 2004 paper 5 中將其推廣為V_pq必須是一個(gè)submodular函數(shù)(文中稱之為regular，其實(shí)后來都稱之為submodular)，即函數(shù)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之后的算法其實(shí)并不能保證最終結(jié)果是strong local minimum (注意，沒有truncating的alpha expansion只是能保證找到strong local minimum，不能保證是global mininum)，但是實(shí)際使用中效果不錯(cuò)。另外專門針對(duì)non-submodular進(jìn)行優(yōu)化的算法有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的一個(gè)強(qiáng)勁對(duì)手，其淵源可以追溯到MIT在ICCV 2003上的paper HYPERLINK http:/people.csail./billf/tappenIccv.pdf t _blank 8，比較這兩種方法在stereo上的性能，結(jié)果貌似不分上下，Graph Cuts略勝一點(diǎn)點(diǎn)。后來大牛Richard Szeliski聯(lián)合一堆MRF的experts搞了一個(gè)benchmark評(píng)測(cè)這些方法，見TPAMI 2008 paper HYPERLINK http:/visi

20、/MRF/pdf/MRF-PAMI.pdf t _blank 9，和這個(gè) HYPERLINK /MRF/ t _blank benchmark，上面有code可以下載，集成了很多算法，非常值得研究。結(jié)論是，Graph Cuts (alpha expansion)算法表現(xiàn)比較出色，另外Belief Propagation的一個(gè)改進(jìn)算法叫Tree ReWeighted Message Passing (TRW-S)也表現(xiàn)出色，而Belief Propagation似乎表現(xiàn)不那么理想。不過其實(shí)其中除了Photom

21、ontage之外的其他比較中，基本都難分高下(在Photomontage中，alpha expansion完爆其他算法)。在實(shí)際使用中，至少在stereo的 HYPERLINK /stereo/eval/ t _blank Middlebury benchmark上，Belief Propagation還是占了大多數(shù)席位。跟Graph Cuts相比，Belief Propagation至少有以下幾個(gè)優(yōu)點(diǎn)：(1). 對(duì)能量方程不存在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算法，其背景知識(shí)可以參考Coursera上Daphne Koller的 HYPERLINK https:/www.cours/course/pgm t _blank

23、 Probabilistic Graphical Model。Belief Propagation (BP)算法最早可以追溯到Pearl的書 11，該算法最初是設(shè)計(jì)在tree或者graph without cycles上通過message passing的方式計(jì)算MAP的(也就是上面提到的energy minimization)，在這種情況下，BP可以計(jì)算出exact的結(jié)果(其實(shí)等價(jià)于dynamic programming算法)。而在更為普遍的情況下，即graph中有cycle時(shí)，BP并不能保證可以converge，但是在很多情況下，可以converge到strong local minimu

24、m (有點(diǎn)類似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，前者是用來計(jì)算MAP的(max of probability product)，后者是用來計(jì)算marginal propabil

25、ity的，我們這里只討論max-product (其實(shí)sum-product算法類似，只是計(jì)算message時(shí)稍有不同)。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 圖像處理中的全局優(yōu)化技術(shù)(Global optimization techniques in image processing and computer vision) (三)2013-09-25 11:221083人閱讀 HYPERLINK /mulinb/article/details/12005723 l comments 評(píng)論(1) HYPERLINK javascript:void(0

35、); o 收藏 收藏 HYPERLINK /mulinb/article/details/12005723 l report o 舉報(bào) 舉報(bà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 計(jì)算機(jī)視覺 HYPERLINK /tag/image t _blank image HYPER

36、LINK /tag/vision t _blank visionMulinB按：最近打算好好學(xué)習(xí)一下幾種圖像處理和計(jì)算機(jī)視覺中常用的 global optimization (或 energy minimization) 方法，這里總結(jié)一下學(xué)習(xí)心得。分為以下幾篇： 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(光流法)這個(gè)詞乍一看很能唬住人，啥東東這么高級(jí)，是追蹤光的流動(dòng)軌跡嗎？沒這么玄乎。其實(shí)optical flow是一個(gè)很樸實(shí)的low

38、-level vision的東西，就是每個(gè)pixel從一幀圖像到另一幀圖像的位置偏移(displacement)。如下圖所示， Two Input Frames Optical Flow (Vector Plot) Optical Flow (Color Plot)上面的color plot，其實(shí)是通過一個(gè)二維的color wheel將2D的motion vector用顏色show出來，常用的color wheel如下所示(中心點(diǎn)表示橫向和縱向的位移都為0，用白色表示)：在上面的例子中，可以看出背景中大多數(shù)pixel是往左上方偏移一點(diǎn)(相對(duì)于鏡頭)，因此在optical flow中，背景呈現(xiàn)淺

39、藍(lán)色(在color wheel的第二象限)。至于計(jì)算optical flow這個(gè)東東到底有啥用途，可以說絕對(duì)是視頻編輯的基石，參見 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在電影編輯中的作用(比如合成黑客帝國中的超級(jí)慢鏡頭)。正

40、是由于其重要的作用，如何計(jì)算optical flow從1980s就開始成為計(jì)算機(jī)視覺的研究熱門。早期的計(jì)算主要focus在計(jì)算subpixel級(jí)的displacement，隨著視頻分辨率的增加，最近的很多算法開始考慮較大的displacement，通常需要先計(jì)算幀與幀之間pixel級(jí)別的correspondence，然后進(jìn)行warping后再使用傳統(tǒng)算法計(jì)算subpixel精度的optical flow結(jié)果。至于評(píng)測(cè)optical flow算法的accuracy，最經(jīng)典的一個(gè)benchmark是 HYPERLINK /flow/eval/

41、t _blank Middlebury，但其用于排名的dataset只有12張圖，比較容易o(hù)verfitting，最近兩年又出現(xiàn)兩個(gè)比較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(lǐng)(x,y,t)表示在t時(shí)

42、刻frame上像素(x,y)處的亮度(或顏色)，那么optical flow的目的就是求出在t+1時(shí)刻的frame上，該像素相對(duì)于原來(x,y)的位移量(u,v)，用方程表示即：其中u和v是未知量。這就是optical flow中著名的Brightness Constancy Model。不過，數(shù)字圖像畢竟是離散化pixel by pixel的，如果只給出兩幀圖像，如何計(jì)算出每個(gè)pixel的subpixel級(jí)的displacement(位移)呢？如果從correspondence的角度去考慮，在frame1中的某個(gè)pixel，只能找到其在frame2中對(duì)應(yīng)的pixel整數(shù)位置，這樣只能得到pi

43、xel級(jí)的displacement，而無法精確到subpixel精度。在經(jīng)典的optical flow算法中，一般利用 HYPERLINK http:/en.wikip/wiki/Taylor_series t _blank 一階泰勒展開作為工具來建立圖像gradient和displacement之間的關(guān)系，這一步驟通常被稱為Linearization。具體原理如下( HYPERLINK http:/www.cs.toron/fleet/research/Papers/flowChapter05.pdf t _blank 這里有個(gè)不錯(cuò)的tutorial介紹的也很詳細(xì)，by David Flee

44、t and Yair Weiss)：假設(shè)圖像的intensity是連續(xù)的，如下圖所示(1D case)，黑色的曲線表示frame1中的圖像，藍(lán)色的曲線表示frame2中的圖像，待求的displacement是深藍(lán)色的箭頭dx/dt。對(duì)曲線進(jìn)行一階泰勒展開，其實(shí)就是假設(shè)曲線的局部是線性的，這樣可以考察如圖的紅綠藍(lán)組成的三角形。注意，dI/dx并非是紅色線段的長度，而是其斜率。這樣可以得到圖中所示的關(guān)系，注意負(fù)號(hào)是因?yàn)樾甭势鋵?shí)表示的是鈍角的tan。這樣一來就建立了圖像的derivative和displacement之間的關(guān)系，注意dI/dx是圖像在spatial上的derivative，dI/dt

45、是圖像在temporal上的derivative。將上面的這個(gè)方程用在2D的圖像上，對(duì)于每個(gè)pixel，可以寫出以下方程：其中，I_x和I_y是圖像沿spatial的x和y兩個(gè)方向的derivative(即圖像gradient的兩個(gè)分量)，I_t是圖像沿temporal的derivative(可以用兩幀圖像的difference來近似)，u和v是該pixel沿x和y方向的位移，也就是待求的optical flow未知量。這其實(shí)就是對(duì)上面的Brightness Constancy Model的Lineariazation的結(jié)果，也就是optical flow中著名的Gradient Constr

46、aint Equation。需要注意的是，上面這個(gè)模型是建立在兩個(gè)假設(shè)基礎(chǔ)上：第一，圖像變化是連續(xù)的；第二，位移不是很大。如果這兩點(diǎn)假設(shè)不成立，那么泰勒展開的近似是很差的。直覺想象一下，如果圖像不是連續(xù)的，而且displacement很大，無論如何是無法將displacement和圖像gradient聯(lián)系起來的。不過在實(shí)際中，上述兩個(gè)假設(shè)可以很容易使其成立。關(guān)于第一點(diǎn)，一般可以預(yù)先對(duì)圖像進(jìn)行Gaussian Smoothing，使其變化較為平緩；關(guān)于第二點(diǎn)，一般是對(duì)圖像降分辨率建立金字塔，通過Coarse-To-Fine的方式一步一步去求解?；谏厦娴姆匠?，最經(jīng)典的兩個(gè)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，分別從不同的角度增加了求解該方程的穩(wěn)定性。Lucas-Kanade方法是將每個(gè)pixel周圍的一些pixels考慮進(jìn)來，但每個(gè)pixel的未知量是單獨(dú)求解的，所以是一種local方法；而Horn-Schunck方法是將上

48、面的方程納入到一個(gè)regularization的framework中，加入optical flow是locally smooth的prior，所有的pixel的未知量之間相互依賴，需要用global optimization的方法求解。目前state-of-the-art的方法，一般都是基于Horn-Schunck的framework做的，這里要介紹的經(jīng)典optical flow算法也是基于這個(gè)framework經(jīng)過幾次改良得到的。石器時(shí)代：令小寫的u和v分別表示每個(gè)pixel處沿x和y方向的displacement，大寫的U和V分別表示由所有pixel的u和v組成的map，那么Horn-Sc

49、hunck的目標(biāo)函數(shù)可以寫作如下形式：可以看出，第一項(xiàng)data term其實(shí)就是Brightness Constancy Model的Least Square形式，第二項(xiàng)regularization term目的是令結(jié)果的U和V較為smooth。對(duì)該目標(biāo)函數(shù)進(jìn)行minimization即可求出U和V。由于該目標(biāo)函數(shù)是quadratic，根據(jù)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)可以將其轉(zhuǎn)化為偏微分方程形式，再進(jìn)行離散化，最終可以歸結(jié)為求解一個(gè)大型線性方程組，利用Conjugate Gradient或者SOR可以很容易求解，參見 HYPERLINK /mulinb/article/details/9079645 t _blank 上一篇文章。青銅時(shí)代：根據(jù)robust statistics理論，quadratic的目標(biāo)函數(shù)對(duì)outlier太敏感。而其實(shí)在locally smooth a

51、ssumption下，最理想的情況是一個(gè)場(chǎng)景中只有一種motion。如果有多種motion，那么就相互構(gòu)成outlier，會(huì)嚴(yán)重影響結(jié)果，這顯然是quadratic目標(biāo)函數(shù)的軟肋。而這種情況恰恰是現(xiàn)實(shí)中最常發(fā)生的。因此，Michael J. Black和P. Anandan HYPERLINK /black/Papers/cviu.63.1.1996.pdf t _blank 3提出了將上述目標(biāo)函數(shù)中的L2 norm換成更為robust的函數(shù)(比如L1 norm或者truncated L1 norm)，形成了目前較為常用的形式：目前最常用的robust函數(shù)是

52、Charbonnier函數(shù)psi(x2)=sqrt(x2+1e-6)，即L1 norm (增加了一個(gè)很小的數(shù)字1e-6為了使其convex，容易求解optimization)。這樣一來，data term是L1 norm，regularization term使用了L1 norm后其實(shí)就成了Total Variation，因此這個(gè)目標(biāo)函數(shù)又被稱為TV-L1formulation。另外，目前流行的coarse-to-fine、warping的framework也是在這篇paper里基本定形的。白銀時(shí)代：為了避免光照對(duì)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個(gè)color channel之外多加兩個(gè)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的區(qū)別)。另外值得一提的是，在 HYPERLINK /flow/eval/results/results-e1.php t _blank Middlebury上有個(gè)叫improved TV-L1 HYPERLINK http:

55、/vision.in.tum.de/_media/spezial/bib/dagstuhlopticalflowchapter.pdf t _blank 6的算法，速度貌似很快，效果也不錯(cuò)。其實(shí)之前的很多算法都是基于TV-L1 formulation的，不過這篇paper 6 主要是介紹一種快速算法的。其實(shí)，該文的主要contribution在于：第一，該文提出用texture decomposition的方式先提取image的texture，然后用texture作為data term，旨在避免光照等的影響，跟前面的加入gradient data term思路類似。第二，該文提出對(duì)每一個(gè)ite

56、ration求解出的flow進(jìn)行median filter去掉outlier，后來這個(gè)小trick被證實(shí)是很有效的一步 7。另外，該文 HYPERLINK http:/vision.in.tum.de/_media/spezial/bib/dagstuhlopticalflowchapter.pdf t _blank 6中對(duì)implementation的描述也比較細(xì)致，如果要實(shí)現(xiàn)optical flow算法，這篇paper很值得一看(可以直接忽略其之前的版本5)。黃金時(shí)代：對(duì)經(jīng)典算法中使用的各種trick進(jìn)行總結(jié)的集大成者是Deqing Sun等人的 HYPERLINK http:/cs.br

57、/dqsun/pubs/cvpr_2010_flow.pdf t _blank CVPR 2010 paper 7及其擴(kuò)展 HYPERLINK /dqsun/pubs/Sun2013QAP.pdf t _blank IJCV 2013 paper 8。該猛人將之前paper中五花八門的trick統(tǒng)統(tǒng)試了一遍，總結(jié)出哪些是精華，哪些是糟粕。最難能可貴的是，他將所有的 HYPERLINK /dqsun/code/ijcv_flow_code.zip t _blank matlab代碼公布于眾，使得后來者省去了不少

58、揣測(cè)如何做implementation的時(shí)間，強(qiáng)贊一個(gè)。美中不足的是，這些實(shí)驗(yàn)是在Middlebury的training data上完成的，但是Middlebury的dataset有點(diǎn)小，只有幾張圖，難免讓人覺得有可能overfitting，調(diào)查的trick是否真的如paper中得出的結(jié)論那般，值得商榷(在其IJCV 2013 paper 8中也發(fā)現(xiàn)，算法在 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這里簡單地對(duì)求解上述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及他對(duì)Brox算法的重新推導(dǎo) HYPERLINK http:/people.csail./celiu/Thesis/CePhDThesis.pdf t _blank 9(Appendix A)。為了簡化推導(dǎo)過程，下面假設(shè)圖像I是由3個(gè)color channel加上2個(gè)gradient channel組成的5個(gè)channel的圖像(paper 4中推導(dǎo)時(shí)將gradient channel顯式的表示了出來，看起來過于復(fù)雜)。由上面的TV-L1 formulation，經(jīng)過Linearization