مشخصات برای WebP Lossless Bitstream

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

چکیده

فرمت فشرده‌سازی بدون اتلاف WebP یک فرمت تصویری برای فشرده‌سازی بدون اتلاف تصاویر ARGB است. این فرمت بدون اتلاف، مقادیر پیکسل‌ها، از جمله مقادیر رنگ برای پیکسل‌های کاملاً شفاف را دقیقاً ذخیره و بازیابی می‌کند. یک الگوریتم جهانی برای فشرده‌سازی متوالی داده‌ها (LZ77)، کدگذاری پیشوندی و یک حافظه پنهان رنگ برای فشرده‌سازی داده‌های حجیم استفاده می‌شوند. سرعت رمزگشایی سریع‌تر از PNG و همچنین فشرده‌سازی ۲۵٪ متراکم‌تر از آنچه می‌توان با استفاده از فرمت PNG امروزی به دست آورد، نشان داده شده است.

۱ مقدمه

این سند، نمایش داده‌های فشرده‌شده از یک تصویر WebP بدون اتلاف را شرح می‌دهد. این سند به عنوان مرجعی دقیق برای پیاده‌سازی رمزگذار و رمزگشای WebP بدون اتلاف در نظر گرفته شده است.

در این سند، ما به طور گسترده از نحو زبان برنامه‌نویسی C برای توصیف جریان بیتی استفاده می‌کنیم و وجود تابعی برای خواندن بیت‌ها، ReadBits(n) را فرض می‌کنیم. بایت‌ها به ترتیب طبیعی جریان حاوی آنها خوانده می‌شوند و بیت‌های هر بایت به ترتیب بیت اول با کمترین اهمیت خوانده می‌شوند. هنگامی که چندین بیت به طور همزمان خوانده می‌شوند، عدد صحیح از داده‌های اصلی به ترتیب اصلی ساخته می‌شود. باارزش‌ترین بیت‌های عدد صحیح برگردانده شده، باارزش‌ترین بیت‌های داده‌های اصلی نیز هستند. بنابراین، عبارت

b = ReadBits(2);

با دو عبارت زیر معادل است:

b = ReadBits(1);
b |= ReadBits(1) << 1;

ما فرض می‌کنیم که هر جزء رنگ، یعنی آلفا، قرمز، آبی و سبز، با استفاده از یک بایت ۸ بیتی نمایش داده می‌شود. ما نوع مربوطه را uint8 تعریف می‌کنیم. یک پیکسل کامل ARGB توسط نوعی به نام uint32 نمایش داده می‌شود که یک عدد صحیح بدون علامت متشکل از ۳۲ بیت است. در کدی که رفتار تبدیل‌ها را نشان می‌دهد، این مقادیر در بیت‌های زیر کدگذاری شده‌اند: آلفا در بیت‌های ۳۱ تا ۲۴، قرمز در بیت‌های ۲۳ تا ۱۶، سبز در بیت‌های ۱۵ تا ۸ و آبی در بیت‌های ۷ تا ۰؛ با این حال، پیاده‌سازی‌های این فرمت می‌توانند از نمایش دیگری به صورت داخلی استفاده کنند.

به طور کلی، یک تصویر WebP بدون اتلاف شامل داده‌های هدر، اطلاعات تبدیل و داده‌های واقعی تصویر است. هدرها شامل عرض و ارتفاع تصویر هستند. یک تصویر WebP بدون اتلاف می‌تواند قبل از کدگذاری آنتروپی، چهار نوع تبدیل مختلف را طی کند. اطلاعات تبدیل در جریان بیت شامل داده‌های مورد نیاز برای اعمال تبدیل‌های معکوس مربوطه است.

۲ فهرست اصطلاحات

آر جی بی

یک مقدار پیکسلی شامل مقادیر آلفا، قرمز، سبز و آبی.

تصویر ARGB

یک آرایه دو بعدی شامل پیکسل‌های ARGB.

حافظه پنهان رنگ

یک آرایه کوچک با آدرس‌دهی هش‌شده برای ذخیره رنگ‌های اخیراً استفاده‌شده تا بتوان آن‌ها را با کدهای کوتاه‌تر فراخوانی کرد.

تصویر نمایه سازی رنگ

تصویری تک‌بعدی از رنگ‌ها که می‌تواند با استفاده از یک عدد صحیح کوچک (تا ۲۵۶ در قالب WebP بدون افت کیفیت) فهرست‌بندی شود.

تصویر تبدیل رنگ

یک تصویر دوبعدی با وضوح کمتر که حاوی داده‌هایی در مورد همبستگی اجزای رنگ است.

نقشه برداری از فاصله

فواصل LZ77 را طوری تغییر می‌دهد که کمترین مقادیر را برای پیکسل‌ها در مجاورت دوبعدی داشته باشد.

تصویر آنتروپی

یک تصویر دوبعدی با وضوح کمتر که نشان می‌دهد کدام کدگذاری آنتروپی باید در یک مربع مربوطه در تصویر استفاده شود، یعنی هر پیکسل یک کد پیشوند متا است.

LZ77

