Incremental projection approach of regularization for inverse problems. (English) Zbl 1358.49023
Summary: This paper presents an alternative approach to the regularized least squares solution of ill-posed inverse problems. Instead of solving a minimization problem with an objective function composed of a data term and a regularization term, the regularization information is used to define a projection onto a convex subspace of regularized candidate solutions. The objective function is modified to include the projection of each iterate in the place of the regularization. Numerical experiments based on the problem of motion estimation for geophysical fluid images, show the improvement of the proposed method compared with regularization methods. For the presented test case, the incremental projection method uses 7 times less computation time than the regularization method, to reach the same error target. Moreover, at convergence, the incremental projection is two order of magnitude more accurate than the regularization method.
MSC:
| 49K40 | Sensitivity, stability, well-posedness |
| 49M05 | Numerical methods based on necessary conditions |
| 68U10 | Computing methodologies for image processing |
Software:
LIBOPTReferences:
| [1] | Anandan, P.: A computational framework and an algorithm for the measurement of visual motion. Int. J. Comput. Vis. 2, 283-310 (1989). doi:10.1007/BF00158167 · doi:10.1007/BF00158167 |
| [2] | Barron, J.L., Fleet, D.J., Beauchemin, S.S.: Performance of optical flow techniques. Int. J. Comput. Vis. 12, 43-77 (1994) · doi:10.1007/BF01420984 |
| [3] | Battiti, R., Amaldi, E., Koch, C.: Computing optical flow across multiple scales: an adaptive coarse-to-fine strategy. Int. J. Comput. Vis. 6, 133-145 (1991). doi:10.1007/BF00128153 · doi:10.1007/BF00128153 |
| [4] | Beck, Amir, Teboulle, Marc: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [5] | Bertero, M., Pogcio, T.A., Torre, V.: Ill-posed problems in early vision. Proc. IEEE 76, 869-889 (1988) · doi:10.1109/5.5962 |
| [6] | Black, M.J., Anandan, P.: The robust estimation of multiple motions: parametric and piecewise-smooth flow fields. Comput. Vis. Image Underst. 63, 75-104 (1996) · doi:10.1006/cviu.1996.0006 |
| [7] | Bonesky, T.: Morozov’s discrepancy principle and tikhonov-type functionals. Inverse Probl. 25, 015015 (2009) · Zbl 1162.65028 · doi:10.1088/0266-5611/25/1/015015 |
| [8] | Bruhn, A., Weickert, J.: A multigrid platform for real-time motion computation with discontinuity-preserving variational methods. Int. J. Comput. Vis. 70, 257-277 (2006) · Zbl 1477.68336 · doi:10.1007/s11263-006-6616-7 |
| [9] | Bruhn, A., Weickert, J., Schnörr, C.: Lucas/Kanade meets Horn/Schunck: combining local and global optic flow methods. Int. J. Comput. Vis. 61, 211-231 (2005) · Zbl 1477.68337 · doi:10.1023/B:VISI.0000045324.43199.43 |
| [10] | Chambolle, A., De Vore, R.A., Lee, N.Y., Lucier, B.J.: Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage. IEEE Trans. Image Process. 7, 319-335 (1998) · Zbl 0993.94507 · doi:10.1109/83.661182 |
| [11] | Combettes, P., Pesquet, J.: Proximal thresholding algorithm for minimization over orthonormal bases. SIAM J. Optim. 18, 1351-1376 (2008) · Zbl 1167.90011 · doi:10.1137/060669498 |
| [12] | Daubechies, I., Defrise, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413-1457 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042 |
| [13] | Eggermont, P.P.B., LaRiccia, V.N., Nashed, M.Z.: On weakly bounded noise in ill-posed problems. Inverse Probl. 25, 115018 (2009) · Zbl 1191.65056 · doi:10.1088/0266-5611/25/11/115018 |
| [14] | Elad, M., Matalon, B., Zibulevsky, M.: Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization. Appl. Comput. Harmon. Anal. 23, 346-367 (2007) · Zbl 1133.65022 · doi:10.1016/j.acha.2007.02.002 |
| [15] | Enkelmann, W.: Investigations of multigrid algorithms for the estimation of optical flow fieldsin image sequences. Comput. Vis. Graph. Image Process. 43, 150-177 (1988) · doi:10.1016/0734-189X(88)90059-X |
| [16] | Figueiredo, M.A.T., Nowak, R.D.: An em algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12, 906-916 (2003) · Zbl 1279.94015 · doi:10.1109/TIP.2003.814255 |
| [17] | Fleet, D.J.: Measurement of Image Velocity. Kluwer Academic Publishers, Dordrecht (1992) · Zbl 0758.68059 · doi:10.1007/978-1-4615-3648-2 |
| [18] | Fleet, D.J., Jepson, A.D.: Computation of component image velocity from local phase information. Int. J. Comput. Vis. 5, 77-104 (1990) · doi:10.1007/BF00056772 |
| [19] | Fleet, D.J., Black, M.J., Yacoob, Y., Jepson, A.D.: Design and use of linear models for image motion analysis. Int. J. Comput. Vis. 36, 171-193 (2000) · doi:10.1023/A:1008156202475 |
| [20] | Flór, J.-B., Eames, I.: Dynamcis of monopolar vortices on a topographic beta-plane. J. Fluid Mech. 456, 353-376 (2002) · Zbl 0987.76510 · doi:10.1017/S0022112001007728 |
| [21] | Gilbert, J.C., Jonsson, X.: LIBOPT—an environment for testing solvers on heterogeneous collections of problems—version 1.0. Technical Report RT-0331, INRIA (2007) |
| [22] | Glazer, F., Reynolds, G., Anandan, P.: Scene matching by hierarchical correlation. In: Proceedings of CVPR, pp. 432-441 (1983) |
| [23] | Hadamard, J.: Sur les problèmes aux dérivés partielles et leur signification physique. Princet. Univ. Bull. 13, 49-52 (1902) |
| [24] | Horn, B.K.P., Schunck, B.G.: Determining optical flow. Artif. Intell. 59, 81-87 (1981) · Zbl 1507.68311 · doi:10.1016/0004-3702(93)90173-9 |
| [25] | Lepskiǐ, O.V.: A problem of adaptive estimation in gaussian white noise. Theory Probab. Appl. 35, 454-466 (1990) · Zbl 0745.62083 · doi:10.1137/1135065 |
| [26] | Louis, A.K.: Inverse und Schlecht Gestellte Probleme, Teubner Studienbücher Mathematik. B.G. Teubner, Stuttgart (1989) · Zbl 0667.65045 · doi:10.1007/978-3-322-84808-6 |
| [27] | Lucas, B.D., Kanade, T.: An iterative image registration technique with an application to stereo vision. In: Proceedings of the 7th International Joint Conference on Artificial Intelligence—Volume 2, IJCAI’81, pp. 674-679. Morgan Kaufmann Publishers Inc., San Francisco (1981) |
| [28] | Mathé, P.: The lepskii principle revisited. Inverse Probl. 22, L11 (2006) · Zbl 1095.65045 · doi:10.1088/0266-5611/22/3/L02 |
| [29] | Mathé, P., Tautenhahn, U.: Regularization under general noise assumptions. Inverse Probl. 27, 035016 (2011) · Zbl 1220.47016 · doi:10.1088/0266-5611/27/3/035016 |
| [30] | McDermott, J., Weiss, Y., Adelson, E.H.: Beyond junctions: nonlocal form constraints on motion interpretation. Perception 30, 905-23 (2001) · doi:10.1068/p3219 |
| [31] | Mémin, E., Pérez, P.: Hierarchical estimation and segmentation of dense motion fields. Int. J. Comput. Vis. 46, 129-155 (2002) · Zbl 1012.68724 · doi:10.1023/A:1013539930159 |
| [32] | Mitiche, A., Bouthemy, P.: Computation and analysis of image motion: a synopsis of current problems and methods. Int. J. Comput. Vis. 19, 29-55 (1996) · doi:10.1007/BF00131147 |
| [33] | Morozov, V.A., Nashed, Z.: Methods for Solving Incorrectly Posed Problems. Springer-Verlag, New York (1984) · Zbl 0549.65031 · doi:10.1007/978-1-4612-5280-1 |
| [34] | Nashed, MZ; Colton, DL (ed.); Gilbert, RP (ed.), Approximate regularized solutions to improperly posed linear integral and operator equations, No. 430, 289-332 (1974), Berlin · Zbl 0298.47006 · doi:10.1007/BFb0066275 |
| [35] | Natterer, F.: Regularisierung schlecht gestellter Probleme durch Projektionsverfahren. Numer. Math. 28, 329-341 (1977) · Zbl 0364.65042 · doi:10.1007/BF01389972 |
| [36] | Poggio, T., Koch, C.: Ill-Posed problems in early vision: from computational theory to analogue networks. Proc. R. Soc. Lond. B Biol. Sci. 226, 303-323 (1985) · Zbl 0587.65085 · doi:10.1098/rspb.1985.0097 |
| [37] | Ramlau, R.: Morozov’s discrepancy principle for tikhonov regularization of nonlinear operators. Numer. Funct. Anal. Optim. 23, 2002 (2001) · Zbl 1002.65064 |
| [38] | Schuster, T., Weickert, J.: On the application of projection methods for computing optical flow fields. Inverse Probl. Imaging 1, 673-690 (2007) · Zbl 1147.68817 · doi:10.3934/ipi.2007.1.673 |
| [39] | Schuster, T., Kaltenbacher, B., Hofmann, B., Kazimierski, K.S.: Tikhonov regularization of linear operators with power-type penalties. In: Regularization Methods in Banach Spaces. Radon Series on Computational and Applied Mathematics, pp. 108-142. Walter de Gruyter, Berlin (2012) · Zbl 1259.65087 |
| [40] | Simpson, I.J.A., Woolrich, M.W., Groves, A.R., Schnabel, J.A.: Longitudinal brain MRI analysis with uncertain registration. In: Proceedings of the 14th International Conference on Medical Image Computing and Computer-Assisted Intervention—Volume Part II, MICCAI’11, pp. 647-654. Springer-Verlag, Berlin (2011) |
| [41] | Tikhonov, A.N.: Regularization of incorrectly posed problems. Sov. Math. 4, 1624-1627 (1963) · Zbl 0183.11601 |
| [42] | Tikhonov, A.N., Arsenin, V.Y.: Solutions of Ill-Posed Problems. W.H. Winston, New York (1977) · Zbl 0354.65028 |
| [43] | Titaud, O., Vidard, A., Souopgui, I., Le Dimet, F.-X.: Assimilation of image sequences in numerical models. Tellus A 62, 30-47 (2010) · Zbl 1178.86014 · doi:10.1111/j.1600-0870.2009.00416.x |
| [44] | Vonesch, C., Unser, M.: A fast iterative thresholding algorithm for wavelet-regularized deconvolution. In: Proceedings of the SPIE Conference on Mathematical Imaging: Wavelet XII, vol. 6701, pp. 67010D-1-67010D-5, San Diego, August 26-29, 2007 · Zbl 0973.94003 |
| [45] | Wedel, A.; Pock, T.; Zach, C.; Bischof, H.; Cremers, D.; Cremers, D. (ed.); Rosenhahn, B. (ed.); Yuille, AL (ed.); Schmidt, FR (ed.), An improved algorithm for TV-L1 optical flow, 23-45 (2009), Berlin · doi:10.1007/978-3-642-03061-1_2 |
| [46] | Weickert, J., Bruhn, A., Brox, T., Papenberg, N.: Mathematical Models for Registration and Applications to Medical Imaging. Mathematics in Industry, p. 103. Springer, Berlin (2006) · Zbl 1231.68271 · doi:10.1007/978-3-540-34767-5_5 |
| [47] | Wright, Stephen J., Nowak, Robert D., Mário, A.T.: Figueiredo, Sparse reconstruction by separable approximation. Trans. Signal Process. 57, 2479-2493 (2009) · Zbl 1391.94442 · doi:10.1109/TSP.2009.2016892 |
| [48] | Xu, C., Prince, J.L.: Snakes, shapes, and gradient vector flow. TIP 7, 359-369 (1998) · Zbl 0973.94003 |
| [49] | Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for \[\ell_1\] ℓ1-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1, 143-168 (2008) · Zbl 1203.90153 · doi:10.1137/070703983 |
| [50] | Yuan, J., Schnörr, C., Mémin, E.: Discrete orthogonal decomposition and variational fluid flow estimation. J. Math. Imag. Vis. 28, 67-80 (2007) · Zbl 1478.65104 · doi:10.1007/s10851-007-0014-9 |
| [51] | Zach, C., Pock, T., Bischof, H.: A duality based approach for realtime tv-l1 optical flow. In: Proceedings of the 29th DAGM Conference on Pattern Recognition, pp. 214-223. Springer-Verlag, Berlin (2007) · Zbl 1391.94442 |
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.
