רשתות Halftone של JBIG2 ב-PDFlibPas: HSKIP והיסטים שליליים

PDFlibPas תיקנה שני פגמים בלתי תלויים במפענח ה-JBIG2 המקורי שלה לאזורי halftone: ב-v3.539.37 מסכת ה-skip של HSKIP מאונדקסת בתור HSKIP[ng, mg] כפי ש-ITU-T T.88 §6.6.5.1 מגדיר אותה, וב-v3.539.38 רשתות שמגיעות לקואורדינטות שליליות, דרך HGX או HGY שלילי או דרך סיבוב, ממוקמות עם הזחת floor אמיתית. לפני המהדורות האלה, אזורי halftone נגועים יצאו משובשים או מוזזים, בלי שום שגיאה. שני הבאגים הסתתרו מאחורי נתוני בדיקה שבמקרה היו סימטריים או לא-שליליים, והשני מדליק תכונה של Delphi ו-Free Pascal שנושכת הרחוק מחוץ ל-JBIG2: shr על מספר שלם מסומן הוא הזחה לוגית, לא ה->> האריתמטי שהתקן מניח

אזורי halftone הם סוג אזור JBIG2 הנדיר ביותר, כך שמפענח יכול לעבד אלפי מסמכים סרוקים לפני שהוא פוגש תצלום מסוך שקודד כאחד כזה. כשזה קורה, הכישלון מרושע: הקובץ נפרסר, אורכי ה-segment מסתדרים, לעמוד יש הגודל הנכון, והאזור הוא זבל

מה אזור halftone של JBIG2 באמת מפענח?

אזור halftone של JBIG2 הוא רשת של bitmap קטנים שנבחרו מתוך מילון pattern, והעבודה האמיתית של המפענח היא לחשב אינדקס לכל תא רשת ואת מיקום הפיקסל שבו אותו תא נוחת. מילון ה-pattern מחזיק HNUMPATS patterns בגודל HPW × HPH פיקסלים. segment של אזור ה-halftone מתאר אז רשת של HGW עמודות על HGH שורות ותמונת גווני אפור באותו גודל, מקודדת בתור bitplanes עם קידוד Gray. כל bitplane מפוענח עם פרוצדורת האזור הגנרית מעל bitmap של HGW × HGH, המישור המשמעותי ביותר קודם, והמישורים יחד נותנים לכל תא את אינדקס ה-pattern שלו

מיקום תאים משתמש באריתמטיקת fixed-point עם שבר של 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

מסכת ה-skip נכנסת דרך הדגל האופציונלי HENABLESKIP. כשהדגל מוגדר, §6.6.5.1 בונה bitmap HSKIP של HGW × HGH ומגדיר HSKIP[ng, mg] ל-1 עבור כל תא שה-pattern שלו שוכן כולו מחוץ לאזור: x + HPW <= 0, x >= HBW, y + HPH <= 0 או y >= HBH. אז bitplanes הגוונים מפוענחים עם אותה מסכה בתור bitmap ה-skip של האזור הגנרי, כך שהמפענח האריתמטי לא קורא ולא מעדכן הקשר עבור תא שדולג. מפענח ומקודד חייבים להסכים על כל ביט של HSKIP, אחרת שני המקודדים האריתמטיים יוצאים מהסנכרון

למה מסכת HSKIP משוחלפת שברה רק רשתות לא ריבועיות?

מסכת ה-skip נכתבה עם הקואורדינטות שלה מוחלפות, ורק רשת לא ריבועית חשפה את זה, כי רשת ריבועית משאירה כל קואורדינטה מוחלפת בתוך המסכה. PDFlibPas מאחסנת bitmap עם accessor פיקסלים בצורת (column, row), והקוד שבנה את המסכה העביר (mg, ng), שורה קודם. מפענח ה-bitplanes של הגוונים קורא את המסכה נכון בתור (ng, mg). לולאת מיקום ה-pattern קראה אותה חזרה בסדר המוחלף של הבונה, כך שהשניים הסכימו, וסקירה של לוגיקת המיקום לבדה הייתה מעבירה אותה. מלכודת שמות החמירה את זה: בלולאת המיקום המשתנה שנקראת col עוברת על שורות הרשת ו-Row עובר על עמודות הרשת