یک الگوریتم فشرده‌سازی پنجره کشویی مبتنی بر دیکشنری که یا نمادها را منتشر می‌کند یا آنها را به عنوان دنباله‌هایی از نمادهای گذشته توصیف می‌کند.

کد پیشوند متا

یک عدد صحیح کوچک (تا ۱۶ بیت) که یک عنصر را در جدول پیشوند متا اندیس‌گذاری می‌کند.

تصویر پیش‌بینی‌کننده

یک تصویر دوبعدی با وضوح کمتر که نشان می‌دهد کدام پیش‌بینی‌کننده مکانی برای یک مربع خاص در تصویر استفاده شده است.

کد پیشوند

یک روش کلاسیک برای انجام کدگذاری آنتروپی که در آن تعداد بیت‌های کمتری برای کدهای مکرر استفاده می‌شود.

کدگذاری پیشوندی

روشی برای کدگذاری آنتروپی اعداد صحیح بزرگتر، که چند بیت از عدد صحیح را با استفاده از یک کد آنتروپی کدگذاری می‌کند و بیت‌های باقی‌مانده را به صورت خام کدگذاری می‌کند. این امر باعث می‌شود که توصیف کدهای آنتروپی حتی زمانی که محدوده نمادها بزرگ است، نسبتاً کوچک باقی بماند.

ترتیب اسکن خطی

ترتیب پردازش پیکسل‌ها (از چپ به راست و از بالا به پایین)، که از پیکسل بالا سمت چپ شروع می‌شود. پس از تکمیل یک ردیف، از ستون سمت چپ ردیف بعدی ادامه دهید.

۳ سربرگ RIFF

ابتدای هدر شامل ظرف RIFF است که شامل ۲۱ بایت زیر است:

1. رشته 'RIFF'.
2. یک مقدار ۳۲ بیتی با روش little-endian برای طول قطعه داده، که برابر با کل اندازه قطعه داده است که توسط سرآیند RIFF کنترل می‌شود. معمولاً این مقدار برابر با اندازه بار داده (اندازه فایل منهای ۸ بایت: ۴ بایت برای شناسه «RIFF» و ۴ بایت برای ذخیره خود مقدار) است.
3. رشته 'WEBP' (نام کانتینر RIFF).
4. رشته 'VP8L' (FourCC برای داده‌های تصویر رمزگذاری شده بدون اتلاف).
5. یک مقدار ۳۲ بیتی Little-endian از تعداد بایت‌های موجود در جریان داده‌ی بدون اتلاف.
6. امضای ۱ بایتی 0x2f.

۲۸ بیت اول جریان بیت، عرض و ارتفاع تصویر را مشخص می‌کنند. عرض و ارتفاع به صورت اعداد صحیح ۱۴ بیتی به صورت زیر رمزگشایی می‌شوند:

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

دقت ۱۴ بیتی برای عرض و ارتفاع تصویر، حداکثر اندازه یک تصویر WebP بدون افت کیفیت را به ۱۶۳۸۴ در ۱۶۳۸۴ پیکسل محدود می‌کند.

بیت alpha_is_used فقط یک راهنما است و نباید روی رمزگشایی تأثیر بگذارد. وقتی همه مقادیر آلفا در تصویر ۲۵۵ هستند، باید روی ۰ و در غیر این صورت روی ۱ تنظیم شود.

int alpha_is_used = ReadBits(1);

عدد_نسخه یک کد ۳ بیتی است که باید روی ۰ تنظیم شود. هر مقدار دیگری باید به عنوان خطا در نظر گرفته شود.

int version_number = ReadBits(3);

۴ تبدیل

این تبدیل‌ها، دستکاری‌های برگشت‌پذیر داده‌های تصویر هستند که می‌توانند با مدل‌سازی همبستگی‌های مکانی و رنگی، آنتروپی نمادین باقی‌مانده را کاهش دهند. آن‌ها می‌توانند فشرده‌سازی نهایی را متراکم‌تر کنند.

یک تصویر می‌تواند از چهار نوع تبدیل عبور کند. بیت ۱ نشان‌دهنده وجود یک تبدیل است. هر تبدیل فقط یک بار مجاز به استفاده است. تبدیل‌ها فقط برای تصویر ARGB سطح اصلی استفاده می‌شوند؛ تصاویر با وضوح کمتر (تصویر تبدیل رنگ، تصویر آنتروپی و تصویر پیش‌بینی‌کننده) هیچ تبدیلی ندارند، حتی بیت ۰ که نشان‌دهنده پایان تبدیل‌ها است.

معمولاً، یک انکودر از این تبدیل‌ها برای کاهش آنتروپی شانون در تصویر باقیمانده استفاده می‌کند. همچنین، داده‌های تبدیل را می‌توان بر اساس کمینه‌سازی آنتروپی تعیین کرد.

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

پس از نوع تبدیل، داده تبدیل قرار می‌گیرد. داده‌های تبدیل شامل اطلاعات مورد نیاز برای اعمال تبدیل معکوس هستند و به نوع تبدیل بستگی دارند. تبدیل‌های معکوس به ترتیب معکوسی که از جریان بیت خوانده می‌شوند، اعمال می‌شوند، یعنی آخرین تبدیل اول انجام می‌شود.

