PNG イメージを自力でパースしてみる～5/6 PNGフォーマット編～

ここまでのあらすじ

PNG イメージを自力でパースしてみる～1/6 予備知識編～
PNG イメージを自力でパースしてみる～2/6 Deflateの基本と固定ハフマン編～
PNG イメージを自力でパースしてみる～3/6 カスタムハフマン編～
PNG イメージを自力でパースしてみる～4/6 非圧縮とzlib編～

zlibを解凍するプログラムが一通り完成した。いよいよPNGファイルのパースに挑戦してみる。

PNGフォーマット
- シグネチャ
- チャンク
チャンクの種類
PNGイメージのパース
- フィルタリング処理
サンプル
参考にしたサイトさん

PNGフォーマット

PNGファイルの中身は、以下のような構成になっている

シグネチャ
チャンク (IHDR)
チャンク
　⋮
チャンク (IEND)

チャンクは１ファイルにつき、必要な数だけ作られる。

このチャンクのかたまりの中で、IHDRのチャンク (後述) は必ず先頭に出現し、
IENDのチャンク (後述) は必ず末尾に出現する。

シグネチャ

ファイルの先頭に必ず出現し、このファイルがPNGファイルであることを示す 8バイト長のデータ。すべてのPNGファイルは共通して、以下の値の並びを保有する。

10進 (16進)：

137 (89)

80 (50)

78 (4e)

71 (47)

13 (0d)

10 (0a)

26 (1a)

10 (0a)

PNGファイルをロードするプログラムは、まず初めにファイルの先頭 8バイトを読み出し、このシグネチャの並びと一致するかどうかで、対象が確かに PNGファイルであるかどうかをチェックする必要がある

ちなみにこの並びの中に現れる各値は、それぞれ以下のような役割を持つ

10進	16進	ASCII文字	役割
137	89	\221	ASCII文字として表現できない値。ファイルに必ず非ASCII文字を含むことで、テキストファイルとして間違えてロードされてしまう可能性を減らす。
80	50	P	自身のフォーマット名を表す
78	4e	N
71	47	G
13	0d	\r	"改行文字"として解釈されてしまい、システムによって勝手に「\r」や「\n」に置き換えられたりしないかを検出するために利用される
10	0a	\n
26	1a	\032	Control-z文字。ファイルの中身をテキストとして読み出し表示させようとしたDOSコマンドを停止させる
10	0a	\n	"改行文字"として解釈されてしまい、システムによって勝手に「\r」や「\r\n」に置き換えられたりしないかを検出するために利用される

チャンク

PNGファイル中に現れる各チャンクは、共通して以下のような構造になっている

Length	4バイト
Chunk Type	4バイト
Chunk Data	Length バイト
CRC	4バイト

1. Length（データのサイズ）

このチャンクの Chunk Data 部のサイズ (バイト数) を表す値をここに4バイト長で格納する。最小で「0」最大で「 $2^{31}-1$ 」までの値を収められる

2. Chunk Type（チャンクの種類）

このチャンクの種類を表す、アルファベット4文字のデータがここに格納される

3. Chunk Data（データ）

Length が「0」ではない場合、このチャンクの種類に関連したデータが、この場所に格納される。

4. CRC（crc32チェックサム）

CRC32チェックサムアルゴリズムを使って算出された値を、ここに4バイト長で格納する。ここの詳しい解説は、次回の記事で行うことにする。

なお、PNGファイル中に現れるこれら多バイト長の数値データはすべてビッグエンディアンの並びになっている。これらの数値データを読み出す際には、その読み出したデータのバイト並びに気を付けること。

チャンクの種類

PNGで利用できるチャンクの種類 (Chunk Type) を以下にざっと書き並べてみる

Chunk Type	説明	必須
IHDR	ヘッダ情報	〇
PLTE	パレット	〇
IDAT	イメージデータ	〇
IEND	終端	〇
tRNS	透過
cHRM	色度と白色点
gAMA	イメージガンマ
iCCP	埋め込みICCプロファイル
sBIT	主要ビット
sRGB	標準的なRGB色空間
tEXt	テキストデータ
zTXt	圧縮テキストデータ
iTXt	国際テキストデータ
bKGD	背景色
hIST	画像のヒストグラム
pHYs	ピクセル寸法
sPLT	推奨パレット
tIME	最終更新時刻

これすべてに対応しようとすると、さすがに途中で心が折れそう..
今回は必須チャンクに分類されるもののうち、

