A dual interpretation for direct binary search and its implications for 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.

Look-up-table based halftoning algorithm.

Screening is a low complexity halftoning algorithm that has been widely used in many applications. However, screen design requires that the stacking property be obeyed. This constraint limits the texture quality at each gray level. We present a look-up-table based halftoning algorithm for which the stacking constraint is not necessarily satisfied; but the binary patterns for individual levels are still correlated. The binary patterns are designed level by level using the direct binary search method. The algorithm improves halftone image quality compared with screening.

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.

Optimization of sensor response functions for colorimetry of reflective and emissive objects.

This paper describes the design of color filters for a surface color measurement device. The function of the device is to return the XYZ tristimulus vector characterizing the color of the surface. The device is designed to measure emissive as well as reflective surfaces. It uses an internal set of LEDs to illuminate reflective surfaces while characterizing their color under assumed standard illuminants. In the design of the filters, we formulate a nonlinear optimization problem with the goal of minimizing error in the uniform color space CIE L*a*b*. Our optimization criteria employs a technique to retain a linear structure while approximating the true L*a*b* error. In addition, our solution is regularized to account for system noise, filter roughness, and filter implementation errors. Experimental results indicate average and worst-case device accuracy of 0.27 L*a*b* DeltaE units and 1.56 L*a*b* DeltaE units for a "system tolerance" of 0.0005.

Motion estimation based on time-sequentially sampled imagery.

Determining the parameters of motion within a time-varying scene is an important problem in such fields as computer vision, motion compensated video coding, and tracking. Most motion estimation algorithms operate on image data that has been sampled in both space and time. However, very little work has been done to investigate the impact of the underlying sampling strategy on the motion estimation problem. The authors investigate motion estimation with time-sequentially sampled image data. They consider both centroid-displacement-based and Fourier-based approaches to motion estimation with this type of data. For comparision, they also examine the performance of these estimators with conventional, frame-instantaneously sampled data. The motion estimators are developed and evaluated in the context of the tracking problem. In particular, they present extensive numerical results showing the performance of the motion estimators in a simulated tracking environment within which the assumptions underlying the development of the estimators are violated. These results suggest empirical rules for choosing parameter values for the estimators.

Sequential scalar quantization of vectors: an analysis.

Proposes an efficient vector quantization (VQ) technique called sequential scalar quantization (SSQ). The scalar components of the vector are individually quantized in a sequence, with the quantization of each component utilizing conditional information from the quantization of previous components. Unlike conventional independent scalar quantization (ISQ), SSQ has the ability to exploit intercomponent correlation. At the same time, since quantization is performed on scalar rather than vector variables, SSQ offers a significant computational advantage over conventional VQ techniques and is easily amenable to a hardware implementation. In order to analyze the performance of SSQ, the authors appeal to asymptotic quantization theory, where the codebook size is assumed to be large. Closed-form expressions are derived for the quantizer mean squared error (MSE). These expressions are used to compare the asymptotic performance of SSQ with other VQ techniques. The authors also demonstrate the use of asymptotic theory in designing SSQ for a practical application (color image quantization), where the codebook size is typically small. Theoretical and experimental results show that SSQ far outperforms ISQ with respect to MSE while offering a considerable reduction in computation over conventional VQ at the expense of a moderate increase in MSE.

Synthesis of diffractive optical bar codes.

A new type of diffractive optical bar code (DOBC) is proposed. Rather than scanning directly, the DOBC is coherently illuminated, and the first diffraction order is sensed. The spacing between the bars is chosen so that the thresholded diffraction pattern yields a specified binary code. Two approaches are investigated for synthesis of the DOBC: phase shaping and a gradient-based, nonlinear, constrained optimization technique. The two design methods are compared based on numerical results, and the validity of the overall design approach is verified by optically sensing the diffraction patterns for a number of fabricated DOBC's.

Multiple scattering by a planar array of parallel dielectric cylinders.

The solution of the multiple-scattering problem for N parallel dielectric cylinders is considered for plane-wave illumination perpendicular to the cylinder axes. We describe a nonlinear programming approach to solve the multiple-scattering matrix for an arbitrary planar array of N parallel dielectric cylinders. To our knowledge, no calculations have been made previously for multiple scattering by more than two parallel dielectric cylinders. Numerical results for four abutting cylinders with end-on illumination demonstrate damping of internal resonance features similar to previously published results for two cylinders. Furthermore, we present numerical examples of scattering from eight unequally spaced, parallel dielectric cylinders with broadside illumination. Because of coupling between the cylinders, the incident energy is spread evenly between the intensity peaks behind the array of cylinders.

