ข้อกำหนดสำหรับ WebP Lossless Bitstream

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

บทคัดย่อ

WebP แบบไม่สูญเสียรายละเอียดเป็นรูปแบบรูปภาพสำหรับการบีบอัดรูปภาพ ARGB แบบไม่สูญเสียรายละเอียด รูปแบบแบบไม่สูญเสียจะจัดเก็บและกู้คืนค่าพิกเซลอย่างถูกต้อง รวมถึงค่าสีสำหรับพิกเซลที่โปร่งใสทั้งหมด อัลกอริทึมสากลสำหรับลำดับ การบีบอัดข้อมูล (LZ77) การเขียนโค้ดคำนำหน้า และแคชสีใช้สำหรับ การบีบอัดข้อมูลจำนวนมาก มีการสาธิตความเร็วในการถอดรหัสที่เร็วกว่า PNG รวมถึงการบีบอัดที่หนาแน่นขึ้น 25% เมื่อเทียบกับการใช้รูปแบบ PNG ในปัจจุบัน

1 บทนำ

เอกสารนี้อธิบายการนำเสนอข้อมูลแบบบีบอัดของระบบ WebP แบบไม่สูญเสียรายละเอียด รูปภาพ เอกสารนี้มีไว้เพื่อเป็นข้อมูลอ้างอิงโดยละเอียดสำหรับการใช้งานโปรแกรมเข้ารหัสและโปรแกรมถอดรหัส WebP แบบไม่มีการสูญเสีย

ในเอกสารนี้ เราใช้ไวยากรณ์ภาษาโปรแกรม C อย่างครอบคลุมเพื่ออธิบาย บิตสตรีมและสมมติว่ามีฟังก์ชันสำหรับบิตการอ่าน ReadBits(n) ระบบจะอ่านไบต์ตามลําดับตามธรรมชาติของสตรีมที่มีไบต์เหล่านั้น และอ่านบิตของไบต์แต่ละรายการตามลําดับบิตที่มีค่าน้อยที่สุดก่อน วันและเวลา มีการอ่านบิตพร้อมกันหลายบิต จำนวนเต็มจะสร้างขึ้นจาก ข้อมูลเดิมในลำดับเดิม บิตที่สำคัญที่สุดของผลลัพธ์ จำนวนเต็มเป็นบิตที่สำคัญที่สุดของข้อมูลต้นฉบับด้วย ดังนั้น ข้อความ

b = ReadBits(2);

เทียบเท่ากับข้อความ 2 ข้อความด้านล่าง

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

เราสมมติว่าส่วนประกอบแต่ละสี ซึ่งได้แก่ อัลฟา สีแดง สีน้ำเงิน และสีเขียว แสดงโดยใช้ไบต์ 8 บิต เรากําหนดประเภทที่เกี่ยวข้องเป็น uint8 ต พิกเซล ARGB ทั้งหมดแสดงด้วยประเภทที่เรียกว่า uint32 ซึ่งเป็นโมเดลที่ไม่มีการรับรอง จำนวนเต็มที่ประกอบด้วย 32 บิต ในโค้ดที่แสดงลักษณะการทํางานของการเปลี่ยนรูปแบบ ค่าเหล่านี้จะเข้ารหัสไว้ในบิตต่อไปนี้ อัลฟ่าในบิต 31..24, สีแดงในบิต 23..16, สีเขียวในบิต 15..8 และสีน้ำเงินในบิต 7..0 อย่างไรก็ตาม การใช้งานรูปแบบนี้สามารถใช้การนําเสนอรูปแบบอื่นภายในได้

โดยทั่วไป รูปภาพ WebP แบบไม่สูญเสียรายละเอียดจะประกอบด้วยข้อมูลส่วนหัว ข้อมูลการเปลี่ยนรูปแบบ และ ข้อมูลภาพจริง ส่วนหัวประกอบด้วยความกว้างและความสูงของรูปภาพ WebP รูปภาพแบบไม่สูญเสียรายละเอียดผ่านการเปลี่ยนรูปแบบได้ 4 ประเภทก่อนที่จะ เข้ารหัสเอนโทรปีแล้ว ข้อมูลการเปลี่ยนรูปแบบในบิตสตรีมจะมีข้อมูล ที่จำเป็นต่อการใช้การแปลงผกผันที่เกี่ยวข้อง

2 ชื่อ

ARGB

ค่าพิกเซลที่ประกอบด้วยค่าอัลฟ่า แดง เขียว และน้ำเงิน

รูปภาพ ARGB

อาร์เรย์ 2 มิติที่มีพิกเซล ARGB

แคชสี

อาร์เรย์ที่ระบุแฮชขนาดเล็กสำหรับจัดเก็บสีที่ใช้ล่าสุดเพื่อให้ ก็เรียกรหัสที่สั้นลง

รูปภาพการจัดทำดัชนีสี

รูปภาพสี 1 มิติที่จัดทําดัชนีได้โดยใช้จำนวนเต็มขนาดเล็ก (สูงสุด 256 ภายใน WebP แบบไม่สูญเสียคุณภาพ)

รูปภาพเปลี่ยนสี

รูปภาพย่อยแบบ 2 มิติที่มีข้อมูลเกี่ยวกับสหสัมพันธ์ของ ส่วนประกอบของสี

