🐷

G3 FaxとG4 Faxの圧縮

2022/05/17に公開

二値画像

画像圧縮

tech

二値画像の圧縮

二値画像は白と黒だけで構成されている画像である。二値画像は、他の画像とは違った圧縮の方法が使われることが多い。ところでインターネットで流れている画像方式には二値画像専用圧縮は存在しないのだがPDFでは使われているのである。PDFがサポートしているので二値画像専用の圧縮は残り続けるのであった。ここではG3/G4について記すが、更に新しい規格にJBIG/JBIG2などが存在する。

日本語の資料

Group3 Fax圧縮とは

Group3 Fax圧縮は、1980年にCCITT ITU-T Recommendation T.4 : Standardization of Group 3 facsimile terminals for document transmissionで定義されたFaxの圧縮方式である。中身は二値画像の圧縮アルゴリズムである。中身はランレングスを改良ハフマンで符号化しているだけなのだが、テーブルが大きくてデバッグが面倒。実際には伝送プロトコルまで含んでいるのだが、画像圧縮・伸長時プロトコルの部分は実装する必要が無いので無視する。ただし、1980年に作られた規格で、当時はデータの伝送エラーが多発した時代なので修正用プロトコルが積んであるのであるのだがTIFFデータを読むとき伝送エラーは考えないのでTIFFに搭載されているG3/G4圧縮にはそのようなコードは存在しない。

Group3 1D圧縮

1D圧縮は、ランレングスを改良ハフマンで符号化しているだけある。行の最後にEOLと呼ばれるコードを付加する。これは途中でデータエラーが発生した場合、次の行で復帰するためのコードである。

Group3 2D圧縮

2D圧縮は、上の行との差分コードだけを送る形式である。サイズは半分に減るようである。ただし、Group3の場合、一定行ごとに1D圧縮のコードを送る必要がある。2D圧縮はデータエラーが発生すると後の行までその影響が波及するため回復するために必要があるのである。また、データが短すぎると複合機の処理が追いつかない可能性があるのでEOLの前に0をfillする仕様になっている。

Group4 圧縮

Group4 圧縮は1984年CCITT ITU-T Recommendation T.6で定義されてた規格である。ただし圧縮の原理は、Group3 2D圧縮とほぼ同じである。しかし、ISDNなどのデジタル通信を前提とした規格なので、エラーはさらに下のレイヤーで回復していることを期待しておりエラー処理が一切入っていない。行ごとのEOLは存在せず、1D圧縮のコードも存在しない。つまり、最初に送られてくる一行何pixelのデータやデータ処理にバグがあると目も当てられない状況になる。

圧縮の仕組み

基本的にファクシミリで送信する文書は、白が続き、黒が少し続き、白が続くと言う構造になっているため、白用のハフマンコードと黒用のハフマンコードの二種類を保有している。そして、白の長さ→黒の長さ→白の長さ→黒の長さと繰り返しハフマンコードを送信する。

受信機は黒の時だけプリントし、白の時は何もしないと言う処理をおこなう。なぜなら、ファクシミリは白い紙に伝送するからである。そしてスペースの大半は白になる。したがって他のデジタル画像と異なり、0が白（なにもしない）、1が黒になる。

また伝送の仕組みの関係かLSBからデータが格納されている。これは伝送自体の仕様と関連している様である。記憶ではRS-232-Cは非同期がMSBから送信、同期がLSBから送信していた記憶があるのだが覚えてない。G3の規格もLSBからデータを送信しているのであろう。しかし、受信機はbyte単位ではなくbit単位でデータが送られてきた順番通り処理していただけの気がする。しかし同じ事をPCで処理するとLSBは意外に面倒。これはCPUがほぼMSBを想定しているからである。そのため出力はbit逆転をしないと行けない。

0x87

MSB         LSB
7 6 5 4 3 2 1 0
1 0 0 0 0 1 1 1

MSB LSB 逆転

7 6 5 4 3 2 1 0
1 1 1 0 0 0 0 1

0xe1

一次元圧縮 MH(Modified Huffman)方式

G3の一次元圧縮はランレングス＋改良ハフマン圧縮である。一番最初にEOLを出力し、それから最初の行の処理始める。行ごとの処理は最初に白が続く数、次に黒が続く数を出力し、行の最後にEOL(0000 0000 0001)を出力する。

例

○○○○○○○●●●○○○○○○○○○●○○○○○●●●●○○○○○○

出力 (7,3),(9,1),(5,4),(6,EOL)

ただし、白と黒のハフマン符号が異なるので最終的には以下になる。

1111 10 10100 010 1100 011 1110 000000000001

ファクシミリで伝送する場合、bitをそのまま出力するだけで十分だが、PCに格納する場合、byteにまとめて逆転する必要がある。

11111010 10001011 000111110 00000000 0001xxxx

ここからMSBに変換

01011111 11010001 011111000 00000000 xxxx1000

行の最初が黒の場合は白0からカウントする。

●●●○○○○○○○●●●○○○○○○○○○●○○○○○○●

出力 (0,3),(7,3),(9,1),(5,1),EOL 黒が最後に来るパターンは少ないので確認できない。

ただし、ハフマン符号は0-63と64から64刻みで2560までしか用意されていない。そのため64以上の数字は以下に変換し、ハフマン符号化する。

70 = 64 + 6
1290 = 1280 + 10
7001 = 2560 + 2560 + 1856 + 25
64 = 64 + 0

展開するときは0-63が来るまで加算していく。そのため、64以上の数字をマークアップコード、0-63の数字をターミネイトコードと呼ぶ。

二次元圧縮 MR(Modified Read)方式

二次元圧縮は上の行との差分だけを出力する。ただし、最初の前の行は全て白と仮定する。また一次元符号化の時の一番最初が白のルールも変わらない。

