High order statistics based blind
deconvolution of bi-level images with
unknown intensity values

doi:10.1364/OE.18.012872

« Show journal navigation

High order statistics based blind deconvolution of bi-level images with unknown intensity values

Jeongtae Kim and Soohyun Jang »View Author Affiliations

Optics Express, Vol. 18, Issue 12, pp. 12872-12889 (2010)
http://dx.doi.org/10.1364/OE.18.012872

View Full Text Article

Acrobat PDF (2264 KB)

Journal Search
Article Lookup

Article Tools

Citations

Alert me when this article is cited
Export Citation/Save

Full Text
Article Info
References (25)
Cited By
Figures (6)
Metrics

Abstract

We propose a novel linear blind deconvolution method for bi-level images. The proposed method seeks an optimal point spread function and two parameters that maximize a high order statistics based objective function. Unlike existing minimum entropy deconvolution and least squares minimization methods, the proposed method requires neither unrealistic assumption that the pixel values of a bi-level image are independently identically distributed samples of a random variable nor tuning of regularization parameters. We demonstrate the effectiveness of the proposed method in simulations and experiments.

1. Introduction

Images acquired from imaging devices are often blurred due to out-of-focus, motion of imaging devices and/or objects, etc. Since a blurred image can be modeled by the convolution of a true image and a point spread function (PSF), deconvolution using the PSF is necessary to restore the true image from the blurred acquired image. If the PSF is not known, the deconvolution becomes more challenging blind deconvolution. Since point spread functions are not completely known in many deconvolution problems, blind deconvolution has been studied intensively. Existing blind deconvolution methods include maximum likelihood type methods [1–5

T. J. Holmes, “Blind deconvolution of quantum-limited incorehent imagery:maximum-likelihood approach,” J. Opt. Soc. Am. A 9, 1052–1061 (1992). [CrossRef] [PubMed]

], linear filtering methods [6–10

D. Kundur and D. Hatzinakos, “A novel blind deconvolution scheme for image restoration using recursive filtering,” IEEE Trans. Signal Process. 45, 375–390 (1998). [CrossRef]

], etc. See excellent review articles for the details of the existing methods [11–13

D. Kundur and D. Hatzinakos, “Blind image deconvolution,” IEEE Trans. Image Process. 2, 223–235 (1993).

In our point of view, blind deconvolution methods may be classified into two categories. One includes linear methods that attempt to restore true image by some linear filtering of the acquired image. Such methods often iteratively determine the linear filter by maximizing an objective function based on the a prori information about the true image such as support size [6

D. Kundur and D. Hatzinakos, “A novel blind deconvolution scheme for image restoration using recursive filtering,” IEEE Trans. Signal Process. 45, 375–390 (1998). [CrossRef]

] and pixel intensity values [7–9

G. R. Ayers and J. C. Dainty, ‘Iterative blind deconvolution method and its application,” Opt. Lett. 13, 547–549 (1998). [CrossRef]

]. The other category includes nonlinear methods that seek both an image and a PSF that maximize some objective function such as a likelihood function [1–5

T. J. Holmes, “Blind deconvolution of quantum-limited incorehent imagery:maximum-likelihood approach,” J. Opt. Soc. Am. A 9, 1052–1061 (1992). [CrossRef] [PubMed]

]. Since the maximization problem is a well known ill-posed problem in the sense that the solution is not unique (interchanging the PSF and the image would yield the same likelihood value), one is required to incorporate a priori information about the PSF and/or true image to regularize a solution. One of the most widely used regularizing methods is adding a penalty function based on the a priori information to the objective function. Since both the linear and nonlinear methods rely on the a priori information about true image and/or true PSF heavily, an effective incorporation of the information is crucial for successful blind deconvolution.

In this article, we investigate a blind deconvolution method for images that have only two intensity values (bi-level image) such as barcode, text and license plates that are found in many engineering applications [10

N. Miura, N. Baba, S. Isobe, M. Noguchi, and Y. Norimoto, “Binary star reconstruction with use of the blind deconvolution method,” J. Mod. Opt. 39, 1137–1146 (1992). [CrossRef]

,14

H. Lee and J. Kim, “Retrospective correction of nonuniform illumination on bi-level images,” Opt. Express 15, 23880–23893 (2009). [CrossRef]

,15

Y. Shen, E. Y. Lam, and N. Wong, “Binary image restoration by positive semidefinite programming,” Opt. Lett. 32, 121–123 (2007). [CrossRef]

]. There have been several investigations on the blind deconvolution of bi-level images based on the a priori information that true image has only two intensity values. For example, there have been nonlinear methods such as total variation and double-well function based regularization method [3

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

], iterated quadratic programming method [4

E. Y. Lam, “Blind bi-level image restoration with iterated quadratic programming,” IEEE Trans. Circ. Syst. Part 2 52, 52–56 (2007). [CrossRef]

] and parameterized model based method [5

J. Kim and H. Lee, “Joint nonuniform illumination estimation and deblurring for bar code signals,” Opt. Express 17, 14817–14837 (2007). [CrossRef]

]. In addition, linear filtering methods using three step iteration algorithm (TSIA) [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

] and minimum entropy method (MED) [9

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

] have been studied. The existing methods have their own drawbacks. For example, the total variation and double-well function based method [3

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

] and iterated quadratic programming based method [4

E. Y. Lam, “Blind bi-level image restoration with iterated quadratic programming,” IEEE Trans. Circ. Syst. Part 2 52, 52–56 (2007). [CrossRef]

] assume that two intensity values are known, which is unrealistic in practice. In addition, the method in [3

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

] requires tuning of two regularization parameters, which is difficult to automate. Another nonlinear method based on the parameterized barcode model can be applied only for 1D barcode images [5

J. Kim and H. Lee, “Joint nonuniform illumination estimation and deblurring for bar code signals,” Opt. Express 17, 14817–14837 (2007). [CrossRef]

]. The existing linear methods also have drawbacks such as slow convergence [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

] and noise sensitivity [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

, 9

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

To overcome the drawbacks of the existing methods, we study a novel linear method for the blind deconvolution of bi-level images. We focus on the linear method since it has advantages of not requiring tuning of regularization parameters. Typically, the nonlinear methods require two regularization parameters (one for regularzation function for image, the other for PSF) and the performance of the methods greatly depends on the selection of the regularization parameters. Moreover, the automatic tuning of the parameters is challenging since the selection of the regularization parameters should depend on an acquired image and unknown true PSF. In addition, to our knowledge, there have been no nonlinear blind deconvolution method for bi-level images with two unknown intensity values.

Linear deconvolution methods for bi-level images often use high order statistics as an objective function to determine an optimal filter since the second order statistics is not able to measure the binariness of an image [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

,12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

]. High order statistics such as cumulants have been widely used [9

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

,12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

] for the deconvolution of independently and identically distributed (i.i.d.) images (no correlation between pixel values) regardless of whether true images are binary or not. The method, also known as minimum entropy deconvolution (MED) method, has a theoretical basis that the magnitude of a normalized cumulant of a linear combination of a random variable (RV) is always smaller than that of the RV. By virtue of that, one can expect that the sample estimation of the normalized cumulant is maximized when the blur (i.e. linear combination) is removed [12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

]. Since the sample estimation of the fourth order normalized cumulant (often called kurtosis, which is one of the most widely used normalized cumulants for blind deconvolution) reaches upper bound when deconvolved signal has all zeros but one nonzero value, the method is also known as a method that seeks “simple or sporadic structure” signal [17

D. Donoho, “On minimum entropy deconvolution,” Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).

]. Although the method can be used effectively for signals that have zero (or small) correlation such geophysical signals [12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

, 16

M. D. Sacchi, D. R. Velis, and A. H. Comingues, “Minimum entropy deconvolution with frequency-domain constraints,” Geophysics 59, 938–945 (1994). [CrossRef]

, 17

D. Donoho, “On minimum entropy deconvolution,” Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).

], the performance is limited for the deconvolution of an image since true image has neither zero correlation nor “simple or sporadic structure” in general.