การแมประยะทาง

เปลี่ยนระยะทาง LZ77 ให้มีค่าต่ำสุดสำหรับพิกเซลใน ความใกล้ชิดแบบ 2 มิติ

รูปภาพเอนโทรปี

รูปภาพความละเอียดย่อย 2 มิติที่ระบุการโค้ดข้อมูลเอ็นโทรปีซึ่งควรใช้ในสี่เหลี่ยมจัตุรัสที่เกี่ยวข้องในรูปภาพ กล่าวคือ พิกเซลแต่ละพิกเซลคือโค้ดคำนำหน้าเมตา

LZ77

อัลกอริทึมการบีบอัดหน้าต่างเลื่อนแบบพจนานุกรม ซึ่งจะปล่อย หรืออธิบายเป็นลำดับสัญลักษณ์ในอดีต

รหัสคำนำหน้าเมตา

จำนวนเต็มขนาดเล็ก (สูงสุด 16 บิต) ที่จัดทําดัชนีองค์ประกอบในตารางคำนำหน้าเมตา

รูปภาพตัวทำนาย

รูปภาพความละเอียดย่อย 2 มิติที่ระบุตัวทำนายเชิงพื้นที่ที่ใช้สำหรับสี่เหลี่ยมจัตุรัสหนึ่งๆ ในรูปภาพ

รหัสคำนำหน้า

วิธีคลาสสิกในการเข้ารหัสเอนโทรปีที่ใช้บิตจำนวนน้อยลงสําหรับโค้ดที่พบบ่อย

การเขียนโค้ดคำนำหน้า

วิธีเข้ารหัสเอนโทรปีจำนวนเต็มขนาดใหญ่ ซึ่งเข้ารหัสจำนวนเต็ม 2-3 บิตโดยใช้รหัสเอนโทรปี และเข้ารหัสบิตที่เหลือแบบไม่เข้ารหัส วิธีนี้ช่วยให้คำอธิบายของรหัสเอนโทรปีมีความยาวไม่มากนักแม้ว่าช่วงของสัญลักษณ์จะกว้างมากก็ตาม

ลำดับบรรทัดสแกน

ลำดับการประมวลผลของพิกเซล (จากซ้ายไปขวาและบนลงล่าง) เริ่มต้น จากพิกเซลด้านบนซ้าย เมื่อแถวเสร็จสมบูรณ์แล้ว ให้ดำเนินการต่อจาก คอลัมน์ด้านซ้ายของแถวถัดไป

ส่วนหัว RIFF 3

จุดเริ่มต้นของส่วนหัวมีคอนเทนเนอร์ RIFF ซึ่งประกอบด้วย 21 ไบต์ต่อไปนี้

1. สตริง "RIFF"
2. ค่า 32 บิตของความยาวช่องที่เป็นช่องปลายน้อยซึ่งเป็นขนาดทั้งหมด ของกลุ่มที่ควบคุมโดยส่วนหัว RIFF โดยปกติแล้ว ค่านี้เท่ากับ ขนาดเพย์โหลด (ขนาดไฟล์ลบ 8 ไบต์: 4 ไบต์สำหรับ "RIFF" และ 4 ไบต์สำหรับจัดเก็บค่านั้น)
3. สตริง "WEBP" (ชื่อคอนเทนเนอร์ RIFF)
4. สตริง "VP8L" (FourCC สำหรับข้อมูลรูปภาพที่เข้ารหัสแบบไม่สูญเสียคุณภาพ)
5. ค่า 32 บิตแบบ Little Endian ของจำนวนไบต์ในสตรีมแบบไม่สูญเสีย
6. ลายเซ็น 1 ไบต์ 0x2f

28 บิตแรกของบิตสตรีมจะระบุความกว้างและความสูงของรูปภาพ ความกว้างและความสูงจะถอดรหัสเป็นจำนวนเต็ม 14 บิตดังนี้

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

ความแม่นยำ 14 บิตสำหรับความกว้างและความสูงของรูปภาพจะจำกัดขนาดสูงสุดของรูปภาพ WebP แบบไม่สูญเสียให้เป็น 16384 x 16384 พิกเซล

บิต alpha_is_used เป็นคำแนะนำเท่านั้น และไม่ควรส่งผลต่อการถอดรหัส ควร กำหนดเป็น 0 เมื่อค่าอัลฟ่าทั้งหมดเป็น 255 ในรูปภาพ และ 1 ในกรณีอื่นๆ

int alpha_is_used = ReadBits(1);

version_number คือรหัส 3 บิตที่ต้องตั้งค่าเป็น 0 ค่าอื่นๆ ควร ถือเป็นข้อผิดพลาด

int version_number = ReadBits(3);

การเปลี่ยนรูปแบบ 4 รายการ

การแปลงเป็นการทำซ้ำแบบย้อนกลับได้ของข้อมูลภาพที่สามารถลด เอนโทรปีเชิงสัญลักษณ์ที่เหลืออยู่ด้วยการสร้างแบบจำลองความสัมพันธ์เชิงพื้นที่และสี ซึ่งอาจทำให้การบีบอัดขั้นสุดท้ายมีความหนาแน่นมากขึ้น