IHDR(ヘッダ情報)
IDAT(イメージデータ)
IEND(終端)

の３つのみに対応することにしてみる。

IHDR (ヘッダ情報)

Length	4バイト
Chunk Type ： "IHDR"	4バイト
Chunk Data	計 13バイト
・Width	4バイト
・Height	4バイト
・Bit Depth	1バイト
・Color Type	1バイト
・Compression Method	1バイト
・Filter Method	1バイト
・Interlace method	1バイト
CRC	4バイト

シグネチャを読み出した後、チャンクのかたまりの先頭に必ず現れるチャンク。
データ部は、以下の要素で構成される

1. Width （イメージの横幅）
2. Height（イメージの縦幅）

画像の縦横のピクセル数の値がそれぞれ4バイト長で収められる。

3. Bit Depth（ビット深度）

ピクセルの色要素「R」「 G」「 B」のそれぞれ、またはパレット番号 (今回は取り扱わない) が何ビット長で記録されているかを表す値が、ここに 1バイト長で収められる。

なお、後の Color Type の値によって、この場所に設定できる値が異なってくる

4. Color Type（カラータイプ）

PNGイメージのカラータイプを表す値が、ここに1バイト長で収められる。
ここに設定される値は、以下のビットフラグの組み合わせによって形成される

1（001）：パレット使用　　 (0なら不使用)
2（010）：カラー使用　　　(0ならグレースケール)
4（100）： αチャンネル使用 (0なら不使用)

ただし、このうち実際に使用することのできるフラグの組み合わせは、いくつかに限られている。使用が可能な Color Type と対応する使用が可能な Bit Depth との一覧を以下に示す

Color Type	Bit Depth	説明
0（000）	1, 2, 4, 8, 16	グレースケール
2（010）	8, 16	RGBカラー
3（011）	1, 2, 4, 8	インデックスカラー(要PLTEチャンク)
4（100）	8, 16	グレースケール＋ αチャンネル
6（110）	8, 16	RGBカラー＋ αチャンネル

5. Compression Method（圧縮方法）

画像データの圧縮のために、どのようなアルゴリズムを利用したかを表す値を、ここに 1バイト長で収める。「0」が設定されている場合、自身の画像データが、Deflate によって圧縮されたことを表す。

なお、０以外の値は、現状扱われることがない。とりあえず今は「0を読み出せれば正しい」と覚えていれば問題ないはず

6. Filter Method（フィルタ方法）

圧縮前の画像データに対して、どのような事前処理を行ったかを表す値を、ここに 1バイト長で収める。「0」が設定されている場合、画像データに対して、圧縮前にフィルタリング処理 (後述) が施されることを表す。

なお、０以外の値は、現状扱われることがない。こちらもとりあえずは「0を読み出せれば正しい」と覚えておけば問題ないはず

7. Interlace Method（インタレース）

画像データのピクセル要素の出現規則を表す値を、ここに 1バイト長で収める。
「0」ならインタレースなし、「1」ならインタレースありとなる。

画像データにおけるインタレースとは、画像データ中のピクセル要素をそのままの順で出現させるのではなく、飛び飛びで出現させるようにする手法のこと。

うち、インタレースありの PNGイメージは、以下の図に示す通りに処理される。

f:id:DarkCrowCorvus:20170120234812g:plain

これによる利点は、画像データを読み始めた早い段階で、おおざっぱな画像の全体像がわかるということ。初めにモザイク調で表示させ、読み込みが進み次第、徐々に鮮明になるように画像を表示させることができるようになる。

なお、今回は残念ながら実装が面倒だったのでインタレースに対応していない。
気が向いたらそのうち..

IDAT (イメージデータ)

Length	4バイト
Chunk Type ： "IDAT"	4バイト
Chunk Data （画像データ）	Length バイト
CRC	4バイト

実際に画像を構成するピクセル要素またはパレット番号の連なりからなるデータが、このチャンクの中に収められる。

このとき、収められる画像データには、フィルタリング処理 (後述) と zlibによる圧縮が施される。zlibについては、前回の記事で紹介済み。

なお、このIDATチャンクは、ファイル中にいくつでも出現してかまわないことになっている。その場合、それらのIDATチャンクは必ず１か所に連続して出現する。

IEND (終端)

Length	4バイト
Chunk Type ： "IEND"	4バイト
CRC	4バイト

