Technischer Artikel

PDFlibPas JBIG2-Halftone-Raster: HSKIP und negative Offsets

Der native JBIG2-Halftone-Region-Dekoder in PDFlibPas indexiert die HSKIP-Skip-Maske als HSKIP[ng, mg], wie ITU-T T.88 §6.6.5.1 es definiert, und platziert Raster, die zu negativen Koordinaten kommen – durch ein negatives HGX oder HGY oder durch Rotation – mit einem echten Floor-Shift. Beide Details sind leicht falsch zu machen, ohne dass ein Fehler geworfen würde: Die Halftone-Region kommt einfach als Datenmüll oder verschoben heraus, und beide Fehler verstecken sich hinter Testdaten, die zufällig symmetrisch oder nicht negativ sind. Der zweite dreht sich an einer Eigenschaft von Delphi und Free Pascal auf, die weit über JBIG2 hinaus zubeißt: shr auf einer vorzeichenbehafteten Ganzzahl ist ein logischer Shift, nicht der arithmetische >>, den der Standard annimmt

Halftone-Regionen sind der seltenste JBIG2-Regionstyp, ein Dekoder kann also Tausende gescannter Dokumente verarbeiten, bevor ihm eine als solche kodierte gerasterte Fotografie begegnet. Wenn es so weit ist, ist der Ausfall übel: Die Datei parst, die Segmentlängen addieren sich, die Seite hat die richtige Größe, und die Region ist Müll

Was dekodiert eine JBIG2-Halftone-Region eigentlich?

Eine JBIG2-Halftone-Region ist ein Raster kleiner Bitmaps aus einem Pattern-Dictionary, und die eigentliche Arbeit des Dekoders besteht darin, für jede Rasterzelle einen Index und die Pixelposition zu berechnen, an der diese Zelle landet. Das Pattern-Dictionary hält HNUMPATS Patterns von HPW × HPH Pixeln. Das Halftone-Region-Segment beschreibt dann ein Raster aus HGW Spalten mal HGH Zeilen und ein Graustufenbild derselben Größe, kodiert als Gray-kodierte Bitplanes. Jedes Bitplane wird mit der Generic-Region-Prozedur über eine HGW × HGH-Bitmap dekodiert, höchstwertige Plane zuerst, und die Planes zusammen geben jeder Zelle ihren Pattern-Index

Die Zellplatzierung nutzt Fixed-Point-Arithmetik mit 8-Bit-Bruchteil. Der Rasterursprung HGX, HGY ist ein Paar 32-Bit-Werte, und der Rastervektor HRX, HRY beschreibt den Schritt zwischen Nachbarzellen, was ein rotiertes Raster erlaubt. Für Rasterzeile mg und Rasterspalte ng berechnet T.88 §6.6.5 die Pixelposition als:

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

Die Skip-Maske kommt über das optionale HENABLESKIP-Flag ins Spiel. Ist das Flag gesetzt, baut §6.6.5.1 eine HGW × HGH-Bitmap HSKIP und setzt HSKIP[ng, mg] auf 1 für jede Zelle, deren Pattern vollständig außerhalb der Region liegt: x + HPW <= 0, x >= HBW, y + HPH <= 0 oder y >= HBH. Die Graustufen-Bitplanes werden dann mit dieser Maske als Skip-Bitmap der Generic-Region dekodiert, der arithmetische Dekoder liest also weder Kontext für eine übersprungene Zelle noch aktualisiert er ihn. Dekoder und Encoder müssen sich in jedem Bit von HSKIP einig sein, sonst geraten die beiden arithmetischen Coder aus dem Tritt

Warum bricht eine transponierte HSKIP-Maske nur nicht-quadratische Raster?

