Halftoning |
|||||||||||||
Home |
Motivation
Many devices such as printers and fax machines can often create only pure
black and white images. To represent intermediate grey values, it is
necessary to virtually increase the range of such devices by using a
halftoning algorithm.
Our Contributions
Lattice-Boltzmann Model Encoding of directions in LB framework Our first contribution [1] is an iterative dithering algorithm by use of a lattice Boltzmann framework. Lattice Boltzmann methods have been introduced as an alternative numerical method for simulating fluid dynamics. In our approach we assume that grey values are small particles. Lattice Boltzmann models are able to model transitions between discrete grid points in an iterative scheme on a microscopic level that effect the result on a macroscopic level.
Our transitions are based on local gradients such that we allow a flow of
particles towards pixels with higher grey value and block flow in opposite
direction. With this setting it is possible to bring pixels to desirable
states such as black or white states. After convergence of the iterative
scheme we perform a thresholding for pixels that were not binarised.
By construction of this framework, we are able to give an iterative
rotationally invariant dithering algorithm. Furthermore, the embedding into
the lattice Boltzmann framework allows to derive a macroscopic formulation,
from which follows that our method employs a diffusion-advection equation. Electrostatic Halftoning
Our halftoning approach in [2] models black dots in the image by charged particles which repel each other, but are attracted by grey values in the image. It is motivated by the fact that, for regions of constant density, e.g. regions of constant grey value in an image, black points in the resulting image shall be equally distributed. Repulsion between particles First, let us focus on a uniform grey image. We initialise the solution with a random distribution of the desired number of black pixels. Next, we regard these pixels as small charged particles within a 2-D particle system on a bounded domain. As a consequence of electrostatic laws, these particles repulse each other. If we simulate the evolution of the system for some time, particles will move such that their relative distances are maximised. In the end, this gives us a uniform distribution of particles in the specified domain: We obtain a halftoned image. Attraction by grid points The system described so far cannot create halftones of images with more than one grey value. However, this drawback can easily be remedied: At all grid positions, we introduce stationary charges that are proportional to the grey value of the respective pixel of the input image. These "invisible" particles attract moving charges and thus control the number of black pixels within any region. Resulting forces on particles
Finally, we regard both attractive and repulsive forces during the evolution
of the image. This yields an appealing halftoning result where both
constant regions and edges in the image are synthesised. Since the
overall system is designed to be electrically neutral, it allows a
a precise reproduction of all grey values in both dithering and
stippling applications.
Publications
|
||||||||||||
MIA Group |