技術記事

PDFlibPas JBIG2ハーフトーングリッド:HSKIPと負のオフセット

PDFlibPasのネイティブJBIG2ハーフトーンリージョンデコーダーは、ITU-T T.88 §6.6.5.1の定義どおり、HSKIPスキップマスクをHSKIP[ng, mg]としてインデックスします。そして、負のHGXやHGY、あるいは回転によって負の座標に達するグリッドを、真のフロアシフトで配置します。どちらの細部も、エラーを1つも上げずに間違えやすいものです。ハーフトーンリージョンはただ崩れたりずれたりして出てきて、2つの間違いはともに、たまたま対称だったり非負だったりするテストデータの陰に隠れます。しかも2つ目は、JBIG2を遥かに越えて噛みつくDelphiとFree Pascalの性質に根ざしています。符号付き整数へのshrは論理シフトであって、標準が想定する算術の>>ではないのです

ハーフトーンリージョンはJBIG2のリージョンタイプの中で最も稀です。だからデコーダーは、網点化された写真が1つエンコードされてやって来る前に、何千ものスキャン文書を処理できてしまいます。いざ来たときの失敗は厄介です。ファイルはパースされ、セグメント長は合計が合い、ページは正しいサイズで、そしてリージョンがゴミになる

JBIG2ハーフトーンリージョンは実際に何をデコードするのか

JBIG2ハーフトーンリージョンは、パターン辞書から選んだ小さなビットマップのグリッドです。デコーダーの本当の仕事は、すべてのグリッドセルのインデックスと、そのセルが着地するピクセル位置の計算です。パターン辞書はHPW×HPHピクセルのパターンをHNUMPATS個保持します。ハーフトーンリージョンセグメントは続いて、HGW列×HGH行のグリッドと、同じサイズのグレースケール画像、Gray符号化ビットプレーンとしてコードされたものを記述します。各ビットプレーンはHGW×HGHビットマップ上でジェネリックリージョン手順により、最上位プレーンから順にデコードされ、プレーン群が合わさって各セルにパターンインデックスを与えます

セル配置は8ビット分数を持つ固定小数点演算を使います。グリッド原点HGX、HGYは32ビット値のペアで、グリッドベクトルHRX、HRYは隣接セル間のステップを記述します。これが回転グリッドを可能にします。グリッド行mg、グリッド列ngに対し、T.88 §6.6.5はピクセル位置を次のように計算します:

  • x = (HGX + mg × HRY + ng × HRX) >> 8
  • y = (HGY + mg × HRX − ng × HRY) >> 8

スキップマスクはオプションのHENABLESKIPフラグを通して登場します。フラグが立っているとき、§6.6.5.1はHGW×HGHビットマップのHSKIPを組み立て、パターンが完全にリージョンの外側にあるセル——x + HPW <= 0、x >= HBW、y + HPH <= 0、y >= HBHのいずれかを満たすセル——すべてについてHSKIP[ng, mg]を1にセットします。グレースケールビットプレーンは、そのマスクをジェネリックリージョンのスキップビットマップとしてデコードされます。だから算術デコーダーは、スキップされたセルのコンテキストを読みませんし、更新もしません。デコーダーとエンコーダーはHSKIPの1ビット1ビットまで合意しなければなりません。さもないと2つの算術コーダーの同期が崩れます

転置されたHSKIPマスクが正方形でないグリッドしか壊さないのはなぜか

座標を入れ替えたまま書かれたスキップマスクは、正方形でないグリッドでしか姿を現しません。正方形のグリッドでは、入れ替わった座標がどれもマスク内に収まるからです。(column, row)のピクセルアクセサーに対し、(mg, ng)と行を先に渡すビルダーは転置マスクを書き込み、グレースケールビットプレーンのデコーダーはそれを(ng, mg)として読みます。パターン配置ループがマスクをビルダーの入れ替わった順序で読み戻すなら、2者は一致するので、配置ロジックだけのレビューなら素通しです。回す対象に反する名前のループ変数がさらに拍車をかけます。colという名前の変数がグリッド行を回り、隣でRowがグリッド列を回る、という具合です

16×8リージョン上の4×4パターンの5×3グリッドで見てみます。HRX = 1024、HRY = 0では、グリッド列4はx = 16に、グリッド行2はy = 8に着地し、どちらもリージョンの外です。正しいマスクは7セルに印を付けます。列4の全体と行2の全体です。入れ替わった書き込みは、高さ3行しかないマスクの行インデックス3と4にピクセルを立てようとし、範囲外の書き込みを静かに無視するビットマップセッターはそれを捨てます。生き残るのは列2、行0から2。その結果、デコーダーはエンコーダーがコードした2セルをスキップし、エンコーダーがスキップした6セルをデコードします

