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

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

บทคัดย่อ

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

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 มิติที่ระบุว่าใช้ตัวทำนายเชิงพื้นที่ใด สำหรับสี่เหลี่ยมจัตุรัสหนึ่งๆ ในรูปภาพ

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

วิธีคลาสสิกในการทำ Entropy Coding ซึ่งใช้จำนวนบิตน้อยลง สำหรับโค้ดที่พบบ่อยกว่า

การเข้ารหัสคำนำหน้า

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

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

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

3 ส่วนหัว RIFF

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

1. สตริง "RIFF"
2. ค่า 32 บิตแบบ Little-Endian ของความยาวของ Chunk ซึ่งเป็นขนาดทั้งหมด ของ Chunk ที่ควบคุมโดยส่วนหัว 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✕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 ที่ระบุจุดสิ้นสุดของการแปลง

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

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

// Decode actual image data (Section 5).

หากมีการเปลี่ยนรูปแบบ บิต 2 บิตถัดไปจะระบุประเภทการเปลี่ยนรูปแบบ การแปลงมี 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 ทั้งหมดจะยังไม่ทราบ

เมื่อพิจารณาจากพิกเซลข้างเคียงก่อนหน้า โหมดการคาดคะเนต่างๆ จะ กำหนดไว้ดังนี้

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

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

ตัวเลือกตัวทำนายมีการกำหนดดังนี้

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

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

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

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

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

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

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

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

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

การระบุ TR-pixel สำหรับพิกเซลในคอลัมน์ขวาสุดเป็น ข้อยกเว้น พิกเซลในคอลัมน์ขวาสุดจะได้รับการคาดการณ์โดยใช้โหมด [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;

การแปลงสีจริงจะทำโดยการกำหนดเดลต้าการแปลงสี เดลต้าการแปลงสีขึ้นอยู่กับ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 บิต) คุณสมบัติการขยายเครื่องหมายของการดำเนินการเลื่อนไม่มีผลที่นี่ เนื่องจากจะใช้เฉพาะ 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 เหล่านั้น จากนั้นจะใช้เพื่อแทนที่ค่าพิกเซลด้วยดัชนีที่สอดคล้องกัน โดยจะแทนที่แชแนลสีเขียวของพิกเซลด้วยดัชนี กำหนดค่า Alpha ทั้งหมดเป็น 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 (มอด 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. รูปภาพเอนโทรปี: จัดเก็บรหัสคำนำหน้าเมตา (ดู"การถอดรหัสรหัสคำนำหน้าเมตา")
3. รูปภาพตัวทำนาย: จัดเก็บข้อมูลเมตาสำหรับการเปลี่ยนรูปแบบตัวทำนาย (ดู"การเปลี่ยนรูปแบบตัวทำนาย")
4. รูปภาพการเปลี่ยนสี: สร้างขึ้นโดยใช้ค่า ColorTransformElement (กำหนดไว้ใน "การเปลี่ยนสี") สำหรับบล็อกต่างๆ ของรูปภาพ
5. รูปภาพการจัดทำดัชนีสี: อาร์เรย์ที่มีขนาด color_table_size (ค่า ARGB สูงสุด 256 ค่า) ซึ่งจัดเก็บข้อมูลเมตาสำหรับการเปลี่ยนการจัดทำดัชนีสี (ดู"การเปลี่ยนการจัดทำดัชนีสี")

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

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

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

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

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

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

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

5.2.1 อักษรตามตัวที่เข้ารหัสคำนำหน้า

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

5.2.2 การอ้างอิงย้อนกลับ LZ77

การอ้างอิงย้อนกลับคือทูเพิลของความยาวและรหัสระยะทาง:

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

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

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

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

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

ซูโดโค้ดเพื่อรับค่า (ความยาวหรือระยะทาง) จากรหัสคำนำหน้ามีดังนี้

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 การเข้ารหัสแคชสี

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

เหตุผล: วิธีนี้ช่วยให้บางครั้งสามารถอ้างอิงสีที่ใช้ล่าสุดได้อย่างมีประสิทธิภาพมากกว่าการปล่อยสีโดยใช้วิธีอื่นๆ อีก 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 ภาพรวม

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

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

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

6.2 รายละเอียด

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

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

สำหรับพิกเซล (x, y) ใดๆ จะมีชุดรหัสคำนำหน้า 5 ชุดที่เชื่อมโยงกับพิกเซลนั้น รหัสเหล่านี้ (ตามลำดับบิตสตรีม) ได้แก่

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

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

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

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

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

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

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

สัญลักษณ์ทั้ง 2 ควรแตกต่างกัน อนุญาตให้ใช้สัญลักษณ์ซ้ำกันได้ แต่ ไม่มีประสิทธิภาพ

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

รหัสความยาวปกติ

ความยาวของรหัสคำนำหน้าจะพอดีกับ 8 บิต และอ่านได้ดังนี้ โดย num_code_lengths จะระบุจำนวนความยาวของรหัส

int num_code_lengths = 4 + ReadBits(4);

ความยาวของรหัสจะได้รับการเข้ารหัสโดยใช้รหัสคำนำหน้า คุณต้องอ่านความยาวของรหัสระดับล่าง code_length_code_lengths ก่อน ส่วนที่เหลือของ code_length_code_lengths (ตามลำดับใน kCodeLengthCodeOrder) จะเป็น 0

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

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

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

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

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

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

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

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

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

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

รูปภาพเอนโทรปีจะกำหนดว่าใช้รหัสคำนำหน้าใดในส่วนต่างๆ ของรูปภาพ

บิต 3 บิตแรกมีprefix_bits value ขนาดของภาพเอนโทรปี ได้มาจาก 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) ตามที่อธิบายไว้ใน "การถอดรหัสข้อมูลรูปภาพที่เข้ารหัสเอนโทรปี"

6.2.3 การถอดรหัสข้อมูลรูปภาพที่เข้ารหัสเอนโทรปี

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

จากนั้นอ่านสัญลักษณ์ S จากบิตสตรีมโดยใช้รหัสคำนำหน้า #1 โปรดทราบว่า S คือ จำนวนเต็มใดก็ได้ในช่วง 0 ถึง (256 + 24 + color_cache_size- 1)

การตีความ S ขึ้นอยู่กับค่าของ 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 โครงสร้างโดยรวมของรูปแบบ

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