Digital Halftoning Algorithms Based on Optimization Criteria and Their Experimental Evaluation (Special Section on Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
Digital halftoning is a well-known 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 combinatorial problem which allows an exact so1ution with graph-theoretic tools. For this, we consider a d-dimensional grid of n≔N^d pixels (d≦1). For each pixel, we define a so-called k-neighborhood, 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 prob1em, we are going to minimize the sum of distances of all k-neighborhoods between the original picture and the halftoned one. We show that the problem can be solved in linear time in the one-dimensional case while it looks hopeless to have a polynomial-time algorithm in higher dimension including the usual two-dimensional case. We present an exact algorithm for the one-dimensional case which runs in O(n) time if k is regarded to be a constant. For two-dimensional 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.
社団法人電子情報通信学会の論文
1996-04-25

Digital Halftoning Algorithms Based on Optimization Criteria and Their Experimental Evaluation (Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク