Blue and green noise halftoning models

In this article, we review the spatial and spectral characteristics of blue- and green-noise halftoning models. In the case of blue noise, dispersed-dot dither patterns are constructed by isolating minority pixels as homogeneously as possible, and by doing so, a pattern composed exclusively of high-frequency spectral components is produced. Blue-noise halftoning is preferred for display devices that can accommodate isolated dots such as various video displays and some print technologies such as ink-jet. For print marking engines that cannot support isolated pixels, dispersed-dot halftoning is inappropriate. For such cases, clustered-dot halftoning is used to avoid dot-gain instability. Green-noise halftones are clustered-dot, blue-noise patterns. Such patterns enjoy the blue-noise properties of homogeneity and lack low-frequency texture but have clusters of minority pixels on blue-noise centers. Green noise is composed exclusively of midfrequency spectral components. In addition to the basic spatial and spectral characteristics of the halftoning models, this article also reviews some of the earlier work done to improve error diffusion as a noise generator. We also discuss processes to generate threshold arrays to achieve blue and green noise with the computationally efficient process of ordered dither.     

Green-noise digital halftoning

In this paper, we introduce the concept of green noise-the multifrequency component of white noise-and its advantages over blue noise for digital halftoning. Unlike blue-noise dither patterns, which are composed exclusively of isolated pixels, green-noise dither patterns are composed of pixel-clusters making them less susceptible to image degradation from nonideal printing artifacts such as dot-gain. Although they are not the only techniques which generate clustered halftones, error-diffusion with output-dependent feedback and variations based on filter weight perturbation are shown to be good generators of green noise, thereby allowing for tunable coarseness. Using statistics developed for blue noise, we closely examine the spectral content of resulting dither patterns. We introduce two spatial-domain statistics for analyzing the spatial arrangement of pixels in aperiodic dither patterns, because green noise patterns may be anisotropic, and therefore spectral statistics based on radial averages may be inappropriate for the study of these patterns     

Digital color halftoning

Digital color halftoning is the process of transforming continuous-tone color images into images with a limited number of colors. The importance of this process arises from the fact that many color imaging systems use output devices such as color printers and low-bit depth displays that are bilevel or multilevel with a few levels. The goal is to create the perception of a continuous-tone color image using the limited spatiochromatic discrimination capability of the human visual system. In decreasing order of how locally algorithms transform a given image into a halftone and, therefore, in increasing order of computational complexity and halftone quality, monochrome digital halftoning algorithms can be placed in one of three categories: 1) point processes (screening or dithering), 2) neighborhood algorithms (error diffusion), and 3) iterative methods. All three of these algorithm classes can be generalized to digital color halftoning with some modifications. For an in-depth discussion of monochrome halftoning algorithms, the reader is directed to the July 2003 issue of IEEE Signal Processing Magazine. In the remainder of this article, we only address those aspects of halftoning that specifically have to do with color. For a good overview of digital color halftoning, the reader is directed to Haines et al. (2003). In addition, Agar et al. (2003) contains a more in-depth treatment of some of the material found in this work.     

Printer models and error diffusion

A new model-based approach to digital halftoning is proposed. It is intended primarily for laser printers, which generate "distortions" such as "dot overlap". Conventional methods, such as clustered-dot ordered dither, resist distortions at the expense of spatial and gray-scale resolution. The proposed approach relies on printer models that predict distortions, and rather than merely resisting them, it exploits them to increase, rather than decrease, both spatial and gray-scale resolution. We propose a general framework for printer models and find a specific model for laser printers. As an example of model-based halftoning, we propose a modification of error diffusion, which is often considered the best halftoning method for CRT displays with no significant distortions. The new version exploits the printer model to extend the benefits of error diffusion to printers. Experiments show that it provides high-quality reproductions with reasonable complexity. The proposed modified error diffusion technique is compared with Stucki's (1981) MECCA, which is a similar but not widely known technique that accounts for dot overlap. Model-based halftoning can be especially useful in transmission of high-quality documents using high-fidelity gray-scale image encoders.     

