We model a degraded image as an original image that has been subject to linear frequency distortion and additive noise injection. Since the psychovisual effects of frequency distortion and noise injection are independent, we decouple these two sources of degradation and measure their effect on the human visual system. We develop a distortion measure (DM) of the effect of frequency distortion, and a noise quality measure (NQM) of the effect of additive noise. The NQM, which is based on Peli's (1990) contrast pyramid, takes into account the following: 1) variation in contrast sensitivity with distance, image dimensions, and spatial frequency; 2) variation in the local luminance mean; 3) contrast interaction between spatial frequencies; 4) contrast masking effects. For additive noise, we demonstrate that the nonlinear NQM is a better measure of visual quality than peak signal-to noise ratio (PSNR) and linear quality measures. We compute the DM in three steps. First, we find the frequency distortion in the degraded image. Second, we compute the deviation of this frequency distortion from an allpass response of unity gain (no distortion). Finally, we weight the deviation by a model of the frequency response of the human visual system and integrate over the visible frequencies. We demonstrate how to decouple distortion and additive noise degradation in a practical image restoration system.

Halftones and other binary images are difficult to process with causing several degradation. Degradation is greatly reduced if the halftone is inverse halftoned (converted to grayscale) before scaling, sharpening, rotating, or other processing. For error diffused halftones, we present (1) a fast inverse halftoning algorithm and (2) a new multiscale gradient estimator. The inverse halftoning algorithm is based on anisotropic diffusion. It uses the new multiscale gradient estimator to vary the tradeoff between spatial resolution and grayscale resolution at each pixel to obtain a sharp image with a low perceived noise level. Because the algorithm requires fewer than 300 arithmetic operations per pixel and processes 7x7 neighborhoods of halftone pixels, it is well suited for implementation in VLSI and embedded software. We compare the implementation cost, peak signal to noise ratio, and visual quality with other inverse halftoning algorithms.

Digital halftoning quantizes a graylevel image to one bit per pixel. Halftoning by error diffusion reduces local quantization error by filtering the quantization error in a feedback loop. In this paper, we linearize error diffusion algorithms by modeling the quantizer as a linear gain plus additive noise. We confirm the accuracy of the linear model in three independent ways. Using the linear model, we quantify the two primary effects of error diffusion: edge sharpening and noise shaping. For each effect, we develop an objective measure of its impact on the subjective quality of the halftone. Edge sharpening is proportional to the linear gain, and we give a formula to estimate the gain from a given error filter. In quantifying the noise, we modify the input image to compensate for the sharpening distortion and apply a perceptually weighted signal-to-noise ratio to the residual of the halftone and modified input image. We compute the correlation between the residual and the original image to show when the residual can be considered signal independent. We also compute a tonality measure similar to total harmonic distortion. We use the proposed measures for edge sharpening, noise shaping, and tonality to evaluate the quality of error diffusion algorithms.

We present raster image processing algorithms for rehalftoning error diffused halftones and producing interpolated error diffused halftones. Rehalftoning converts a halftone created by one method into one created by another method. In interpolated halftoning, interpolation increases the image size before halftoning, e.g. for printing. Both rehalftoning and interpolated halftoning introduce blur and noise in the output image. To compensate for the blur, we use modified error diffusion, which has a variable gain parameter to control the sharpness. We derive optimal formulas for the sharpness control parameter to make the overall frequency response flat. The high-frequency noise is masked by error diffusion. The proposed algorithms yield halftones of high fidelity at a low computational cost.

We present a fast, non-iterative technique for producing grayscale images from error diffused and dithered halftones. The first stage of the algorithm consists of a Gaussian filter and a median filter, while the second stage consists of a bandpass filter, a thresholding operation, and a median filter. The second stage enhances the rendering of edges in the inverse halftone. We compare our algorithm to the best reported statistical smoothing, wavelet, and Bayesian algorithms to show that it delivers comparable PSNR and subjective quality at a fraction of the computation and memory requirements. For error diffused halftones, our technique is seven times faster than the MAP estimation method and 75 times faster than the wavelet method. For dithered halftones, our technique is 200 times faster than the MAP estimation method. A C implementation of the algorithm is available.

We present an inverse halftoning algorithm for error diffused halftones. At each pixel, the algorithm applies a separable 7/spl times/7 FIR filter parameterized by the computed local horizontal and vertical gradients. All operations are entirely local; only 7 rows of image storage and fewer than 300 operations per pixel are required. The algorithm can be easily implemented in embedded software or hardware. We compare our algorithm with previously reported approaches, and show that it delivers comparable PSNR and subjective quality at a fraction of the computation and memory requirements. A C implementation of the algorithm is available.

The error diffusion algorithm for digital halftoning is equivalent in form to a noise-shaping feedback coder, a class of delta-sigma modulator. The white noise assumption of the quantizer error is known to be false; in fact, the quantizer error is seen to be highly correlated with the input image. To account for this correlation, we use a gain model for the quantizer. This model accurately predicts the edge sharpening and noise shaping caused by all error diffusion schemes. It also permits an extension of error diffusion to oversampled imagery.