מפרט ל-WebP ללא אובדן נתונים (Bitstream)

ג'ירקי אלאקוויג'אלה (Jyrki Alakuijala, Ph.D.), Google Inc.,‎ 9.03.2023

מופשט

WebP Lossless הוא פורמט תמונה שמיועד לדחיסה ללא אובדן נתונים של תמונות ARGB. פורמט Lossless מאחסן ומשחזר בדיוק את ערכי הפיקסלים, כולל צבעים לפיקסלים שקופים לחלוטין. אלגוריתם אוניברסלי עבור רצף דחיסת נתונים (LZ77), קידוד לפי תחילית ומטמון צבעים משמשים למטרות הבאות: דחיסת נתונים בכמות גדולה. מהירויות הפענוח גבוהות יותר ממהירות הפענוח של PNG וגם דחיסה צפופה של 25% ממה שניתן להשיג באמצעות בפורמט PNG של היום.

1 מבוא

במסמך הזה מתוארת ייצוג הנתונים הדחוסים של תמונה WebP ללא אובדן נתונים. המטרה שלו היא לשמש כחומר עזר מפורט לגבי המקודד מסוג WebP Lossless וממפענח.

במסמך הזה אנחנו משתמשים באופן נרחב בתחביר של שפת תכנות C כדי לתאר את ה-bitstream, ונניח שקיימת פונקציה לקריאת ביטים, ReadBits(n) הבייטים נקראים בסדר הטבעי של עדכוני התוכן שמכילים וביטים של כל בייט נקראים בסדר יורד, הכי פחות משמעותי. מתי קוראים בו-זמנית מספר ביטים, המספר השלם מורכב הנתונים המקוריים בסדר המקורי. הביטים המשמעותיים ביותר של מספרים שלמים הם גם הביטים המשמעותיים ביותר של הנתונים המקוריים. לכן, טענה

b = ReadBits(2);

שווה ערך לשתי ההצהרות הבאות:

b = ReadBits(1);
b |= ReadBits(1) << 1;

אנחנו מניחים שכל רכיב צבע שהוא אלפא, אדום, כחול וירוק שמיוצגים באמצעות בייט של 8 ביט. אנחנו מגדירים את הסוג התואם כ-uint8. א' כל פיקסל ARGB מיוצג על ידי סוג שנקרא uint32, מספר שלם שמורכב מ-32 סיביות. בקוד שמציג את ההתנהגות של של הטרנספורמציה, הערכים האלה מקודדים בביטים הבאים: אלפא בביטים 31..24, אדום בביטים 23..16, ירוק בביטים 15..8 וכחול בביטים 7..0; עם זאת, של הפורמט יכולים להשתמש בייצוג אחר באופן פנימי.

באופן כללי, תמונה ללא אובדן נתונים של WebP מכילה נתוני כותרת, טרנספורמציה מידע של נתוני התמונה עצמם. הכותרות מכילות את הרוחב והגובה של התמונה. WebP תמונה ללא אובדן נתונים יכולה לעבור ארבעה סוגים שונים של שינויים לפני במקודדים. מידע הטרנספורמציה ב-bitstream מכיל את הנתונים שנדרשות כדי להחיל את התמרות ההופכיות המתאימות.

2 מינוחים

ARGB

ערך פיקסלים שכולל ערכי אלפא, אדום, ירוק וכחול.

תמונה של ARGB

מערך דו-ממדי שמכיל פיקסלים של ARGB.

מטמון צבעים

מערך קטן עם כתובות גיבוב (hash) שמאחסן צבעים שהיו בשימוש לאחרונה, כדי לאפשר לך לזכור אותם באמצעות קודים קצרים יותר.

תמונה להוספת צבעים

תמונה חד-ממדית של צבעים שניתן להוסיף לאינדקס באמצעות מספר שלם קטן (עד 256 ב-WebP Lossless).

תמונה של טרנספורמציית צבע

תמונה דו-ממדית של תת-רזולוציה שמכילה נתונים על מתאמים של ורכיבי צבע שונים.

מיפוי מרחק

משנה את המרחקים של LZ77 לערכים הנמוכים ביותר של פיקסלים קירבה דו-ממדית.

תמונת אנטרופיה

תמונה דו-ממדית של תת-רזולוציה, שמציינת איזה קידוד אנטרופיה בריבוע תואם בתמונה. כלומר, כל פיקסל הוא מטא .

LZ77

אלגוריתם לדחיסת חלונות הזזה, שמבוסס על מילונים, שפולט או מתאר אותם כרצפים של סמלי עבר.

מטא קידומת

מספר שלם קטן (עד 16 ביט) שמוסיף לאינדקס רכיב בטבלת המטא-תחילית.

תמונת חיזוי

תמונה דו-ממדית של תת-רזולוציה, שמציינת איזה חיזוי מרחבי שמשמש לריבוע מסוים בתמונה.

קוד קידומת

דרך קלאסית לבצע תכנות אנטרופיה שבה נעשה שימוש במספר קטן יותר של ביטים לקודים תכופים יותר.

תכנות שמבוסס על תחילית

שיטה לקידוד אנתרופי של מספרים שלמים גדולים יותר, שבה כמה ביטים של המספר השלם מקודדים באמצעות קוד אנתרופי, והביטים הנותרים מקודדים בפורמט גולמי. כך אפשר את התיאורים של קודי האנטרופיה כך שיישארו קטנים יחסית גם כאשר טווח הסמלים גדול.

סדר הסריקה

סדר עיבוד של פיקסלים (משמאל לימין ומלמעלה למטה), החל מהפיקסל בצד שמאל למעלה. לאחר שהושלמה שורה, ממשיכים של השורה הבאה בצד ימין של השורה הבאה.

3 כותרת RIFF

תחילת הכותרת כוללת את הקונטיינר RIFF. הוא מורכב 21 הבייטים הבאים:

1. המחרוזת 'RIFF'.
2. ערך קטן מאוד של 32 ביט של אורך המקטע, שהוא הגודל כולו של המקטע שנשלט על ידי הכותרת RIFF. בדרך כלל, הערך גודל המטען הייעודי (גודל הקובץ פחות 8 בייטים: 4 בייטים למאפיין 'RIFF' ו-4 בייטים לאחסון הערך עצמו).
3. המחרוזת 'WEBP' (שם מאגר התגים של RIFF).
4. המחרוזת 'VP8L' (FourCC לנתוני תמונה בקידוד ללא אובדן).
5. ערך קטן מאוד של 32 ביט של מספר הבייטים בסטרימינג ללא אובדן מידע.
6. חתימה בגודל 0x2f של 1 בייט.

