Can variational models for correspondence problems benefit from upwind discretisations? (English) Zbl 1255.68170
Summary: Optic flow and stereo reconstruction are important examples of correspondence problems in computer vision. Correspondence problems have been studied for almost 30 years, and energy-based methods such as variational approaches have become popular for solving this task. However, despite the long history of research in this field, only little attention has been paid to the numerical approximation of derivatives that naturally occur in variational approaches. In this paper we show that strategies from hyperbolic numerics can lead to a significant quality gain in computational results. Starting from a basic formulation of correspondence problems, we take on a novel perspective on the mathematical model. Switching the roles of known and unknown with respect to image data and displacement field, we use the arising hyperbolic colour equation as a basis for a refined numerical approach. For its discretisation, we propose to use one-sided differences in the correct direction identified via a smooth predictor solution. The one-sided differences that are first-order accurate are blended with higher-order central schemes. Thereby the blending mechanism interpolates between the following two situations: The one-sided method is employed at image edges which often coincide with edges in the displacement field. In smooth image parts the higher-order scheme is used. We apply our new scheme to several prototypes of variational models for optic flow and stereo reconstruction, where we achieve significant qualitative improvements compared to standard discretisations.
MSC:
| 68T45 | Machine vision and scene understanding |
Keywords:
finite difference methods; adaptive methods; hyperbolic colour equation; variational correspondence problems; variational optic flow; variational stereoReferences:
| [1] | Baker, S., Roth, S., Scharstein, D., Black, M.J., Lewis, J.P., Szeliski, R.: A database and evaluation methodology for optical flow. In: Proc. 2007 IEEE International Conference on Computer Vision. Rio de Janeiro, Brazil. IEEE Computer Society Press, Los Alamitos (2007) |
| [2] | Barron, J.L., Fleet, D.J., Beauchemin, S.S.: Performance of optical flow techniques. Int. J. Comput. Vis. 12(1), 43–77 (1994) · doi:10.1007/BF01420984 |
| [3] | Ben-Ari, R., Sochen, N.: Variational stereo vision with sharp discontinuities and occlusion handling. In: Proc. 2007 IEEE International Conference on Computer Vision. Rio de Janeiro, Brazil. IEEE Computer Society Press, Los Alamitos (2007) |
| [4] | Bertero, M., Poggio, T.A., Torre, V.: Ill-posed problems in early vision. Proc. IEEE 76(8), 869–889 (1988) · doi:10.1109/5.5962 |
| [5] | Bigün, J., Granlund, G.H., Wiklund, J.: Multidimensional orientation estimation with applications to texture analysis and optical flow. IEEE Trans. Pattern Anal. Mach. Intell. 13(8), 775–790 (1991) · doi:10.1109/34.85668 |
| [6] | Black, M.J., Anandan, P.: The robust estimation of multiple motions: parametric and piecewise smooth flow fields. Comput. Vis. Image Underst. 63(1), 75–104 (1996) · doi:10.1006/cviu.1996.0006 |
| [7] | Brox, T., Bruhn, A., Papenberg, N., Weickert, J.: High accuracy optical flow estimation based on a theory for warping. In: Pajdla, T., Matas, J. (eds.) Computer Vision–ECCV 2004, Part IV. Lecture Notes in Computer Science, vol. 3024, pp. 25–36. Springer, Berlin (2004) · Zbl 1098.68736 |
| [8] | Brown, M., Burschka, D., Hager, G.: Advances in computational stereo. IEEE Trans. Pattern Anal. Mach. Intell. 25(8), 993–1008 (2003) · doi:10.1109/TPAMI.2003.1217603 |
| [9] | Bruhn, A., Weickert, J., Kohlberger, T., Schnörr, C.: A multigrid platform for real-time motion computation with discontinuity-preserving variational methods. Int. J. Comput. Vis. 70(3), 257–277 (2006) · Zbl 1477.68336 · doi:10.1007/s11263-006-6616-7 |
| [10] | Courant, R., Friedrichs, K., Lewy, H.: Über die partiellen Differenzengleichungen der mathematischen Physik. Math. Ann. 100(1), 32–74 (1928) · JFM 54.0486.01 · doi:10.1007/BF01448839 |
| [11] | Elsgolc, L.: Calculus of Variations. Pergamon Press, Oxford (1962) · Zbl 0101.32001 |
| [12] | Evans, L.C.: Partial Differential Equations. Oxford University Press, Oxford (1998) · Zbl 0902.35002 |
| [13] | Fleet, D.J., Weiss, Y.: Optical flow estimation. In: Paragios, N., Chen, Y., Faugeras, O. (eds.) Handbook of Mathematical Models in Computer Vision, Chap. 15, pp. 239–258. Springer, Berlin (2006) |
| [14] | Godlewski, E., Raviart, P.-A.: Hyperbolic Systems of Conservation Laws. Mathématiques et Applications. Ellipses, Paris (1991) · Zbl 0768.35059 |
| [15] | Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2000) · Zbl 0956.68149 |
| [16] | Horn, B., Schunck, B.: Determining optical flow. Artif. Intell. 17, 185–203 (1981) · doi:10.1016/0004-3702(81)90024-2 |
| [17] | Klette, R., Schlüns, K., Koschan, A.: Computer Vision: Three-Dimensional Data from Images. Springer, Singapore (1998) · Zbl 0917.68219 |
| [18] | LeVeque, R.J.: Numerical Methods for Conservation Laws. Birkhäuser, Basel (1992) · Zbl 0847.65053 |
| [19] | LeVeque, R.J.: Finite Volume Methods for Hyperbolic Problems. Cambridge University Press, Cambridge (2002) · Zbl 1010.65040 |
| [20] | Lucas, B., Kanade, T.: An iterative image registration technique with an application to stereo vision. In: Proc. Seventh International Joint Conference on Artificial Intelligence. Vancouver, Canada, pp. 674–679 (1981) |
| [21] | Mansouri, A.R., Mitiche, A., Konrad, J.: Selective image diffusion: application to disparity estimation. In: Proc. 1998 IEEE International Conference on Image Processing, vol. 3. Chicago, IL, pp. 284–288 (1998) |
| [22] | Marquina, A., Osher, S.: Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal. SIAM J. Sci. Comput. 22(2), 387–405 (2000) · Zbl 0969.65081 · doi:10.1137/S1064827599351751 |
| [23] | Mémin, E., Pérez, P.: Hierarchical estimation and segmentation of dense motion fields. Int. J. Comput. Vis. 46(2), 129–155 (2002) · Zbl 1012.68724 · doi:10.1023/A:1013539930159 |
| [24] | Morton, K.W., Mayers, L.M.: Numerical Solution of Partial Differential Equations. Cambridge University Press, Cambridge (1994) · Zbl 0811.65063 |
| [25] | Nir, T., Bruckstein, A.M., Kimmel, R.: Over-parameterized variational optical flow. Int. J. Comput. Vis. 76(2), 205–216 (2008) · Zbl 1477.68402 · doi:10.1007/s11263-007-0051-2 |
| [26] | Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [27] | Scharstein, D., Szeliski, R.: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. Int. J. Comput. Vis. 47(1–3), 7–42 (2002) · Zbl 1012.68731 · doi:10.1023/A:1014573219977 |
| [28] | Slesareva, N., Bruhn, A., Weickert, J.: Optic flow goes stereo: A variational method for estimating discontinuity-preserving dense disparity maps. In: Kropatsch, W., Sablatnig, R., Hanbury, A. (eds.) Pattern Recognition. Lecture Notes in Computer Science, vol. 3663, pp. 33–40. Springer, Berlin (2005) |
| [29] | Toro, E.F.: Riemann Solvers and Numerical Methods for Fluid Dynamics, 2nd edn. Springer, Berlin (1999) · Zbl 0923.76004 |
| [30] | Trucco, E., Verri, A.: Introductory Techniques for 3-D Computer Vision. Prentice Hall, Englewood Cliffs (1998) |
| [31] | Wedel, A., Cremers, D., Pock, T., Bischof, H.: Structure- and motion-adaptive regularization for high accuracy optic flow. In: Proc. 2009 IEEE International Conference on Computer Vision. Kyoto, Japan. IEEE Computer Society Press, Los Alamitos (2009) |
| [32] | Werlberger, M., Pock, T., Bischof, H.: Motion estimation with non-local total variation regularization. In: Proc. 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco, CA, USA. IEEE Computer Society Press, Los Alamitos (2010) |
| [33] | Xu, L., Jia, J., Matsushita, Y.: Motion detail preserving optical flow estimation. In: Proc. 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco, CA, USA. IEEE Computer Society Press, Los Alamitos (2010) |
| [34] | Young, D.M.: Iterative Solution of Large Linear Systems. Dover, New York (2003) · Zbl 1049.65022 |
| [35] | Zimmer, H., Breuß, M., Weickert, J., Seidel, H.-P.: Hyperbolic numerics for variational approaches to correspondence problems. In: Tai, X.-C., et al. (eds.) Scale Space and Variational Methods in Computer Vision. Lecture Notes in Computer Science, vol. 5567, pp. 636–647. Springer, Berlin (2009) |
| [36] | Zimmer, H., Bruhn, A., Weickert, J., Valgaerts, L., Salgado, A., Rosenhahn, B., Seidel, H.-P.: Complementary optic flow. In: Cremers, D., Boykov, Y., Blake, A., Schmidt, F.R. (eds.) Energy Minimization Methods in Computer Vision and Pattern Recognition–EMMCVPR. Lecture Notes in Computer Science, vol. 5681, pp. 207–220. Springer, Berlin (2009) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