รูปภาพจะมีการเปลี่ยนรูปแบบได้ 4 ประเภท จำนวน 1 บิตหมายถึง การเปลี่ยนรูปแบบ อนุญาตให้ใช้การเปลี่ยนรูปแบบแต่ละรายการได้เพียงครั้งเดียว การเปลี่ยนรูปแบบจะใช้เฉพาะกับรูปภาพ ARGB ระดับหลักเท่านั้น รูปภาพความละเอียดย่อย (รูปภาพการเปลี่ยนรูปแบบสี รูปภาพเอนโทรปี และรูปภาพตัวคาดการณ์) ไม่มีการเปลี่ยนรูปแบบ แม้แต่บิต 0 ที่แสดงถึงจุดสิ้นสุดของการแปลง

โดยปกติแล้ว ตัวเข้ารหัสจะใช้การเปลี่ยนรูปแบบเหล่านี้เพื่อลดเอนโทรปีของ Shannon ในรูปภาพส่วนที่เหลือ นอกจากนี้ ข้อมูลการแปลงยังตัดสินใจได้จากเอนโทรปี ขอบเขตที่เล็กที่สุด

while (ReadBits(1)) {  // Transform present.
  // Decode transform type.
  enum TransformType transform_type = ReadBits(2);
  // Decode transform data.
  ...
}

// Decode actual image data (Section 5).

หากมีการเปลี่ยนรูปแบบ สองบิตถัดไปจะระบุประเภทการเปลี่ยนรูปแบบ การเปลี่ยนรูปแบบมี 4 ประเภท

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);

ข้อมูลการแปลงประกอบด้วยโหมดการคาดการณ์สำหรับแต่ละบล็อกของรูปภาพ รูปภาพนี้เป็นรูปภาพความละเอียดย่อยที่องค์ประกอบสีเขียวของพิกเซลจะกำหนดว่าจะใช้ตัวทำนายใด 14 ตัวกับพิกเซล block_width * block_height ทั้งหมดภายในบล็อกรูปภาพ ARGB หนึ่งๆ รูปภาพความละเอียดย่อยนี้เข้ารหัสโดยใช้ เทคนิคเดียวกับที่อธิบายไว้ในบทที่ 5

จำนวนคอลัมน์บล็อก transform_width ที่ใช้ในแบบ 2 มิติ การจัดทำดัชนี สําหรับพิกเซล (x, y) เราสามารถคํานวณที่อยู่บล็อกตัวกรองที่เกี่ยวข้องได้โดยทำดังนี้

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

โหมดการคาดการณ์มีด้วยกัน 14 โหมด ในโหมดการคาดการณ์แต่ละโหมด ระบบจะคาดคะเนค่าพิกเซลปัจจุบันจากพิกเซลใกล้เคียงอย่างน้อย 1 พิกเซลที่ทราบค่าแล้ว

เราเลือกพิกเซลใกล้เคียง (TL, T, TR และ L) ของพิกเซลปัจจุบัน (P) เป็น ดังต่อไปนี้:

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

โดย TL หมายถึงด้านซ้ายบน T หมายถึงด้านบน TR หมายถึงด้านขวาบน และ L หมายถึงด้านซ้าย ณ เวลาคาดการณ์ค่าของ P พิกเซล O, TL, T, TR และ L ทั้งหมดได้รับการประมวลผลแล้ว และระบบไม่ทราบค่าพิกเซล P และพิกเซล X ทั้งหมด

สำหรับพิกเซลใกล้เคียงที่อยู่ก่อนหน้า โหมดการคาดการณ์ต่างๆ ได้แก่ มีคำจำกัดความดังนี้

