## Joint nonuniform illumination estimation and deblurring for bar code signals

Optics Express, Vol. 15, Issue 22, pp. 14817-14837 (2007)

http://dx.doi.org/10.1364/OE.15.014817

Acrobat PDF (1464 KB)

### 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

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

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

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]

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

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

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

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

**20**, 121–135 (2004). [CrossRef]

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]

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

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]

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

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]

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

15. D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. **208**, 212–223 (2002). [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]

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]

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]

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

*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

*t*denotes one-dimensional (1D) spatial location, ∗ denotes the convolution operator,

*I*(

*t*),

*G*(

*t*) and

*x*(

*t*) denote

*unknown*illumination, blurring kernel, and

*clean*bar code signal, respectively,

*c*> 0 denotes

*unknown*constant background and

*n*(

*t*) denotes additive noise. Estimation of

*I*(

*t*),

*G*(

*t*),

*x*(

*t*) and

*c*from

*y*(

*t*) is an ill-posed problem since the problem is underdetermined, and thus its solution is not unique [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]

*K*, in a bar code signal is known. Based on the assumption, we parameterize a

*clean*bar code signal as follows:

**e**= [

*e*

_{1},

*e*

_{2},...,

*e*] denotes the locations of edges such that

_{K}*e*

_{i+1}>

*e*, and

_{i}*u*(

*t*) is the unit step function. We also parameterize the blurring kernel using the Gaussian function with

*unknown*standard deviation

*σ*> 0 as follows:

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

**2**, 223–235 (1993). [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]

*β*

^{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

*l*,

_{j}*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]

**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

*θ*= [

*θ*

_{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*(

*t*),

_{i}*i*= 1,...,

*M*subject to the constraints such as

*e*<

_{i}*e*

_{i+1},

*σ*> 0,

*c*> 0 and

*b*> 0. To solve the problem, one effective approach is determining a parameter vector

_{j}*θ*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:*θ ^

*F*(

*θ*) is defined as

*f*(θ) is the sampled residual defined as

_{i}*t*denotes the sample locations, and [

_{i}*G*(

*t*;

_{i}*σ*)∗

*x*(

*t*;

_{i}**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]

*F*(

*θ*) as follows:

*f*(

*θ*) = [

*f*

_{1}(

*θ*),...,

*f*(

_{M}*θ*)]

^{T}and the Jacobian matrix

*J*(

*θ*) ∊ ℝ

^{M×N}of

*f*(

*θ*) is defined as follows:

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

_{θ}

^{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]

*i*,

*j*)

^{th}element of the Hessian matrix is defined as follows:

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]

*regularization*based on

*a priori*information about the solution is required [24

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

*I*(

*t*;

_{i}**b**

_{1}) and

*I*(

*t*;

_{i}**b**

_{2}) that have the same shapes as the blurred bar code signal [

*G*(

*t*;

_{i}*σ*

_{2})∗

*x*(

*t*;

_{i}**e**

_{2})+

*c*

_{2})] and [

*G*(

*t*;

*σ*

_{1})∗

*x*(

*t*;

_{i}**e**

_{1})+

*c*

_{1})], respectively, such that:

**h**∊ ℝ

