Deterministic Blue Noise Sampling by Solving Largest Empty Circle Problems

Yoshihiro Kanamori, Zoltan Szego and Tomoyuki Nishita

University of Tsukuba / The University of Tokyo


Abstract:

Sampling patterns with a blue noise distribution are widely used in many areas of computer graphics, yet their efficient generation remains a difficult problem. We propose a method to generate point sets with a blue noise distribution using a deterministic algorithm with no preprocessing. We insert each new sample at the center of the largest empty circle in the point set, which is obtained by calculating the Delaunay-triangulation of the set and finding the triangle with the largest circumcircle. Our method supports adaptive sampling according to a user-specified density function, as well as specifying the exact number of required samples. It can also be extended to perform sampling on a three-dimensional curved surface.

Keywords: Blue noise sampling, Delaunay triangulation, halftoning

Publications:

  1. Yoshihiro Kanamori, Zoltan Szego, Tomoyuki Nishita: "Deterministic Blue Noise Sampling by Solving Largest Empty Circle Problems," Journal of IIEEJ, Vol.40, No.1, 2011-1. [PDF]
  2. Zoltan Szego, Yoshihiro Kanamori, Tomoyuki Nishita: "Blue Noise Sampling via Delaunay Triangulation," IEVC2010 (IIEEJ Image Electronics and Visual Computing Workshop 2010), 2010-3 [PPTX] (Best Presentation Award).

Last modified: 4 March, 2011

[back]