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.     

Quantization of accumulated diffused errors in error diffusion.

Due to its high image quality and moderate computational complexity, error diffusion is a popular halftoning algorithm for use with inkjet printers. However, error diffusion is an inherently serial algorithm that requires buffering a full row of accumulated diffused error (ADE) samples. For the best performance when the algorithm is implemented in hardware, the ADE data should be stored on the chip on which the error diffusion algorithm is implemented. However, this may result in an unacceptable hardware cost. In this paper, we examine the use of quantization of the ADE to reduce the amount of data that must be stored. We consider both uniform and nonuniform quantizers. For the nonuniform quantizers, we build on the concept of tone-dependency in error diffusion, by proposing several novel feature-dependent quantizers that yield improved image quality at a given bit rate, compared to memoryless quantizers. The optimal design of these quantizers is coupled with the design of the tone-dependent parameters associated with error diffusion. This is done via a combination of the classical Lloyd-Max algorithm and the training framework for tone-dependent error diffusion. Our results show that 4-bit uniform quantization of the ADE yields the same halftone quality as error diffusion without quantization of the ADE. At rates that vary from 2 to 3 bits per pixel, depending on the selectivity of the feature on which the quantizer depends, the feature-dependent quantizers achieve essentially the same quality as 4-bit uniform quantization.     

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.     

A multiscale error diffusion technique for digital halftoning

A new digital halftoning technique based on multiscale error diffusion is examined. We use an image quadtree to represent the difference image between the input gray-level image and the output halftone image. In iterative algorithm is developed that searches the brightest region of a given image via "maximum intensity guidance" for assigning dots and diffuses the quantization error noncausally at each iteration. To measure the quality of halftone images, we adopt a new criterion based on hierarchical intensity distribution. The proposed method provides very good results both visually and in terms of the hierarchical intensity quality measure.     

Joint halftoning and watermarking

A framework to jointly halftone and watermark a grayscale images is presented. The framework needs the definition of three components: a human visual system (HVS)-based error metric between the continuous-tone image and a halftone, a watermarking scheme with a corresponding watermark detection measure, and a search strategy to traverse the space of halftones. We employ the HVS-based error metric used in the direct binary search (DBS) halftoning algorithm, and we use a block-based spread spectrum watermarking scheme and the toggle and swap search strategy of DBS. The halftone is printed on a desktop printer and scanned using a flatbed scanner. The watermark is detected from the scanned image and a number of post-processed versions of the scanned image, including one restored in Adobe PhotoShop. The results show that the watermark is extremely resilient to printing, scanning, and post-processing; for a given baseline image quality, joint optimization is better than watermarking and halftoning independently. For this particular algorithm, the original continuous-tone image is required to detect the watermark.     

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.     

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.     

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     

A fast, high-quality inverse halftoning algorithm for errordiffused halftones

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.     

Data hiding watermarking for halftone images

In many printer and publishing applications, it is desirable to embed data in halftone images. We proposed some novel data hiding methods for halftone images. For the situation in which only the halftone image is available, we propose data hiding smart pair toggling (DHSPT) to hide data by forced complementary toggling at pseudo-random locations within a halftone image. The complementary pixels are chosen to minimize the chance of forming visually undesirable clusters. Our experimental results suggest that DHSPT can hide a large amount of hidden data while maintaining good visual quality. For the situation in which the original multitone image is available and the halftoning method is error diffusion, we propose the modified data hiding error diffusion (MDHED) that integrates the data hiding operation into the error diffusion process. In MDHED, the error due to the data hiding is diffused effectively to both past and future pixels. Our experimental results suggest that MDHED can give better visual quality than DHSPT. Both DHSPT and MDHED are computationally inexpensive.     

Halftone image classification using LMS algorithm and naive Bayes