^{1×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:

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

*i.e*., the problem of estimating

*θ*= [

_{s}**e**, σ,

*c*,

*b*]

^{T}∊ ℝ

^{K+3}, where

*b*> 0. For this model, all the B-spline coefficients

*b*,

_{j}*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*(

*t*) ∊ {0,1},

_{i}*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*(

*t*) having a bounded total variation from

_{i}*y*(

*t*) is well-posed with some constraints such that σ > 0 and

_{i}*b*∊

*P*, where

*P*is a compact subset of positive real numbers [3

**20**, 121–135 (2004). [CrossRef]

**20**, 121–135 (2004). [CrossRef]

*in a neighborhood of the minimizer is positive definite,*θ ˜

_{s}*i.e*., for all

*θ*∊ ℝ

_{s}^{K+3}, the following inequality holds:

*J*(

_{s}*θ*) ∊ ℝ

_{s}^{M×(K+3)}is the Jacobian matrix of

*f*(

*θ*) = [

_{s}*f*

_{1}(θ

_{s}), ...,

*f*(

_{M}*θ*)]

_{s}^{T}.

*θ*= [

_{u}**e**,

*σ*,

*c*,

**b**]

_{u}^{T}∊ ℝ

^{N}and

*= [*θ ˜

_{u}**e**̃,

*,*σ ˜

*c̃*,

**b̃**]

_{u}^{T}∊ ℝ

^{N}are the extended vectors of

*θ*and

_{s}*using*θ ˜

_{s}**b**= [

_{u}*b*,..,

*b*] ∊ ℝ

^{L}and

**b̃**= [

_{u}*b̃*,..,

*b̃*] ∊ ℝ

^{L}, respectively. Furthermore,since

*∂f*(

_{i}*θ*)/

*∂b*is not a function of

_{j}*b*, it is straightforward to show the following equality:

_{j}*= [*θ ˜

**e**̃,

*,*σ ˜

*c̃*,

**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:

*θ*(

^{T}J*)*θ ˜

^{T}

*J*(

*)*θ ˜

*θ*> 0 is required. To overcome the problem, we design a new objective function that includes a regularizing penalty function:

*λ*> 0 is a regularization parameter and the roughness penalty function

*R*(∙) is defined as follows:

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

*α*> 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]

*λ*controls the trade-off between the fidelity to the observed data and the smoothness of the illumination.

*in a neighborhood of the minimizer, the Hessian matrix of the objective function Φ(*θ ˜

*θ*) in Eq. (18) is well approximated as follows:

*θ*that has uniform B-spline coefficients,

*θ*(

^{T}J*)*θ ˜

*(*

^{T}J*)*θ ˜

*θ*> 0 by Eq. (17) while

*λθ*

^{T}**R**

*θ*= 0, and for

*θ*whose B-spline coefficients are not uniform,

*λθ*

^{T}**R**

*θ*> 0 even if

*θ*(

^{T}J*)*θ ˜

*(*

^{T}J*)*θ ˜

*θ*= 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]

*θ*} as follows:

_{k}*H*(

*θ*) =

_{k}*J*(

*θ*)

_{k}*(*

^{T}J*θ*)+

_{k}*λ*

**R**.

*σ*> 0,

*e*

_{i+1}>

*e*,

_{i}*i*= 1,..,

*K*,

*c*> 1 and

*b*>0,

_{j}*j*= 1,..,

*L*, one must solve the constrained nonlinear least squares problem. To do this, we have incorporated active set strategy [30] 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

*σ*using the distance from the last local maxima to the last local minima in the spatial domain, as described in the previous investigations [1

**2**, 223–235 (1993). [CrossRef] [PubMed]

*σ*were very small, the initial illumination estimate would be close to the true illumination. We also initialize the constant background

*c*by dividing the minimum of the observed signal by the estimated magnitude of illumination.

## 3. Results

### 3.1. Simulations

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

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

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

_{1},

_{2},...,

_{K-1}], whose elements are defined as follows:

*t̂*is the location of each estimated edge. If the elements of

_{i}_{i1}<

_{i2}<

_{i3}<

_{i4}, where

*i*1,

*i*2,

*i*3, and

*i*4 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.

_{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

*t*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

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

*σ*/

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

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

*λ*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.

*λ*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.

*λ*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

*λ*= 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.

*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*

*correct*

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

_{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.

*λ*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

**100**, 145–160 (1999). [CrossRef]

*λ*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.

*λ*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

**100**, 145–160 (1999). [CrossRef]

## 4. Discussion

**208**, 212–223 (2002). [CrossRef] [PubMed]

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]

**20**, 121–135 (2004). [CrossRef]

*λ*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.

*σ*, 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]. 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.

## 5. Conclusion

## Acknowledgements

## References and links

1. | E. Joseph and T. Pavlids, “Deblurring of bilevel waveforms,” IEEE Trans. Image Process. |

2. | E. Joseph and T. Pavlids, “Bar code waveform recognition using peak locations,” IEEE Trans. Pattern Anal. Mach. Intell. |

3. | S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. |

4. | E. Marom, S. Krešić-Jurić, and L. Bergstein, “Analysis of speckle noise in bar-code scanning systems,” J. Opt. Soc. Am. A |

5. | E. Marom, S. Krešić-Jurić, and L. Bergstein, “Speckle noise in bar-code scanning systems-power spectral density and SNR,” Appl. Opt. |

6. | S. Krešić-Jurić, “Edge detection in bar code signals corrupted by integrated time-varying speckle,” Pattern Recogn. |

7. | L. Qu and Y. C. Tu, “Change point estimation of bilevel functions,” J. Mod. Appl. Stat. Meth. |

8. | R. C. Palmer, |

9. | J. S. Chen and G. Medioni, “Detection, localization and estimation of edges,” IEEE Trans. Pattern Anal. Mach. Intell. |

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

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

15. | D. Tomazevic, B. Likar, and F. Pernus, “Comparative evaluation of retrospective shading correction methods,” J. Microsc. |

