OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 15, Iss. 22 — Oct. 29, 2007
  • pp: 14817–14837
« Show journal navigation

Joint nonuniform illumination estimation and deblurring for bar code signals

Jeongtae Kim and Hana Lee  »View Author Affiliations


Optics Express, Vol. 15, Issue 22, pp. 14817-14837 (2007)
http://dx.doi.org/10.1364/OE.15.014817


View Full Text Article

Acrobat PDF (1464 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We present a novel joint nonuniform illumination estimation and deblurring method for bar code signals based on a penalized nonlinear squares objective function. The objective function is based on the proper parameterization of a bar code signal and nonuniform illumination as well as a regularization on the illumination using a smoothness penalty. By the minimization of the objective function, the proposed method simultaneously estimates the bar code signal and illumination in the spatial domain. In simulations and experiments, the proposed method showed improved performance compared with two conventional bar code decoding methods without deblurring or nonuniform illumination correction. In a few iterations, the proposed method was able to decode test bar code signals that were not decodable due to blurring or nonuniform illumination.

© 2007 Optical Society of America

1. Introduction

Decoding information from an acquired bar code image requires accurate estimation of the true lengths of bar and space patterns in the bar code image since information is encoded in the lengths of the patterns. To do this, one of the most widely used methods involves detecting edges in the acquired image using an edge detector and subsequently estimating the lengths by computing the differences between the detected edges [1

1. E. Joseph and T. Pavlids, “Deblurring of bilevel waveforms,” IEEE Trans. Image Process. 2, 223–235 (1993). [CrossRef] [PubMed]

]. This local edge based method often does not perform satisfactorily if the image is blurred due to defocusing since the true starting locations of the patterns do not correspond to the detected edges in the acquired image. This has been a concern in bar code signal processing. Researchers have therefore investigated various methods for the deblurring of a bar code signal including improved local methods such as a modified edge detector method [1

1. E. Joseph and T. Pavlids, “Deblurring of bilevel waveforms,” IEEE Trans. Image Process. 2, 223–235 (1993). [CrossRef] [PubMed]

] and a peak detection method [2

2. E. Joseph and T. Pavlids, “Bar code waveform recognition using peak locations,” IEEE Trans. Pattern Anal. Mach. Intell. 16, 630–640 (1994). [CrossRef]

].

Recently, drawbacks of the local methods have been noted, such as sensitivity to noise and limited accuracy in detecting the starting locations of patterns [3

3. S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

]. Several researchers have investigated the statistical properties of speckle noise and its effect on the accuracy of the detected edge locations for laser based scanning systems [4

4. E. Marom, S. Krešić-Jurić, and L. Bergstein, “Analysis of speckle noise in bar-code scanning systems,” J. Opt. Soc. Am. A 18, 889–901 (2001). [CrossRef]

, 5

5. E. Marom, S. Krešić-Jurić, and L. Bergstein, “Speckle noise in bar-code scanning systems-power spectral density and SNR,” Appl. Opt. 42, 161–174 (2003). [CrossRef] [PubMed]

]. In addition, a thorough investigation on edge localization errors due to additive noise has been reported [6

6. S. Krešić-Jurić, “Edge detection in bar code signals corrupted by integrated time-varying speckle,” Pattern Recogn. 38, 2483–2493 (2005). [CrossRef]

]. On the other hand, to overcome the problems, researchers have also investigated alternative global approaches, such as a penalized least squares method [3

3. S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

] and a nonlinear least squares method based on the parameterization of a bar code signal using the locations of edges [7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

]. The deblurring problem, which requires the restoration of a bi-level bar code signal and a convolutional blurring kernel from an acquired signal, is an underdetermined ill-posed inverse problem. Thus, the penalized least squares method incorporated a regularizing penalty function based on the total variation of a bar code signal [3

3. S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

]. Alternatively, the nonlinear least squares method parameterized a bar code signal using edge locations under the assumption that the number of edges is known. Since the bar code signal was parameterized using a small number of parameters, the problem was considered well-posed although it lacks rigorous mathematical proof [7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

]. Compared with the total variation method, the parametric method has the advantage that only a small number of parameters need to be estimated without requiring regularization, thereby improving speed without causing difficulty in tuning the regularization parameter [7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

]. Although the approach is limited for bar code signals whose number of edges is known, there exists a class of bar code signals whose number of edges is predetermined, such as UPC and PDF417 [8

8. R. C. Palmer, The bar code book: reading, printing and specification of bar code symbols (Helmers Publishing Inc.1999).

]. Moreover, in practical situations, the number of edges can be estimated by proper selection of edge candidates during edge detection. In fact, the assumption that the number of edges is known has been often used for modeling the interaction of edges [1

1. E. Joseph and T. Pavlids, “Deblurring of bilevel waveforms,” IEEE Trans. Image Process. 2, 223–235 (1993). [CrossRef] [PubMed]

, 9

9. J. S. Chen and G. Medioni, “Detection, localization and estimation of edges,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 191–198 (1989). [CrossRef]

].

Although the global approaches showed satisfactory performance for deblurring of bar code signals in simulations [3

3. S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

, 7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

], the performance for real bar code images often suffers since the images are usually distorted by nonuniform illumination. To alleviate the problem, attempts have been made to improve lighting devices for bar code scanners [10

10. M. D. Sanner, “Ambient illumination bar code reader,” U. S. Patent 4,874,933 (1989).

,11

11. J. Debiez and F. Lerat, “Intelligent light source,” U. S. Patent 6,774,893 B2 (2004).

]. However, even with such additional hardware devices, the nonuniformity cannot be removed completely. Moreover, demand is increasing for a general purpose hand-held device with imaging capability, such as a mobile phone with a digital camera, having the capability of decoding bar codes [12

12. R. Shams and P. Sadeghi, “Bar code recognition in highly distorted and low resolution images,” in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2007) pp. 737–740.

]. Images acquired by such a device may be more severely distorted by nonuniform illumination. The effect of nonuniform illumination on the intensities of an acquired image is a spatially varying multiplicative field acting on the intensities of an intrinsic image, since the acquired image is the product of the illumination and the reflectance of the intrinsic image [13

13. D. A. Forsyth and J. Ponce, Computer vision: A modern approach (Prentice Hall, 2003).

, 14

14. T. Chen, W. Yin, X. S. Zhou, D. Comaniciu, and T. S. Huang, “Total variation models for variable lighting face recognition,” IEEE Trans. Pattern Anal. Mach. Intell. 28, 1519–1524 (2006). [CrossRef] [PubMed]

]. In the presence of such nonuniform illumination on an image, the performance of image analysis such as segmentation and registration is often degraded [15

15. D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. 208, 212–223 (2002). [CrossRef] [PubMed]

, 16

16. Z. Hou, “A review on MR image inhomogeneity correction,” Int. J. Biomed. Imag. 2006, 1–11 (2006). [CrossRef]

]. We have observed a similar adverse effect of nonuniform illumination in the deblurring of a bar code signal. Therefore, for correct decoding of a bar code signal acquired under nonuniform illumination, both nonuniform illumination compensation and deblurring are essential.

