PNG画像を自力で読む

2010年3月31日 (水)

PNG画像を自力で読む

　このサイトではPNG画像をあちこちで使ってます。
　まあ、一番よく使ってるのはJpegですが。
　プログラムを組むときも、この二つはよく使われますね。
　なんせどちらも無料、かつ使い勝手のいいライブラリ (libpng、libjpeg) が用意されてますし。
　てなわけで、普通はPNG画像を自分のプログラムに組み込みたいなら libpng を使えばいいんですが、ちょいと思い立って自力で組んでみることにしました。

　D言語ならコードを劇的に減らせますし、MMX化したきゃインラインアセンブラも付いてます。慎重に組めば若干の高速化も期待できるかも。
　なによりファイルフォーマットを理解するのは、けっしてマイナスにはなりません。
　機能を必要最小限にとどめておけば、たった1,000行程度のコードでPNG画像を読むことが可能ですぞえ。
　もっとも実際にネットで配布するようなソフトウェアには安全なライブラリを使った方がいいので、あくまで学習用と考えるべきですが。

どこまで実装する？

　PNG画像ローダを全部実装すんのは面倒です。
　ガンマ補正値だのICCプロファイルだのピクセル寸法だのヒストグラムだのといった、細かい仕様は無視することにします。
　画面に表示させるだけなら以下の必須チャンクだけ読めれば、ちゃんと画像データを取得できます。

PNG画像フォーマットの必須チャンク

IHDR: ヘッダ情報
必ずファイルの先頭になければダメです。画像サイズやビット深度、アルファチャネルの有無などが書いてあります。
IDAT: データ本体
zlib で圧縮された画像データです。このチャンクが複数入ってることがありますが、その場合でも必ず連続してる上、単純に連結するだけでいいので簡単です。
PLTE: パレット情報
IHDR でインデックスカラー (2、4、16、256色) が指定された場合のみ必須となってます。
RGB画像の場合、古いPCでの減色用に存在する場合がありますが、いまどき使わないでしょうから無視しても構いません。
グレースケール画像の場合、このチャンクは絶対にありませんので注意。 (もしあったら圧縮したソフトのバグです)
IEND: PNGデータ終端
名前からわかると思いますが、「PNGデータはここで終わりダヨーン」というチャンクです。中身は常に空っぽ。
むろんPNG画像ファイルの最後に書かれてます。
最後でなくてもこのチャンクが出たら、なにがなんでもそこで終了。

インターレースに対応させる？

　インターレース (スキャンライン飛び越し表示) は、遅いネット回線などで表示してる分には便利ですが、自分で組むとなるとスキャンラインの処理が面倒です。(通常の1ループ処理に対し、7回ループ処理を行う必要があります)
　ゲームアプリケーションなど、ローカルPC内のデータだけを表示させるのであれば、普通に上から下まで読み込んだ方が処理が軽く、バグも出にくいので今回は実装しないことにします。

カラーモードは全部対応させる？

　PNGはインデックスカラー、グレースケール、RGBフルカラー、グレースケール + アルファチャネル、RGBフルカラー + アルファチャネルと、様々な画像形式に対応しています。
　これらすべてに対応させるのは骨が折れそうですが、実際は画面に表示するとき以外、全部同じ処理でデコードできるので問題ありません。
　ただでさえインターレースに対応させないことで厳密なPNGローダではなくなってしまったので、カラーモードくらいは全部に対応させたいものです。

チャンクの読み方

　各チャンクは以下のような順番で保存されています。
　順番に読むだけなので、実装も簡単です。

データブロックのサイズ: 4バイト
最初にチャンクデータのブロックサイズを読みます。
4バイトだからってストリームで toInt() とか呼び出してはいけません。PNGファイルのバイトオーダーは Big Endian (上位バイト→下位バイトの順に並ぶ) なので、x86系のCPUで読む時には1バイトずつ上位バイトから読む必要があります。
チャンク形式: 4バイト
「IHDR」とか「IDAT」など、チャンクの名前が入ってます。
PNGはチャンク名の大文字小文字の違いで必須チャンクか否かや、コピー安全性などのチェックを行っているので、間違えないようにしてください。
ちなみに必須チャンクはすべて大文字、補助チャンクは1文字目が小文字、仕様で決まってない（独自に追加した）チャンクは2文字目が小文字、どんなチャンクでも3文字目は必ず大文字、コピーしても安全なチャンクは4文字目が大文字、と厳密に決まってます。
チャンクデータ: (サイズ可変)
IHDR の場合はヘッダ情報、IDAT のときは画像データなどが入っています。
サイズは先頭の4バイトで指定されていますので、その分のデータを読み込むだけです。
チャンクによっては0バイトの場合もあります。
CRC: 4バイト
データの整合性チェック用のCRC値です。チャンク形式の文字列とチャンクデータを結合した値から算出します。
無視しても構いませんが、何MBもある巨大PNGファイルの全CRCをチェックしても数ミリ秒もかかりませんので、ちゃんとチェックした方がいいでしょう。
この値と算出した値が異なっている場合、チャンクのデータは壊れています。
CRC計算用のC言語コードはPNG仕様書に書いてありますが、一応以下にD言語で書き直したコードを載せておきます。

