七色雑記

手法の概要

差分を利用するシンプルな画像圧縮の例として，以下のようなものが考えられます．

1. 差分の元となる画像 A を普通に記録する
2. 差分が発生する領域（顔など）を決め，画像 B, 画像 C, ... はその領域だけを切り出して記録する
3. ゲーム実行時にはゲームエンジン・スクリプト側で差分画像をレイヤーで重ねて表示する

この方法はシンプルでありながら，差分をとらずに画像を一枚一枚記録する場合と比べるとかなりの効率を期待できます． しかし，この手法にはいくらか改善点が考えられます．ここでは以下のようなものを考えます．

1. 差分が発生する領域を人力でざっくり指定するのではなく，プログラムによりピクセル単位で差分をとったほうが，データ量・人間の手間を削減できるのではないか
2. 画像 A からだけでなく，すでに生成された画像のうちもっとも近いものから差分をとるようにすれば，さらにデータ量を削減できるのではないか

ということで，上の機能を実際に実装してみました．

なお，画像圧縮の方法としては，今回のような単純な差分ではなく，MPEG のような予測符号化や画像間の予測・補償を使った方法もあり，それを使えばさらに圧縮率を向上できる可能性がありますが，今回は，アドベンチャーゲームエンジンが持つ既存のレイヤー合成の機能だけで実現できる上記の方法のみを考えます．

重ね合わせの枚数制限

上記で説明したように，たとえば画像 A から画像 B を生成し，画像 C はどちらか近い方から生成し，としていけば画像サイズをより小さくできることが見込めます． しかし，復元時に参照する画像の枚数があまり多いと，画像の重ね合わせによる計算コストが大きくなる可能性があります． そこで，重ね合わせの枚数に制限を設け，その範囲内で総ファイルサイズを最小にできるような仕組みを実装しました．

ただ，実際のユースケースを考えると，基本的に差分 CG はゲーム中の特定箇所で集中して使われる傾向にあるため，メモリが潤沢にあるのであれば全差分画像をまとめてデコードしてメモリに置いておけばよく，わざわざ重ね合わせの枚数制限を設ける必要はないかもしれません．

実験

実際にプログラムを作成し，いくつかの商業ゲームのイベント CG をスクリーンキャプチャして圧縮した結果を以下に示します．

表の「重ね合わせなし」は，画像の差分をとらずに普通に PNG で圧縮して記録した場合，つまりもともとの画像の総ファイルサイズを示します． 「重ね合わせ上限 2」は，1 枚の画像とそこからの差分だけで記録するケース，つまりシンプルな差分記録方式に相当します．

この結果を見ると，重ね合わせ上限を 3 以上に増やすことで，上限 2 のケース，つまりシンプルな差分記録方式と比べて画像サイズをより小さくできていることがわかります． 特に変化の大きかったデータセット #1, #5 は，データセット中にカットインのような面積の大きい差分があり，そのような場合でも本手法により効率よく圧縮できていることがわかります． また，重ね合わせ上限を 3 に設定すれば，「重ね合わせ上限なし」のケースと比べてもほとんど圧縮効率が劣らないことがわかります．

本来ならここで，実際の商業ゲームでの圧縮データと比較しての考察もすべきですが，製品をリバースエンジニアリングしたりアセットのアーカイブを開けたりしなければならずあまり気が進まないので，ここまでにしておきます．

まとめ

この記事では，ゲームで使われる画像素材に対して，総ファイルサイズが最小になるような順序で差分をとることで，効率よく圧縮できることを示しました． 圧縮されたデータは通常のレイヤー合成によって復元可能であるため，ほとんどのゲームエンジンにおいて，エンジン自体に手を入れることなく対応できます．

実際の商業 PC ゲームとの比較まではできませんでしたが，この手法によりある程度のデータ削減は可能であると見込めます． 削減できた分の容量は，画像の高解像度化や音声データの高ビットレート化に割くことができ，ユーザー体験とゲームの価値向上に貢献できます．

最初に書いたとおり，この記事で使用したプログラムは MIT ライセンスで配布しております．プログラムによって生成された画像データ自体はプログラムのライセンスとは関係なく使用できますので，ぜひご活用ください． 利用報告や比較レポート，質問なども，Twitter やこの記事のコメント等でぜひお寄せください．

（もっと FullHD 対応のゲーム増えてくれ）

技術的解説

今回の実験で使用したプログラムは，以下のような方法で，総ファイルサイズが最小になるような差分の取り方を求めています．

1. 各画像単体と，画像間の全組み合わせの差分画像に対して PNG 圧縮を行い，圧縮サイズのマトリックスを求める (scan.exe)
2. 1. で得られたサイズをアークのコストと見なす最小有向全域木問題を生成する (formulate.exe)
3. 2. で生成された問題を混合整数線形計画問題ソルバーで解く (cbc.exe)
4. 求めた解をもとに結果画像を出力する (organize.exe)

1. は単純に，画像を読み込んで画素ごとに比較して差分を抽出するだけです．

2., 3. について，今回のテーマとなっている「総ファイルサイズが最小になるような差分の取り方を求める問題」は，「ファイルサイズをアークのコストとする最小有向全域木を求める問題」とみなすことで，既知のアルゴリズムを使って最適解を求めることができます． ただし，画像の重ね合わせ枚数に上限を設ける場合は，ホップ数制約付きの最小有向全域木問題となり，これは NP 困難となります． 今回は Gouveia ら [1] の手法を使い，ホップ数制約付き最小有向全域木問題を有向シュタイナー木問題に変換して解きました． 以下に，2. で生成しているシュタイナー木のイメージを示します．

この問題は，「始点から各端点へそれぞれ異なる品種の製品を輸送したいとき，建設費が最小となる道の組み合わせはどれか」という多品種流問題の一種とみなすことができ，各製品の流量についての関係式を立てることで，混合整数線形計画問題として解くことができます（参考：多品種流問題 | opt100）．

元の論文では，問題の性質を利用して効率よく解を求める方法が説明されていますが，難しくてよくわからなかったので，今回は 3. に書いたように汎用のソルバー (Cbc - COIN-OR Branch-and-Cut Solver) に丸投げしています．

4. については，実は 3. が求まった時点で最小の総ファイルサイズはわかっているため，サイズの比較だけできればいい今回の実験では 4. は不要なのですが，ここでは実用のユースケースを想定してあえて書いています．

[1] Gouveia, Luis & Simonetti, Luidi & Uchoa, Eduardo. (2011). Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs. Math. Program.. 128. 123-148. 10.1007/s10107-009-0297-2.