チャンクのかたまりの末尾に、必ず現れるチャンク。
自身を読み出した地点がファイルが終わりであることを示す。

なお、IENDチャンクはデータ部を持たない。
Lengthには常に０に設定される。

PNGイメージのパース

対応できるチャンクを IHDR, IDAT, IEND に限った場合、これから以下に示す手順で、PNGイメージから、画像を構成するピクセルデータを引っ張りだすことができる

シグネチャ一致チェック
チャンク読み出し
IDATチャンクの zlib圧縮データを解凍
解凍したデータのフィルタリングを解く

1. シグネチャ一致チェック

ファイル先頭の 8バイトを読み出し、前述したシグネチャの並びと一致するかどうかをチェックする。

一致しなかった場合、そのファイルが PNGイメージではない、もしくは、ファイルを正しく読み出すことができないため、エラーとみなして、テキトウに処理を終了する。

2. チャンク読み出し

以下を IEND チャンクが出現するまで繰り返す

チャンクのLength (4バイト) を読み出す
Chunk Typeの4文字 (4バイト) を読み出す
Lengthが 0 でなければ、そのバイト数分だけ Chunk Dataを読み出す
CRC (4バイト) を読み出す

くどいようではあるけれど、今回は IHDR, IDAT, IEND のチャンクのみに対応する。それ以外のチャンクに遭遇しても、中身を考慮せずそのまま読み飛ばすことにする。

2.1. IHDRチャンク読み出し

シグネチャ並びの直後に出現。この場所に記録されている情報は、後に画像データを復元したり、ピクセル要素を抽出したりするために必要になる

なお、Color Typeが「3」である場合、ファイル中に PLTEチャンクが出現し、画像データはパレット番号によって構成される。

対応チャンク 3つ縛りの制限下では、このフォーマットに対応することができない。今回に限っては、これをエラーとみなしてテキトウに処理を終了することにする。
実装はたぶんまたそのうち...

2.2. IDATチャンクの読み出し

前述した通り、圧縮された実画像データがここに格納されている。

なお、このチャンクが複数出現する場合は、チャンクが出現した順番にChunk Data部のデータを連結する

3. IDATチャンクのzlib圧縮データを解凍

IDATチャンクから得られた Chunk Data 部
またはそれら複数を結合したデータに対して、zlibによる解凍を行う。

フィルタリング処理

PNGファイルに収められる画像データは、zlibによって圧縮される前に、その圧縮効率を上げる目的で フィルタリング という事前処理が施される

PNGイメージをパースする際、zlib解凍を行った後それを本来の画像データに戻すために、そのデータのフィルタリングを解く必要がある

現在、フィルタリングには、以下の 5種類のアルゴリズムが利用されている

番号	フィルタ名	説明
0	None	フィルタなし
1	Sub	隣接する左ピクセル色との差分
2	Up	隣接する上ピクセル色との差分
3	Average	左と上のピクセルの平均色との差分
4	Paeth	左、上、左上のピクセルのうち次回出現しそうな色との差分

これらのフィルタリングアルゴリズムは、画像の各水平ラインごとに行われる

フィルタタイプ０：None

該当する画像の水平ラインの先頭に「0」を表す数値を 8ビット長で付加する
先頭に 8ビット付加する以外には、水平ラインに対して特になにも行わない。

f:id:DarkCrowCorvus:20170209000242j:plain

ちなみに、ビット深度が 8 に満たないとき (BitDepth=1,2,4)
各水平ラインの末端がバイト境界になっていなかった場合は、次に出現するバイト境界の地点までの間にパディングが詰められるみたい

次の水平ラインの先頭ビットは必ず、その直近のバイト境界の位置から始まる

f:id:DarkCrowCorvus:20170207233748j:plain

フィルタタイプ１：Sub

該当する画像の水平ラインの先頭に「1」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、左隣のピクセルの値との差分値になる。

f:id:DarkCrowCorvus:20170209000256j:plain

なお、差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる。
　※例えば差の結果が負数の場合 [-1, -2, -3] は [255, 254, 253] のような通りになる。

また先頭のピクセルについては、左隣に参照できるピクセルがないため、左隣のピクセル値 = 0 として扱う

ここまでを見たとおり、フィルタリング処理自身は、データを圧縮するような作用を持っていない。しかも各水平ラインの先頭に、フィルタを識別するための 8ビットを付与するため、このままではむしろデータサイズを増やしてしまうだけのように見える。