Compared with the deblurring problem, the nonuniform illumination compensation problem has rarely been studied for bar code images. To our knowledge,no investigation on retrospective nonuniform illumination compensation has been reported, although several inventions on improving hardware devices for more uniform illumination have been published [10

10. M. D. Sanner, “Ambient illumination bar code reader,” U. S. Patent 4,874,933 (1989).

,11

11. J. Debiez and F. Lerat, “Intelligent light source,” U. S. Patent 6,774,893 B2 (2004).

]. The analogous problem, however, has been intensively studied in microscopy image processing [15

15. D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. 208, 212–223 (2002). [CrossRef] [PubMed]

,17

17. B. Likar, J. B. A. Maintz, M. A. Viergever, and F. Pernus, “Retrospective shading correction based on entropy minimization,” J. Microsc. 197, 285–295 (2000). [CrossRef] [PubMed]

], magnetic resonance (MR) image corrections [16

16. Z. Hou, “A review on MR image inhomogeneity correction,” Int. J. Biomed. Imag. 2006, 1–11 (2006). [CrossRef]

, 18

18. B. H. Brinkmann, A. Manduca, and R. A. Robb, “Optimized homomorphic unsharp masking for MR grayscale inhomogeneity correction,” IEEE Trans. Med. Imag. 17, 161–171 (1998). [CrossRef]

, 19

19. J. G. Sled, A. P. Zijdenbos, and A. C. Evans, “A nonparametric method for automatic correction of intensity nonuniformity in MRI data,” IEEE Trans. Med. Imag. 17, 87–97 (1998). [CrossRef]

] and document image processing [20

20. M. S. Brown and Y. C. Tsoi, “Geometric and shading correction for images of printed materials using boundary,” IEEE Trans. Image Process. 15, 1544–1554 (2006). [CrossRef] [PubMed]

]. The nature of the nonuniform illumination compensation (often called shading correction) is the estimation of the unknown multiplicative field (nonuniform illumination for microscopy and document images, inhomogeneous magnetic field for MR images) and unknown intrinsic image from an observed image. Simultaneously estimating the nonuniform illumination and the intrinsic image in the spatial domain is a well known underdetermined ill-posed problem [14

14. T. Chen, W. Yin, X. S. Zhou, D. Comaniciu, and T. S. Huang, “Total variation models for variable lighting face recognition,” IEEE Trans. Pattern Anal. Mach. Intell. 28, 1519–1524 (2006). [CrossRef] [PubMed]

]. Consequently, conventional methods often separate the illumination and the intrinsic image in the frequency domain or in the distribution domain (such as a histogram domain). For example, based on the assumption that illumination is slowly varying in the spatial domain, methods that separate illumination based on homomorphic filtering (lowpass filtering of the observed signal after taking the logarithm) have been investigated [15

15. D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. 208, 212–223 (2002). [CrossRef] [PubMed]

,18

18. B. H. Brinkmann, A. Manduca, and R. A. Robb, “Optimized homomorphic unsharp masking for MR grayscale inhomogeneity correction,” IEEE Trans. Med. Imag. 17, 161–171 (1998). [CrossRef]

]. The performance of these approaches is limited since the intrinsic image also has low frequency components. Other methods rely on the assumption that the distribution of the observed image is the blurred distribution of the intrinsic image due to nonuniform illumination. Such methods seek a multiplicative field that minimizes the entropy of the estimated intrinsic image [17

17. B. Likar, J. B. A. Maintz, M. A. Viergever, and F. Pernus, “Retrospective shading correction based on entropy minimization,” J. Microsc. 197, 285–295 (2000). [CrossRef] [PubMed]

] or that maximizes the frequency contents of the distribution of the estimated intrinsic image [19

19. J. G. Sled, A. P. Zijdenbos, and A. C. Evans, “A nonparametric method for automatic correction of intensity nonuniformity in MRI data,” IEEE Trans. Med. Imag. 17, 87–97 (1998). [CrossRef]

].

For nonuniform illumination compensation and deblurring for a bar code signal, we believe that the existing methods are not the most appropriate since they do not utilize the fact that a bar code signal is a bi-level waveform. In addition, since the existing methods only attempt to compensate for nonuniform illumination effects, deblurring and edge detection must be performed separately in order to decode the bar code.

In this study, we propose a joint nonuniform illumination estimation and deblurring method that simultaneously estimates nonuniform illumination and a bar code signal in the spatial domain. We parameterize a bar code signal using the locations of edges and model nonuniform illumination using a sum of B-spline functions that has been shown to be effective in approximating a continuous function [21

21. M. Unser, “Splines: A perfect fit for signal and image processing,” IEEE Signal Process. Mag. 16, 22–38 (1999). [CrossRef]

]. Since the minimization of square errors between an observed signal and a signal model can be ill-posed even though the number of parameters in our model is much smaller than the number of observations, we incorporate a regularizing penalty based on the a priori information that illumination is slowly varying in the spatial domain. The proposed method utilizes the fact that the true intrinsic image is a blurred bi-level image based on accurate modeling of a bar code signal. Moreover, since nonuniform illumination and the bar code signal are jointly estimated, the proposed method does not suffer from performance degradation in deblurring due to nonuniform illumination effects.

2. Theory

2.1. Model

We model an observed bar code signal under unknown illumination by the product of a blurred bar code signal and a spatially varying illumination field with additive noise as follows:

y(t)=I(t)[G(t)x(t)+c]+n(t),
(1)

We assume that the number of edges, K, in a bar code signal is known. Based on the assumption, we parameterize a clean bar code signal as follows:

x(t;e)=i=1K(1)i1u(tei),
(2)

where e = [e 1,e 2,...,eK] denotes the locations of edges such that e i+1 > ei, and u(t) is the unit step function. We also parameterize the blurring kernel using the Gaussian function with unknown standard deviation σ> 0 as follows:

G(t;σ)=12πσ2et22σ2.
(3)

Although the true blurring kernel is neither space invariant nor an exact Gaussian function [22

22. D. G. Bailey, “Super-resolution of bar codes,” J. Electron. Imag. 10, 213–220 (2001). [CrossRef]

], the simple, space invariant Gaussian model has been effectively used for modeling blurring kernels in many other investigations and applications including modeling the line spread function in flying spot laser based bar code scanners [1–3

1. E. Joseph and T. Pavlids, “Deblurring of bilevel waveforms,” IEEE Trans. Image Process. 2, 223–235 (1993). [CrossRef] [PubMed]

,6

6. S. Krešić-Jurić, “Edge detection in bar code signals corrupted by integrated time-varying speckle,” Pattern Recogn. 38, 2483–2493 (2005). [CrossRef]

,7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

]. We model spatially varying illumination using third order B-spline functions that are uniformly located in the spatial domain as follows:

I(t;b)=j=1Lbjβ3(tlj),
(4)

where β 3(t) is a third order B-spline function centered at zero, L is the number of the B-spline functions, b = [b 1, ...,bL] denotes the coefficients for the B-spline function and lj, j = 1,..., L denote uniformly distributed center locations of the B-spline functions. We predetermine the locations of the B-spline functions. In addition, we impose positivity constraints on the coefficients for the B-Spline functions to ensure that illumination is positive everywhere. The B-spline based model in Eq. (4) has been shown effective for approximating a continuous function by proper selection of the coefficients [21

21. M. Unser, “Splines: A perfect fit for signal and image processing,” IEEE Signal Process. Mag. 16, 22–38 (1999). [CrossRef]

]. With the models in Eq. (1)–Eq. (4), the goal of joint nonuniform illumination estimation and deblurring of a bar code signal is the accurate estimation of e, b, c, and σ from y(t). Although accurate estimation of e is sufficient for correct decoding of a bar code signal, we think that accurate estimation of b, c, and σ is also necessary for the accurate estimation of e. If the parameters b, c, and σ are not accurately estimated, estimation of e with the inaccurately estimated parameters corresponds to estimation based on an incorrect signal model. It has been reported that the performance of an estimator based on an incorrect model deteriorates, i.e., the estimator may have larger bias and/or variance than that of an estimator based on a correct model [23

23. Y. C. Eldar, A. Ben-Tal, and A. Nemirovski, “Robust mean-squared error estimation in the presence of model uncertainties,” IEEE Trans. Signal Process. 53, 168–181 (2005). [CrossRef]

].