16. | Z. Hou, “A review on MR image inhomogeneity correction,” Int. J. Biomed. Imag. |

17. | B. Likar, J. B. A. Maintz, M. A. Viergever, and F. Pernus, “Retrospective shading correction based on entropy minimization,” J. Microsc. |

18. | B. H. Brinkmann, A. Manduca, and R. A. Robb, “Optimized homomorphic unsharp masking for MR grayscale inhomogeneity correction,” IEEE Trans. Med. Imag. |

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

20. | M. S. Brown and Y. C. Tsoi, “Geometric and shading correction for images of printed materials using boundary,” IEEE Trans. Image Process. |

21. | M. Unser, “Splines: A perfect fit for signal and image processing,” IEEE Signal Process. Mag. |

22. | D. G. Bailey, “Super-resolution of bar codes,” J. Electron. Imag. |

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

24. | M. Gulliksson, “KKT conditions for rank-deficient nonlinear least-squares problems with rank-deficient nonlinear constraints,” J. Optim. Theor. Appl. |

25. | P. E. Gill and W. Murray, “Algorithms for the solution of the nonlinear least-squares problem,” SIAM J. Numer. Anal. |

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

27. | E. Kreyszig, |

28. | J. A. Fessler, “Penalized weighted least-squares image reconstruction for positron emission tomography,” IEEE. Trans. Med. Imag. |

29. | J. Kim, |

30. | P. E. Gill, W. Murray, and M. H. Wright, |

31. | W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, |

**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

- E. Joseph and T. Pavlids, "Deblurring of bilevel waveforms," IEEE Trans. Image Process. 2, 223-235 (1993). [CrossRef] [PubMed]
- E. Joseph and T. Pavlids, "Bar code waveform recognition using peak locations," IEEE Trans. Pattern Anal. Mach. Intell. 16, 630-640 (1994). [CrossRef]
- S. Esedoglu, "Blind deconvolution of bar code signals," Inverse Probl. 20, 121-135 (2004). [CrossRef]
- 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]
- 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]
- S. Krešić-Jurić, "Edge detection in bar code signals corrupted by integrated time-varying speckle," Pattern Recogn. 38, 2483-2493 (2005). [CrossRef]
- L. Qu and Y. C. Tu, "Change point estimation of bilevel functions," J. Mod. Appl. Stat. Meth. 5, 347-355 (2006).
- R. C. Palmer, The bar code book: reading, printing and specification of bar code symbols (Helmers Publishing Inc. 1999).
- J. S. Chen and G. Medioni, "Detection, localization and estimation of edges," IEEE Trans. Pattern Anal. Mach. Intell. 11, 191-198 (1989). [CrossRef]
- M. D. Sanner, "Ambient illumination bar code reader," U. S. Patent 4,874,933 (1989).
- J. Debiez and F. Lerat, "Intelligent light source," U. S. Patent 6,774,893 B2 (2004).
- 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.
- D. A. Forsyth and J. Ponce, Computer vision: A modern approach (Prentice Hall, 2003).
- 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]
- D. Tomazevic, B. Likar, and F. Pernus, "Comparative evaluation of retrospective shading correction methods," J. Microsc. 208, 212-223 (2002). [CrossRef] [PubMed]
- Z. Hou, "A review on MR image inhomogeneity correction," Int. J. Biomed. Imaging 2006, 1-11 (2006). [CrossRef]
- 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]
- 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]
- 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]
- 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]
- M. Unser, "Splines: A perfect fit for signal and image processing," IEEE Signal Process. Mag. 16, 22-38 (1999). [CrossRef]
- D. G. Bailey, "Super-resolution of bar codes," J. Electron. Imag. 10, 213-220 (2001). [CrossRef]
- 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]
- 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]
- 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]
- 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]
- E. Kreyszig, Advanced Engineering Mathematics, 8th ed. (Wiley, 1998).
- J. A. Fessler, "Penalized weighted least-squares image reconstruction for positron emission tomography," IEEE.Trans. Med. Imag. 13, 290-300 (1997). [CrossRef]
- 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]
- P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization (Academic Press, 1981).
- 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.

### Figures

Fig. 1. |
Fig. 2. |
Fig. 3. |

Fig. 4. |
Fig. 5. |
Fig. 6. |

Fig. 7. |
Fig. 8. |
Fig. 9. |

Fig. 10. |
Fig. 11. |
Fig. 12. |

Fig. 13. |
||

« Previous Article | Next Article »

OSA is a member of CrossRef.