โหมด	ค่าที่คาดการณ์ของแต่ละแชแนลของพิกเซลปัจจุบัน
0	0xff000000 (แสดงสีดำทึบใน ARGB)
1	L
2	T
3	ลีราตุรกี (TRY)
4	TL
5	Average2(Average2(L, TR), T)
6	เฉลี่ย 2(L, TL)
7	เฉลี่ย 2(L, T)
8	เฉลี่ย 2(TL, T)
9	ค่าเฉลี่ย2(T, TR)
10	Average2(Average2(L, TL), Average2(T, TR))
11	Select(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

Average2 กำหนดไว้ดังต่อไปนี้สำหรับคอมโพเนนต์ ARGB แต่ละรายการ

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

ตัวคาดการณ์ Select มีการกำหนดไว้ดังต่อไปนี้

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

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

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

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

ดำเนินการฟังก์ชัน ClampAddSubtractFull และ ClampAddSubtractHalf แล้ว สำหรับคอมโพเนนต์ ARGB แต่ละรายการดังนี้

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

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

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

มีกฎการจัดการพิเศษสำหรับพิกเซลเส้นขอบบางรายการ หากมีการเปลี่ยนรูปแบบตัวทำนาย ไม่ว่าโหมด [0..13] สำหรับพิกเซลเหล่านี้จะเป็นโหมดใด ค่าที่คาดการณ์สำหรับพิกเซลด้านซ้ายบนสุดของรูปภาพจะเป็น 0xff000000, พิกเซลทั้งหมดในแถวบนสุดจะเป็นพิกเซล L และพิกเซลทั้งหมดในคอลัมน์ด้านซ้ายสุดจะเป็นพิกเซล T

การระบุพิกเซล TR สําหรับพิกเซลในคอลัมน์ด้านขวาสุดนั้นยอดเยี่ยม ระบบจะคาดการณ์พิกเซลในคอลัมน์ขวาสุดโดยใช้โหมด [0..13] เช่นเดียวกับพิกเซลที่ไม่ได้อยู่บนเส้นขอบ แต่เป็นพิกเซลด้านซ้ายสุดบน แถวเดียวกับพิกเซลปัจจุบันจะใช้เป็นพิกเซล TR แทน

ค่าพิกเซลสุดท้ายได้จากการบวกแต่ละช่องของค่าที่คาดการณ์เข้ากับค่าที่เหลือที่เข้ารหัส

void PredictorTransformOutput(uint32 residual, uint32 pred,
                              uint8* alpha, uint8* red,
                              uint8* green, uint8* blue) {
  *alpha = ALPHA(residual) + ALPHA(pred);
  *red = RED(residual) + RED(pred);
  *green = GREEN(residual) + GREEN(pred);
  *blue = BLUE(residual) + BLUE(pred);
}

4.2 การเปลี่ยนสี

เป้าหมายของการเปลี่ยนรูปแบบสีคือการแยกค่า R, G และ B ของพิกเซลแต่ละพิกเซล การเปลี่ยนรูปแบบสีจะคงค่าสีเขียว (G) ไว้ตามเดิม และเปลี่ยนค่า สีแดง (R) โดยอิงตามค่าสีเขียวและแปลงค่าสีน้ำเงิน (B) ตาม ค่าสีเขียว ตามด้วยค่าสีแดง

เช่นเดียวกับในกรณีของการเปลี่ยนรูปแบบตัวทำนาย ระบบจะแบ่งรูปภาพออกเป็นบล็อกก่อน แล้วใช้โหมดการเปลี่ยนรูปแบบเดียวกันกับพิกเซลทั้งหมดในบล็อก องค์ประกอบการเปลี่ยนสีมี 3 ประเภทสําหรับแต่ละบล็อก

typedef struct {
  uint8 green_to_red;
  uint8 green_to_blue;
  uint8 red_to_blue;
} ColorTransformElement;

การเปลี่ยนสีจริงจะทําได้โดยกําหนดค่า Delta การเปลี่ยนสี เดลต้าการเปลี่ยนสีขึ้นอยู่กับ 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() ค่าที่มีเครื่องหมายควรตีความว่าเป็นตัวเลขแบบเติมเต็ม 2 บิต 8 บิต (กล่าวคือ ช่วง uint8 [128..255] จะแมปกับช่วง [-128..-1] ของค่า int8 ที่แปลง)

การคูณต้องใช้ความแม่นยำมากขึ้น (อย่างน้อย 16 บิต ความแม่นยำ) พร็อพเพอร์ตี้ส่วนขยายป้ายของการดำเนินการ Shift ไม่สำคัญ ที่นี่ จะใช้เพียง 8 บิตต่ำสุดจากผลลัพธ์ และในบิตเหล่านี้ การเปลี่ยนส่วนขยายป้ายและการเปลี่ยนแบบที่ไม่ได้ลงชื่อนั้นสอดคล้องกัน

ในตอนนี้ เราอธิบายเนื้อหาของข้อมูลการแปลงสีเพื่อให้ใช้การถอดรหัสได้ สีผกผันจะเปลี่ยนรูปแบบและเรียกคืนค่าสีแดงและน้ำเงินเดิม 3 บิตแรกของข้อมูลการแปลงสีประกอบด้วยความกว้างและความสูงของ บล็อกรูปภาพตามจำนวนบิตเช่นเดียวกับการแปลงตัวคาดการณ์:

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

ส่วนที่เหลือของข้อมูลการเปลี่ยนสีมีอินสแตนซ์ ColorTransformElement ซึ่งสอดคล้องกับแต่ละบล็อกของรูปภาพ ระบบจะถือว่าColorTransformElement 'cte' แต่ละรายการเป็นพิกเซลในรูปภาพความละเอียดย่อยซึ่งมีองค์ประกอบอัลฟ่าเป็น 255, องค์ประกอบสีแดงเป็น cte.red_to_blue, องค์ประกอบสีเขียวเป็น cte.green_to_blue และองค์ประกอบสีน้ำเงินเป็น cte.green_to_red

ในระหว่างการถอดรหัส ระบบจะถอดรหัสบล็อก ColorTransformElement รายการและใช้การเปลี่ยนสีแบบกลับกับค่า ARGB ของพิกเซล อาส ที่กล่าวถึงก่อนหน้านี้ การแปลงสีแบบผกผันเป็นการเพิ่ม ColorTransformElement เป็นค่าสำหรับช่องสีแดงและสีน้ำเงิน อัลฟ่าและสีเขียว ช่องทิ้งไว้ตามเดิม

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

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

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

4.3 ลบการเปลี่ยนแปลงสีเขียว

การเปลี่ยนรูปแบบลบสีเขียวจะลบค่าสีเขียวออกจากค่าสีแดงและสีน้ำเงินของพิกเซลแต่ละพิกเซล เมื่อมีการแปลงนี้ ตัวถอดรหัสจะต้องเพิ่มค่าสีเขียวลงในทั้งค่าสีแดงและสีน้ำเงิน ไม่มีข้อมูลที่เชื่อมโยงกับการเปลี่ยนรูปแบบนี้ ตัวถอดรหัสจะใช้การเปลี่ยนรูปแบบย้อนกลับดังนี้

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

การแปลงนี้ซ้ำซ้อนเนื่องจากสามารถประมาณโดยใช้การแปลงสีได้ แต่เนื่องจากไม่มีข้อมูลเพิ่มเติม เราสามารถเข้ารหัสการแปลงลบสีเขียวโดยใช้บิตน้อยกว่าการแปลงสีแบบเต็มรูปแบบ

4.4 การเปลี่ยนรูปแบบการจัดทำดัชนีสี

หากค่าพิกเซลที่ไม่ซ้ำกันมีไม่มากนัก วิธีสร้างอาร์เรย์ดัชนีสีและแทนที่ค่าพิกเซลด้วยดัชนีของอาร์เรย์อาจมีประสิทธิภาพมากกว่า ซึ่งการแปลงการจัดทําดัชนีสีจะทําให้บรรลุเป้าหมายนี้ได้ (ในบริบทของ WebP แบบไม่สูญเสียข้อมูล เราไม่ได้เรียกการแปลงนี้ว่าการเปลี่ยนจานสีโดยเฉพาะ เนื่องจากมีแนวคิดที่คล้ายกันแต่มีความยืดหยุ่นมากกว่าในการเข้ารหัส WebP แบบไม่สูญเสียข้อมูล ซึ่งก็คือแคชสี)

การแปลงการจัดทำดัชนีสีจะตรวจสอบจํานวนค่า ARGB ที่ไม่ซ้ำกันในรูปภาพ หากตัวเลขนั้นต่ำกว่าเกณฑ์ (256) ระบบจะสร้างอาร์เรย์ของค่า ARGB เหล่านั้น จากนั้นจะใช้เพื่อแทนที่ค่าพิกเซลด้วยดัชนีที่สอดคล้องกัน โดยระบบจะแทนที่ช่องสีเขียวของพิกเซลด้วยดัชนี ตั้งค่าค่าอัลฟาทั้งหมดเป็น 255 และค่าสีแดงและสีน้ำเงินทั้งหมดเป็น 0

ข้อมูลการแปลงประกอบด้วยขนาดตารางสีและรายการในสี ตัวถอดรหัสจะอ่านข้อมูลการเปลี่ยนรูปแบบการจัดทําดัชนีสีดังนี้

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

ระบบจะจัดเก็บตารางสีโดยใช้รูปแบบพื้นที่เก็บข้อมูลรูปภาพ ตารางสี หาได้โดยการอ่านรูปภาพ โดยไม่มีส่วนหัว RIFF, ขนาดรูปภาพ และ จะเปลี่ยนรูปแบบ โดยสมมติว่ามีความสูง 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 บ่งบอกว่ามีการรวมพิกเซล 2 รายการเข้าด้วยกัน และแต่ละพิกเซลมีช่วง [0..15] ค่า 2 หมายความว่า รวม 4 พิกเซล และแต่ละพิกเซลมีช่วงอยู่ที่ [0..3] ค่า 3 บ่งชี้ว่ารวมพิกเซล 8 รายการเข้าด้วยกัน และแต่ละพิกเซลมีช่วง [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 บทบาทของข้อมูลรูปภาพ

เราใช้ข้อมูลรูปภาพในบทบาทที่แตกต่างกัน 5 บทบาท ดังนี้

1. รูปภาพ ARGB: จัดเก็บพิกเซลจริงของรูปภาพ
2. รูปภาพ Entropy: จัดเก็บรหัสคำนำหน้าเมตา (ดู"การถอดรหัสรหัสคำนำหน้าเมตา")
3. รูปภาพตัวทำนาย: จัดเก็บข้อมูลเมตาสําหรับการเปลี่ยนรูปแบบตัวทำนาย (ดู"การเปลี่ยนรูปแบบตัวทำนาย")
4. รูปภาพเปลี่ยนรูปแบบสี: สร้างด้วยค่า ColorTransformElement (มีคำจำกัดความใน "Color Transform") สำหรับบล็อกต่างๆ ของรูปภาพ
5. รูปภาพการจัดทําดัชนีสี: อาร์เรย์ขนาด color_table_size (สูงสุด 256) ค่า ARGB) ที่จัดเก็บข้อมูลเมตาสำหรับการเปลี่ยนรูปแบบการจัดทำดัชนีสี (โปรดดู "การเปลี่ยนการจัดทำดัชนีสี")

5.2 การเข้ารหัสข้อมูลรูปภาพ

การเข้ารหัสข้อมูลรูปภาพไม่ขึ้นอยู่กับบทบาทของรูปภาพ

ภาพจะถูกแบ่งออกเป็นชุดบล็อกขนาดคงที่ (โดยปกติคือ 16x16) บล็อก) แต่ละบล็อกเหล่านี้จะจําลองโดยใช้รหัสเอนโทรปีของตนเอง และ บล็อกหลายบล็อกอาจใช้โค้ดเอนโทรปีเดียวกัน

