faster octree color quantization

256色画像全盛期はとっくに過ぎ去った感がありますが、今回は画像を256色以下に減色するという話です。減色された画像の画質を向上させる方法として誤差拡散法がありますが、今回はそれはやりません。

減色する方法は大昔から研究されていて有名なものがいくつかあります。

• 均等量子化法 (uniform quantization)
  • RGB888などをRGB332などにマッピングする
  • 高速、単純、簡易、だが画質は低い
• 頻度法 (popularity algorithm)
  • 画素の出現頻度からパレットを作成する
  • 画質はいまいち
• 中央値分割法 (median cut algorithm)
  • 一時は最強と呼ばれていた手法
  • 色空間を二分していく
  • 複雑だが割と高速で割ときれい
  • 色空間はRGBよりもYCbCrで分割する方がよいはず
• 八分木 (octree algorithm)
  • 現在最強の手法
  • モダンで簡潔で高速できれい
  • 以下の文書とソースコードが分かりやすい
    • http://www.microsoft.com/msj/archive/S3F1.aspx
    • http://www.microsoft.com/msj/archive/s3f1a.htm
    • http://www.leptonica.com/papers/colorquant.pdf

今回はoctreeをやります。画質を追求するのはImage Magickなどがやっていますので、速度を追求してみましょう。octreeの計算量は、画像の横幅をW、縦幅をH、深さをDとすると、O(W*H*D)となります。試した限りだと、octreeだと深さが4〜5程度で画像を人が認識するには十分な画質が得られますが、いかんせんループ回数が多すぎます。ピクセル処理なのにボクセル処理してるみたいな計算量です。

量子化ループの最適化その１

octreeのループ処理のコードを見ると、同じ画素に対しては全く同じ処理が繰り返されるということが分かります。これを利用した最適化を考えます。画像のヒストグラムを求めることができれば、画像の色数分だけのループで済みそうですね。画像の色数Cは、必ずC<=W*H以下になるので、計算量は必ず最適化前よりも小さくなります。

画像の色数分だけループする方法に処理を書き換えるには、画像のヒストグラムを求める必要があります。画像の画素をソートすることで画像のヒストグラムを求めることができますが*1、ソートは割とコストがかかるので高速化には使えません*2。よって、真面目にヒストグラムを計算する方が良さそうです。しかし、真面目にヒストグラムを計算すると大量にメモリが必要になります。RGB888で、ヒストグラムの各要素を符合なし整数で管理すると、2^24*4で64MBものメモリが必要になってしまいます。最近の端末やサーバなら余裕な気もしますが、長いことクライアントアプリを作ってきた私の感覚的にはメモリを使い過ぎですし、色数が1677万色もあると最悪で65536x65536の画像に相当する処理をやらないといけなくなるので高速化できるのかが不安になってきます。というわけで、精度を落とすことを考えてみましょう。

• RGB888 -> 2^24*4 -> 64MB (65536x65536程度の画像に相当する)
• RGB777 -> 2^21*4 -> 8MB (2896x2896程度の画像に相当する)
• RGB666 -> 2^18*4 -> 1MB (1024x1024程度の画像に相当する)
• RGB565 -> 2^16*4 -> 256KB (512x512程度の画像に相当する)
• RGB555 -> 2^15*4 -> 128KB (362x362程度の画像に相当する)
• RGB444 -> 2^12*4 -> 16KB (128x128程度の画像に相当する)

感覚的にRGB666程度なら精度的にも速度的にも空間的にもよさそうですね。実際に試してみたところ、手元のマシンで処理時間を30〜50ミリ秒程度から10ミリ秒以下まで削減できました。いいですね。しかし、高速化前と結果が異なります。高速化前の方が画質がいいです。これは高速化+RGB888でやっても高速化前の画質に劣ります・・・。せっかくのoctreeが台無しで残念ですね。

量子化ループの最適化その２

ノードキャッシュ

octreeは動的に八分木のノードに使うメモリを確保・破棄します。確かに空間的な効率はいいです。単発呼び出しなら。ただし、繰返し呼び出すとメモリの断片化が起こってOSにあまり優しくない気がします。優しくないのは紳士的ではありませんので、優しくできないかを考えてみましょう。小さいメモリの確保・破棄が連続すると断片化が発生しやすいですが、確保・破棄がなければ断片化は発生しません。ノードをプールしておけばいいわけですね。ではいくつプールしておけばいいでしょうか？これは八分木の深さによります。それぞれの深さのノードがいくつ存在しうるかを考えてみましょう。

• 深さ 0 -> ノード数 1
• 深さ 1 -> ノード数 8
• 深さ 2 -> ノード数 64
• 深さ 3 -> ノード数 512
• 深さ 4 -> ノード数 4096 (4K)
• 深さ 5 -> ノード数 32768 (32K)
• 深さ 6 -> ノード数 262144 (256K)
• 深さ 7 -> ノード数 2097152 (2MB)
• 深さ 8 -> ノード数 16777216 (16MB)

上で深さ4〜5で十分な画質が得られると書いたので、深さ4までキャッシュすることを考えてみましょう。深さ4までのノードを連続したアドレス空間に配置するために、順序付けを考えてみましょう。例えばこんな感じです。

• 深さ 0 -> 0
• 深さ 1 -> 1〜8 (1+n)
• 深さ 2 -> 9〜72 (1+(1+n)*8 = 1+8+8*n)
• 深さ 3 -> 73〜584 (1+8+(1+n)*64 = 1+8+64+64*n)
• 深さ 4 -> 585〜4680 (1+8+64+(1+n)*512 = 1+8+64+512+512*n)

これで深さに応じた順序付けができました。簡単ですね。

パレットインデクス付の最適化

上記の処理で高速にパレットが生成できるようになりましたが、実際に減色された画像を得るには生成したパレットと画像を対応付ける必要があります。この画素はパレットでいうとどの色だ、という処理ですね。octreeは全ての画素を処理するまでパレットが決定されないので、効率的な逆引きが難しいのです。何の前提条件もない場合、近似色計算は画素毎にパレットの全エントリとの色空間の距離を調べて最も距離が小さいものを選択していくという処理になります。計算量はパレットのエントリ数をPとするとO(W*H*P)となります。またボクセル処理みたいになってます。ボクセル処理は禁止です。感覚的には、画素からハッシュ的にパレットのインデクスを求めることができれば高速に処理できそうな気がします。

*1:http://d.hatena.ne.jp/izariuo440/20120320/1332212854

*2:私が試した限りでは、ソートだけで最適化前のoctreeの処理よりも時間がかかってしまいましたが、画素数によってはソートの方が速いかもしれません