To apply the principle of the MED method for the deconvolution of a bi-level image, a method that maximizes the sample fourth order normalized cumulant of the horizontal and vertical differences of an acquired image was investigated [9

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

]. The method is based on the assumption that the horizontal and vertical differences in true bi-level image have more “sporadic or simple structure” than that of a blurred image. We call this method difference MED (DMED) method to discriminate it from the usual MED method. Although the method is intuitively plausible, it has several drawbacks. Firstly, it is not guaranteed that the sample kurtosis of the difference image is maximized when the deconvolved image is bi-level since the horizontal and vertical differences of a bi-level image are not i.i.d. realizations of a RV. Therefore, there might exist a filter whose output is significantly different from a bi-level image but has higher kurtosis than that of the bi-level image. In addition, the DMED method may amplify the effect of noise due to the differencing operations. To overcome the drawbacks of the DMED method, a method that minimizes a high order statistics based objective function using three step iteration approach was investigated [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

]. However, the method is slow [4

E. Y. Lam, “Blind bi-level image restoration with iterated quadratic programming,” IEEE Trans. Circ. Syst. Part 2 52, 52–56 (2007). [CrossRef]

] and sensitive to noise [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

To overcome the drawbacks of the existing methods, we investigate a novel method whose objective function is minimized when deconvolved image is bi-level. The method searches a Wiener-like filter (known to be more robust to noise [7

G. R. Ayers and J. C. Dainty, ‘Iterative blind deconvolution method and its application,” Opt. Lett. 13, 547–549 (1998). [CrossRef]

]) and the mid-level of two unknown intensity values during the optimization of a high order statistics based objective function. Unlike the DMED method, the proposed method neither assume that the pixels of true image (or difference image) are i.i.d. realizations of a RV nor compute differences of an acquired image. By virtue of that, we expect that the performance of the proposed method should be better than that of the DMED method.

2. Problem formulation

We model an M×N image acquired from an imaging device by the convolution of true image and true PSF plus additive noise as follows:

y (m, n) = \underset{j}{Σ} \underset{k}{Σ} h (n - j, m - k) x (j, k) + w (m, n), m = 1, . . . M, n = 1, . . ., N,

(1)

where y(m,n), h(m,n), x(m,n) and w(m,n) represent blurred acquired image, true PSF, true image and additive noise, respectively. The pixel value of true image at each discrete grid has one of two unknown intensity values β₁ and β₂ such that x(m,n) ∈ {β₁, β₂}. The goal of blind deconvolution is the accurate estimation of the true image x = [x(1,1), x(1,2), ...., x(M,N)] from y = [y(1,1), y(1,2), ...., y(M,N)] without knowledge of h = [h(1,1), h(1,2), ...., h(M,N)]. To achieve the goal, perhaps, the most natural approach is the following penalized nonlinear maximum likelihood type method:

(\hat{x}, \hat{h}) = \underset{x \in {β_{1}, β_{2}}, h}{argmin} - L (x, h; y) + λ_{1} R_{1} (x) + λ_{2} R_{2} (h),

(2)

where L(·, ·) is the likelihood function, R₁(x) and R₂(h) are regularization functions for image x and PSF h, λ₁ and λ₂ are associated regularization parameters, respectively. Note that solving the problem defined in Eq. (2) is very difficult since it requires a binary optimization with two unknown binary values. In addition, automatic tuning of the two regularization parameters is also challenging. To our knowledge, no method has been proposed to solve the problem defined in Eq. (2), although there exists a method based on Eq. (2) for the case that two intensity values are known [3

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

]. However, the method is not applicable in practice since the two intensity values are not known in general.

As an alternative, one may apply the least squares minimization (LSM) method based on the Gaussian likelihood function without binary optimization [18

N. F. Law and R. G. Lane, “Blind deconvolution using least squares minimisation,” Opt. Commun. 128, 341–352 (1996). [CrossRef]

]. The method is based on the Gaussian likelihood and two regularization functions as follows:

(\hat{x}, \hat{h}) = \underset{x, h}{argmin} \underset{n, m}{Σ} {∣ y (n, m) - h (n, m) * x (n, m) ∣}^{2} + λ_{1} R_{1} (x) + λ_{2} R_{2} (h),

(3)

where * is the 2D convolution operator. One of the most widely used regularization functions is a smoothness penalty function defined as follows:

R_{1} (x) = \underset{n, m}{Σ} {(x (n + 1, m) - 2 x (n, m) + x (n - 1, m))}^{2} + {(x (n, m + 1) - 2 x (n, m) + x (n - 1, m - 1))}^{2}

R_{2} (h) = \underset{n, m}{Σ} {(h (n + 1, m) - 2 h (n, m) + h (n - 1, m))}^{2} + {(h (n, m + 1) - 2 h (n, m) + h (n - 1, m - 1))}^{2}

(4)

Note that the method defined in Eq. (3) does not require binary optimization. However, the method still suffers from cumbersome tuning of the two regularization parameters. In addition, regularization function such as the smoothness penalty is not based on the a priori information that true image is bi-level image. To our knowledge, effective regularization functions specialized for bi-level images with two unknown intensity values have not been investigated yet.

Unlike the nonlinear method in Eq. (2), linear methods attempt to restore the true image by determining an optimal filter that maximizes an objective function as follows:

\hat{f} = \underset{f}{argmax} Φ_{z} (f; y),

(5)

where Φ_z(·) is some objective function that measures the degree of binariness of the filtered image z defined as follows:

z (m, n; f) = \underset{j}{Σ} \underset{k}{Σ} f (m - j, n - k) y (j, k), m = 1, . . . M, n = 1, . . ., N,

(6)

where f = [f(1,1), f(1,2), ⋯, f(M,N)] are the coefficients of a linear filter. In other words, the method seeks a filter whose output image is the most consistent with the a priori information that the true image has only two intensity values. Often it is assumed that the PSF h(m,n) in Eq. (1) has stable inverse filter f(m,n) such that f(m,n)**h(m,n) = δ(m−m_o,n−n_o), where m_o and n_o are some shifts in the spatial domain. Clearly, the assumption is not always valid since many PSFs (such as PSF for out-of-focus blur, motion blur) do not have stable inverse. Even if the PSF is invertible, the method still suffers from amplifying the noise since the inverse filter is a high pass filter in nature. Nevertheless, several researchers have reported that the methods perform well under modest noise levels [6–9

D. Kundur and D. Hatzinakos, “A novel blind deconvolution scheme for image restoration using recursive filtering,” IEEE Trans. Signal Process. 45, 375–390 (1998). [CrossRef]

]. Note that for most cases, the linear filtering methods do not require regularization functions.

3. MED based methods

The MED method determines an optimal filter by maximizing the following objective function [17

D. Donoho, “On minimum entropy deconvolution,” Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).

\hat{f} = \underset{f}{argmax} \frac{\frac{1}{MN} Σ_{m, n} {(z (m, n; f))}^{4}}{{(\frac{1}{MN} Σ_{m, n} {(z (m, n; f))}^{2})}^{2}} .

(7)

The objective function defined in Eq. (7) can be thought as the sample estimation of the fourth order normalized cumulant (kurtosis) of a zero mean random variable (RV) Z (except for correction term -3 for making the kurtosis of a Gaussian RV zero [12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

]), provided that z(m,n; f), m = 1, …M, n = 1, …N are i.i.d. samples of Z. The objective function reaches the maximum value MN when the signal z(m,n; f) has all zero values but only one nonzero value. Due to that, the MED method is known as a method that seeks “simple or sporadic structure” in deconvolved signal [17

D. Donoho, “On minimum entropy deconvolution,” Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).

]. The MED method has been effectively used for the deconvolution of geophysical signals such as seismic signals, mainly due to that ideal geophysical signals have most zero values but small numbers of spikes [16

M. D. Sacchi, D. R. Velis, and A. H. Comingues, “Minimum entropy deconvolution with frequency-domain constraints,” Geophysics 59, 938–945 (1994). [CrossRef]

, 17

D. Donoho, “On minimum entropy deconvolution,” Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).

