Manuel Gräf, Daniel Potts, Gabriele Steidl : Quadrature errors, discrepancies and their relations to halftoning on the torus and the sphere

Author(s):

Manuel Gräf
Daniel Potts
Gabriele Steidl

Title:

Quadrature errors, discrepancies and their relations to halftoning on the torus and the sphere

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 05, 2011

Mathematics Subject Classification:

65T40	[]
65K10	[]
53B21	[]
49M15	[]
33C55	[]

Abstract:

This paper deals with a special halftoning process, also called stippling, which aims to create the illusion of a gray-value image by appropriately distributing black dots. Recently a framework for this task was proposed by minimizing an attraction-repulsion functional consisting of the difference of two continuous, convex functions. One of them describes attracting forces caused by the image gray values, the other one enforces repulsion between dots. In this paper, we generalize this approach by considering quadrature error functionals on reproducing kernel Hilbert spaces (RKHSs) with respect to the quadrature nodes, where we ask for optimal distributions of these nodes. For special reproducing kernels these quadrature error functionals coincide with discrepancy functionals. It turns out that the attraction-repulsion functional appears for a special RKHS of functions on R2. Moreover, our more general framework enables us to consider optimal point distributions not only in R2 but also on the torus T2 and the sphere S2. For a large number of points the computation of such point distributions is a serious challenge and requires fast algorithms. To this end, we work in RKHSs of bandlimited functions on T2 and S2. Then the quadrature error functional can be rewritten as a least squares functional. We propose a nonlinear conjugate gradient method to compute a minimizer of this functional and show that each iteration step can be computed in an efficient way by fast Fourier transforms at nonequispaced nodes on the torus and the sphere. Numerical examples demonstrate the good halftoning results obtained by our method.

Keywords:

Halftoning, dithering, stippling, point distributions, quadrature rules, discrepancies, optimization methods on Riemannian manifolds, CG method, nonequispaced fast Fourier transform, spherical Fourier transform.

Language:

English

Publication time:

02/2011