A framework for moving least squares method with total variation minimizing regularization. (English) Zbl 1292.49033
Summary: In this paper, we propose a computational framework to incorporate regularization terms used in regularity based variational methods into least squares based methods. In the regularity based variational approach, the image is a result of the competition between the fidelity term and a regularity term, while in the least squares based approach the image is computed as a minimizer to a constrained least squares problem. The total variation minimizing denoising scheme is an exemplary scheme of the former approach with the total variation term as the regularity term, while the moving least squares method is an exemplary scheme of the latter approach. Both approaches have appeared in the literature of image processing independently. By putting schemes from both approaches into a single framework, the resulting scheme benefits from the advantageous properties of both parties. As an example, in this paper, we propose a new denoising scheme, where the total variation minimizing term is adopted by the moving least squares method. The proposed scheme is based on splitting methods, since they make it possible to express the minimization problem as a linear system. In this paper, we employ the split Bregman scheme for its simplicity. The resulting denoising scheme overcomes the drawbacks of both schemes, i.e., the staircase artifact in the total variation minimizing based denoising and the noisy artifact in the moving least squares based denoising method. The proposed computational framework can be utilized to put various combinations of both approaches with different properties together.
MSC:
| 49M25 | Discrete approximations in optimal control |
| 65K10 | Numerical optimization and variational techniques |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 68U10 | Computing methodologies for image processing |
Keywords:
image denoising; total variation; minimizers; moving least squares method; Bregman iterationReferences:
| [1] | Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing: Partial Differential Equations and the Calculus of Variations. Applied Mathematical Sciences, vol. 147. Springer, Berlin (2002) · Zbl 1109.35002 |
| [2] | Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542 |
| [3] | Beck, A., Teboulle, M.: Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. 18(11), 2419-2434 (2009) · Zbl 1371.94049 · doi:10.1109/TIP.2009.2028250 |
| [4] | Blomgren, P.; Chan, T.; Mulet, P.; Wong, C. K., Total variation image restoration: numerical methods and extensions, 384-387 (1997) |
| [5] | Bose, N.K., Ahuja, N.A.: Superresolution and noise filtering using moving least squares. IEEE Trans. Image Process. 15(8), 2239-2248 (2006) · doi:10.1109/TIP.2006.877406 |
| [6] | Bougleux, S., Elmoataz, A., Melkemi, M.: Local and nonlocal discrete regularization on weighted graphs for image and mesh processing. Int. J. Comput. Vis. 84(2), 220-236 (2009) · Zbl 1481.94008 · doi:10.1007/s11263-008-0159-z |
| [7] | Breitkopf, P., Naceur, H., Passineux, A., Villon, P.: Moving least squares response surface approximation: formulation and metal forming applications. Comput. Struct. 83(17-18), 1411-1428 (2005) · doi:10.1016/j.compstruc.2004.07.011 |
| [8] | Brox, T., Kleinschmidt, O., Cremers, D.: Efficient nonlocal means for denoising of textural patterns. IEEE Trans. Image Process. 17(7), 1083-1092 (2008) · doi:10.1109/TIP.2008.924281 |
| [9] | Bruhn, A.; Weickert, J., Towards ultimate motion estimation: combining highest accuracy with real-time performance, No. 1, 749-755 (2005) |
| [10] | 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 |
| [11] | Buades, A., Coll, B., Morel, J.M.: A review of image denoising algorithms, with a new one. Multiscale Model. Simul. 4(2), 490-530 (2005) · Zbl 1108.94004 · doi:10.1137/040616024 |
| [12] | Caselles, V., Chambolle, A., Novaga, M.: The discontinuity set of solutions of the TV denoising problem and some extensions. Multiscale Model. Simul. 6(3), 879-894 (2007) · Zbl 1145.49024 · doi:10.1137/070683003 |
| [13] | Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1-2), 89-97 (2004) · Zbl 1366.94048 |
| [14] | Chambolle, A., Lions, P.-L.: Image recovery via total variation minimization and related problems. Numer. Math. 76(2), 167-188 (1997) · Zbl 0874.68299 · doi:10.1007/s002110050258 |
| [15] | Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120-145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1 |
| [16] | Chan, T., Marquina, A., Mulet, P.: High-order total variation based image restoration. SIAM J. Sci. Comput. 22(2), 503-516 (2000) · Zbl 0968.68175 · doi:10.1137/S1064827598344169 |
| [17] | Chan, T., Esedoglu, S., Park, F., Yip, A.: Recent Developments in Total Variation Image Restoration. Mathematical Models in Computer Vision. Springer, Berlin (2005) |
| [18] | Chan, T., Esedoglu, S., Park, F.E.: Image decomposition combining staircase reduction and texture extraction. J. Vis. Commun. Image Represent. 18(6), 464-486 (2007) · doi:10.1016/j.jvcir.2006.12.004 |
| [19] | Chan, T.; Esedoglu, S.; Park, F., A fourth order dual method for staircase reduction in texture extraction and image restoration problems, 4137-4140 (2010) |
| [20] | Chu, C.K., Glad, I.K., Godtliebsen, F., Marron, J.S.: Edge-preserving smoothers for image processing. J. Am. Stat. Assoc. 93(442), 526-556 (1998) · Zbl 0954.62115 · doi:10.1080/01621459.1998.10473702 |
| [21] | Dabov, K., Foi, A., Katkovnik, V., Egiazarian, K.: Image denoising by sparse 3D transform-domain collaborative filtering. IEEE Trans. Image Process. 16(8), 2080-2095 (2007) · doi:10.1109/TIP.2007.901238 |
| [22] | Deledalle, C.A., Duval, V., Salmon, J.: Non-local methods with shape-adaptive patches (NLM-SAP). IMA J. Numer. Anal. 43(2), 103-120 (2012) · Zbl 1255.68227 |
| [23] | Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program., Ser. A 55(3), 293-318 (1992) · Zbl 0765.90073 · doi:10.1007/BF01581204 |
| [24] | Elad, M.: On the origin of the bilateral filter and ways to improve it. IEEE Trans. Image Process. 11(10), 1141-1151 (2002) · doi:10.1109/TIP.2002.801126 |
| [25] | Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split-Bregman. UCLA CAM-Reports 09-31 (2009) |
| [26] | Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015-1046 (2010) · Zbl 1206.90117 · doi:10.1137/09076934X |
| [27] | Fenn, M.; Steidl, G., Robust local approximation of scattered data, No. 31, 317-334 (2006) · doi:10.1007/1-4020-3858-8_17 |
| [28] | Gilboa, G., Osher, S.: Nonlocal linear image regularization and supervised segmentation. Multiscale Model. Simul. 6(2), 595-630 (2007) · Zbl 1140.68517 · doi:10.1137/060669358 |
| [29] | Gilboa, G., Osher, S.: Nonlocal operators with applications to image processing. Multiscale Model. Simul. 7(3), 1005-1028 (2008) · Zbl 1181.35006 · doi:10.1137/070698592 |
| [30] | Goldstein, T., Osher, S.: The split Bregman method for L1 regularized problems. SIAM J. Imaging Sci. 2(2), 323-343 (2009) · Zbl 1177.65088 · doi:10.1137/080725891 |
| [31] | Gwosdek, P., Bruhn, A., Weickert, J.: Variational optic flow on the Sony PlayStation 3—accurate dense flow fields for real-time applications. J. Real-Time Image Process. 5(3), 163-177 (2010) · doi:10.1007/s11554-009-0132-2 |
| [32] | Kamilov, U.; Bostan, E.; Unser, M., Generalized total variation denoising via Augmented Lagrangian cycle spinning with Haar wavelets, 909-912 (2012) |
| [33] | Kervrann, C., Boulanger, J.: Local adaptivity to variable smoothness for exemplar-based image regularization and representation. Int. J. Comput. Vis. 79(1), 45-69 (2008) · doi:10.1007/s11263-007-0096-2 |
| [34] | Lancaster, P., Salkauskas, K.: Surfaces generated by moving least squares methods. Math. Comput. 37(155), 141-158 (1981) · Zbl 0469.41005 · doi:10.1090/S0025-5718-1981-0616367-1 |
| [35] | Levin, D.: The approximation power of moving least-squares. Math. Comput. 67(224), 1517-1531 (1998) · Zbl 0911.41016 · doi:10.1090/S0025-5718-98-00974-0 |
| [36] | Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964-979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071 |
| [37] | Meyer, Y., Oscillating patterns in image processing and nonlinear evolution equations, No. 22 (2001), Providence · Zbl 0987.35003 |
| [38] | Mirzaei, D., Schaback, R., Dehghan, M.: On generalized moving least squares and diffuse derivatives. IMA J. Numer. Anal. 32(3), 983-1000 (2012) · Zbl 1252.65037 · doi:10.1093/imanum/drr030 |
| [39] | Mrazek, P.; Meickert, J.; Bruhn, A., On robust estimation and smoothing with spatial and tonal kernels, No. 31, 335-352 (2006) · doi:10.1007/1-4020-3858-8_18 |
| [40] | Nayroles, B., Touzot, G., Villon, P.: Generalizing the finite element method: diffuse approximation and diffuse elements. Comput. Mech. 10(5), 307-318 (1992) · Zbl 0764.65068 · doi:10.1007/BF00364252 |
| [41] | Nikolova, M.: Local strong homogeneity of a regularized estimator. SIAM J. Appl. Math. 61(2), 633-658 (2000) · Zbl 0991.94015 · doi:10.1137/S0036139997327794 |
| [42] | Nikolova, M.: Weakly constrained minimization: application to the estimation of images and signals involving constant regions. J. Math. Imaging Vis. 21(2), 155-175 (2004) · Zbl 1435.94081 · doi:10.1023/B:JMIV.0000035180.40477.bd |
| [43] | Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. Multiscale Model. Simul. 4(2), 460-489 (2005) · Zbl 1090.94003 · doi:10.1137/040605412 |
| [44] | Pizarro, L., Mrázek, P., Didas, S., Grewenig, S., Weickert, J.: Generalised nonlocal image smoothing. Int. J. Comput. Vis. 90(1), 62-87 (2010) · Zbl 1477.94020 · doi:10.1007/s11263-010-0337-7 |
| [45] | Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60(1-4), 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [46] | Sapiro, G.: Geometric Partial Differential Equations and Image Processing. Cambridge University Press, Cambridge (2001) · Zbl 0968.35001 · doi:10.1017/CBO9780511626319 |
| [47] | Schumaker, L.L.: Spline Functions: Basic Theory. Wiley, New York (1981) · Zbl 0449.41004 |
| [48] | Setzer, S., Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage, No. 5567, 464-476 (2009), Berlin · doi:10.1007/978-3-642-02256-2_39 |
| [49] | Setzer, S.: Operator splitting, Bregman methods and frame shrinkage in image processing. Int. J. Comput. Vis. 92(3), 265-280 (2011) · Zbl 1235.68314 · doi:10.1007/s11263-010-0357-3 |
| [50] | Setzer, S.: Infimal convolution regularizations with discrete L1-type functionals. Commun. Math. Sci. 9(3), 797-827 (2011) · Zbl 1269.49063 · doi:10.4310/CMS.2011.v9.n3.a7 |
| [51] | Stefan, W., Renaut, R.A., Gelb, A.: Improved total variation-type regularization using higher order edge detectors. SIAM J. Imaging Sci. 3(2), 232-251 (2010) · Zbl 1195.41007 · doi:10.1137/080730251 |
| [52] | Takeda, H., Farsiu, S., Milanfar, P.: Kernel regression for image processing and reconstruction. IEEE Trans. Image Process. 16(2), 349-366 (2007) · doi:10.1109/TIP.2006.888330 |
| [53] | Tomasi, C.; Manduchi, R., Bilateral filtering for gray and color images, 839-846 (1998) |
| [54] | Unser, M., Blu, T.: Cardinal exponential splines: Part I: theory and filtering algorithms. IEEE Trans. Signal Process. 53(4), 1425-1438 (2005) · Zbl 1370.94262 · doi:10.1109/TSP.2005.843700 |
| [55] | Vogel, C.R., Oman, M.E.: Iterative methods for total variation denoising. SIAM J. Sci. Comput. 17(1), 227-238 (1996) · Zbl 0847.65083 · doi:10.1137/0917016 |
| [56] | Wang, C., Liu, Z.: Total variation for image restoration with smooth area protection. J. Signal Process. Syst. 61(3), 271-277 (2010) · doi:10.1007/s11265-010-0451-3 |
| [57] | Wang, Y., Yin, W., Zhang, Y.: A fast algorithm for image deblurring with total variation regularization. CAAM Technical Report 07-10 (2007) |
| [58] | Winker, G., Aurich, V., Hahn, K., Martin, A., Rodenacker, K.: Noise reduction in images: some recent edge-preserving methods. Pattern Recognit. Image Anal. 9(4), 749-766 (1999) |
| [59] | Wu, C., Tai, X.-C.: Augmented Lagrangian method, dual methods, and split Bregman iterations for ROF, vectorial TV and higher order models. SIAM J. Imaging Sci. 3(3), 300-339 (2010) · Zbl 1206.90245 · doi:10.1137/090767558 |
| [60] | Yoon, J., Lee, Y.: Nonlinear image upsampling method based on radial basis function interpolation. IEEE Trans. Image Process. 19(10), 2682-2692 (2010) · Zbl 1371.94221 · doi:10.1109/TIP.2010.2050108 |
| [61] | Zhang, X., Burger, M., Bresson, X., Osher, S.: Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM J. Imaging Sci. 3(3), 253-276 (2010) · Zbl 1191.94030 · doi:10.1137/090746379 |
| [62] | Zhang, X., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46(1), 20-46 (2011) · Zbl 1227.65052 · doi:10.1007/s10915-010-9408-8 |
| [63] | Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Reports 08-34 (2008) · Zbl 1370.94262 |
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.
