Articolo tecnico

Griglie halftone JBIG2 in PDFlibPas: HSKIP e offset negativi

Il decoder nativo delle regioni halftone JBIG2 in PDFlibPas indica la maschera skip HSKIP come HSKIP[ng, mg], come la definisce ITU-T T.88 §6.6.5.1, e posiziona le griglie che raggiungono coordinate negative, tramite un HGX o HGY negativo o tramite rotazione, con uno shift floor vero. Entrambi i dettagli sono facili da sbagliare senza che alcun errore venga sollevato: la regione halftone semplicemente esce conficcata o spostata, e entrambi gli errori si nascondono dietro dati di prova che per caso sono simmetrici o non negativi. Il secondo è innescato da una proprietà di Delphi e Free Pascal che morde ben oltre JBIG2: shr su un intero con segno è uno shift logico, non la >> aritmetica che lo standard presume

Le regioni halftone sono il tipo di regione JBIG2 meno comune, così un decoder può processare migliaia di documenti scansionati prima di incontrare una fotografia a retino codificata come tale. Quando ci arriva, il guasto è cattivo: il file si analizza, le lunghezze dei segmenti tornano, la pagina ha la dimensione giusta, e la regione è spazzatura

Che cosa decodifica davvero una regione halftone JBIG2?

Una regione halftone JBIG2 è una griglia di piccole bitmap scelte da un dizionario di pattern, e il lavoro vero del decoder è calcolare un indice per ogni cella della griglia e la posizione in pixel dove quella cella atterra. Il dizionario di pattern contiene HNUMPATS pattern di HPW × HPH pixel. Il segmento di regione halftone descrive poi una griglia di HGW colonne per HGH righe e un'immagine a scala di grigi della stessa dimensione, codificata come bitplane Gray-coded. Ogni bitplane viene decodificato con la procedura di regione generica su una bitmap HGW × HGH, piano più significativo prima, e i piani insieme danno a ogni cella il suo indice di pattern

Il posizionamento delle celle usa aritmetica fixed point con una frazione a 8 bit. L'origine della griglia HGX, HGY è una coppia di valori a 32 bit, e il vettore griglia HRX, HRY descrive il passo tra celle vicine, il che consente una griglia ruotata. Per la riga griglia mg e la colonna griglia ng, T.88 §6.6.5 calcola la posizione in pixel come:

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

La maschera skip entra attraverso il flag opzionale HENABLESKIP. Quando il flag è impostato, §6.6.5.1 costruisce una bitmap HGW × HGH HSKIP e imposta HSKIP[ng, mg] a 1 per ogni cella il cui pattern giace interamente fuori dalla regione: x + HPW <= 0, x >= HBW, y + HPH <= 0 oppure y >= HBH. I bitplane a scala di grigi vengono poi decodificati con quella maschera come bitmap skip della regione generica, così il decoder aritmetico né legge né aggiorna contesto per una cella saltata. Decoder ed encoder devono concordare su ogni bit di HSKIP, o i due codificatori aritmetici perdono il passo

Perché una maschera HSKIP trasposta rompe solo le griglie non quadrate?

Una maschera skip scritta con le coordinate scambiate si vede solo su una griglia non quadrata, perché una griglia quadrata tiene ogni coordinata scambiata dentro la maschera. Con un accessore pixel (column, row), un costruttore che passa (mg, ng), riga prima, scrive la maschera trasposta, mentre il decoder dei bitplane a scala di grigi la legge come (ng, mg). Se il ciclo di posizionamento dei pattern rilegge la maschera nell'ordine scambiato del costruttore, i due sono d'accordo, e una revisione della sola logica di posizionamento la fa passare. Le variabili di ciclo con nomi contro ciò che iterano peggiorano le cose, come una col che cammina le righe della griglia accanto a una Row che cammina le colonne

