2016年8月19日

ZIP ファイルに内容の似た PNG ファイルを大量に突っ込む話

2016年から PSDTool というツールを作っている。

これは端的に説明すると PSD ファイルをブラウザで読み込んで、レイヤーごとにバラして保存したり、レイヤーの表示状態を切り替えた画像をたくさん保存したりするためのツール。

PSDTool にはブラウザのブックマークに似た機能があり、レイヤーの表示/非表示の切り替えを行った状態を保存しておくことができる。
更にエクスポート機能を使うことで登録した項目を PNG ファイルで ZIP ファイルに詰め込むことができる。

メインの用途は古典的な立ち絵イラストを、各種ツールで扱いやすい形式、構造に変換すること。
(ここでいう古典的とは、モーフィングのような機能を含まないという意味)
立ち絵を使うツール側で高度な画像合成ができるなら PSD のレイヤーごとに書き出すのもいいが、合成済みの画像を得られた方が便利なケースも当然多い。

合成済みの画像をたくさん ZIP ファイルに保存する場合、表情だけがちょっと違うような、似た内容の画像をたくさん保存することになる。これを ZIP にそのまま突っ込むのは扱いやすい反面ファイルサイズが全然縮まないので、色々考えてみた話。

要するに、こういう感じのファイルセットを効率よく圧縮したい。
(C) 零度の青空 air 独自拡張機能対応ありがとうございます
ちなみに PSDTool 上で「シンプルビュー」を使えるようにして、エクスポートで「シンプルビューの全パターンをエクスポート」を選ぶと、このようにたくさんのパターンの PNG ファイルを簡単に得ることができる。

ZIP ファイルに内容が似た PNG ファイルをたくさん入れた時の圧縮効率の悪さ

まず、ZIP ファイルにちょっとだけ内容が違う PNG ファイルをたくさん入れた時の問題点を整理する。
  1. ZIP ファイルではファイル毎に圧縮するので、2つのファイルが似ているかは考慮されない。
    例えば圧縮後に 2KiB になるファイルを2つ ZIP に入れれば 4KiB ぐらいになるし、10個入れれば全部同じ内容のファイルでも 20KiB ぐらいになる。
  2. ZIP ファイルで最も一般的な圧縮メソッドである Deflate は LZ77 のウィンドウサイズが最大でも 32KiB と小さい。
    だからもし ZIP ファイルで PNG ファイル同士が似ていることが考慮できたとしても、ファイルが 32KiB を超えると似た場所を上手く見つけられなくなる。
  3. 画像が既に PNG ファイルとして圧縮されているので、表示した時に見た目がほぼ一緒でもファイルのデータ自体には結構差があって、似ているかどうかの判断が難しい。
ZIP ファイルが縮まない原因として大きいのはこの辺だと思う。

どのような対処方法が考えられるか

1 や 2 の問題は 7z ファイルなどのような新しいファイル形式や、TAR 形式のように複数のファイルを1つのファイルにまとめてから圧縮するような形式である程度解決する。
しかし汎用的なコンテナフォーマットとしては ZIP ほど普及していないので、OS を問わずツールを準備せず簡単に展開できるというレベルではなく、ZIP に比べて取っ付きにくい。
自作プログラムで展開するケースを考えても、色々な言語で扱いやすい実装があることが多い ZIP に比べ普及率や速度の面で扱いづらいし、TAR だと上から圧縮すると任意のファイルへランダムアクセスもしづらい。

3 の問題は無圧縮の画像データにすればデータ的に似ている場所の検出は簡単になるけど、例えばほとんど内容が同じ BMP ファイルを 7z ファイルに大量に入れてあるとしたら、一度に全てを展開したりするとちょっとした高圧縮ファイル爆弾になりうるので危険が危ない。

自分でアーカイブフォーマットなどを自作するのももちろん考えたが、世の中にあるツールが全て使えないことになるのでこれもまたつらい。

そんなこんなで ZIP や PNG でもっと縮める方法を考えた末、ちょっとしたアイディアが浮かぶ。

Tiled 用の形式で書き出す

(C) 零度の青空 air
Tiled はマップエディタで、ドラクエみたいなマップとか、マリオのステージ構成とか、ああいうタイル状に並べたデータを作るためのツール。これ用のデータとして立ち絵を書き出す試み。

例えば立ち絵画像2枚をそれぞれ 16x16 のマスで切り分けていくと、表情とか変化があった部分はマスの内容が異なるけど、ほとんどのマスは同じ内容になるのが容易に想像できる。
ほとんどのマスが同じということは、多くの場所でタイルチップの使い回しができる。
立ち絵画像1枚だけで考えても、余白の透明部分などはかなりの場所で使い回しができる。

こうして PNG や ZIP のまま Tiled 形式を上手く使って、似た部分を効率よく格納できるようになった。
画像を元の形に復元するためには当然タイルを並べないといけないが、レイヤー合成ほど複雑で多彩な処理は必要としないし、レンダリング済み画像だから元画像のレイヤー数が多くても表示の際にメモリ消費や描画負荷が増えることはない。
タイルチップを並べた画像1枚に相当なバリエーションのデータが詰まっているため消費メモリ面で見ても結構アドバンテージがあるように思う。

PNG ファイルを ZIP ファイルに詰めた場合大体 82MB ぐらいになるデータが PNG + TSX + TMX で 1.24MB まで縮み、今回は 512x512 のテクスチャに全てのタイルが収まった。
TMX の書き出し方などはテスト段階なので最終的にはサイズが変わるかもしれないが、なかなかの結果だ。

まあこの方法で書き出せるようになっても需要はほとんどなさそうだけど。
この機能は準備ができたらそのうち公開する予定。

---- 2016-08-21 追記

処理を整理し別の PSD ファイルでも試してみたところ、PNG ファイルを ZIP ファイルに詰めた場合 1.22GB になるデータが PNG + TMX の ZIP で 18MB、ZIP ではなく 7z に入れると 534KB まで縮んだ。
テストに使った PSD ファイルが 826KB で ZIP に入れると 539KB、7z に入れると 291KB なのでなかなかの健闘ぷり。

---- 2016-10-28 追記

ここで得られた知見を元に改めて独自のアーカイブフォーマットを試作してみたところ、上記のテストで 1.24MB だったものは 234KB、追記で書いた 18MB のものは 733KB に縮めることができた。
自分が作った専用ビューワ以外で開けないので今のところ実用性はアレではある。
Clip to Evernote