5×3グリッドに対するPDFlibPasのJBIG2ハーフトーンスキップマスクを示す図。正しいHSKIP[ng, mg]は列4と行2にスキップの印を付けますが、3行のマスクの行3と行4を狙った転置書き込みは静かに捨てられ、列2だけが生き残り、算術コーダーの同期が崩れます
転置されたマスクを露呈させるのは正方形でないグリッドだけです。そして起きたコーダーの非同期は、エラーを上げる代わりにリージョンを崩します

そうなっても算術デコーダーは失敗しません。後続のセルのビットから余分なピクセルをデコードし、コンテキストは間違った隣人を読み、最初の不一致以降のパターンインデックスはすべてノイズになります。だから症状は、いくつかのずれたセルではなく、崩れたリージョンなのです。正方形グリッドでは同じ間違いはしばしば見えません。入れ替わった座標はどれもマスクを出ず、範囲外セルが対角線について対称なとき、たとえば右端と下端に同じ数だけセルがはみ出すグリッドでは、転置マスクはビット単位で正しいマスクと一致します。HENABLESKIPはさらにオプションで、グレースケール画像がMMRコードのときは0でなければならず、エンコーダーが立てることも滅多にありません。間違いが表面化する道はごくわずかです。PDFlibPasでは、ビルダーはHSKIP[ng, mg]と書き込み、配置ループは同じ順序で読みます

負のハーフトーングリッドオフセットが3層で壊れる理由

リージョンの左や上から始まるハーフトーングリッドは、デコーダーの3つの場所で別々に間違い得て、それぞれの間違いが次の1つを隠します。T.88はこのジオメトリを意図的に許しています。網点をリージョンでなくページに合わせるエンコーダーや、回転グリッドを使うエンコーダーは、リージョンが切り取る負のセルコーナーを自然に生み出します。3層すべてが揃って正しくなければなりません。どれか1つだけ正しくしても、症状が変わるだけだからです

層1:符号付きフィールドが符号なしとして読まれる

T.88 §7.4.5.1.2はHGXとHGYを符号付き32ビット値として定義します。符号なしフィールドに使うのと同じ32ビットヘルパー、つまり負の結果をすべて0へクランプするヘルパーで読むと、HGX = -900で始まるはずのグリッドは黙ってリージョン原点へ移動させられます。下の例では、画像全体が2行分低く出ます。このクランプは、他の2層を隠す仕組みでもあります。原点が非負に強制されているかぎり、負の座標はHRY > 0の回転グリッドを通してしか現れ得ず、そこではy = HGY + mg × HRX − ng × HRYが、後のグリッド列でゼロを割ります

層2:shrは>> 8ではない

T.88は>> 8と書いて、マイナス無限大方向へ丸める算術シフトを意味します。その直訳がshr 8ですが、DelphiとFree Pascalでは、符号付き整数へのshrは論理シフトです。符号ビットはゼロとしてシフトインされます。-512を保持するIntegerへのshr 8は、-2の代わりに16777214を返します。y = -2に描かれ下半分に切り詰められるはずのパターンは、1600万行下へ送られ、リージョン外として捨てられます。クラッシュは何もなく、ハーフトーンの最上行がただ消える

層3:ピクセルではなく固定小数点を比較する

固定小数点値に対するスキップテストは、分数が非ゼロのとき、ピクセル位置に対するそれと等価ではありません。論理シフトを回避してシフト前の値にxx + HPW × 256 <= 0をテストするやり方は、T.88テストの等価物に見えます。HGX = -900と4ピクセルパターンでは、-900 + 1024 = 124となり、正なのでセルはスキップされません。標準は先にシフトします。floor(-900 / 256) = -4で、-4 + 4 = 0はx + HPW <= 0を満たし、セルは完全に外側にありスキップされなければなりません。エンコーダーはスキップし、デコーダーはデコードし、グレースケール画像は転置マスクのケースとまったく同じように漂う

負のHGXにあるグリッドに対する3つのJBIG2ハーフトーンの罠を示す図。符号なしヘルパー経由で読まれた符号付きフィールドは0へクランプされ、論理shrとして訳されたT.88の右シフトはパターンを1600万行下へ送り、固定小数点値のスキップテストはエンコーダーがスキップしたセルを保持します
それぞれの間違いが次を隠すため、PDFlibPasは3層すべてを、マスクビルダーと配置ループが共有する1つのHalftoneGridPixelヘルパーで処理します