Eine Skip-Maske, die mit vertauschten Koordinaten geschrieben wurde, zeigt sich nur an einem nicht-quadratischen Raster, denn ein quadratisches Raster hält jede vertauschte Koordinate innerhalb der Maske. Bei einem (column, row)-Pixel-Accessor schreibt ein Builder, der (mg, ng) übergibt, Zeile zuerst, die transponierte Maske, während der Graustufen-Bitplane-Dekoder sie als (ng, mg) liest. Wenn die Pattern-Platzierungsschleife die Maske in der vertauschten Reihenfolge des Builders zurückliest, sind sich die beiden einig, und eine Überprüfung allein der Platzierungslogik lässt sie durchgehen. Schleifenvariablen, die gegen das benannt sind, worüber sie iterieren, verschärfen das – etwa ein col, der über Rasterzeilen läuft, neben einem Row, der über Rasterspalten läuft

Nehmen Sie ein 5 × 3-Raster aus 4 × 4-Patterns auf einer 16 × 8-Region. Mit HRX = 1024 und HRY = 0 landet Rasterspalte 4 bei x = 16 und Rasterzeile 2 bei y = 8, beide außerhalb der Region. Die korrekte Maske markiert sieben Zellen: die ganze Spalte 4 und die ganze Zeile 2. Die vertauschten Schreibvorgänge versuchen, Pixel in den Zeilenindizes 3 und 4 einer nur drei Zeilen hohen Maske zu setzen, und ein Bitmap-Setter, der außerhalb des Bereichs liegende Schreibvorgänge stillschweigend ignoriert, wirft sie weg. Übrig bleibt Spalte 2, Zeilen 0 bis 2. Der Dekoder überspringt also zwei Zellen, die der Encoder kodiert hat, und dekodiert sechs Zellen, die der Encoder übersprungen hat

PDFlibPas-JBIG2-Halftone-Skip-Masken für ein 5 mal 3 Raster, bei dem die korrekte HSKIP[ng, mg] Spalte 4 und Zeile 2 als übersprungen markiert, während die transponierten Schreibvorgänge, die auf Zeilen 3 und 4 einer dreizeiligen Maske zielten, stillschweigend verworfen werden und nur Spalte 2 überlebt, wodurch die arithmetischen Coder außer Takt geraten
Nur ein nicht-quadratisches Raster legt eine transponierte Maske offen, und die daraus folgende Coder-Entsynchronisierung macht die Region zu Datenmüll, statt einen Fehler zu werfen

Der arithmetische Dekoder scheitert nicht, wenn das passiert. Er dekodiert zusätzliche Pixel aus Bits, die späteren Zellen gehören, seine Kontexte lesen falsche Nachbarn, und jeder Pattern-Index nach der ersten Diskrepanz ist Rauschen – deshalb ist das Symptom eine vermüllte Region statt ein paar verrutschter Zellen. Auf einem quadratischen Raster ist derselbe Fehler oft unsichtbar: Keine vertauschte Koordinate verlässt die Maske, und wenn die Zellen außerhalb der Region symmetrisch zur Diagonale liegen – ein Raster, das rechte und untere Kante um dieselbe Zellenzahl überragt, zum Beispiel –, ist die transponierte Maske bit für bit die korrekte. HENABLESKIP ist zudem optional, muss 0 sein, wenn das Graustufenbild MMR-kodiert ist, und wird von Encodern selten gesetzt, der Fehler hat also sehr wenige Möglichkeiten aufzutauchen. In PDFlibPas schreibt der Builder HSKIP[ng, mg], und die Platzierungsschleife liest dieselbe Reihenfolge

Warum scheitern negative Halftone-Grid-Offsets in drei Schichten?

Ein Halftone-Raster, das links von oder über seiner Region beginnt, kann an drei getrennten Stellen in einem Dekoder schiefgehen, und jeder Fehler versteckt den nächsten. T.88 erlaubt diese Geometrie mit Absicht. Ein Encoder, der sein Raster an der Seite statt an der Region ausrichtet oder ein rotiertes Raster nutzt, produziert von Natur aus negative Zellecken, die die Region beschneidet. Alle drei Schichten müssen zusammen stimmen, denn jede einzeln richtige ändert nur das Symptom

Schicht 1: ein Vorzeichenfeld als vorzeichenlos gelesen