Binary genetic algorithm-based pattern LUT for grayscale digital half-toning

Grayscale digital half-toning is a popular technique to reproduce grayscale images with devices that can support only two levels at output, i.e., black and white. Printers, LCD displays, etc. are some common examples of such devices. Considering 0 and 1 as black and white, respectively, this can be represented as an image-wise binary pattern generation process. The binary patterns are aimed to retain the local tonal and structural characteristics of grayscale image for a faithful illusion of the original grayscale image. Apart from tonal and structural characteristics retention, desired blue-noise characteristics also contribute significantly toward eye pleasant appearance of half-tone images. The paper presents a binary genetic algorithm-based approach to generate such binary patterns through optimizing randomly generated binary strings against a visual cost function. Paper also presents a pattern look-up-table (LUT)-based approach toward conventional clustered dot ordered dithering which is suitable for devices like laser or offset printers that cannot recognize individual pixels. The pattern LUT approach is driven toward green-noise characteristics instead of the blue-noise characteristics. The results obtained with test images are presented pictorially and evaluated through half-tone quality evaluation metrics. The evaluation results and comparison with state-of-art techniques shows the potential of presented technique for practical implementations.     

Blue-noise multitone dithering.

The introduction of the blue-noise spectra-high-frequency white noise with minimal energy at low frequencies-has had a profound impact on digital halftoning for binary display devices, such as inkjet printers, because it represents an optimal distribution of black and white pixels producing the illusion of a given shade of gray. The blue-noise model, however, does not directly translate to printing with multiple ink intensities. New multilevel printing and display technologies require the development of corresponding quantization algorithms for continuous tone images, namely multitoning. In order to define an optimal distribution of multitone pixels, this paper develops the theory and design of multitone, blue-noise dithering. Here, arbitrary multitone dot patterns are modeled as a layered superposition of stack-constrained binary patterns. Multitone blue-noise exhibits minimum energy at low frequencies and a staircase-like, ascending, spectral pattern at higher frequencies. The optimum spectral profile is described by a set of principal frequencies and amplitudes whose calculation requires the definition of a spectral coherence structure governing the interaction between patterns of dots of different intensities. Efficient algorithms for the generation of multitone, blue-noise dither patterns are also introduced.     

Training-based descreening.

Conventional halftoning methods employed in electrophotographic printers tend to produce Moiré artifacts when used for printing images scanned from printed material, such as books and magazines. We present a novel approach for descreening color scanned documents aimed at providing an efficient solution to the Moiré problem in practical imaging devices, including copiers and multifunction printers. The algorithm works by combining two nonlinear image-processing techniques, resolution synthesis-based denoising (RSD), and modified smallest univalue segment assimilating nucleus (SUSAN) filtering. The RSD predictor is based on a stochastic image model whose parameters are optimized beforehand in a separate training procedure. Using the optimized parameters, RSD classifies the local window around the current pixel in the scanned image and applies filters optimized for the selected classes. The output of the RSD predictor is treated as a first-order estimate to the descreened image. The modified SUSAN filter uses the output of RSD for performing an edge-preserving smoothing on the raw scanned data and produces the final output of the descreening algorithm. Our method does not require any knowledge of the screening method, such as the screen frequency or dither matrix coefficients, that produced the printed original. The proposed scheme not only suppresses the Moiré artifacts, but, in addition, can be trained with intrinsic sharpening for deblurring scanned documents. Finally, once optimized for a periodic clustered-dot halftoning method, the same algorithm can be used to inverse halftone scanned images containing stochastic error diffusion halftone noise.     

Model-based digital halftoning

