Technisch artikel

PDFlibPas JBIG2-halftonegrids: HSKIP en negatieve offsets

De native JBIG2-halftoneregiondecoder in PDFlibPas indexeert het HSKIP-skipmask als HSKIP[ng, mg], zoals ITU-T T.88 §6.6.5.1 het definieert, en plaatst grids die negatieve coördinaten bereiken, via een negatieve HGX of HGY of via rotatie, met een echte floor-shift. Beide details zijn makkelijk verkeerd te doen zonder dat er ook maar een foutmelding komt: de halftoneregion komt simpelweg verhaspeld of verschoven uit de bus, en beide fouten verschuilen zich achter testdata die toevallig symmetrisch of niet-negatief is. De tweede draait om een eigenschap van Delphi en Free Pascal die ver buiten JBIG2 toehapt: shr op een signed integer is een logical shift, niet de arithmetic >> die de standaard veronderstelt

Halftoneregions zijn het minst voorkomende JBIG2-regiontype, dus een decoder kan duizenden gescande documenten verwerken voordat hij een gerasterde foto tegenkomt die als zodanig is gecodeerd. Als het zover is, is de falering gemene: het bestand parst netjes, de segmentlengten kloppen op, de pagina heeft de juiste grootte, en de region is rommel

Wat decodeert een JBIG2-halftoneregion eigenlijk?

Een JBIG2-halftoneregion is een grid van kleine bitmaps uit een pattern dictionary, en het echte werk van de decoder is voor elke gridcel een index en de pixelpositie berekenen waar die cel neerkomt. De pattern dictionary bevat HNUMPATS patterns van HPW × HPH pixels. Het halftoneregionsegment beschrijft vervolgens een grid van HGW kolommen bij HGH rijen en een grijswaardenafbeelding van dezelfde grootte, gecodeerd als Gray-gecodeerde bitplanes. Elke bitplane wordt met de generic region-procedure over een HGW × HGH-bitmap gedecodeerd, meest significante plane eerst, en samen geven de planes elke cel zijn patternindex

Celplaatsing gebruikt fixed-point rekenkunde met een breuk van 8 bits. De gridorigine HGX, HGY is een paar 32-bit waarden, en de gridvector HRX, HRY beschrijft de stap tussen naburige cellen, wat een gedraaid grid toestaat. Voor gridrij mg en gridkolom ng berekent T.88 §6.6.5 de pixelpositie als:

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

Het skipmask komt binnen via de optionele vlag HENABLESKIP. Als de vlag staat, bouwt §6.6.5.1 een HGW × HGH-bitmap HSKIP en zet HSKIP[ng, mg] op 1 voor elke cel waarvan het patroon volledig buiten de region ligt: x + HPW <= 0, x >= HBW, y + HPH <= 0 of y >= HBH. De grijswaarden-bitplanes worden daarna met dat mask als skip-bitmap van de generic region gedecodeerd, dus de arithmetic decoder leest voor een overgeslagen cel geen context en werkt die niet bij. Decoder en encoder moeten op elke bit van HSKIP overeenkomen, anders lopen de twee arithmetic coders uit de pas

Waarom valt een getransponeerd HSKIP-mask alleen bij niet-vierkante grids op?

Een skipmask dat met verwisselde coördinaten is weggeschreven valt alleen op bij een niet-vierkant grid, want een vierkant grid houdt elke verwisselde coördinaat binnen het mask. Met een pixel-accessor in de vorm (column, row) schrijft een bouwer die (mg, ng) doorgeeft, rij eerst, het getransponeerde mask, terwijl de grijswaarden-bitplanedecoder het als (ng, mg) leest. Als de patroonplaatsingslus het mask terugleest in de verwisselde volgorde van de bouwer, zijn de twee het eens, en een review van alleen de plaatsingslogica laat hem passeren. Lusvariabelen die een naam dragen die niet dekt wat ze doorlopen, maken het erger: een col die over gridrijen loopt naast een Row die over gridkolommen loopt

Neem een grid van 5 × 3 met patronen van 4 × 4 op een region van 16 × 8. Met HRX = 1024 en HRY = 0 landt gridkolom 4 op x = 16 en gridrij 2 op y = 8, allebei buiten de region. Het correcte mask markeert zeven cellen: heel kolom 4 en heel rij 2. De verwisselde schrijfacties proberen pixels op rijindexen 3 en 4 te zetten in een mask van maar drie rijen hoog, en een bitmapsetter die buiten-bereik-schrijfacties stilletjes negeert, laat ze vallen. Wat overblijft is kolom 2, rijen 0 tot 2. De decoder slaat dus twee cellen over die de encoder heeft gecodeerd, en decodeert zes cellen die de encoder heeft overgeslagen