Former research on inverse halftoning most focus on developing a general-purpose method for all types of halftone patterns, such as error diffusion, ordered dithering, etc., while fail to consider the natural discrepancies among various halftoning methods. To achieve optimal image quality for each halftoning method, the classification of halftone images is highly demanded. This study employed the least mean-square filter for improving the robustness of the extracted features, and employed the naive Bayes classifier to verify all the extracted features for classification. Nine of the most well-known halftoning methods were involved for testing. The experimental results demonstrated that the classification performance can achieve a 100% accuracy rate, and the number of distinguishable halftoning methods is more than that of a former method established by Chang and Yu.     

Adaptive threshold modulation for error diffusion halftoning

Grayscale digital image halftoning quantizes each pixel to one bit. In error diffusion halftoning, the quantization error at each pixel is filtered and fed back to the input in order to diffuse the quantization error among the neighboring grayscale pixels. Error diffusion introduces nonlinear distortion (directional artifacts), linear distortion (sharpening), and additive noise. Threshold modulation, which alters the quantizer input, has been previously used to reduce either directional artifacts or linear distortion. This paper presents an adaptive threshold modulation framework to improve halftone quality by optimizing error diffusion parameters in the least squares sense. The framework models the quantizer implicitly, so a wide variety of quantizers may be used. Based on the framework, we derive adaptive algorithms to optimize 1) edge enhancement halftoning and 2) green noise halftoning. In edge enhancement halftoning, we minimize linear distortion by controlling the sharpening control parameter. We may also break up directional artifacts by replacing the thresholding quantizer with a deterministic bit flipping (DBF) quantizer. For green noise halftoning, we optimize the hysteresis coefficients.     

自适应反馈视觉感知差的误差扩散半色调算法

文章基于人眼对亮度的视觉感受特性。提出了一种自适应反馈视觉感知差的误差扩散算法（PEF Error Diffusion算法）。首先提出视觉感知差的概念，然后根据原图像区域的灰度特征，自适应地计算反馈系数，将视觉感知差反馈给原连续调图像，以补偿误差扩散所引起的不同区域的灰度损失。实验结果表明，由于视觉感知差的引入及反馈系数的自适应变化。PEF Error Diffusion算法能够明显增强图像的整体对比度．减弱点增益现象的不良影响，并准确再现更多的图像细节．因而表现出比传统算法更好的主观视觉效果。     

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.     

Modeling and quality assessment of halftoning by error diffusion

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.     

Inverse halftoning and kernel estimation for error diffusion

Two different approaches in the inverse halftoning of error-diffused images are considered. The first approach uses linear filtering and statistical smoothing that reconstructs a gray-scale image from a given error-diffused image. The second approach can be viewed as a projection operation, where one assumes the error diffusion kernel is known, and finds a gray-scale image that will be halftoned into the same binary image. Two projection algorithms, viz., minimum mean square error (MMSE) projection and maximum a posteriori probability (MAP) projection, that differ on the way an inverse quantization step is performed, are developed. Among the filtering and the two projection algorithms, MAP projection provides the best performance for inverse halftoning. Using techniques from adaptive signal processing, we suggest a method for estimating the error diffusion kernel from the given halftone. This means that the projection algorithms can be applied in the inverse halftoning of any error-diffused image without requiring any a priori information on the error diffusion kernel. It is shown that the kernel estimation algorithm combined with MAP projection provide the same performance in inverse halftoning compared to the case where the error diffusion kernel is known.     

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.     

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.     

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.     

Impact of HVS models on model-based halftoning

A model for the human visual system (HVS) is an important component of many halftoning algorithms. Using the iterative direct binary search (DBS) algorithm, we compare the halftone texture quality provided by four different HVS models that have been reported in the literature. Choosing one HVS model as the best for DBS, we then develop an approximation to that model which significantly improves computational performance while minimally increasing the complexity of the code. By varying the parameters of this model, we find that it is possible to tune it to the gray level being rendered, and to thus yield superior halftone quality across the tone scale. We then develop a dual-metric DBS algorithm that effectively provides a tone-dependent HVS model without a large increase in computational complexity.