2.2. Regularization

Based on the models defined in Eq. (1)–Eq. (4), we consider the problem of estimating the parameter vector θ = [θ 1, ...,θN]T = [e, σ,c,b]T ∊ ℝN, where the number of total parameters N = K + 2 + L, from the samples of the observed signal y(ti),i = 1,...,M subject to the constraints such as ei < e i+1, σ > 0, c > 0 and bj > 0. To solve the problem, one effective approach is determining a parameter vector θ that minimizes square errors between an observed signal and a model subject to the constraints. This leads to a constrained optimization problem. Although constraints do exist, we focus on unconstrained optimization since, for most real bar code signals, the constraints are not violated during optimization provided the initial estimate is close to the optimal parameter vector. Within the unconstrained optimization framework, the most natural approach is determining an estimator θ^ that minimizes the sum of nonlinear squares:

θ̂=argminθF(θ),
(5)

here the objective function F(θ) is defined as

F(θ)=12i=1M[fi(θ)]2,
(6)

where fi(θ) is the sampled residual defined as

fi(θ)=y(ti)I(ti;b)[G(ti;σ)x(ti;e)],
(7)

where ti denotes the sample locations, and [G(ti;σ)∗ x(ti;e)] denotes [G(t;σ)∗x(t;e)]t=ti for notational simplicity. The nonlinear least squares problem in Eq. (5) can be ill-posed, even though the number of variables N is usually smaller than the number of observations M, since the minimizer may not be unique [24

24. M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

]. Note that the minimizer is determined by zeroing the gradient of the objective function F(θ) as follows:

θF(θ)|θ=θ̂=J(θ)Tf(θ)|θ=θ̂=0,
(8)

where θF(θ)=[F(θ)θ1,,F(θ)θN]T, f(θ) = [f 1(θ),...,fM(θ)]T and the Jacobian matrix J(θ) ∊ ℝM×N of f(θ) is defined as follows:

[J(θ)]ij=fi(θ)θj.
(9)

For θ˜ in a neighborhood of θ^, if J(θ˜) (J(θ) |θ˜ = J(θ˜) for notational simplicity) is rank-deficient, i.e., the rank of J(θ˜) is smaller than N, the nonlinear least squares problem is ill-posed since the solution of Eq. (8) is not unique [24

24. M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

]. Equivalently, the Hessian matrix ∇θ 2 F(θ) ∊ ℝN×N of the objective function F(θ) can be singular at θ˜ since, in a neighborhood of θ^, the Hessian matrix is well approximated by the Jacobian as follows [25

25. P. E. Gill and W. Murray, “Algorithms for the solution of the nonlinear least-squares problem,” SIAM J. Numer. Anal. 15, 977–992 (1978). [CrossRef]

]:

θ2F(θ˜)J(θ˜)TJ(θ˜),
(10)

where (i, j)th element of the Hessian matrix is defined as follows:

[θ2F(θ)]ij=2F(θ)θiθj.
(11)

Therefore, it is difficult to apply the Gauss-Newton method or its variations to solve the nonlinear least squares problem since the approximated Hessian is not invertible [24

24. M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

,25

25. P. E. Gill and W. Murray, “Algorithms for the solution of the nonlinear least-squares problem,” SIAM J. Numer. Anal. 15, 977–992 (1978). [CrossRef]

]. For an ill-posed problem, in order to determine unique solution and stabilize a numerical procedure for the solution, regularization based on a priori information about the solution is required [24

24. M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

,25

25. P. E. Gill and W. Murray, “Algorithms for the solution of the nonlinear least-squares problem,” SIAM J. Numer. Anal. 15, 977–992 (1978). [CrossRef]

]. The regularization is usually accomplished by adding a regularizing penalty function to the objective function in such a way that the approximated Hessian matrix becomes positive definite [26

26. J. Eriksson, P. A. Wedin, M. E. Gulliksson, and I. Söderkvist, “Regularization methods for uniformly rank-deficient nonlinear least-squares problems,” J. Optim. Theor. Appl. 127, 1–26 (2005). [CrossRef]

].

A situation causing the nonlinear least squares method with nonuniform illumination model to be ill-posed is when illumination is indistinguishable from the blurred bar code signal. For example, suppose that there are two different illuminations I(ti;b 1) and I(ti;b 2) that have the same shapes as the blurred bar code signal [G(ti; σ 2)∗x(ti;e 2)+ c 2)] and [G(t; σ 1)∗x(ti;e 1)+ c 1)], respectively, such that:

I(ti;b1)[G(ti;σ1)x(ti;ei)+c1]=I(ti;b2)[G(ti;σ2)x(ti;e2)+c2],i=1,,M.
(12)

By the mean value theorem [27

27. E. Kreyszig, Advanced engineering mathematics, 8th ed. (Wiley, 1998).

], there exists a nonzero vector h ∊ ℝN and a parameter vector θ˜ on the line connecting θ 1 = [e 1,σ 1,c 1,b 1] and θ 2 = [e 2;σ 2,c 2,b 2] in the parameter space such that:

hJ(θ˜)T=0,
(13)

where, 0 denotes the 1 × M zero vector. Equation (13) implies that J(θ˜) is rank deficient. To prevent singular Hessian matrices during optimization, we regularize I(t; b) such that illumination would not have a waveform similar to the blurred bar code model.

Before designing a regularization method, we first consider the nonlinear least squares problem in Eq. (5)–Eq. (7) using the uniform illumination model, i.e., the problem of estimating θs = [e, σ, c, b]T ∊ ℝK+3, where b > 0. For this model, all the B-spline coefficients bj, j = 1,..,L in Eq. (4) are set by b. The nonlinear least squares problem with uniform illumination model is equivalent to estimating σ, c, b, and a bi-level signal x(ti) ∊ {0,1}, i = 1,...,M that has the total variation of K (number of edges). Note that the set of bi-level signals having total variation of K is the same as the set of bi-level signals composed of K edges. It has been shown that the estimation of x(ti) having a bounded total variation from y(ti) is well-posed with some constraints such that σ > 0 and bP, where P is a compact subset of positive real numbers [3

3. S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

]. One can also show that two different parameter vectors do not satisfy Eq. (12) by extending the uniqueness proof in [3

3. S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

]. Based on the result, we assume that the nonlinear least squares with uniform illumination model is well-posed and the unique minimizer is determined by zeroing the gradient of the objective function. For most real bar code signals, this assumption is true since the constraints are not violated during optimization. Based on the assumption, the approximated Hessian at some θ˜s in a neighborhood of the minimizer is positive definite, i.e., for all θs ∊ ℝK+3, the following inequality holds:

θsTJs(θ˜s)TJ(θ˜s)θs>0,
(14)

where Js(θs) ∊ ℝM×(K+3) is the Jacobian matrix of f(θs) = [f 1s), ...,fM(θs)]T.

Next, we consider a regularization method for the nonlinear least squares method with nonuniform illumination model. From inequality (14), it is straightforward to show that

