
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Digital Halftoning Algorithms Based on Optimization Criteria and Their Experimental Evaluation
Tetsuo ASANO Desh RANJAN Thomas ROOS
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E79A
No.4
pp.524532 Publication Date: 1996/04/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: discrete algorithm, combinatiorial optimization, digital halftoning, computational complexity, experimental evaluation,
Full Text: PDF(1002.5KB)>>
Summary:
Digital halftoning is a wellknown 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 graphtheoretic tools. For this, we consider a ddimensional grid of n := N^{d} pixels (d 1). For each pixel, we define a socalled kneighborhood, 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 kneighborhoods between the original picture and the halftoned one. We show that the problem can be solved in linear time in the onedimensional case while it looks hopeless to have a polynomialtime algorithm in higher dimension including the usual twodimensional case. We present an exact algorithm for the onedimensional case which runs in O(n) time if k is regarded to be a constant. For twodimensional 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.