28 הביטים הראשונים של ה-bitstream מציינים את הרוחב והגובה של התמונה. הרוחב והגובה מפענחים כמספרים שלמים של 14 ביט באופן הבא:

int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;

הדיוק של 14 סיביות ביחס לרוחב ולגובה של התמונה מגביל את הגודל המרבי של תמונה ללא אובדן נתונים של WebP עד 1,6384 גישה ל-16,384 פיקסלים.

הביט alpha_is_used הוא רמז בלבד ולא אמור להשפיע על הפענוח. צריך להגדיר אותו לערך 0 כשכל ערכי האלפא בתמונה הם 255, ולערך 1 במקרים אחרים.

int alpha_is_used = ReadBits(1);

השדה version_number הוא קוד בן 3 ביט שצריך להגדיר ל-0. כל ערך אחר יטופלו כשגיאה.

int version_number = ReadBits(3);

4 טרנספורמציות

הטרנספורמציות הן מניפולציות הפיכות של נתוני התמונה, שיכולות לצמצם את האנטרופיה הסימבולית שנותרה על ידי בניית מודל של התאמות מרחביות וצבעוניות. הם יכולה להפוך את הדחיסה הסופית לצפיפות יותר.

תמונה יכולה לעבור ארבעה סוגים של שינויים. ביט אחד מציין את הנוכחות של טרנספורמציה. בכל טרנספורמציה מותר להשתמש פעם אחת בלבד. נעשה שימוש בטרנספורמציות רק לתמונה ב-ARGB ברמה הראשית. את התמונות המשניות (תמונה לטרנספורמציה של צבע, תמונת אנטרופיה ותמונת חיזוי) לא משתנים, אפילו לא ה-0 הביטים שמציינת את סוף השינויים.

בדרך כלל, מקודד ישתמש בטרנספורמציות האלה כדי לצמצם את האנטרופיה של Shannon בתמונה הנותרת. בנוסף, ניתן לקבוע את נתוני הטרנספורמציה על סמך האנטרופיה צמצום החיפוש.

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 5).

אם קיימת טרנספורמציה, שני הביטים הבאים מציינים את סוג הטרנספורמציה. יש ארבעה סוגי טרנספורמציות.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

אחרי סוג הטרנספורמציה מופיעים הנתונים של הטרנספורמציה. נתוני הטרנספורמציה מכילים ותלוי במידע שנדרש כדי להחיל את הטרנספורמציה ההפוכה סוג של טרנספורמציה. התמרות ההופכיות מיושמות בסדר הפוך, קוראים אותם מה-bitstream, כלומר, מהשלב האחרון.

בשלב הבא נתאר את נתוני הטרנספורמציה לפי סוגים שונים.

4.1 טרנספורמציה של חזוי

אפשר להשתמש בטרנספורמציה של החיזוי כדי להפחית את האנטרופיה על ידי ניצול העובדה שלרוב יש התאמה בין פיקסלים קרובים. בטרנספורמציה של החיזוי, ערך הפיקסל הנוכחי צפוי על סמך הפיקסלים שכבר מפוענחו (בשורת הסריקה ) ורק הערך השיור (בפועל - צפוי) מקודד. הירוק רכיב של פיקסל מגדיר אילו מ-14 החיזויים ישמשו של קבוצת ה-ARGB. מצב החיזוי קובע את הסוג של הצפוי לשימוש. אנחנו מחלקים את התמונה לריבועים, ואת כל הפיקסלים בריבוע משתמשים באותו מצב חיזוי.

3 הביטים הראשונים של נתוני החיזוי מגדירים את הרוחב והגובה של הבלוק במספר של ביטים.

int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) (((num) + (den) - 1) / (den))
int transform_width = DIV_ROUND_UP(image_width, 1 << size_bits);

נתוני הטרנספורמציה מכילים את מצב החיזוי של כל בלוק של התמונה. הוא היא תמונה בתת-רזולוציה שבה הרכיב הירוק של פיקסל מגדיר 14 החיזויים משמשים לכל block_width * block_height הפיקסלים בתוך בלוק מסוים של תמונת ה-ARGB. התמונה המשנית מקודדת באמצעות אותן שיטות שמתוארות בפרק 5.

מספר העמודות של הבלוק, transform_width, משמש להוספת אינדקס דו-מימדי. עבור פיקסל (x, y), אפשר לחשב את הכתובת המתאימה של בלוק המסנן באופן הבא:

int block_index = (y >> size_bits) * transform_width +
                  (x >> size_bits);

יש 14 מצבי חיזוי שונים. בכל מצב חיזוי, הערך הנוכחי של הפיקסל משוער לפי פיקסל אחד או יותר שנמצאים בסמוך לו וערכיהם כבר ידועים.

בחרנו את הפיקסלים השכנים (TL,‏ T,‏ TR ו-L) של הפיקסל הנוכחי (P) באופן הבא:

O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    TL   T    TR   O    O    O    O
O    O    O    O    L    P    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X

כאשר TL פירושו צד שמאל למעלה, T פירושו למעלה, TR פירושו צד ימין למעלה ו-L פירושו שמאל. בשעה זמן חיזוי הערך ל-P, כל הפיקסלים O, TL, T, TR ו-L עבר עיבוד, והפיקסל P וכל ה-X פיקסלים לא ידועים.

בהינתן הפיקסלים השכנים הקודמים, מצבי החיזוי השונים מוגדר באופן הבא.

מצב	הערך החזוי של כל ערוץ של הפיקסל הנוכחי
0	0xff000000 (מייצג צבע שחור מוצק ב-ARGB)
1	L
2	T
3	TR
4	TL
5	Average2(Average2(L, TR), T)
6	Average2(L, TL)
7	ממוצע2(L, T)
8	ממוצע2(TL, T)
9	ממוצע2(T, TR)
10	ממוצע2(Average2(L, TL), Average2(T, TR))
11	בחירה(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

Average2 מוגדר כך לכל רכיב ARGB:

uint8 Average2(uint8 a, uint8 b) {
  return (a + b) / 2;
}

החיזוי שבחרתם מוגדר כך:

uint32 Select(uint32 L, uint32 T, uint32 TL) {
  // L = left pixel, T = top pixel, TL = top-left pixel.

  // ARGB component estimates for prediction.
  int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
  int pRed = RED(L) + RED(T) - RED(TL);
  int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
  int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);

  // Manhattan distances to estimates for left and top pixels.
  int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
           abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
  int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
           abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));

  // Return either left or top, the one closer to the prediction.
  if (pL < pT) {
    return L;
  } else {
    return T;
  }
}

