NDLI: Quadrature Errors, Discrepancies, and Their Relations to Halftoning on the Torus and the Sphere

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Gräf, Manuel Steidl, Gabriele Potts, Daniel
Copyright Year	2012
Abstract	This paper deals with continuous-domain quantization, which aims to create the illusion of a gray-value image by appropriately distributing black dots. For lack of notation, we refer to the process as halftoning, which is usually associated with the quantization on a discrete grid. Recently a framework for this task was proposed by minimizing an attraction-repulsion functional consisting of the difference of two continuous, convex functions. The first one of these functions describes attracting forces caused by the image gray values, the second one enforces repulsion between the 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, which leads to a geometric interpretation. It turns out that the original attraction-repulsion functional appears for a special RKHS of functions on $\mathbb R^2$. Moreover, our more general framework enables us to consider optimal point distributions not only in $\mathbb R^2$ but also on the torus $\mathbb T^2$ and the sphere $\mathbb S^2$. 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 $\mathbb T^2$ and $\mathbb S^2$. Then the quadrature error functional can be rewritten as a least squares functional. We use 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 quantization results obtained by our method.
Starting Page	A2760
Ending Page	A2791
Page Count	32
File Format	PDF
ISSN	10648275
DOI	10.1137/100814731
e-ISSN	10957197
Issue Number	5
Volume Number	34
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2012-10-18
Access Restriction	Subscribed
Subject Keyword	halftoning Spherical harmonics quadrature rules Trigonometric approximation and interpolation stippling spherical Fourier transform Poisson disk distribution discrepancies Methods of Riemannian geometry Optimization and variational techniques point distributions CG method nonequispaced fast Fourier transform Newton-type methods optimization methods on Riemannian manifolds dithering
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in