二次元圧縮にはモードが5つあり、そのどれかを利用する。仕様にエクステンション（拡張モード）が存在するがほぼ使われて居ない。一応規格にはアンコンプレスモードが存在するが、拡張モードをlibtiffはエラーとして処理、pdf.jsも拡張モード自体をエラーで処理しておりサポートしたところでメジャーなリーダーが読み取れないので無視してよさそう。

ただし、G3 FAXの場合、k行置きに一次元圧縮を出力する必要がある。kは以下で決まる。k行置きに1bitのフラグを送信する。一次元の時はbit1になる。恐らくエラー発生時に復旧しやすくするための仕組みである。

標準 k = 2
オプション
- 200ライン/25.4mm k = 4
- 300ライン/25.4mm k = 6
- 400ライン/25.4 mm k = 8
- 600ライン/25.4 mm k = 12
- 800ライン/25.4mm k = 16
- 1200ライン/25.4 mm k = 24

復号するときはEOLの後の最初の1bitを読み出し、0ならば二次元圧縮、1ならば一次元圧縮として残りを処理する。

なお、二次元圧縮では該当行の処理位置をa0とし、次の変化点をa1,その次をa2。前の行の変化点をb0,b1,b2と記す。

またEOLの手前にFill bitと言う0の連続が入る場合がある。これは本来、処理が追いつかない場合の時間稼ぎに挟むためのもの。

また仕様書にはページの終わりにEOL+1を6回送信すると書いてあるが、TIFFでは省略されているようである。

PASSモード

PASSモードは二次元圧縮のモードの一つである。以下の様な時にPASSモードで出力する。

    b0    b1  b2
-1　○○○○○○●●●●○○○●●●　
 0　○○○○○○○○○○○○○○○●
    a0　　　　a0'
 　 Pass

a0と同じ色がb2まで続く場合Passを出力しb0をa0'に設定する。

Horizontalモード

水平モードである。このモードの出力は、一次元符号化のワンセットと同じである。ただし、黒が先に来る場合がある。これは後の垂直モードが使えない場合に使用する。a0はa1、次にa2になる。


    b0     　   b1
-1　●○○○○○○○○○○○●●●　
 0　○○○○●●●●○○○○○○●●
    a0　a1  a2　　　
 　 Horiz(w 4,b 4) 

    b0
-1　○○○○○○○○○○○○○○○○○○○　
 0　●●●●●●●●○○○○○○○○○○●
    a0      a1       a2　　　
 　 Horiz(b 8,w 10)

Verticalモード

Virtical(垂直)モードは更に上の行から何PixelずれているかでVr3,Vr2,Vr1,V,Vl1,Vl2,Vl3が存在する。rは右で、lが左である。


    b0     b1 b2 b3
-1　○○○○○○●●●●○○○●●●●●●　
 0　○○○○○○●●●●○○○●●●●●●
    a0    a1  a2  a3
    V     V   V   V

a1 = b1 の時は Vモードになる。


    b0    b1 b2 b3
-1　○○○○○○●●●●○○○●●●●●●　
 0　○○○○○●●●●●○○○○●●●●●
    a0   a1  a2   a3
     Vl1   V   Vr1

a1がb1より左に1-3pixelずれている場合は、Vl1-3になる。右に1-3pixelずれている場合は、Vr1-3になる。

G4 FAX MMR(Modified Modified Read)方式

単純にCCITT圧縮と呼んだ場合はこの方式を指していることが多い。G4 FAXは先述の二次元圧縮のみで構成されている。最初の行の前の行は全て白として扱う。またG3と異なり、ページの最後以外にEOL(000000000001)は出てこない。二次元圧縮しかないので行ごとのフラグも存在しない。そのため改行はデコーダが一番端までデコードしたと解釈した時点でとりおこなう事になる。

ページの終わりに000000000001 000000000001 を送信することになっているこれをEOFBと言う。ところで実際のTIFF画像を解析してみたら最後に000000000001が8回続いていたものが存在したのでG4 FAXの場合、EOLを検出した時点でデコードを終了して良い気がする。エンコーダが間違っている部分をまともに解析しても仕方が無い。

復号の方法

一次元圧縮の場合はw,bの順でハフマン復号し、出力する。

二次元圧縮の場合は、a0の直後に来る変化点b1を探すことから始まる。a0が白であればb1は黒、a0が黒ならb1は白になるので、前の行のa0より後に来る変化点を探すことになる。

面倒なのはPassモードで、a0' = b2と仮置きし、次の出力でb2の後に来る変化点を探すことになる（Horizの場合はデータがそのまま入って居る）

このとき前の行をスキャンする必要があるのかと言えば実は必要無い。変化点(a0)だけを記録していけば良いのである。ただし、Passモードのa0'は記録しない。

そうすることでデータは必ず白、黒、白、黒の順番で並ぶのである。

●○○○○○●●●●○○○●●●

例えば上の場合のa0は、0,1,6,10,13,16になる。そこからa0に一番近いb1を探せば良い。通常はカウンタを一つ飛ばすときだが、Horizで細かい変化が続く場合、b1がa0と同じか小さい場合がある。その場合、b1がa0より大きくなるまでスキャンする必要がある。ただし変化点は白黒交互なので2ずつスキップしないと色が逆転するので注意。

なお、このケースでは最初にVが来る事は無い。Vl1かHorizになるはずである。ただこの方法を使う場合Vlが来た時でVlが来た時はポインタを一度2つ戻す必要がある。これはb1が有るべき場所より先に進んでしまう事があるから。

まぁ、このアルゴリズムでほとんど速くならなかったのですけど。他のルーチンが遙かに重くて誤差値に隠れてしまった。