In addition to the previous justification, it has been known that the magnitude of the normalized cumulant of a linear combination of a RV is always smaller than that of the RV [12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

]. Based on the fact, if the pixel intensity values of true image are i.i.d. samples of a RV, ideal inverse filter (which restores the i.i.d. sample values) would yield maximum magnitude of the normalized cumulants.

However, it is difficult to apply the method for the deconvolution of images since adjacent pixels in true image have non-negligible correlation. In addition, it is clear that seeking “simple or sporadic structure” in deconvolved image is not a good strategy in general. To avoid the difficulty, based on the observation that differences between adjacent pixels of true bi-level image might be more “sporadic (or spiky)” than that of the blurred image, the DMED method seeks a filter that maximizes the sample kurtosis of horizontal and vertical differences [9

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

]. The DMED method is defined as follows:

\hat{f} = \underset{f}{argmax} \underset{n}{Σ} \frac{Σ_{m} d_{x}^{4} (m, n; f)}{{(Σ_{m} d_{x}^{2} (m, n; f))}^{2}} + \underset{m}{Σ} \frac{Σ_{n} d_{y}^{4} (m, n; f)}{{(Σ_{n} d_{y}^{2} (m, n; f))}^{2}},

(8)

where d_x(m,n; f) = z(m,n; f)−z(m−1, n; f) and d_y(m,n; f) = z(m,n; f)−z(m,n−1; f).

Although the method is plausible, it has two drawbacks. Firstly, since the pixel values of the difference image are not i.i.d. realizations of a RV even for a noise free image, there might exist a filter whose output difference image is very “sporadic” but far from the difference of a bi-level image. Therefore maximizing the objective function defined in Eq. (8) might yield unrealistic image. Secondly, due to difference operation, it may amplify the effect of noises. Due to that, the method was only tested for noise free image in the previous investigation [9

H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]

4. Proposed method

To overcome the drawbacks of the MED based methods in applying for blind deconvolution of bi-level images, we propose a novel linear filtering method based on the normalized cumulants. We pay attention to the following fact. If a deconvolved image using a linear filter f̃ is an ideal bi-level image, there exists a constant ᾶ (which is the mid-level of two levels) that satisfies the following relationship:

∣ z (n, m; \tilde{f}) - \tilde{α} ∣ = k, \forall (m, n),

(9)

where k is some constant. Based on the fact, we design an objective function with variables f and α that is minimized at f = f̃ and α = ᾶ. To do that, we consider the following high order statistics based objective function with variables f and α:

Φ (f, α) = \frac{\frac{1}{MN} Σ_{m, n} {(z (m, n; f) - α)}^{4}}{{(\frac{1}{MN} Σ_{m, n} {(z (m, n; f) - α)}^{2})}^{2}} .

(10)