CRCチェックコード – D言語版

/**
 * CRC テーブル
 */
private uint[256] crc_table;

/**
 * CRC テーブル初期化
 *
 * static this() はプログラムの開始時、自動的に実行されます。
 * C言語のように、フラグで初期化済かをチェックする必要はありません。
 */
static this()
{
    foreach(n, ref c; crc_table)
    {
        c = n;

        for(int i = 0; i < 8; i ++)
        {
            if(c & 1)
                c = 0xEDB88320 ^ (c >> 1);
            else
                c >>= 1;
        }
    }
}

/**
 * チャンク名とチャンクデータから CRC を算出
 *
 * Params:
 *      chunkName = チャンク名
 *      chunkData = チャンクデータ
 *
 * Returns:
 *      算出されたCRC値
 */
uint crc(char[4] chunkName, void[] chunkData)
{
    uint result = -1;
    char[] str = chunkName ~ cast(char[])chunkData;

    foreach(c; str)
        result = crc_table[(result ^ c) & 0xFF] ^ (result >> 8);

    return result ^ -1;
}

実際に組んでみよう

　ほんじゃま本番、いよいよ実装に入ります。
　実装といっても、PNG画像は以下の手順通り処理を行えばデコードできてしまうので、ポイントだけ説明することにします。

PNG画像のデコード手順

PNG シグネチャのチェック
PNGファイルの先頭8バイトには、必ず以下のデータが入っています。
const ubyte[8] SIGNATURE = [137, 80, 78, 71, 13, 10, 26, 10];
この値を比較し、1バイトでも違うデータがあった場合はエラーを投げて終了します。
ちなみにこのデータはD文字列で書くと、以下のようになります。
const char[8] SIGNATURE = \x89 "PNG\r\n" \x1A "\n";
最初に非ASCII文字があるので、間違えてテキストエディタで開けば文字化けして、バイナリデータであることが判明します。(Shift_JIS だと次の「P」と結合され、「臼NG」になっちゃいます)
続いて文字列「PNG」、改行 (\r\n) 、EOF、改行 (\n) となっているのがわかると思います。
IHDR ヘッダの読み込み
シグネチャの直後は必ず IHDR チャンクです。
もし別のチャンクが入ってたらエラーを投げて終了します。
IHDR チャンクの画像サイズ (幅、高さ)、カラーモード、ビット深度を調べれば、デコードされた画像を保存するバッファのサイズが確定します。
必要なメモリはこの時点で確保しておきましょう。
IDAT、PLTE チャンクの読み取り
IHDR の位置は先頭、IEND は最後と決まってますが、その他のチャンクはいつ出現するかわかりません。
順にチャンクを読み込み、IDAT、PLTE 以外のチャンクが出たら読み飛ばします。
IDAT、PLTE チャンクの読み取り手順は後述。
IEND チャンクが出現するまでスキップ
……というのが普通のPNGローダですが、IDAT、PLTE 以外は不要 (インデックスカラー以外では PLTE も不要) なので、ここで処理を終了してしまいます。 (笑)

PLTE (パレット情報) チャンクの読み方

　色数 x 3バイト分のデータがあります。(256色なら 256 x 3 = 768バイト)
　「x 3」はそれぞれRGB値であり、R、B、G の順に並んでいます。
　x86 の場合は BGR 順に並べる必要があるので、バイトオーダーを反転してコピーします。

IDAT (イメージデータ) の読み方