در ادامه، داده‌های تبدیل را برای انواع مختلف شرح می‌دهیم.

۴.۱ تبدیل پیش‌بینی‌کننده

تبدیل پیش‌بینی‌کننده می‌تواند با بهره‌گیری از این واقعیت که پیکسل‌های همسایه اغلب با هم هم‌بسته هستند، برای کاهش آنتروپی استفاده شود. در تبدیل پیش‌بینی‌کننده، مقدار پیکسل فعلی از پیکسل‌هایی که قبلاً رمزگشایی شده‌اند (به ترتیب خط اسکن) پیش‌بینی می‌شود و فقط مقدار باقیمانده (واقعی - پیش‌بینی‌شده) کدگذاری می‌شود. مؤلفه سبز یک پیکسل مشخص می‌کند که کدام یک از ۱۴ پیش‌بینی‌کننده در یک بلوک خاص از تصویر 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);

داده‌های تبدیل شامل حالت پیش‌بینی برای هر بلوک از تصویر است. این یک تصویر با وضوح کمتر است که در آن مؤلفه سبز یک پیکسل، مشخص می‌کند کدام یک از ۱۴ پیش‌بینی‌کننده برای تمام پیکسل‌های block_width * block_height در یک بلوک خاص از تصویر ARGB استفاده شود. این تصویر با وضوح کمتر با استفاده از همان تکنیک‌های شرح داده شده در فصل ۵ کدگذاری می‌شود.

تعداد ستون‌های بلوک، transform_width ، در اندیس‌گذاری دوبعدی استفاده می‌شود. برای یک پیکسل (x, y)، می‌توان آدرس بلوک فیلتر مربوطه را به صورت زیر محاسبه کرد:

int block_index = (y >> size_bits) * transform_width +
                  (x >> size_bits);

۱۴ حالت پیش‌بینی مختلف وجود دارد. در هر حالت پیش‌بینی، مقدار پیکسل فعلی از یک یا چند پیکسل همسایه که مقادیر آنها از قبل مشخص است، پیش‌بینی می‌شود.

ما پیکسل‌های همسایه (TL، T، TR و L) پیکسل فعلی (P) را به صورت زیر انتخاب کردیم:

O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    O    O    O    O    O    O    O
O    O    O    O    TL   T    TR   O    O    O    O
O    O    O    O    L    P    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X
X    X    X    X    X    X    X    X    X    X    X

که در آن TL به معنی بالا-چپ، T به معنی بالا، TR به معنی بالا-راست و L به معنی چپ است. در زمان پیش‌بینی مقدار برای P، تمام پیکسل‌های O، TL، T، TR و L قبلاً پردازش شده‌اند و پیکسل P و تمام پیکسل‌های X ناشناخته هستند.

با توجه به پیکسل‌های همسایه قبلی، حالت‌های پیش‌بینی مختلف به شرح زیر تعریف می‌شوند.

Average2 برای هر جزء ARGB به صورت زیر تعریف می‌شود:

uint8 Average2(uint8 a, uint8 b) {
  return (a + b) / 2;
}

پیش بینی کننده 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);
}

۴.۲ تبدیل رنگ

هدف از تبدیل رنگ، نامرتبط کردن مقادیر 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 با استفاده از یک عدد صحیح ۸ بیتی علامت‌دار که نشان‌دهنده یک عدد با ممیز ثابت ۳.۵ است و یک کانال رنگ 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 تبدیل شده آن نگاشت می‌شود).

ضرب باید با دقت بیشتری (با حداقل دقت ۱۶ بیتی) انجام شود. خاصیت بسط علامت عملیات شیفت در اینجا اهمیتی ندارد؛ فقط ۸ بیت پایین از نتیجه استفاده می‌شوند و در این بیت‌ها، شیفت بسط علامت و شیفت بدون علامت با یکدیگر سازگار هستند.

حال، محتویات داده‌های تبدیل رنگ را توصیف می‌کنیم تا رمزگشایی بتواند تبدیل رنگ معکوس را اعمال کرده و مقادیر اصلی قرمز و آبی را بازیابی کند. 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;
}

۴.۳ تبدیل تفریق سبز

تبدیل تفریق سبز، مقادیر سبز را از مقادیر قرمز و آبی هر پیکسل کم می‌کند. وقتی این تبدیل وجود دارد، رمزگشا باید مقدار سبز را به هر دو مقدار قرمز و آبی اضافه کند. هیچ داده‌ای مرتبط با این تبدیل وجود ندارد. رمزگشا تبدیل معکوس را به شرح زیر اعمال می‌کند:

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

این تبدیل زائد است، زیرا می‌توان آن را با استفاده از تبدیل رنگ مدل‌سازی کرد، اما از آنجایی که هیچ داده اضافی در اینجا وجود ندارد، تبدیل سبز تفریق را می‌توان با استفاده از بیت‌های کمتری نسبت به یک تبدیل رنگ کامل کدگذاری کرد.

۴.۴ تبدیل نمایه‌سازی رنگ