เหตุผล: การจัดเก็บรหัสเอนโทรปีมีค่าใช้จ่าย ค่าใช้จ่ายนี้สามารถลดได้หากบล็อกที่คล้ายกันทางสถิติใช้รหัสเอนโทรปีเดียวกัน จึงจัดเก็บรหัสดังกล่าวเพียงครั้งเดียว เช่น โปรแกรมเปลี่ยนไฟล์จะค้นหาบล็อกที่คล้ายกันได้โดยการจัดกลุ่มบล็อกเหล่านั้น โดยใช้คุณสมบัติทางสถิติ หรือโดยการสุ่มจับคู่ คลัสเตอร์ที่เลือกเมื่อลดจำนวนบิตโดยรวมที่ต้องใช้ในการเข้ารหัส รูปภาพ

แต่ละพิกเซลจะเข้ารหัสโดยใช้ 1 ใน 3 วิธีที่เป็นไปได้ดังนี้

1. ลิเทอรัลที่เข้ารหัสคำนำหน้า: แต่ละแชแนล (สีเขียว แดง น้ำเงิน และอัลฟา) คือ ด้วยการเข้ารหัสเอนโทรปีอย่างอิสระ
2. LZ77 การอ้างอิงแบบย้อนหลัง: ลำดับพิกเซลถูกคัดลอกมาจากตำแหน่งอื่นใน รูปภาพ
3. โค้ดแคชสี: การใช้รหัสแฮชแบบคูณสั้นๆ (แคชสี ดัชนี) ของสีที่ปรากฏล่าสุด

