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.     

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.     

基于色调处理技术的图像认证算法

基于色调处理技术,该文给出了一种有效可行且具有自修复能力的图像认证算法。首先,基于误差扩散色调处理技术将水印图像4bit色调量化,井依据混沌置乱算子,将色调结果置乱,然后构造平均误差最小的特征集合C,最后依据误差扩散数据隐藏算法将置乱后水印图像隐藏于原始图像中;在认证端,从接收到的图像提取其中所隐藏水印信息并进行逆置乱,比较接收到的图像和反置乱后的隐藏信息,判断内容发生变化的位置,并依据所提取的水印信息修复被篡改图像。实验结果表明,该算法对删除、替换、篡改等破坏图像内容的恶意操作有精确的检测和定位,以及自修复能力。     

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.     

Design and analysis of vector color error diffusion halftoningsystems

Traditional error diffusion halftoning is a high quality method for producing binary images from digital grayscale images. Error diffusion shapes the quantization noise power into the high frequency regions where the human eye is the least sensitive. Error diffusion may be extended to color images by using error filters with matrix-valued coefficients to take into account the correlation among color planes. For vector color error diffusion, we propose three contributions. First, we analyze vector color error diffusion based on a new matrix gain model for the quantizer, which linearizes vector error diffusion. The model predicts the key characteristics of color error diffusion, esp. image sharpening and noise shaping. The proposed model includes linear gain models for the quantizer by Ardalan and Paulos (1987) and by Kite et al. (1997) as special cases. Second, based on our model, we optimize the noise shaping behavior of color error diffusion by designing error filters that are optimum with respect to any given linear spatially-invariant model of the human visual system. Our approach allows the error filter to have matrix-valued coefficients and diffuse quantization error across color channels in an opponent color representation. Thus, the noise is shaped into frequency regions of reduced human color sensitivity. To obtain the optimal filter, we derive a matrix version of the Yule-Walker equations which we solve by using a gradient descent algorithm. Finally, we show that the vector error filter has a parallel implementation as a polyphase filterbank.     

Color error-diffusion halftoning

Grayscale halftoning converts a continuous-tone image (e.g., 8 bits per pixel) to a lower resolution (e.g., 1 bit per pixel) for printing or display. Grayscale halftoning by error diffusion uses feedback to shape the quantization noise into high frequencies where the human visual system (HVS) is least sensitive. In color halftoning, the application of grayscale error-diffusion methods to the individual colorant planes fails to exploit the HVS response to color noise. Ideally the quantization error must be diffused to frequencies and colors, to which the HVS is least sensitive. Further it is desirable for the color quantization to take place in a perceptual space so that the colorant vector selected as the output color is perceptually closest to the color vector being quantized. This article discusses the design principles of color error diffusion that differentiate it from grayscale error diffusion, focusing on color error diffusion halftoning systems using the red, green, and blue (RGB) space for convenience.     

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.     

Slant Transform Image Coding

A new unitary transform called the slant transform, specifically designed for image coding, has been developed. The transformation possesses a discrete sawtoothlike basis vector which efficiently represents linear brightness variations along an image line. A fast computational algorithm has been found for the transformation. The slant transformation has been utilized in several transform image-coding systems for monochrome and color images. Computer simulation results indicate that good quality coding can be accomplished with about 1 to 2 bits/pixel for monochrome images and 2 to 3 bits/pixel for color images.     

Image Compression Using Adaptive Vector Quantization

The paper demonstrates the application of adaptive vector quantization techniques to the coding of monochromatic and color pictures. Codebooks of representative vectors are generated for different portions of the image. By means of extensive simulations, the performance of the coder for monochrome images is estimated as a function of the various coding parameters-vector dimensionality, number of representative vectors, and degree of adaptivity. It is shown that for a vector size of dimension 4, there is a zone of operation, ranging from 1.0 to 1.5 bits/pixel, where adaptive vector quantization is advantageous. Despite the simplicity of the decoder, the performance of the adaptive vector quantizer is found to be comparable with block transform coding schemes for both monochrome and color pictures.     

Hybrid LMS-MMSE inverse halftoning technique

The objective of this work is to reconstruct high quality gray-level images from bilevel halftone images. We develop optimal inverse halftoning methods for several commonly used halftone techniques, which include dispersed-dot ordered dither, clustered-dot ordered dither, and error diffusion. At first, the least-mean-square (LMS) adaptive filtering algorithm is applied in the training of inverse halftone filters. The resultant optimal mask shapes are significantly different for various halftone techniques, and these mask shapes are also quite different from the square shape that was frequently used in the literature. In the next step, we further reduce the computational complexity by using lookup tables designed by the minimum mean square error (MMSE) method. The optimal masks obtained from the LMS method are used as the default filter masks. Finally, we propose the hybrid LMS-MMSE inverse halftone algorithm. It normally uses the MMSE table lookup method for its fast speed. When an empty cell is referred, the LMS method is used to reconstruct the gray-level value. Consequently, the hybrid method has the advantages of both excellent reconstructed quality and fast speed. In the experiments, the error diffusion yields the best reconstruction quality among all three halftone techniques.     

Embedded multilevel error diffusion

We present an algorithm for image browsing systems that embeds the output of binary Floyd-Steinberg (1975) error diffusion, or a low bit-depth gray-scale or color error diffused image into higher bit-depth gray-scale or color error diffused images. The benefits of this algorithm are that a low bit-depth halftoned image can be directly obtained from a higher bit-depth halftone for printing or progressive transmission simply by masking one or more bits off of the higher bit-depth image. The embedding can be done in any bits of the output, although the most significant or the least significant bits are most convenient. Due to constraints on the palette introduced by embedding, the image quality for the higher bit-depth halftone may be reduced. To preserve the image quality, we present algorithms for color palette organization, or binary index assignment, to be used as a preprocessing step to the embedding algorithm.     