PDFlibPas JBIG2-halftone-skipmasks voor een grid van 5 bij 3 waarin het correcte HSKIP[ng, mg] kolom 4 en rij 2 als overgeslagen markeert, terwijl de getransponeerde schrijfacties op rijen 3 en 4 van een drierialig mask stilletjes werden laten vallen en alleen kolom 2 overleefde, wat de arithmetic coders uit de pas bracht
Alleen een niet-vierkant grid ontmaskert een getransponeerd mask, en de coder-desync die het oplevert verhaspelt de region in plaats van een fout te geven

De arithmetic decoder faalt niet zodra dat gebeurt. Hij decodeert extra pixels uit bits die aan latere cellen toebehoren, zijn contexts lezen verkeerde buren, en elke patternindex na de eerste mismatch is ruis, en daarom is het symptoom een verhaspelde region in plaats van een paar verkeerd geplaatste cellen. Op een vierkant grid is dezelfde fout vaak onzichtbaar: geen enkele verwisselde coördinaat verlaat het mask, en als de buiten-de-region-cellen symmetrisch rond de diagonaal liggen, bijvoorbeeld een grid dat rechts en onder met evenveel cellen uitsteekt, is het getransponeerde mask bit voor bit het correcte. HENABLESKIP is bovendien optioneel, moet 0 zijn wanneer de grijswaardenafbeelding MMR-gecodeerd is, en wordt door encoders zelden gezet, dus de fout heeft heel weinig manieren om naar boven te komen. In PDFlibPas schrijft de bouwer HSKIP[ng, mg] en leest de plaatsingslus dezelfde volgorde

Waarom falen negatieve halftone-gridoffsets in drie lagen?

Een halftonegrid dat links van of boven zijn region begint kan in een decoder op drie aparte plekken misgaan, en elke fout houdt de volgende verborgen. T.88 staat deze geometrie met opzet toe. Een encoder die zijn raster op de pagina uitlijnt in plaats van op de region, of een gedraaid grid gebruikt, produceert van nature negatieve celhoeken die de region bijsnijdt. Alle drie de lagen moeten samen kloppen, want er één alleen goed doen verandert hooguit het symptoom

Laag 1: een signed veld als unsigned gelezen

T.88 §7.4.5.1.2 definieert HGX en HGY als signed 32-bit waarden. Leest u ze via dezelfde 32-bit helper die voor unsigned velden gebruikt, één die elke negatieve uitkomst naar 0 klemt, dan wordt een grid dat op HGX = -900 had moeten beginnen stilletjes op de regionorigine neergezet; in het voorbeeld hieronder komt het hele beeld twee rijen te laag uit de bus. De clamp verhult ook de andere twee lagen: met een geforceerd niet-negatieve origine kan een negatieve coördinaat alleen via een gedraaid grid met HRY > 0 verschijnen, waar y = HGY + mg × HRX − ng × HRY bij latere gridkolommen onder nul zakt

Laag 2: shr is niet >> 8

T.88 schrijft >> 8 en bedoelt een arithmetic shift, die richting min oneindig afrondt. De letterlijke vertaling is shr 8, en in Delphi en Free Pascal is shr op een signed integer een logical shift: het tekenbit wordt als nul ingeschoven. Voor een Integer met -512 geeft shr 8 16777214 in plaats van -2. Een patroon dat op y = -2 getekend en tot zijn onderhelft bijgesneden had moeten worden, wordt zestien miljoen rijen naar beneden gestuurd en als buiten de region weggegooid. Niets crasht; de bovenste rij van de halftone verdwijnt simpelweg

Laag 3: fixed point vergelijken in plaats van pixels