Optical median filtering using threshold decomposition.

A hybrid optical/electronic system performs median filtering and related ranked-order operations using threshold decomposition to encode the image. Threshold decomposition transforms the nonlinear neighborhood ranking operation into a linear space-invariant filtering step followed by a point-to-point threshold comparison step. Spatial multiplexing allows parallel processing of all the threshold components as well as recombination by a second linear space-invariant filtering step. An incoherent optical correlation system performs the linear filtering, using a magnetooptic spatial light modulator as the input device and a computergenerated hologram in the filter plane. Thresholding is done electronically. By adjusting the value of the threshold, the same architecture is used to perform median, minimum, and maximum filtering of images.

Synthesis of digital holograms by direct binary search.

A new approach to the design of computer-generated holograms makes optimal use of the available device resolution. An iterative search algorithm minimizes an error criterion by directly manipulating the binary hologram and observing the effect on the desired reconstruction. Several measures of error and efficiency useful in assessing the optimality of digital holograms are defined. Methods for designing digital holograms that are based on projections and error diffusion are presented as established techniques for comparison to direct binary search.

Representation-related errors in binary digital holograms: a unified analysis.

Images reconstructed from binary digital holograms are degraded by errors due to the binary representation of the complex-valued object spectrum and by errors due to computational and plotter limitations. In this paper, representation-related errors are analyzed in terms of false images that appear in the desired reconstruction order and in adjacent diffraction orders. It is shown that the false images are strongly dependent on the manner in which the object spectrum is sampled and on the mapping from spectral sample to binary transmittance. Three categories of digital holograms are distinguished: those that sample the object spectrum at the center of each hologram cell; those that sample at the center of each aperture; and those that sample at each resolvable spot. In going from the first to the third category, the reconstruction is successively less degraded by false images. For the third category, there are no false images in the desired reconstruction order and only one false image in each adjacent order. The two methods in this category differ only in the suppression of these false images.

Binary display of images when spot size exceeds step size.

Many binary digital devices for display or printing of images are capable of placing spots of size S at an array of addressable points spaced R apart where S < R. A new representation is described for display or printing of continuous-tone images with such devices for which S/R < 2. The presentation takes into account spot overlap to assure correct tone reproduction, minimize pattern visibility, and maximize detail rendition. The algorithm is a modification of ordered dither that utilizes in one direction the subspot size addressibility of the device to increase the number of available levels of tone per unit area and enhance the good visual properties of the dither matrix. While not implementable by thresholding, the algorithm may be implemented by a nearly point-to-point spatially periodic mapping from continuous-tone image-to-device input. Fourier analysis provides a theoretical basis for the representation. Experimental work is presented that confirms the results of the analysis.

Computer-aided design of dither signals for binary display of images.

The quality of binary images displayed using ordered dither is strongly dependent on the spatial arrangement of the thresholds in the dither signal. In the frequency domain, this dependence may be viewed as a consequence of aliasing. A computer-aided approach to the design of dither signals that uses a pairwise exchange algorithm to minimize a measure of susceptibility to aliasing is described. The susceptibility measure may be chosen to take into account many factors that affect perceived image quality. Experimental results are presented that illustrate the potential of the method.

Aliasing error in digital holography.

The use of the discrete Fourier transform in digital holography introduces aliasing error in the reconstructed image. Spectrum shaping to reduce dynamic range may also result in a serious increase in aliasing error. The effect of aliasing in digital holography is analyzed. It is proposed that the bandwidth be constrained when shaping the image spectrum. Experimental results show the approach to be quite effective.

Minimax spectrum shaping with a bandwidth constraint.

A new approach to spectrum shaping, in which the maximum of the spectrum is minimized subject to a constraint on the bandwidth, is considered. The results can be applied to a variety of methods of digital holography. A lower bound for the maximum and a figure of merit are obtained. Practical methods for minimax shaping of the spectrum are described and compared via computer simulations. The results of these simulations indicate that the lower bound is relatively tight, and the figure of merit is a good one.