θsTJs(θ˜s)TJ(θ˜s)θs=θuTJu(θ˜u)TJ(θ˜u)θu,
(15)

where, θu = [e, σ, c, bu]T ∊ ℝN and θ˜u = [ẽ, σ˜, , u]T ∊ ℝN are the extended vectors of θs and θ˜s using bu = [b,..,b] ∊ ℝL and u = [,..,] ∊ ℝL, respectively. Furthermore,since ∂fi(θ)/∂bj is not a function of bj, it is straightforward to show the following equality:

J(θ˜)=J(θ˜u),
(16)

where θ˜ = [ẽ, σ˜, , b̃] with a b̃ vector that does not necessarily have uniform B-spline coefficients. Based on inequality (14), Eq. (15) and Eq. (16), the approximated Hessian of the objective function F(θ) satisfies the following inequality:

θuTJ(θ˜)TJ(θ˜)θu>0.
(17)

Note that inequality (17) does not guarantee the positive definiteness of the approximated Hessian since θTJ(θ˜)T J(θ˜)θ > 0 is required. To overcome the problem, we design a new objective function that includes a regularizing penalty function:

Φ(θ)=12i=0M[fi(θ)]2+λR(θ),
(18)

where λ > 0 is a regularization parameter and the roughness penalty function R(∙) is defined as follows:

R(θ)=12θTRθ=j=1L1(bjbj+1)2,
(19)

where R is the matrix representation of the roughness penalty function [28

28. J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE. Trans. Med. Imag. 13, 290–300 (1997). [CrossRef]

]. The penalty function in Eq. (19) penalizes the changes of neighboring B-spline coefficients, thereby encouraging the estimated illumination to be smooth. It has been shown that if the change of neighboring B-spline coefficients is bounded by a constant α > 0, then the first order derivatives of nonuniform illumination in Eq. (4) are bounded by α/L where L is the distance between two neighboring B-spline coefficients [29

29. J. Kim, Intensity-based image registration using robust similarity measure and constrained optimization: Applications for radiation therapy, Ph.D. dissertation, The University of Michigan, Ann Arbor, 2004. [PubMed]

]. The first term in the objective function in Eq. (18) encourages errors in fitting data to the observations to be small, while the second term encourages estimated illumination to be smooth. The regularization parameter λ controls the trade-off between the fidelity to the observed data and the smoothness of the illumination.

For θ˜ in a neighborhood of the minimizer, the Hessian matrix of the objective function Φ(θ) in Eq. (18) is well approximated as follows:

θ2Φ(θ˜)J(θ˜)TJ(θ˜)+λR.
(20)

We claim that the approximated Hessian is positive definite, satisfying the following inequality:

θTJ(θ˜)TJ(θ˜)θ+λθTRθ>0.
(21)

The claim is true since for θ that has uniform B-spline coefficients, θTJ(θ˜)TJ(θ˜)θ > 0 by Eq. (17) while λθT R θ = 0, and for θ whose B-spline coefficients are not uniform, λθT R θ > 0 even if θTJ(θ˜)TJ(θ˜)θ = 0. Since the approximated Hessian in Eq. (20

20. M. S. Brown and Y. C. Tsoi, “Geometric and shading correction for images of printed materials using boundary,” IEEE Trans. Image Process. 15, 1544–1554 (2006). [CrossRef] [PubMed]

) is positive definite in a neighborhood of the minimizer, one may apply the Gauss-Newton algorithm to minimize the objective function in Eq. (18). We minimize the objective function using the standard Gauss-Newton algorithm that constructs a sequence of parameters {θk} as follows:

θk+1=θkH(θk)1J(θk)Tf(θk),k=1,2,
(22)

where H(θk) = J(θk)TJ(θk)+λ R.

Due to the constraints such as σ > 0, e i+1 > ei, i = 1,.., K, c > 1 and bj >0,j= 1,..,L, one must solve the constrained nonlinear least squares problem. To do this, we have incorporated active set strategy [30

30. P. E. Gill, W. Murray, and M. H. Wright, Practical optimization (Academic Press, 1981).

] with the Gauss-Newton algorithm. However, in practice, no constraint was violated during iterations for most bar code signals that were correctly decoded. For a severely blurred and noisy image, we observed that certain constraints were violated during iterations. For these cases, the bar code was not correctly decoded.

2.3. Initial estimates

3. Results

3.1. Simulations

To evaluate the performance of the proposed joint nonuniform illumination estimation and de-blurring method, we conducted simulations using UPC bar code signals. Bars and spaces in a true UPC bar code image can have one of four different lengths, each length being an integer multiple of a minimum length up to four times the minimum. For simplicity of notation, we denote the minimum length by length 1 and other lengths by length 2 through length 4 based on the ratios of their lengths to the minimum. Figure 1(a) shows a two-dimensional (2D) UPC bar code image representing code ‘012345678905’. Figure 1(b) shows a clean 1D signal of the same code with a constant background of unity (without loss of generality, we assume that the interval of interest starts at t = 0 and ends at t = 1). If Fig. 1(a) were an ideal image, Fig. 1(b) would correspond to a horizontal line scan of Fig. 1(a). In Fig. 1(b), the length of the bar code signal is 0.9406 (excluding the background) and the length 1 corresponds to 0.0099.

We synthesized the 1D blurred signal shown in Fig. 2(a) by convolving the signal shown in Fig. 1(b) with the Gaussian convolutional kernel whose σ is 0.007. We also generated two synthetic nonuniform illuminations (shown in Fig. 2(b)) having Gaussian and linear functional forms, respectively. We multiplied each synthetic nonuniform illumination with the signal in Fig. 2(a), and added white Gaussian noise for generating synthetic observations. Figure 2(c) and Fig. 2(d) show two synthetic observations with the Gaussian and the linear illuminations, respectively. For comparison, we have included a synthetic observation with uniform illumination whose magnitude is unity in Fig. 2(c) and Fig. 2(d).

Fig. 1. 2D image and 1D signal for UPC bar code representing ‘012345678905‘: (a) 2D UPC bar code image; (b) 1D ideal bar code signal.

To decode the signal shown in Fig. 2(c), we applied three different methods: (1) the edge based method that attempts to decode the signal using initial estimates of edge locations, (2) the nonlinear least squares with uniform illumination model (NLS-UI) method and (3) the proposed method (the nonlinear least squares with nonuniform illumination model). For the proposed method, we placed 128 B-spline functions uniformly in the spatial domain.

Figure 3(a) shows the fitted bar code signal using the edge based method, which may be considered as the initial fitting for the proposed method (to simplify the illustration, the true c value was used instead of the initial one). Figure 3(b) and Fig. 3(c) show the fitted signals by using the NLS-UI method and the proposed method, respectively. Figure 3(d) shows the estimated illumination using the proposed method with the regularization parameter λ = 50. As shown in Fig. 3(a), Fig. 3(b) and Fig. 3(c), the fitted signal using the proposed method is closer to the observed signal than that using the other methods. Note that the fitted signal in Fig. 3(b) has larger fitting errors around peaks than that using the proposed method. In addition, the estimated nonuniform illumination in Fig. 3(d) was close to the true illumination that was used to synthesize the observation.

We also applied the three methods to the observation shown in Fig. 2(d), although the figures are not shown here. The results were similar to the results shown in Fig. 3: the proposed method gave the best match of the fitted signal to the observed signal.

