画像平面分割の高速化(1)
2009/12/20 19:49 - AS3.0
ココとかココとかココとかココとか、皆さんもそうでしょうが、ご多分に漏れずワタクシも萌えたクチです。
wonderfl 上で、fumix さんが「フラクタルで画像を描画する」を、そのfork として ep91ckok さんが「forked from: フラクタルで画像を描画する」を投稿なさいましたが、この平面分割アルゴリズム、さらに高速化できないもんだろうかといろいろ考えておりました。
リアルタイムレベルの速度にできると嬉しいなあ、というゴール設定をしてきましたが、なんとかそれらしい速度で描画できるようになったので、ここで記事としてまとめておきます。
なんとかそれらしい速度で描画できるようになったのが↓
まずはおさらい。
このアルゴリズムは BitmapData を対象とした再帰処理なわけですが、その概略は以下のようになっています。
- BitmapData の指定領域の全ピクセルの輝度の標準偏差を求める
- 標準偏差が閾値以上の場合、指定領域を4分割し、それぞれの領域に対して再帰処理を続行
- 標準偏差が閾値未満の場合、再帰せず、指定領域の平均色を求め、塗りつぶす
先人のコードを拝見すると、輝度の標準偏差取得と、平均色取得で、以下のことをおこなう必要があることが分かります。
平均色取得
- 全ピクセルを走査、走査中はピクセルの R、G、B 各要素ごとに、それぞれの値を加算し続ける
- ピクセル走査終了後、加算で得られたそれぞれ値をピクセル数で除算
- その除算で得られたそれぞれ値から色を構成
輝度の標準偏差取得
- bitmapData をモノクロ化
- 全ピクセルを走査、走査中はピクセルの R の値を加算し続ける（R、G、B どれでも良いが便宜上 R を対象とした）
- ピクセル走査終了後、加算で得られた値をピクセル数で除算、得られた値を輝度の平均値とする
- 再度、全ピクセルを走査、走査中はピクセルの R 値から平均値をマイナスし、その値の二乗を求め、加算し続ける
- ピクセル走査終了後、加算で得られた値の平方根を求める
ここでパッと見でも分かるお金がかかる処理（FITC Tokyo 2009 の同時翻訳的表現）は、全ピクセル走査でしょう。 走査領域が大きければ大きいほど、処理コストがかさみます。例えば100 pixel × 100 pixel の領域を走査すると1万回ループする必要があります。 wonderfl のステージサイズ 465 pixel × 465 pixel だとおよそ22万回。
とはいうものの、全ピクセルを検査しなければならない処理で、ループ回数を減らすことなんかできるのかなぁ？
そんな壁にぶち当たったときです。そう彼に出逢ったのは。
彼の名前は BitmapData.histogram。
続く。