Digital halftoning is the process of generating a pattern of pixels with a limited number of colors that, when seen by the human eye, is perceived as a continuous-tone image. Digital halftoning is used to display continuous-tone images in media in which the direct rendition of the tones is impossible. The most common example of such media is ink or toner on paper, and the most common rendering devices for such media are, of course, printers. Halftoning works because the eye acts as a spatial low-pass filter that blurs the rendered pixel pattern, so that it is perceived as a continuous-tone image. Although all halftoning methods rely at least implicitly, on some understanding of the properties of human vision and the display device, the goal of model-based halftoning techniques is to exploit explicit models of the display device and the human visual system (HVS) to maximize the quality of the displayed images. Based on the type of computation involved, halftoning algorithms can be broadly classified into three categories: point algorithms (screening or dithering), neighborhood algorithms (error diffusion), and iterative algorithms [least squares and direct binary search (DBS)]. All of these algorithms can incorporate HVS and printer models. The best halftone reproductions, however, are obtained by iterative techniques that minimize the (squared) error between the output of the cascade of the printer and visual models in response to the halftone image and the output of the visual model in response to the original continuous-tone image.     

Inkjet printer model-based halftoning.

The quality of halftone prints produced by inkjet (IJ) printers can be limited by random dot-placement errors. While a large literature addresses model-based halftoning for electrophotographic printers, little work has been done on model-based halftoning for IJ printers. In this paper, we propose model-based approaches to both iterative least-squares halftoning and tone-dependent error diffusion (TDED). The particular approach to iterative least-squares halftoning that we use is direct binary search (DBS). For DBS, we use a stochastic model for the equivalent gray-scale image, based on measured dot statistics of printed IJ halftone patterns. For TDED, we train the tone-dependent weights and thresholds to mimic the spectrum of halftone textures generated by model-based DBS. We do this under a metric that enforces both the correct radially averaged spectral profile and angular symmetry at each radial frequency. Experimental results generated with simulated printers and a real printer show that both IJ model-based DBS and IJ model-based TDED very effectively suppress IJ printer-induced artifacts.     

Tree-structured method for LUT inverse halftoning and for imagehalftoning

The authors previously proposed a look up table (LUT) based method for inverse halftoning of images. The LUT for inverse halftoning is obtained from the histogram gathered from a few sample halftone images and corresponding original images. Many of the entries in the LUT are unused because the corresponding binary patterns hardly occur in commonly encountered halftones. These are called nonexistent patterns. In this paper, we propose a tree structure which will reduce the storage requirements of an LUT by avoiding nonexistent patterns. We demonstrate the performance on error diffused images and ordered dither images. Then, we introduce LUT based halftoning and tree-structured LUT (TLUT) halftoning. Even though the TLUT method is more complex than LUT halftoning, it produces better halftones and requires much less storage than LUT halftoning. We demonstrate how the error diffusion characteristics can be achieved with this method. Afterwards, our algorithm is trained on halftones obtained by direct binary search (DBS). The complexity of TLUT halftoning is higher than the error diffusion algorithm but much lower than the DBS algorithm. Also, the halftone quality of TLUT halftoning increases if the size of the TLUT gets bigger. Thus, the halftone image quality between error diffusion and DBS will be achieved depending on the size of the tree-structure in the TLUT algorithm     

Compaction of ordered dithered images with arithmetic coding

Ordered dither is considered to be a simple and effective method among all halftoning techniques. In this paper, compaction of ordered dithered images using arithmetic coding is studied. A preprocessor referred to as pixel interleaving (i.e., grouping pixels with similar dithering thresholds) is employed in such a way that dithered images can be efficiently coded with the JBIG1 code and high compressibility can be achieved. Experimental results reveal that the four-pixel interleaving achieves the best compression performance.     

A multiscale error diffusion technique for digital multitoning

Multitoning is the representation of digital pictures using a given set of available color intensities, which are also known as tones or quantization levels. It can be viewed as the generalization of halftoning, where only two such quantization levels are available. Its main application is for printing and, similar to halftoning, can be applied to both colored and grayscale images. In this paper, we present a method to produce multitones based on the multiscale error diffusion technique. Key characteristics of this technique are: 1) the use of an image quadtree; 2) the quantization order of the pixels being determined through "maximum intensity guidance" on the image quadtree; and 3) noncausal error diffusion. Special care has been given to the problem of banding, which is one of the inherent limitations in error diffusion when applied to multitoning. Banding is evident in areas of the image with values close to one of the available quantization levels; our approach is to apply a preprocessing step to alleviate part of the problem. Our results are evaluated both in terms of visual appearance and using a set of standard metrics, with the latter demonstrating the blue-noise characteristics and very low anisotropy of the proposed method.     

