Japan Advanced Institute of Science and Technology
Computational Geometric and Combinatorial Approaches to Digital Halftoning
Abstract
Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. In this talk I will explain how computational geometry and combinatorial optimization can contribute to digital halftoning or what geometric and combinatorial problems are related to digital halftoning.
Extended abstract
There are two different techniques in digital halftoning. A cluster-dot halftoning reproducing continuous tone by changing the sizes of clusters has been commonly used in offset printing. Since a cluster consists of a number of small dots, fine control on the number of dots (cluster size) is required to reproduce a natural tone. Consequently, the cluster size becomes large, which degrades effective resolution. On the contrary, if we kept cluster size small to increase the effective resolution, then effective tone scale would be degraded. Thus, there is a trade-off between effective resolution and effective tone scale. It was hard to balance these indices, especially in the case of low resolution printers. In this talk, we propose an adaptive algorithm which arranges or grows clusters according to spatial frequency of the cluster-dot halftoning using geometric optimization algorithm.
Optimization of a dither mask used in a so-called Ordered Dither algorithm for halftoning is also an interesting topic. The problem is how to arrange n2 integers from 0 to n2-1 as uniformly as possible over an nxn matrix. Again we introduce a discrepancy-based measure to evaluate the uniformity. The measure is based on the observation that if those integers are uniformly distributed over a matrix then the average of elements in a rigid submatrix (or region) of a fixed size must be the same wherever we take such a submatrix. So, we define the discrepancy of a matrix to be the largest difference of the average in such a region with the average in the whole matrix.
We present different schema to achieve low discrepancy for a family of square regions. More concretely, we prove that the discrepancy for a family of 2x2 regions can be 0 if and only if the matrix size is even. For families of larger regions we have a result that the discrepancy of a k2xk2 matrix for kxk regions can be 0 while it cannot be 0 if the matrix size n and region size k are relatively prime.