Poisson Disk Sampling による Image Stippling

Poisson disk samplingによるimage stipplingを実装してみました．

Stipplingとは

Stipplingとは点のパターンで画像を表現することです．
アートの世界では点刻と呼ばれているようです．
このような画像をコンピュータで生成するには
画像の輝度値のような与えられた値にたいして点の密度を変えることが必要となります．
ここでPoisson Disk Samplingが登場します．

Poisson Disk Sampling とは

ランダムかつ点同士がある距離以上離れているようなサンプリングをPoisson Disk Samplingと呼びます．
blue noise property
もともとは画像をレンダリングする際のantialiasingのための技術で，
CGの分野では"Stochastic sampling in computer graphics"で初めて登場しました．
この中で著者はpoisson disk samplingを周波数的に解析し（ローパスフィルタを打ち消すような周波数特性になっている），
なぜantialiasingとして有効なのかを議論しています．
猿の目のphotoreceptorの配置も規則的ではなくblue noise samplingのような配置になっているそうです．

antialiasing以外にもimage stipplingやtexture synthesisなど様々な応用があります．
Poisson disk samplingの周波数はblue noiseというカテゴリに属し，
Poisson disk samplingを含んだblue noiseの生成方法の研究はComputer Graphicsの分野でホットなトピック
となっています．

実現方法

Poisson disk samplingを実現する手法として大きく2つに分けられます．

Dart throwing

これはその名の通りダーツを投げるようにある領域に対しランダムに点を発生させ，その点を中心とする円の内部に点が存在しない場合，その点を採用するという手順を繰り返すことで分布を発生させます．

Fast Poisson Disk Sampling in Arbitrary Dimensions

任意の次元で高速にサンプリングする方法を提案しています．

Voronoi graph

とても多いので最新のものを幾つか挙げておきます．

Variational blue noise sampling

Centroidal Voronoi tessellationのエネルギー + Capacity Constrained Voronoi tessellationのエネルギーを目的関数とするCapacity-constrained-centroidal voronoi tessellationを提案