Contributions to Horn-Schunck optical flow equations-part I: Stability and rate of convergence of classical algorithm

Abstract

Globally exponential stability (which implies convergence and uniqueness) of their classical iterative algorithm is established using methods of heat equations and energy integral after embedding the discrete iteration into a continuous flow. The stability condition depends explicitly on smoothness of the image sequence, size of image domain, value of the regularization parameter, and finally discretization step. Specifically, as the discretization step approaches to zero, stability holds unconditionally. The analysis also clarifies relations among the iterative algorithm, the original variation formulation and the PDE system. The proper regularity of solution and natural images is briefly surveyed and discussed. Experimental results validate the theoretical claims both on convergence and exponential stability.

Keywords

optical flow / Horn-Schunck equations / globally exponential stability / convergence / convergence rate / heat equations; energy integral and estimate / Gronwall inequality / natural images / regularity

References

[1] HornB K P, SchunckB G. Determining optical flow [J]. Artificial Intelligence, 1981, 17: 185-203

[2] WuL DComputer vision [M], 1993ShanghaiFudan University Press180-202

[3] DongG-h, AnX-j, HuD-wen. Horn-Schunck optical flow equations. Part II: Decoupling via linear transformations [C]. 2012 Sino-foreign-interchange Worshop on Information Science & Intelligent Data Engineering (IScIDE 2012). Nanjing, 2012

[4] DongG-h, AnX-j, HuD-wen. Horn-Schunck optical flow equations. Part III: Alternating iteration algorithms [J]. Przeglad Elektrotchniczny (PE), 2013, 89: 193-197

[5] VekuaI. New methods for solving elliptic equations [M]. HOU Zong-yi, 1963ShanghaiShanghai Science and Technology Press

[6] ChenY-z, WuL-chengElliptic partial differential equations and systems of order two [M], 1997BeijingChina Academic Press201-213

[7] YuD-h, TangH-zhongNumeric solutions to differential equations [M], 2003BeijingChina Academic Press106

[8] GuChao-hao, Li-Da-Qian, ChenShu-xing, ShenWei-xi, QinTie-hu, ShiJia-hong.Methods of mathematical physics [M], 1985ShanghaiFudan University Press118-140

[9] COURANT R, HILBERT D. Methods of mathematical physics, Vol. II [M]. XIONG Zhen-xiang, YANG Ying-chen. Beijing: China Academic Press, 1977: 212–223, 269–284. (in Chinese).

[10] MumfordD, ShahJ. Optimal approximation by piecewise smooth functions and variational problems [J]. Communications on Pure and Applied Mathematics, 1989, 42: 577-685

[11] MorelJ M, SoliminiS. Variational method in image segmentation [M]. Progress in Nonlinear Differential Equations and Their Applications, Boston: Birkhauser, 199535-43

[12] GuichardF, MorelJ M. Partial differential equations and image iterative filtering [M]. State of the Art in Numerical Analysis, 1997OxfordOxford University Press525-562

[13] ChanT, ShenJImage processing and analysis-variational, PDE, wavelet, and stochastic methods [M], 2005PhiladelphiaSIAM91-143

[14] GousseauY, MorelJ M. Are natural images of bounded variation?. [J]. SIAM Journal of Mathematical Analysis, 2001, 33(3): 634-648

[15] MeyerY. Oscillating patterns in image processing and nonlinear evolution equations [M]. University Lecture Series (Lewis Memorial Lectures), Vol. 22. American Mathematical Society, 20011-70

[16] ZhuS-c, WuY-n, MumfordD. Minimax entropy principle and its application to texture modeling [J]. Neural Computation, 1997, 9: 1627-1660

[17] BesagJ. Spatial interaction and the statistical analysis of lattice systems [J]. Journal of Royal Statistical Society B, 1974, 36(2): 192-236

[18] GemanS, GemanD. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1984, 6: 721-741

[19] WinkleG. Image analysis, random fields and dynamic Monte Carlo methods: A mathematical introduction [M]. Springer-Verlag, 19951-9

[20] DesolneuxA, MoisanL, MorelJ M. Edge detection by Helmholtz principle [J]. Journal of Mathematical Imaging and Vision, 2001, 14: 271-284

[21] HuangJStatistics of natural images and models [D], 2000Rhode IslandDivision of Applied Mathematics, Brown University

[22] LeeA, MumfordD, HuangJ. Occlusion models for natural images [J]. International Journal of Computer Vision, 2001, 41: 35-59

[23] GrenanderU, SrivastavaA. Probability models for clutter in natural images [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23: 424-429

[24] GidasB, MumfordD. Stochastic models for generic images [J]. Quaterly of Applied Mathematics, 2001, 59: 85-111

[25] PedersenK, LeeA. Toward a full probability model of edges in natural images [C]. Lecture Notes in Computer Science, Volume 2350, Springer-Verlag, 2002328

[26] SrivastavaA, LiuX W, GrenanderU. Universal analytical forms for modeling image probabilities [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24: 1200-1214

[27] LeeA, PedersenK, MumfordD. The nonlinear statistics of high-contrast patches in natural images [J]. International Journal of Computer Vision, 2003, 54: 83-103

[28] SrivastavaA, LeeA, SimoncelliE, ZhuS C. On advances in statistical modeling of natural images [J]. Journal of Mathematical Imaging and Vision, 2003, 18: 17-33

[29] MumfordDHaykinS, PrincipeJ C, SejnowskiT J, McWhirterJ. Empirical statistics and stochastic models for visual signals [C]. New Directions in Statistical Signal Processing: From Systems to Brain, 20051-34

[30] WuY N, LiJ, LiuZ, ZhuS C. Statistical principles in image modeling [J]. Technometrics, 2007, 49(3): 249-261

[31] MumfordD, DesolneuxAPattern theory: the stochastic analysis of real world signals [EB/OL], 2008

[32] TorreV, PoggioTOn edge detection [R]. MIT, A. I. Memo 768, 1984

[33] FieldD J. Relations between the statistics of natural images and the response properties of cortical cells [J]. Journal of the Optical Society of American, A, 1987, 4: 2379-2394

[34] FieldD J. Wavelets, vision and the statistics of natural scenes [J]. Philosophical Transactions on Royal Society of London A, 1999, 357: 2527-2542

[35] SimoncelliE. Modeling the joint statistics of images in the wavelet domain [C]. Proceedings of the 44th Annual Meeting of SPIE, 1999188-195

[36] SimoncelliE. Natural image statistics and neural representation [J]. Annual Review of Neuroscience, 2001, 24: 1193-1216

[37] SunD, RothS, BlackM JA quantitative analysis of current practices in optical flow estimation and the principles behind them [R], 2010

[38] MiticheA, MansouriA-R. On convergence of the Horn and Schunck optical-flow estimation method [J]. IEEE Trans Image Proc, 2004, 13(6): 848-852

[39] KAMEDAL Y, IMIYA A, OHNISHI N. A convergence proof for the Horn-Schunck optical-flow computation scheme using neighborhood decomposition [C]// BRIMKOV V E, BAMEYA R P, HAUPYMAN H A. IWCIA 2008. Berlin: Springer, 4958: 262–273.