The goodness of fit of the estimated signal to the observed signal is only one measure of the performance of each method. The goal of bar code deblurring is the accurate estimation of edge locations, and accurate estimation of the length of each bar and space pattern is the key element to correctly decode a bar code signal. Thus we compute the estimated lengths of patterns, Δ^ = [Δ^ 1, Δ^ 2,..., Δ^ K-1], whose elements are defined as follows:

Δ̂i=t̂i+1t̂ii=1,2,,K1,
(23)

where i is the location of each estimated edge. If the elements of Δ^ satisfy the following relationship, Δ^ i1 < Δ^ i2 < Δ^ i3 < Δ^ i4, where i1, i2, i3, and i4 denote the indices for length 1, length 2, length 3, and length 4 in the true bar code signal, one may decode the bar code correctly by proper grouping of the estimated lengths.

Fig. 2. Synthetic blurred bar code signals with nonuniform illuminations: (a) synthetic blurred bar code signal; (b) synthetic nonuniform illuminations; (c) synthetic observation with the Gaussian illumination; (d) synthetic observation with the linear illumination.

Figure 4(a), Fig. 4(b) and Fig. 4(c) show Δ^ for the signal shown in Fig. 2(c) using the edge based method, the NLS-UI method and the proposed method, respectively. For comparison, we have included the true length of patterns in the figures. As shown in Fig. 4(a), the edge based method was not able to decode the bar code signal correctly since Δ^ 37 and Δ^ 39 (length 1 in the true signal) are larger than Δ^ 40 and Δ^ 42 (length 2). In addition, Δ^ 22 (length 3) is almost the same as Δ^ 36 (length 4). The NLS-UI method was likewise not able to decode the bar code. In Fig. 4(b), Δ^ 25 (length 2 in the true signal) was larger than Δ^ 26 (length 3). In addition, Δ^ 54 (length 2) was larger than Δ^ 55 (length 3). Compared with the conventional methods, the proposed method showed significantly improved results. As shown in Fig. 4(c), the estimated lengths Δ^ by the proposed method are very close to the true lengths. Clearly, the bar code can be correctly decoded by grouping the estimated lengths using the threshold 1 through threshold 3 shown in Fig. 4(c).

We repeated the same simulations for the signal in Fig. 2(d) and obtained similar results. Neither the edge based method nor the NLS-UI method decoded the signal correctly, while the proposed method decoded correctly. For brevity, these figures are not shown here.

Fig. 3. Fitted signals for the observation in Fig. 2(c) using the three methods, plus the estimated illumination by the proposed method: (a) fitted bar code signal using the edge method; (b) fitted bar code signal using the NLS-UI method; (c) fitted bar code signal using the proposed method; (d) estimated illumination by the proposed method.

To quantify the performance of each method in terms of correct estimation of edge locations, we computed the maximum error (ME) of the estimated edge locations as follows:

ME=maxit̂ititrue,i=1,2,,K,
(24)

where titrue denotes the true locations of edges. We use the ME for evaluating the performance of each method instead of usual mean square error since a large estimation error of a single edge location can result in the failure of decoding entire bar code [6

6. S. Krešić-Jurić, “Edge detection in bar code signals corrupted by integrated time-varying speckle,” Pattern Recogn. 38, 2483–2493 (2005). [CrossRef]

]. To evaluate the statistical properties of each method, we applied each of the three methods 100 times for the signal shown in Fig. 2(c) and Fig. 2(d) with different noise realizations, and computed the average of the ME. We repeated these simulations for different size blurring kernels and for signals with different signal-to-noise ratios (SNR). Table 1 and Table 2 summarize the results for the signals shown in Fig. 2(c) and Fig. 2(d), respectively. In the tables, we represent the level of blur by 2σ/T (T is the length 1 in the signal shown in Fig. 1(b)) since the edge localization error for a stripe (bar or space) due to a blurring kernel is approximately inversely proportional to the width of the stripe. As shown in the tables, the proposed method exhibited smaller ME than the existing methods in all simulations.

Fig. 4. Estimated lengths of patterns for the signal shown in Fig. 2(c) using the three methods: (a) the edge method; (b) the NLS-UI method; (c) the proposed method.

Table 1. Average ME values of the three methods for the signal shown in Fig. 2(c) with different size blurring kernels and SNR values (the unit for ME value is 10-3).

table-icon
View This Table
| View All Tables

Since the ultimate goal of bar code decoding is to decode a bar code signal correctly, we also evaluated the performance of each method by a decode rate that was computed by the percentage of correct decoding for the signal shown in Fig. 2(c) in 100 different noise realizations. We repeated the computation of the decode rate for different size blurring kernels and for signals with different SNR. Table 3 summarizes the results. As shown in the table, the proposed method showed significantly improved decode rate compared with the other methods in all simulations. An interesting observation was that, for blur level 1.21, the decode rate of the NLS-UI method for higher SNR signals (20dB and 25dB) was worse than that for lower SNR signal (15dB).

Table 2. Average ME values of the three methods for the signal shown in Fig. 2(d) with different size blurring kernels and SNR values (the unit for ME value is 10-3).

table-icon
View This Table
| View All Tables

Table 3. Decode rate values of the three methods for the signal shown in Fig. 2(c) with different size blurring kernels and SNR values (the unit for decode rate is %.)

table-icon
View This Table
| View All Tables

This is due to the fact that the NLS-UI method was not able to decode noise free signal since the method was based on an incorrect model (uniform illumination model while true illumination was nonuniform). For low SNR signal, we suspect that large variability of estimated edge locations due to noise happened to result in correct decoding in some realizations. When modeling error was small, i.e., true illumination was close to unform illumination, we observed that the decode rate of the NLS-UI method improved as SNR increased although results for this are not included for brevity.

In the preceding simulations, the regularization parameter λ was determined manually. To investigate the effect of λ, we applied the proposed method to the signals shown in Fig. 2(c) and Fig. 2(d) while changing the value of λ. Figure 5(a) and Fig. 5(b) show the estimated nonuniform illuminations with different λ values for the signals shown in Fig. 2(c) and Fig. 2(d), respectively. As shown in the figures, small λ yielded rapidly changing illumination that is not close to the true illumination. As a result, a very small regularization parameter such as λ = 0.1 prevented the proposed method from accurately decoding the bar code. Using a very large λ value, such as λ = 1000 in Fig. 5(a) and λ = 10000 in Fig. 5(b), also led to incorrect decoding, yielding almost uniform illumination. In other words, if λ is too large, the proposed method yields results very similar to those of the NLS-UI method. However, for a wide range of λ such as 0.1 < λ < 1000, the proposed method was able to correctly decode the signals.

Figure 6(a) and Fig. 6(b) show the changes of the objective function and the ME of the estimated edge locations during optimization using the proposed method with different λ values for the signals shown in Fig. 2(c) and Fig. 2(d). As shown in Fig. 6(a), the proposed method converged to the minima within less than 10 iterations for every λ value. Note that the converged values of the objective function using smaller λ values are smaller than that using larger λ. This result is expected since a smaller regularization parameter implies more fidelity to the measured data. However, as shown in Fig. 6(b), the ME of the estimated edge locations with a small λ such as 0.1 or 1 is larger than that with λ = 50. This result implies that simply minimizing data fitting errors may yield physically unrealistic results, since rapidly changing illumination can better fit a noisy observation. Therefore, incorporating a priori information about the solution, such as the smoothness of illumination, is important for accurate decoding of a bar code signal.

Fig. 5. Estimated nonuniform illuminations for the signals shown in Fig. 2(c) and Fig. 2(d) with different λ values: (a) for the signal shown in Fig. 2(c); (b) for the signal shown in Fig. 2(d).

