Sequential scalar quantization of vectors: an analysis

Model-based color halftoning using direct binary search

In this paper, we develop a model-based color halftoning method using the direct binary search (DBS) algorithm. Our method strives to minimize the perceived error between the continuous tone original color image and the color halftone image. We exploit the differences in how the human viewers respond to luminance and chrominance information and use the total squared error in a luminance/chrominance based space as our metric. Starting with an initial halftone, we minimize this error metric using the DBS algorithm. Our method also incorporates a measurement based color printer dot interaction model to prevent the artifacts due to dot overlap and to improve color texture quality. We calibrate our halftoning algorithm to ensure accurate colorant distributions in resulting halftones. We present the color halftones which demonstrate the efficacy of our method.

On spatial quantization of color images

Image quantization and digital halftoning, two fundamental image processing problems, are generally performed sequentially and, in most cases, independent of each other. Color reduction with a pixel-wise defined distortion measure and the halftoning process with its local averaging neighborhood typically optimize different quality criteria or, frequently, follow a heuristic approach without reference to any quantitative quality measure. In this paper, we propose a new model to simultaneously quantize and halftone color images. The method is based on a rigorous cost-function approach which optimizes a quality criterion derived from a simplified model of human perception. It incorporates spatial and contextual information into the quantization and thus overcomes the artificial separation of quantization and halftoning. Optimization is performed by an efficient multiscale procedure which substantially alleviates the computational burden. The quality criterion and the optimization algorithms are evaluated on a representative set of artificial and real-world images showing a significant image quality improvement compared to standard color reduction approaches. Applying the developed cost function, we also suggest a new distortion measure for evaluating the overall quality of color reduction schemes.

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.

Sequential linear interpolation of multidimensional functions

We introduce a new approach that we call sequential linear interpolation (SLI) for approximating multidimensional nonlinear functions. The SLI is a partially separable grid structure that allows us to allocate more grid points to the regions where the function to be interpolated is more nonlinear. This approach reduces the mean squared error (MSE) between the original and approximated function while retaining much of the computational advantage of the conventional uniform grid interpolation. To obtain the optimal grid point placement for the SLI structure, we appeal to an asymptotic analysis similar to the asymptotic vector quantization (VQ) theory. In the asymptotic analysis, we assume that the number of interpolation grid points is large and the function to be interpolated is smooth. Closed form expressions for the MSE of the interpolation are obtained from the asymptotic analysis. These expressions are used to guide us in designing the optimal SLI structure. For cases where the assumptions underlying the asymptotic theory are not satisfied, we develop a postprocessing technique to improve the MSE performance of the SLI structure. The SLI technique is applied to the problem of color printer characterization where a highly nonlinear multidimensional function must be efficiently approximated. Our experimental results show that the appropriately designed SLI structure can greatly improve the MSE performance over the conventional uniform grid.

Digital color imaging

This paper surveys current technology and research in the area of digital color imaging. In order to establish the background and lay down terminology, fundamental concepts of color perception and measurement are first presented using vector-space notation and terminology. Present-day color recording and reproduction systems are reviewed along with the common mathematical models used for representing these devices. Algorithms for processing color images for display and communication are surveyed, and a forecast of research trends is attempted. An extensive bibliography is provided.