　前述した通り、IDAT チャンクは複数連続して出現する場合があります。
　順に展開する方が効率的ですが、ストリームクラスなどを通さないとコーディングが面倒です。
　結合して処理する場合は楽ですが、結合時に大きなメモリを使うため、効率は悪くなります。
　どちらの場合でも以下の手順でデコードすることになります。

IDAT デコード手順

zlib 展開バッファの確保
IDAT チャンクは zlib で圧縮されています。
このため、展開 (解凍) 用のメモリを確保する必要がありますが、展開後のデータサイズが 32,768 バイトを超える場合は 32,768 バイトずつ展開する必要があります。
展開後のサイズが 16,384 バイトよりも小さい場合、256 バイトを最小値とした 2ⁿ のサイズ (256、512、1024、2048、4096、8192、16384バイトのいずれか) までバッファを縮小することができます。
32,768バイト固定でも構いませんが、なるべく小さなバッファを使うよう心がけましょう。
zlib 展開
1. で確保したバッファに zlib でデータを展開します。
これは超簡単なので説明は省略。
逆フィルタリング
ここが一番面倒くさいです。
PNGは zlib 圧縮時の圧縮率を上げるため、1 ラインごとに 5 種類のフィルタのうち、いずれかのフィルタ処理を施されています。
これをフィルタリングとは逆の式で元に戻さねばなりません。
各フィルタ処理については後述します。
バイトオーダーの反転
Windows (というか x86系) の画像データは、BGR の順番に並んでいないと都合が悪いです。
しつこいようですがPNGに限らず多くの画像フォーマットは RGB 順に並んでいるため、バイトオーダーを反転させなければなりません。
ただし、アルファチャネルを使った画像の場合は要注意です。
PNGではアルファチャネルは必ず最後尾に並ぶため、ARGB ではなく RGBA の順に配置されています。
これを汎用性の高い (というより、画面に表示するときに楽な) BGRA の順に並べるためには、A のアルファチャネルを除外してソートする必要があります。

イメージデータの逆フィルタリング

　zlib で展開された各ラインは、以下のいずれかのフィルタを施されています。
　各ラインの先頭には1バイトのヘッダがあります。
　ubyte[] data に展開されたデータが入っている場合、data[0] がヘッダ、data[1..$] のスライス配列が実際のラインデータとなります。
　ヘッダには 0～4 のIDが振られており、以下の5種類のフィルタが存在します。
　各フィルタはビット深度に関係なく、それぞれのバイトデータに適用されるので注意が必要です。

0: None フィルタ

　なにもしないフィルタです。これをフィルタといえるかどうかは疑問ですが。
　このIDが振られたピクセルデータは、単にイメージデータのラインにコピーするだけで構いません。

1: Sub フィルタ

　各ピクセルには左のピクセルとの差分が保存されています。
　最初のピクセルには左のピクセルがないため、0 を基準とした差分 (要するに元々のピクセルデータ) が入っています。

　【式】左のピクセルのバイトデータ + 自ピクセルの差分データ = 最終的なピクセルデータ

2: Up フィルタ

　各ピクセルには上のピクセル(直前のラインデータ)との差分が保存されています。
　Sub フィルタと同様、上のラインが存在しないピクセルの場合は、0 を基準とした差分が保存されます。(最初のラインでこのフィルタを選ぶエンコーダはどうかと思いますが……)

　【式】上のピクセルのバイトデータ + 自ピクセルの差分データ = 最終的なピクセルデータ

　ほとんどの画像で出現率が高く、None フィルタを除いてもっとも書きやすく、MMX化の効果も高いフィルタです。気合い入れて作りましょう。
　そういえば高校生のとき、8ビットPCで同人ゲームのCGを圧縮するのに、ちょうどこんな感じのフィルタ書いたなあ。
　ついでですので以下に実際のMMX化コードを載せておきます。

/**
 * Up フィルタ
 *
 * 1ライン上のピクセルとの差分を加算
 *
 * Params:
 *      line    = デコードしたデータ (画像データ) の保存先
 *      src     = zlib で展開したデータ (フィルタIDのヘッダバイトは除く)
 *      prev    = 1ライン上のデコードデータ (前回の line)
 */