T.88 §7.4.5.1.2 definiert HGX und HGY als vorzeichenbehaftete 32-Bit-Werte. Liest man sie durch denselben 32-Bit-Helfer, der für vorzeichenlose Felder benutzt wird und jedes negative Ergebnis auf 0 klemmt, wird ein Raster, das bei HGX = -900 beginnen sollte, stillschweigend auf den Regionsursprung geschoben; im Beispiel unten kommt das ganze Bild zwei Zeilen zu tief heraus. Die Klemme versteckt auch die anderen beiden Schichten: Bei einem erzwungen nicht-negativen Ursprung kann eine negative Koordinate nur über ein rotiertes Raster mit HRY > 0 erscheinen, wo y = HGY + mg × HRX − ng × HRY für spätere Rasterspalten unter null fällt

Schicht 2: shr ist nicht >> 8

T.88 schreibt >> 8 und meint einen arithmetischen Shift, der gegen minus unendlich rundet. Die wörtliche Übersetzung ist shr 8, und in Delphi und Free Pascal ist shr auf einer vorzeichenbehafteten Ganzzahl ein logischer Shift: Als Vorzeichenbit wird eine Null hereingeschoben. Für einen Integer mit -512 liefert shr 8 16777214 statt -2. Ein Pattern, das bei y = -2 gezeichnet und auf seine untere Hälfte beschnitten werden sollte, wird 16 Millionen Zeilen nach unten geschickt und als außerhalb der Region liegend verworfen. Nichts stürzt ab; die oberste Zeile des Halftone verschwindet einfach

Schicht 3: Fixed Point statt Pixel verglichen

Ein Skip-Test auf Fixed-Point-Werten ist nicht äquivalent zu einem auf Pixelpositionen, sobald der Bruchteil ungleich null ist. Dem logischen Shift auszuweichen, indem man xx + HPW × 256 <= 0 auf dem unverschobenen Wert testet, sieht wie ein Äquivalent des T.88-Tests aus. Mit HGX = -900 und einem 4-Pixel-Pattern ergibt das -900 + 1024 = 124, was positiv ist, die Zelle wird also nicht übersprungen. Der Standard shiftet zuerst: floor(-900 / 256) = -4, und -4 + 4 = 0 erfüllt x + HPW <= 0, die Zelle liegt also vollständig außerhalb und muss übersprungen werden. Der Encoder überspringt sie, der Dekoder dekodiert sie, und das Graustufenbild driftet exakt wie im Fall der transponierten Maske

Drei JBIG2-Halftone-Fallen für ein Raster bei negativem HGX: ein über einen vorzeichenlosen Helfer gelesenes Vorzeichenfeld, das auf null geklemmt wird, der als logischer shr übersetzte T.88-Shift rechts, der ein Pattern 16 Millionen Zeilen nach unten schickt, und ein Skip-Test auf Fixed-Point-Werten, der eine vom Encoder übersprungene Zelle behält
Jeder Fehler versteckt den nächsten, deshalb behandelt PDFlibPas alle drei Schichten in einem gemeinsamen HalftoneGridPixel-Helfer, den der Masken-Builder und die Platzierungsschleife nutzen

Nehmen Sie ein 4 × 3-Raster aus 4 × 4-Patterns bei HGX = -900, HGY = -512, HRX = 1024 auf einer 12 × 10-Region. Rasterspalten landen bei x = -4, 0, 4 und 8, Spalte 0 liegt also vollständig außerhalb und gehört in HSKIP; Rasterzeilen landen bei y = -2, 2 und 6, Zeile 0 muss also auf ihre unteren zwei Pixelzeilen beschnitten statt verworfen werden. Die Schichten einzeln richtig zu setzen zeigt den Stapel:

Korrekt behandelte SchichtenDekodierte Region
KeineRaster zum Ursprung gezogen, das ganze Bild zwei Zeilen zu tief
Nur Lesen von HGX / HGY mit VorzeichenErste Rasterzeile fehlt, der Rest durch die Skip-Test-Drift vermüllt
Vorzeichenbehaftetes Lesen, Floor-Shift und Skip-Test im PixelraumIdentisch, Pixel für Pixel, mit der aus T.88 §6.6.5 berechneten Seite und mit zwei unabhängigen Referenzdekodern

PDFlibPas steckt das alles in einen einzigen Helfer, HalftoneGridPixel, geteilt zwischen Skip-Masken-Builder und Platzierungsschleife. Er akkumuliert die Koordinate in Int64, sodass ein großes mg × HRX-Produkt nicht überlaufen kann, dividiert durch 256 mit Rundung gegen minus unendlich und klemmt auf ±MaxInt div 2, damit ein korruptes Raster keine spätere Bitmap-Arithmetik überlaufen kann. Der Skip-Test vergleicht diese Pixelwerte gegen HPW, HPH, HBW und HBH, exakt wie §6.6.5.1 es formuliert

Wie schreibt man einen arithmetischen Right Shift in Delphi?

Delphi hat keinen arithmetischen Shift-Operator, ein korrekter vorzeichenbehafteter Right Shift muss also als Floor-Division geschrieben werden, und das schlichte div ist nicht diese Division. div schneidet gegen null ab. Für nicht-negative Werte stimmen Abschneiden und Floor überein, und sie stimmen auch für negative Werte überein, die exakte Vielfache des Divisors sind — deshalb sieht -512 div 256 = -2 in einem Schnelltest fein aus. Überall sonst sind sie sich uneinig: -900 div 256 ist -3, der Floor ist -4, und -1 div 256 ist 0, der Floor ist -1. Eine JBIG2-Koordinate mit von null verschiedenem Bruchteil ist exakt der Fall, in dem div das falsche Pixel liefert

Auf den Delphi-Compilern Win32 und Win64 liefert eine Integer-Variable mit -512, um 8 nach rechts geschoben, 16777214, und ein Int64 mit -512 liefert 72057594037927934. Free Pascal definiert shr ebenfalls als logischen Shift und liefert SarLongint und SarInt64 in seiner System-Unit für die arithmetische Variante, aber diese Funktionen existieren in Delphi nicht, also braucht zwischen beiden Compilern geteilter Code einen eigenen Helfer:

// Floor-Division: rundet gegen minus unendlich für jedes Vorzeichen von A und B.
// B darf nicht 0 sein, und FloorDiv(Low(Integer), -1) überläuft genau wie 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;

// Arithmetischer Right Shift (das ">>" von C und T.88 auf Werten mit Vorzeichen).
// Bei negativem Value ist not Value = -Value - 1 nicht negativ, der logische
// shr ist dort sicher, und das äußere not bildet das Ergebnis zurück
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;

Der not-Trick shiftet nie eine negative Zahl, hängt also nicht davon ab, wie ein Compiler das Vorzeichenbit behandelt, und er läuft nie über, auch nicht für Low(Integer). Beide Helfer wurden gegen eine Int64-Floor-Referenz über mehrere Millionen Werte geprüft, jeder Shift von 0 bis 31 und die Ränder Low(Integer) und High(Integer) auf Delphi Win32, Delphi Win64 und Free Pascal x86_64. Ein Sanity-Check, den jeder Unit-Test verdient, der Koordinaten anfasst:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logischer Shift, die Falle
  Writeln(V div 256);         // -3        Abschneiden gegen null
  Writeln(FloorDiv(V, 256));  // -4        was T.88 mit >> 8 meint
  Writeln(SarInt32(V, 8));    // -4
end;
PDFlibPas-Zahlenstrahl für die Koordinate -900, um 8 nach rechts geschoben: shr liefert 16777212, div schneidet auf -3 ab, während FloorDiv und SarInt32 beide auf dem Floor-Wert -4 landen, den ITU-T T.88 mit dem Shift meint, was nur zählt, wenn der Fixed-Point-Bruchteil ungleich null ist
Abschneiden und Floor stimmen nur bei exakten Vielfachen überein, deshalb besteht -512 div 256 einen Schnelltest und -900 div 256 wählt das falsche Pixel