Figure 6(c) and Fig. 6(d) show the changes of the objective function and the ME of the estimated edge locations for the signal shown in Fig. 2(d). The results are similar to those in Fig. 6(a) and Fig. 6(b) in the sense that too small or too large λ yields larger ME than a well-chosen λ value such as 500. Although the performance of the proposed method depends on λ, it is worth while to note that the method was able to decode the bar code signals correctly over a wide range of λ.

3.2. Experiments

We acquired real bar code images using a digital camera (Canon EOS-350D). Figure 7(a) and Fig. 7(b) show two bar code images acquired under nonuniform illumination. In Fig. 7(a), illumination around the central portion of the image was brighter than around the outer parts. In Fig. 7(b), illumination was brighter on the left portion of the image than on the right portion. We scanned in horizontal lines across each image for decoding. Figure 7(c) and Fig. 7(d) show the scanned 1D signals from Fig. 7(a) and Fig.7(b), respectively. Unlike the synthesized 1D signals used for simulations, space patterns in these images have higher intensity values than the bar patterns since the intensity levels of the brighter parts are higher in the acquired image.

We applied the two existing methods as well as the proposed method to the real bar code signals shown in Fig. 7(c). Figure 8(a), Fig. 8(b) and Fig. 8(c) show the fitted signals using the three methods. In addition, Fig. 8(d) shows the estimated illumination using the proposed method with λ = 100. Figure 8(a) through Fig. 8(c) show that the proposed method gives a fitted signal more closely matching the observed signal than the other methods do. This result is consistent with the results in the simulations.

Figure 9(a), Fig. 9(b) and Fig. 9(c) show the fitted signals for the observed signal shown in Fig. 7(d) using the three methods. In addition, Fig. 9(d) shows the estimated illumination using the proposed method. The figures demonstrate that the proposed method yields smaller fitting errors than the others.

To evaluate the performance of the three methods in terms of decodability, we computed the lengths of the estimated patterns, Δ^ , by each method. Figure 10(a), Fig. 10(b) and Fig. 10(c) show the estimated Δ^ for the real bar code signal shown in Fig. 7(c) using the edge method, the NLS-UI method and the proposed method, respectively. Since the true length of a length 1 pattern is not known in a real image, we estimated the true length by dividing the sum of estimated lengths by 95 that is the total length of the true patterns when length 1 is unity (since the estimated length 1 is based on an estimated results, it can be different for different estimations). Using the estimated length 1, we generated correct Δ^ based on the ratios of true patterns to the estimated length 1, and included such correct Δ^ for comparison.

Fig. 6. Change of the objective functions and ME during iterations for the signals shown in Fig. 2(c) and Fig. 2(d): (a) the objective function for the signal shown in Fig. 2(c); (b) the ME for the signal shown in Fig. 2(c); (c) the objective function for the signal shown in Fig. 2(d); (d) the ME for the signal shown in Fig. 2(d).

As shown in Fig. 10(a), the edge based method did not decode the bar code correctly, giving Δ^ 17 (length 4 in the actual bar code) is smaller than Δ^ 25 (length 3) and Δ^ 12 (length 2) smaller than Δ^ 16 (length 1). Similarly, the NLS-UI method did not decode the signal correctly. In Fig. 10(b), Δ^ 1 (length 1 in the actual bar code) is larger than Δ^ 8 and Δ^ 10 (length 2). In addition, Δ^ 4 (length 3) is smaller than Δ^ 5 (length 2). Compared with the existing methods, the proposed method was able to estimate the lengths of the patterns more accurately as shown in Fig. 10(c). It is clear that the bar code can be correctly decoded using the thresholds shown in Fig. 10(c).

Figure 11(a), Fig. 11(b) and Fig. 11(c) show the lengths of patterns estimated by the three methods for the real signal shown in Fig. 7(d). Again, the edge method was not able to decode the signal, giving Δ^ 11 and Δ^ 13 (length 2 in the actual bar code) smaller than Δ^ 19 (length 1). As shown in Fig. 11(b), the NLS-UI method also gave a number of errors, especially for the right hand part of the signal. For example, Δ^ 47 (length 2) is smaller than Δ^ 48 (length 1). In addition, Δ^ 59 (length 1) is even larger than Δ^ 36 (length 4). In contrast, Fig. 11(c) shows that the proposed method was able to correctly decode the signal.

Fig. 7. Bar code images under nonuniform illumination: (a) bar code image whose central part is brighter due to nonuniform illumination; (b) bar code image whose left part is brighter due to nonuniform illumination; (c) horizontal line scan of the image in (a); (d) horizontal line scan of the image in (b).

We also studied the effect of the regularization parameter in decoding the real bar code images. Figure 12(a) and Fig. 12(b) show the estimated nonuniform illuminations with different λ values for the real signals shown in Fig. 7(c) and Fig. 7(d), respectively. As expected, Fig. 12 shows that very large λ yielded almost uniform illumination, thereby suffering from the same problem as the NLS-UI method. This is consistent with the simulation results. On the other hand, with very small λ such as 10-2, the estimated illumination is not physically realistic, changing rapidly in the spatial domain. This is due to the fact that the penalized nonlinear least squares problem becomes increasingly ill-conditioned as λ becomes smaller [24

24. M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

], implying that the estimation with smaller λ is more sensitive to noise. As in the simulations, although very small or very large λ values give incorrect decoding, the proposed method correctly decodes bar codes for a broad range of λ values, such as 1 < λ < 1000.

Figure 13(a) and Fig. 13(b) show the changes of the objective function for the real signals of Fig. 7(c) and Fig. 7(d) with different λ values. The optimization procedure converged to the minima within 10 iterations for every case except for very small λ such as 10-2. For λ = 10-2, the numerical optimization procedure showed oscillatory behavior, likely due to the fact the approximated Hessian becomes close to singular [24

24. M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

].

Fig. 8. Fitted signals for the observation in Fig. 7(c)) using the three methods, plus the estimated illumination using the proposed method: (a) the edge method; (b) the NLS-UI method; (c) the proposed method; (d) estimated illumination by the proposed method with λ= 10.

4. Discussion

In the presence of blurring and nonuniform illumination in acquired bar code images, the local edge method and the NLS-UI method, which may be considered the same method described in [7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

] except for the slight extension of including background intensity, did not perform satisfactorily. The edge based method was not able to decode most blurred bar code signals even in simulations with uniform illumination. The NLS-UI method also failed to decode most bar code images acquired under nonuniform illumination. Compared with the two existing methods, the proposed joint nonuniform illumination estimation and deblurring method showed significantly improved results in both simulations and experiments.

One may conceive of a two-step method that first applies one of the existing nonuniform illumination correction methods [15–18

15. D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. 208, 212–223 (2002). [CrossRef] [PubMed]

, 20

20. M. S. Brown and Y. C. Tsoi, “Geometric and shading correction for images of printed materials using boundary,” IEEE Trans. Image Process. 15, 1544–1554 (2006). [CrossRef] [PubMed]

] to an observed bar code signal, then applies a de-blurring method such as the one described in [7

7. L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

]. We believe that our proposed method has advantages over such a hypothetical method. Firstly, unlike the proposed method, the existing nonuniform illumination correction methods do not incorporate the fact that a bar code signal is a bi-level waveform, although a comparative study is deferred to future research. Secondly, since the proposed method jointly performs the estimation of illumination and deblurring of a bar code, it overcomes the problem that errors in nonuniform illumination estimation lead to in errors in deblurring. The hypothetical two-step method involves an optimization of parameters in illumination model followed by a separate optimization of parameters involved in deblurring. Apparently, iterations of these two stages are required for convergence [31

31. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in C++, 2nd ed. (Cambridge, 2005).

]. This requires significantly more computation. Moreover, for many cases, it has been reported that such alternating optimization is less effective than simultaneous optimization [31

31. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in C++, 2nd ed. (Cambridge, 2005).

].