اگر مقادیر پیکسل‌های منحصر به فرد زیادی وجود نداشته باشد، ممکن است ایجاد یک آرایه شاخص رنگ و جایگزینی مقادیر پیکسل با شاخص‌های آرایه، کارآمدتر باشد. تبدیل شاخص رنگ این کار را انجام می‌دهد. (در زمینه WebP بدون اتلاف، ما به طور خاص این را تبدیل پالت نمی‌نامیم زیرا یک مفهوم مشابه اما پویاتر در رمزگذاری بدون اتلاف WebP وجود دارد: حافظه پنهان رنگ.)

تبدیل شاخص‌گذاری رنگ، تعداد مقادیر ARGB منحصر به فرد در تصویر را بررسی می‌کند. اگر این عدد کمتر از یک آستانه (۲۵۶) باشد، آرایه‌ای از آن مقادیر ARGB ایجاد می‌کند که سپس برای جایگزینی مقادیر پیکسل با شاخص مربوطه استفاده می‌شود: کانال سبز پیکسل‌ها با شاخص جایگزین می‌شوند، تمام مقادیر آلفا روی ۲۵۵ و تمام مقادیر قرمز و آبی روی ۰ تنظیم می‌شوند.

داده‌های تبدیل شامل اندازه جدول رنگ و ورودی‌های جدول رنگ است. رمزگشا داده‌های تبدیل اندیس‌گذاری رنگ را به صورت زیر می‌خواند:

// 8-bit value for the color table size
int color_table_size = ReadBits(8) + 1;

جدول رنگ با استفاده از خود قالب ذخیره‌سازی تصویر ذخیره می‌شود. جدول رنگ را می‌توان با خواندن یک تصویر، بدون هدر RIFF، اندازه تصویر و تبدیل‌ها، با فرض ارتفاع ۱ پیکسل و عرض color_table_size ، به دست آورد. جدول رنگ همیشه برای کاهش آنتروپی تصویر، با روش تفریق کدگذاری می‌شود. دلتاهای رنگ‌های پالت معمولاً حاوی آنتروپی بسیار کمتری نسبت به خود رنگ‌ها هستند که منجر به صرفه‌جویی قابل توجهی برای تصاویر کوچک‌تر می‌شود. در رمزگشایی، هر رنگ نهایی در جدول رنگ را می‌توان با جمع کردن مقادیر مؤلفه رنگ قبلی توسط هر مؤلفه ARGB به طور جداگانه و ذخیره ۸ بیت کم‌اهمیت‌تر از نتیجه به دست آورد.

تبدیل معکوس برای تصویر، به سادگی جایگزین کردن مقادیر پیکسل (که شاخص‌های جدول رنگ هستند) با مقادیر واقعی جدول رنگ است. این شاخص‌گذاری بر اساس مؤلفه سبز رنگ ARGB انجام می‌شود.

// Inverse transform
argb = color_table[GREEN(argb)];

اگر ایندکس برابر یا بزرگتر از color_table_size باشد، مقدار رنگ argb باید روی 0x00000000 (مشکی شفاف) تنظیم شود.

وقتی جدول رنگ کوچک باشد (برابر یا کمتر از ۱۶ رنگ)، چندین پیکسل در یک پیکسل واحد قرار می‌گیرند. بسته‌بندی پیکسل، چندین (۲، ۴ یا ۸) پیکسل را در یک پیکسل واحد قرار می‌دهد و به ترتیب عرض تصویر را کاهش می‌دهد. بسته‌بندی پیکسل امکان کدگذاری آنتروپی توزیع مشترک کارآمدتر پیکسل‌های همسایه را فراهم می‌کند و مزایایی شبیه کدگذاری حسابی به کد آنتروپی می‌دهد، اما فقط زمانی می‌توان از آن استفاده کرد که ۱۶ مقدار منحصر به فرد یا کمتر وجود داشته باشد.

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 می‌تواند مقادیر ۰، ۱، ۲ یا ۳ را داشته باشد. مقدار ۰ نشان می‌دهد که هیچ دسته‌بندی پیکسلی برای تصویر انجام نمی‌شود. مقدار ۱ نشان می‌دهد که دو پیکسل با هم ترکیب شده‌اند و هر پیکسل دارای محدوده [۰..۱۵] است. مقدار ۲ نشان می‌دهد که چهار پیکسل با هم ترکیب شده‌اند و هر پیکسل دارای محدوده [۰..۳] است. مقدار ۳ نشان می‌دهد که هشت پیکسل با هم ترکیب شده‌اند و هر پیکسل دارای محدوده [۰..۱] است، یعنی یک مقدار دودویی.

مقادیر به صورت زیر در مولفه سبز قرار می‌گیرند:

• width_bits = 1: برای هر مقدار x، که در آن x ≡ 0 (به پیمانه 2)، یک مقدار سبز در x در 4 بیت کم‌ارزش‌تر از مقدار سبز در x/2 قرار می‌گیرد، و یک مقدار سبز در x+1 در 4 بیت پرارزش‌تر از مقدار سبز در x/2 قرار می‌گیرد.
• width_bits = 2: برای هر مقدار x، که در آن x ≡ 0 (به پیمانه 4)، یک مقدار سبز در x در 2 بیت کم‌ارزش‌تر مقدار سبز در x/4 قرار می‌گیرد، و مقادیر سبز در x+1 تا x+3 به ترتیب در بیت‌های پرارزش‌تر مقدار سبز در x/4 قرار می‌گیرند.
• width_bits = 3: برای هر مقدار x، که در آن x ≡ 0 (به پیمانه 8)، یک مقدار سبز در x در بیت کم‌ارزش‌ترین مقدار سبز در x/8 قرار می‌گیرد، و مقادیر سبز در x+1 تا x+7 به ترتیب در بیت‌های پرارزش‌تر مقدار سبز در x/8 قرار می‌گیرند.

پس از خواندن این تبدیل، image_width توسط width_bits نمونه‌برداری می‌شود. این بر اندازه تبدیل‌های بعدی تأثیر می‌گذارد. اندازه جدید را می‌توان با استفاده از DIV_ROUND_UP ، همانطور که قبلاً تعریف شده است، محاسبه کرد.

image_width = DIV_ROUND_UP(image_width, 1 << width_bits);

۵ داده‌های تصویر

داده‌های تصویر، آرایه‌ای از مقادیر پیکسلی به ترتیب خط اسکن هستند.

۵.۱ نقش داده‌های تصویر

ما از داده‌های تصویری در پنج نقش مختلف استفاده می‌کنیم:

1. تصویر ARGB: پیکسل‌های واقعی تصویر را ذخیره می‌کند.
2. تصویر آنتروپی: کدهای پیشوند متا را ذخیره می‌کند (به «رمزگشایی کدهای پیشوند متا» مراجعه کنید).
3. تصویر پیش‌بینی‌کننده: فراداده‌های مربوط به تبدیل پیش‌بینی‌کننده را ذخیره می‌کند (به «تبدیل پیش‌بینی‌کننده» مراجعه کنید).
4. تصویر تبدیل رنگ: توسط مقادیر ColorTransformElement (تعریف شده در "تبدیل رنگ" ) برای بلوک‌های مختلف تصویر ایجاد می‌شود.
5. تصویر با نمایه‌سازی رنگ: آرایه‌ای به اندازه color_table_size (تا ۲۵۶ مقدار ARGB) که فراداده‌های مربوط به تبدیل نمایه‌سازی رنگ را ذخیره می‌کند (به «تبدیل نمایه‌سازی رنگ» مراجعه کنید).

۵.۲ رمزگذاری داده‌های تصویر

رمزگذاری داده‌های تصویر مستقل از نقش آن است.

تصویر ابتدا به مجموعه‌ای از بلوک‌های با اندازه ثابت (معمولاً بلوک‌های ۱۶x۱۶) تقسیم می‌شود. هر یک از این بلوک‌ها با استفاده از کدهای آنتروپی مخصوص به خود مدل‌سازی می‌شوند. همچنین، چندین بلوک ممکن است کدهای آنتروپی یکسانی داشته باشند.

منطق: ذخیره یک کد آنتروپی هزینه دارد. اگر بلوک‌های از نظر آماری مشابه، یک کد آنتروپی مشترک داشته باشند، می‌توان این هزینه را به حداقل رساند و در نتیجه آن کد را فقط یک بار ذخیره کرد. به عنوان مثال، یک رمزگذار می‌تواند بلوک‌های مشابه را با خوشه‌بندی آنها با استفاده از ویژگی‌های آماری آنها یا با اتصال مکرر یک جفت خوشه تصادفی انتخاب شده، زمانی که مقدار کلی بیت‌های مورد نیاز برای رمزگذاری تصویر را کاهش می‌دهد، پیدا کند.

هر پیکسل با استفاده از یکی از سه روش ممکن کدگذاری می‌شود:

1. لیترال‌های کد شده با پیشوند: هر کانال (سبز، قرمز، آبی و آلفا) به طور مستقل با آنتروپی کد می‌شود.
2. ارجاع معکوس LZ77: دنباله ای از پیکسل ها از جای دیگری در تصویر کپی می شوند.
3. کد حافظه پنهان رنگ: با استفاده از یک کد هش ضربی کوتاه (شاخص حافظه پنهان رنگ) از رنگی که اخیراً دیده شده است.

زیربخش‌های بعدی هر یک از این موارد را به تفصیل شرح می‌دهند.

۵.۲.۱ لیترال‌های کد شده با پیشوند

پیکسل به صورت مقادیر پیشوندی سبز، قرمز، آبی و آلفا (به همین ترتیب) ذخیره می‌شود. برای جزئیات بیشتر به بخش 6.2.3 مراجعه کنید.

۵.۲.۲ مرجع معکوس LZ77

ارجاعات به عقب، تاپل‌هایی از کد طول و فاصله هستند:

• طول نشان می‌دهد که چند پیکسل به ترتیب خط اسکن باید کپی شوند.
• کد فاصله عددی است که موقعیت یک پیکسل قبلاً دیده شده را نشان می‌دهد، پیکسل‌هایی که قرار است از روی آن کپی شوند. نحوه دقیق نگاشت در زیر توضیح داده شده است.