Towards optimized binary pattern generation for grayscale digital halftoning: A binary particle swarm optimization (BPSO) approach

Grayscale digital halftoning produces bi-level representation of original continuous tone images. This process plays pivotal role for devices like printers, plasma panels, LCD displays, etc. The bi-level images can be considered as binary images where ‘0’ and ‘1’ correspond to black and white, respectively. This paper investigates potential of binary particle swarm optimization (BPSO) to generate faithful binary halftone patterns. The cost function addresses important characteristics of original images and pleasant visual appearance of halftone images. The paper also shows the application of pattern look-up-table (p-LUT) approach to address the high processing time of BPSO optimization and simple gradient-based edge enhancement for improved edge retention. Results are evaluated subjectively by statistical measures and psychovisual test. Results are evaluated objectively using image quality evaluation metrics as well. The comparisons with state-of-the-art techniques are also drawn. The evaluation results along with the comparisons show the competitive potential of the presented technique.     

Blue-noise halftoning for hexagonal grids.

In this paper, we closely scrutinize the spatial and spectral properties of aperiodic halftoning schemes on rectangular and hexagonal sampling grids. Traditionally, hexagonal sampling grids have been shunned due to their inability to preserve the high-frequency components of blue-noise dither patterns at gray-levels near one-half, but as will be shown, only through the introduction of diagonal correlations between dots can even rectangular sampling grids preserve these frequencies. And by allowing the sampling grid to constrain the placement of dots, a particular algorithm may introduce visual artifacts just as disturbing as excess energy below the principal frequency. If, instead, the algorithm maintains radial symmetry by introducing a minimum degree of clustering, then that algorithm can maintain its grid defiance illusion fundamental to the spirit of the blue-noise model. As such, this paper shows that hexagonal grids are preferrable because they can support gray-levels near one-half with less required clustering of minority pixels and a higher principal frequency. Along with a thorough Fourier analysis of blue-noise dither patterns on both rectangular and hexagonal sampling grids, this paper also demonstrates the construction of a blue-noise dither array for hexagonal grids.     

JPEG-compliant perceptual coding for a grayscale image printingpipeline

We describe a procedure by which Joint Photographic Experts Group (JPEG) compression may be customized for gray-scale images that are to be compressed before they are scaled, halftoned, and printed. Our technique maintains 100% compatibility with the JPEG standard, and is applicable with all scaling and halftoning methods. The JPEG quantization table is designed using frequency-domain characteristics of the scaling and halftoning operations, as well as the frequency sensitivity of the human visual system. In addition, the Huffman tables are optimized for low-rate coding. Compression artifacts are significantly reduced because they are masked by the halftoning patterns, and pushed into frequency bands where the eye is less sensitive. We describe how the frequency-domain effects of scaling and halftoning may be measured, and how to account for those effects in an iterative design procedure for the JPEG quantization table. We also present experimental results suggesting that the customized JPEG encoder typically maintains "near visually lossless" image quality at rates below 0.5 b/pixel (with reference to the number of pixels in the original image) when it is used with bilinear interpolation and either error diffusion or ordered dithering. Based on these results, we believe that in terms of the achieved bit rate, the performance of our encoder is typically at least 20% better than that of a JPEG encoder using the suggested baseline tables.     

Automatic Image Segmentation by Dynamic Region Growth and Multiresolution Merging

