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

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

چکیده

WebP lossless یک فرمت تصویر برای فشرده سازی بدون تلفات تصاویر 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 در WebPlessless) ایندکس شود.

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

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

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

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

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

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

LZ77

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

کد پیشوند متا

یک عدد صحیح کوچک (تا 16 بیت) که یک عنصر را در جدول متا پیشوند نمایه می کند.

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

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

کد پیشوند

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

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

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

سفارش خط اسکن

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

3 سربرگ RIFF

ابتدای هدر دارای ظرف RIFF است. این شامل 21 بایت زیر است:

1. رشته "RIFF".
2. مقدار کمی اندین و 32 بیتی طول قطعه، که اندازه کل قطعه است که توسط هدر RIFF کنترل می شود. به طور معمول، این برابر با اندازه بار است (اندازه فایل منهای 8 بایت: 4 بایت برای شناسه "RIFF" و 4 بایت برای ذخیره خود مقدار).
3. رشته "WEBP" (نام ظرف RIFF).
4. رشته «VP8L» (FourCC برای داده‌های تصویر رمزگذاری‌شده بدون تلفات).
5. مقدار اندکی اندین و 32 بیتی تعداد بایت‌ها در جریان بدون تلفات.
6. امضای 1 بایتی 0x2f.

28 بیت اول بیت استریم عرض و ارتفاع تصویر را مشخص می کند. عرض و ارتفاع به صورت اعداد صحیح 14 بیتی به صورت زیر رمزگشایی می شوند:

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

دقت 14 بیتی برای عرض و ارتفاع تصویر حداکثر اندازه یک تصویر بدون اتلاف WebP را به 16384✕16384 پیکسل محدود می کند.

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

int alpha_is_used = ReadBits(1);

version_number یک کد 3 بیتی است که باید روی 0 تنظیم شود. هر مقدار دیگری باید به عنوان یک خطا تلقی شود.

int version_number = ReadBits(3);

4 تبدیل می شود

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

یک تصویر می تواند از چهار نوع تبدیل عبور کند. یک بیت ۱ نشان دهنده وجود یک تبدیل است. هر تبدیل مجاز است فقط یک بار استفاده شود. تبدیل ها فقط برای تصویر 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 تبدیل پیش بینی کننده

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

داده های تبدیل شامل حالت پیش بینی برای هر بلوک از تصویر است. این یک تصویر با وضوح فرعی است که در آن جزء سبز رنگ یک پیکسل مشخص می‌کند که کدام یک از ۱۴ پیش‌بینی‌کننده برای تمام پیکسل‌های 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	تی
3	TR
4	TL
5	میانگین2(متوسط2(L، TR)، T)
6	میانگین 2 (L, TL)
7	میانگین 2 (L, T)
8	میانگین 2 (TL، T)
9	میانگین 2 (T, TR)
10	میانگین2(متوسط2(L، TL)، میانگین2(T، TR))
11	انتخاب (L، T، TL)
12	ClampAddSubtractFull(L، T، TL)
13	ClampAddSubtractHalf(Average2(L, T)، TL)

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

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

پیش بینی انتخاب به صورت زیر تعریف می شود:

uint32 Select(uint32 L, uint32 T, uint32 TL) {
  // L = left pixel, T = top pixel, TL = top-left pixel.

  // ARGB component estimates for prediction.
  int pAlpha = ALPHA(L) + ALPHA(T) - ALPHA(TL);
  int pRed = RED(L) + RED(T) - RED(TL);
  int pGreen = GREEN(L) + GREEN(T) - GREEN(TL);
  int pBlue = BLUE(L) + BLUE(T) - BLUE(TL);

  // Manhattan distances to estimates for left and top pixels.
  int pL = abs(pAlpha - ALPHA(L)) + abs(pRed - RED(L)) +
           abs(pGreen - GREEN(L)) + abs(pBlue - BLUE(L));
  int pT = abs(pAlpha - ALPHA(T)) + abs(pRed - RED(T)) +
           abs(pGreen - GREEN(T)) + abs(pBlue - BLUE(T));

  // Return either left or top, the one closer to the prediction.
  if (pL < pT) {
    return L;
  } else {
    return T;
  }
}

توابع ClampAddSubtractFull و ClampAddSubtractHalf برای هر جزء ARGB به شرح زیر انجام می شود:

// Clamp the input value between 0 and 255.
int Clamp(int a) {
  return (a < 0) ? 0 : (a > 255) ? 255 : a;
}

int ClampAddSubtractFull(int a, int b, int c) {
  return Clamp(a + b - c);
}

int ClampAddSubtractHalf(int a, int b) {
  return Clamp(a + (a - b) / 2);
}

قوانین کنترل خاصی برای برخی از پیکسل های حاشیه وجود دارد. اگر یک تبدیل پیش‌بینی‌کننده وجود داشته باشد، صرف نظر از حالت [0..13] برای این پیکسل‌ها، مقدار پیش‌بینی‌شده برای پیکسل بالای سمت چپ تصویر 0xff000000 است، همه پیکسل‌های ردیف بالا L-pixel و همه پیکسل‌ها هستند. در سمت چپ ترین ستون T-pixel هستند.