Prendi una griglia 5 × 3 di pattern 4 × 4 su una regione 16 × 8. Con HRX = 1024 e HRY = 0, la colonna griglia 4 atterra a x = 16 e la riga griglia 2 a y = 8, entrambe fuori dalla regione. La maschera corretta marca sette celle: tutta la colonna 4 e tutta la riga 2. Le scritture scambiate provano a impostare pixel agli indici di riga 3 e 4 in una maschera alta solo tre righe, e un setter della bitmap che ignora silenziosamente le scritture fuori range le scarta. Ciò che sopravvive è la colonna 2, righe da 0 a 2. Il decoder salta quindi due celle che l'encoder ha codificato, e decodifica sei celle che l'encoder ha saltato

Maschere skip halftone JBIG2 di PDFlibPas per una griglia 5 per 3 dove la corretta HSKIP[ng, mg] marca la colonna 4 e la riga 2 come saltate, mentre le scritture trasposte mirate alle righe 3 e 4 di una maschera a tre righe venivano silenziosamente scartate e sopravviveva solo la colonna 2, desincronizzando i codificatori aritmetici
Solo una griglia non quadrata espone una maschera trasposta, e la desincronizzazione dei codificatori che ne risulta conficca la regione invece di sollevare un errore

Il decoder aritmetico non fallisce quando succede. Decodifica pixel extra da bit che appartengono a celle successive, i suoi contesti leggono vicini sbagliati, e ogni indice di pattern dopo il primo disaccordo è rumore, ecco perché il sintomo è una regione conficcata invece di qualche cella fuori posto. Su una griglia quadrata lo stesso errore è spesso invisibile: nessuna coordinata scambiata lascia la maschera, e quando le celle fuori regione sono simmetriche rispetto alla diagonale, per esempio una griglia che sporge dai bordi destro e inferiore dello stesso numero di celle, la maschera trasposta è bit per bit quella corretta. HENABLESKIP è anche opzionale, deve valere 0 quando l'immagine a scala di grigi è codificata MMR, e raramente viene impostato dagli encoder, così l'errore ha pochissimi modi di emergere. In PDFlibPas il costruttore scrive HSKIP[ng, mg] e il ciclo di posizionamento legge lo stesso ordine

Perché gli offset negativi della griglia halftone falliscono su tre livelli?

Una griglia halftone che parte a sinistra o sopra la propria regione può andare storta in tre punti distinti di un decoder, e ogni errore nasconde il successivo. T.88 consente questa geometria deliberatamente. Un encoder che allinea il proprio retino alla pagina invece che alla regione, o usa una griglia ruotata, produce naturalmente angoli di cella negativi che la regione ritaglia. Tutti e tre i livelli devono essere giusti insieme, perché azzeccarne uno solo cambia solo il sintomo

Livello 1: un campo con segno letto come senza segno

T.88 §7.4.5.1.2 definisce HGX e HGY come valori a 32 bit con segno. Leggeteli attraverso lo stesso helper a 32 bit usato per i campi senza segno, uno che forza ogni risultato negativo a 0, e una griglia destinata a partire a HGX = -900 viene spostata in silenzio sull'origine della regione; nell'esempio qui sotto l'intera immagine esce due righe più in basso. Il clamp nasconde anche gli altri due livelli: con l'origine forzata a essere non negativa, una coordinata negativa può comparire solo attraverso una griglia ruotata con HRY > 0, dove y = HGY + mg × HRX − ng × HRY scende sotto zero per le colonne griglia successive

Livello 2: shr non è >> 8

T.88 scrive >> 8 e intende uno shift aritmetico, che arrotonda verso meno infinito. La traduzione letterale è shr 8, e in Delphi e Free Pascal shr su un intero con segno è uno shift logico: il bit di segno entra come zero. Per una Integer che tiene -512, shr 8 dà 16777214 invece di -2. Un pattern che dovrebbe essere disegnato a y = -2 e ritagliato alla sua metà inferiore viene mandato 16 milioni di righe più giù e scartato come fuori regione. Niente crash; semplicemente la riga in alto dell'halftone sparisce

Livello 3: confrontare fixed point invece che pixel

Un test skip su valori fixed point non è equivalente a uno su posizioni in pixel appena la frazione è diversa da zero. Evitare lo shift logico testando xx + HPW × 256 <= 0 sul valore non shiftato sembra un equivalente del test T.88. Con HGX = -900 e un pattern di 4 pixel, dà -900 + 1024 = 124, che è positivo, quindi la cella non viene saltata. Lo standard shifta prima: floor(-900 / 256) = -4, e -4 + 4 = 0 soddisfa x + HPW <= 0, così la cella giace interamente fuori e va saltata. L'encoder la salta, il decoder la decodifica, e l'immagine a scala di grigi deriva esattamente come nel caso della maschera trasposta

