This work presents an approximate global optimization method for image halftone by fusing multi-scale information of the tree model. We employ Gaussian mixture model and hidden Markov tree to characterized the intra-scale clustering and inter-scale persistence properties of the detailed coefficients, respectively. The model of multiscale perceived error metric and the theory of scale-related perceived error metric are used to fuse the statistical distribution of the error metric of the scale of clustering and cross-scale persistence. An Energy function is then generated. Through energy minimization via graph cuts, we gain the halftone image. In the related experiment, we demonstrate the superior performance of this new algorithm when compared with several algorithms and quantitative evaluation.

This paper presents two halftoning methods to improve efficiency in generating structurally similar halftone images using Structure Similarity Index Measurement (SSIM). Proposed Method I reduces the pixel evaluation area by applying pixel-swapping algorithm within inter-correlated blocks followed by phase block-shifting. The effect of various initial pixel arrangements is also investigated. Proposed Method II further improves efficiency by applying bit-climbing algorithm within inter-correlated blocks of the image. Simulation results show that proposed Method I improves efficiency as well as image quality by using an appropriate initial pixel arrangement. Proposed Method II reaches a better image quality with fewer evaluations than pixel-swapping algorithm used in Method I and the conventional structure aware halftone methods.

We propose a method for halftoning grayscale images by drawing weighted centroidal Voronoi tessellations (WCVTs) with black lines on white image planes. Based on the fact that CVT approaches a uniform hexagonal lattice asymptotically, we derive a relationship of darkness between input grayscale images and the corresponding halftone images. Then the derived relationship is used for adjusting the contrast of the halftone images. Experimental results show that the generated halftone images can reproduce the original tone in the input images faithfully.

The error diffusion filter in this paper is optimized with respect to the ideal blue noise pattern corresponding to a single tone level. The filter coefficients are optimized by the minimization of the squared error norm between the Fourier power spectra of the resulting halftone and the blue noise pattern. During the process of optimization, the binary pattern power spectrum matching algorithm is applied with the aid of a new blue noise model. The number of the optimum filters is equal to that of different tones. The visual fidelity of the bilevel halftones generated by the error diffusion filters is evaluated in terms of a weighted signal-to-noise ratio, Fourier power spectra, and others. Experimental results have demonstrated that the proposed filter set generates satisfactory bilevel halftones of grayscale images.

Halftoning is an important process to convert a gray scale image into a binary image with black and white pixels. The Direct Binary Search (DBS) is one of the well-known halftoning methods that can generate high quality binary images for middle tone of original gray scale images. However, binary images generated by the DBS have clippings, that is, have no tone in highlights and shadows of original gray scale images. The first contribution of this paper is to show the reason why the DBS generates binary images with clippings, to clarify the range of tone in original images that may have clipping, and to present a clipping-free DBS-based halftoning algorithm. The key idea is to apply the ordered dither using a threshold array generated by DBS-based method, to highlights and shadows, and then use the DBS. The second contribution is to extend the DBS to generate L-level multitone images with each pixel taking one of the intensity levels , , ..., . However, clippings appear in highlights, middle tone, and shadows of generated L-level multitone images. The third contribution of this paper is to modify the multitone version of the DBS to generate a clipping-free L-level multitone images. The resulting multitone images are so good that they reproduce the tones and the details of the original gray scale images very well.

Self embedding watermarking is a technique used for tamper detection, localization and recovery. This letter proposes a novel self embedding scheme, in which the halftone version of the host image is exploited as a watermark, instead of a JPEG-compressed version used in most existing methods. Our scheme employs a pixel-wise permuted and embedded mechanism and thus overcomes some common drawbacks of the previous methods. Experimental results demonstrate our technique is effective and practical.

