Dithering by Differences of Convex Functions

Teuber, Tanja ; Steidl, Gabriele ; Gwosdek, Pascal ; Schmaltz, Christian ; Weickert, Joachim

dithering_journal_pdflatex_rev.pdf - Published

Download (15MB)

URL: https://ub-madoc.bib.uni-mannheim.de/2893
URN: urn:nbn:de:bsz:180-madoc-28939
Document Type: Working paper
Year of publication: 2010
The title of a journal, publication series: Preprints / Department of Mathematics
Volume: 10-01
Place of publication: Mannheim
Publication language: English
Institution: School of Business Informatics and Mathematics > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC publication series: Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Mathematik > Preprints
Subject: 510 Mathematics
Subject headings (SWD): Bildverarbeitung , Nichtkonvexe Optimierung
Keywords (English): Dithering , halftoning , DC programming , NFFT , fast summation
Abstract: Motivated by a recent halftoning method which is based on electrostatic principles, we analyse a halftoning framework where one minimizes a functional consisting of the difference of two convex functions (DC). One of them describes attracting forces caused by the image gray values, the other one enforces repulsion between points. In one dimension, the minimizers of our functional can be computed analytically and have the following desired properties: the points are pairwise distinct, lie within the image frame and can be placed at grid points. In the two-dimensional setting, we prove some useful properties of our functional like its coercivity and suggest to compute a minimizer by a forward-backward splitting algorithm. We show that the sequence produced by such an algorithm converges to a critical point of our functional. Furthermore, we suggest to compute the special sums occurring in each iteration step by a fast summation technique based on the fast Fourier transform at non-equispaced knots which requires only Ο(m log(m)) arithmetic operations for m points. Finally, we present numerical results showing the excellent performance of our DC dithering method.
Additional information: The authors Gwosdek, Schmaltz and Weickert are with the Mathematical Image Analysis Group, Faculty of Mathematics and Computer Science, Saarland University. This Version: April 29, 2010

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.

Metadata export


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item