AG 1, AG 2, AG 3, AG 4   Info

MPI Audience

60 Minutes

Saarbrücken

Digital halftoning is an important technique to convert a continuous-tone image into a black-and-white binary image which looks similar to an input image. A number of algorithms have been proposed for beatiful and pleasent output pictures. They have been evaluated mainly by human visual comparisons based on experiments for several standard images.

I this talk I will talk about algorithmic aspects of the
digital halftoning. You will see surprisingly many different
topics on algorithms and discrete geometry are related to it.

A main topics is to define an optimally halftoned image based
on some mathematical criterion. In this talk the similarity
between two images is measured by the total sum of differences
in the weighted sums of brightness levels of pixels in a
neighborhood surrounding each pixel. Then, the problem of
producing an optimally halftoned image becomes a combinatorial
optimization problem to find a binary image minimizing this
measure for a given multiple-level image. Despite a negative
result that it is NP-complete even for a simple neighborhood
consisting of $2\times 2$ pixels, we can rely on approximation
algorithms mainly based on network flow algorithms.

Kurt Mehlhorn

--email hidden

passcode not visible

logged in users only

Approximation algorithm, Combinatorial optimization, Computational geometry, Digital geometry, Discrete packing problem, Discrepancy, Dispersion, Feasible flow, Integer linear programming, Integrality theorem on flow, Matrix rounding, Minimum-cost flow, Network flow, Pick's theorem, Scaling algorithm, Space-filling curves, Tiling pattern.