קחו את רשת ה-5 × 3 של patterns של 4 × 4 על אזור של 16 × 8 ש-v3.539.37 משתמש בו בתור מקרה ה-regression שלו. עם HRX = 1024 ו-HRY = 0, עמודת רשת 4 נוחתת ב-x = 16 ושורת רשת 2 ב-y = 8, שניהם מחוץ לאזור. המסכה הנכונה מסמנת שבעה תאים: את כל עמודה 4 ואת כל שורה 2. הכתיבות המוחלפות ניסו להגדיר פיקסלים באינדקסי שורות 3 ו-4 במסכה גבוהה שלוש שורות בלבד, וה-setter של ה-bitmap התעלם בשקט מאותן כתיבות מחוץ לטווח. מה ששרד הייתה עמודה 2, שורות 0 עד 2. המפענח אפוא דילג על שני תאים שהמקודד קידד, ופענח שישה תאים שהמקודד דילג עליהם

המפענח האריתמטי לא נכשל כשזה קורה. הוא מפענח פיקסלים נוספים מתוך ביטים ששייכים לתאים מאוחרים יותר, ההקשרים שלו קוראים שכנים לא נכונים, וכל אינדקס pattern אחרי אי-ההסכמה הראשונה הוא רעש, ולכן הסימפטום היה אזור משובש במקום כמה תאים מוזזים. על רשת ריבועית אותו באג לעיתים קרובות בלתי נראה: אף קואורדינטה מוחלפת לא יוצאת מהמסכה, וכשהתאים מחוץ לאזור סימטריים סביב האלכסון — רשת שחורגת מהקצה הימני והתחתון באותו מספר תאים למשל — המסכה המשוחלפת היא ביט בביט הנכונה. HENABLESKIP גם אופציונלי, חייב להיות 0 כשתמונת הגוונים מקודדת MMR, ומקודדים מגדירים אותו לעיתים רחוקות, כך שלבאג היו מעט מאוד דרכים להתגלות. מאז v3.539.37 הבונה כותב HSKIP[ng, mg] ולולאת המיקום קוראת באותו סדר

למה היסטי רשת halftone שליליים נכשלים בשלוש שכבות?

רשת halftone שמתחילה משמאל לאו מעל האזור שלה שברה את PDFlibPas בשלושה מקומות נפרדים, וכל פגם הסתיר את הבא אחריו. T.88 מרשה את הגאומטריה הזאת במכוון. מקודד שמיישר את המסך שלו לעמוד ולא לאזור, או משתמש ברשת מסובבת, מייצר באופן טבעי פינות תא שליליות שהאזור חותך. v3.539.38 תיקנה את שלוש השכבות יחד, כי תיקון של כל אחת לבדה רק שינה את הסימפטום

שכבה 1: שדה מסומן שנקרא כלא-מסומן

T.88 §7.4.5.1.2 מגדיר את HGX ו-HGY כערכים מסומנים בני 32 ביט, אבל המפענח קרא אותם עם אותו helper בן 32 ביט שהשתמש בו עבור שדות לא-מסומנים, וה-helper הזה לחץ כל תוצאה שלילית אל 0. רשת שהייתה אמורה להתחיל ב-HGX = -900 הוזזה בשקט אל ראשית האזור. במקרה ה-regression של v3.539.38 כל התמונה יצאה שתי שורות נמוכה מדי. הלחיצה גם מסבירה למה שני הפגמים האחרים שרדו כל כך הרבה זמן: עם ראשית שנכפתה להיות לא-שלילית, קואורדינטה שלילית יכלה להופיע רק דרך רשת מסובבת עם HRY > 0, שבה y = HGY + mg × HRX − ng × HRY צונח מתחת לאפס עבור עמודות רשת מאוחרות

שכבה 2: shr אינו >> 8

T.88 כותב >> 8 ומתכוון להזחה אריתמטית, שמעגלת לעבר מינוס אינסוף. המפענח תרגם אותה בתור shr 8. ב-Delphi ו-Free Pascal, shr על מספר שלם מסומן הוא הזחה לוגית: ביט הסימן מוזח פנימה בתור אפס. עבור Integer שמחזיק -512, shr 8 מניב 16777214 במקום -2. pattern שהיה אמור להיצייר ב-y = -2 ולהיחתך לחציו התחתון נשלח 16 מיליון שורות מטה והושלך בתור מחוץ לאזור. שום דבר לא קרס; השורה העליונה של ה-halftone פשוט נעלמה

