Model-based halftoning of color images

We present a new class of models for color printers. They form the basis for model-based techniques that exploit the characteristics of the printer and the human visual system to maximize the quality of the printed images. We present two model-based techniques, the modified error diffusion (MED) algorithm and the least-squares model-based (LSMB) algorithm. Both techniques are extensions of the gray-scale model-based techniques and produce images with high spatial resolution and visually pleasant textures. We also examine the use of printer models for designing blue-noise screens. The printer models cam account for a variety of printer characteristics. We propose a specific printer model that accounts for overlap between neighboring dots of ink and the spectral absorption properties of the inks. We show that when we assume a simple "one-minus-RGB" relationship between the red, green, and blue image specification and the corresponding cyan, magenta, and yellow inks, the algorithms are separable. Otherwise, the algorithms are not separable and the modified error diffusion may be unstable, The experimental results consider the separable algorithms that produce high-quality images for applications where the exact colorimetric reproduction of color is not necessary. They are computationally simple and robust to errors in color registration, but the colors are device dependent.     

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.     

Inverse halftoning using binary permutation filters

The problem of reconstructing a continuous-tone image given its ordered dithered halftone or its error-diffused halftone image is considered. We develop a modular class of nonlinear filters that can reconstruct the continuous-tone information preserving image details and edges that provide important visual cues. The proposed nonlinear reconstruction algorithms, denoted as binary permutation filters, are based on the space and rank orderings of the halftone samples provided by the multiset permutation of the "on" pixels in a halftone observation window. For a given window size, we obtain a wide range of filters by varying the amount of space-rank ordering information utilized in the estimate. For image reconstructions from ordered dithered halftones, we develop periodically space-varying filters that can account for the periodical nature of the underlying screening process. A class of suboptimal but simpler space-invariant reconstruction filters are also proposed and tested. Constrained LMS type algorithms are employed for the design of reconstruction filters that minimize the reconstruction mean squared error. We present simulations showing that binary permutation filters are modular, robust to image source characteristics, and that they produce high visual quality image reconstruction.     

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.     

Halftoning via direct binary search using analytical and stochastic printer models

We incorporate models for printer dot interactions within the iterative direct binary search (DBS) halftoning algorithm. Monochrome electro-photographic printers are considered. Both analytical and stochastic models are studied. In the analytical model it is assumed that the printer can generate a circular spot with constant absorptance at each printer addressable location, whereas the stochastic model is based on microscopic absorptance and variance measurements. We also present an efficient strategy for evaluating the change in computational cost as the search progresses. With our scheme, updating the change in error only involves a few fetches from two look-up-tables and some scalar multiplications and additions. Experimental results are provided that show that DBS with an appropriate model for printer dot interactions yields enhanced detail rendition, and improved tonal gradation in shadow areas.     

Electrophotographic process embedded in direct binary search

A novel halftoning approach that has embedded in it a model for the electrophotographic process is presented. Models for the laser beam, exposure of the organic photoconductor, and the resulting absorptance on the paper are embedded into the direct binary search (DBS) halftoning algorithm. The algorithm is applicable to any arbitrary pixel modulation scheme and is also highly portable between different electrophotographic print engines. Computational issues are addressed to make the approach viable. Results show good exploitation of pixel modulation and improvement over DBS with no printer model throughout most of the tone scale.     

Inverse halftoning using wavelets

This work introduces a new approach to inverse halftoning using nonorthogonal wavelets. The distinct features of this wavelet-based approach are: (1) edge information in the highpass wavelet images of a halftone image is extracted and used to assist inverse halftoning, (2) cross-scale correlations in the multiscale wavelet decomposition are used for removing background halftoning noise while preserving important edges in the wavelet lowpass image, and (3) experiments show that our simple wavelet-based approach outperforms the best results obtained from inverse halftoning methods published in the literature, which are iterative in nature.     

Oriented modulation for watermarking in direct binary search halftone images

