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).

[2]

L. Ambrosio, N. Fusco and D. Pallara, "Functions of Bounded Variation and Free Discontinuity Problems,", Oxford Mathematical Monographs, (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, (2006), 293.

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

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

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

[7]

T. F. Chan and J. Shen, "Image Processing and Analysis,", Variational, (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. 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.

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

[11]

S. Esedoḡlu, Blind deconvolution of bar code signals,, Inverse Problems, 20 (2004), 121. 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. 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, (1992).

[14]

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

[15]

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

[16]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Monographs in Mathematics, 80,, Birkhäuser Verlag, (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, (2008), 95.

[18]

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

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

[20]

J. Moll, The anisotropic total variation flow,, Math. Ann., 332 (2005), 177. 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: , ().

[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. 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. doi: 10.1016/0167-2789(92)90242-F.

[25]

J. E. Taylor, Crystalline variational problems,, Bull. Amer. Math. Soc., 84 (1978), 568. 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), (2011), 159. doi: 10.1109/WACV.2011.5711498.

show all references

References:
[1]

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

[2]

L. Ambrosio, N. Fusco and D. Pallara, "Functions of Bounded Variation and Free Discontinuity Problems,", Oxford Mathematical Monographs, (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, (2006), 293.

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

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

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

[7]

T. F. Chan and J. Shen, "Image Processing and Analysis,", Variational, (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. 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.

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

[11]

S. Esedoḡlu, Blind deconvolution of bar code signals,, Inverse Problems, 20 (2004), 121. 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. 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, (1992).

[14]

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

[15]

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

[16]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Monographs in Mathematics, 80,, Birkhäuser Verlag, (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, (2008), 95.

[18]

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

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

[20]

J. Moll, The anisotropic total variation flow,, Math. Ann., 332 (2005), 177. 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: , ().

[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. 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. doi: 10.1016/0167-2789(92)90242-F.

[25]

J. E. Taylor, Crystalline variational problems,, Bull. Amer. Math. Soc., 84 (1978), 568. 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), (2011), 159. doi: 10.1109/WACV.2011.5711498.

[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]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Mostafa Bendahmane, Kenneth Hvistendahl Karlsen, Mazen Saad. Nonlinear anisotropic elliptic and parabolic equations with variable exponents and $L^1$ data. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1201-1220. doi: 10.3934/cpaa.2013.12.1201

[20]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281

2017 Impact Factor: 1.465

Metrics

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

Other articles
by authors

[Back to Top]