Tre trappole halftone JBIG2 per una griglia a HGX negativo: un campo con segno letto attraverso un helper senza segno viene forzato a zero, lo shift right di T.88 tradotto come uno shr logico manda un pattern 16 milioni di righe più giù, e un test skip su valori fixed point tiene una cella che l'encoder ha saltato
Ogni errore nasconde il successivo, ecco perché PDFlibPas gestisce tutti e tre i livelli in un unico helper condiviso HalftoneGridPixel usato dal costruttore della maschera e dal ciclo di posizionamento

Prendi una griglia 4 × 3 di pattern 4 × 4 a HGX = -900, HGY = -512, HRX = 1024 su una regione 12 × 10. Le colonne griglia atterrano a x = -4, 0, 4 e 8, quindi la colonna 0 è interamente fuori e appartiene a HSKIP; le righe griglia atterrano a y = -2, 2 e 6, quindi la riga 0 va ritagliata alle sue ultime due righe di pixel invece che scartata. Azzeccare i livelli uno alla volta mostra la pila:

Livelli gestiti correttamenteRegione decodificata
NessunoGriglia tirata all'origine, immagine intera due righe più in basso
Solo lettura con segno di HGX / HGYPrima riga griglia mancante, il resto conficato dalla deriva del test skip
Lettura con segno, shift floor e test skip in spazio pixelIdentica, pixel per pixel, alla pagina calcolata da T.88 §6.6.5 e a due decoder di riferimento indipendenti

PDFlibPas mette tutto questo in un solo helper, HalftoneGridPixel, condiviso dal costruttore della maschera skip e dal ciclo di posizionamento. Accumula la coordinata in Int64 così un grande prodotto mg × HRX non può fare wrap, divide per 256 arrotondando verso meno infinito, e limita a ±MaxInt div 2 così una griglia corrotta non può far traboccare la successiva aritmetica bitmap. Il test skip confronta quei valori in pixel con HPW, HPH, HBW e HBH, esattamente come lo enuncia §6.6.5.1

Come si scrive uno shift right aritmetico in Delphi?

Delphi non ha un operatore di shift aritmetico, quindi uno shift right con segno corretto va scritto come divisione floor, e il semplice div non è quella divisione. div tronca verso zero. Per valori non negativi troncamento e floor concordano, e concordano anche per valori negativi multipli esatti del divisore, ecco perché -512 div 256 = -2 sembra a posto in un test veloce. Discordano ovunque altro: -900 div 256 è -3, mentre il floor è -4, e -1 div 256 è 0, mentre il floor è -1. Una coordinata JBIG2 con frazione diversa da zero è esattamente il caso in cui div dà il pixel sbagliato

Sui compilatori Delphi Win32 e Win64, una variabile Integer che tiene -512 shiftata a destra di 8 dà 16777214, e una Int64 che tiene -512 dà 72057594037927934. Free Pascal definisce pure shr come shift logico e spedisce SarLongint e SarInt64 nella propria unità System per la versione aritmetica, ma quelle funzioni non esistono in Delphi, quindi il codice condiviso tra i due compilatori ha bisogno di un helper proprio:

// Divisione floor: arrotonda verso meno infinito per qualunque segno di A e B.
// B non deve essere 0, e FloorDiv(Low(Integer), -1) fa overflow proprio come 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;

// Shift right aritmetico (la ">>" di C e T.88 su valori con segno).
// Per Value negativo, not Value = -Value - 1 è non negativo, così lo
// shr logico è sicuro lì, e il not esterno riporta il risultato indietro
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;