הפונקציות ClampAddSubtractFull ו-ClampAddSubtractHalf מתבצעות לכל רכיב ARGB באופן הבא:

// Clamp the input value between 0 and 255.
int Clamp(int a) {
  return (a < 0) ? 0 : (a > 255) ? 255 : a;
}

int ClampAddSubtractFull(int a, int b, int c) {
  return Clamp(a + b - c);
}

int ClampAddSubtractHalf(int a, int b) {
  return Clamp(a + (a - b) / 2);
}

יש כללי טיפול מיוחדים עבור חלק מהפיקסלים של הגבול. אם קיימת ב-prediction, ללא קשר למצב [0..13] עבור הפיקסלים האלה, הערך הצפוי של הפיקסל השמאלי העליון של התמונה הוא 0xff000000, הכול הפיקסלים בשורה העליונה הם פיקסל-L וכל הפיקסלים בעמודה השמאלית ביותר טי-פיקסל.

ההתייחסות לפיקסלים מסוג TR בעמודה השמאלית ביותר היא יוצא מן הכלל. החיזוי של הפיקסלים בעמודה השמאלית ביותר מתבצע באמצעות המצבים [0..13], בדיוק כמו פיקסלים שלא על הגבול, אלא הפיקסל השמאלי ביותר בשוליים אותה שורה כמו הפיקסל הנוכחי משמש במקום זאת כפיקסל ה-TR.

כדי לקבל את ערך הפיקסל הסופי, מוסיפים כל ערוץ של הערך המשוער לערך השיורי המקודד.

void PredictorTransformOutput(uint32 residual, uint32 pred,
                              uint8* alpha, uint8* red,
                              uint8* green, uint8* blue) {
  *alpha = ALPHA(residual) + ALPHA(pred);
  *red = RED(residual) + RED(pred);
  *green = GREEN(residual) + GREEN(pred);
  *blue = BLUE(residual) + BLUE(pred);
}

4.2 שינוי צבע

מטרת הטרנספורמציה של הצבע היא לעטר את הערכים R, G ו-B בכל אחד פיקסל. טרנספורמציית הצבע שומרת על הערך הירוק (G) כפי שהוא, ומשנה את הערך האדום (R) מבוסס על הערך הירוק, ומשנה את הערך הכחול (B) בערך הירוק ואז בערך האדום.

כמו במקרה של התמרת חיזוי, קודם התמונה מחולקת ואותו מצב טרנספורמציה משמש לכל הפיקסלים בבלוק. עבור בכל בלוק יש שלושה סוגים של אלמנטים לטרנספורמציה של צבע.

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

טרנספורמציה של הצבע בפועל מתבצעת על ידי הגדרת דלתא של טרנספורמציה של צבע. דלתא של טרנספורמציה של צבע תלויה ב-ColorTransformElement, שזהה לכל הפיקסלים בבלוק מסוים. הדלתא מחסרת במהלך צבע טרנספורמציה. במקרה כזה, הצבע ההופכי מתחלף.

פונקציית טרנספורמציה של צבע מוגדרת כך:

void ColorTransform(uint8 red, uint8 blue, uint8 green,
                    ColorTransformElement *trans,
                    uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the transform is just subtracting the transform deltas
  tmp_red  -= ColorTransformDelta(trans->green_to_red,  green);
  tmp_blue -= ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue -= ColorTransformDelta(trans->red_to_blue, red);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

הפונקציה ColorTransformDelta מחושבת באמצעות מספר שלם חתום של 8 ביט שמייצג מספר נקודות קבוע ב-3.5 וערוץ RGB חתום של 8 ביט (c) [-128..127] ומוגדרת כך:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

המרה מייצוג לא חתום של 8 ביט (uint8) לייצוג 8 ביט נדרש אחד (int8) לפני קריאה ל-ColorTransformDelta(). הערך החתום שצריך לפרש כמספר משלים של 8 ביט (כלומר: טווח uint8) הפרמטר [128..255] ממופה לטווח [ -128..-1] של ערך int8 לאחר המרה).

את הכפלה צריך לבצע בצורה מדויקת יותר (בקידוד של 16 ביט לפחות דיוק). המאפיין של הרחבת הסימן של פעולת ההזזה לא רלוונטי כאן. רק 8 הביטים הנמוכים ביותר משמשים מהתוצאה, ובביטים האלה, ההזזה עם הרחבת הסימן וההזזה ללא סימן עקביות זו עם זו.

עכשיו נתאר את התוכן של נתוני טרנספורמציית הצבע, כדי שהפענוח יוכל להחיל את טרנספורמציית הצבע ההפוכה ולשחזר את ערכי האדום והכחול המקוריים. שלוש הביטים הראשונים של נתוני טרנספורמציה של צבע מכילים את הרוחב והגובה של גוש תמונות במספר ביטים, בדיוק כמו שהחיזוי טרנספורמציה:

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

החלק הנותר של הנתונים של טרנספורמציה של צבע מכיל ColorTransformElement המתאימים לכל בלוק של התמונה. כל אחד ColorTransformElement 'cte' מטופל כפיקסל בתמונה ברזולוציה משנה שרכיב האלפא שלו הוא 255, הרכיב האדום הוא cte.red_to_blue, ירוק הרכיב הוא cte.green_to_blue והרכיב הכחול הוא cte.green_to_red.

במהלך הפענוח, מתבצע פענוח של ColorTransformElement מופעים של הבלוק, והטרנספורמציה ההפוכה של הצבע חלה על ערכי ה-ARGB של הפיקסלים. בתור שהזכרנו קודם, טרנספורמציה הפוכה של צבע ColorTransformElement ערכים לערוצים האדומים והכחולים. אלפא וירוק הערוצים לא ישתנו.