12×10リージョン上のHGX = -900、HGY = -512、HRX = 1024にある4×4パターンの4×3グリッドで見てみます。グリッド列はx = -4、0、4、8に着地するので、列0は完全に外側でHSKIPに入ります。グリッド行はy = -2、2、6に着地するので、行0は捨てられるのではなく、下の2ピクセル行へ切り詰められなければなりません。層を1つずつ正しくしていくと、この積み重ねが見えてきます:

正しく処理できた層デコードされたリージョン
なしグリッドが原点へ引き寄せられ、画像全体が2行分低い
符号付きHGX / HGYの読み取りのみ最初のグリッド行が欠落し、残りはスキップテストの漂いで崩れる
符号付き読み取り、フロアシフト、ピクセル空間のスキップテストT.88 §6.6.5から計算したページとも、2つの独立したリファレンスデコーダーとも、ピクセル単位で同一

PDFlibPasはこれらすべてを1つのヘルパー、HalftoneGridPixelにまとめています。スキップマスクビルダーと配置ループが共有するものです。座標をInt64で蓄積するので、大きなmg × HRXの積がラップすることはなく、256でマイナス無限大方向へ丸めて除算し、±MaxInt div 2へクランプするので、壊れたグリッドが後続のビットマップ演算をオーバーフローさせられません。スキップテストは、それらのピクセル値をHPW、HPH、HBW、HBHと比較します。§6.6.5.1が述べるとおりにです

Delphiで算術右シフトはどう書くか

Delphiに算術シフト演算子はないので、正しい符号付き右シフトはフロア除算として書くしかなく、素のdivはその除算ではありません。divはゼロ方向へ切り捨てます。非負の値では切り捨てとフロアは一致し、除数の正確な倍数である負の値でも一致します。だから-512 div 256 = -2は手早いテストでは問題なく見えるのです。それ以外ではどこでも食い違います。-900 div 256は-3ですが、フロアは-4。-1 div 256は0ですが、フロアは-1です。分数が非ゼロのJBIG2座標は、まさにdivが間違ったピクセルを返すケースです

DelphiのWin32とWin64コンパイラでは、-512を保持するInteger変数を8右シフトすると16777214になり、-512を保持するInt64では72057594037927934になります。Free Pascalもshrを論理シフトと定義しつつ、算術版としてSystemユニットにSarLongintとSarInt64を同梱しています。ただし、これらの関数はDelphiには存在しないので、2つのコンパイラで共有するコードには独自のヘルパーが要ります:

// フロア除算:AとBの符号にかかわらずマイナス無限大方向へ丸める
// Bは0以外。FloorDiv(Low(Integer), -1)はdivと同様にオーバーフローする
function FloorDiv(A, B: Integer): Integer;
begin
  Result := A div B;
  if (A mod B <> 0) and ((A < 0) <> (B < 0)) then
    Dec(Result);
end;

// 算術右シフト(符号付き値に対するCとT.88の">>")
// Valueが負でも、not Value = -Value - 1は非負なので、そこでは
// 論理shrは安全で、外側のnotが結果を写像し戻す
function SarInt32(Value: Integer; Shift: Integer): Integer;  // Shiftは0..31
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

function SarInt64(Value: Int64; Shift: Integer): Int64;      // Shiftは0..63
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

notのトリックは負の数を決してシフトしないので、コンパイラが符号ビットをどう扱うかに依存せず、Low(Integer)を含めてオーバーフローもしません。両ヘルパーとも、数百万の値でInt64フロアリファレンスと一致することを確認済みです。0から31までのすべてのシフト、Delphi Win32、Delphi Win64、Free Pascal x86_64でのLow(Integer)とHigh(Integer)のエッジもです。座標に触れるユニットテストなら、どれでも入れておく価値のあるサニティチェックです:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  論理シフト、これが罠
  Writeln(V div 256);         // -3        ゼロ方向への切り捨て
  Writeln(FloorDiv(V, 256));  // -4        T.88が>> 8で意味するもの
  Writeln(SarInt32(V, 8));    // -4
end;
座標-900を8右シフトしたPDFlibPasの数直線を示す図。shrは16777212を返し、divは-3へ切り捨てます。FloorDivとSarInt32はどちらも、ITU-T T.88がシフトで意味するフロア値-4に着地します。これが効いてくるのは固定小数点の分数が非ゼロのときだけです
切り捨てとフロアが一致するのは正確な倍数だけです。だから-512 div 256は手早いテストを通過し、-900 div 256は間違ったピクセルを拾います