ただしこのフィルタリング処理には、その後に続くDeflate の、圧縮効率を底上げするという機能がある。

実際には、Noneを除く 4種類のフィルタリングを使って、PNGイメージ中の値に偏りや同じ値並びを出現させることを行う。

このようにデータを変換することで、Deflateによるハフマン符号化、およびLZ77符号化がうまく働く機会が増えるため、データをより小さく圧縮できるようになる。

f:id:DarkCrowCorvus:20170210084353j:plain

うち「フィルタタイプ 1：Sub」は、横方向にピクセル値の変化が小さい水平ラインに対して効果を発揮する

ここで、フィルタリング処理は、必ず 8ビット単位 で行われるということに注意。
このルールは他のフィルタタイプにも共通する

ビット深度が16であるPNGイメージにおいては、上位8ビット、下位8ビットの2つに分割し、別々にフィルタリング処理を施す

ビット深度が8未満のPNGイメージにNone以外のフィルタタイプを適用する場合は、事前に８ビットに伸長されるらしい...?　サンプルを見つけられなかったため、ちょっと確かではないのだけど..

なお、Subフィルタリングされたピクセルは、
ピクセル値＋左隣のピクセル値の 256による剰余
によって元の値に復元できる

フィルタタイプ２：Up

該当する画像の水平ラインの先頭に「2」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、真上のピクセルの値との差分値になる。 f:id:DarkCrowCorvus:20170211232608j:plain

差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる。
このルールについても、差を扱うすべてのフィルタタイプに共通する

「フィルタタイプ２：Up」は縦方向にピクセルの値の変化が小さい水平ラインに対して効果を発揮する

なお、Upフィルタリングされたピクセルは、
ピクセル値＋真上のピクセル値の 256による剰余
によって元の値に復元できる

フィルタタイプ３：Average

該当する画像の水平ラインの先頭に「3」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、左隣のピクセル値と、真上のピクセル値との平均をとった値との差分値になる。

　filtered value ＝ current － ((left ＋ up) ÷ 2)

f:id:DarkCrowCorvus:20170212174810p:plain

差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる。
また先頭のピクセルについては、左隣に参照できるピクセルがないため、
左隣のピクセル値を 0 として扱い、平均を求める

平均の計算には整数徐算を利用する。
徐算の結果は、値の小さいほうの整数に丸められる（小数点以下切り捨て）

「フィルタタイプ３：Average」は似たピクセル値が密集しているあたりの水平ラインに対して効果を発揮する

なお、Averageフィルタリングされたピクセルは、
ピクセル値＋左隣と真上のピクセル値の平均の 256による剰余
によって元の値に復元できる

フィルタタイプ４：Paeth

該当する画像の水平ラインの先頭に「4」を表す数値を 8ビット長で付加する。
PNGイメージ中に収められるこの水平ライン上の各ピクセルの値は、「Paeth」というアルゴリズムから得られる結果の値との差分値になる。

　filtered value ＝ current － $Paeth$ (left, up, upleft)

f:id:DarkCrowCorvus:20170212230424p:plain

差の結果は非負の 0～255（00～FF）の範囲に収まるよう丸められる

Paethアルゴリズムは、左、上、左上の 3つの隣接するピクセル値から、「この位置に来るであろうピクセル値が、上記 3つのピクセル値のうち、どれと一番近くなりそうか」を予測するために利用される。Alan W. Paethさんが考案した

実際には以下のように求める

int PaethPredictor(int a, int b, int c)
{
    // ┏━━┳━━┓
    // ┃ ｃ ┃ ｂ ┃
    // ┣━━╋━━┫
    // ┃ ａ ┃ ?? ┃
    // ┗━━┻━━┛
    int p = a + b - c;

    // pa = |b - c|　　　横向きの値の変わり具合
    // pb = |a - c|　　　縦向きの値の変わり具合
    // pc = |b-c + a-c|　↑ふたつの合計
    int pa = abs(p - a);    
    int pb = abs(p - b);    
    int pc = abs(p - c);    

    // 横向きのほうがなだらかな値の変化 → 左
    if (pa <= pb && pa <= pc)
        return a;

    // 縦向きのほうがなだらかな値の変化 → 上
    if (pb <= pc)
        return b;
        
    // 縦横それぞれ正反対に値が変化するため中間色を選択 → 左上        
    return c;
}