يوركي ألاكوئيلا، دكتوراه في الفلسفة، Google, Inc., 2023-03-09
فنون تجريدية
تنسيق WebP بدون فقدان أي تفاصيل هو تنسيق صور يتيح ضغط صور ARGB بدون فقدان أي تفاصيل. يخزّن التنسيق غير المنقوص قيم البكسل ويعيدها بدقة، بما في ذلك قيم الألوان للبكسل الشفاف تمامًا. يتم استخدام خوارزمية شاملة لضغط البيانات التسلسلية (LZ77) وتشفير البادئة وذاكرة تخزين مؤقت للألوان لضغط البيانات المجمّعة. وقد تم إثبات أنّ سرعات فك الترميز أسرع من PNG، بالإضافة إلى ضغط أكثر كثافة بنسبة% 25 مقارنةً بما يمكن تحقيقه باستخدام تنسيق PNG الحالي.
1. مقدمة
يوضّح هذا المستند تمثيل البيانات المضغوطة لصورة WebP بدون فقدان البيانات. وهي مخصّصة كمرجع تفصيلي لتنفيذ برنامج الترميز وفك الترميز بدون فقدان البيانات في WebP.
في هذا المستند، نستخدم بشكل موسّع صيغة لغة البرمجة C لوصف دفق البتات، ونفترض وجود دالة لقراءة البتات، ReadBits(n). تتم قراءة البايتات بالترتيب الطبيعي للدفق الذي يحتوي عليها، وتتم قراءة وحدات البت لكل بايت بترتيب الأقل أهمية أولاً. عند قراءة عدة وحدات بت في الوقت نفسه، يتم إنشاء العدد الصحيح من البيانات الأصلية بالترتيب الأصلي. تكون البتات الأكثر أهمية في العدد الصحيح الذي تم إرجاعه هي أيضًا البتات الأكثر أهمية في البيانات الأصلية. وبالتالي، فإن العبارة
b = ReadBits(2);
تعادل العبارتَين أدناه:
b = ReadBits(1);
b |= ReadBits(1) << 1;
نفترض أنّ كل مكوّن من مكوّنات الألوان، أي ألفا والأحمر والأزرق والأخضر، يتم تمثيله باستخدام بايت من 8 بت. نحدّد النوع المقابل على أنّه uint8. يتم تمثيل بكسل ARGB كامل بنوع يُسمى uint32، وهو عدد صحيح غير موقّع يتألف من 32 بت. في الرمز الذي يعرض سلوك عمليات التحويل، يتم ترميز هذه القيم في الأجزاء التالية: قناة ألفا في الأجزاء 31..24، وقناة الأحمر في الأجزاء 23..16، وقناة الأخضر في الأجزاء 15..8، وقناة الأزرق في الأجزاء 7..0. ومع ذلك، يمكن لعمليات تنفيذ التنسيق استخدام تمثيل آخر داخليًا.
بشكل عام، تحتوي صورة WebP بدون فقدان أي تفاصيل على بيانات العنوان ومعلومات التحويل وبيانات الصورة الفعلية. تحتوي العناوين على عرض الصورة وارتفاعها. يمكن أن تخضع صورة WebP بدون فقدان أي تفاصيل لأربعة أنواع مختلفة من عمليات التحويل قبل أن يتم ترميزها باستخدام الترميز القائم على الإنتروبيا. تحتوي معلومات التحويل في دفق البتات على البيانات المطلوبة لتطبيق عمليات التحويل العكسية ذات الصلة.
2 التسمية
- ARGB
- قيمة بكسل تتألف من قيم ألفا والأحمر والأخضر والأزرق
- صورة ARGB
- صفيف ثنائي الأبعاد يحتوي على وحدات بكسل ARGB
- ذاكرة التخزين المؤقت للألوان
- مصفوفة صغيرة ذات عناوين تجزئة لتخزين الألوان المستخدَمة مؤخرًا حتى يمكن استرجاعها برموز أقصر.
- صورة فهرسة الألوان
- صورة أحادية البعد للألوان يمكن فهرستها باستخدام عدد صحيح صغير (يصل إلى 256 ضمن WebP بدون فقدان البيانات).
- تحويل صورة الألوان
- صورة ثنائية الأبعاد ذات دقة فرعية تحتوي على بيانات حول ارتباطات مكوّنات الألوان
- تحديد المسافة
- تغيير مسافات LZ77 للحصول على أصغر قيم لوحدات البكسل في التقارب الثنائي الأبعاد
- صورة الإنتروبيا
- صورة ثنائية الأبعاد ذات دقة فرعية تشير إلى ترميز الإنتروبيا الذي يجب استخدامه في كل مربّع في الصورة، أي أنّ كل بكسل هو رمز بادئة وصفية.
- LZ77
- خوارزمية ضغط مستندة إلى قاموس مع نافذة منزلقة تعرض إما رموزًا أو تصفها كتسلسلات من الرموز السابقة.
- رمز البادئة الوصفية
- عدد صحيح صغير (يصل إلى 16 بت) يفهرس عنصرًا في جدول البادئة الوصفية.
- صورة أداة التوقّع
- صورة ثنائية الأبعاد ذات دقة فرعية تشير إلى أداة التوقّع المكاني المستخدَمة لمربّع معيّن في الصورة
- رمز البادئة
- طريقة تقليدية لترميز البيانات العشوائية، حيث يتم استخدام عدد أقل من البتات للرموز الأكثر تكرارًا.
- ترميز البادئة
- طريقة لترميز الأعداد الصحيحة الأكبر حجمًا باستخدام الترميز بالإنتروبيا، حيث يتم ترميز بضع وحدات بت من العدد الصحيح باستخدام الترميز بالإنتروبيا، ويتم ترميز وحدات البت المتبقية بشكل غير معالَج. يسمح ذلك بأن تظل أوصاف رموز الإنتروبيا صغيرة نسبيًا حتى عندما يكون نطاق الرموز كبيرًا.
- ترتيب خطوط المسح
- ترتيب معالجة وحدات البكسل (من اليمين إلى اليسار ومن الأعلى إلى الأسفل)، بدءًا من وحدة البكسل في أعلى اليمين بعد إكمال صف، تابِع من العمود الأيمن للصف التالي.
3 RIFF Header
يحتوي بداية العنوان على حاوية RIFF. ويتألّف ذلك من 21 بايت على النحو التالي:
- السلسلة "RIFF"
- قيمة 32 بت لطول الجزء، وهي الحجم الكامل للجزء الذي يتحكّم فيه عنوان RIFF، ويتم ترتيب البايتات من الأصغر إلى الأكبر. ويساوي هذا الحجم عادةً حجم الحمولة (حجم الملف ناقص 8 بايت: 4 بايت لمعرّف RIFF و4 بايت لتخزين القيمة نفسها).
- السلسلة "WEBP" (اسم حاوية RIFF).
- السلسلة VP8L (رمز FourCC لبيانات الصور المرمّزة بدون فقدان البيانات)
- قيمة 32 بت بنظام little-endian تمثّل عدد وحدات البايت في البث بدون فقدان البيانات.
- توقيع مكوّن من بايت واحد 0x2f.
تحدّد أول 28 بت من دفق البتات عرض الصورة وارتفاعها. يتم فك ترميز العرض والارتفاع كأعداد صحيحة مكوّنة من 14 بت على النحو التالي:
int image_width = ReadBits(14) + 1;
int image_height = ReadBits(14) + 1;
تحدّ الدقة البالغة 14 بت لعرض الصورة وارتفاعها من الحد الأقصى لحجم صورة WebP غير المضغوطة إلى 16384×16384 بكسل.
إنّ بت alpha_is_used هو تلميح فقط، ولا يجب أن يؤثر في عملية فك الترميز. يجب ضبطها على 0 عندما تكون جميع قيم ألفا 255 في الصورة، وعلى 1 في الحالات الأخرى.
int alpha_is_used = ReadBits(1);
رقم الإصدار هو رمز مكوّن من 3 بتات يجب ضبطه على 0. يجب التعامل مع أي قيمة أخرى على أنّها خطأ.
int version_number = ReadBits(3);
4 عمليات تحويل
عمليات التحويل هي عمليات معالجة قابلة للعكس لبيانات الصورة، ويمكن أن تقلّل من الإنتروبيا الرمزية المتبقية من خلال نمذجة الارتباطات المكانية واللونية. ويمكن أن تجعل عملية الضغط النهائية أكثر كثافة.
يمكن أن تخضع الصورة لأربعة أنواع من عمليات التحويل. تشير القيمة 1 بت إلى توفّر عملية تحويل. يُسمح باستخدام كل عملية تحويل مرة واحدة فقط. يتم استخدام عمليات التحويل فقط لصورة ARGB الرئيسية، ولا تتضمّن صور الدقة الفرعية (صورة تحويل الألوان وصورة الإنتروبيا وصورة التوقّع) أي عمليات تحويل، ولا حتى البت 0 الذي يشير إلى نهاية عمليات التحويل.
عادةً، يستخدم برنامج الترميز عمليات التحويل هذه لتقليل إنتروبيا شانون في الصورة المتبقية. يمكن أيضًا تحديد بيانات التحويل استنادًا إلى تقليل الإنتروبيا.
while (ReadBits(1)) { // Transform present.
// Decode transform type.
enum TransformType transform_type = ReadBits(2);
// Decode transform data.
...
}
// Decode actual image data (Section 5).
في حال توفّر عملية تحويل، تحدّد البتّتان التاليتان نوع عملية التحويل. هناك أربعة أنواع من عمليات التحويل.
enum TransformType {
PREDICTOR_TRANSFORM = 0,
COLOR_TRANSFORM = 1,
SUBTRACT_GREEN_TRANSFORM = 2,
COLOR_INDEXING_TRANSFORM = 3,
};
يلي نوع التحويل بيانات التحويل. تحتوي بيانات التحويل على المعلومات المطلوبة لتطبيق التحويل العكسي، وتعتمد على نوع التحويل. يتم تطبيق عمليات التحويل العكسية بالترتيب العكسي الذي تتم قراءتها به من دفق البتات، أي آخر عملية تحويل أولاً.
بعد ذلك، سنشرح كيفية تحويل البيانات لأنواع مختلفة.
4.1 Predictor Transform
يمكن استخدام عملية تحويل التوقّع لتقليل الإنتروبيا من خلال الاستفادة من حقيقة أنّ وحدات البكسل المجاورة غالبًا ما تكون مرتبطة. في عملية تحويل التوقّع، يتم توقّع قيمة البكسل الحالية من البكسلات التي تم فك ترميزها مسبقًا (بترتيب خط المسح)، ويتم ترميز القيمة المتبقية فقط (القيمة الفعلية - القيمة المتوقّعة). يحدّد المكوّن الأخضر في البكسل أيًّا من المؤشرات الـ 14 يتم استخدامه ضمن جزء معيّن من صورة ARGB. يحدّد وضع التوقّع نوع التوقّع الذي سيتم استخدامه. نقسم الصورة إلى مربّعات، وتستخدم جميع وحدات البكسل في المربّع وضع التوقّع نفسه.
تحدّد الأجزاء الثلاثة الأولى من بيانات التوقّع عرض المربّع وارتفاعه بعدد الأجزاء.
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 وضعًا مختلفًا للتوقّع. في كل وضع من أوضاع التوقّع، يتم توقّع قيمة البكسل الحالية من بكسل واحد أو أكثر من البكسلات المجاورة التي تكون قيمها معروفة.
اخترنا وحدات البكسل المجاورة (أعلى يسار وأعلى وأعلى يمين ويسار) لوحدة البكسل الحالية (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 | بالليرة التركية |
| 4 | قائد فريق |
| 5 | Average2(Average2(L, TR), T) |
| 6 | Average2(L, TL) |
| 7 | Average2(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;
}
يتم تعريف أداة التوقّع "اختيار" على النحو التالي:
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.
يُستثنى من ذلك معالجة البكسل الشفاف للبكسلات في العمود الأقصى على اليسار. يتم توقّع قيم البكسلات في العمود الأقصى على اليسار باستخدام الأوضاع [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 تحويل الألوان
والهدف من تحويل الألوان هو إزالة الارتباط بين قيم الأحمر والأخضر والأزرق لكل بكسل. يحافظ تحويل الألوان على قيمة اللون الأخضر (G) كما هي، ويحوّل قيمة اللون الأحمر (R) استنادًا إلى قيمة اللون الأخضر، ويحوّل قيمة اللون الأزرق (B) استنادًا إلى قيمة اللون الأخضر ثم إلى قيمة اللون الأحمر.
كما هو الحال مع عملية تحويل التوقّع، يتم أولاً تقسيم الصورة إلى مربّعات، ويتم استخدام وضع التحويل نفسه لجميع وحدات البكسل في المربّع. لكل كتلة، هناك ثلاثة أنواع من عناصر تحويل الألوان.
typedef struct {
uint8 green_to_red;
uint8 green_to_blue;
uint8 red_to_blue;
} ColorTransformElement;
يتم إجراء عملية تحويل الألوان الفعلية من خلال تحديد دلتا تحويل الألوان. يعتمد الفرق في تحويل الألوان على ColorTransformElement، وهو نفسه لجميع وحدات البكسل في حزمة معيّنة. ويتم طرح الفرق أثناء تحويل الألوان. بعد ذلك، ما عليك سوى إضافة هذه الفروق إلى عملية تحويل الألوان العكسية.
يتم تعريف دالة تحويل الألوان على النحو التالي:
void ColorTransform(uint8 red, uint8 blue, uint8 green,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the transform is just subtracting the transform deltas
tmp_red -= ColorTransformDelta(trans->green_to_red, green);
tmp_blue -= ColorTransformDelta(trans->green_to_blue, green);
tmp_blue -= ColorTransformDelta(trans->red_to_blue, red);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
يتم احتساب ColorTransformDelta باستخدام عدد صحيح 8 بت يحمل علامة ويمثّل رقمًا ثابتًا بـ 3.5 خانات عشرية، وقناة ألوان RGB 8 بت تحمل علامة (c) [-128..127]، ويتم تعريفه على النحو التالي:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
يجب إجراء عملية تحويل من التمثيل غير الموقّع ذي 8 بتات (uint8) إلى التمثيل الموقّع ذي 8 بتات (int8) قبل استدعاء ColorTransformDelta(). يجب تفسير القيمة الموقّعة على أنّها رقم مكمّل ثنائي 8 بت (أي أنّه يتم ربط نطاق uint8 [128..255] بالنطاق [-128..-1] لقيمة int8 المحوّلة).
يجب إجراء عملية الضرب باستخدام دقة أكبر (بحد أدنى 16 بت). لا تهم خاصية توسيع الإشارة لعملية الإزاحة هنا، بل يتم استخدام 8 بتات فقط من النتيجة، وفي هذه البتات، يكون توسيع الإشارة متوافقًا مع الإزاحة غير الموقّعة.
الآن، نصف محتوى بيانات تحويل الألوان حتى يتمكّن برنامج الترميز من تطبيق عملية تحويل الألوان العكسية واسترداد قيمتَي الأحمر والأزرق الأصليتَين. تحتوي وحدات البت الثلاث الأولى من بيانات تحويل الألوان على عرض وارتفاع كتلة الصورة بعدد وحدات البت، تمامًا مثل تحويل أداة التوقّع:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
يحتوي الجزء المتبقي من بيانات تحويل الألوان على ColorTransformElement
مثال، يتوافق مع كل جزء من الصورة. يتم التعامل مع كل
ColorTransformElement 'cte' على أنّه بكسل في صورة ذات دقة فرعية
مكوّن ألفا فيها هو 255، ومكوّن الأحمر هو cte.red_to_blue، ومكوّن الأخضر
هو cte.green_to_blue، ومكوّن الأزرق هو cte.green_to_red.
أثناء فك الترميز، يتم فك ترميز مثيلات ColorTransformElement للكتل، ويتم تطبيق تحويل الألوان العكسي على قيم ARGB الخاصة بالبكسلات. كما ذكرنا سابقًا، فإنّ تحويل الألوان المعكوسة هو مجرد إضافة قيم ColorTransformElement إلى قنوات الأحمر والأزرق. ويتم ترك قناتَي ألفا والأخضر كما هما.
void InverseTransform(uint8 red, uint8 green, uint8 blue,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the inverse transform is just adding the
// color transform deltas
tmp_red += ColorTransformDelta(trans->green_to_red, green);
tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
tmp_blue +=
ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
4.3 طرح التحويل الأخضر
تطرح عملية تحويل "طرح اللون الأخضر" قيم اللون الأخضر من قيم اللونين الأحمر والأزرق لكل بكسل. عند توفّر عملية التحويل هذه، على أداة فك الترميز إضافة قيمة اللون الأخضر إلى قيمتَي اللونين الأحمر والأزرق. لا تتوفّر بيانات مرتبطة بهذا التحويل. يطبّق برنامج الترميز التحويل العكسي على النحو التالي:
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
هذا التحويل مكرّر، إذ يمكن نمذجته باستخدام تحويل الألوان، ولكن بما أنّه لا تتوفّر بيانات إضافية هنا، يمكن ترميز تحويل طرح اللون الأخضر باستخدام عدد أقل من البتات مقارنةً بتحويل الألوان الكامل.
4.4 تحويل فهرسة الألوان
إذا لم تكن هناك العديد من قيم البكسل الفريدة، قد يكون من الأفضل إنشاء مصفوفة فهرس ألوان واستبدال قيم البكسل بفهارس المصفوفة. وتحقّق عملية تحويل فهرسة الألوان ذلك. (في سياق WebP بدون فقدان البيانات، لا نطلق على هذه العملية اسم "تحويل لوحة الألوان" لأنّ هناك مفهومًا مشابهًا ولكن أكثر ديناميكية في ترميز WebP بدون فقدان البيانات، وهو ذاكرة التخزين المؤقت للألوان).
تتحقّق عملية تحويل فهرسة الألوان من عدد قيم ARGB الفريدة في الصورة. إذا كان هذا الرقم أقل من الحد الأدنى (256)، يتم إنشاء مصفوفة من قيم ARGB هذه، والتي يتم استخدامها بعد ذلك لاستبدال قيم البكسل بالفهرس المقابل: يتم استبدال القناة الخضراء للبكسلات بالفهرس، ويتم ضبط جميع قيم ألفا على 255، وجميع قيم الأحمر والأزرق على 0.
تحتوي بيانات التحويل على حجم جدول الألوان والإدخالات في جدول الألوان. يقرأ برنامج الترميز بيانات تحويل فهرسة الألوان على النحو التالي:
// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;
يتم تخزين جدول الألوان باستخدام تنسيق تخزين الصورة نفسه. يمكن الحصول على جدول الألوان من خلال قراءة صورة بدون عنوان RIFF وحجم الصورة وعمليات التحويل، على أن يكون الارتفاع بكسل واحد والعرض color_table_size.
يتم دائمًا ترميز جدول الألوان باستخدام الطرح لتقليل إنتروبيا الصورة. تحتوي دلتا ألوان اللوحة عادةً على إنتروبيا أقل بكثير من الألوان نفسها، ما يؤدي إلى توفير كبير في الصور الأصغر حجمًا. في عملية فك الترميز، يمكن الحصول على كل لون نهائي في جدول الألوان من خلال إضافة قيم مكونات اللون السابقة حسب كل مكون ARGB بشكل منفصل وتخزين أقل 8 بتات أهمية من النتيجة.
ويتم عكس عملية التحويل للصورة ببساطة عن طريق استبدال قيم البكسل (التي تمثّل فهارس لجدول الألوان) بقيم جدول الألوان الفعلية. تتم الفهرسة استنادًا إلى المكوّن الأخضر من لون ARGB.
// Inverse transform
argb = color_table[GREEN(argb)];
إذا كان الفهرس يساوي color_table_size أو أكبر منه، يجب ضبط قيمة لون argb على 0x00000000 (أسود شفاف).
عندما يكون جدول الألوان صغيرًا (يساوي 16 لونًا أو أقل)، يتم تجميع عدة وحدات بكسل في وحدة بكسل واحدة. تجمع حِزم البكسل عدة وحدات بكسل (2 أو 4 أو 8) في وحدة بكسل واحدة، ما يؤدي إلى تقليل عرض الصورة. تتيح عملية تجميع وحدات البكسل ترميز إنتروبيا مشتركًا أكثر فعالية لتوزيع وحدات البكسل المجاورة، وتوفّر بعض المزايا المشابهة للترميز الحسابي لرمز الإنتروبيا، ولكن لا يمكن استخدامها إلا عندما تكون هناك 16 قيمة فريدة أو أقل.
تحدّد color_table_size عدد وحدات البكسل التي يتم دمجها:
int width_bits;
if (color_table_size <= 2) {
width_bits = 3;
} else if (color_table_size <= 4) {
width_bits = 2;
} else if (color_table_size <= 16) {
width_bits = 1;
} else {
width_bits = 0;
}
تحتوي السمة width_bits على القيمة 0 أو 1 أو 2 أو 3. تشير القيمة 0 إلى أنّه لن يتم تجميع وحدات البكسل للصورة. تشير القيمة 1 إلى أنّه تم دمج بكسلين، ويتراوح نطاق كل بكسل بين [0..15]. تشير القيمة 2 إلى أنّه يتم دمج أربع وحدات بكسل، ويتراوح نطاق كل وحدة بكسل بين [0..3]. تشير القيمة 3 إلى أنّه يتم دمج ثمانية وحدات بكسل، وأنّ كل وحدة بكسل تتضمّن نطاقًا من [0..1]، أي قيمة ثنائية.
يتم تجميع القيم في المكوّن الأخضر على النحو التالي:
width_bits= 1: لكل قيمة x، حيث x ≡ 0 (mod 2)، يتم وضع قيمة خضراء عند x في 4 وحدات بت الأقل أهمية من القيمة الخضراء عند x / 2، ويتم وضع قيمة خضراء عند x + 1 في 4 وحدات بت الأكثر أهمية من القيمة الخضراء عند x / 2.width_bits= 2: لكل قيمة x، حيث x ≡ 0 (mod 4)، يتم وضع قيمة خضراء عند x في وحدتَي البت الأقل أهمية من القيمة الخضراء عند x / 4، ويتم وضع القيم الخضراء عند x + 1 إلى x + 3 بالترتيب في وحدات البت الأكثر أهمية من القيمة الخضراء عند x / 4.width_bits= 3: لكل قيمة x، حيث x ≡ 0 (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 ترميز بيانات الصور
إنّ ترميز بيانات الصورة مستقل عن دورها.
يتم أولاً تقسيم الصورة إلى مجموعة من المربّعات الثابتة الحجم (عادةً مربّعات 16×16). يتم تصميم كلّ من هذه الأقسام باستخدام رموز إنتروبيا خاصة بها. بالإضافة إلى ذلك، قد تتشارك عدة كتل رموز الإنتروبيا نفسها.
السبب: يؤدي تخزين رمز إنتروبيا إلى تكبّد تكلفة. ويمكن تقليل هذه التكلفة إلى الحد الأدنى إذا كانت الوحدات المتشابهة إحصائيًا تتشارك رمز قصور، وبالتالي يتم تخزين هذا الرمز مرة واحدة فقط. على سبيل المثال، يمكن لبرنامج الترميز العثور على كتل متشابهة من خلال تجميعها باستخدام خصائصها الإحصائية أو من خلال ضم زوج من المجموعات المحددة عشوائيًا بشكل متكرر عندما يقلل من إجمالي عدد البتات اللازمة لترميز الصورة.
يتم ترميز كل بكسل باستخدام إحدى الطرق الثلاث الممكنة:
- القيم الحرفية المرمّزة بالبادئة: يتم ترميز كل قناة (الأخضر والأحمر والأزرق وقناة ألفا) بشكل مستقل باستخدام ترميز الإنتروبيا.
- مرجع LZ77 للخلف: يتم نسخ تسلسل من وحدات البكسل من موضع آخر في الصورة.
- رمز ذاكرة التخزين المؤقت للألوان: استخدام رمز تجزئة ضربي قصير (فهرس ذاكرة التخزين المؤقت للألوان) للون تم عرضه مؤخرًا
توضّح الأقسام الفرعية التالية كلّاً من هذه الحالات بالتفصيل.
5.2.1 القيم الحرفية ذات البادئة
يتم تخزين البكسل كقيم مسبوقة برمز بادئة للألوان الأخضر والأحمر والأزرق وقيمة ألفا (بهذا الترتيب). راجِع الفقرة 6.2.3 للاطّلاع على التفاصيل.
5.2.2 مرجع LZ77 السابق
المراجع الخلفية هي مجموعات من الطول ورمز المسافة:
- يشير الطول إلى عدد وحدات البكسل التي سيتم نسخها بترتيب خطوط المسح.
- رمز المسافة هو رقم يشير إلى موضع بكسل سبق ظهوره، ويتم نسخ البكسلات منه. يمكنك الاطّلاع على عملية الربط الدقيقة أدناه.
يتم تخزين قيم الطول والمسافة باستخدام ترميز البادئة 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) للبكسل المجاور، أي البكسل الذي يقع فوق البكسل الحالي (لا يوجد فرق في عدد البكسلات في الاتجاه X، وفرق بكسل واحد في الاتجاه Y).
وبالمثل، يشير رمز المسافة 3 إلى البكسل في أعلى اليمين.
يمكن للمفكّك تحويل رمز المسافة distance_code إلى مسافة ترتيب خطوط المسح dist على النحو التالي:
(xi, yi) = distance_map[distance_code - 1]
dist = xi + yi * image_width
if (dist < 1) {
dist = 1
}
حيث distance_map هو التعيين المذكور أعلاه، وimage_width هو عرض الصورة بالبكسل.
5.2.3 ترميز ذاكرة التخزين المؤقت للألوان
تخزّن ذاكرة التخزين المؤقت للألوان مجموعة من الألوان التي تم استخدامها مؤخرًا في الصورة.
السبب: بهذه الطريقة، يمكن في بعض الأحيان الرجوع إلى الألوان المستخدَمة مؤخرًا بشكل أكثر فعالية من عرضها باستخدام الطريقتين الأخريين (الموضّحتين في 5.2.1 و5.2.2).
يتم تخزين رموز ذاكرة التخزين المؤقت للألوان على النحو التالي. أولاً، هناك قيمة ذات بت واحد تشير إلى ما إذا كان يتم استخدام ذاكرة التخزين المؤقت للألوان. إذا كانت قيمة هذه البت 0، لن تتوفّر رموز ذاكرة التخزين المؤقت للألوان، ولن يتم إرسالها في رمز البادئة الذي يفك تشفير الرموز الخضراء ورموز بادئة الطول. ومع ذلك، إذا كانت قيمة هذا الجزء 1، يتم قراءة حجم ذاكرة التخزين المؤقت للألوان بعد ذلك:
int color_cache_code_bits = ReadBits(4);
int color_cache_size = 1 << color_cache_code_bits;
تحدّد color_cache_code_bits حجم ذاكرة التخزين المؤقت للألوان (1 <<
color_cache_code_bits). ويتراوح نطاق القيم المسموح بها لـ color_cache_code_bits بين [1 و11]. يجب أن تشير أدوات فك الترميز المتوافقة إلى
تدفّق بتات تالف للقيم الأخرى.
ذاكرة التخزين المؤقت للألوان هي مصفوفة بحجم color_cache_size. يخزّن كل إدخال لون ARGB واحدًا. يتم البحث عن الألوان من خلال فهرسة (0x1e35a7bd * color) >> (32 -
color_cache_code_bits). يتم إجراء عملية بحث واحدة فقط في ذاكرة التخزين المؤقت للألوان، ولا يتم حل أي تعارض.
في بداية فك ترميز صورة أو ترميزها، يتم ضبط جميع الإدخالات في جميع قيم ذاكرة التخزين المؤقت للألوان على صفر. يتم تحويل رمز ذاكرة التخزين المؤقت للألوان إلى هذا اللون في وقت فك الترميز. يتم الحفاظ على حالة ذاكرة التخزين المؤقت للألوان من خلال إدراج كل بكسل، سواء تم إنتاجه من خلال الإشارة إلى الخلف أو كقيم حرفية، في ذاكرة التخزين المؤقت بالترتيب الذي تظهر به في البث.
6 Entropy Code
6.1 نظرة عامة
يتم ترميز معظم البيانات باستخدام رمز بادئة أساسي. وبالتالي، يتم نقل الرموز عن طريق إرسال أطوال رموز البادئة، بدلاً من رموز البادئة الفعلية.
على وجه الخصوص، يستخدم التنسيق ترميز البادئة المتغيّر مكانيًا. بعبارة أخرى، يمكن أن تستخدم أجزاء مختلفة من الصورة رموز إنتروبيا مختلفة.
السبب: قد تختلف خصائص المناطق المختلفة في الصورة. لذلك، يتيح السماح لهم باستخدام رموز إنتروبيا مختلفة المزيد من المرونة وربما تحسينًا في مستوى الضغط.
6.2 التفاصيل
تتألف بيانات الصورة المشفرة من عدة أجزاء:
- فك ترميز رموز البادئة وإنشاؤها
- رموز البادئة الوصفية
- بيانات الصور المرمّزة بالإنتروبيا
لكل بكسل معيّن (x, y)، هناك مجموعة من خمسة رموز بادئة مرتبطة به. الرموز هي (حسب ترتيب دفق البتات):
- رمز البادئة رقم 1: يُستخدم للقناة الخضراء وطول المرجع الخلفي وذاكرة التخزين المؤقت للألوان.
- رمز البادئة 2 و3 و4: يُستخدم للقنوات الحمراء والزرقاء وقناة ألفا، على التوالي.
- الرمز البادئ رقم 5: يُستخدَم لتحديد مسافة المرجع الخلفي.
من الآن فصاعدًا، سنشير إلى هذه المجموعة باسم مجموعة رموز البادئة.
6.2.1 فك تشفير رموز البادئة وإنشاؤها
يوضّح هذا القسم كيفية قراءة أطوال رمز البادئة من دفق البتات.
يمكن ترميز أطوال رموز البادئة بطريقتَين. يتم تحديد الطريقة المستخدَمة بواسطة قيمة مكوّنة من بت واحد.
- إذا كانت هذه الوحدة 1، يكون رمز طول بسيط.
- إذا كانت هذه البت 0، يكون رمز طول عادي.
في كلتا الحالتين، يمكن أن تكون هناك أطوال رموز غير مستخدَمة لا تزال جزءًا من البث. قد يكون هذا الإجراء غير فعّال، ولكن يسمح به التنسيق. يجب أن تكون الشجرة الموصوفة شجرة ثنائية كاملة. يُعدّ عنصر ورقة واحد شجرة ثنائية كاملة ويمكن ترميزه باستخدام رمز طول الرمز البسيط أو رمز طول الرمز العادي. عند ترميز عقدة ورقة واحدة باستخدام رمز طول الرمز العادي، تكون جميع أطوال الرموز باستثناء رمز واحد أصفارًا، ويتم وضع علامة على قيمة عقدة الورقة الواحدة بطول 1، حتى عندما لا يتم استهلاك أي وحدات بت عند استخدام شجرة عقدة الورقة الواحدة هذه.
رمز طول الرمز البسيط
يُستخدم هذا النوع في الحالة الخاصة التي يتوفّر فيها رمز بادئة واحد أو رمزان فقط في النطاق [0..255] مع طول الرمز 1. تكون جميع أطوال رموز البادئة الأخرى أصفارًا ضمنيًا.
يشير البت الأول إلى عدد الرموز:
int num_symbols = ReadBits(1) + 1;
في ما يلي قيم الرموز.
يتم ترميز الرمز الأول باستخدام بت واحد أو 8 بتات، وذلك حسب قيمة is_first_8bits. النطاق هو [0..1] أو [0..255] على التوالي. يُفترض دائمًا أنّ الرمز الثاني، إذا كان متوفّرًا، يقع في النطاق [0..255] ويتم ترميزه باستخدام 8 بت.
int is_first_8bits = ReadBits(1);
symbol0 = ReadBits(1 + 7 * is_first_8bits);
code_lengths[symbol0] = 1;
if (num_symbols == 2) {
symbol1 = ReadBits(8);
code_lengths[symbol1] = 1;
}
يجب أن يكون الرمزان مختلفَين. يُسمح باستخدام الرموز المكرّرة، ولكنها غير فعّالة.
ملاحظة: هناك حالة خاصة أخرى وهي عندما تكون أطوال رموز البادئة كلها أصفارًا (رمز بادئة فارغ). على سبيل المثال، يمكن أن يكون رمز البادئة الخاص بالمسافة فارغًا إذا لم تكن هناك مراجع للخلف. وبالمثل، يمكن أن تكون رموز البادئة الخاصة بقنوات ألفا والأحمر والأزرق فارغة إذا تم إنتاج جميع وحدات البكسل ضمن رمز بادئة البيانات الوصفية نفسه باستخدام ذاكرة التخزين المؤقت للألوان. ومع ذلك، لا تتطلّب هذه الحالة معالجة خاصة، لأنّه يمكن ترميز رموز البادئة الفارغة على أنّها تلك التي تحتوي على رمز واحد 0.
رمز طول الرمز العادي
تتلاءم أطوال رموز البادئة مع 8 بتات ويتم قراءتها على النحو التالي.
أولاً، يحدّد num_code_lengths عدد أطوال الرموز.
int num_code_lengths = 4 + ReadBits(4);
يتم تشفير أطوال الرموز نفسها باستخدام رموز البادئة، ويجب أولاً قراءة أطوال الرموز ذات المستوى الأدنى، code_length_code_lengths. بقية الأرقام في code_length_code_lengths (وفقًا للترتيب في kCodeLengthCodeOrder) هي أصفار.
int kCodeLengthCodes = 19;
int kCodeLengthCodeOrder[kCodeLengthCodes] = {
17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
};
int code_length_code_lengths[kCodeLengthCodes] = { 0 }; // All zeros
for (i = 0; i < num_code_lengths; ++i) {
code_length_code_lengths[kCodeLengthCodeOrder[i]] = ReadBits(3);
}
بعد ذلك، إذا كان ReadBits(1) == 0، يتم ضبط الحد الأقصى لعدد رموز القراءة المختلفة
(max_symbol) لكل نوع من الرموز (A وR وG وB والمسافة) على حجم الأبجدية:
- القناة G: 256 + 24 +
color_cache_size - الأحرف الحرفية الأخرى (A وR وB): 256
- رمز المسافة: 40
في ما عدا ذلك، يتم تعريفها على النحو التالي:
int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);
إذا كانت قيمة max_symbol أكبر من حجم الأبجدية لنوع الرمز، يكون
دفق البت غير صالح.
بعد ذلك، يتم إنشاء جدول بادئات من code_length_code_lengths ويُستخدم لقراءة ما يصل إلى أطوال الرموز max_symbol.
- يشير الرمز [0..15] إلى أطوال الرموز الحرفية.
- تعني القيمة 0 أنّه لم يتم ترميز أي رموز.
- تشير القيم [1..15] إلى طول البت للرمز المعنيّ.
- يكرّر الرمز 16 القيمة السابقة غير الصفرية [3..6] مرات، أي
3 + ReadBits(2)مرات. إذا تم استخدام الرمز 16 قبل إصدار قيمة غير صفرية، سيتم تكرار القيمة 8. - ينتج الرمز 17 سلسلة من الأصفار بطول [3..10]، أي
3 + ReadBits(3)مرة. - يُصدر الرمز 18 سلسلة من الأصفار بطول [11..138]، أي
11 + ReadBits(7)مرة.
بعد قراءة أطوال الرموز، يتم إنشاء رمز بادئة لكل نوع من الرموز (A وR وG وB والمسافة) باستخدام أحجام الأبجدية الخاصة بكل منها.
يجب أن يرمز رمز طول الرمز العادي إلى شجرة قرار كاملة، أي يجب أن يكون مجموع
2 ^ (-length) لجميع الرموز غير الصفرية واحدًا بالضبط. ومع ذلك، هناك استثناء واحد لهذه القاعدة، وهو شجرة عقدة الورقة الفردية، حيث يتم وضع علامة 1 على قيمة عقدة الورقة، بينما تكون القيم الأخرى أصفارًا.
6.2.2 فك ترميز رموز البادئة الوصفية
كما ذكرنا سابقًا، يتيح التنسيق استخدام رموز بادئة مختلفة لأجزاء مختلفة من الصورة. رموز البادئة الوصفية هي فهارس تحدّد رموز البادئة التي يجب استخدامها في أجزاء مختلفة من الصورة.
يمكن استخدام رموز البادئة الوصفية فقط عندما يتم استخدام الصورة في دور صورة ARGB.
هناك احتمالان لرموز البادئة الوصفية، ويتم تحديدهما من خلال قيمة ذات بت واحد:
- إذا كانت هذه البتة صفرًا، لن يكون هناك سوى رمز بادئة وصفية واحد مستخدَم في كل مكان في الصورة. ولن يتم تخزين المزيد من البيانات.
- إذا كانت قيمة هذا الجزء هي 1، تستخدم الصورة رموز بادئة بيانات وصفية متعددة. يتم تخزين رموز البادئة الوصفية هذه كـ صورة إنتروبيا (موضّحة أدناه).
تحدّد مكوّنات الأحمر والأخضر في البكسل رمز بادئة بيانات وصفية يبلغ 16 بت ويُستخدم في جزء معيّن من صورة ARGB.
صورة الإنتروبيا
تحدّد صورة الإنتروبيا رموز البادئة المستخدَمة في أجزاء مختلفة من الصورة.
تحتوي الأجزاء الثلاثة الأولى على قيمة prefix_bits. يتم استخلاص أبعاد صورة الإنتروبيا من prefix_bits:
int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
DIV_ROUND_UP(image_height, 1 << prefix_bits);
حيث DIV_ROUND_UP هو كما تم تعريفه سابقًا.
تحتوي الأجزاء التالية على صورة إنتروبيا بعرض prefix_image_width وارتفاع prefix_image_height.
تفسير رموز البادئة الوصفية
يمكن الحصول على عدد مجموعات رموز البادئة في صورة ARGB من خلال العثور على أكبر رمز بادئة وصفية من صورة الإنتروبيا:
int num_prefix_groups = max(entropy image) + 1;
حيث يشير max(entropy image) إلى أكبر رمز بادئة مخزَّن في صورة الإنتروبيا.
بما أنّ كل مجموعة رموز بادئة تحتوي على خمسة رموز بادئة، فإنّ العدد الإجمالي لرموز البادئة هو:
int num_prefix_codes = 5 * num_prefix_groups;
بافتراض وجود بكسل (x, y) في صورة ARGB، يمكننا الحصول على رموز البادئة المقابلة لاستخدامها على النحو التالي:
int position =
(y >> prefix_bits) * prefix_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];
حيث افترضنا وجود بنية PrefixCodeGroup تمثّل مجموعة من خمسة رموز بادئة. بالإضافة إلى ذلك، prefix_code_groups هي مصفوفة من PrefixCodeGroup (بحجم num_prefix_groups).
تستخدم أداة فك الترميز بعد ذلك مجموعة رموز البادئة prefix_group لفك ترميز البكسل (x, y)، كما هو موضّح في "فك ترميز بيانات الصور المرمّزة باستخدام إنتروبيا".
6.2.3 فك ترميز بيانات الصور المرمّزة باستخدام الإنتروبيا
بالنسبة إلى الموضع الحالي (x, y) في الصورة، يحدّد برنامج الترميز أولاً مجموعة رموز البادئة المناسبة (كما هو موضّح في القسم الأخير). بالنظر إلى مجموعة رموز البادئة، تتم قراءة البكسل وفك ترميزه على النحو التالي.
بعد ذلك، اقرأ الرمز S من دفق البتات باستخدام رمز البادئة رقم 1. يُرجى العِلم أنّ S هو أي عدد صحيح في النطاق من 0 إلى (256 + 24 + color_cache_size- 1).
يعتمد تفسير S على قيمته:
- إذا كانت قيمة S أقل من 256
- استخدِم الحرف S كمكوّن أخضر.
- قراءة اللون الأحمر من دفق البتات باستخدام رمز البادئة رقم 2
- قراءة اللون الأزرق من دفق البتات باستخدام رمز البادئة رقم 3
- قراءة قيمة ألفا من دفق البتات باستخدام رمز البادئة رقم 4
- إذا كان S >= 256 وS < 256 + 24
- استخدِم S - 256 كرمز بادئة الطول.
- قراءة وحدات بت إضافية للطول من دفق البتات
- تحديد طول المرجع الخلفي L من رمز بادئة الطول وعدد البتات الإضافية التي تم قراءتها
- اقرأ رمز بادئة المسافة من دفق البتات باستخدام رمز البادئة رقم 5.
- قراءة وحدات بت إضافية للمسافة من دفق البتات
- حدِّد المسافة D المرجعية السابقة من رمز بادئة المسافة والبتات الإضافية التي تمّت قراءتها.
- نسخ L بكسل (بالترتيب حسب خطوط المسح) من تسلسل البكسلات بدءًا من الموضع الحالي ناقص D بكسل
- If S >= 256 + 24
- استخدِم S - (256 + 24) كفهرس في ذاكرة التخزين المؤقت للألوان.
- الحصول على لون ARGB من ذاكرة التخزين المؤقت للألوان في هذا الفهرس
7 البنية العامة للتنسيق
في ما يلي عرض للتنسيق في "صيغة باكوس ناور المعززة" (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