ส่วนย่อยต่อไปนี้จะอธิบายแต่ละข้ออย่างละเอียด

5.2.1 ลิเทอรัลที่มีรหัสคำนำหน้า

ระบบจะจัดเก็บพิกเซลเป็นค่าที่มีรหัสนำหน้าเป็นสีเขียว แดง น้ำเงิน และแอลฟา (ตามลำดับดังกล่าว) ดูรายละเอียดที่ส่วนที่ 6.2.3

5.2.2 LZ77 ข้อมูลอ้างอิงย้อนหลัง

การอ้างอิงย้อนหลังคือคู่ของความยาวและรหัสระยะทาง ดังนี้

• ความยาวระบุจำนวนพิกเซลตามลําดับเส้นสแกนที่จะคัดลอก
• รหัสระยะห่างคือตัวเลขที่ระบุตําแหน่งของพิกเซลที่มองเห็นก่อนหน้านี้ ซึ่งระบบจะคัดลอกพิกเซลจากตําแหน่งนั้น การแมปที่แน่นอนจะอธิบายไว้ด้านล่าง

ค่าความยาวและระยะทางจะจัดเก็บโดยใช้การเขียนโค้ดคำนำหน้า LZ77

การเขียนโค้ดคำนำหน้า LZ77 จะแบ่งค่าจำนวนเต็มขนาดใหญ่ออกเป็น 2 ส่วน ได้แก่ คำนำหน้า โค้ดและบิตพิเศษ ระบบจะจัดเก็บรหัสนำหน้าโดยใช้รหัสเอนโทรปี ส่วนบิตส่วนเกินจะจัดเก็บตามที่เป็นอยู่ (ไม่มีรหัสเอนโทรปี)

เหตุผล: วิธีนี้ช่วยลดความต้องการพื้นที่เก็บข้อมูลสำหรับเอนโทรปี โค้ด นอกจากนี้ ค่าขนาดใหญ่มักมีไม่มากนัก จึงต้องใช้บิตเพิ่มเติมสำหรับค่าจำนวนน้อยมากในรูปภาพ ดังนั้นแนวทางนี้ส่งผลให้การบีบอัดได้ดีขึ้น โดยรวม

ตารางต่อไปนี้แสดงรหัสคำนำหน้าและบิตเพิ่มเติมที่ใช้สำหรับจัดเก็บค่าในช่วงต่างๆ

หมายเหตุ: ความยาวสูงสุดของการอ้างอิงย้อนหลังถูกจำกัดไว้ที่ 4096 ดังนั้น เฉพาะรหัสนำหน้า 24 รายการแรก (ที่มีบิตเพิ่มเติมที่เกี่ยวข้อง) เท่านั้นที่มีความหมายสำหรับค่าความยาว แต่สำหรับค่าระยะทาง จะใช้รหัสนำหน้าทั้งหมด 40 รหัสได้