Il trucco not non shifta mai un numero negativo, quindi non dipende da come un compilatore tratta il bit di segno, e non fa mai overflow, incluso per Low(Integer). Entrambi gli helper hanno riscontrato un riferimento floor Int64 su diversi milioni di valori, ogni shift da 0 a 31 e i bordi Low(Integer) e High(Integer) su Delphi Win32, Delphi Win64 e Free Pascal x86_64. Un controllo di sanità da conservare in qualsiasi unit test che tocca coordinate:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  shift logico, la trappola
  Writeln(V div 256);         // -3        truncation toward zero
  Writeln(FloorDiv(V, 256));  // -4        what T.88 means by >> 8
  Writeln(SarInt32(V, 8));    // -4
end;
Linea dei numeri di PDFlibPas per la coordinata -900 shiftata a destra di 8: shr dà 16777212, div tronca a -3, mentre FloorDiv e SarInt32 atterrano entrambi sul valore floor -4 che ITU-T T.88 intende per lo shift, il che conta solo quando la frazione fixed point è diversa da zero
Troncamento e floor concordano solo sui multipli esatti, così -512 div 256 passa un test veloce e -900 div 256 prende il pixel sbagliato

Math.Floor(V / 256) restituisce pure -4, ma la sua deviazione attraverso Double perde precisione per valori Int64 sopra 253, quindi la geometria intera dovrebbe restare negli interi

Quali chiamate PDFlibPas fanno girare il decoder halftone?

Il decoder halftone JBIG2 gira quando PDFlibPas renderizza una pagina con il renderer integrato, perché il rendering ha bisogno di pixel. RenderPageToFile e RenderPageToStream entrambi lo raggiungono attraverso gli stream immagine JBIG2Decode della pagina, quindi ri-renderizzare una pagina halftone è la via diretta per verificare ciò che il decoder produce. Lo stesso decoder gestisce gli altri tipi di regione JBIG2, coperti in tabelle Huffman personalizzate JBIG2 nel decoder Pascal puro e decodificare file JBIG2 ad accesso casuale in Delphi, e la bitmap renderizzata alimenta conversioni come renderizzare pagine PDF in bianco e nero a 1 bit

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
      // Il rendering decodifica ogni regione JBIG2, halftone compresi
      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.

L'estrazione delle immagini prende normalmente una via diversa. GetPageImageList restituisce le immagini JBIG2 in forma nativa, e SaveImageListItemDataToFile o GetImageListItemDataToString ti passa un file JBIG2 standalone costruito dai byte dello stream: l'header del file, i dati JBIG2Globals e un segmento end-of-file attorno ai dati della pagina. La proprietà 400 di GetImageListItemIntProperty riporta 6 per un tale elemento. Nulla viene decodificato su quella via, quindi un .jb2 estratto che sembra corretto in un altro viewer mentre la pagina renderizzata mostra rumore punta alla via di decodifica piuttosto che allo 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;

Quando maschere o conversioni di colore forzano un fallback renderizzato, l'elemento torna come bitmap decodificata e il decoder halftone gira davvero. Di più sulle image list in estrazione di testo, immagini e font PDF in Delphi

Riferimento rapido: regole della griglia halftone JBIG2

  • Indicizza la maschera skip come HSKIP[ng, mg], colonna griglia prima, e rileggila nello stesso ordine ovunque si posizionino celle (T.88 §6.6.5.1)
  • Prova qualsiasi codice halftone o griglia con una griglia non quadrata e un insieme asimmetrico di celle fuori regione, perché una griglia quadrata può nascondere completamente un indice trasposto
  • Leggi HGX e HGY come valori a 32 bit con segno (T.88 §7.4.5.1.2), mai attraverso un helper senza segno che forzi i negativi
  • Traduci la >> 8 dello standard come divisione floor per 256, non come shr 8 e non come div 256
  • Esegui il test skip su posizioni in pixel shiftate; la forma fixed point differisce ogni volta che la frazione è diversa da zero, come mostra HGX = -900 con un pattern di 4 pixel
  • Accumula le coordinate griglia in Int64 e limitale prima di passarle al codice bitmap, così una griglia corrotta non può fare overflow

PDFlibPas renderizza, estrae e modifica documenti PDF da Delphi e C++Builder con un decoder JBIG2 Pascal nativo che gestisce maschere skip halftone, origini griglia negative e griglie ruotate come specifica T.88. Vedi la PDFlibPas Delphi PDF library per funzionalità, edizioni e un download di prova