Look-up table (LUT) method for inverse halftoning

In this paper we propose look-up table (LUT) based methods 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. The method is extremely fast (no filtering is required) and the PSNR and visual image quality achieved is comparable to the best methods known for inverse halftoning. The LUT inverse halftoning method does not depend on the specific properties of the halftoning method, and can be applied to any halftoning method. Then, an algorithm for template selection for LUT inverse halftoning is introduced. We demonstrate the performance of the LUT inverse halftoning algorithm on error diffused images and ordered dithered images. We also extend LUT inverse halftoning to color halftones.     

Wavelet-based inverse halftoning for error diffused halftones

This paper describes a technique for inverse halftoning based on the wavelet domain deconvolution that comprises Fourier-domain followed by wavelet-domain noise suppression, in order to benefit from the advantages of each of them. The proposed algorithm can be formulated as a linear deconvolution problem. In fact, we model such a gray-scale image to be the result of a convolution of the original image with a point spread function (PSF) and a colored noise. Our method performs inverse halftoning by first inverting the model specified convolution operator and then attenuating the residual noise using scalar wavelet-domain shrinkage. Using simulations, we verify that the proposed method is competitive with state-of-the-art inverse halftoning techniques in the mean-square-sense and that has also good visual performance. We illustrate the results with simulations on some examples.     

An adaptive inverse halftoning algorithm

A class of inverse halftoning algorithms that recovers grayscale (continuous-tone) images from halftone images is proposed. The basic structure is an optimized linear filter. Then, a properly designed adaptive postprocessor is employed to enhance the recovered image quality. Finally, a multistage space-varying algorithm is developed that uses the basic linear filter structure as before but with spatially adaptive parameters.     

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.     

Enhancing inverse halftoning via coupled dictionary training

Inverse halftoning is a challenging problem in image processing. Traditionally, this operation is known to introduce visible distortions into reconstructed images. This paper presents a learning-based method that performs a quality enhancement procedure on images reconstructed using inverse halftoning algorithms. The proposed method is implemented using a coupled dictionary learning algorithm, which is based on a patchwise sparse representation. Specifically, the training is performed using image pairs composed by images restored using an inverse halftoning algorithm and their corresponding originals. The learning model, which is based on a sparse representation of these images, is used to construct two dictionaries. One of these dictionaries represents the original images and the other dictionary represents the distorted images. Using these dictionaries, the method generates images with a smaller number of distortions than what is produced by regular inverse halftone algorithms. Experimental results show that images generated by the proposed method have a high quality, with less chromatic aberrations, blur, and white noise distortions.     

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.     

Local linear LUT method for spatial colour-correction algorithm speed-up

There is a class of nonlinear filtering algorithms for digital colour enhancement, characterised by data-driven local effects and high computational cost. A new method called LLL (local linear look-up table (LUT)) is presented, which speeds up these filters without losing their local effect. Usually, classic LUT-based methods are global whereas the approach presented here uses the principles of LUT transformation in a local way. The main idea of this method is to apply the colour-enhancement algorithm to a small sub-sampled version of the input image and to use a modified look-up table technique to maintain the local filtering effect of the colour-enhancement algorithm. The method increases the speed of colour-filtering algorithms, reducing the number of pixels involved in the computation by sub-sampling the input image. To overcome possible loss of detail due to sub-sampling, an optional, additional stage to maintain high-frequency content is shown. LLL with two of these filters, the Brownian Retinex implementation and the automatic colour equalisation algorithm, are tested. Results, comparison and conclusions are presented.     

A secure fingerprint template generation mechanism using visual secret sharing with inverse halftoning

Fingerprints are the most popular and widely practiced biometric trait for human recognition and authentication. Due to the wide approval, reliable fingerprint template generation and secure saving of the generated templates are highly vital. Since fingers are permanently connected to the human body, loss of fingerprint data is irreversible. Cancelable fingerprint templates are used to overcome this problem. This paper introduces a novel cancelable fingerprint template generation mechanism using Visual Secret Sharing (VSS), data embedding, inverse halftoning, and super-resolution. During the fingerprint template generation, VSS shares with some hidden information are formulated as the secure cancelable template. Before authentication, the secret fingerprint image is reconstructed back from the VSS shares. The experimental results show that the proposed cancelable templates are simple, secure, and fulfill all the properties of the ideal cancelable templates, such as security, accuracy, non-invertibility, diversity, and revocability. The experimental analysis shows that the reconstructed fingerprint images are similar to the original fingerprints in terms of visual parameters and matching error rates.     

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.     

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.     