שכבה 3: השוואת fixed-point במקום פיקסלים

מבחן ה-skip השווה ערכי fixed-point, לא מיקומי פיקסלים, והשניים אינם שקולים ברגע שהשבר לא אפס. הקוד המקורי עקף את ההזחה הלוגית על ידי בדיקת xx + HPW × 256 <= 0 על הערך הלא-מוזח, שנחשב שקול למבחן של T.88. עם HGX = -900 ו-pattern בן 4 פיקסלים, זה נותן -900 + 1024 = 124, שהוא חיובי, ולכן התא אינו נדלג. התקן מזיז קודם: floor(-900 / 256) = -4, ו--4 + 4 = 0 עומד בתנאי x + HPW <= 0, כך שהתא שוכן כולו מחוץ וחייב לדלג. המקודד דילג עליו, המפענח פיענח אותו, ותמונת הגוונים סטתה בדיוק כמו במקרה המסכה המשוחלפת

מקרה ה-regression של v3.539.38 משתמש ברשת 4 × 3 של patterns של 4 × 4 ב-HGX = -900, HGY = -512, HRX = 1024 על אזור של 12 × 10. עמודות הרשת נוחתות ב-x = -4, 0, 4 ו-8, ולכן עמודה 0 כולה מחוץ לאזור ושייכת ל-HSKIP; שורות הרשת נוחתות ב-y = -2, 2 ו-6, ולכן שורה 0 חייבת להיחתך לשתי שורות הפיקסלים התחתונות שלה במקום להיזרק. תיקון השכבות אחת בכל פעם משחזר את המחסנית:

פגמים שתוקנו	האזור המפוענח
אף אחד (לפני v3.539.38)	הרשת נגררה לראשית, כל התמונה שתי שורות נמוכה מדי
קריאה מסומנת של HGX / HGY בלבד	שורת הרשת הראשונה חסרה, השאר משובש מהסטייה של מבחן ה-skip
קריאה מסומנת, הזחת floor ומבחן skip במרחב פיקסלים	זהה, פיקסל בפיקסל, לעמוד שחושב מ-T.88 §6.6.5 ולשני מפענחי ייחוס בלתי תלויים

התיקון הוא helper אחד, HalftoneGridPixel, משותף לבונה מסכת ה-skip וללולאת המיקום. הוא צובר את הקואורדינטה ב-Int64 כך שמכפלה גדולה של mg × HRX לא יכולה להתגלגל, מחלק ב-256 עם עיגול לעבר מינוס אינסוף, ולוחץ אל ±MaxInt div 2 כך שרשת פגומה לא יכולה לגרום לגלישה מאוחרת באריתמטיקת ה-bitmap. מבחן ה-skip משווה עכשיו את ערכי הפיקסלים האלה מול HPW, HPH, HBW ו-HBH, בדיוק כפי ש-§6.6.5.1 קובע

איך כותבים הזחה ימנית אריתמטית ב-Delphi?

ל-Delphi אין אופרטור הזחה אריתמטי, ולכן הזחה ימנית מסומנת נכונה חייבת להיכתב בתור חלוקת floor, ו-div פשוט אינה החלוקה הזאת. div חותך לעבר אפס. עבור ערכים לא-שליליים חיתוך ו-floor מסכימים, והם מסכימים גם עבור ערכים שליליים שהם כפולות מדויקים של המחלק, ולכן -512 div 256 = -2 נראה תקין בבדיקה מהירה. בכל מקום אחר הם חולקים דעה: -900 div 256 הוא -3, בזמן שה-floor הוא -4, ו--1 div 256 הוא 0, בזמן שה-floor הוא -1. קואורדינטת JBIG2 עם שבר לא אפס היא בדיוק המקרה שבו div נותן את הפיקסל הלא נכון

במהדרי Delphi Win32 ו-Win64, משתנה Integer שמחזיק -512 ומוזח ימינה ב-8 נותן 16777214, ו-Int64 שמחזיק -512 נותן 72057594037927934. Free Pascal מגדיר גם הוא את shr בתור הזחה לוגית ומספק את SarLongint ו-SarInt64 ביחידת ה-System שלו עבור הגרסה האריתמטית, אבל הפונקציות האלה לא קיימות ב-Delphi, ולכן קוד שמשותף בין שני המהדרים זקוק ל-helper משלו:

// חלוקת floor: מעגלת לעבר מינוס אינסוף לכל סימן של 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). שני ה-helpers התאימו להפניה של floor ב-Int64 על פני כמה מיליוני ערכים, כל הזחה מ-0 עד 31 וגבולות Low(Integer) ו-High(Integer) על Delphi Win32, Delphi Win64 ו-Free Pascal x86_64. בדיקת היגיון ששווה לשמור בכל unit test שנוגע בקואורדינטות:

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;

Math.Floor(V / 256) מחזיר גם -4, אבל העיקוף שלו דרך Double מאבד דיוק עבור ערכי Int64 מעל 2⁵³, ולכן גאומטריה שלמה כדאי שתישאר בשלמים

אילו קריאות PDFlibPas מריצות את מפענח ה-halftone?

מפענח ה-halftone של JBIG2 רץ כש-PDFlibPas מרנדרת עמוד עם ה-renderer המובנה, כי רינדור זקוק לפיקסלים. RenderPageToFile ו-RenderPageToStream שניהם מגיעים אליו דרך streams התמונות מסוג JBIG2Decode של העמוד, ולכן רינדור חוזר של עמוד halftone הוא הדרך הישירה לאשר ש-v3.539.38 משנה את הפלט שלכם. אותו מפענח מטפל בסוגי האזור האחרים של JBIG2, שמכוסים ב-טבלאות Huffman מותאמות אישית של JBIG2 במפענח הפסקל הטהור וב-פענוח קבצי JBIG2 של random-access ב-Delphi, וה-bitmap המרונדר מזין המרות כמו רינדור עמודי PDF ל-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
      // רינדור מפענח כל אזור JBIG2, halftones כלולים
      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 עצמאי שנבנה מבייטי ה-stream: כותרת הקובץ, נתוני ה-JBIG2Globals ו-segment סיום-קובץ מסביב לנתוני העמוד. תכונה 400 של GetImageListItemIntProperty מדווחת 6 עבור פריט כזה. שום דבר לא מפוענח בנתיב הזה, ולכן .jb2 שחולץ ונראה נכון בצופן אחר בזמן שהעמוד המרונדר מציג רעש היה סימן טיפוסי לשני באגי ה-halftone האלה:

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;

כשמסכות או המרת צבעים כופים fallback מרונדר, הפריט חוזר בתור bitmap מפוענח ומפענח ה-halftone כן רץ. עוד על רשימות תמונות ב-חילוץ טקסט, תמונות וגופנים מ-PDF ב-Delphi

עזר זריז: כללי רשת halftone של JBIG2

• מאנדקסים את מסכת ה-skip בתור HSKIP[ng, mg], עמודת רשת קודם, וקוראים אותה חזרה באותו סדר בכל מקום שבו ממקמים תאים (T.88 §6.6.5.1, תוקן ב-PDFlibPas v3.539.37)
• בודקים כל קוד halftone או רשת עם רשת לא ריבועית וקבוצה אסימטרית של תאים מחוץ לאזור, כי רשת ריבועית יכולה להסתיר אינדקס משוחלף לחלוטין
• קוראים את HGX ו-HGY בתור ערכים מסומנים בני 32 ביט (T.88 §7.4.5.1.2), לעולם לא דרך helper לא-מסומן שלוחץ שליליים
• מתרגמים את >> 8 של התקן בתור חלוקת floor ב-256, לא בתור shr 8 ולא בתור div 256
• מריצים את מבחן ה-skip על מיקומי פיקסלים מוזחים; הצורה של ה-fixed-point שונה בכל פעם שהשבר לא אפס, כפי ש-HGX = -900 עם pattern של 4 פיקסלים מראה
• צוברים קואורדינטות רשת ב-Int64 ולוחצים לפני שמוסרים אותן לקוד bitmap, כך שרשת פגומה לא יכולה לגרום לגלישה
• שדרגו ל-v3.539.38 ומעלה אם המסמכים שלכם מכילים אזורי halftone עם HENABLESKIP, ראשי רשת שליליים או רשתות מסובבות

PDFlibPas מרנדרת, מחלצת ועורכת מסמכי PDF מ-Delphi ו-C++Builder עם מפענח JBIG2 פסקלי מקורי שמטפל עכשיו במסכות skip של halftone, בראשי רשת שליליים וברשתות מסובבות כפי ש-T.88 מפרט. ראו את PDFlibPas Delphi PDF library ליכולות, מהדורות והורדת ניסיון