Math.Floor(V / 256)も-4を返します。ただしDoubleへの迂回は、253を超えるInt64値で精度を失うので、整数ジオメトリは整数のままにしておくべきです

どのPDFlibPas呼び出しがハーフトーンデコーダーを走らせるのか

JBIG2ハーフトーンデコーダーが走るのは、PDFlibPasが組み込みレンダラーでページを描画するときです。描画はピクセルを必要とします。RenderPageToFileもRenderPageToStreamも、ページのJBIG2Decode画像ストリームを通してそこへ届きます。だからハーフトーンページを再描画することが、デコーダーが何を出すかを直接確かめる方法になります。同じデコーダーは他のJBIG2リージョンタイプも扱います。純PascalデコーダーにおけるJBIG2カスタムHuffmanテーブルとDelphiでランダムアクセスJBIG2ファイルをデコードする方法で扱われているものです。そして描画されたビットマップは、PDFページを1ビットモノクロへ描画するような変換へ流れます

uses
  SysUtils, PDFlibrary;

var
  Lib: TPDFlib;
  Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile('scanned-halftone.pdf', '') <> 1 then
      raise Exception.CreateFmt('Load failed, error %d', [Lib.LastErrorCode]);
    for Page := 1 to Lib.PageCount do
      // レンダリングはすべてのJBIG2リージョンをデコードする。ハーフトーンも含めて
      if Lib.RenderPageToFile(150, Page, PDF_RENDER_PNG,
        Format('page-%.3d.png', [Page])) <> 1 then
        Writeln('Page ', Page, ' was not rendered');
  finally
    Lib.Free;
  end;
end.

画像抽出は通常、別の経路を通ります。GetPageImageListはJBIG2画像をネイティブ形式で返し、SaveImageListItemDataToFileやGetImageListItemDataToStringは、ストリームバイトから組み立てられたスタンドアローンJBIG2ファイルを手渡します。ファイルヘッダー、JBIG2Globalsデータ、ページデータを囲むend-of-fileセグメントです。GetImageListItemIntPropertyのプロパティ400は、その種のアイテムに対して6を報告します。この経路では何もデコードされないので、抽出した.jb2が他のビューアーでは正しく見えるのに、描画されたページにはノイズが出るなら、疑うべきはストリームではなくデコード経路です:

var
  ListID, I: Integer;
begin
  Lib.SelectPage(1);
  ListID := Lib.GetPageImageList(0);
  if ListID = 0 then
    Exit;
  try
    for I := 1 to Lib.GetImageListCount(ListID) do
      if Lib.GetImageListItemIntProperty(ListID, I, 400) = 6 then  // スタンドアローンJBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

マスクや色変換が描画フォールバックを強制するときは、アイテムはデコード済みビットマップとして戻り、ハーフトーンデコーダーはちゃんと走ります。画像リストの詳細は、Delphi PDFテキスト、画像、フォント抽出にあります

クイックリファレンス:JBIG2ハーフトーングリッドのルール

  • スキップマスクはHSKIP[ng, mg]とグリッド列を先にインデックスし、セルを配置するどこでも同じ順序で読み戻す(T.88 §6.6.5.1)
  • ハーフトーンやグリッドのコードは、正方形でないグリッドと非対称な範囲外セルのセットでテストする。正方形グリッドは転置インデックスを完全に隠せる
  • HGXとHGYは符号付き32ビット値として読む(T.88 §7.4.5.1.2)。負をクランプする符号なしヘルパー経由では決して読まない
  • 標準の>> 8は256によるフロア除算として訳す。shr 8でもdiv 256でもなく
  • スキップテストはシフト後のピクセル位置で走らせる。分数が非ゼロのときは固定小数点形式が必ず食い違う。HGX = -900と4ピクセルパターンの例が示すとおり
  • グリッド座標はInt64で蓄積し、ビットマップコードへ渡す前にクランプする。壊れたグリッドがオーバーフローできないように

PDFlibPasは、ハーフトーンスキップマスク、負のグリッド原点、回転グリッドをT.88の指定どおりに扱うネイティブPascal JBIG2デコーダーで、DelphiとC++BuilderからPDF文書を描画、抽出、編集します。機能、エディション、トライアルダウンロードは、PDFlibPas Delphi PDF libraryを参照してください