Math.Floor(V / 256) liefert ebenfalls -4, aber sein Umweg über Double verliert Präzision für Int64-Werte über 253, Ganzzahl-Geometrie sollte also in Ganzzahlen bleiben

Welche PDFlibPas-Aufrufe fahren den Halftone-Dekoder?

Der JBIG2-Halftone-Dekoder läuft, wenn PDFlibPas eine Seite mit dem eingebauten Renderer rendert, denn Rendern braucht Pixel. RenderPageToFile und RenderPageToStream erreichen ihn beide über die JBIG2Decode-Bildstreams der Seite, ein Halftone-Blatt also erneut zu rendern ist der direkte Weg zu prüfen, was der Dekoder produziert. Derselbe Dekoder behandelt die anderen JBIG2-Regionstypen, behandelt in JBIG2 Custom Huffman Tables im Pure-Pascal-Dekoder und Random-Access-JBIG2-Dateien in Delphi dekodieren, und die gerenderte Bitmap füttert Konversionen wie PDF-Seiten nach 1-Bit-Monochrome rendern

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
      // Rendering dekodiert jede JBIG2-Region, Halftones eingeschlossen
      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.

Die Bildextraktion nimmt normalerweise einen anderen Pfad. GetPageImageList liefert JBIG2-Bilder in Native-Form, und SaveImageListItemDataToFile oder GetImageListItemDataToString gibt Ihnen eine eigenständige JBIG2-Datei aus den Stream-Bytes: der Dateiheader, die JBIG2Globals-Daten und ein End-of-File-Segment um die Seitendaten. Property 400 von GetImageListItemIntProperty meldet 6 für so ein Item. Auf diesem Pfad wird nichts dekodiert, eine extrahierte .jb2, die in einem anderen Viewer korrekt aussieht, während die gerenderte Seite Rauschen zeigt, zeigt also auf den Dekodierpfad und nicht auf den Stream:

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  // standalone JBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

Wenn Masken oder Farbumwandlung einen gerenderten Fallback erzwingen, kommt das Item als dekodierte Bitmap zurück, und der Halftone-Dekoder fährt dann doch. Mehr zu Bildlisten in Delphi PDF Text-, Bild- und Font-Extraktion

Kurzreferenz: Regeln für JBIG2-Halftone-Raster

  • Die Skip-Maske als HSKIP[ng, mg] indexieren, Rasterspalte zuerst, und sie überall dort in derselben Reihenfolge zurücklesen, wo Zellen platziert werden (T.88 §6.6.5.1)
  • Jeden Halftone- oder Raster-Code mit einem nicht-quadratischen Raster und einer asymmetrischen Menge von Zellen außerhalb der Region testen, denn ein quadratisches Raster kann einen transponierten Index komplett verstecken
  • HGX und HGY als vorzeichenbehaftete 32-Bit-Werte lesen (T.88 §7.4.5.1.2), nie über einen vorzeichenlosen Helfer, der Negative klemmt
  • Das >> 8 des Standards als Floor-Division durch 256 übersetzen, weder als shr 8 noch als div 256
  • Den Skip-Test auf verschobenen Pixelpositionen fahren; die Fixed-Point-Form weicht immer dann ab, wenn der Bruchteil ungleich null ist, wie HGX = -900 mit einem 4-Pixel-Pattern zeigt
  • Rasterkoordinaten in Int64 akkumulieren und klemmen, bevor sie in Bitmap-Code wandern, damit ein korruptes Raster nicht überlaufen kann

PDFlibPas rendert, extrahiert und editiert PDF-Dokumente aus Delphi und C++Builder mit einem nativen Pascal-JBIG2-Dekoder, der Halftone-Skip-Masken, negative Rasterursprünge und rotierte Raster so behandelt, wie T.88 es spezifiziert. Features, Editionen und einen Testdownload finden Sie auf der PDFlibPas Delphi PDF library