void filterUp(ubyte[] line, ubyte[] src, ubyte[] prev)
in
{
    // 契約: 引数の事前チェックを行います。 (デバッグビルド時のみ)
    assert(line.length >= src.length);
    assert(line.length == prev.length);
}
body
{
    /*
     * 以下の計算をアセンブラで高速化
     *
     * foreach(i, p; src)
     *  line[i] = cast(ubyte)(prev[i] + p);
     */

    bool mmxSupported = std.cpuid.mmx();
    size_t size = src.length;
    auto pSrc  = src.ptr;
    auto pDst  = line.ptr;
    auto pPrev = prev.ptr;

    asm
    {
        ; // 準備
        mov ESI, dword ptr pSrc;
        mov EDI, dword ptr pDst;
        mov EBX, dword ptr pPrev;
        mov ECX, size;

        mov AL, mmxSupported;
        cmp AL, 0;
        jz MMX_UNSUPPORTED; // MMX 未対応なら1バイトずつ計算

        ; // 8バイト境界
        mov EAX, ECX;
        and EAX, 7;         // size % 8
        mov EDX, EAX;       // 8バイト境界の余りを保存
        shr ECX, 3;         // size / 8
        jz END_MMX;         // データが8バイト未満の場合

    ; // MMX で8バイトずつまとめて計算
    LOOP_MMX:
        movq MM0, [ESI];    // MM0 = src[i..i + 8]
        movq MM1, [EBX];    // MM1 = prev[i..i + 8]
        paddb MM0, MM1;     // MM0 += MM1
        movq [EDI], MM0;    // line[i..i + 8] = MM0
        add EBX, 8;
        add ESI, 8;
        add EDI, 8;
        loop LOOP_MMX;

        emms;               // MMX レジスタを解放

    ; // 余りのバイトを計算
    END_MMX:
        mov ECX, EDX;       // 8バイト境界の余りを復元

    ; // MMX 未対応の場合
    MMX_UNSUPPORTED:
        jcxz END_OF_LINE;

    ; // 1バイトずつ計算
    LOOP_PIXEL:
        mov AL, [ESI];
        add AL, [EBX];
        mov [EDI], AL;
        inc EBX;
        inc ESI;
        inc EDI;
        loop LOOP_PIXEL;

    END_OF_LINE:
        ;
    }
}

　コメントを読むとわかるかもですが、元はたった2行のコードです。(笑)
　MMX化すると移植性はまったくなくなりますし、デバッグもしにくくなるのが欠点ですが、効果は折り紙付きです。(いまどき存在するかどうかは疑問ですが、一応MMX未対応の無印Pentiumでも動作します)

3: Average フィルタ

　各ピクセルには左と上のピクセルの平均値 (左 + 上 ÷ 2) との差分が保存されています。
　Sub フィルタや Up フィルタ同様、存在しないピクセルは 0 とみなされます。

　【式】 (左のピクセル + 上のピクセル) ÷ 2 + 自ピクセルの差分データ = 最終的なピクセルデータ

4: Paeth フィルタ

　各ピクセルには左、上、左上のいずれかのピクセルとの差分が保存されています。
　他のフィルタ同様、存在しないピクセルの値は 0 とみなします。
　どのピクセルとの差分を取るかは、ラインデータの各バイトごとに以下の方法で算出します。

　【基準ピクセル算出式】

「左 + 上 – 左上」の値 X を計算します。
「X – 左ピクセルのバイトデータ」の絶対値を A とします。
「X – 上ピクセルのバイトデータ」の絶対値を B とします。
「X – 左上ピクセルのバイトデータ」の絶対値を C とします。
A、B、C のうち、最小の値を選択します。(同じ値が複数あった場合、A がもっとも優先度が高く、Cがもっとも低い)
選択された値が A の場合、左のピクセルを基準とします。
選択された値が B の場合、上のピクセルを基準とします。
選択された値が C の場合、左上のピクセルを基準とします。

　【式】基準ピクセルのバイトデータ + 自ピクセルの差分データ = 最終的なピクセルデータ

まとめ

　とまあ、駆け足で書きましたが、こんな感じで自作PNGローダが完成しました。
　開発期間は3日。デバッグ後のコードはMMX抜きだと1,000行ちょい、MMXありでも1,500行程度です。
　ロードした後はビットマップに起こすなり、Direct3D のアルファ付きテクスチャとして貼り付けるなりして遊べます。(上の画像ではテクスチャに直接貼り付けてます)
　PNGはわりかし簡単な実装でデコーダを作れるので、練習用にはもってこいかと思います。

トラックバック

TrackBack URL :

コメントはまだありません。

日	月	火	水	木	金	土
« 8月
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

PNG画像を自力で読む

2010年3月31日 (水)