In this paper, a halftoning-based watermarking method is presented. This method enables high pixel-depth watermark embedding, while maintaining high image quality. This technique is capable of embedding watermarks with pixel depths up to 3 bits without causing prominent degradation to the image quality. To achieve high image quality, the parallel oriented high-efficient direct binary search (DBS) halftoning is selected to be integrated with the proposed orientation modulation (OM) method. The OM method utilizes different halftone texture orientations to carry different watermark data. In the decoder, the least-mean-square-trained filters are applied for feature extraction from watermarked images in the frequency domain, and the na?ve Bayes classifier is used to analyze the extracted features and ultimately to decode the watermark data. Experimental results show that the DBS-based OM encoding method maintains a high degree of image quality and realizes the processing efficiency and robustness to be adapted in printing applications.     

Algorithms of halftoning color images with edge enhancement

Printers usually generate a limited number of colors and lack the ability of producing continuous-tone color images. Traditional error-diffusion algorithms are used to solve this problem. Compared with other approaches, the approaches of using error-diffusion in general can generate halftoned images of better quality. However, smeared edges and textures may occur in these halftoned images. To produce halftoned images of higher quality, these artifacts due to unstable images, dot-overlap, and error-diffusion must be eliminated or reduced. In this paper, we show that unstable images can be eliminated or reduced through using a proper color difference formula to select the reproduction colors even vector error-diffusion is performed in the RGB domain. We also present a method of using different filters to halftone different components of a color. This approach may have clearer and sharper edges for halftoned color images. Unexpected colors may be generated due to dot-overlap in the printing process. We have presented a method to eliminate this color distortion in the process of error-diffusion. Halftoning a color image by our proposed error-diffusion algorithm with edge enhancement has the following characteristics: the unstable images do not exist; the color-error caused by dot-overlap is corrected; and the smeared edges are sharpened.     

Video halftoning.

This paper studies video halftoning that renders a digital video sequence onto display devices, which have limited intensity resolutions and color palettes, by trading the spatiotemporal resolution for enhanced intensity/color resolution. This trade is needed when a continuous tone video is not necessary or not practical for video display, transmission, and storage. In particular, the quantization error of a pixel is diffused to its spatiotemporal neighbors by separable one-dimensional temporal and two-dimensional spatial error diffusions. Motion-adaptive gain control is employed to enhance the temporal consistency of the visual patterns by minimizing the flickering artifacts. Experimental results of halftone and colortone videos are demonstrated and evaluated with various halftoning techniques.     

Digital color halftoning with generalized error diffusion andmultichannel green-noise masks

In this paper, we introduce two novel techniques for digital color halftoning with green-noise-stochastic dither patterns generated by homogeneously distributing minority pixel clusters. The first technique employs error diffusion with output-dependent feedback where, unlike monochrome image halftoning, an interference term is added such that the overlapping of pixels of different colors can be regulated for increased color control. The second technique uses a green-noise mask, a dither array designed to create green-noise halftone patterns, which has been constructed to also regulate the overlapping of different colored pixels. As is the case with monochrome image halftoning, both techniques are tunable, allowing for large clusters in printers with high dot-gain characteristics, and small clusters in printers with low dot-gain characteristics.     

Entropy-constrained halftoning using multipath tree coding

We suggest an optimization-based method for halftoning that involves looking ahead before a decision for each binary output pixel is made. We first define a mixture distortion criterion that is a combination of a frequency-weighted mean square error (MSE) and a measure depending on the distances between minority pixels in the halftone. A tree-coding approach with the ML-algorithm is used for minimizing the distortion criterion to generate a halftone. While this approach generates halftones of high quality, these halftones are not very amenable to lossless compression. We introduce an entropy constraint into the cost function of the tree-coding algorithm that optimally trades off between image quality and compression performance in the output halftones.     

Efficient design centering of analog integrated circuits using binary search

