analog

アニメ絵などのべた塗り画に特化した画像処理アルゴリズムのアイデア

原始的すぎて30年前に発明され廃れているかもしれない。素人の思いつきということで一つご容赦を。

コンセプト
ビットマップからオーサリング時のレイヤーをリバース・エンジニアリングする技術であり、圧縮技術でもある。アニメ画からセル画のレイヤーを推論・復元するようなもの。

解説
パレットとレイヤーを使う。まずビットマップ全体で使われている全色のパレットが必要。パレットの色数だけレイヤーを用意する。色がレイヤーに紐付いているために、レイヤーのデータは「ある色が、あるピクセルに、あるかないか」だけを表現すればよいので、1ピクセルあたり1ビットで表現できる。各レイヤーは色ごとのモノクロビットマップ。また、べた塗りの画を想定しているので、各レイヤーをランレンクスか4分木で圧縮する。

特徴
・デコードは速いのでは？
・VRAM描画処理、プログラマブルシェーダとの相性がよいのでは？
・ASIC、FPGAなどの半導体での処理にも向いているのでは？
・ベタ塗りじゃない場合、ノイズが多い場合、色数が多すぎる場合には不向きか？
・要するにFlashアニメのような画の圧縮に向いている？（ただし動画としての圧縮はまだ考慮していない）
・PhotoshopやIllustratorやFlashのプラグインとして直接上記データ形式で書き出してもいい

〜〜〜

発展
色を抽出してレイヤーのビットマップを作る際に、欠けているビットを推論・復元できる可能性がある。「この色の後ろに、この色が塗られているはずだ」という塗り重ねの推論。領域の隣接関係から可能なはず。

留意点
レイヤーの前後関係をグラフ化して推論していく？　矛盾して解決できない場合（回路）がありそうなので、ヒューリスティクスで解決する必要がありそう。

例
丸い塗り領域があったときに、(A)丸い穴があいて背景が見えている（丸の塗りは背景色）、(B)背景に丸い領域が載っかっている（丸の塗りは前景色）、という2通り。これは人間が見ても2通りの解釈ができる場合があるので、ヒューリスティクスで勝手にどちらかに決める。

展望
ステレオグラムジェレネータは同じような処理をしてるはずなので、きっと簡単なアルゴリズムと思われる。

※これをやるなら「1色1レイヤー」の過程を崩し、「同じ色でもZ座標が異なれば別レイヤー」と。同じ色でも同じレイヤー（Z座標）とは限らないので。下塗り背景色とハイライト色が一緒の場合など。

結果
各レイヤーは、なるべく「意味のあるかたちのまとまり」となって記録される。よりオーサリング向きのレイヤーデータが抽出できることになる。つまりリバース・エンジニアリング向きに。

〜〜〜

用途
１．プアなハードウェアでもデコードが速い圧縮方式
２．リバース・エンジニアリングして勝手にPhotoshopなどで編集するため

ふりかえり
同じ色が使われている箇所から共通の「色情報」を抜き出し、そのかわりに個々の箇所のデータ量を減らす。これは辞書式圧縮方式そのものだな。GIFのLZWとは違うとはいえ、すでに誰かが考えてそうだ。そしていまいちだから普及していないという説。