Fig. 9. Fitted signals for the observation in Fig. 7(d) by the three methods, plus the estimated illumination by the proposed method: (a) the edge method; (b) the NLS-UI method; (c) the proposed method; (d) estimated illumination by the proposed method with λ= 10.

Fig. 10. Estimated lengths of patterns by the three methods for the signal in Fig. 7(c): (a) the edge method; (b) the NLS-UI method; (c) the proposed method.

As shown in the simulations and experiments, the design of the regularization parameter λ is important for accurate estimation of illumination and the locations of edges. Using a very large λ in the proposed method yields estimation results similar to the NLS-UI method. Using a very small λ yields unrealistic estimation of illumination and inaccurate estimation of edges due to noise and numerical instability. However, for a broad range of λ values, the proposed method was able to correctly decode bar code signals that were not decodable by conventional methods, suggesting that the tuning of λ may not be very difficult in practice. In our simulations and experiments, we determined λ manually. We plan to investigate an automatic method for tuning of the regularization parameter.

We applied the Gauss-Newton method with active set strategy for solving the constrained penalized nonlinear least squares in our method. Although we designed a constrained optimization method to accommodate constraints such as the positivity of σ, the positivity of illumination, the positivity of background intensity and the orders of edge locations, no constraint was violated during iterations for most bar code images that were successfully decoded. It may be possible to solve the nonlinear least squares problem using other optimization methods such as the variable metric method, the Levenberg-Marquadt method, etc [31

31. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in C++, 2nd ed. (Cambridge, 2005).

]. However, it is unlikely that there will be great improvement using an alternative method since the Gauss-Newton method converged quickly to the minimum. By virtue of the fast convergence, we believe our proposed method is very promising for the real time decoding of bar codes. Moreover, for many bar code images, we think that it might be possible to decode bar codes correctly after only two or three iterations.

Fig. 11. Estimated lengths of patterns by the three methods for the signal in Fig. 7(d): (a) the edge method; (b) the NLS-UI method; (c) the proposed method.
Fig. 12. Estimated nonuniform illuminations for the signals shown in Fig. 7(c) and Fig. 7(d) with different λ values: (a) for the signal shown in Fig. 7(c); (b) for the signal shown in Fig. 7(d).
Fig. 13. Change of the objective functions during iterations for the signals shown in Fig. 7(c) and Fig. 7(d): (a) for the signal shown in Fig. 7(c); (b) for the signal shown in Fig. 7(d).

5. Conclusion

We have proposed a novel joint nonuniform illumination estimation and deblurring method for bar code signals based on a penalized nonlinear squares objective function. Based on the proper parameterization of a bar code signal and illumination as well as a regularization on the illumination using a smoothness penalty, the proposed method is able to simultaneously estimate the bar code signal and illumination in the spatial domain. In the simulations and experiments, the proposed method showed improved performance compared with the edge based method without deblurring and the NLS-UI method without nonuniform illumination correction. In particular, the proposed method was able to decode test bar code images in a few iterations that were not decodable by the two methods. Since blurring and nonuniform illumination are unavoidable in many situations, we believe that the proposed method will be useful for decoding bar code images.

Acknowledgements

The authors are very grateful to Leming Qu from Boise State University, Boise, ID and Yi-Cheng Tu from Purdue University, West Lafayette, IN for providing us with code for initial edge location estimation. The authors are also very grateful to the anonymous reviewer for his/her thorough review of the paper and many insightful suggestions. This work was partly supported by a grant under Brain Korea 21 and by the Dobesys Co.Ltd. in Korea.

References and links

1.

E. Joseph and T. Pavlids, “Deblurring of bilevel waveforms,” IEEE Trans. Image Process. 2, 223–235 (1993). [CrossRef] [PubMed]

2.

E. Joseph and T. Pavlids, “Bar code waveform recognition using peak locations,” IEEE Trans. Pattern Anal. Mach. Intell. 16, 630–640 (1994). [CrossRef]

3.

S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]

4.

E. Marom, S. Krešić-Jurić, and L. Bergstein, “Analysis of speckle noise in bar-code scanning systems,” J. Opt. Soc. Am. A 18, 889–901 (2001). [CrossRef]

5.

E. Marom, S. Krešić-Jurić, and L. Bergstein, “Speckle noise in bar-code scanning systems-power spectral density and SNR,” Appl. Opt. 42, 161–174 (2003). [CrossRef] [PubMed]

6.

S. Krešić-Jurić, “Edge detection in bar code signals corrupted by integrated time-varying speckle,” Pattern Recogn. 38, 2483–2493 (2005). [CrossRef]

7.

L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. 5, 347–355 (2006).

8.

R. C. Palmer, The bar code book: reading, printing and specification of bar code symbols (Helmers Publishing Inc.1999).

9.

J. S. Chen and G. Medioni, “Detection, localization and estimation of edges,” IEEE Trans. Pattern Anal. Mach. Intell. 11, 191–198 (1989). [CrossRef]

10.

M. D. Sanner, “Ambient illumination bar code reader,” U. S. Patent 4,874,933 (1989).

11.

J. Debiez and F. Lerat, “Intelligent light source,” U. S. Patent 6,774,893 B2 (2004).

12.

R. Shams and P. Sadeghi, “Bar code recognition in highly distorted and low resolution images,” in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2007) pp. 737–740.

13.

D. A. Forsyth and J. Ponce, Computer vision: A modern approach (Prentice Hall, 2003).

14.

T. Chen, W. Yin, X. S. Zhou, D. Comaniciu, and T. S. Huang, “Total variation models for variable lighting face recognition,” IEEE Trans. Pattern Anal. Mach. Intell. 28, 1519–1524 (2006). [CrossRef] [PubMed]

15.

D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. 208, 212–223 (2002). [CrossRef] [PubMed]

16.

Z. Hou, “A review on MR image inhomogeneity correction,” Int. J. Biomed. Imag. 2006, 1–11 (2006). [CrossRef]

17.

B. Likar, J. B. A. Maintz, M. A. Viergever, and F. Pernus, “Retrospective shading correction based on entropy minimization,” J. Microsc. 197, 285–295 (2000). [CrossRef] [PubMed]

18.

B. H. Brinkmann, A. Manduca, and R. A. Robb, “Optimized homomorphic unsharp masking for MR grayscale inhomogeneity correction,” IEEE Trans. Med. Imag. 17, 161–171 (1998). [CrossRef]

19.

J. G. Sled, A. P. Zijdenbos, and A. C. Evans, “A nonparametric method for automatic correction of intensity nonuniformity in MRI data,” IEEE Trans. Med. Imag. 17, 87–97 (1998). [CrossRef]

20.

M. S. Brown and Y. C. Tsoi, “Geometric and shading correction for images of printed materials using boundary,” IEEE Trans. Image Process. 15, 1544–1554 (2006). [CrossRef] [PubMed]

21.

M. Unser, “Splines: A perfect fit for signal and image processing,” IEEE Signal Process. Mag. 16, 22–38 (1999). [CrossRef]

22.

