August  2011, 5(3): 591-617. doi: 10.3934/ipi.2011.5.591

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, Canada

2. 

Department of Mathematics, University of California Los Angeles, Math Sciences Building 6363, 520 Portola Plaza, Los Angeles, California, 90095, United States

3. 

Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, 8888 University Drive, V5A 1S6, Canada

Received  July 2010 Revised  March 2011 Published  August 2011

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.
Citation: Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591
References:
[1]

R. A. Adams, "Sobolev Spaces," Pure and Applied Mathematics, 65,, Academic Press, (1975).   Google Scholar

[2]

L. Ambrosio, N. Fusco and D. Pallara, "Functions of Bounded Variation and Free Discontinuity Problems,", Oxford Mathematical Monographs, (2000).   Google Scholar

[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, (2006), 293.   Google Scholar

[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.  doi: 10.1007/s002459900124.  Google Scholar

[5]

T. F. Chan and S. Esedoḡlu, Aspects of total variation regularized $L^1$ function approximation,, SIAM J. Appl. Math., 65 (2005), 1817.  doi: 10.1137/040604297.  Google Scholar

[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.  doi: 10.1137/040615286.  Google Scholar

[7]

T. F. Chan and J. Shen, "Image Processing and Analysis,", Variational, (2005).   Google Scholar

[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.  doi: 10.1137/090773829.  Google Scholar

[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.   Google Scholar

[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., (1976).   Google Scholar

[11]

S. Esedoḡlu, Blind deconvolution of bar code signals,, Inverse Problems, 20 (2004), 121.  doi: 10.1088/0266-5611/20/1/007.  Google Scholar

[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.  doi: 10.1002/cpa.20045.  Google Scholar

[13]

L. C. Evans and R. F. Gariepy, "Measure Theory and Fine Properties of Functions," Studies in Advanced Mathematics,, CRC Press, (1992).   Google Scholar

[14]

G. Gilboa and S. Osher, Nonlocal linear image regularization and supervised segmentation,, Multiscale Model. Simul., 6 (2007), 595.  doi: 10.1137/060669358.  Google Scholar

[15]

G. Gilboa and S. Osher, Nonlocal operators with applications to image processing,, Multiscale Model. Simul., 7 (2008), 1005.  doi: 10.1137/070698592.  Google Scholar

[16]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Monographs in Mathematics, 80,, Birkhäuser Verlag, (1984).   Google Scholar

[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, (2008), 95.   Google Scholar

[18]

M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 1.21, May 2010., Available from: , ().   Google Scholar

[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, (2001).   Google Scholar

[20]

J. Moll, The anisotropic total variation flow,, Math. Ann., 332 (2005), 177.  doi: 10.1007/s00208-004-0624-0.  Google Scholar

[21]

A. Mosek, Mosek: A Full Featured Software Package Intended for Solution of Large Scale Optimization Problems, 2008., Available from: , ().   Google Scholar

[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).   Google Scholar

[23]

W. Ring, Structural properties of solutions to total variation regularization problems,, M2AN Math. Model. Numer. Anal., 34 (2000), 799.  doi: 10.1051/m2an:2000104.  Google Scholar

[24]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[25]

J. E. Taylor, Crystalline variational problems,, Bull. Amer. Math. Soc., 84 (1978), 568.  doi: 10.1090/S0002-9904-1978-14499-1.  Google Scholar

[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), (2011), 159.  doi: 10.1109/WACV.2011.5711498.  Google Scholar

show all references

References:
[1]

R. A. Adams, "Sobolev Spaces," Pure and Applied Mathematics, 65,, Academic Press, (1975).   Google Scholar

[2]

L. Ambrosio, N. Fusco and D. Pallara, "Functions of Bounded Variation and Free Discontinuity Problems,", Oxford Mathematical Monographs, (2000).   Google Scholar

[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, (2006), 293.   Google Scholar

[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.  doi: 10.1007/s002459900124.  Google Scholar

[5]

T. F. Chan and S. Esedoḡlu, Aspects of total variation regularized $L^1$ function approximation,, SIAM J. Appl. Math., 65 (2005), 1817.  doi: 10.1137/040604297.  Google Scholar

[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.  doi: 10.1137/040615286.  Google Scholar

[7]

T. F. Chan and J. Shen, "Image Processing and Analysis,", Variational, (2005).   Google Scholar

[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.  doi: 10.1137/090773829.  Google Scholar

[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.   Google Scholar

[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., (1976).   Google Scholar

[11]

S. Esedoḡlu, Blind deconvolution of bar code signals,, Inverse Problems, 20 (2004), 121.  doi: 10.1088/0266-5611/20/1/007.  Google Scholar

[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.  doi: 10.1002/cpa.20045.  Google Scholar

[13]

L. C. Evans and R. F. Gariepy, "Measure Theory and Fine Properties of Functions," Studies in Advanced Mathematics,, CRC Press, (1992).   Google Scholar

[14]

G. Gilboa and S. Osher, Nonlocal linear image regularization and supervised segmentation,, Multiscale Model. Simul., 6 (2007), 595.  doi: 10.1137/060669358.  Google Scholar

[15]

G. Gilboa and S. Osher, Nonlocal operators with applications to image processing,, Multiscale Model. Simul., 7 (2008), 1005.  doi: 10.1137/070698592.  Google Scholar

[16]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Monographs in Mathematics, 80,, Birkhäuser Verlag, (1984).   Google Scholar

[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, (2008), 95.   Google Scholar

[18]

M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 1.21, May 2010., Available from: , ().   Google Scholar

[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, (2001).   Google Scholar

[20]

J. Moll, The anisotropic total variation flow,, Math. Ann., 332 (2005), 177.  doi: 10.1007/s00208-004-0624-0.  Google Scholar

[21]

A. Mosek, Mosek: A Full Featured Software Package Intended for Solution of Large Scale Optimization Problems, 2008., Available from: , ().   Google Scholar

[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).   Google Scholar

[23]

W. Ring, Structural properties of solutions to total variation regularization problems,, M2AN Math. Model. Numer. Anal., 34 (2000), 799.  doi: 10.1051/m2an:2000104.  Google Scholar

[24]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259.  doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[25]

J. E. Taylor, Crystalline variational problems,, Bull. Amer. Math. Soc., 84 (1978), 568.  doi: 10.1090/S0002-9904-1978-14499-1.  Google Scholar

[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), (2011), 159.  doi: 10.1109/WACV.2011.5711498.  Google Scholar

[1]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022

[2]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037

[3]

Denis R. Akhmetov, Renato Spigler. $L^1$-estimates for the higher-order derivatives of solutions to parabolic equations subject to initial values of bounded total variation. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1051-1074. doi: 10.3934/cpaa.2007.6.1051

[4]

Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems & Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273

[5]

Daniela De Silva, Nataša Pavlović, Gigliola Staffilani, Nikolaos Tzirakis. Global well-posedness for a periodic nonlinear Schrödinger equation in 1D and 2D. Discrete & Continuous Dynamical Systems - A, 2007, 19 (1) : 37-65. doi: 10.3934/dcds.2007.19.37

[6]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507

[7]

Patrick Fischer. Multiresolution analysis for 2D turbulence. Part 1: Wavelets vs cosine packets, a comparative study. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 659-686. doi: 10.3934/dcdsb.2005.5.659

[8]

Abdelwahab Bensouilah, Van Duong Dinh, Mohamed Majdoub. Scattering in the weighted $ L^2 $-space for a 2D nonlinear Schrödinger equation with inhomogeneous exponential nonlinearity. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2735-2755. doi: 10.3934/cpaa.2019122

[9]

Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems & Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53

[10]

Michela Procesi. Quasi-periodic solutions for completely resonant non-linear wave equations in 1D and 2D. Discrete & Continuous Dynamical Systems - A, 2005, 13 (3) : 541-552. doi: 10.3934/dcds.2005.13.541

[11]

Guangrong Wu, Ping Zhang. The zero diffusion limit of 2-D Navier-Stokes equations with $L^1$ initial vorticity. Discrete & Continuous Dynamical Systems - A, 1999, 5 (3) : 631-638. doi: 10.3934/dcds.1999.5.631

[12]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[13]

Julia García-Luengo, Pedro Marín-Rubio, José Real. Regularity of pullback attractors and attraction in $H^1$ in arbitrarily large finite intervals for 2D Navier-Stokes equations with infinite delay. Discrete & Continuous Dynamical Systems - A, 2014, 34 (1) : 181-201. doi: 10.3934/dcds.2014.34.181

[14]

Gianluca Crippa, Elizaveta Semenova, Stefano Spirito. Strong continuity for the 2D Euler equations. Kinetic & Related Models, 2015, 8 (4) : 685-689. doi: 10.3934/krm.2015.8.685

[15]

Ka Kit Tung, Wendell Welch Orlando. On the differences between 2D and QG turbulence. Discrete & Continuous Dynamical Systems - B, 2003, 3 (2) : 145-162. doi: 10.3934/dcdsb.2003.3.145

[16]

Julien Cividini. Pattern formation in 2D traffic flows. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 395-409. doi: 10.3934/dcdss.2014.7.395

[17]

Géry de Saxcé, Claude Vallée. Structure of the space of 2D elasticity tensors. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1525-1537. doi: 10.3934/dcdss.2013.6.1525

[18]

Igor Kukavica, Amjad Tuffaha. On the 2D free boundary Euler equation. Evolution Equations & Control Theory, 2012, 1 (2) : 297-314. doi: 10.3934/eect.2012.1.297

[19]

Bernd Kawohl, Guido Sweers. On a formula for sets of constant width in 2d. Communications on Pure & Applied Analysis, 2019, 18 (4) : 2117-2131. doi: 10.3934/cpaa.2019095

[20]

Melody Dodd, Jennifer L. Mueller. A real-time D-bar algorithm for 2-D electrical impedance tomography data. Inverse Problems & Imaging, 2014, 8 (4) : 1013-1031. doi: 10.3934/ipi.2014.8.1013

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]