ד"ר יורקי אלקויאלה (Jyrki Alakuijala), Google, Inc., 9 במרץ 2023
מופשט
WebP Lossless הוא פורמט תמונה שמאפשר דחיסה ללא אובדן נתונים של תמונות ARGB. בפורמט ללא אובדן נתונים, ערכי הפיקסלים מאוחסנים ומוחזרים במדויק, כולל ערכי הצבעים של פיקסלים שקופים לחלוטין. כדי לדחוס את הנתונים בכמות גדולה, נעשה שימוש באלגוריתם אוניברסלי לדחיסת נתונים רציפים (LZ77), בקידוד קידומות ובמטמון צבעים. הוכחו מהירויות פענוח מהירות יותר מ-PNG, וגם דחיסה צפופה יותר ב-25% ממה שאפשר להשיג באמצעות פורמט PNG הנוכחי.
1 מבוא
במסמך הזה מתואר ייצוג הנתונים הדחוסים של קובץ WebP Lossless תמונה. המסמך הזה מיועד לשמש כמקור מידע מפורט להטמעת המקודד והמפענח ללא אובדן נתונים של 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 תמונה ללא אובדן נתונים יכולה לעבור ארבעה סוגים שונים של שינויים לפני במקודדים. נתוני הטרנספורמציה בזרם הביטים מכילים את הנתונים הנדרשים כדי להחיל את הטרנספורמציות ההפוכות המתאימות.
2 מינוחים
- ARGB
- ערך פיקסל שמורכב מערכי אלפא, אדום, ירוק וכחול.
- תמונה מסוג ARGB
- מערך דו-ממדי שמכיל פיקסלים של ARGB.
- מטמון צבעים
- מערך קטן עם כתובות גיבוב (hash) שמאחסן צבעים שהיו בשימוש לאחרונה, כדי לאפשר לך לזכור אותם באמצעות קודים קצרים יותר.
- תמונה להוספת צבעים
- תמונה חד-מימדית של צבעים שאפשר להוסיף לאינדקס באמצעות מספר שלם קטן (עד 256 ב-WebP ללא אובדן נתונים).
- תמונה לטרנספורמציה של צבע
- תמונה דו-מימדית ברזולוציה נמוכה שמכילה נתונים על המתאמים של רכיבי הצבע.
- מיפוי מרחקים
- משנה את המרחקים של LZ77 לערכים הנמוכים ביותר של פיקסלים קירבה דו-ממדית.
- תמונת אנטרופיה
- תמונה דו-ממדית ברזולוציה נמוכה שמציינת את קידוד האנטרופיה שצריך להשתמש בו בריבועים המתאימים בתמונה, כלומר כל פיקסל הוא קוד מטא-תחילית.
- LZ77
- אלגוריתם דחיסת נתונים מבוסס-מילון של חלון הזזה, שמפיק סמלים או מתאר אותם כרצפים של סמלים קודמים.
- מטא קידומת
- מספר שלם קטן (עד 16 ביט) שמוסיף לאינדקס רכיב בקידומת המטא טבלה.
- תמונת חיזוי
- תמונה דו-מימדית ברזולוציה נמוכה שמציינת איזה מנבא מרחבי משמש לריבועים מסוימים בתמונה.
- קוד תחילית
- דרך קלאסית לבצע תכנות אנטרופיה שבה נעשה שימוש במספר קטן יותר של ביטים לקודים תכופים יותר.
- קידוד קידומות
- שיטה לקידוד אנתרופי של מספרים שלמים גדולים יותר, שבה כמה ביטים של המספר השלם מקודדים באמצעות קוד אנתרופי, והביטים הנותרים מקודדים בפורמט גולמי. כך התיאורים של קודי האנטרופיה יכולים להישאר קטנים יחסית גם כשטווח הסמלים גדול.
- סדר הסריקה
- סדר עיבוד של פיקסלים (משמאל לימין ומלמעלה למטה), החל מהפיקסל בצד שמאל למעלה. לאחר שהושלמה שורה, ממשיכים של השורה הבאה בצד ימין של השורה הבאה.
3 כותרת RIFF
קונטיינר ה-RIFF נמצא בתחילת הכותרת. הוא מורכב מ-21 הבייטים הבאים:
- המחרוזת 'RIFF'.
- ערך של 32 ביט ב-little-endian של אורך הקטע, שהוא הגודל המלא של הקטע שנשלט על ידי כותרת ה-RIFF. בדרך כלל, הוא שווה לגודל המטען הייעודי (גודל הקובץ פחות 8 בייטים: 4 בייטים למזהה RIFF ו-4 בייטים לאחסון הערך עצמו).
- המחרוזת 'WEBP' (שם הקונטיינר של RIFF).
- מחרוזת 'VP8L' (FourCC לנתוני תמונה בקידוד ללא אובדן נתונים).
- ערך קטן מאוד של 32 ביט של מספר הבייטים בסטרימינג ללא אובדן מידע.
- חתימה בגודל 0x2f של 1 בייט.
28 הביטים הראשונים של ה-bitstream מציינים את הרוחב והגובה של התמונה. הרוחב והגובה מפענחים כמספרים שלמים של 14 ביט באופן הבא:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
הדיוק של 14 סיביות עבור רוחב וגובה התמונה מגביל את הגודל המרבי של תמונה ללא אובדן נתונים של WebP עד 1,6384 גישה ל-16,384 פיקסלים.
הבייט alpha_is_used הוא רק רמז, והוא לא אמור להשפיע על הפענוח. היא צריכה מוגדר ל-0 כאשר כל ערכי האלפא הם 255 בתמונה, ו-1 אם לא.
int alpha_is_used = ReadBits(1);
השדה version_number הוא קוד בן 3 ביט שצריך להגדיר ל-0. כל ערך אחר צריך להיחשב כשגיאה.
int version_number = ReadBits(3);
4 טרנספורמציות
השינויים הם מניפולציות הפיכות על נתוני התמונה שיכולות לצמצם את האנטרופיה הסמלית הנותרת באמצעות בניית מודלים של מתאמים מרחביים וצבעים. הם יכולה להפוך את הדחיסה הסופית לצפיפות יותר.
תמונה יכולה לעבור ארבעה סוגים של טרנספורמציות. ביט אחד מציין את נוכחות הטרנספורמציה. בכל טרנספורמציה מותר להשתמש פעם אחת בלבד. נעשה שימוש בטרנספורמציות רק לתמונה ב-ARGB ברמה הראשית. את התמונות המשניות (תמונה לטרנספורמציה של צבע, תמונת אנטרופיה ותמונת חיזוי) לא משתנים, אפילו לא ה-0 הביטים שמציינת את סוף השינויים.
בדרך כלל, מקודד ישתמש בשינויים האלה כדי לצמצם את אנטרופיה Shannon בתמונה הנותרת. בנוסף, ניתן לקבוע את נתוני הטרנספורמציה על סמך האנטרופיה צמצום החיפוש.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
אם יש טרנספורמציה, שני הביטים הבאים מציינים את סוג הטרנספורמציה. יש ארבעה סוגים של טרנספורמציות.
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
אחרי סוג הטרנספורמציה מופיעים הנתונים של הטרנספורמציה. נתוני הטרנספורמציה מכילים ותלוי במידע שנדרש כדי להחיל את הטרנספורמציה ההפוכה סוג של טרנספורמציה. התמרות ההופכיות מיושמות בסדר הפוך, קוראים אותם מה-bitstream, כלומר, מהשלב האחרון.
בהמשך מתוארים נתוני הטרנספורמציה של סוגים שונים.
4.1 טרנספורמציה של חזוי
אפשר להשתמש בטרנספורמציה של החיזוי כדי להפחית את האנטרופיה על ידי ניצול העובדה שלרוב יש התאמה בין פיקסלים קרובים. בטרנספורמציה של החיזוי, ערך הפיקסל הנוכחי צפוי על סמך הפיקסלים שכבר מפוענחו (בשורת הסריקה ) ורק הערך השיור (בפועל - צפוי) מקודד. הירוק רכיב של פיקסל מגדיר אילו מ-14 החיזויים ישמשו של קבוצת ה-ARGB. מצב החיזוי קובע את סוג החיזוי שבו נעשה שימוש. אנחנו מחלקים את התמונה לריבועים, ואת כל הפיקסלים בריבוע משתמשים באותו מצב חיזוי.
3 הביטים הראשונים של נתוני התחזית מגדירים את רוחב וגובה הבלוק במספר ביטים.
int size_bits = ReadBits(3) + 2;
int block_width = (1 << size_bits);
int block_height = (1 << size_bits);
#define DIV_ROUND_UP(num, den) (((num) + (den) - 1) / (den))
int transform_width = DIV_ROUND_UP(image_width, 1 << size_bits);
נתוני הטרנספורמציה מכילים את אופן החיזוי לכל בלוק בתמונה. הוא
היא תמונה בתת-רזולוציה שבה הרכיב הירוק של פיקסל מגדיר
14 החיזויים משמשים לכל block_width * block_height הפיקסלים בתוך
בלוק מסוים של תמונת ה-ARGB. התמונה המשנית מקודדת באמצעות
אותן שיטות שמתוארות בפרק 5.
מספר העמודות של הבלוק, transform_width, משמש להוספת אינדקס דו-מימדי. עבור פיקסל (x, y), אפשר לחשב את הכתובת המתאימה של בלוק המסנן באופן הבא:
int block_index = (y >> size_bits) * transform_width +
(x >> size_bits);
יש 14 מצבי חיזוי שונים. בכל מצב חיזוי, הערך הנוכחי ניתן לחזות את ערך הפיקסל מפיקסל קרוב אחד או יותר שהערכים שלהם כבר ידוע.
בחרנו את הפיקסלים הסמוכים (TL, T, TR ו-L) של הפיקסל הנוכחי (P) בתור ככה:
O O O O O O O O O O O
O O O O O O O O O O O
O O O O TL T TR O O O O
O O O O L P X X X X X
X X X X X X X X X X X
X X X X X X X X X X X
כאשר TL פירושו צד שמאל למעלה, T פירושו למעלה, TR פירושו צד ימין למעלה ו-L פירושו שמאל. בזמן חיזוי הערך של P, כל הפיקסלים O, TL, T, TR ו-L כבר עברו עיבוד, ופיקסל P וכל הפיקסלים X לא ידועים.
בהתאם לקודמים של הפיקסלים השכנים, מצבי החיזוי השונים מוגדרים באופן הבא.
| מצב | הערך הצפוי של כל ערוץ בפיקסל הנוכחי |
|---|---|
| 0 | 0xff000000 (לייצוג צבע שחור מלא ב-ARGB) |
| 1 | L |
| 2 | T |
| 3 | TR |
| 4 | TL |
| 5 | Average2(Average2(L, TR), T) |
| 6 | Average2(L, TL) |
| 7 | ממוצע2(L, T) |
| 8 | Average2(TL, T) |
| 9 | Average2(T, TR) |
| 10 | Average2(Average2(L, TL), Average2(T, TR)) |
| 11 | Select(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;
}
החזוי של Select מוגדר כך:
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 טרנספורמציית צבע
מטרת טרנספורמציית הצבע היא לבטל את הקורלציה בין ערכי ה-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). הערך החתום
שצריך לפרש כמספר משלים של 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 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 ממוקם בשני הביטים הכי פחות משמעותיים ערך ירוק ב-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 |
| 9..12 | 6 | 2 |
| 13..16 | 7 | 2 |
| ... | ... | ... |
| 3072..4096 | 23 | 10 |
| ... | ... | ... |
| 524289..786432 | 38 | 18 |
| 786433..1048576 | 39 | 18 |
הקוד המדומה לקבלת ערך (אורך או מרחק) מקוד הקידומת הוא:
if (prefix_code < 4) {
return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;
מיפוי מרחק
כפי שצוין קודם לכן, קוד מרחק הוא מספר שמציין את המיקום של פיקסלים שראינו בעבר, שממנו יש להעתיק את הפיקסלים. קטע המשנה הזה מגדיר את המיפוי בין קוד המרחק לבין המיקום של תג פיקסל.
קודי מרחק גדולים מ-120 מציינים את מרחק הפיקסלים בסדר של שורת הסריקה, עם הזזה של 120.
קודי המרחק הקטנים ביותר [1..120] הם מיוחדים ושמורים לאזור קרוב לאותו פיקסל. השכונה הזו מורכבת מ-120 פיקסלים:
- פיקסלים שנמצאים בשורה אחת עד 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 פרטים
נתוני התמונה המוצפנים מורכבים מכמה חלקים:
- פענוח וקיבוץ של קודי הקידומות.
- קודי קידומת של מטא.
- נתוני תמונה מקודדים באנטרופיה.
לכל פיקסל נתון (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;
}
שני הסמלים צריכים להיות שונים. מותר להשתמש בסמלים כפולים, אבל זה לא יעיל.
הערה: מקרה מיוחד נוסף הוא כאשר כל אורכי קודי הקידומת הם אפסים (קוד קידומת ריק). לדוגמה, קוד קידומת למרחק יכול להיות ריק אם אין הפניות לאחור. באופן דומה, קודי הקידומות של אלפא, אדום וכחול יכולים להיות ריקים אם כל הפיקסלים באותו קוד קידומת של meta נוצרים באמצעות מטמון הצבעים. עם זאת, אין צורך לטפל במקרה הזה באופן מיוחד, כי אפשר לקודד קודי קידומת ריקים כאלה שמכילים סמל יחיד 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 והמרחק) באמצעות גדלי האלפבית המתאימים.
regular Code Length Code (אורך קוד רגיל) חייב לקודד עץ החלטות מלא, כלומר הסכום של
2 ^ (-length) לכל הקודים שאינם אפס חייב להיות בדיוק אחד. עם זאת, יש כלל אחד שבו קיימת חריגה: עץ עם צומת עלה יחיד, שבו ערך צומת העלה מסומן בערך 1 ושאר הערכים הם 0.
6.2.2 פענוח של קודי תחילית של Meta
כפי שציינו קודם, הפורמט מאפשר להשתמש בקודי קידומת שונים עבור בלוקים שונים של התמונה. קודי קידומת של מטא הם אינדקסים שמזהים קודי קידומת לשימוש בחלקים שונים של התמונה.
אפשר להשתמש בקודים של קידומת מטא רק כשהתמונה משמשת בתור תמונה ARGB.
יש שתי אפשרויות לקודי הקידומת של המטא, שמסומנות בערך של ביט אחד:
- אם הבייט הזה הוא אפס, יש רק קוד מטא-תחילית אחד שמשמש בכל מקום בתמונה. לא יישמרו נתונים נוספים.
- אם הבייט הזה הוא אחד, התמונה משתמשת בכמה קודי קידומת מטא. קודי המטא-תחילית האלה מאוחסנים כתמונה של אנטרופי (כפי שמתואר בהמשך).
הרכיבים האדומים והירוקים של פיקסל מגדירים מטא-קידומת של 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 תלויה בערך שלו:
- אם S < 256
- משתמשים ב-S כרכיב הירוק.
- קוראים את האדום מזרם הביט באמצעות קוד הקידומת מס' 2.
- יש לקרוא בצבע כחול מה-bitstream באמצעות קוד קידומת #3.
- קריאת אלפא מזרם הביטים באמצעות קוד הקידומת מס' 4.
- If S >= 256 & S < 256 + 24
- משתמשים ב-S – 256 כקוד קידומת באורך.
- קריאת ביטים נוספים של האורך מזרם הביטים.
- מחשבים את אורך ההפניה לאחור L לפי קוד הקידומת של האורך והביטים הנוספים שנקראו.
- יש לקרוא את קוד התחילית של המרחק מה-bitstream באמצעות קוד קידומת #5.
- קריאת ביטים נוספים למרחק מזרם הביטים.
- יש לקבוע את המרחק של הפניה לאחור 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