This paper introduces a procedure for automatically design centering analog integrated circuits called the divide-and-focus method (DAF). DAF is a simple, efficient, and effective algorithm for design centering complex circuits, even if the performance of the original nominal design is poor. DAF uses a binary search of each dimension of parameter space to rapidly focus on regions promising high yield. DAF was applied to a third-order elliptic CMOS transconductance-C integrated circuit filter derived from an automated layout and containing 126 nodes and 319 MOSFETS. Using five key capacitor values as design centering parameters, DAF improved yield in the presence of parasitic capacitance (as extracted from the layout) by a factor of 19 from an initial value of 4% to a final value of 76%. By relaxing constraints on component value symmetry, DAF found a higher yield than was possible when maintaining symmetry, where DAF achieved a yield of 34%. Since DAF uses Monte Carlo analysis to estimate circuit yield, its execution time can be further reduced by exploiting the parallelism implicit in Monte Carlo techniques. Using a local area network of 10 workstations similar to those available at most engineering sites, DAF completed the design centering of the filter 7.4 times faster than when using a single workstation.Supported in part by a Research Initiation grant (CCR-9111941) from the National Science Foundation.Supported in part by a grant (MIP-9121360) from the National Science Foundation.     

Hiding color watermarks in halftone images using maximum-similarity binary patterns

This paper presents a halftoning-based watermarking method that enables the embedding of a color image into binary black-and-white images. To maintain the quality of halftone images, the method maps watermarks to halftone channels using homogeneous dot patterns. These patterns use a different binary texture arrangement to embed the watermark. To prevent a degradation of the host image, a maximization problem is solved to reduce the associated noise. The objective function of this maximization problem is the binary similarity measure between the original binary halftone and a set of randomly generated patterns. This optimization problem needs to be solved for each dot pattern, resulting in processing overhead and a long running time. To overcome this restriction, parallel computing techniques are used to decrease the processing time. More specifically, the method is tested using a CUDA-based parallel implementation, running on GPUs. The proposed technique produces results with high visual quality and acceptable processing time.     

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.     

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.     

Soft-decision decoding of binary linear block codes using reducedbreadth-first search algorithms

The article discusses soft-decision decoding of binary linear block codes using the t-algorithm and its variants. New variants of the basic algorithm are presented that reduce the decoding complexity using a threshold adaptive to the signal-to-noise ratio and address the variable decoding complexity by either limiting the memory or using a generalized M-algorithm with a nonconstant state profile     

A dual interpretation for direct binary search and its implicationsfor tone reproduction and texture quality

The direct binary search (DBS) algorithm employs a search heuristic to minimize the mean-squared perceptually filtered error between the halftone and continuous-tone original images. Based on an efficient method for evaluating the effect on the mean squared error of trial changes to the halftone image, we show that DBS also minimizes in a pointwise sense the absolute error under the same visual model, but at twice the viewing distance associated with the mean-squared error metric. This dual interpretation sheds light on the convergence properties of the algorithm, and clearly explains the tone bias that has long been observed with halftoning algorithms of this type. It also demonstrates how tone bias and texture quality are linked via the scale parameter, the product of printer resolution and viewing distance. Finally, we show how the tone bias can be eliminated by tone-correcting the continuous-tone image prior to halftoning it.     

Watermarking-based image authentication with recovery capability using halftoning technique

In this paper two watermarking algorithms for image content authentication with localization and recovery capability of the tampered regions are proposed. In both algorithms, a halftone version of the original gray-scale image is used as an approximated version of the host image (image digest) which is then embedded as a watermark sequence into given transform domains of the host image. In the first algorithm, the Integer Wavelet Transform (IWT) is used for watermark embedding which is denominated WIA-IWT (Watermarking-based Image Authentication using IWT), while in the second one, the Discrete Cosine Transform (DCT) domain is used for this purpose, we call this algorithm WIA-DCT (Watermarking-based Image Authentication using DCT). In the authentication stage the tampered regions are detected using the Structural Similarity index (SSIM) criterion, which are then recovered using the extracted halftone image. In the recovery stage, a Multilayer Perceptron (MLP) neural network is used to carry out an inverse halftoning process to improve the recovered image quality. The experimental results demonstrate the robustness of both algorithms against content preserved modifications, such as JPEG compression, as well as an effective authentication and recovery capability. Also the proposed algorithms are compared with some previously proposed content authentication algorithms with recovery capability to show the better performance of the proposed algorithms.