The main contribution of this work is to present several hardware implementations of an "n choose k" counter (C(n,k) counter for short), which lists all n-bit numbers with (n-k) 0's and k 1's, and to show their applications. We first present concepts of C(n,k) counters and their efficient implementations on an FPGA. We then go on to evaluate their performance in terms of the number of used slices and the clock frequency for the Xilinx VirtexII family FPGA XC2V3000-4. As one of the real life applications, we use a C(n,k) counter to accelerate a digital halftoning method that generates a binary image reproducing an original gray-scale image. This method repeatedly replaces an image pattern in small square regions of a binary image by the best one. By the partial exhaustive search using a C(n,k) counter we succeeded in accelerating the task of finding the best image pattern and achieved a speedup factor of more than 2.5 over the simple exhaustive search.

Digital halftoning is used to quantize a grayscale image to a binary image. Error diffusion halftoning generates a high-quality binary image, but also generates some defects such as the warm effect, sharpening, and so forth. To reduce these defects, Kite proposed a modified threshold modulation method that utilizes a multiplicative parameter for controlling sharpening. Nevertheless, some degradation was observed near the edges of objects with a large luminance change. In this paper, we propose a method of controlling the multiplicative parameter in proportion to the magnitude of the local edge slope. The results of computer simulation show a greater reduction of sharpening in the halftone image. In particular, there is a great improvement in the quality of the edges of objects with a large luminance change.

In this paper we propose an inter-block evaluation method to further reduce evaluation numbers in GA-based image halftoning technique. We design the algorithm to avoid noise in the fitness function by evolving all image blocks concurrently, exploiting the inter-block correlation, and sharing information between neighbor image blocks. The effectiveness of the method when the population and image block size are reduced, and the configuration of selection and genetic operators are investigated in detail. Simulation results show that the proposed method can remarkably reduce the entire evaluation numbers to generate high quality bi-level halftone images by suppressing noise around block boundaries.

An image halftoning technique that uses a simple GA has proven to be effective generating bi-level halftone images with quality higher than conventional techniques. Many devices are designed to handle more than two halftone levels and a GA based multi-level halftoning technique is desirable. In this paper we extend the bi-level halftoning technique to generate multi-level halftone images. Also we introduce an improved GA (GA-SRM) into the proposed multi-level halftoning technique. Experimental results show that the proposed technique can effectively generate high quality multi-level halftone images and that the inclusion of GA-SRM substantially contributes reducing memory usage and accelerating image generation.

This paper presents a new method of designing a dither matrix based on simulated annealing. An obtained dither matrix (halftone screen/mask) is appropriate for press printing. Because of several physical reasons, halftoning for press printing is more difficult than halftoning for electronic displays, or ink-jet printers. Even if stochastic dispersed-dot screening (so-called FM-screening) is one of the best solutions for halftoning, that is not appropriate for press printing. On the other hand, classical periodic clustered-dot screening (so-called AM-screening) is more important and is widely used even now. We recognize unfavorable quality of AM-screening, but we can not ignore its productive stability in printing section. The proposed halftone dither matrix has aperiodic clustered-dot pattern, and size of cluster can be controlled by a weighting parameter of a cost function. We will obtain a dither matrix which consists of clustered-dots. Some characteristics of the design algorithm and halftoned images are investigated in detail. As a result, the fact that an obtained dither matrix is superior to AM-screen and comparable to FM-screen in visual quality, and the matrix is comparable to AM-screen and superior to FM-screen in press printability is confirmed.

A halftoning technique that uses a simple GA has proven to be very effective to generate high quality halftone images. Recently, the two major drawbacks of this conventional halftoning technique with GAs, i.e. it uses a substantial amount of computer memory and processing time, have been overcome by using an improved GA (GA-SRM) that applies genetic operators in parallel putting them in a cooperative-competitive stand with each other. The halftoning problem is a true multiobjective optimization problem. However, so far, the GA based halftoning techniques have treated the problem as a single objective optimization problem. In this work, the improved GA-SRM is extended to a multiobjective optimization GA to simultaneously generate halftone images with various combinations of gray level precision and spatial resolution. Simulation results verify that the proposed scheme can effectively generate several high quality images simultaneously in a single run reducing even further the overall processing time.

