Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes

Rustum Choksi; Yves van Gennip; Adam Oberman

doi:10.3934/ipi.2011.5.591

Article Contents

2011, Volume 5, Issue 3: 591-617. Doi: 10.3934/ipi.2011.5.591

This issue Previous Article Alpha divergences based mass transport models for image matching problems Next Article Errors of regularisation under range inclusions using variable Hilbert scales

Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes

1.
Department of Mathematics and Statistics, McGill University, Burnside Hall, Room 1005, 805 Sherbrooke Street West, Montreal, Quebec, H3A 2K6
2.
Department of Mathematics, University of California Los Angeles, Math Sciences Building 6363, 520 Portola Plaza, Los Angeles, California, 90095
3.
Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, 8888 University Drive, V5A 1S6

Received: July 2010

Revised: March 2011

Published: August 2011

Abstract Related Papers Cited by

Abstract

We consider variations of the Rudin-Osher-Fatemi functional which are particularly well-suited to denoising and deblurring of 2D bar codes. These functionals consist of an anisotropic total variation favoring rectangles and a fidelity term which measure the $L^1$ distance to the signal, both with and without the presence of a deconvolution operator. Based upon the existence of a certain associated vector field, we find necessary and sufficient conditions for a function to be a minimizer. We apply these results to 2D bar codes to find explicit regimes -- in terms of the fidelity parameter and smallest length scale of the bar codes -- for which the perfect bar code is attained via minimization of the functionals. Via a discretization reformulated as a linear program, we perform numerical experiments for all functionals demonstrating their denoising and deblurring capabilities.

Keywords:

Mathematics Subject Classification: 49N45, 94A08.

Citation:

Related Papers

Cited by

References

[1]	R. A. Adams, "Sobolev Spaces," Pure and Applied Mathematics, 65, Academic Press, New York-London, 1975.
[2]	L. Ambrosio, N. Fusco and D. Pallara, "Functions of Bounded Variation and Free Discontinuity Problems," Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 2000.
[3]	B. Berkels, M. Burger, M. Droske, O. Nemitz and M. Rumpf, Cartoon extraction based on anisotropic image classification, in "Vision, Modeling, and Visualization," proceedings, November 22-24, 2006, Akademische Verlagsgesellschaft Aka GmbH, Berlin, (2006), 293-300.
[4]	E. Casas, K. Kunisch and C. Pola, Regularization by functions of bounded variation and applications to image enhancement, Appl. Math. Optim., 40 (1999), 229-257.doi: 10.1007/s002459900124.
[5]	T. F. Chan and S. Esedoḡlu, Aspects of total variation regularized $L^1$ function approximation, SIAM J. Appl. Math., 65 (2005), 1817-1837 (electronic).doi: 10.1137/040604297.
[6]	T. F. Chan, S. Esedoḡlu and M. Nikolova, Algorithms for finding global minimizers of image segmentation and denoising models, SIAM J. Appl. Math., 66 (2006), 1632-1648 (electronic).doi: 10.1137/040615286.
[7]	T. F. Chan and J. Shen, "Image Processing and Analysis," Variational, PDE, Wavelet, and Stochastic Methods, SIAM (Society for Industrial and Applied Mathematics), Philadelphia, PA, 2005.
[8]	R. Choksi and Y. van Gennip, Deblurring of one dimensional bar codes via total variation energy minimisation, SIAM J. Imaging Sci., 3 (2010), 735-764.doi: 10.1137/090773829.
[9]	C.-H. Chu, D.-N. Yang and M.-S. Chen, Image stablization for 2d barcode in handheld devices, in "Proceedings of the 15th International Conference on Multimedia" (eds. R. Lienhart, A. R. Prasad, A. Hanjalic, S. Choi, B. P. Bailey and N. Sebe), Augsburg, Germany, September 24-29, 2007, ACM, (2007), 697-706.
[10]	I. Ekeland and R. Temam, "Convex Analysis and Variational Problems," Translated from the French, Studies in Mathematics and its Applications, 1, North-Holland Publishing Co., Amsterdam-Oxford, American Elsevier Publishing Co., Inc., New York, 1976.
[11]	S. Esedoḡlu, Blind deconvolution of bar code signals, Inverse Problems, 20 (2004), 121-135.doi: 10.1088/0266-5611/20/1/007.
[12]	S. Esedoḡlu and S. J. Osher, Decomposition of images by the anisotropic Rudin-Osher-Fatemi model, Comm. Pure Appl. Math., 57 (2004), 1609-1626.doi: 10.1002/cpa.20045.
[13]	L. C. Evans and R. F. Gariepy, "Measure Theory and Fine Properties of Functions," Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992.
[14]	G. Gilboa and S. Osher, Nonlocal linear image regularization and supervised segmentation, Multiscale Model. Simul., 6 (2007), 595-630.doi: 10.1137/060669358.
[15]	G. Gilboa and S. Osher, Nonlocal operators with applications to image processing, Multiscale Model. Simul., 7 (2008), 1005-1028.doi: 10.1137/070698592.
[16]	E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Monographs in Mathematics, 80, Birkhäuser Verlag, Basel, 1984.
[17]	M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs, in "Recent Advances in Learning and Control, Lecture Notes in Control and Information Sciences" (eds. V. Blondel, S. Boyd and H. Kimura), 371, Springer, London, (2008), 95-110. Available from: http://stanford.edu/ boyd/graph_dcp.html.
[18]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 1.21, May 2010. Available from: http://cvxr.com/cvx.
[19]	Y. Meyer, Oscillating patterns in image processing and nonlinear evolution equations, in "The Fifteenth Dean Jacqueline B. Lewis Memorial Lectures," University Lecture Series, 22, American Mathematical Society, Providence, RI, 2001.
[20]	J. Moll, The anisotropic total variation flow, Math. Ann., 332 (2005), 177-218.doi: 10.1007/s00208-004-0624-0.
[21]	A. Mosek, Mosek: A Full Featured Software Package Intended for Solution of Large Scale Optimization Problems, 2008. Available from: http://www.mosek.com/.
[22]	R. Palmer, "The Bar Code Book: A Comprehensive Guide to Reading, Printing, Specifying, Evaluating, and Using Bar Code and Other Machine-Readable Symbols," fifth edition, Trafford Publishing, 2007.
[23]	W. Ring, Structural properties of solutions to total variation regularization problems, M2AN Math. Model. Numer. Anal., 34 (2000), 799-810.doi: 10.1051/m2an:2000104.
[24]	L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[25]	J. E. Taylor, Crystalline variational problems, Bull. Amer. Math. Soc., 84 (1978), 568-588.doi: 10.1090/S0002-9904-1978-14499-1.
[26]	W. Xu and S. McCloskey, 2D barcode localization and motion deblurring using a flutter shutter camera, in "2011 IEEE Workshop on Applications of Computer Vision (WACV)," (2011), 159-165.doi: 10.1109/WACV.2011.5711498.