ג'ירקי אלקוויג'לה, Ph.D., Google, Inc., 2023-03-09
מופשט
WebPlossless הוא פורמט תמונה לדחיסה ללא אובדן של תמונות ARGB. הפורמט ללא אובדן נתונים מאחסן ומשחזר בדיוק את ערכי הפיקסלים, כולל ערכי הצבעים עבור פיקסלים שקופים לחלוטין. אלגוריתם אוניברסלי לדחיסת נתונים רציפה (LZ77), לקידוד קידומת ולמטמון צבעים משמש לדחיסת הנתונים בכמות גדולה. הוכחו שמהירויות הפענוח גבוהות יותר מ-PNG, וגם דחיסת נתונים צפופה יותר ב-25% בהשוואה לפורמט ה-PNG כיום.
1 מבוא
במסמך הזה מתואר ייצוג הנתונים הדחוסים של תמונה ללא אובדן WebP. הוא מיועד לעיון מפורט בהטמעה של מקודד ומפענח WebP ללא אובדן נתונים.
במסמך הזה אנחנו משתמשים באופן נרחב בתחביר של שפת תכנות 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.
- מטמון צבעים
- מערך קטן עם כתובות גיבוב לאחסון צבעים שהיו בשימוש לאחרונה, כדי לזכור אותם באמצעות קודים קצרים יותר.
- תמונה להוספת צבע לאינדקס
- תמונה חד-ממדית של צבעים, שניתן להוסיף לאינדקס באמצעות מספר שלם קטן (עד 256 בתוך WebP ללא אובדן).
- תמונה של המרת צבע
- תמונה דו-ממדית של רזולוציה משנית, שמכילה נתונים לגבי מתאמים של רכיבי צבע.
- מיפוי מרחק
- משנים מרחקים ב-LZ77 לערכים הקטנים ביותר של פיקסלים בקרבה דו-ממדית.
- תמונת אנטרופיה
- תמונה דו-ממדית של רזולוציה משנית, שמציינת באיזה קוד אנטרופיה צריך להשתמש בריבוע המתאים בתמונה, כלומר, כל פיקסל הוא קוד מטא-קידומת.
- LZ77
- אלגוריתם לדחיסת חלונות הזזה מבוסס מילון שפולט סמלים או מתאר אותם כרצפים של סמלים מהעבר.
- קוד קידומת מטא
- מספר שלם קטן (עד 16 ביטים) שמוסיף לאינדקס רכיב בטבלת המטא-תחילית.
- תמונת חיזוי
- תמונה דו-ממדית של רזולוציה משנית, שמציינת איזה חיזוי מרחבי משמש לריבוע מסוים בתמונה.
- קוד קידומת
- דרך קלאסית לביצוע קידוד אנטרופיה, שבה נעשה שימוש במספר קטן יותר של ביטים ליצירת קודים בתדירות גבוהה.
- קידוד קידומת
- דרך לקודד באנטרופיה מספרים שלמים גדולים יותר, שמקודדת כמה סיביות מהמספר השלם באמצעות קוד אנטרופיה ומקודדת את שאר הביטים הגולמיים. כך התיאורים של קודי האנטרופיה נשארים קטנים יחסית גם כשטווח הסמלים גדול.
- סדר שורות הסריקה
- סדר עיבוד של פיקסלים (משמאל לימין ומלמעלה למטה), החל מהפיקסל שבצד שמאל למעלה. אחרי שממלאים כל שורה, ממשיכים מהעמודה הימנית של השורה הבאה.
3 כותרת RIFF
בתחילת הכותרת מופיע מאגר RIFF. הוא מורכב מ-21 הבייטים הבאים:
- המחרוזת 'RIFF'.
- ערך קצת אנדיאני של 32 ביט של אורך המקטע, שהוא הגודל המלא של הקטע בשליטת כותרת ה-RIFF. בדרך כלל, זה שווה לגודל המטען הייעודי (גודל הקובץ פחות 8 בייטים: 4 בייטים למזהה RIFF ו-4 בייטים לאחסון הערך עצמו).
- המחרוזת 'WEBP' (שם מאגר RIFF).
- המחרוזת 'VP8L' (FourCC לנתוני תמונה בקידוד ללא אובדן).
- ערך קצת אנדי, של 32 ביט של מספר הבייטים בזרם ללא אובדן.
- חתימה 1 בייט 0x2f.
28 הביטים הראשונים של ה-bitstream מציינים את הרוחב והגובה של התמונה. רוחב וגובה מפוענחים כמספרים שלמים של 14 סיביות באופן הבא:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
הדיוק ב-14 ביט של הרוחב והגובה של התמונה מגביל את הגודל המקסימלי של תמונה ללא אובדן נתונים ב-WebP ל-16384 טווח פיקסלים.
הביט 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 | בלירה טורקית (TRY) |
| 4 | TL |
| 5 | ממוצע2(ממוצע2(L, TR), T) |
| 6 | ממוצע2(L, TL) |
| 7 | ממוצע2(L, T) |
| 8 | ממוצע2(TL, T) |
| 9 | ממוצע2(T, TR) |
| 10 | ממוצע2(ממוצע2(L, TL), Avg2(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);
}
קיימים כללי טיפול מיוחדים לחלק מהפיקסלים בגבולות. אם יש טרנספורמציה של חיזוי, ללא קשר למצב [0..13] של הפיקסלים האלה, הערך החזוי לפיקסל העליון ביותר של התמונה הוא 0xff000000. כל הפיקסלים בשורה העליונה הם L-pixel וכל הפיקסלים בעמודה הימנית ביותר הם T-pixel.
ניתן להתייחס לפיקסלים ב-TR עבור פיקסלים בעמודה הימנית ביותר. הפיקסלים בעמודה הימנית ביותר חזויים באמצעות המצבים [0..13], בדיוק כמו פיקסלים, לא בגבול, אבל במקום זאת נעשה שימוש בפיקסל השמאלי ביותר באותה שורה שבה משמש הפיקסל הנוכחי בתור TR-pixel.
ערך הפיקסלים הסופי מתקבל על ידי הוספת כל ערוץ של הערך החזוי לערך השיורי המקודד.
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 וערוץ צבע 8 ביט חתום של RGB (c) [ -128..127]
ומוגדר כך:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
לפני שמפעילים את ColorTransformDelta(), צריך להמיר את הייצוג הלא חתום של 8 ביט (uint8) ל-one (int8) החתום ב-8 ביט. צריך לפרש את הערך החתום כמספר משלים של שניים של 8 ביט (כלומר: טווח uint8 [128..255] ממופה לטווח [ -128..-1] של הערך שהומר ל-int8).
יש לבצע את הכפל ברמת דיוק גבוהה יותר (בדיוק של 16 ביט לפחות). למאפיין תוסף החתימה של פעולת Shift אין חשיבות כאן. כתוצאה מכך נעשה שימוש רק ב-8 הביטים הנמוכים ביותר, והשינויים של תוסף הסימנים ושל ההחלפה הלא חתומה תואמים זה לזה.
עכשיו נתאר את התוכן של נתוני הטרנספורמציה של הצבע, כך שפענוח הקידוד יוכל להחיל את התמרת הצבעים ההופכי ולשחזר את הערכים המקוריים של הצבע האדום והכחול. 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 חיסור הטרנספורמציה הירוקה
הטרנספורמציה הירוקה מחסירה ערכים ירוקים מהערכים האדום והכחול של כל פיקסל. כשהטרנספורמציה הזו קיימת, המפענח צריך להוסיף את הערך הירוק גם לערך האדום וגם לערך הכחול. אין נתונים שמשויכים להעברה הזו. המפענח מחיל את הטרנספורמציה ההפוכה באופן הבא:
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 צבעים או פחות מ-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 תפקידים של נתוני תמונות
אנחנו משתמשים בנתוני תמונות בחמישה תפקידים שונים:
- תמונת ARGB: שומרת את הפיקסלים בפועל של התמונה.
- תמונת אנטרופיה: שומרת את קודי הקידומות של המטא (ראו "פענוח קודי קידומת של מטא").
- תמונת חיזוי: שומרת את המטא-נתונים של הטרנספורמציה של החיזוי (מידע נוסף זמין במאמר 'טרנספורמציה של חיזוי').
- תמונה של המרת צבע: נוצרה על ידי ערכי
ColorTransformElement(מוגדר ב-"שינוי צבע") עבור בלוקים שונים של התמונה. - תמונה של הוספת צבעים לאינדקס: מערך בגודל
color_table_size(עד 256 ערכי ARGB) שמאחסנים את המטא-נתונים של הטרנספורמציה של הוספת הצבעים לאינדקס (מידע נוסף זמין במאמר "שינוי הוספת צבעים").
5.2 קידוד של נתוני תמונה
הקידוד של נתוני התמונה אינו תלוי בתפקידם.
קודם כול התמונה מחולקת לקבוצה של בלוקים בגודל קבוע (בדרך כלל בלוקים בגודל 16x16). המודלים של כל אחד מהבלוקים האלה נעשים באמצעות קודי אנטרופיה משלו. כמו כן, כמה בלוקים עשויים לחלוק את אותם קודים של אנטרופיה.
נימוק: אחסון של קוד אנטרופיה כרוך בעלות. אפשר למזער את העלות אם בלוקים דומים מבחינה סטטיסטית משתפים קוד אנטרופיה, וכך שומרים את הקוד פעם אחת בלבד. לדוגמה, מקודד יכול למצוא בלוקים דומים על ידי קיבוץ שלהם באמצעות המאפיינים הסטטיסטיים שלהם, או על ידי חיבור חוזר של זוג אשכולות שנבחרו באופן אקראי כאשר הוא מפחית את כמות הסיביות הכוללת שנדרשת לקידוד התמונה.
כל פיקסל מקודד באחת משלוש השיטות האפשריות:
- ליטרלים בקידוד קידומת: כל ערוץ (ירוק, אדום, כחול ואלפא) מקודד אנטרופיה בנפרד.
- הפניה לאחור LZ77: רצף של פיקסלים מועתק ממקום אחר בתמונה.
- קוד של מטמון צבע: באמצעות קוד גיבוב קצר הכפלה (אינדקס מטמון צבע) של צבע שנצפה לאחרונה.
בקטעי המשנה הבאים מתואר בפירוט כל אחת מהן.
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 |
| 12.9.09 | 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]. מפענחים תואמים צריכים לציין
bit-stream פגום עבור ערכים אחרים.
מטמון צבעים הוא מערך בגודל color_cache_size. כל רשומה שומרת צבע ARGB אחד. ניתן לחפש צבעים על ידי הוספה שלהם לאינדקס לפי (0x1e35a7bd * color) >> (32 -
color_cache_code_bits). רק חיפוש אחד מתבצע במטמון צבעים, ללא פתרון להתנגשויות.
בתחילת הפענוח או הקידוד של תמונה, כל הערכים בכל ערכי מטמון הצבעים מוגדרים לאפס. קוד מטמון הצבעים מומר לצבע הזה בזמן הפענוח. המצב של מטמון הצבעים נשמר על ידי הכנסה של כל פיקסל למטמון לפי הסדר שבו הן מופיעות בזרם, בין אם הפיקסלים נוצרים באמצעות הפניות לאחור ובין אם הם מופיעים בליטרל.
6 קוד אנטרופיה
6.1 סקירה כללית
רוב הנתונים מקודדים באמצעות קוד קידומת קנוני. לכן הקודים נשלחים על ידי שליחת אורך הקוד של הקידומת, בניגוד לקודי הקידומת עצמם.
באופן ספציפי, הפורמט משתמש בקוד קידומת של וריאציות מרחביות. במילים אחרות, אפשר להשתמש בקודי אנטרופיה שונים בין בלוקים שונים של התמונה.
הסיבה: לאזורים שונים בתמונה עשויים להיות מאפיינים שונים. לכן האפשרות להשתמש בקודים שונים של אנטרופיה מספקת גמישות רבה יותר ודחיסתה אפשרית.
6.2 פרטים
נתוני התמונה המקודדת מורכבים מכמה חלקים:
- פענוח הקוד ובניית הקודים של הקידומות.
- מטא קודים של קידומת.
- נתוני תמונה בקידוד האנטרופיה.
לכל פיקסל נתון (x, y), יש קבוצה של חמש קודי קידומת המשויכות אליו. הקודים האלה הם (לפי סדר העברת הנתונים):
- קוד קידומת מס' 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 ו-distance) לפי גודל האותיות המתאים.
הקוד הרגיל של אורך קוד צריך לקודד עץ החלטות מלא. כלומר, הסכום של 2 ^ (-length) לכל הקודים שהם לא אפס חייב להיות אחד בדיוק. עם זאת, יש יוצא מן הכלל אחד לכלל הזה, עץ הצומת עם עלה אחד, שבו הערך של צומת העלה מסומן עם ערך 1 וערכים אחרים הם 0.
6.2.2 פענוח הקוד של קודי קידומת המטא
כפי שצוין קודם, הפורמט מאפשר להשתמש בקודי קידומת שונים לבלוקים שונים של התמונה. קודי קידומת של מטא הם אינדקסים שמזהים באילו קודי קידומת להשתמש בחלקים שונים של התמונה.
אפשר להשתמש בקודי קידומת של מטא רק כאשר התמונה נמצאת בשימוש בתפקיד של תמונת 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.
פרשנות של קודי קידומת מטא
אפשר למצוא את מספר קבוצות הקודים של התחילית בתמונת ה-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), כפי שמוסבר במאמר "Decoding Entropy-Coded Image Data".
6.2.3 נתוני תמונה בקידוד אנטרופיה מפוענחת
למיקום הנוכחי (x, y) בתמונה, המפענח מזהה תחילה את קבוצת קודי התחילית התואמת (כפי שמוסבר בקטע הקודם). בהתאם לקבוצת קודי הקידומת, הפיקסל נקרא ומפוענח באופן הבא.
לאחר מכן, קרא את הסמל S מה-bitstream באמצעות קוד קידומת #1. שימו לב ש-S הוא כל מספר שלם בטווח 0 עד (256 + 24 + color_cache_size- 1).
הפרשנות של S תלויה בערך שלה:
- אם S < 256
- צריך להשתמש ב-S בתור הרכיב הירוק.
- הקראה בצבע אדום מה-bitstream באמצעות קוד קידומת #2.
- הקראה בצבע כחול מה-bitstream באמצעות קוד קידומת #3.
- קרא את האלפא מה-bitstream באמצעות קוד קידומת #4.
- אם S >= 256 ו-S < 256 + 24
- צריך להשתמש במספר S-256 כקוד קידומת אורך.
- קריאת ביטים נוספים לאורך האורך מה-bitstream.
- קובעים את האורך של ההפניה לאחור מקוד התחילית של האורך ואת הקוד של הביטים הנוספים.
- קוראים את קוד קידומת המרחק מה-bitstream באמצעות קוד קידומת #5.
- צריך לקרוא ביטים נוספים למרחק מה-bitstream.
- קובעים את המרחק D אחורה מקוד קידומת המרחק ואת הסיביות הנוספות שנקראות.
- מעתיקים L פיקסלים (בסדר שורת הסריקה) מרצף הפיקסלים, החל מהמיקום הנוכחי פחות D פיקסלים.
- אם S >= 256 + 24
- יש להשתמש ב-S - (256 + 24) כאינדקס למטמון הצבעים.
- מקבלים צבע 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