آدرس دادن پیکسل های TR برای پیکسل های سمت راست ترین ستون استثنایی است. پیکسل‌های سمت راست‌ترین ستون با استفاده از حالت‌های [0..13] پیش‌بینی می‌شوند، درست مانند پیکسل‌هایی که در حاشیه نیستند، اما از سمت چپ‌ترین پیکسل در همان ردیف پیکسل فعلی به‌عنوان پیکسل TR استفاده می‌شود.

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

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 بیت کمتر از نتیجه استفاده می شود و در این بیت ها، تغییر پسوند علامت و جابجایی بدون علامت با یکدیگر همخوانی دارند.

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

int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;

بخش باقی مانده از داده های تبدیل رنگ حاوی نمونه های ColorTransformElement است که مربوط به هر بلوک تصویر است. هر ColorTransformElement 'cte' در یک تصویر با وضوح فرعی که جزء آلفا آن 255 است، جزء قرمز cte.red_to_blue ، جزء سبز cte.green_to_blue ، و جزء آبی cte.green_to_red است، به عنوان یک پیکسل در نظر گرفته می شود.

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

void InverseTransform(uint8 red, uint8 green, uint8 blue,
                      ColorTransformElement *trans,
                      uint8 *new_red, uint8 *new_blue) {
  // Transformed values of red and blue components
  int tmp_red = red;
  int tmp_blue = blue;

  // Applying the inverse transform is just adding the
  // color transform deltas
  tmp_red  += ColorTransformDelta(trans->green_to_red, green);
  tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
  tmp_blue +=
      ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);

  *new_red = tmp_red & 0xff;
  *new_blue = tmp_blue & 0xff;
}

4.3 تفریق تبدیل سبز

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

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

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

4.4 تبدیل نمایه سازی رنگ

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

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

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

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

جدول رنگ با استفاده از خود فرمت ذخیره سازی تصویر ذخیره می شود. جدول رنگ را می توان با خواندن یک تصویر، بدون هدر RIFF، اندازه تصویر و تبدیل ها، با فرض ارتفاع 1 پیکسل و عرض 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 در 2 بیت کم اهمیت از مقدار سبز در x / 4، و مقادیر سبز در x + 1 تا x قرار می گیرد. + 3 به منظور بیت های مهم تر از مقدار سبز در x / 4 قرار می گیرند.
• width_bits = 3: برای هر مقدار x، که در آن x ≡ 0 (mod 8)، یک مقدار سبز در x در کمترین بیت ارزش سبز در x / 8 قرار می گیرد، و مقادیر سبز در x + 1 تا x + 7 قرار می گیرد. به ترتیب بیت های مهمتر از مقدار سبز در x/8 قرار می گیرند.

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

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

5 داده های تصویری

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

5.1 نقش داده های تصویری

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

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

5.2 رمزگذاری داده های تصویر

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

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

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

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

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

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

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 پیکسل تشکیل شده است:

• پیکسل هایی که 1 تا 7 ردیف بالاتر از پیکسل فعلی هستند و حداکثر 8 ستون در سمت چپ یا حداکثر تا 7 ستون در سمت راست پیکسل فعلی قرار دارند. [مجموع چنین پیکسل ها = 7 * (8 + 1 + 7) = 112 ].
• پیکسل هایی که در همان ردیف پیکسل فعلی قرار دارند و تا 8 ستون در سمت چپ پیکسل فعلی قرار دارند. [ 8 چنین پیکسل].

نگاشت بین کد فاصله distance_code و افست پیکسل همسایه (xi, yi) به شرح زیر است:

(0, 1),  (1, 0),  (1, 1),  (-1, 1), (0, 2),  (2, 0),  (1, 2),
(-1, 2), (2, 1),  (-2, 1), (2, 2),  (-2, 2), (0, 3),  (3, 0),
(1, 3),  (-1, 3), (3, 1),  (-3, 1), (2, 3),  (-2, 3), (3, 2),
(-3, 2), (0, 4),  (4, 0),  (1, 4),  (-1, 4), (4, 1),  (-4, 1),
(3, 3),  (-3, 3), (2, 4),  (-2, 4), (4, 2),  (-4, 2), (0, 5),
(3, 4),  (-3, 4), (4, 3),  (-4, 3), (5, 0),  (1, 5),  (-1, 5),
(5, 1),  (-5, 1), (2, 5),  (-2, 5), (5, 2),  (-5, 2), (4, 4),
(-4, 4), (3, 5),  (-3, 5), (5, 3),  (-5, 3), (0, 6),  (6, 0),
(1, 6),  (-1, 6), (6, 1),  (-6, 1), (2, 6),  (-2, 6), (6, 2),
(-6, 2), (4, 5),  (-4, 5), (5, 4),  (-5, 4), (3, 6),  (-3, 6),
(6, 3),  (-6, 3), (0, 7),  (7, 0),  (1, 7),  (-1, 7), (5, 5),
(-5, 5), (7, 1),  (-7, 1), (4, 6),  (-4, 6), (6, 4),  (-6, 4),
(2, 7),  (-2, 7), (7, 2),  (-7, 2), (3, 7),  (-3, 7), (7, 3),
(-7, 3), (5, 6),  (-5, 6), (6, 5),  (-6, 5), (8, 0),  (4, 7),
(-4, 7), (7, 4),  (-7, 4), (8, 1),  (8, 2),  (6, 6),  (-6, 6),
(8, 3),  (5, 7),  (-5, 7), (7, 5),  (-7, 5), (8, 4),  (6, 7),
(-6, 7), (7, 6),  (-7, 6), (8, 5),  (7, 7),  (-7, 7), (8, 6),
(8, 7)