Robust Watermarking with Kernels-Alternated Error Diffusion and Weighted Lookup Table in Halftone Images

A halftone watermarking method of high quality, robustness, and capacity flexibility is presented in this paper. An objective halftone image quality evaluation method based on the human visual system obtained by a least-mean-square algorithm is also introduced. In the encoder, the kernels-alternated error diffusion (KAEDF) is applied. It is able to maintain the computational complexity at the same level as ordinary error diffusion. Compared with Hel-Or using ordered dithering, the proposed KAEDF yields a better image quality through using error diffusion. We also propose a weighted lookup table (WLUT) in the decoder instead of lookup table (LUT), as proposed by Pei and Guo, so as to achieve a higher decoded rate. As the experimental results demonstrate, this technique is able to guard against degradation due to tampering, cropping, rotation, and print-and-scan processes in error-diffused halftone images.     

彩色图像误差扩散多值量化滤波器的优化设计

在多值量化情况下 ,因量化误差为白噪声的理想条件无法满足 ,故实施误差扩散处理时仅单纯地进行高通滤波 (误差蓝化 )将损害图像固有的低频特性。误差扩散算法中较为理想的误差滤波器应在高频域具有较大增益 ,而在低频域具有有限度衰减。在兼顾滤波器稳定性因素的同时对误差滤波器的脉冲响应进行了重新设计 ,并以此构成了用于彩色图像颜色量化的多色调误差扩散优化处理算法。     

颜色量化——色彩退化算法

颜色量化是利用人眼对颜色的惰性,将原图像中不太重要的相似颜色合并为一种颜色,减少图像中的颜色,而使量化前后的图像对于人眼的认识误差最小即量化误差最小。在此从揭示八叉树颜色量化算法的优缺点开始,优化八叉树结构,进化为以二叉堆和数组索引数据结构,对最不重要颜色不断地进行退化,最终达到量化要求的颜色数量。实践证明,在相同情况下,二叉堆比八叉树颜色量化对图像的量化误差更小。     

Fuzzy algorithms for combined quantization and dithering

Color quantization reduces the number of the colors in a color image, while the subsequent dithering operation attempts to create the illusion of more colors with this reduced palette. In quantization, the palette is designed to minimize the mean squared error (MSE). However, the dithering that follows enhances the color appearance at the expense of increasing the MSE. We introduce three joint quantization and dithering algorithms to overcome this contradiction. The basic idea is the same in two of the approaches: introducing the dithering error to the quantizer in the training phase. The fuzzy C-means (FCM) and the fuzzy learning vector quantization (FLVQ) algorithms are used to develop two combined mechanisms. In the third algorithm, we minimize an objective function including an inter-cluster separation (ICS) term to obtain a color palette which is more suitable for dithering. The goal is to enlarge the convex hull of the quantization colors to obtain the illusion of more colors after error diffusion. The color contrasts of images are also enhanced with the proposed algorithm. We test the results of these three new algorithms using quality metrics which model the perception of the human visual system and illustrate that substantial improvements are achieved after dithering     

Fuzzy error diffusion

Quantization errors are generally hidden by performing a dithering operation on the image. A common method is to utilize error diffusion. However, this method is prone to error accumulation, resulting in color impulses and streaks. This paper presents a new approach to error diffusion dithering through a fuzzy error diffusion algorithm. In this method, the amount of error to be diffused is determined by considering the relative location of the pixel not only to the closest codebook vector, but to all other palette entries. The goal is to hide the quantization errors by error diffusion, while preventing the excess accumulation of errors. This is achieved through an attraction-repulsion schema according to a fuzzy membership function. We also explored methods to speed up the fuzzy error diffusion process through a L-filter approach by determining a fixed set of membership values. We have implemented the fuzzy error diffusion algorithm for color images and achieved drastic improvements, resulting in superior quality dithered images and significantly lower mean squared error values. A different error measure modeling the characteristic of the human visual system also indicates the superiority of our method.     

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.     

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.     

基于矢量量化的误差扩散半色调图像有损压缩算法

随着误差扩散半色调图像在书刊、杂志、打印输出和传真文件中广泛应用和大量传播,有必要对这类特殊的二值图像进行压缩以利于节省存储空间且加快传输速度。提出一种基于矢量量化思想并结合人眼视觉特征的误差扩散半色调图像有损压缩方法。首先,原始图像被分成若干个4×4的像素块,将这些块分别与一个模拟人眼视觉特性的5×5高斯滤波器做卷积。然后,将得到的8×8的卷积结果作为输入矢量,经过LBG算法训练得到一个码书。之后,对每个码字,找到与其最相似的4×4的像素块作为最终的码字。这样就建立了用来压缩原始图像的码书。最后一步就是利用该码书用传统的矢量量化思想压缩原始图像并得到最终的码字索引。仿真实验结果表明通过该方法得到的压缩图像的视觉质量得到进一步的提高。该方法在压缩比和保持图像质量取得了较好的折中。     

Effects of luminance quantization error on color image processing

A common approach to color image processing is to apply monochrome techniques to the quantized intensity component. However, the quantization error in the intermediate intensity image propagates to the final processed image. This can lead to significant distortion, depending on the input RGB values and on the particular image processing function being applied. A theoretical analysis of the worst-case quantization error is presented. Experimental results with histogram equalization demonstrate how the histogram resolution affects the performance.