ช่วงของค่า	รหัสคำนำหน้า	บิตเพิ่มเติม
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 คอลัมน์ทางด้านขวาของพิกเซลปัจจุบัน [จํานวนรวมของ Pixel ดังกล่าว = 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 การเข้ารหัสแคชสี

แคชสีจะจัดเก็บชุดสีที่ใช้ล่าสุดในรูปภาพ

เหตุผล: วิธีนี้ทำให้บางครั้งสีที่ใช้ล่าสุดอาจหมายถึง มีประสิทธิภาพมากกว่าการปล่อยเนื้อหาโดยใช้อีก 2 วิธี (อธิบายไว้ใน 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 ไว้ 1 ชุด สี ระบบจะค้นหาสีโดยการจัดทำดัชนีสีภายใน (0x1e35a7bd * color) >> (32 - color_cache_code_bits) ระบบจะทำการค้นหาเพียงครั้งเดียวในแคชสี ไม่มีการแก้ไขข้อขัดแย้ง

ในช่วงเริ่มต้นของการถอดรหัสหรือการเข้ารหัสรูปภาพ ระบบจะตั้งค่ารายการทั้งหมดในค่าแคชสีทั้งหมดเป็น 0 ระบบจะแปลงรหัสแคชสีเป็นสีนี้เมื่อถอดรหัส สถานะของแคชสีจะรักษาไว้โดยการแทรกทุก พิกเซลจะสร้างขึ้นโดยการอ้างอิงย้อนหลังหรือเป็นลิเทอรัลลงในแคชใน ตามลำดับที่ปรากฏในสตรีม

6 โค้ดเอนโทรปี

6.1 ภาพรวม

ข้อมูลส่วนใหญ่จะเขียนโค้ดโดยใช้โค้ดคำนำหน้า Canonical ดังนั้น จะมีการส่งรหัสโดยการส่งความยาวของโค้ดคำนำหน้าเป็น ซึ่งไม่ใช่รหัสคำนำหน้าจริง

โดยเฉพาะอย่างยิ่ง รูปแบบนี้จะใช้การเขียนโค้ดคำนำหน้าของตัวแปรเชิงพื้นที่ ในอีก รูปภาพบล็อกต่างๆ อาจใช้เอนโทรปีที่แตกต่างกัน

เหตุผล: พื้นที่ต่างๆ ของรูปภาพอาจมีลักษณะที่แตกต่างกัน ดังนั้น การให้ใช้รหัสเอนโทรปีที่แตกต่างกันจึงมีความยืดหยุ่นมากขึ้นและอาจมีการบีบอัดที่ดีขึ้น

6.2 รายละเอียด

ข้อมูลรูปภาพที่เข้ารหัสประกอบด้วยหลายส่วน ดังนี้

1. การถอดรหัสและการสร้างรหัสคำนำหน้า
2. โค้ดคำนำหน้าเมตา
3. ข้อมูลรูปภาพที่เข้ารหัสด้วยเอนโทรปี

สำหรับพิกเซลหนึ่งๆ (x, y) จะมีชุดรหัสนำหน้าห้ารหัสที่เกี่ยวข้องกับ ได้ รหัสเหล่านี้มีดังนี้ (ตามลำดับบิตสตรีม)

• รหัสคำนำหน้า #1: ใช้สำหรับช่องสีเขียว ความยาวอ้างอิงย้อนหลัง และ แคชสี
• รหัสคำนำหน้า #2, #3 และ #4: ใช้สำหรับแชแนลสีแดง น้ำเงิน และอัลฟา ตามลำดับ
• รหัสนำหน้า #5: ใช้สำหรับระยะการอ้างอิงย้อนหลัง

จากนี้ไป เราจะเรียกชุดนี้ว่ากลุ่มโค้ดคำนำหน้า

6.2.1 การถอดรหัสและการสร้างรหัสคำนำหน้า

ส่วนนี้จะอธิบายวิธีอ่านความยาวของรหัสนำหน้าจากบิตสตรีม

ความยาวของรหัสนำหน้าสามารถเขียนโค้ดได้ 2 วิธี ระบุวิธีการที่ใช้แล้ว ด้วยค่า 1 บิต

• หากบิตนี้เป็น 1 แสดงว่าเป็นรหัสความยาวโค้ดแบบง่าย
• หากบิตนี้เป็น 0 แสดงว่าเป็นรหัสความยาวโค้ดปกติ

ไม่ว่าจะในกรณีใด อาจมีความยาวโค้ดที่ไม่ได้ใช้ซึ่งยังคงเป็นส่วนหนึ่งของสตรีม วิธีนี้อาจไร้ประสิทธิภาพ แต่รูปแบบอนุญาตให้ใช้ได้ แผนผังที่อธิบายต้องเป็นแผนผังไบนารีที่สมบูรณ์ โหนดด้านเดียวคือ เป็นแผนผังไบนารีที่สมบูรณ์และสามารถเข้ารหัสได้โดยใช้ รหัสความยาวรหัสหรือรหัสความยาวรหัสปกติ เมื่อเขียนโค้ดแบบด้านเดียว ที่ใช้โค้ดความยาวโค้ดปกติ แต่ความยาวโค้ดแค่ 0 หลักเท่านั้น และค่าโหนดเดี่ยวๆ จะมีความยาวเท่ากับ 1 แม้ว่าจะไม่มี ระบบจะใช้บิตต่างๆ เมื่อมีการใช้แผนผังโหนดแบบใบเดี่ยวนั้น

โค้ดความยาวโค้ดแบบง่าย

ตัวแปรนี้ใช้ในกรณีพิเศษเมื่อมีสัญลักษณ์นำหน้าเพียง 1 หรือ 2 ตัว ช่วง [0..255] ที่มีความยาวโค้ด 1 ความยาวรหัสคำนำหน้าอื่นๆ ทั้งหมดจะถือว่ามีค่าเป็น 0 โดยปริยาย

บิตแรกระบุจํานวนสัญลักษณ์

int num_symbols = ReadBits(1) + 1;

ค่าสัญลักษณ์มีดังนี้

สัญลักษณ์แรกนี้เข้ารหัสโดยใช้ 1 หรือ 8 บิต ทั้งนี้ขึ้นอยู่กับค่าของ is_first_8bits ช่วงคือ [0..1] หรือ [0..255] ตามลำดับ องค์ประกอบที่ 2 หากมี จะถือว่าอยู่ในช่วง [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 จะแสดงค่าที่ไม่ใช่ 0 ก่อนหน้า [3..6] ซ้ำ ซึ่งก็คือ 3 + ReadBits(2) ครั้ง หากใช้รหัส 16 ก่อนที่จะมีการส่งค่าที่ไม่ใช่ 0 ระบบจะส่งค่า 8 ซ้ำ
• โค้ด 17 ทำให้เกิดความยาวเลข 0 ติดต่อกัน [3..10] ซึ่งก็คือ 3 + ReadBits(3) ครั้ง
• โค้ด 18 กระจายความยาวเป็นศูนย์ [11..138] ซึ่งก็คือ 11 + ReadBits(7) ครั้ง

เมื่ออ่านความยาวของรหัสแล้ว รหัสนำหน้าสำหรับสัญลักษณ์แต่ละประเภท (A, R, G, B และ ระยะทาง) จะสร้างขึ้นโดยใช้ขนาดตัวอักษรที่เกี่ยวข้อง

รหัสความยาวโค้ดปกติต้องเข้ารหัสแผนภูมิการตัดสินใจแบบสมบูรณ์ กล่าวคือผลรวมของ 2 ^ (-length) สำหรับรหัสทั้งหมดที่ไม่ใช่ 0 ต้องเป็น 1 เท่านั้น อย่างไรก็ตาม มี ข้อยกเว้นประการหนึ่งของกฎนี้คือต้นโหนด Leaf เดี่ยว จะมีค่า 1 กำกับไว้ และค่าอื่นๆ เป็น 0s

6.2.2 การถอดรหัสโค้ดคำนำหน้าเมตา

ตามที่ระบุไว้ก่อนหน้านี้ รูปแบบนี้สามารถใช้รหัสนำหน้าที่แตกต่างกันสำหรับ บล็อกต่างๆ ของรูปภาพ โค้ดคำนำหน้าเมตา คือดัชนีที่ระบุว่า รหัสนําหน้าเพื่อใช้ในส่วนต่างๆ ของรูปภาพ

คุณจะใช้รหัสคำนำหน้าเมตาได้เฉพาะเมื่อใช้รูปภาพในบทบาทของรูปภาพ ARGB

รหัสคำนำหน้าเมตามี 2 รูปแบบ ซึ่งระบุด้วยค่า 1 บิต ดังนี้

• หากบิตนี้เป็น 0 แสดงว่ามีการใช้รหัสคำนำหน้าเมตาเพียงรหัสเดียวในทุกตำแหน่งในรูปภาพ โดยจะไม่จัดเก็บข้อมูลเพิ่มเติม
• หากบิตนี้เป็นบิตเดียว รูปภาพจะใช้รหัสคำนำหน้าเมตาหลายรหัส เมตาเหล่านี้ โค้ดคำนำหน้าจะจัดเก็บเป็นรูปภาพเอนโทรปี (ตามที่อธิบายไว้ด้านล่าง)

ส่วนประกอบสีแดงและสีเขียวของพิกเซลจะกำหนดโค้ดคำนำหน้าเมตา 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) หมายถึงรหัสนำหน้าที่ใหญ่ที่สุดซึ่งจัดเก็บไว้ใน รูปภาพเอนโทรปี

เนื่องจากกลุ่มรหัสคำนำหน้าแต่ละกลุ่มมีรหัสนำหน้า 5 รหัส จำนวนคำนำหน้าทั้งหมด คือ

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 ซึ่งแสดงถึงชุดรหัสคำนำหน้า 5 รายการ นอกจากนี้ prefix_code_groups ยังเป็นอาร์เรย์ของ PrefixCodeGroup (ขนาด num_prefix_groups)

จากนั้นตัวถอดรหัสจะใช้กลุ่มโค้ดคำนำหน้า prefix_group เพื่อถอดรหัสพิกเซล (x, y) ตามที่อธิบายไว้ใน "การถอดรหัสเอนโทรปี-โค้ดรูปภาพ Data"

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 & วิ 256 + 24
   1. ใช้ S - 256 เป็นรหัสนำหน้าความยาว
   2. อ่านบิตเพิ่มเติมเพื่อความยาวจากบิตสตรีม
   3. กำหนดความยาวการอ้างอิงย้อนหลัง L จากรหัสนำหน้าความยาวและบิตเพิ่มเติมที่อ่าน
   4. อ่านรหัสคำนำหน้าระยะทางจากบิตสตรีมโดยใช้รหัสนำหน้า #5
   5. อ่านบิตเพิ่มเติมระยะทางจากบิตสตรีม
   6. กำหนดระยะทางอ้างอิงย้อนหลัง D จากโค้ดคำนำหน้าระยะทาง และบิตพิเศษที่อ่านได้
   7. คัดลอกพิกเซล L (ตามลำดับบรรทัดสแกน) จากลำดับพิกเซลเริ่มต้น ที่ตำแหน่งปัจจุบันลบ D พิกเซล
3. If S >= 256 + 24
   1. ใช้ S - (256 + 24) เป็นดัชนีในแคชสี
   2. หาสี ARGB จากแคชสีที่ดัชนีดังกล่าว

7 โครงสร้างโดยรวมของรูปแบบ

ด้านล่างนี้คือมุมมองรูปแบบใน Augmented Backus-Naur Form (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