void InverseTransform(uint8 red, uint8 green, uint8 blue,
                      ColorTransformElement *trans,
                      uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the inverse transform is just adding the
  // color transform deltas
  tmp_red  += ColorTransformDelta(trans->green_to_red, green);
  tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue +=
      ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

4.3 החסרה של טרנספורמציה ירוקה

החיסור של התמרת ירוקה מחסיר ערכים ירוקים מהערכים האדומים והכחולים של לכל פיקסל. כשהטרנספורמציה הזו קיימת, המפענח צריך להוסיף את הצבע הירוק גם לערך האדום וגם לערך הכחול. אין נתונים שמשויכים לפריט הזה ונבצע טרנספורמציה. המפענח מחיל את הטרנספורמציה ההפוכה באופן הבא:

void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
  *red  = (*red  + green) & 0xff;
  *blue = (*blue + green) & 0xff;
}

הטרנספורמציה הזו מיותרת, כי ניתן ליצור אותה באמצעות מודל הטרנספורמציה של הצבע, מכיוון שאין כאן נתונים נוספים, ניתן לחלק את הטרנספורמציה הירוקה בחיסור נעשה שימוש בפחות ביטים מטרנספורמציה של צבע מלא.

4.4 טרנספורמציה של הוספת צבעים

אם אין הרבה ערכי פיקסלים ייחודיים, יכול להיות שעדיף ליצור ומחליפים את ערכי הפיקסלים באינדקסים של המערך. הצבע אנחנו משיגים את המטרה הזו. (בהקשר של WebP ללא אובדן מידע, אנחנו לא לקרוא לזה טרנספורמציה של לוח צבעים, כי מודל קיים קונספט דינמי בקידוד ללא אובדן נתונים של WebP: מטמון צבעים.)

התכונה 'הוספת צבעים לאינדקס' משנה את המספר של ערכי ה-ARGB הייחודיים תמונה. אם המספר נמוך מהסף (256), הוא יוצר מערך של ערכי ARGB, שמשמשים להחלפת ערכי הפיקסלים האינדקס התואם: הערוץ הירוק של הפיקסלים מוחלף וכל ערכי האלפא מוגדרים ל-255, וכל הערכים האדומים והכחולים מוגדרים ל-0.

נתוני הטרנספורמציה מכילים את הגודל של טבלת הצבעים ואת הרשומות בטבלת הצבעים. המפענח קורא את נתוני הטרנספורמציה של הוספת צבעים באופן הבא:

// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;

טבלת הצבעים נשמרת באמצעות פורמט האחסון של התמונות עצמו. טבלת הצבעים על ידי קריאת תמונה, ללא הכותרת RIFF, גודל התמונה משתנה, בהנחה שהגובה של פיקסל אחד והרוחב של color_table_size. טבלת הצבעים תמיד מקודדת באמצעות חיסור כדי לצמצם את אנטרופיה של התמונות. השינויים צבעי לוח הצבעים מכילים בדרך כלל פחות אנטרופיה מאשר הצבעים והן מניבות חיסכון משמעותי בתמונות קטנות יותר. בתהליך הפענוח, אפשר לקבל כל צבע סופי בטבלת הצבעים על ידי הוספת ערכי הרכיבים הקודמים של הצבע לכל רכיב ARGB בנפרד ושמירת 8 הביטים הפחות משמעותיים של התוצאה.

הטרנספורמציה ההפוכה של התמונה פשוט מחליפה את ערכי הפיקסלים נמצאים באינדקס של טבלת הצבעים) עם הערכים בפועל של טבלת הצבעים. האינדקס על סמך הרכיב הירוק של צבע ה-ARGB.

// Inverse transform
argb = color_table[GREEN(argb)];

אם האינדקס שווה ל-color_table_size או גדול ממנו, ערך הצבע של aRGB צריך להיות מוגדר כ-0x00000000 (שחור שקוף).

כשטבלת הצבעים קטנה (16 צבעים או פחות), כמה פיקסלים מקובצים בפיקסל אחד. חבילות הפיקסלים של כמה (2, 4 או 8) פיקסלים לפיקסל יחיד, תוך הקטנת רוחב התמונה בהתאמה. פיקסל קיבוץ הנתונים מאפשר קידוד יעיל יותר של אנטרופיה של התפלגות משותפת של פיקסלים קרובים, והיא מעניקה כמה יתרונות אריתמטיים כמו קידוד של קוד אנטרופיה, אבל ניתן להשתמש בו רק כאשר יש 16 ערכים ייחודיים או פחות.

color_table_size מציין כמה פיקסלים משולבים:

int width_bits;
if (color_table_size <= 2) {
  width_bits = 3;
} else if (color_table_size <= 4) {
  width_bits = 2;
} else if (color_table_size <= 16) {
  width_bits = 1;
} else {
  width_bits = 0;
}

width_bits מכיל ערך 0, 1, 2 או 3. הערך 0 מציין שאין פיקסל יש ליצור קיבוץ עבור התמונה. הערך 1 מציין ששני פיקסלים משולב, ולכל פיקסל יש טווח של [0..15]. הערך 2 מציין שילוב של ארבעה פיקסלים, ולכל פיקסל יש טווח של [0..3]. הערך 3 מציין ששמונה פיקסלים משולבים ולכל פיקסל יש טווח של [0..1], כלומר, ערך בינארי.

הערכים נדחים ברכיב הירוק באופן הבא:

• width_bits = 1: לכל ערך x, כאשר x ≡ 0 (mod 2), הערך הירוק ב-x ממוקם ב-4 הביטים המשמעותיים הכי פחות של הערך הירוק ב-x / 2, והערך הירוק ב-x + 1 ממוקם ב-4 הביטים המשמעותיים הכי הרבה של הערך הירוק ב-x / 2.
• width_bits = 2: לכל ערך של x, שבו x ÷ 0 (mod 4), ירוק ב-x ממוקם בשני הביטים הכי פחות משמעותיים ערך ירוק ב-x / 4, וערכים ירוקים ב-x + 1 עד x + 3 ממוקמים בתוך לפייות המשמעותיות יותר של הערך הירוק במספר x / 4.
• width_bits = 3: לכל ערך של x, שבו x ÷ 0 (מודל 8), ירוק בערך x ממוקם בחלק הקטן ביותר של השטח הירוק וערך ב-x / 8, וערכים ירוקים ב-x + 1 עד x + 7 ממוקמים לפי הסדר לקצוות המשמעותיים יותר של הערך הירוק ב-x / 8.