Een skiptest op fixed-point waarden is niet equivalent aan één op pixelposities zodra de breuk ongelijk nul is. De logical shift omzeilen door xx + HPW × 256 <= 0 te testen op de ongeschoven waarde lijkt op een equivalent van de T.88-test. Met HGX = -900 en een patroon van 4 pixels geeft dat -900 + 1024 = 124, wat positief is, dus de cel wordt niet overgeslagen. De standaard schuift eerst: floor(-900 / 256) = -4, en -4 + 4 = 0 voldoet aan x + HPW <= 0, dus de cel ligt volledig buiten en moet worden overgeslagen. De encoder slaat hem over, de decoder decodeert hem, en de grijswaardenafbeelding drijft precies af zoals in het getransponeerde-mask-geval

Drie JBIG2-halftonevalkuilen voor een grid op negatieve HGX: een signed veld gelezen via een unsigned helper klemt op nul, de shift right uit T.88 vertaald als een logical shr stuurt een patroon zestien miljoen rijen naar beneden, en een skiptest op fixed-point waarden houdt een cel vast die de encoder overging
Elke fout houdt de volgende verborgen, en daarom behandelt PDFlibPas alle drie de lagen in één gedeelde HalftoneGridPixel-helper die de maskbouwer en de plaatsingslus gebruiken

Neem een grid van 4 × 3 met patronen van 4 × 4 op HGX = -900, HGY = -512, HRX = 1024 op een region van 12 × 10. Gridkolommen landen op x = -4, 0, 4 en 8, dus kolom 0 ligt volledig buiten en hoort in HSKIP; gridrijen landen op y = -2, 2 en 6, dus rij 0 moet tot zijn onderste twee pixelrijen worden bijgesneden in plaats van te worden weggegooid. De lagen één voor één goed doen laat de stapel zien:

Correct behandelde lagenGedecodeerde region
GeenGrid naar de origine getrokken, hele beeld twee rijen te laag
Alleen signed HGX / HGY lezenEerste gridrij ontbreekt, de rest verhaspeld door de skiptest-drift
Signed lezen, floor-shift en skiptest in pixelruimteIdentiek, pixel voor pixel, aan de pagina berekend uit T.88 §6.6.5 en aan twee onafhankelijke referentiedecoders

PDFlibPas stopt dit alles in één helper, HalftoneGridPixel, gedeeld door de skipmask-bouwer en de plaatsingslus. Hij accumuleert de coördinaat in Int64 zodat een groot product mg × HRX niet kan omslaan, deelt door 256 met afronding richting min oneindig, en klemt op ±MaxInt div 2 zodat een corrupt grid de bitmaprekenkunde later niet kan laten overlopen. De skiptest vergelijkt die pixelwaarden tegen HPW, HPH, HBW en HBH, precies zoals §6.6.5.1 het voorschrijft

Hoe schrijft u een arithmetic right shift in Delphi?

Delphi heeft geen arithmetic shift-operator, dus een correcte signed right shift moet als floordivisie worden geschreven, en gewone div is die deling niet. div kapt richting nul af. Voor niet-negatieve waarden komen afkappen en afronden naar beneden overeen, en ook voor negatieve waarden die exacte veelvouden van de deler zijn, en daarom ziet -512 div 256 = -2 er in een snelle test prima uit. Ze verschillen overal elders: -900 div 256 is -3 terwijl de floor -4 is, en -1 div 256 is 0 terwijl de floor -1 is. Een JBIG2-coördinaat met een ongelijk-nul-breuk is precies het geval waarin div de verkeerde pixel geeft

Op de Delphi-compilers Win32 en Win64 geeft een Integer-variabele met -512 acht posities naar rechts geschoven 16777214, en een Int64 met -512 geeft 72057594037927934. Free Pascal definieert shr eveneens als logical shift en levert SarLongint en SarInt64 mee in zijn System-unit voor de arithmetic-variant, maar die functies bestaan niet in Delphi, dus code die tussen de twee compilers deelt heeft een eigen helper nodig:

// Floordivisie: rondt richting min oneindig af bij elk teken van A en B.
// B mag niet 0 zijn, en FloorDiv(Low(Integer), -1) overloopt net als 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;

// Arithmetic right shift (de C- en T.88-">>" op signed waarden).
// Bij negatieve Value is not Value = -Value - 1 niet-negatief, dus de
// logical shr is daar veilig, en de buitenste not zet het resultaat terug
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;