The objective function in Eq. (10) reaches its lowest bound at f = f̃ and α = ᾶ that satisfy the condition in Eq. (9) [12

J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]

]. (The proof is a simple application of Hölder’s inequality.) Note that the objective function in Eq. (10) is minimized at f = f̃ and α = ᾶ regardless of whether true bi-level image is an i.i.d. image or not. The condition in Eq. (9) can be satisfied when the deconvolved image is a bi-level image or a constant image. Since a constant image might be generated when all filter coefficients are zero, we normalize filter coefficients in a way such that the sum of the coefficients should be unity to prevent such trivial minimizer from occurring [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

Although one may effectively restore true bi-level image by minimizing the objective function defined in Eq. (10) for the cases of invertible PSF and noise free image, the performance of such method might deteriorate since neither PSF is invertible, nor is noise power negligible in general. We attempt to improve the performance of the method by adopting Wiener-like filter that is known to be robust to noise [11

D. Kundur and D. Hatzinakos, “Blind image deconvolution,” IEEE Trans. Image Process. 2, 223–235 (1993).

, 19

J. Kim, “Restoration of bi-level images via iterative semi-blind Wiener filtering,” Trans. KIEE 57, 1290–1294 (2008).

]. The Wiener filter is the well known linear least squares error (LLSE) filter [20

H. L. Van Trees, Detection, estimation, and modulation theory, Part 1 (Wiley, 1968).

] (provided that the PSF and power spectrums of the signals and noises are known) regardless of whether the PSF is invertible or not. If the power spectrums are unknown, the pseudo Wiener filter using noise-to-signal ratio (NSR) is often used [21

R. C. Gonzalez, R. E. Woods, and S. L. Eddins, Digital image processing using MATLAB , (Prentice Hall, New York, 2002).

]. We adopt the pseudo Wiener filter that generates filtered image as follows [19

J. Kim, “Restoration of bi-level images via iterative semi-blind Wiener filtering,” Trans. KIEE 57, 1290–1294 (2008).

z (m, n; h, η) = ℱ^{- 1} {\frac{H^{*} (ω_{x}, ω_{y})}{{∣ H (ω_{x}, ω_{y}) ∣}^{2} + η} Y (ω_{x}, ω_{y})},

(11)

where ℱ⁻¹{·} is the 2D inverse Fourier transform operator, H(ω_x,ω_y) is the Fourier transform of PSF h, and η is the NSR. Since both the PSF and NSR are unknown, we search the PSF h and NSR η that minimize the objective function defined in Eq. (10). Note that we allow negative pixel values in restored images since ultimate goal of blind deconvolution of bi-level images is an accurate estimation of the bi-level images after binarization. Negative pixel values do not affect the performance of the binarization and were allowed in a previous investigation on bi-level image restoration [4

E. Y. Lam, “Blind bi-level image restoration with iterated quadratic programming,” IEEE Trans. Circ. Syst. Part 2 52, 52–56 (2007). [CrossRef]

In summary, using the objective function defined in Eq.(10) and filtered image defined in Eq. (11), we search the PSF h, unknown mid-level α and NSR η. Further, we limit search space by incorporating additional information about the mid-level of true bi-level image and the range of η. It would be reasonable to assume that the mid-level is between the maximum and the minimum of the observed image and signal-to-noise ratio is in some range (e.g.,between 10dB and 100dB). Incorporating such information would be helpful to determine a more realistic solution. Finally, the propose method is defined as follows:

(\hat{h}, \hat{α}, \hat{η}) = \underset{h, α_{1} \leq α \leq α_{2}, η_{1} \leq η \leq η_{2}}{argmin} Φ_{z} (h, α, η),

(12)

where α₁, α₂ and η₁, η₂ are the lower and upper bounds for α and η, respectively, and Φ_z(h, α, η) is defined as follows:

Φ_{z} (h, α, η) = \frac{\frac{1}{MN} Σ_{m, n} {(z (m, n; h, η) - α)}^{4}}{{(\frac{1}{MN} Σ_{m, n} {(z (m, n; h, η) - α)}^{2})}^{2}} .

(13)

One may solve the constrained optimization problem defined in Eq. (12) using a constrained optimization algorithm. We solve the problem using a gradient based trust-region-reflective method [22

T. Mathworks, Optimization toolbox user’s guide (Mathworks Inc., 2003).

Unlike the conventional MED and DMED method, the proposed method is not based on unrealistic assumption that the intensity values of pixels are i.i.d. realizations of a RV. Without the unrealistic assumption, it is guaranteed that the objective function of the proposed method is minimized when the deconvolved image is a bi-level image. In addition, we expect that the proposed method is robust to noise since not only it adopts Wiener-like filter but also it performs no noise amplifying differencing operation.

5. Results

5.1. Simulations

We conducted simulation studies to evaluate the performance of the proposed method in comparison with the DMED method. Figure 1(a) and Fig. 1(b) show true QR barcode image and text image that were used for simulation. The sizes of the QR barcode image and the text image were 290×290 and 290×468, respectively.

Fig. 1. Images for simulation: (a) true barcode image; (b) true text image.

We synthesized blurred barcode image and text image by convolving the true images with a 2D separable Gaussian PSF that has the same standard deviation σ for both x and y directions. Note that the 2D Gaussian function is often used for modeling out-of-focus blur [5

J. Kim and H. Lee, “Joint nonuniform illumination estimation and deblurring for bar code signals,” Opt. Express 17, 14817–14837 (2007). [CrossRef]

]. We also added white Gaussian noise to the synthesized blurred images to simulate the effect of noise. Figure 2(a) shows a synthesized noisy blurred barcode image (using PSF with σ = 6 pixels) whose SNR is 25 dB.

To quantify the degree of the similarity between an image and the true image, we defined two measures, the correlation coefficient (COR) between the image and the true image and bit error rate (BER). We computed the BER as the percentage of error pixels after the binarization of the image using a global threshold that was determined by the well-known Otsu’s method [21

R. C. Gonzalez, R. E. Woods, and S. L. Eddins, Digital image processing using MATLAB , (Prentice Hall, New York, 2002).

]. The COR value of the image shown in Fig. 2(a) was 0.786 and the BER of its binarization shown in Fig. 2(b) was 12.63%. Note that it is difficult to decode the barcode since the binarized image without deblurring has many error pixels.

To restore the true image from the noisy blurred image, we applied the DMED method and the proposed method to the image shown in Fig. 2(a). We applied 23×23 separable and symmetric filter for linear filter f for the DMED method and PSF h for the proposed method. If the support size of PSF is too small, then the blind deconvolution is not able to estimate true PSF while large support size make optimization complicated. Therefore, we determined the support size considering the maximum blur size that we attempt to compensate for. Note that there are many blind deconvolution methods based on the correct support size information. Those methods are prone to the errors in the support size of the PSF [11

D. Kundur and D. Hatzinakos, “Blind image deconvolution,” IEEE Trans. Image Process. 2, 223–235 (1993).

]. Unlike the methods, the proposed method does not require accurate knowledge of the correct support size. For example, we use the same support size for all the different blur point spread functions in the subsequent simulations and experiments. We defer investigating automatic determination of the support size to future study. We initialized the coefficients of the filter and PSF by delta function, i.e., assumed there is no blur in an acquired image. For the proposed method, we determined α₁, α₂ by the minimum and the maximum value of the observed image and η₁, η₂ by corresponding SNR 10dB and 100dB, respectively. For comparison purpose, we also applied the LSM method defined in Eq. (3) and Eq. (4). We manually tuned two regularization parameters λ₁ and λ₂ in a way such that the BER of the LSM method is minimized.

Figure 2(c) (COR 0.372) and Fig. 2(d) (BER 39.76%) show deblurred image by the DMED method and its binarization, respectively. (For display purpose, we normalize the intensity values in figures in this paper.) As shown in the images, the performance of the DMED method was not satisfactory. The COR value of the image shown in Fig. 2(c) was smaller than that of the image without deblurring. In addition, the BER value of the binarized image (shown in Fig. 2(d)) was larger than that of the binarization without deblurring.

The LSM method showed better performance than the DMED method. Figure 2(e) (COR 0.813) and Fig. 2(f) (BER 10.06 %) show the restored image using the LSM method and its binirization, respectively. As shown in the figures, the LSM method was able to improve the quality of the blurred image.

Compared with the DMED method and the LSM method, the proposed method showed significantly improved results. Figure 2(g) (COR 0.901) and Fig. 2(h) (BER 3.86%) show deblurred image by the proposed method and its binarization. As shown in the figures, it is clear that the proposed method significantly improved the quality of the observed image.

We believe that the poor performance of the DMED method is originated from its objective function. The DMED objective function value of the image shown in Fig. 2(c) was 7.95 while that of the image shown in Fig. 2(e) was 6.71. Apparently, more bi-level like image in Fig. 2(e) has smaller objective function value than that of the unrealistic image shown in Fig. 2(c). This is due to the fact that the DMED method seeks only more “simple and sporadic” structure in difference image regardless of binariness in deblurred image.

We also applied the three methods for the deconvolution of the text image shown in Fig. 3(a) that was generated by convolving the true text image shown in Fig. 1(b) with 2D separable Gaussian PSF (σ = 5 pixels). The SNR of the image was 35 dB and the COR value was 0.751. Figure 3(b) shows the binarization of the image in Fig. 3(a) (BER 6.69%). Figure 3(c) (COR 0.811) and Fig. 3(d) (BER 4.93%) show deblurred image and its binarization using the DMED method, respectively. Compared with the results for the barcode image, the performance of the DMED method was better as it was able to improve the quality of the observed image. We think this is due to that the edge image of the text image has more sporadic structure than that of the barcode image. For the text image, the DMED method outperformed the LSM method. As shown in the restored image by the LSM method in Fig. 3(e) (COR 0.754) and its binarization in Fig. 3(f) (BER 6.67%), the restored images by the LSM method were almost the same as blurred images.

Fig. 2. Barcode images: (a) noisy blurred barcode image (σ=6 pixels, SNR=25dB, COR=0.786); (b) binarization of Fig. 2(a) (BER=12.63%); (c) deblurred barcode image using the DMED method (COR=0.372); (d) binarization of Fig. 2(c) (BER=39.76%); (e) deblurred barcode image using the LSM method (COR=0.813); (f) binarization of Fig. 2(e) (BER=10.06%); (g) deblurred barcode image using the proposed method (COR=0.901); (h) binarization of Fig. 2(f) (BER=3.86%).

Although the performance of the DMED method was better than that of the LSM method, the DMED method was no better than the proposed method. Figure 3(g) (COR 0.894) and Fig. 3(h) (BER 2.18%) show deblurred image and its binarization using the proposed method. The COR value of the deblurred image using the proposed method was significantly larger than that of using the DMED method and the BER value of the binarized image using the proposed method is less than half of that using the DMED method.

The previous results show the performances of the DMED method, the LSM method and the proposed method for just one noise realization and a fixed amount of blur. To evaluate the performance of each method more thoroughly, we repeated the deblurring procedure for 50 different noise realizations for different noise powers and different amounts of blur (e.g., different σ values in PSF). Table 1 and Table 2 show average COR and BER values of the 50 noise realizations for the deconvolution of the barcode image, respectively. As shown in the tables, the performance of the proposed method was significantly better than that of the DMED method for every SNR and σ values. As a matter of fact, deblurred images by the DMED method were worse than observed images in the sense that the COR and BER values after applying the DMED method were worse than that of blurred images. On the contrary, the proposed method was able to improve the COR and BER values for every cases. For the cases of small blur and high SNR, the LSM method with manually tuned optimal parameters showed better performance than the proposed method. However, for most cases, the proposed method outperformed the LSM method. Note that we manually searched two regularization parameters (λ₁ = 10⁻²,λ₂ = 10⁻⁴) for the LSM method. It is challenging to tune the regularization parameters automatically since the optimal parameters vary depending on unknown true image, unknown PSF and unknown SNR. By comparison, the proposed method showed better performance for most cases without requiring manual tuning of any parameter.

Table 1. COR values of blurred images and deblurred images by the three methods for the barcode image with different amounts of blur and SNR values (unit for SNR is dB.)

SNR	blurred				DMED				LSM				proposed
	σ				σ				σ				σ
	3	4	5	6	3	4	5	6	3	4	5	6	3	4	5	6
40	.905	.875	.837	.788	.804	.495	.405	.130	.932	.900	.864	.821	.946	.922	.911	.908
35	.905	.875	.837	.788	.782	.389	.383	.375	.982	.900	.863	.820	.943	.920	.911	.906
30	.904	.874	.836	.787	.770	.387	.485	.384	.931	.898	.860	.815	.939	.917	.909	.902
25	.903	.872	.833	.784	.778	.386	.351	.300	.927	.891	.850	.803	.934	.914	.907	.901
20	.897	.866	.825	.775	.813	.376	.294	.352	.913	.871	.826	.773	.926	.909	.904	.895
15	.881	.846	.802	.749	.853	.350	.338	.312	.876	.825	.772	.712	.918	.906	.899	.886

Table 3 and Table 4 show average COR and BER values for the deconvolution of the text image, respectively. Unlike the results for the barcode image, the DMED method was able to improve the quality of blurred text images. However, the performance of the proposed method was better than that of the DMED method for every cases except for noisy and severely blurred images (e.g., SNR=20dB, 15dB and σ = 4, σ = 5 pixels) where the COR and BER values of the DMED method were slightly better than that of the proposed method. We do not think the results of such cases are meaningful for performance comparison since characters in restored images using both methods were not recognizable (e.g. BER is higher than 5%). The performance of the LSM methods was slightly better than that of the proposed method for the cases of the smallest blur (e.g., σ = 2 pixels). (Note that we had to search optimal parameters (λ₁ = 10⁻¹,λ₂ = 10⁵) for the text image again since that were not same as the optimal parameters for the barcode image.) However, for most cases, the proposed method outperformed the DMED method and the LSM method as shown in the tables.

Fig. 3. Text images: (a) noisy blurred text image (σ=5 pixels, SNR=35dB, COR=0.751); (b) binarization of Fig. 3(a) (BER=6.69%); (c) deblurred text image using the DMED method (COR=0.811); (d) binarization of Fig. 3(c) (BER=4.93%); (e) deblurred text image using the LSM method (COR=0.754); (f) binarization of Fig. 3(e) (BER=6.67%); (g) deblurred text image using the proposed method (COR=0.894); (h) binarization of Fig. 3(g) (BER=2.18%).

Table 2. BER values of blurred images and deblurred images by the three methods for the barcode image with different amounts of blur and SNR values (unit for BER is %.)

SNR	blurred				DMED				LSM				proposed
	σ				σ				σ				σ
	3	4	5	6	3	4	5	6	3	4	5	6	3	4	5	6
40	3.86	5.14	9.49	12.8	9.30	28.9	29.2	47.5	.97	3.74	6.30	9.34	3.25	3.50	3.60	3.60
35	3.89	5.15	9.42	12.7	12.2	29.8	29.3	40.5	1.01	3.69	6.28	9.44	3.29	3.50	3.59	3.70
30	3.92	5.23	9.16	12.7	18.8	29.8	30.1	36.3	1.14	3.74	6.34	9.67	3.31	3.53	3.62	3.86
25	3.99	5.63	8.90	12.7	13.1	29.8	40.1	40.3	1.59	4.11	6.82	10.4	3.37	3.57	3.65	3.91
20	4.27	6.19	9.15	13.3	9.27	30.1	39.1	36.8	2.58	5.25	8.31	12.6	3.46	3.67	3.75	4.24
15	5.13	7.29	10.4	15.0	6.60	33.5	36.6	37.7	4.47	7.87	11.8	16.6	3.51	3.71	4.00	4.82

Table 3. COR values of blurred images and deblurred images by the three methods for the text image with different amounts of blur and SNR values (unit for SNR is dB.)

SNR	blurred				DMED				LSM				proposed
	σ				σ				σ				σ
	3	4	5	6	3	4	5	6	3	4	5	6	3	4	5	6
40	.906	.854	.798	.754	.934	.914	.887	827	.909	.887	.853	.813	.941	.925	.912	.898
35	.906	.854	.797	.754	.931	.910	.879	813	.909	.887	.853	.813	.939	.922	.908	.839
30	.905	.853	.797	.754	.927	.905	.867	802	.909	.887	.853	.813	.935	.918	.903	.811
25	.904	.852	.795	.753	.922	.898	.852	796	.908	.886	.853	.813	.931	.914	.876	.802
20	.899	.846	.789	.751	.915	.887	.834	787	.907	.885	.851	.809	.926	.908	.818	.793
15	.884	.829	.770	.742	.905	.870	.816	736	.904	.881	.843	.796	.918	.899	.804	.779

Table 4. BER values of blurred images and deblurred images by the three methods for the text image with different amounts of blur and SNR values (unit for BER is %.)

SNR	blurred				DMED				LSM				proposed
	σ				σ				σ				σ
	3	4	5	6	3	4	5	6	3	4	5	6	3	4	5	6
40	2.17	4.52	5.91	6.72	1.49	1.66	2.83	4.77	1.16	2.52	4.22	5.62	1.46	1.49	1.62	1.99
35	2.18	4.52	5.90	6.72	1.51	1.76	3.31	4.92	1.16	2.52	4.21	5.62	1.47	1.50	1.72	4.42
30	2.18	4.52	5.88	6.74	1.54	1.97	3.95	5.06	1.16	2.52	4.21	5.61	1.49	1.53	1.82	5.42
25	2.19	4.54	5.88	6.77	1.58	2.29	4.43	5.24	1.16	2.52	4.20	5.61	1.49	1.57	3.02	5.63
20	2.24	4.56	5.93	6.85	1.66	2.83	4.77	5.49	1.16	2.50	4.20	5.62	1.49	1.70	5.25	5.81
15	2.38	4.61	6.05	7.07	2.01	3.80	5.15	7.11	1.19	2.52	4.25	5.72	1.54	1.97	5.56	6.02

One may argue that the performance of the LSM method can be improved by other regularization functions (possibly by a novel regularization function that is specialized for bi-level images or total variation [23

T. Chan and C. K. Wong, “Total variation blind deconvolution,” IEEE Trans. Image Process. 7, 370–375 (1998). [CrossRef]

]). We do not intend to claim that the proposed method outperforms every LSM methods. The purpose of the comparison is to show the effectiveness of the proposed method that does not require tuning of regularization parameters. More thorough comparison with possible nonlinear methods is deferred to future study.

We also tested the performance of the proposed method for non-Gaussian blur. We conducted simulation studies using a non-minimum phase non-causal auto-regressive (AR) filter blur that was used to test the performance of blind deconvolution of bi-level images in a previous investigation [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

]. The Fourier transform of a noisy blurred image by the AR filter blur is defined as follows [8

T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]

Y (ω_{x}, ω_{y}) = \frac{(1 - ρ^{4})}{(1 - ρ e^{- j ω_{x}}) (1 - ρ e^{j ω_{x}}) (1 - ρ e^{- j ω_{y}}) (1 - ρ e^{j ω_{y}})} X (ω_{x}, ω_{y}) + W (ω_{x}, ω_{y}),

(14)

where ρ represents correlation between adjacent pixels and W(ω_x,ω_y) does the Fourier transform of Gaussian noise. Figure 4(a) and Fig. 4(b) show blurred barcode and text image (SNR=30dB, ρ = 0.82 for barcode and ρ = 0.80 for text) using the AR filter. Figure 4(c) and Fig. 4(d) show the binarization of the blurred barcode and text image, respectively. We applied the DMED, the LSM and the proposed method for the blind deconvolution of the blurred images. Figure 4(e) and Fig. 4(f) show binarized images after applying the DMED method while Fig. 4(g) and Fig. 5(h) do those after applying the LSM method. (For brevity, we do not show deconvolved images.) As shown in the figures, the performance of the DMED method for the barcode image and the performance of the LSM method for the text image were very poor as the BER values after applying the methods were higher than those without deconvolution. Although the DMED and LSM method were able to improve the text image and the barcode image, respectively, the proposed method outperformed the methods as shown in the banarized barcode image (Fig. 4(i)(BER 1.55%)) and binarized text image (Fig. 4(j)(BER 1.96%)).

To evaluate the statistical properties of the three methods for the blurred images by the AR filter, we repeated simulations for 50 times for different amounts of blur (i.e. different ρ values) and different SNR values. Table 5 and Table 6 show average BER values of the three methods. (For brevity, we do not show COR values.) As shown in the tables, the proposed method outperformed the DMED method and the LSM method.

Table 5. BER values of blurred images and deblurred images by the three methods for the barcode image blurred by AR filter with different amounts of blur and SNR values (unit for BER is %.)

SNR	blurred			DMED			LSM			proposed
	ρ			ρ			ρ			ρ
	0.72	0.76	0.80	0.72	0.76	0.80	0.72	0.76	0.80	0.72	0.76	0.80
40	2.47	5.76	8.27	18.5	20.6	22.8	3.32	3.57	4.49	0.18	0.25	0.45
35	2.56	5.81	8.28	8.30	12.6	22.4	3.34	3.65	4.83	0.24	0.33	0.75
30	2.89	5.70	8.37	7.70	9.83	20.0	3.45	4.03	6.14	0.35	0.69	1.59
25	3.33	5.56	8.51	7.35	9.22	12.0	4.28	5.95	9.79	0.81	0.71	1.48
20	3.85	5.81	9.05	7.19	8.39	9.65	8.86	12.1	16.9	1.20	1.99	3.06
15	5.14	7.31	11.1	6.94	8.07	15.4	18.8	22.1	26.1	2.22	2.69	4.40

Table 6. BER values of blurred images and deblurred images by the three methods for the text image blurred by AR filter with different amounts of blur and SNR values (unit for BER is %.)

SNR	blurred			DMED			LSM			proposed
	ρ			ρ			ρ			ρ
	0.72	0.76	0.80	0.72	0.76	0.80	0.72	0.76	0.80	0.72	0.76	0.80
40	4.69	5.44	6.14	0.42	0.64	1.23	2.70	3.55	4.46	0.11	0.56	1.53
35	4.68	5.43	6.13	0.63	1.07	2.26	2.70	3.57	4.51	0.17	0.60	2.06
30	4.68	5.42	6.12	1.09	2.09	3.03	2.75	3.64	4.69	0.27	0.67	2.07
25	4.70	5.41	6.12	2.13	2.91	3.97	3.00	4.02	5.30	0.99	1.48	3.71
20	4.72	5.42	6.18	3.00	3.85	4.72	4.57	6.24	8.39	1.08	2.28	3.87
15	4.78	5.53	6.40	4.00	4.69	5.32	14.2	16.1	16.9	2.14	2.48	3.57

Note that the performance of non-convex optimization based methods (such as the DMED method and the proposed method) depends on initial estimate of parameters since optimization may converge to the nearest local minimum from the initial guess [24

E. K. P. Chong and S. H. Żak, An introduction to optimization , 3rd ed. (Wiley-Interscience, New Jersey, 2008).

]. It is very difficult to analyze the robustness to initial estimate since the effect of initial estimate can be different for different images and different noise realizations. During our simulations, we initialized PSF by delta function (i.e. no blur) for images blurred by Gaussian function and barcode images blurred by AR filter, and optimization converged to global minimum. In addition, we tested different initial PSFs (Gaussian PSFs with different σ values) and found optimization converged to global minimum for certain ranges of σ values. Note that the ranges are different for different amounts of blur and different SNR values. For blurred text images by the AR filter, we repeated optimization using initial Gaussian PSFs with different σ values and determined image that has the smallest objective function value. As a matter of fact, the strategy is one of the most widely used simple global optimization strategies [25

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

]. We do not think that the existence of local minima in the proposed objective function makes the proposed method less effective since we were able to find global minimum by the simple strategy. One may also apply global optimization algorithms such as simulated annealing method and genetic algorithm [24

E. K. P. Chong and S. H. Żak, An introduction to optimization , 3rd ed. (Wiley-Interscience, New Jersey, 2008).

]. We defer more thorough investigation on applying the global optimization methods to future study.

Fig. 4. Images for AR blur: (a) barcode; (b) text; (c) binarization of Fig. 4(a)(BER 8.48%); (d) binarization of Fig. 4(b)(BER 6.14%); (e) barcode by DMED (BER 41.9%); (f) text by DMED(BER 2.92%); (g) barcode by LSM(BER 6.21%); (h) text by LSM (BER 4.66%); (i) barcode by proposed (BER 1.55%) (j) text by proposed (BER 1.96%).

5.2. Real image

We also tested the performance of the proposed method in comparison with the DMED method for real images. We acquired real barcode and text images under normal illumination using a digital camera (Canon EOS-40D) without auto focusing. Figure 5(a) and Fig. 5(b) show the real barcode image and its binarization, respectively. As shown in the figures, due to blur and noise present in the acquired image, the binarized image has many error pixels. Figure 5(c) and Fig. 5(d) show restored image and its binirization using the DMED method. The performance of the DMED method was not satisfactory as the results of the restoration were even worse than the acquired images without deblurring. Figure 5(e) and Fig. 5(f) show restored image and its binarization using the LSM method. For the LSM method, we searched best parameters based on the subjective evaluation of the quality of restored image. Unlike the DMED method, the LSM method was able to improve the quality of the acquired image. Figure 5(e) and Fig. 5(f) show deblurred image using the proposed method and its binarization, respectively. Based on subjective evaluation, we believe that the proposed method showed better performance than the DMED and the LSM method. Although it is not possible to quantify the degree of the improvement since ground truth image is not available, it is clear that the binarized image using the proposed method (Fig. 5(h)) is more similar to the image shown in Fig. 1(b) than other binzarized images such as Fig. 5(d) and Fig. 5(f).

We also tested the performance of the three methods using a real text image. Figure 6(a) and Fig. 6(b) show the real text image and its binarization, respectively. Figure 6(c) and Fig. 6(d) show deblurred image and its binarization using the DMED method while Fig. 6(e) and Fig. 6(f) show those using the LSM method. Unlike the real barcode image case, the DMED method was able to improve the acquired image as shown in Fig. 6(c) and Fig. 6(d). As pointed out before, this phenomenon is originated from the fact that the edge image of the true text image has more “simple and sporadic” structure than the barcode image. Figure 6(g) and Fig. 6(h) shows restored image and its binarization using the proposed method. Based on the subjective evaluation of Fig. 6(g) and Fig. 6(h) in comparison with Fig. 6(c), Fig 6(d), Fig. 6(e) and Fig. 6(f), we believe that the proposed method outperformed the DMED method and the LSM method.

6. Conclusions

We have proposed a novel linear blind deconvolution method for bi-level images. The proposed method searches mid-level of two intensity values, PSF and noise-to-signal ratio by minimizing a high order statistics based objective function that reaches its lowest bound when deconvolved image is a bi-level image. Unlike conventional methods, the proposed method requires neither unrealistic assumptions such as image pixel values are i.i.d. samples of a random variable nor tuning of regularization parameters. We demonstrated the effectiveness of the proposed method in simulations and experiments using barcode and text images.

Fig. 5. Real barcode image and deblurred images: (a) real noisy blurred barcode image; (b) binarization of image shown in Fig. 5(a); (c) deblurred real barcode image using the DMED method; (d) binarization of image shown in Fig. 5(c); (e) deblurred real barcode image using the LSM method; (f) binarization of image shown in Fig. 5(e); (e) deblurred real barcode image using the proposed method; (f) binarization of image shown in Fig. 5(g).

Fig. 6. Real text image and deblurred images: (a) real noisy blurred text image; (b) binarization of image shown in Fig. 6(a); (c) deblurred real text image using the DMED method; (d) binarization of image shown in Fig. 6(c); (e) deblurred real text image using the LSM method; (f) binarization of image shown in Fig. 6(e); (g) deblurred real text image using the proposed method; (h) binarization of image shown in Fig. 6(g).

Acknowledgments

The authors are very grateful to the anonymous reviewers for thorough review of the paper and many insightful suggestions. The authors are also grateful to Sohyun Ahn for helping us prepare this paper. This work was supported by the Korean Research Foundation Grant funded by the Korean Government (KRF-2008-331-D00419) and Korean Science Engineering Foundation (KOSEF R17-2008-041-01001-0) funded by the Korean Government.

References and links

1.	T. J. Holmes, “Blind deconvolution of quantum-limited incorehent imagery:maximum-likelihood approach,” J. Opt. Soc. Am. A 9, 1052–1061 (1992). [CrossRef] [PubMed]
2.	D. A. Fish, A. M. Brinicombe, E. R. Pike, and G. Walker, “Blind deconvolution by means of the Richardson-Lucy algorithm,” J. Opt. Soc. Am. A 12, 58–65 (1995). [CrossRef]
3.	S. Esedoglu, “Blind deconvolution of bar code signals,” Inverse Probl. 20, 121–135 (2004). [CrossRef]
4.	E. Y. Lam, “Blind bi-level image restoration with iterated quadratic programming,” IEEE Trans. Circ. Syst. Part 2 52, 52–56 (2007). [CrossRef]
5.	J. Kim and H. Lee, “Joint nonuniform illumination estimation and deblurring for bar code signals,” Opt. Express 17, 14817–14837 (2007). [CrossRef]
6.	D. Kundur and D. Hatzinakos, “A novel blind deconvolution scheme for image restoration using recursive filtering,” IEEE Trans. Signal Process. 45, 375–390 (1998). [CrossRef]
7.	G. R. Ayers and J. C. Dainty, ‘Iterative blind deconvolution method and its application,” Opt. Lett. 13, 547–549 (1998). [CrossRef]
8.	T. Li and K. Lii, “A joint estimation approach for two-tone image deblurring by blind deconvolution,” IEEE Trans. Image Process. 11, 847–858 (2002). [CrossRef]
9.	H. Wu, “Minimum entropy deconvolution for restoration of blurred two-tone images,” Electronics Letters 26, 1183–1184 (1990). [CrossRef]
10.	N. Miura, N. Baba, S. Isobe, M. Noguchi, and Y. Norimoto, “Binary star reconstruction with use of the blind deconvolution method,” J. Mod. Opt. 39, 1137–1146 (1992). [CrossRef]
11.	D. Kundur and D. Hatzinakos, “Blind image deconvolution,” IEEE Trans. Image Process. 2, 223–235 (1993).
12.	J. A. Cadzow, “Blind deconvolution via cumulant extrema,” IEEE Signal Processing Magazine. , 24–41 (1996). [CrossRef]
13.	P. Campisi and K. Egiazarian Eds., Blind image deconvolution: Theory and applications , (CRC, New York, 2007). [CrossRef]
14.	H. Lee and J. Kim, “Retrospective correction of nonuniform illumination on bi-level images,” Opt. Express 15, 23880–23893 (2009). [CrossRef]
15.	Y. Shen, E. Y. Lam, and N. Wong, “Binary image restoration by positive semidefinite programming,” Opt. Lett. 32, 121–123 (2007). [CrossRef]
16.	M. D. Sacchi, D. R. Velis, and A. H. Comingues, “Minimum entropy deconvolution with frequency-domain constraints,” Geophysics 59, 938–945 (1994). [CrossRef]
17.	D. Donoho, “On minimum entropy deconvolution,” Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).
18.	N. F. Law and R. G. Lane, “Blind deconvolution using least squares minimisation,” Opt. Commun. 128, 341–352 (1996). [CrossRef]
19.	J. Kim, “Restoration of bi-level images via iterative semi-blind Wiener filtering,” Trans. KIEE 57, 1290–1294 (2008).
20.	H. L. Van Trees, Detection, estimation, and modulation theory, Part 1 (Wiley, 1968).
21.	R. C. Gonzalez, R. E. Woods, and S. L. Eddins, Digital image processing using MATLAB , (Prentice Hall, New York, 2002).
22.	T. Mathworks, Optimization toolbox user’s guide (Mathworks Inc., 2003).
23.	T. Chan and C. K. Wong, “Total variation blind deconvolution,” IEEE Trans. Image Process. 7, 370–375 (1998). [CrossRef]
24.	E. K. P. Chong and S. H. Żak, An introduction to optimization , 3rd ed. (Wiley-Interscience, New Jersey, 2008).
25.	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
(100.1455) Image processing : Blind deconvolution

ToC Category:
Image Processing

History
Original Manuscript: March 1, 2010
Revised Manuscript: April 23, 2010
Manuscript Accepted: May 25, 2010
Published: June 1, 2010

Citation
Jeongtae Kim and Soohyun Jang, "High order statistics based blind deconvolution of bi-level images with unknown intensity values," Opt. Express 18, 12872-12889 (2010)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-18-12-12872

Sort: Author | Year | Journal | Reset

References

T. J. Holmes, "Blind deconvolution of quantum-limited incorehent imagery:maximum-likelihood approach," J. Opt. Soc. Am. A 9, 1052-1061 (1992). [CrossRef] [PubMed]
D. A. Fish, A. M. Brinicombe, E. R. Pike and G. Walker, "Blind deconvolution by means of the Richardson-Lucy algorithm," J. Opt. Soc. Am. A 12, 58-65 (1995). [CrossRef]
S. Esedoglu, "Blind deconvolution of bar code signals," Inverse Probl. 20, 121-135 (2004). [CrossRef]
E. Y. Lam, "Blind bi-level image restoration with iterated quadratic programming," IEEE Trans. Circ. Syst. Part 2 52, 52-56 (2007). [CrossRef]
J. Kim and H. Lee, "Joint nonuniform illumination estimation and deblurring for bar code signals," Opt. Express 17, 14817-14837 (2007). [CrossRef]
D. Kundur and D. Hatzinakos, "A novel blind deconvolution scheme for image restoration using recursive filtering," IEEE Trans. Signal Process. 45, 375-390 (1998). [CrossRef]
G. R. Ayers, and J. C. Dainty, ‘Iterative blind deconvolution method and its application," Opt. Lett. 13, 547-549 (1998). [CrossRef]
T. Li and K. Lii, "A joint estimation approach for two-tone image deblurring by blind deconvolution," IEEE Trans. Image Process. 11, 847-858 (2002). [CrossRef]
H. Wu, "Minimum entropy deconvolution for restoration of blurred two-tone images," Electronics Letters 26, 1183-1184 (1990). [CrossRef]
N. Miura, N. Baba, S. Isobe, M. Noguchi, and Y. Norimoto, "Binary star reconstruction with use of the blind deconvolution method," J. Mod. Opt. 39, 1137-1146 (1992). [CrossRef]
D. Kundur and D. Hatzinakos, "Blind image deconvolution," IEEE Trans. Image Process. 2, 223-235 (1993).
J. A. Cadzow, "Blind deconvolution via cumulant extrema," IEEE Signal Processing Magazine., 24-41 (1996). [CrossRef]
P. Campisi and K. Egiazarian, eds., Blind image deconvolution: Theory and applications, (CRC, New York, 2007). [CrossRef]
H. Lee and J. Kim, "Retrospective correction of nonuniform illumination on bi-level images," Opt. Express 15, 23880-23893 (2009). [CrossRef]
Y. Shen, E. Y. Lam, and N. Wong, "Binary image restoration by positive semidefinite programming," Opt. Lett. 32, 121-123 (2007). [CrossRef]
M. D. Sacchi, D. R. Velis, and A. H. Comingues, "Minimum entropy deconvolution with frequency-domain constraints," Geophysics 59, 938-945 (1994). [CrossRef]
D. Donoho, "On minimum entropy deconvolution," Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).
N. F. Law and R. G. Lane, "Blind deconvolution using least squares minimisation," Opt. Commun. 128, 341-352 (1996). [CrossRef]
J. Kim, "Restoration of bi-level images via iterative semi-blind Wiener filtering," Trans. KIEE 57, 1290-1294 (2008).
H. L. Van Trees, Detection, estimation, and modulation theory, Part 1 (Wiley, 1968).
R. C. Gonzalez, R. E. Woods, and S. L. Eddins, Digital image processing using MATLAB, (Prentice Hall, New York, 2002).
T. Mathworks, Optimization toolbox user’s guide (Mathworks Inc., 2003).
T. Chan and C. K. Wong, "Total variation blind deconvolution," IEEE Trans. Image Process. 7, 370-375 (1998). [CrossRef]
E. K. P. Chong and S. H. Zak, An introduction to optimization, 3rd ed., (Wiley-Interscience, New Jersey, 2008).
W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical recipes in C++, 2nd ed., (Cambridge, 2005).

Electronics Letters

H. Wu, "Minimum entropy deconvolution for restoration of blurred two-tone images," Electronics Letters 26, 1183-1184 (1990). [CrossRef]

Geophysics

M. D. Sacchi, D. R. Velis, and A. H. Comingues, "Minimum entropy deconvolution with frequency-domain constraints," Geophysics 59, 938-945 (1994). [CrossRef]

IEEE Signal Processing Magazine.

J. A. Cadzow, "Blind deconvolution via cumulant extrema," IEEE Signal Processing Magazine., 24-41 (1996). [CrossRef]

IEEE Trans. Circ. Syst

E. Y. Lam, "Blind bi-level image restoration with iterated quadratic programming," IEEE Trans. Circ. Syst. Part 2 52, 52-56 (2007). [CrossRef]

IEEE Trans. Image Process.

T. Li and K. Lii, "A joint estimation approach for two-tone image deblurring by blind deconvolution," IEEE Trans. Image Process. 11, 847-858 (2002). [CrossRef]
T. Chan and C. K. Wong, "Total variation blind deconvolution," IEEE Trans. Image Process. 7, 370-375 (1998). [CrossRef]
D. Kundur and D. Hatzinakos, "Blind image deconvolution," IEEE Trans. Image Process. 2, 223-235 (1993).

IEEE Trans. Signal Process.

D. Kundur and D. Hatzinakos, "A novel blind deconvolution scheme for image restoration using recursive filtering," IEEE Trans. Signal Process. 45, 375-390 (1998). [CrossRef]

Inverse Probl.

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

J. Mod. Opt.

N. Miura, N. Baba, S. Isobe, M. Noguchi, and Y. Norimoto, "Binary star reconstruction with use of the blind deconvolution method," J. Mod. Opt. 39, 1137-1146 (1992). [CrossRef]

J. Opt. Soc. Am. A

Opt. Commun.

N. F. Law and R. G. Lane, "Blind deconvolution using least squares minimisation," Opt. Commun. 128, 341-352 (1996). [CrossRef]

Opt. Express

J. Kim and H. Lee, "Joint nonuniform illumination estimation and deblurring for bar code signals," Opt. Express 17, 14817-14837 (2007). [CrossRef]
H. Lee and J. Kim, "Retrospective correction of nonuniform illumination on bi-level images," Opt. Express 15, 23880-23893 (2009). [CrossRef]

Opt. Lett.

Trans. KIEE

J. Kim, "Restoration of bi-level images via iterative semi-blind Wiener filtering," Trans. KIEE 57, 1290-1294 (2008).

Other

H. L. Van Trees, Detection, estimation, and modulation theory, Part 1 (Wiley, 1968).
R. C. Gonzalez, R. E. Woods, and S. L. Eddins, Digital image processing using MATLAB, (Prentice Hall, New York, 2002).
T. Mathworks, Optimization toolbox user’s guide (Mathworks Inc., 2003).
E. K. P. Chong and S. H. Zak, An introduction to optimization, 3rd ed., (Wiley-Interscience, New Jersey, 2008).
W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical recipes in C++, 2nd ed., (Cambridge, 2005).
D. Donoho, "On minimum entropy deconvolution," Applied Time Series Analysis II, D. F. Findley ed., (Academic, New York, 1991).
P. Campisi and K. Egiazarian, eds., Blind image deconvolution: Theory and applications, (CRC, New York, 2007). [CrossRef]

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.

Click here to see a list of articles that cite this paper