مقادیر طول و فاصله با استفاده از کدگذاری پیشوندی LZ77 ذخیره می‌شوند.

کدگذاری پیشوندی LZ77 مقادیر صحیح بزرگ را به دو بخش تقسیم می‌کند: کد پیشوندی و بیت‌های اضافی . کد پیشوندی با استفاده از یک کد آنتروپی ذخیره می‌شود، در حالی که بیت‌های اضافی به همان صورت (بدون کد آنتروپی) ذخیره می‌شوند.

منطق : این رویکرد، نیاز به فضای ذخیره‌سازی برای کد آنتروپی را کاهش می‌دهد. همچنین، مقادیر بزرگ معمولاً نادر هستند، بنابراین بیت‌های اضافی برای مقادیر بسیار کمی در تصویر استفاده می‌شوند. بنابراین، این رویکرد در کل منجر به فشرده‌سازی بهتری می‌شود.

جدول زیر کدهای پیشوندی و بیت‌های اضافی مورد استفاده برای ذخیره محدوده‌های مختلف مقادیر را نشان می‌دهد.

شبه‌کد برای بدست آوردن مقدار (طول یا فاصله) از کد پیشوندی به شرح زیر است:

if (prefix_code < 4) {
  return prefix_code + 1;
}
int extra_bits = (prefix_code - 2) >> 1;
int offset = (2 + (prefix_code & 1)) << extra_bits;
return offset + ReadBits(extra_bits) + 1;

نقشه برداری از فاصله

همانطور که قبلاً اشاره شد، کد فاصله عددی است که موقعیت یک پیکسل قبلاً دیده شده را نشان می‌دهد، پیکسل‌هایی که قرار است از آن کپی شوند. این زیربخش، نگاشت بین یک کد فاصله و موقعیت یک پیکسل قبلی را تعریف می‌کند.

کدهای فاصله بزرگتر از ۱۲۰ نشان‌دهنده فاصله پیکسلی به ترتیب خط اسکن با انحراف ۱۲۰ هستند.

کدهای کوچکترین فاصله [1..120] خاص هستند و برای همسایگی نزدیک پیکسل فعلی رزرو شده‌اند. این همسایگی شامل 120 پیکسل است:

• پیکسل‌هایی که ۱ تا ۷ ردیف بالاتر از پیکسل فعلی هستند و تا ۸ ستون در سمت چپ یا تا ۷ ستون در سمت راست پیکسل فعلی قرار دارند. [مجموع این پیکسل‌ها = 7 * (8 + 1 + 7) = 112 ].
• پیکسل‌هایی که در همان ردیف پیکسل فعلی هستند و تا ۸ ستون در سمت چپ پیکسل فعلی قرار دارند. [ 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.1 و 5.2.2 توضیح داده شده است) ارجاع داد.

کدهای حافظه پنهان رنگ به صورت زیر ذخیره می‌شوند. ابتدا، یک مقدار ۱ بیتی وجود دارد که نشان می‌دهد آیا از حافظه پنهان رنگ استفاده شده است یا خیر. اگر این بیت ۰ باشد، هیچ کد حافظه پنهان رنگی وجود ندارد و آنها در کد پیشوندی که نمادهای سبز و کدهای پیشوند طول را رمزگشایی می‌کند، ارسال نمی‌شوند. با این حال، اگر این بیت ۱ باشد، اندازه حافظه پنهان رنگ در مرحله بعد خوانده می‌شود:

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) جستجو می‌شوند. فقط یک جستجو در حافظه پنهان رنگ انجام می‌شود؛ هیچ حل تعارضی وجود ندارد.

در ابتدای رمزگشایی یا کدگذاری یک تصویر، تمام ورودی‌ها در تمام مقادیر حافظه پنهان رنگ روی صفر تنظیم می‌شوند. کد حافظه پنهان رنگ در زمان رمزگشایی به این رنگ تبدیل می‌شود. وضعیت حافظه پنهان رنگ با وارد کردن هر پیکسل، چه با ارجاع به عقب و چه به صورت حروف الفبا، به ترتیبی که در جریان ظاهر می‌شوند، در حافظه پنهان حفظ می‌شود.

۶ کد آنتروپی

۶.۱ مرور کلی

بیشتر داده‌ها با استفاده از یک کد پیشوندی متعارف کدگذاری می‌شوند. از این رو، کدها با ارسال طول کد پیشوندی ، برخلاف کدهای پیشوندی واقعی، منتقل می‌شوند.

به طور خاص، این فرمت از کدگذاری پیشوندی متغیر مکانی استفاده می‌کند. به عبارت دیگر، بلوک‌های مختلف تصویر می‌توانند به طور بالقوه از کدهای آنتروپی متفاوتی استفاده کنند.

منطق : نواحی مختلف تصویر ممکن است ویژگی‌های متفاوتی داشته باشند. بنابراین، اجازه دادن به آنها برای استفاده از کدهای آنتروپی مختلف، انعطاف‌پذیری بیشتر و فشرده‌سازی بالقوه بهتری را فراهم می‌کند.