D. G. Bailey, “Super-resolution of bar codes,” J. Electron. Imag. 10, 213–220 (2001). [CrossRef]

23.

Y. C. Eldar, A. Ben-Tal, and A. Nemirovski, “Robust mean-squared error estimation in the presence of model uncertainties,” IEEE Trans. Signal Process. 53, 168–181 (2005). [CrossRef]

24.

M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. 100, 145–160 (1999). [CrossRef]

25.

P. E. Gill and W. Murray, “Algorithms for the solution of the nonlinear least-squares problem,” SIAM J. Numer. Anal. 15, 977–992 (1978). [CrossRef]

26.

J. Eriksson, P. A. Wedin, M. E. Gulliksson, and I. Söderkvist, “Regularization methods for uniformly rank-deficient nonlinear least-squares problems,” J. Optim. Theor. Appl. 127, 1–26 (2005). [CrossRef]

27.

E. Kreyszig, Advanced engineering mathematics, 8th ed. (Wiley, 1998).

28.

J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE. Trans. Med. Imag. 13, 290–300 (1997). [CrossRef]

29.

J. Kim, Intensity-based image registration using robust similarity measure and constrained optimization: Applications for radiation therapy, Ph.D. dissertation, The University of Michigan, Ann Arbor, 2004. [PubMed]

30.

P. E. Gill, W. Murray, and M. H. Wright, Practical optimization (Academic Press, 1981).

31.

W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical recipes in C++, 2nd ed. (Cambridge, 2005).

OCIS Codes
(100.3020) Image processing : Image reconstruction-restoration
(100.3190) Image processing : Inverse problems
(150.2950) Machine vision : Illumination
(100.1455) Image processing : Blind deconvolution

ToC Category:
Image Processing

History
Original Manuscript: August 28, 2007
Revised Manuscript: October 16, 2007
Manuscript Accepted: October 22, 2007
Published: October 25, 2007

Citation
Jeongtae Kim and Hana Lee, "Joint nonuniform illumination estimation and deblurring for bar code signals," Opt. Express 15, 14817-14837 (2007)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-22-14817


Sort:  Year  |  Journal  |  Reset  

References

  1. E. Joseph and T. Pavlids, "Deblurring of bilevel waveforms," IEEE Trans. Image Process. 2, 223-235 (1993). [CrossRef] [PubMed]
  2. E. Joseph and T. Pavlids, "Bar code waveform recognition using peak locations," IEEE Trans. Pattern Anal. Mach. Intell. 16, 630-640 (1994). [CrossRef]
  3. S. Esedoglu, "Blind deconvolution of bar code signals," Inverse Probl. 20, 121-135 (2004). [CrossRef]
  4. E. Marom, S. Krešić-Jurić, and L. Bergstein, "Analysis of speckle noise in bar-code scanning systems," J. Opt. Soc. Am. A 18, 889-901 (2001). [CrossRef]
  5. E. Marom, S. Krešić-Jurić, and L. Bergstein, "Speckle noise in bar-code scanning systems-power spectral density and SNR," Appl. Opt. 42, 161-174 (2003). [CrossRef] [PubMed]
  6. S. Krešić-Jurić, "Edge detection in bar code signals corrupted by integrated time-varying speckle," Pattern Recogn. 38, 2483-2493 (2005). [CrossRef]
  7. L. Qu and Y. C. Tu, "Change point estimation of bilevel functions," J. Mod. Appl. Stat. Meth. 5, 347-355 (2006).
  8. R. C. Palmer, The bar code book: reading, printing and specification of bar code symbols (Helmers Publishing Inc. 1999).
  9. J. S. Chen and G. Medioni, "Detection, localization and estimation of edges," IEEE Trans. Pattern Anal. Mach. Intell. 11, 191-198 (1989). [CrossRef]
  10. M. D. Sanner, "Ambient illumination bar code reader," U. S. Patent 4,874,933 (1989).
  11. J. Debiez and F. Lerat, "Intelligent light source," U. S. Patent 6,774,893 B2 (2004).
  12. R. Shams and P. Sadeghi, "Bar code recognition in highly distorted and low resolution images," in Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (IEEE, 2007) pp. 737-740.
  13. D. A. Forsyth and J. Ponce, Computer vision: A modern approach (Prentice Hall, 2003).
  14. T. Chen, W. Yin, X. S. Zhou, D. Comaniciu, and T. S. Huang, "Total variation models for variable lighting face recognition," IEEE Trans. Pattern Anal. Mach. Intell. 28, 1519-1524 (2006). [CrossRef] [PubMed]
  15. D. Tomazevic, B. Likar, and F. Pernus, "Comparative evaluation of retrospective shading correction methods," J. Microsc. 208, 212-223 (2002). [CrossRef] [PubMed]
  16. Z. Hou, "A review on MR image inhomogeneity correction," Int. J. Biomed. Imaging 2006, 1-11 (2006). [CrossRef]
  17. B. Likar, J. B. A. Maintz, M. A. Viergever, and F. Pernus, "Retrospective shading correction based on entropy minimization," J. Microsc. 197, 285-295 (2000). [CrossRef] [PubMed]
  18. B. H. Brinkmann, A. Manduca, and R. A. Robb, "Optimized homomorphic unsharp masking for MR grayscale inhomogeneity correction," IEEE Trans. Med. Imag. 17, 161-171 (1998). [CrossRef]
  19. J. G. Sled, A. P. Zijdenbos, and A. C. Evans, "A nonparametric method for automatic correction of intensity nonuniformity in MRI data," IEEE Trans. Med. Imag. 17, 87-97 (1998). [CrossRef]
  20. M. S. Brown and Y. C. Tsoi, "Geometric and shading correction for images of printed materials using boundary," IEEE Trans. Image Process. 15, 1544-1554 (2006). [CrossRef] [PubMed]
  21. M. Unser, "Splines: A perfect fit for signal and image processing," IEEE Signal Process. Mag. 16, 22-38 (1999). [CrossRef]
  22. D. G. Bailey, "Super-resolution of bar codes," J. Electron. Imag. 10, 213-220 (2001). [CrossRef]
  23. Y. C. Eldar, A. Ben-Tal, and A. Nemirovski, "Robust mean-squared error estimation in the presence of model uncertainties," IEEE Trans. Signal Process. 53, 168-181 (2005). [CrossRef]
  24. M. Gulliksson, "KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints," J. Optim. Theor. Appl. 100, 145-160 (1999). [CrossRef]
  25. P. E. Gill and W. Murray, "Algorithms for the solution of the nonlinear least-squares problem," SIAM J. Numer. Anal. 15, 977-992 (1978). [CrossRef]
  26. J. Eriksson, P. A. Wedin, M. E. Gulliksson, and I. Soderkvist, "Regularization methods for uniformly rankdeficient nonlinear least-squares problems," J. Optim. Theor. Appl. 127, 1-26 (2005). [CrossRef]
  27. E. Kreyszig, Advanced Engineering Mathematics, 8th ed. (Wiley, 1998).
  28. J. A. Fessler, "Penalized weighted least-squares image reconstruction for positron emission tomography," IEEE.Trans. Med. Imag. 13, 290-300 (1997). [CrossRef]
  29. J. Kim, Intensity-based image registration using robust similarity measure and constrained optimization: Applications for radiation therapy, Ph.D. dissertation, The University of Michigan, Ann Arbor, 2004. [PubMed]
  30. P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization (Academic Press, 1981).
  31. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C++, 2nd ed. (Cambridge, 2005).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited