New metric describes edge noise in bilevel images

Almost all images suffer from degradation of some form. Therefore, significant research effort is spent on developing methods to remove this. Its most common form is additive Gaussian noise. This often comes together with a blurring degradation or point-spread-function (PSF) convolution,

The noise (N) is usually represented by its standard deviation, σ_N (see Figure 1), which describes the qualitative noise effect on gray-level images using a quantitative metric. Noise-removal algorithms, such as the Wiener filter,¹ use the noise level to produce an optimal restoration filter.

Figure 1. Image with four noise regions. From left to right, noise standard deviation σ_N= {0, 0.001, 0.004, 0.01}.

In bilevel images, such as combined text and graphical document images, additive Gaussian noise is often present. Source images are also often blurred by the acquisition optics. However, because their content is inherently of two levels (black and white), it is very common to apply a threshold, Θ, to degraded images to return the content to two levels,

This nonlinear operation changes the effects of noise and blurring in the final bilevel image. The intensity levels will always change abruptly from white to black, and vice versa, even without additive noise. The edge contours will now exhibit different characteristics. Corners will become rounded^2,3 and strokes can become thicker or thinner.^3,4 The additive noise appears in two primary regions: in solid regions and along edges.

In solid regions of white (black), any pixels that exceed (fall below) the threshold will turn black (white). These color reversals are collectively called salt-and-pepper noise (see Figure 2). This effect can be predicted quantitatively from the cumulative normal distribution, which is described entirely by σ_N and Θ,

and

Figure 2. Bilevel image with four noise regions. From left to right, σ_N= {0, 0.005, 0.01, 0.015}, all thresholded at Θ=0 .5.

P is the probability and ζ is a dummy variable of integration. This assumes that background white and foreground black have values of 0 and 1, respectively, in units of absorbtance. The solid regions are affected by salt-and-pepper noise, which can often be removed using median filters and similar techniques.¹

In addition to noisy pixels in the solid regions, noise occurs along the stroke edges (see Figure 3). These noise features interfere with many analysis operations, such as fitting lines to edges and character or symbol recognition. Moreover, edge noise is more difficult to remedy because noise-removal filters can also remove desired image features. While the noise in gray-level images can be described wholly by the additive noise variance, and in solid regions of bilevel images a combination of the noise variance and binarization threshold provides an adequate characterization, edge noise is also affected by the slope of the edge contour and the blurring PSF.

Figure 3. Bilevel image with four noise regions. The first has no noise, for reference. While σ_N=0.015 is constant, the noise spread (NS) takes on the increasing values {0, 0.06, 0.12, 0.18}. All are thresholded at Θ=0.5. Blurring varies from left to right as {none, 0.64, 1.27, 1.9}.

We have developed a quantity, the noise spread (NS), to qualitatively and quantitatively describe this edge noise. For a straight edge, blurring with a PSF of width w leads to formation of an edge-spread function (ESF): see Figure 4. When thresholded without additive noise, a unique position for the threshold crossing is determined, but in the presence of additive noise that position is not unique. The probability of exceeding the threshold will be a function of the threshold level as well as the distance from the blurred edge to the threshold,

where x is position relative to the edge.

Figure 4. Noisy blurred edge. In the NS region, the noisy signal crosses the threshold many times.

The NS can be defined by the bounds of a linearization region and is a function of the PSF's functional form (Gaussian, Cauchy, or other), width, and binarization threshold,

The line-spread function (LSF) is the 1D PSF. While the noise standard deviation in Figure 3 is constant, the observed edge noise increases and the NS follows this increase. We have shown that NS is proportional to the expected Hamming distance between the original and the noisy-edge images, and correlated with the ability to fit a line to a straight edge.⁵ We are working to develop noise-removal algorithms that, given the NS level, can self-calibrate for optimal performance.

In summary, we have defined a metric that describes the amount of edge noise present in bilevel images both quantitatively and qualitatively. This could be used for image characterization in a similar fashion to the signal-to-noise ratio. We have also prototyped a method to estimate the NS directly from noisy bilevel images.⁵

This material is based on work supported by the National Science Foundation under grant CCR-0238285.