Image segmentation is a fundamental task in many computer vision applications. In this paper, we propose a new unsupervised color image segmentation algorithm, which exploits the information obtained from detecting edges in color images in the CIE L_*a_*b_* color space. To this effect, by using a color gradient detection technique, pixels without edges are clustered and labeled individually to identify some initial portion of the input image content. Elements that contain higher gradient densities are included by the dynamic generation of clusters as the algorithm progresses. Texture modeling is performed by color quantization and local entropy computation of the quantized image. The obtained texture and color information along with a region growth map consisting of all fully grown regions are used to perform a unique multiresolution merging procedure to blend regions with similar characteristics. Experimental results obtained in comparison to published segmentation techniques demonstrate the performance advantages of the proposed method.     

Monochromatic-Based Method for Impulse Noise Detection and Suppression in Color Images

A new method to detect and reduce the impulse noise in color images is presented in this paper. The method consists of two stages: detection and filtering. Since each of the individual channels (components) of the color image can be considered as a monochrome image, both stages are applied to each channel separately, and then the individual results are combined into one output image. The corrupted pixels are detected in the first stage based on a proposed innovative switching technique. The noise-free pixels are copied to their corresponding locations in the output image. In the second stage, average filtering is applied only to those pixels which are determined to be noisy in the first stage, and only noise-free pixel values are involved in calculating this average. The size of the sliding window depends on the estimated noise density and is very small even for high noise densities. The proposed method is effective in noise reduction while preserving edge details and color chromaticity. Simulation results show that the proposed method outperforms all the tested existing state-of-the-art methods used in digital color image restoration in both standard objective measurements and perceived image quality.     

Color to gray and back: color embedding into textured gray images.

We have developed a reversible method to convert color graphics and pictures to gray images. The method is based on mapping colors to low-visibility high-frequency textures that are applied onto the gray image. After receiving a monochrome textured image, the decoder can identify the textures and recover the color information. More specifically, the image is textured by carrying a subband (wavelet) transform and replacing bandpass subbands by the chrominance signals. The low-pass subband is the same as that of the luminance signal. The decoder performs a wavelet transform on the received gray image and recovers the chrominance channels. The intent is to print color images with black and white printers and to be able to recover the color information afterwards. Registration problems are discussed and examples are presented.     

Memory efficient error diffusion

Because of its good image quality and moderate computational requirements, error diffusion has become a popular halftoning solution for desktop printers, especially inkjet printers. By making the weights and thresholds tone-dependent and using a predesigned halftone bitmap for tone-dependent threshold modulation, it is possible to achieve image quality very close to that obtained with far more computationally complex iterative methods. However, the ability to implement error diffusion in very low cost or large format products is hampered by the requirement to store the tone-dependent parameters and halftone bitmap, and also the need to store error information for an entire row of the image at any given point during the halftoning process. For the first problem, we replace the halftone bitmap by deterministic bit flipping, which has been previously applied to halftoning, and we linearly interpolate the tone-dependent weights and thresholds from a small set of knot points. We call this implementation a reduced lookup table. For the second problem, we introduce a new serial block-based approach to error diffusion. This approach depends on a novel intrablock scan path and the use of different parameter sets at different points along that path. We show that serial block-based error diffusion reduces off-chip memory access by a factor equal to the block height. With both these solutions, satisfactory image quality can only be obtained with new cost functions that we have developed for the training process. With these new cost functions and moderate block size, we can obtain image quality that is very close to that of the original tone-dependent error diffusion algorithm.     

A POCS-based restoration algorithm for restoring halftoned color-quantized images.

This paper studies the restoration of images which are color-quantized with error diffusion. Though there are many reported algorithms proposed for restoring noisy blurred color images and inverse halftoning, restoration of color-quantized images is rarely addressed in the literature especially when the images are color-quantized with halftoning. Direct application of existing restoration techniques are generally inadequate to deal with this problem. In this paper, a restoration algorithm based on projection onto convex sets is proposed. This algorithm makes use of the available color palette and the mechanism of a halftoning process to derive useful a priori information for restoration. Simulation results showed that it could improve the quality of a halftoned color-quantized image remarkably in terms of both SNR and CIELAB color difference metric.