אחרי קריאת הטרנספורמציה הזו, image_width מקבל תת-דגימה של width_bits. הזה משפיעה על גודל התמרות הבאות. אפשר לחשב את הגודל החדש באמצעות DIV_ROUND_UP, כפי שהוגדר מוקדם יותר.

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

5 נתוני תמונות

נתוני התמונה הם מערך של ערכי פיקסלים בסדר הסריקה.

5.1 התפקידים של נתוני התמונה

אנחנו משתמשים בנתוני תמונות בחמישה תפקידים שונים:

1. תמונה בפורמט ARGB: אחסון הפיקסלים של התמונה בפועל.
2. תמונת אנטרופיה: שומרת את קודי הקידומת של המטא-נתונים (ראו "פענוח קוד של קודי קידומת של מטא-קידומת").
3. תמונת חיזוי: שמירת המטא-נתונים עבור התמרת חיזוי (מידע נוסף זמין בקטע "Predictor Transform").
4. תמונת טרנספורמציה של צבע: נוצרה על ידי ערכים של ColorTransformElement (מוגדר ב"טרנספורמציה של צבע") לבלוקים שונים של התמונה.
5. תמונה להוספת צבעים: מערך בגודל color_table_size (עד 256) ערכי ARGB) שמאחסנים את המטא-נתונים עבור הטרנספורמציה של הוספת צבעים (ראו "טרנספורמציה של הוספת צבעים לאינדקס").

5.2 קידוד של נתוני תמונה

הקידוד של נתוני התמונה לא תלוי בתפקיד שלהם.

תחילה התמונה מחולקת לקבוצה של בלוקים בגודל קבוע (בדרך כלל 16x16) ). כל אחד מהבלוקים האלה מתוכנן באמצעות קודי אנטרופי משלו. כמו כן, כמה בלוקים עשויים להשתמש באותם קודי אנטרופיה.

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

כל פיקסל מקודד באחת משלוש השיטות האפשריות:

1. ליטרלים עם קידומת: כל ערוץ (ירוק, אדום, כחול ואלפא) מקודד בנפרד באמצעות אנטרופי.
2. הפניה לאחור של LZ77: רצף של פיקסלים מועתקים ממקומות אחרים ב- את התמונה.
3. קוד מטמון צבעים: שימוש בקוד גיבוב מכפיל קצר (מטמון צבעים) של צבע שנראה לאחרונה.

בקטעי המשנה הבאים מתואר בפירוט כל אחד מהם.

5.2.1 ליטרלים בקידוד קידומת

הפיקסל מאוחסן כערכים עם תחילית של ירוק, אדום, כחול ואלפא (בסדר הזה). פרטים נוספים זמינים בסעיף 6.2.3 פרטים.

5.2.2 הפניה לאחור של LZ77

הפניות לאחור הן צמדים של length וקוד מרחק:

• 'אורך' מציין כמה פיקסלים יש להעתיק לפי סדר שורת הסריקה.
• קוד המרחק הוא מספר שמציין את המיקום של פיקסל שצולם בעבר, שממנו צריך להעתיק את הפיקסלים. המיפוי המדויק שמתוארים בהמשך.

ערכי האורך והמרחק מאוחסנים באמצעות קידומת LZ77.

קידוד קידומות של LZ77 מחלק ערכים שלמים גדולים לשני חלקים: קוד הקידומת וביטים נוספים. קוד הקידומת מאוחסן באמצעות קוד אנטרופיה, והביטים הנוספים מאוחסנים כמו שהם (ללא קוד אנטרופיה).

הסיבה: גישה זו מצמצמת את דרישת האחסון לאנטרופיה בנוסף, ערכים גדולים הם בדרך כלל נדירים, לכן יש להשתמש בביטים נוספים כמה ערכים בתמונה. לכן, הגישה הזו מובילה לדחיסה טובה יותר באופן כללי.

הטבלה הבאה מציינת את קודי התחילית והביטים הנוספים שמשמשים לאחסון טווחי ערכים שונים.

טווח ערכים	קוד קידומת	ביטים נוספים
1	0	0
2	1	0
3	2	0
4	3	0
5..6	4	1
7..8	5	1
9..12	6	2
13..16	7	2
...	...	...
3072..4096	23	10
...	...	...
524289..786432	38	18
786433..1048576	39	18

הקוד המדומה לקבלת ערך (אורך או מרחק) מקוד התחילית הוא ככה:

if (prefix_code < 4) {
  return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;

מיפוי מרחק

כפי שצוין קודם לכן, קוד מרחק הוא מספר שמציין את המיקום של פיקסלים שראינו בעבר, שממנו יש להעתיק את הפיקסלים. קטע המשנה הזה מגדיר את המיפוי בין קוד המרחק לבין המיקום של תג פיקסל.

קודי מרחק שגדולים מ-120 מציינים את מרחק הפיקסלים לפי סדר קווי הסריקה. לקזז ב-120.

קודי המרחק הקטנים ביותר [1..120] הם מיוחדים והם שמורים לסימון סגירה. של הפיקסל הנוכחי. השכונה הזו מורכבת מ-120 פיקסלים:

• פיקסלים שנמצאים במרחק של 1 עד 7 שורות מעל הפיקסל הנוכחי, באורך של עד 8 עמודות משמאל או עד 7 עמודות מימין לפיקסל הנוכחי. [סה"כ פיקסלים כאלה = 7 * (8 + 1 + 7) = 112].
• מספר הפיקסלים שנמצאים בשורה של הפיקסל הנוכחי והגודל שלהם הוא עד 8 עמודות מימין לפיקסל הנוכחי. [8 פיקסלים כאלה].

המיפוי בין קוד המרחק distance_code לבין הפיקסל שמסביב הקיזוז (xi, yi) הוא כך:

(0, 1),  (1, 0),  (1, 1),  (-1, 1), (0, 2),  (2, 0),  (1, 2),
(-1, 2), (2, 1),  (-2, 1), (2, 2),  (-2, 2), (0, 3),  (3, 0),
(1, 3),  (-1, 3), (3, 1),  (-3, 1), (2, 3),  (-2, 3), (3, 2),
(-3, 2), (0, 4),  (4, 0),  (1, 4),  (-1, 4), (4, 1),  (-4, 1),
(3, 3),  (-3, 3), (2, 4),  (-2, 4), (4, 2),  (-4, 2), (0, 5),
(3, 4),  (-3, 4), (4, 3),  (-4, 3), (5, 0),  (1, 5),  (-1, 5),
(5, 1),  (-5, 1), (2, 5),  (-2, 5), (5, 2),  (-5, 2), (4, 4),
(-4, 4), (3, 5),  (-3, 5), (5, 3),  (-5, 3), (0, 6),  (6, 0),
(1, 6),  (-1, 6), (6, 1),  (-6, 1), (2, 6),  (-2, 6), (6, 2),
(-6, 2), (4, 5),  (-4, 5), (5, 4),  (-5, 4), (3, 6),  (-3, 6),
(6, 3),  (-6, 3), (0, 7),  (7, 0),  (1, 7),  (-1, 7), (5, 5),
(-5, 5), (7, 1),  (-7, 1), (4, 6),  (-4, 6), (6, 4),  (-6, 4),
(2, 7),  (-2, 7), (7, 2),  (-7, 2), (3, 7),  (-3, 7), (7, 3),
(-7, 3), (5, 6),  (-5, 6), (6, 5),  (-6, 5), (8, 0),  (4, 7),
(-4, 7), (7, 4),  (-7, 4), (8, 1),  (8, 2),  (6, 6),  (-6, 6),
(8, 3),  (5, 7),  (-5, 7), (7, 5),  (-7, 5), (8, 4),  (6, 7),
(-6, 7), (7, 6),  (-7, 6), (8, 5),  (7, 7),  (-7, 7), (8, 6),
(8, 7)

לדוגמה, קוד המרחק 1 מציין היסט של (0, 1) עבור בפיקסל הקרוב, כלומר הפיקסל שמעל לפיקסל הנוכחי (0 פיקסלים) הבדל בכיוון ה-X והבדל של פיקסל אחד בכיוון ה-Y). באופן דומה, קוד המרחק 3 מציין את הפיקסל בפינה השמאלית העליונה.

המפענח יכול להמיר קוד מרחק distance_code לסדר שורה המרחק dist באופן הבא:

(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
  dist = 1
}

כאשר distance_map הוא המיפוי שצוין למעלה, ו-image_width הוא הרוחב של התמונה בפיקסלים.

5.2.3 קידוד של מטמון צבעים

במטמון הצבעים מאוחסנת קבוצה של צבעים שנעשה בהם שימוש לאחרונה בתמונה.

נימוק: כך, אפשר להתייחס לפעמים לצבעים שבהם נעשה שימוש לאחרונה. ביעילות רבה יותר מאשר פליטת הנתונים באמצעות שתי השיטות האחרות (המתוארות 5.2.1 ו-5.2.2).

קודי מטמון הצבעים מאוחסנים באופן הבא. קודם כל, יש ערך של 1 ביט מציין אם נעשה שימוש במטמון הצבעים. אם הבייט הזה הוא 0, אין קודי מטמון של צבעים והם לא מועברים בקוד הקידומת שמפענח את הסמלים הירוקים ואת קודי הקידומת של האורך. עם זאת, אם הבייט הזה הוא 1, המערכת קוראת את גודל המטמון של הצבעים:

int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;

color_cache_code_bits מגדיר את הגודל של מטמון הצבעים (1 << color_cache_code_bits). טווח הערכים המותרים של color_cache_code_bits היא [1..11]. מפענחים שפועלים בהתאם למדיניות חייבים לציין Bitstream פגום עבור ערכים אחרים.

מטמון צבעים הוא מערך בגודל color_cache_size. כל כניסה מאחסנת ARGB אחד צבע. כדי לחפש צבעים, צריך להוסיף אותם לאינדקס עד (0x1e35a7bd * color) >> (32 - color_cache_code_bits). רק חיפוש אחד יתבצע במטמון צבעים. אין יישוב מחלוקות.

בתחילת פענוח או קידוד של תמונה, כל הרשומות בכל הערכים של מטמון הצבעים מוגדרות לאפס. קוד מטמון הצבעים מומר לצבע הזה ב בזמן הפענוח. המצב של מטמון הצבעים נשמר על ידי הוספה של כל פיקסל, בין אם הוא נוצר על ידי הפניה לאחור או כמילת ליטרל, למטמון לפי הסדר שבו הוא מופיע בסטרימינג.

קוד אנטרופיה 6

6.1 סקירה כללית

רוב הנתונים מקודדים באמצעות קוד קידומת קנוני. לכן, הקודים נשלחים על ידי שליחת אורך הקוד בקידומת, כפי בניגוד לקודי התחילית בפועל.

באופן ספציפי, הפורמט משתמש בקידוד תחילית של וריאנטים מרחבי. בעוד אבל בלוקים שונים של התמונה עלולים להשתמש באנטרופיה שונה קודים.

הסיבה: יכול להיות שלאזורים שונים בתמונה יהיו מאפיינים שונים. לכן, היכולת להשתמש בקודי אנטרופיה שונים מספקת גמישות רבה יותר או לשפר את הדחיסה.

6.2 פרטים

נתוני התמונה המקודדת מורכבים מכמה חלקים:

1. פענוח ופיתוח של קודי הקידומת.
2. קודי קידומת של מטא.
3. נתוני תמונה בקידוד אנטרופיה.

לכל פיקסל נתון (x, y), קיימת קבוצה של חמישה קודי קידומת המשויכים אל את זה. הקודים האלה הם (בסדר Bitstream):

• קוד קידומת מס' 1: משמש לערוץ ירוק, לאורך הפניה לאחור, וגם מטמון צבעים.
• קוד קידומת 2, #3 ו-4: משמש לערוצים אדומים, כחולים ואלפא. בהתאמה.
• קוד קידומת מס' 5: משמש לצורך הפניה לאחור למרחק.

מכאן ואילך, אנחנו מתייחסים לקבוצה הזו בתור קבוצת קוד קידומת.

6.2.1 פענוח ופיתוח של קודי הקידומת

בקטע הזה מוסבר איך לקרוא את אורכי התחילית של ה-bitstream.

אפשר לקודד את אורך קוד הקידומת בשתי דרכים. השיטה שבה נעשה שימוש מצוינת בערך של 1 ביט.

• אם הביט הזה הוא 1, מדובר בקוד פשוט של אורך קוד.
• אם הבייט הזה הוא 0, זהו קוד באורך קוד רגיל.

בשני המקרים, יכול להיות שיהיו קטעי קוד שלא בשימוש שעדיין הם חלק מהזרם. ייתכן שזה לא יעיל, אבל זה מותר לפי הפורמט. העץ המתואר חייב להיות עץ בינארי מלא. צומת עלה יחיד הוא נחשב לעץ בינארי שלם ואפשר לקודד אותו באמצעות הפונקציה או קוד באורך רגיל של קוד. כשמקודדים צומת עלה יחיד באמצעות קוד אורך קוד רגיל, כל אורכי הקודים מלבד אחד הם אפסים, וערך הצומת היחיד מסומן באורך 1 – גם אם לא נצרכים ביטים בזמן השימוש בעץ הצומת היחיד.

קוד פשוט של אורך קוד

הווריאנט הזה משמש במקרה מיוחד שבו נמצאים רק סמל קידומת 1 או 2 הטווח [0..255] עם אורך הקוד 1. כל שאר האורך של קודי התחילית הם אפסים מפורשים.

הבייט הראשון מציין את מספר הסמלים:

int num_symbols = ReadBits(1) + 1;

ערכי הסמלים הבאים הם.

הסמל הראשון מקודד באמצעות 1 או 8 סיביות, בהתאם לערך של is_first_8bits הטווח הוא [0..1] או [0..255], בהתאמה. השנייה ההנחה היא שסמל הקוד, אם קיים, הוא תמיד בטווח [0..255] באמצעות 8 ביטים.

int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
  symbol1 = ReadBits(8);
  code_lengths[symbol1] = 1;
}

