Floyd-Steinberg Error diffusion [R.A. Ulichney, Digital Halftoning. Cambridge, MA: MIT Press, 1987.].
and their original gray-scale images.
References for Toggle/Swap and Toggle-Only schemes:
D.J. Lieberman and J.P. Allebach, ``A dual interpretation for direct binary search and its implications for tone reproduction and texture quality,''
IEEE Trans. Image Processing, vol. 9, pp. 1950-1963, Nov. 2000.
D.J. Lieberman and J.P. Allebach, ``Efficient model based halftoning using direct binary search,''
J. Electron. Imag., submitted for publication.
T.N. Pappas and D.L. Neuhoff, ``Least-squares model-based halftoning,''
IEEE Trans. Image Processing, vol. 8, pp. 1102-1116, Aug. 1999.
Initial halftone image with random image [see images below].
Run Simplified Grid algorithm described in Section 2 and 3 of the paper with row-column activation schedule for 10 iterations.
Output halftone image is the binary image at 10th iteration.
For this experiment:
Human visual system corresponding to halftone image is a Gaussian filter with standard deviation = 1.5 truncated to 9x9.
Human visual system corresponding to original gray-scale image is a Gaussian filter with standard deviation = 0.9 truncated to 5x5.
No complexity reduction by exploiting filter- and image- dependency such as symmetry of filters and initial images for fast convergence.
Toggle/Swap & Toggle-Only algorithms
Initial halftone image with random image [see images below].
Run Toggle/Swap or Toggle-Only algorithm using DBS approach as described in of the reference 2 (Lieberman and Allebach) above and
process until the image converges.
Output halftone image is the binary image at convergence.
For this experiment:
Human visual systems are the same as Simplifed Grid algorithm.
The DBS approach using here is refered as orginal version in the reference 2 above.
with modification for 2 different filters of human visual systems (i.e., for halftone and original gray-scale images). Note that, authors use the same filters in the reference paper.
In other words, there is no complexity reduction by exploiting filter- and image- dependency such as symmetry of filters and initial images for fast convergence.
Image is processed in the raster-scan manner without using the any kind of block processing.
Note:
Most techniques in DBS approach to reduce the complexity and accelerate the speed of Toggle/Swap or Toggle-Only algorithms can also be used in the Grid algorithm.
Therefore, we expect our algorithm, once filter- and image-dependent optimizations have been corporated, to operate at least at a comparable speed comparing with DBS approach.
For the experiments, we try to optimize the programs for Simplified Grid, Toggle-Swap, and Toggle-Only algorithms in order to make these programs operate as fast as possible.
However, we do not guarantee that our programs are the best for each technique.
Floyd-Steinberg Error diffusion: This is done in Sun Ultra-30 (using SunOS 5.6).
Use command rawtopgm to create .pgm (portable graymap) file from raw image file.
Use command pgmtopbm to create .pbm (portable bitmap) file from .pgm file using Floyd-Steinberg error diffusion.
Create raw binary (error diffusion) image file from .pbm file.
Comment on measurements (metric & speed)
"Metric" or the measure of distortion is the square error metric between halftone and original gray-scale images averaged per pixel over the whole image except the first 5 pixels from the image boundary.
"Speed" is measured as the CPU time difference (Sun Ultra-30) between the beginning and ending of halftoning processes without counting
the required running time for initialzation (e.g., table initialzation for toggle-swap or DBS).
Instruction for viewing images and animations
Click each thumbnail to view the details of each image.
Click the word Click for Animation to see the (successive) iterative process until process is terminated.
Note that all iterative process will begin with the initial random binary image and the process will be looped so that it will restart after it ends.
Moreover, each iteration will be hold for 1 second and the last iteration will be hold for 2 seconds.