This paper presents an accelerated image halftoning technique using an improved genetic algorithm with tiny populations. The algorithm is based on a new cooperative model for genetic operators in GA. Two kinds of operators are used in parallel to produce offspring: (i) SRM (Self-Reproduction with Mutation) to introduce diversity by means of Adaptive Dynamic-Block (ADB) mutation inducing the appearance of beneficial mutations. (ii) CM (Crossover and Mutation) to promote the increase of beneficial mutations in the population. SRM applies qualitative mutation only to the bits inside a mutation block and controls the required exploration-exploitation balance through its adaptive mechanism. An extinctive selection mechanism subjects SRM's and CM's offspring to compete for survival. The simulation results show that our scheme impressively reduces computer memory and processing time required to obtain high quality halftone images. For example, compared to the conventional image halftoning technique with GA, the proposed algorithm using only a 2% population size required about 15% evaluations to generate high quality images. The results make our scheme appealing for practical implementations of the image halftoning technique using GA.

This letter introduces a new digital halftoning technique based on error diffusion along a random space-filling curve. The purpose of introducing randomness is to erase regular patterns which tend to arise in an image area of uniform intensity. A simple algorithm for generating a random space-filling curve is proposed based on a random spanning tree and maze traversal. Some experimental results are also given.

Digital halftoning is a well-known technique in image processing to convert an image having several bits for brightness levels into a binary image consisting only of black and white dots. A great number of algorithms have been presented for this problem, some of which have only been evaluated just by comparison with human eyes. In this paper we formulate the digital halftoning problem as a combinatiorial problem which allows an exact solution with graph-theoretic tools. For this, we consider a d-dimensional grid of n := Nd pixels (d 1). For each pixel, we define a so-called k-neighborhood, k {0,...N - 1}, which is the set of at most (2k + 1)d pixels that can be reached from the current pixel in a distance of k. Now, in order to solve the digital halftoning problem, we are going to minimize the sum of distances of all k-neighborhoods between the original picture and the halftoned one. We show that the problem can be solved in linear time in the one-dimensional case while it looks hopeless to have a polynomial-time algorithm in higher dimension including the usual two-dimensional case. We present an exact algorithm for the one-dimensional case which runs in O(n) time if k is regarded to be a constant. For two-dimensional case we present fast approximation techniques based on space filling curves. An experimental comparison of several implementations of approximate algorithms proves that our algorithms are of practical interest.

This paper describes highly parallel analog image coding and decoding by cellular neural networks (CNNs). The communication system in which the coder (C-) and decoder (D-) CNNs are embedded consists of a differential transmitter with an internal receiver model in the feedback loop. The C-CNN encodes the image through two cascaded techniques: structural compression and halftoning. The D-CNN decodes the received data through a reconstruction process, which includes a dynamic current distribution, so that the original input to the C-CNN can be recognized. The halftoning serves as a dynamic quantization to convert each pixel to a binary value depending on the neighboring values. We approach halftoning by the minimization of error energy between the original gray image and reconstructed halftone image, and the structural compression from the viewpoints of topological and regularization theories. All dynamics are described by CNN state equations. Both the proposed coding and decoding algorithms use only local image information in a space inveriant manner, therefore errors are distributed evenly and will not introduce the blocking effects found in DCT-based coding methods. In the future, the use of parallel inputs from on-chip photodetectors would allow direct dynamic quantization and compression of image sequences without the use of multiple bit analog-to-digital converters. To validate our theory, a simulation has been performed by using the relaxation method on an 150 frame image sequence. Each input image was 256256 pixels whth 8 bits per pixel. The simulated fixed compression rate, not including the Huffman coding, was about 1/16 with a PSNR of 31[dB]35[dB].