ちょっと仕事で adaptive sampling のアレをナニする感じのことを考えていて、ふとヒルベルト曲線順にグリッドを巡回して、素数のインデックスに対応する点にサンプリング点を置いたらイイ感じになるんじゃないかなーと思いついて実験したので書き残しておきます。きっとこのくらいのことは既に誰かが考えているんじゃないかと思うのでご存知でしたら教えてください。
ヒルベルト曲線
ヒルベルト曲線とは一般的により高次元な空間を一筆書きのように巡回する曲線(曲線といってもカクカク曲がってますが)です。日本語のWikipediaの項目 にはあまり情報がないですね……。英語版Wikipediaの項目のほうが多少情報が多いです。まあ2次元だとこのように 2^n 四方のグリッドを、必ず隣合うグリッドを繋ぎながら(4近傍、つまり斜めに跳ぶのはなし)全ての点を通るような辿りかたを作ることができます。
たとえば 1024x1024 のグリッド(2^10 四方)だと次数10のヒルベルト曲線で全てのグリッドを巡回できるので、それぞれのグリッドに連番(インデックス)を振ることができます。このインデックス*1が素数の時にそこにサンプリング点を置くことにします。
という手順で作ってみたのが以下の画像です。1024x1024 でサンプリング点のピクセルを黒い点にしています。
さてこのサンプリング点の分布の性質はどうでしょうか。ためしに同じ頻度になるようにランダムな確率でサンプリング点を置いた画像を作ってみました。
そして両者を 2次元フーリエ変換してみます。
まずランダムにサンプリング点を配置したほう。
ホワイトノイズのような結果ですね。方向にも空間周波数成分にもあまり偏りがありません。あたりまえですけど。
次にヒルベルト曲線と素数を使ったサンプリング点の配置のフーリエ変換結果。
なんというか、独特のムラと、グリッド状のピークが見てとれます。中央にあるピークは画像が全体的に明い(サンプリング点の密度は 8% くらい)なのでそのために全体の底上げのために必要なのではないかと思います。それを除けば低周波成分はやや少ないのでこの点は良い*2ものの、ピークのパターンが見えるのはエイリアシングの原因になるかもしれないので、あまりいい性質ではないかもしれませんね。残念です。
なおこの実験では一様に 1024x1024 のグリッドを使いましたが、ヒルベルト曲線は再帰的に生成できるので、局所的な importance に応じてヒルベルト曲線の次数を上げることで adaptive なサンプリング点配置ができるんじゃないかと思います。というかそれができるから何か adaptive sampling に利用できないかなぁと思って「素数なら、素数なんとかしてくれる」とやってみたのでした。