به عنوان مثال، کد فاصله 1 یک آفست (0, 1) را برای پیکسل مجاور نشان می دهد، یعنی پیکسل بالای پیکسل فعلی (تفاوت 0 پیکسل در جهت X و تفاوت 1 پیکسل در جهت 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] است. رمزگشاهای سازگار باید یک جریان بیتی خراب را برای مقادیر دیگر نشان دهند.

کش رنگ آرایه ای با اندازه color_cache_size است. هر ورودی یک رنگ ARGB را ذخیره می کند. رنگ‌ها با فهرست‌بندی (0x1e35a7bd * color) >> (32 - color_cache_code_bits) جستجو می‌شوند. فقط یک جستجو در یک کش رنگ انجام می شود. هیچ حل تعارضی وجود ندارد

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

6 کد آنتروپی

6.1 بررسی اجمالی

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

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

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

6.2 جزئیات

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

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

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

• کد پیشوند شماره 1 : برای کانال سبز، طول مرجع به عقب و حافظه پنهان رنگ استفاده می شود.
• کد پیشوند #2، #3 و #4 : به ترتیب برای کانال های قرمز، آبی و آلفا استفاده می شود.
• کد پیشوند #5 : برای فاصله مرجع به عقب استفاده می شود.

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

6.2.1 رمزگشایی و ساخت کدهای پیشوند

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

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

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

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

کد ساده طول کد

این نوع در موارد خاصی استفاده می شود که فقط 1 یا 2 نماد پیشوند در محدوده [0..255] با طول کد 1 قرار دارند. تمام طول های کد پیشوند دیگر به طور ضمنی صفر هستند.

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

int num_symbols = ReadBits(1) + 1;

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

این نماد اول بسته به مقدار is_first_8bits با استفاده از 1 یا 8 بیت کدگذاری می شود. محدوده به ترتیب [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
• لفظ دیگر (الف، ر و ب): 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 مشخص شده است و مقادیر دیگر 0s هستند.

6.2.2 رمزگشایی کدهای پیشوند متا

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

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

دو امکان برای کدهای پیشوند متا وجود دارد که با مقدار 1 بیتی نشان داده می شود:

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

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

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

تصویر آنتروپی مشخص می کند که کدام کدهای پیشوند در قسمت های مختلف تصویر استفاده می شوند.

3 بیت اول حاوی مقدار prefix_bits است. ابعاد تصویر آنتروپی از prefix_bits گرفته شده است:

int prefix_bits = ReadBits(3) + 2;
int prefix_image_width =
    DIV_ROUND_UP(image_width, 1 << prefix_bits);
int prefix_image_height =
    DIV_ROUND_UP(image_height, 1 << prefix_bits);

جایی که DIV_ROUND_UP همانطور که قبلاً تعریف شده است.

بیت های بعدی حاوی تصویر آنتروپی عرض prefix_image_width و ارتفاع prefix_image_height هستند.

تفسیر کدهای پیشوند متا

تعداد گروه های کد پیشوند در تصویر ARGB را می توان با یافتن بزرگترین کد پیشوند متا از تصویر آنتروپی به دست آورد:

int num_prefix_groups = max(entropy image) + 1;

که در آن max(entropy image) بزرگترین کد پیشوند ذخیره شده در تصویر آنتروپی را نشان می دهد.

از آنجایی که هر گروه کد پیشوند شامل پنج کد پیشوند است، تعداد کل کدهای پیشوند عبارتند از:

int num_prefix_codes = 5 * num_prefix_groups;

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

int position =
    (y >> prefix_bits) * prefix_image_width + (x >> prefix_bits);
int meta_prefix_code = (entropy_image[position] >> 8) & 0xffff;
PrefixCodeGroup prefix_group = prefix_code_groups[meta_prefix_code];

که در آن ما وجود ساختار PrefixCodeGroup را فرض کرده ایم که مجموعه ای از پنج کد پیشوند را نشان می دهد. همچنین، prefix_code_groups آرایه‌ای از PrefixCodeGroup (با اندازه num_prefix_groups ) است.

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

6.2.3 رمزگشایی داده های تصویر کدگذاری شده با آنتروپی

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

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

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

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

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

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

توجه داشته باشید که *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