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

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

מופשט

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

1 מבוא

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

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

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

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

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

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

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 מה-bitstream תוך שימוש בקוד קידומת #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. אם S >= 256 & S < 256 + 24
   1. צריך להשתמש ב-S עד 256 כקוד קידומת של אורך.
   2. קריאת ביטים נוספים עבור האורך של ה-bitstream.
   3. מצאו את אורך ההפניה לאחור L מקוד הקידומת של האורך ו- לקרוא ביטים נוספים.
   4. יש לקרוא את קוד התחילית של המרחק מה-bitstream באמצעות קוד קידומת #5.
   5. כדאי לקרוא בקטעים נוספים את המרחק מה-bitstream.
   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