CATS Keynote Speaker
Professor Tetsuo Asano

Japan Advanced Institute of Science and Technology

Computational Geometric and Combinatorial Approaches to Digital Halftoning


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 n x n 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.


Prof. Tetsuo Asano was born in Kyoto Prefecture, Japan, in 1949. He got B.E., M.E., and Ph.D degrees from Osaka University, Japan, in 1972, 1974, and 1977, respectively.

In 1977 he joined Osaka Electro-Communication University as a lecturer and moved to JAIST (Japan Advanced Institute of Science and technology) in 1997. He is now a professor in School of Information Science.

He served as a Presidential Advisor in 1999-2000 and as a senator in 2001-2003. His research interest includes algorithms and data structures, especially in computational geometry, combinatorial optimization, computer graphics, computer vision using geometric information, and VLSI layout design.

He has been serving as editor of several journals including Discrete and Computational Geometry, Computational Geometry: Theory and Applications, International Journal of Computational Geometry and Applications, and Theory of Computing Systems.

He has contributed to ACM Annual Symposium on Computational Geometry as a program committee member in 1990, 1994, 1996, and 2004. He served as a chair of a Special Interest Group on Algorithms of Information Processing Society of Japan in 1994-1996. He is a Fellow of the Association of Computing Machinery (2001) and Information Processing Society of Japan (2004).

Copyright © 2005 - ACSW 2006 Organising Committee
Site Credits