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

Jyrki Alakuijala, Ph.D., Google, Inc., ‫2023-03-09

מופשט

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

‫1 מבוא

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

במסמך הזה אנחנו משתמשים באופן נרחב בתחביר של שפת התכנות C כדי לתאר את זרם הביטים, ומניחים שקיימת פונקציה לקריאת ביטים, 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 ללא אובדן נתונים יכולה לעבור ארבעה סוגים שונים של טרנספורמציות לפני שהיא עוברת קידוד אנטרופיה. מידע הטרנספורמציה בזרם הביטים מכיל את הנתונים שנדרשים להחלת הטרנספורמציות ההפוכות המתאימות.

‫2 מינוח

ARGB

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

תמונת ARGB

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

מטמון צבעים

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

תמונה עם אינדקס צבעים

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

שינוי צבעים בתמונה

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

מיפוי מרחקים

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

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

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

LZ77

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

קוד קידומת meta

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

תמונה של חיזוי

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

קוד קידומת

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

קידוד תחיליות

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

סדר שורות הסריקה

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

‫3 RIFF Header

בתחילת הכותרת יש מאגר RIFF. הוא מורכב מ-21 הבייטים הבאים:

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

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

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

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

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

int alpha_is_used = ReadBits(1);

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

int version_number = ReadBits(3);

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

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

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

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

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,
};

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

בהמשך מתואר תהליך שינוי הנתונים עבור סוגים שונים.

‫4.1 Predictor Transform

אפשר להשתמש בטרנספורמציה של חיזוי כדי להקטין את האנטרופיה. לשם כך, מנצלים את העובדה שלעתים קרובות יש קורלציה בין פיקסלים סמוכים. בטרנספורמציה של החיזוי, הערך הנוכחי של הפיקסל מחושב על סמך הפיקסלים שכבר פוענחו (בסדר של שורות הסריקה), ורק הערך השיורי (בפועל – חזוי) מקודד. הרכיב הירוק של פיקסל מגדיר איזה מבין 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 לא ידועים.

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

הערך של 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);
}

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

הטיפול בפיקסל 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 Color Transform (שינוי צבע)

המטרה של שינוי הצבע היא לבטל את המתאם בין ערכי ה-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;
}

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

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

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

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 הפחתת טרנספורמציה ירוקה

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

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

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

‫4.4 המרה של אינדקס צבעים

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

הטרנספורמציה של יצירת אינדקס צבעים בודקת את מספר ערכי ה-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 ממוקם ב-2 הביטים הכי פחות משמעותיים של הערך הירוק ב-x / 4, וערכים ירוקים ב-x + 1 עד x + 3 ממוקמים לפי הסדר בביטים המשמעותיים יותר של הערך הירוק ב-x / 4.
• ‫width_bits = 3: לכל ערך x, כאשר x ≡ 0 (mod 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. תמונת החיזוי: מאחסנת את המטא-נתונים של טרנספורמציית החיזוי (ראו 'טרנספורמציית החיזוי').
4. תמונה עם שינוי צבע: נוצרת על ידי ערכי ColorTransformElement (מוגדרים בColor Transform) עבור בלוקים שונים של התמונה.
5. תמונה עם אינדקס צבעים: מערך בגודל color_table_size (עד 256 ערכי ARGB) שמאחסן את המטא-נתונים של טרנספורמציית אינדקס הצבעים (ראו 'טרנספורמציית אינדקס הצבעים').

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

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

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

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

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

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

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

‫5.2.1 מחרוזות ליטרליות עם קידומת

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

‫5.2.2 הפניה לאחור ב-LZ77

הפניות לאחור הן טפלים של length ו-distance code:

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

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

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

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

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

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

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 מימין לפיקסל הנוכחי. ‫[Total such pixels = 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).

קודי מטמון הצבעים נשמרים באופן הבא. קודם כל, יש ערך של ביט אחד שמציין אם נעשה שימוש במטמון הצבעים. אם הביט הזה הוא 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]. מפענחים תואמים צריכים לציין זרם ביטים פגום עבור ערכים אחרים.

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

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

‫6 Entropy Code

‫6.1 סקירה כללית

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

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

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

‫6.2 פרטים

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

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

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

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

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

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

בקטע הזה מוסבר איך לקרוא את אורכי קידומות הקוד מזרם הביטים.

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

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

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

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

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

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

int num_symbols = ReadBits(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 גדול מגודל האלפבית של סוג הסמל, זרם הביטים לא תקין.

לאחר מכן נבנית טבלת תחיליות מ-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 ומרחק) באמצעות גודלי האלפבית המתאימים.

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

‫6.2.2 פענוח של קודי תחילית Meta

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

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

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

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

הרכיבים האדום והירוק של פיקסל מגדירים קוד מטא-קידומת של 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.

הסבר על קודי קידומת Meta

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

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

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

הערה: *element פירושו שאפשר לחזור על element אפס פעמים או יותר. ‫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