שני הסמלים צריכים להיות שונים. מותר להשתמש בסמלים כפולים, אבל בלתי יעיל.

הערה: עוד מקרה מיוחד הוא כשכל האורך של קודי התחילית הוא אפס (אפס קידומת ריקה). לדוגמה, קוד קידומת של מרחק יכול להיות ריק אם אין הפניות לאחור. באופן דומה, קודי קידומת של אלפא, אדום ו- כחול יכול להיות ריק אם נוצרים כל הפיקסלים באותו מטא קוד קידומת באמצעות מטמון הצבעים. עם זאת, אין צורך לטפל במקרה הזה באופן מיוחד, כי אפשר לקודד קודי קידומת ריקים כאלה שמכילים סמל יחיד 0.

קוד של אורך קוד רגיל

אורכי הקוד של קוד התחילית הם 8 ביטים, והם נקראים כך. קודם כל, num_code_lengths מציין את מספר אורכי הקוד.

int num_code_lengths = 4 + ReadBits(4);

אורכי הקוד מקודדים בעצמם באמצעות קודי קידומת. קוד ברמה נמוכה יותר אורכים, code_length_code_lengths, קודם צריך לקרוא אותו. את שאר האפשרויות code_length_code_lengths (לפי ההזמנה בkCodeLengthCodeOrder) הם אפסים.

int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
  17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 };  // All zeros
for (i = 0; i < num_code_lengths; ++i) {
  code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}

לאחר מכן, אם הערך הוא ReadBits(1) == 0, המספר המקסימלי של סמלים שנקראים (max_symbol) לכל סוג סמל (A, R, G, B ומרחק) מוגדר גודל אלפביתי:

• ערוץ G: 256 + 24 + color_cache_size
• מילים אחרות (A, R ו-B): 256
• קוד מרחק: 40

אחרת, הוא מוגדר כך:

int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);

אם max_symbol גדול מגודל האלפבית של סוג הסמל, הערך ה-bitstream לא חוקי.

לאחר מכן, טבלת תחילית נבנית מ-code_length_code_lengths ומשמשת להקראה עד max_symbol באורךי קוד.

• הקוד [0..15] מציין את אורכי הקוד באופן מילולי.
  • המשמעות של ערך 0 היא שלא קודדו סמלים.
  • הערכים [1..15] מציינים את אורך הביט של הקוד המתאים.
• קוד 16 חוזר על הערך הקודם שאינו אפס [3..6] פעמים, כלומר 3 + ReadBits(2) פעמים. אם משתמשים בקוד 16 לפני ערך שאינו אפס נוצר ערך, ערך של 8 חוזר על עצמו.
• קוד 17 פולט רצף של אפסים באורך [3..10], כלומר 3 + ReadBits(3) פעמים.
• קוד 18 משדר רצף של אפסים באורך [11..138], כלומר 11 + ReadBits(7) פעמים.

לאחר הקראת אורכי הקוד, יופיע קוד קידומת לכל סוג סמל (A, R, G, B ו-B מרחק) נוצר לפי גודל האלפבית המתאים.

regular Code Length Code (אורך קוד רגיל) חייב לקודד עץ החלטות מלא, כלומר הסכום של 2 ^ (-length) לכל הקודים שאינם אפס חייב להיות בדיוק אחד. עם זאת, יש כלל אחד שבו קיימת חריגה: עץ עם צומת עלה יחיד, שבו ערך צומת העלה מסומן בערך 1 ושאר הערכים הם 0.

6.2.2 פענוח קודים של מטא קידומת

כפי שציינו קודם, הפורמט מאפשר להשתמש בקודי קידומת שונים עבור בלוקים שונים של התמונה. קודי קידומת של מטא הם אינדקסים שמזהים קודי קידומת לשימוש בחלקים שונים של התמונה.

אפשר להשתמש בקודים של תחילית מטא רק כשהתמונה משמשת בתור תמונה ARGB.

יש שתי אפשרויות לקודי התחילית של המטא-קידומות, ויצוין בהן ערך 1-bit ערך:

• אם הביט הזה הוא אפס, יש רק מטא-קידומת אחת בשימוש בכל מקום ב- את התמונה. לא מאוחסנים נתונים נוספים.
• אם הבייט הזה הוא אחד, התמונה משתמשת בכמה קודי קידומת מטא. המטא-נתונים האלה קודי התחילית נשמרים כתמונת אנטרופיה (מתוארת בהמשך).

הרכיבים האדומים והירוקים של פיקסל מגדירים מטא-קידומת של 16 סיביות המשמשות בלוק מסוים של תמונת ה-ARGB.

תמונה של אנטרופיה

תמונה של אנטרופיה מגדירה את קודי הקידומת שבהם נעשה שימוש בחלקים שונים של התמונה.

3 הביטים הראשונים מכילים את הערך של prefix_bits. מאפייני האנטרופיה נגזרות מ-prefix_bits:

int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
    DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
    DIV_ROUND_UP(image_height, 1 << prefix_bits);

כאשר DIV_ROUND_UP מוגדר מוקדם יותר.

הביטים הבאים מכילים תמונת אנטרופיה ברוחב prefix_image_width ובגובה prefix_image_height.

פירוש של קודים של מטא קידומת

אפשר לקבל את מספר הקבוצות של קודי התחילית בתמונה של ה-ARGB, באמצעות הפונקציה קוד המטא-קידומת הגדול ביותר מתמונת האנטרופיה:

int num_prefix_groups = max(entropy image) + 1;

כאשר max(entropy image) מציין את קוד התחילית הגדול ביותר שמאוחסן תמונה באנטרופיה.

מכיוון שכל קבוצה של קודי תחילית מכילה חמישה קודי תחילית, המספר הכולל של קודי התחילית הוא:

int num_prefix_codes = 5 * num_prefix_groups;

בהינתן פיקסל (x, y) בתמונת ה-ARGB, נוכל לקבל את הקידומת המתאימה יש להשתמש בהם באופן הבא:

int position =
    (y >> prefix_bits) * prefix_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];

שבו אנחנו מניחים שקיים מבנה PrefixCodeGroup, שמייצג קבוצה של חמישה קודי קידומת. בנוסף, prefix_code_groups הוא מערך של PrefixCodeGroup (בגודל num_prefix_groups).

לאחר מכן, המפענח משתמש בקבוצת קידומות החיוג prefix_group כדי לפענח את הפיקסל (x, y), כפי שמוסבר ב"פענוח תמונה שמקודדת באנטרופיה" נתונים".

6.2.3 פענוח נתוני תמונה שמקודדים באנטרופיה

במיקום הנוכחי (x, y) בתמונה, המפענח מזהה קודם את קבוצת קודי קידומת התואמת (כפי שהוסבר בקטע האחרון). בהינתן קבוצת מקודדים, הפיקסלים נקראים ומפוענחים באופן הבא.

בשלב הבא, קוראים את הסמל S מזרם הביט באמצעות קוד הקידומת מס' 1. שימו לב ש-S היא כל מספר שלם בטווח 0 עד (256 + 24 + color_cache_size- 1).

הפרשנות של S תלויה בערך שלה:

1. אם S < 256
   1. משתמשים ב-S כרכיב הירוק.
   2. יש לקרוא בצבע אדום מה-bitstream באמצעות קוד קידומת #2.
   3. יש לקרוא בצבע כחול מה-bitstream באמצעות קוד קידומת #3.
   4. קריאת האלפא מה-bitstream באמצעות קוד קידומת #4.
2. If S >= 256 & S < 256 + 24
   1. צריך להשתמש ב-S עד 256 כקוד קידומת של אורך.
   2. קריאת ביטים נוספים עבור האורך של ה-bitstream.
   3. מצאו את אורך ההפניה לאחור L מקוד התחילית של האורך ו- לקרוא ביטים נוספים.
   4. יש לקרוא את קוד התחילית של המרחק מה-bitstream באמצעות קוד קידומת #5.
   5. קריאת ביטים נוספים למרחק מזרם הביטים.
   6. יש לקבוע את המרחק של הפניה לאחור D מקוד הקידומת של המרחק והקטעים הנוספים שנקראו.
   7. העתקת L פיקסלים (בסדר שורת הסריקה) מרצף הפיקסלים שמתחיל במיקום הנוכחי פחות D פיקסלים.
3. אם S >= 256 + 24
   1. השתמשו ב-S - (256 + 24) בתור האינדקס למטמון הצבעים.
   2. אחזור צבע ARGB מהמטמון של הצבעים במיקום הזה.

7 המבנה הכולל של הפורמט

למטה ניתן לראות את הפורמט בטופס ב-Backus-Naur (ABNF) RFC 5234 RFC 7405. היא לא כוללת את כל הפרטים. סוף התמונה (EOI) מקודדים באופן מרומז רק את מספר הפיקסלים (image_width * image_height).

הערה: המשמעות של *element היא שאפשר לחזור על element פעמים 0 או יותר. 5element פירושו ש-element חוזר על עצמו בדיוק 5 פעמים. %b מייצג ערך בינארי.

7.1 מבנה בסיסי

format        = RIFF-header image-header image-stream
RIFF-header   = %s"RIFF" 4OCTET %s"WEBPVP8L" 4OCTET
image-header  = %x2F image-size alpha-is-used version
image-size    = 14BIT 14BIT ; width - 1, height - 1
alpha-is-used = 1BIT
version       = 3BIT ; 0
image-stream  = optional-transform spatially-coded-image

7.2 המבנה של טרנספורמציות

optional-transform   =  (%b1 transform optional-transform) / %b0
transform            =  predictor-tx / color-tx / subtract-green-tx
transform            =/ color-indexing-tx

predictor-tx         =  %b00 predictor-image
predictor-image      =  3BIT ; sub-pixel code
                        entropy-coded-image

color-tx             =  %b01 color-image
color-image          =  3BIT ; sub-pixel code
                        entropy-coded-image

subtract-green-tx    =  %b10

color-indexing-tx    =  %b11 color-indexing-image
color-indexing-image =  8BIT ; color count
                        entropy-coded-image

7.3 המבנה של נתוני התמונה

spatially-coded-image =  color-cache-info meta-prefix data
entropy-coded-image   =  color-cache-info data

color-cache-info      =  %b0
color-cache-info      =/ (%b1 4BIT) ; 1 followed by color cache size

meta-prefix           =  %b0 / (%b1 entropy-image)

data                  =  prefix-codes lz77-coded-image
entropy-image         =  3BIT ; subsample value
                         entropy-coded-image

prefix-codes          =  prefix-code-group *prefix-codes
prefix-code-group     =
    5prefix-code ; See "Interpretation of Meta Prefix Codes" to
                 ; understand what each of these five prefix
                 ; codes are for.

prefix-code           =  simple-prefix-code / normal-prefix-code
simple-prefix-code    =  ; see "Simple Code Length Code" for details
normal-prefix-code    =  ; see "Normal Code Length Code" for details

lz77-coded-image      =
    *((argb-pixel / lz77-copy / color-cache-code) lz77-coded-image)

לפניכם רצף אפשרי לדוגמה:

RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image