۶.۲ جزئیات

داده‌های تصویر کدگذاری شده از چندین بخش تشکیل شده است:

1. رمزگشایی و ساخت کدهای پیشوندی.
2. کدهای پیشوند متا.
3. داده‌های تصویر کدگذاری شده با آنتروپی.

برای هر پیکسل داده شده (x، y)، مجموعه‌ای از پنج کد پیشوندی مرتبط با آن وجود دارد. این کدها (به ترتیب جریان بیتی) عبارتند از:

• کد پیشوند شماره ۱ : برای کانال سبز، طول مرجع معکوس و حافظه پنهان رنگ استفاده می‌شود.
• کد پیشوند #۲، #۳ و #۴ : به ترتیب برای کانال‌های قرمز، آبی و آلفا استفاده می‌شود.
• کد پیشوند شماره ۵ : برای فاصله مرجع معکوس استفاده می‌شود.

از اینجا به بعد، ما به این مجموعه به عنوان یک گروه کد پیشوندی اشاره می‌کنیم.

۶.۲.۱ رمزگشایی و ساخت کدهای پیشوندی

این بخش نحوه خواندن طول کدهای پیشوندی از جریان بیتی را شرح می‌دهد.

طول کدهای پیشوندی را می‌توان به دو روش کدگذاری کرد. روش مورد استفاده با یک مقدار ۱ بیتی مشخص می‌شود.

• اگر این بیت ۱ باشد، یک کد با طول کد ساده است.
• اگر این بیت 0 باشد، یک کد با طول کد معمولی است.

در هر دو مورد، ممکن است طول کدهای استفاده نشده‌ای وجود داشته باشند که هنوز بخشی از جریان هستند. این ممکن است ناکارآمد باشد، اما توسط قالب مجاز است. درخت توصیف شده باید یک درخت دودویی کامل باشد. یک گره برگ تکی، یک درخت دودویی کامل در نظر گرفته می‌شود و می‌تواند با استفاده از کد طول کد ساده یا کد طول کد معمولی کدگذاری شود. هنگام کدگذاری یک گره برگ تکی با استفاده از کد طول کد معمولی ، همه طول کدها به جز یکی صفر هستند و مقدار گره برگ تکی با طول ۱ مشخص می‌شود -- حتی زمانی که هیچ بیتی هنگام استفاده از آن درخت گره برگ تکی مصرف نمی‌شود.

کد طول کد ساده

این نوع در موارد خاص استفاده می‌شود که فقط ۱ یا ۲ نماد پیشوند در محدوده [۰..۲۵۵] با طول کد 1 قرار دارند. تمام طول‌های کد پیشوند دیگر به طور ضمنی صفر هستند.

بیت اول تعداد نمادها را نشان می‌دهد:

int num_symbols = ReadBits(1) + 1;

مقادیر نماد در زیر آمده است.

این نماد اول با استفاده از ۱ یا ۸ بیت، بسته به مقدار is_first_8bits ، کدگذاری می‌شود. محدوده به ترتیب [0..1] یا [0..255] است. نماد دوم، در صورت وجود، همیشه در محدوده [0..255] فرض می‌شود و با استفاده از ۸ بیت کدگذاری می‌شود.

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 هستند، کدگذاری کرد.

کد طول کد عادی

طول کدهای کد پیشوند در ۸ بیت جا می‌شود و به صورت زیر خوانده می‌شود. ابتدا، 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: ۲۵۶ + ۲۴ + color_cache_size
• سایر حروف (A، R و B): ۲۵۶
• کد فاصله: ۴۰

در غیر این صورت، به صورت زیر تعریف می‌شود:

int length_nbits = 2 + 2 * ReadBits(3);
int max_symbol = 2 + ReadBits(length_nbits);

اگر max_symbol بزرگتر از اندازه الفبای مربوط به نوع نماد باشد، جریان بیتی نامعتبر است.

سپس یک جدول پیشوند از code_length_code_lengths ساخته می‌شود و برای خواندن طول کدهای تا max_symbol استفاده می‌شود.

• کد [0..15] طول کد تحت‌اللفظی را نشان می‌دهد.
  • مقدار ۰ به این معنی است که هیچ نمادی کدگذاری نشده است.
  • مقادیر [1..15] طول بیت کد مربوطه را نشان می‌دهند.
• کد ۱۶ مقدار غیر صفر قبلی [۳..۶] را تکرار می‌کند، یعنی 3 + ReadBits(2) بار. اگر کد ۱۶ قبل از انتشار مقدار غیر صفر استفاده شود، مقدار ۸ تکرار می‌شود.
• کد ۱۷ یک رشته صفر به طول [۳..۱۰] منتشر می‌کند، یعنی 3 + ReadBits(3) بار.
• کد ۱۸ یک رشته صفر به طول [11..138] منتشر می‌کند، یعنی 11 + ReadBits(7) بار.

پس از خواندن طول کدها، یک کد پیشوندی برای هر نوع نماد (A، R، G، B و فاصله) با استفاده از اندازه‌های الفبای مربوطه تشکیل می‌شود.