De not-truc schuift nooit een negatief getal, dus ze hangt niet af van hoe een compiler het tekenbit behandelt, en ze loopt nooit over, ook niet voor Low(Integer). Beide helpers kwamen over enkele miljoenen waarden, elke shift van 0 tot 31 en de randen Low(Integer) en High(Integer) overeen met een Int64-floorreferentie op Delphi Win32, Delphi Win64 en Free Pascal x86_64. Een sanity check die het bewaren waard is in elke unittest die coördinaten aanraakt:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  logical shift, de valkuil
  Writeln(V div 256);         // -3        afkappen richting nul
  Writeln(FloorDiv(V, 256));  // -4        wat T.88 met >> 8 bedoelt
  Writeln(SarInt32(V, 8));    // -4
end;
PDFlibPas-getallijn voor de coördinaat -900 acht posities naar rechts geschoven: shr geeft 16777212, div kapt af op -3, terwijl FloorDiv en SarInt32 allebei op de floorwaarde -4 uitkomen die ITU-T T.88 met de shift bedoelt, wat alleen telt zodra de fixed-point-breuk ongelijk nul is
Afkappen en floor komen alleen bij exacte veelvouden overeen, dus -512 div 256 doorstaat een snelle test en -900 div 256 pakt de verkeerde pixel

Math.Floor(V / 256) geeft ook -4 terug, maar zijn omweg via Double verliest precisie voor Int64-waarden boven 253, dus integer-geometrie hoort in integers te blijven

Welke PDFlibPas-aanroepen laten de halftonedecoder draaien?

De JBIG2-halftonedecoder draait zodra PDFlibPas een pagina met de ingebouwde renderer rendert, want renderen heeft pixels nodig. RenderPageToFile en RenderPageToStream bereiken hem allebei via de JBIG2Decode-beeldstreams van de pagina, dus een halftonepagina opnieuw renderen is de directe manier om te zien wat de decoder produceert. Dezelfde decoder behandelt de andere JBIG2-regiontypes, beschreven in JBIG2 custom Huffman tables in de pure Pascal-decoder en random-access JBIG2-bestanden decoderen in Delphi, en de gerenderde bitmap voedt conversies zoals PDF-pagina’s renderen naar 1-bit monochrome

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
      // Renderen decodeert elke JBIG2-region, halftones inbegrepen
      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.

Beeldextractie volgt normaal een ander pad. GetPageImageList geeft JBIG2-afbeeldingen in native vorm terug, en SaveImageListItemDataToFile of GetImageListItemDataToString overhandigt u een standalone JBIG2-bestand opgebouwd uit de streambytes: de file header, de JBIG2Globals-data en een end-of-file-segment om de paginadata. Property 400 van GetImageListItemIntProperty meldt 6 voor zo’n item. Op dat pad wordt niets gedecodeerd, dus een geëxtraheerde .jb2 die er in een andere viewer correct uitziet terwijl de gerenderde pagina ruis toont, wijst op het decodeerpad in plaats van op de 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;

Wanneer masks of kleurconversie een gerenderde fallback afdwingen, komt het item terug als gedecodeerde bitmap en draait de halftonedecoder wel. Meer over image lists staat in Delphi PDF-tekst-, afbeeldings- en fontextractie

Snelnaslag: JBIG2-halftonegridregels

  • Indexeer het skipmask als HSKIP[ng, mg], gridkolom eerst, en lees het terug in dezelfde volgorde waar ook cellen worden geplaatst (T.88 §6.6.5.1)
  • Test elke halftone- of gridcode met een niet-vierkant grid en een asymmetrische set buiten-de-region-cellen, want een vierkant grid kan een getransponeerde index volledig verbergen
  • Lees HGX en HGY als signed 32-bit waarden (T.88 §7.4.5.1.2), nooit via een unsigned helper die negatieven klemt
  • Vertaal de >> 8 van de standaard als een floordivisie door 256, niet als shr 8 en niet als div 256
  • Draai de skiptest op geschoven pixelposities; de fixed-point-vorm wijkt af zodra de breuk ongelijk nul is, zoals HGX = -900 met een patroon van 4 pixels laat zien
  • Accumuleer gridcoördinaten in Int64 en klem ze af voordat u ze aan bitmapcode doorgeeft, zodat een corrupt grid niet kan overlopen

PDFlibPas rendert, extraheert en bewerkt PDF-documenten vanuit Delphi en C++Builder met een native Pascal JBIG2-decoder die halftone-skipmasks, negatieve gridoriginen en gedraaide grids verwerkt zoals T.88 het voorschrijft. Zie de PDFlibPas Delphi PDF-library voor functies, edities en een proefdownload