On the phase response of the error diffusion filter for imagehalftoning

Conventional error diffusion halftoning uses a causal error filter. We propose the iterative error diffusion algorithm by extending the error diffusion to accommodate noncausal error filters. We realize the importance of the phase response of the error filter in the error diffusion halftoning method, and demonstrate it using examples. Iterative error diffusion is able to realize a zero phase error filter. We also trace a drawback of error diffusion to the shape of the error filter, and provide a remedy. The results obtained using a zero phase error filter in the iterative error diffusion algorithm are, in our opinion, superior to the error diffusion halftones.     

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.     

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.     

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.     

Training Classifiers for Tree-structured Categories with Partially Labeled Data

In this paper we propose a new method for training classifiers for multi-class problems when classes are not (necessarily) mutually exclusive and may be related by means of a probabilistic tree structure. It is based on the definition of a Bayesian model relating network parameters, feature vectors and categories. Learning is stated as a maximum likelihood estimation problem of the classifier parameters. The proposed algorithm is specially suited to situations where each training sample is labeled with respect to only one or part of the categories in the tree. Our experiments on information retrieval scenarios show the advantages of the proposed method.     

LUT filters for quantized processing of signals

We introduce a method to perform filtering on approximations (quantized versions) of the input signal, which lends itself to a practical implementation solely based on look-up tables (LUTs). The LUT filter approximates the performance of some traditional nonlinear filters at a fraction of the cost. The filter is divided into an approximation stage that is constant for all filters and a filtering stage, which is one LUT that can change in order to implement different filters. We introduce an overlapped hierarchical vector quantization (OHVQ) scheme that is used as the approximation stage. The output is produced by mapping the OHVQ codes to filtered data. Hence, all processing is done via LUTs, even though the filter size needs to be small because of typical OHVQ contraints. Switching among filters demands changing pointers to only one small LUT. Preliminary analysis and image processing examples are shown, demonstrating the efficacy of the proposed method.     

Two-step inverse scattering method for one-dimensional permittivityprofiles

A numerical method to invert the dielectric permittivity profile from the Riccati equation using the Newton-Kantorovich iterative scheme is described. Instead of handling the equations in terms of usual geometrical depth, we determine the profile as a function of the electromagnetic path length since the convergence and the stability of the solution are found to be significantly better in this case. The initial profile used as a starting point for the inversion is obtained by another method employing successive reconstruction of dielectric interfaces and homogeneous layers in a step-like form. This method, though not always accurate, is fast and well suited for the approximate reconstruction of the profile, thus creating ideal starting conditions for the previous approach. As a result, the computation time is considerably reduced, without using any a priori information. The approach is applicable to both continuous and discontinuous profiles of high contrast and exhibits a good stability of the solution with respect to noisy input data. A lossy medium profile can also be inverted provided the overall thickness of the inhomogeneous slab and the background permittivity are known     

Blue and green noise halftoning models

In this article, we review the spatial and spectral characteristics of blue- and green-noise halftoning models. In the case of blue noise, dispersed-dot dither patterns are constructed by isolating minority pixels as homogeneously as possible, and by doing so, a pattern composed exclusively of high-frequency spectral components is produced. Blue-noise halftoning is preferred for display devices that can accommodate isolated dots such as various video displays and some print technologies such as ink-jet. For print marking engines that cannot support isolated pixels, dispersed-dot halftoning is inappropriate. For such cases, clustered-dot halftoning is used to avoid dot-gain instability. Green-noise halftones are clustered-dot, blue-noise patterns. Such patterns enjoy the blue-noise properties of homogeneity and lack low-frequency texture but have clusters of minority pixels on blue-noise centers. Green noise is composed exclusively of midfrequency spectral components. In addition to the basic spatial and spectral characteristics of the halftoning models, this article also reviews some of the earlier work done to improve error diffusion as a noise generator. We also discuss processes to generate threshold arrays to achieve blue and green noise with the computationally efficient process of ordered dither.