کد طول کد عادی باید یک درخت تصمیم کامل را کدگذاری کند، یعنی مجموع 2 ^ (-length) برای همه کدهای غیر صفر باید دقیقاً برابر با یک باشد. با این حال، یک استثنا برای این قانون وجود دارد، درخت گره تک برگ، که در آن مقدار گره برگ با مقدار 1 و سایر مقادیر 0 مشخص می‌شوند.

۶.۲.۲ رمزگشایی کدهای پیشوند متا

همانطور که قبلاً اشاره شد، این قالب امکان استفاده از کدهای پیشوندی مختلف را برای بلوک‌های مختلف تصویر فراهم می‌کند. کدهای پیشوندی متا ، شاخص‌هایی هستند که مشخص می‌کنند از کدام کدهای پیشوندی در قسمت‌های مختلف تصویر استفاده شود.

کدهای پیشوند متا فقط زمانی می‌توانند استفاده شوند که تصویر در نقش یک تصویر ARGB استفاده شود.

دو حالت برای کدهای پیشوند متا وجود دارد که با مقدار ۱ بیتی نشان داده می‌شوند:

• اگر این بیت صفر باشد، فقط یک کد پیشوند متا در همه جای تصویر استفاده شده است. هیچ داده دیگری ذخیره نمی‌شود.
• اگر این بیت یک باشد، تصویر از چندین کد پیشوند متا استفاده می‌کند. این کدهای پیشوند متا به عنوان یک تصویر آنتروپی (که در زیر توضیح داده شده است) ذخیره می‌شوند.

اجزای قرمز و سبز یک پیکسل، یک کد پیشوند متای ۱۶ بیتی را تعریف می‌کنند که در یک بلوک خاص از تصویر 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) استفاده می‌کند، همانطور که در «رمزگشایی داده‌های تصویر کدگذاری شده با آنتروپی» توضیح داده شده است.

۶.۲.۳ رمزگشایی داده‌های تصویر کدگذاری شده با آنتروپی

برای موقعیت فعلی (x، y) در تصویر، رمزگشا ابتدا گروه کد پیشوند مربوطه را شناسایی می‌کند (همانطور که در بخش قبل توضیح داده شد). با داشتن گروه کد پیشوند، پیکسل به شرح زیر خوانده و رمزگشایی می‌شود.

در مرحله بعد، نماد S را از جریان بیتی با استفاده از کد پیشوند شماره ۱ بخوانید. توجه داشته باشید که S هر عدد صحیحی در محدوده 0 تا (256 + 24 + color_cache_size - 1) است.

تفسیر S به مقدار آن بستگی دارد:

1. اگر S < 256
   1. از S به عنوان مؤلفه سبز استفاده کنید.
   2. با استفاده از کد پیشوند شماره ۲، رنگ قرمز را از جریان بیتی بخوانید.
   3. با استفاده از کد پیشوند شماره ۳، رنگ آبی را از جریان بیتی بخوانید.
   4. با استفاده از کد پیشوند شماره ۴، آلفا را از جریان بیتی بخوانید.
2. اگر S >= 256 و S < 256 + 24 باشد
   1. از S-256 به عنوان کد پیشوند طول استفاده کنید.
   2. بیت‌های اضافی را برای طول از جریان بیت بخوانید.
   3. طول مرجع معکوس L را از کد پیشوند طول و بیت‌های اضافی خوانده شده تعیین کنید.
   4. کد پیشوند فاصله را از جریان بیتی با استفاده از کد پیشوند شماره ۵ بخوانید.
   5. بیت‌های اضافی را برای فاصله از جریان بیت بخوانید.
   6. فاصله مرجع معکوس D را از کد پیشوند فاصله و بیت‌های اضافی خوانده شده تعیین کنید.
   7. L پیکسل (به ترتیب خط اسکن) را از توالی پیکسل‌هایی که از موقعیت فعلی منهای D پیکسل شروع می‌شوند، کپی کن.
3. اگر S >= ۲۵۶ + ۲۴ باشد
   1. از S - (256 + 24) به عنوان اندیس در حافظه پنهان رنگ استفاده کنید.
   2. رنگ ARGB را از حافظه پنهان رنگ در آن فهرست دریافت کنید.

۷ ساختار کلی قالب

در زیر نمایی از قالب موجود در فرم Augmented Backus-Naur (ABNF) مطابق با RFC 5234 RFC 7405 مشاهده می‌کنید. این تصویر تمام جزئیات را پوشش نمی‌دهد. انتهای تصویر (EOI) فقط به صورت ضمنی در تعداد پیکسل‌ها (image_width * image_height) کدگذاری شده است.

Note that *element means element can be repeated 0 or more times. 5element means element is repeated exactly 5 times. %b represents a binary value.

7.1 Basic Structure

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 Structure of Transforms

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 Structure of the Image Data

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)

The following is a possible example sequence:

RIFF-header image-size %b1 subtract-green-tx
%b1 predictor-tx %b0 color-cache-info
%b0 prefix-codes lz77-coded-image