ข้อกำหนดสำหรับ 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);

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

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

แคชสี

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

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

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

ภาพแปลงสี

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

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

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

ภาพเอนโทรปี

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

LZ77

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

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

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

รูปภาพตัวคาดการณ์

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

รหัสนำหน้า

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

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

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

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

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

ส่วนหัว RIFF จำนวน 3 ชุด

ส่วนต้นของส่วนหัวมีคอนเทนเนอร์ 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 ถัดจาก6384 พิกเซล

บิต 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 ทั้งหมด

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

โหมด	ค่าที่คาดการณ์ไว้ของแต่ละแชแนลของพิกเซลปัจจุบัน
0	0xff000000 (แสดงสีดำทึบใน ARGB)
1	L
2	T
3	ลีราตุรกี (TRY)
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	Select(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

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

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

ตัวคาดคะเน "เลือก" มีการกำหนดไว้ดังนี้

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

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

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

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

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

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

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

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

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

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

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

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 บิต) คุณสมบัติส่วนขยายเครื่องหมายของการดำเนินการ Shift จะไม่คำนึงถึงในส่วนนี้ เนื่องจากผลลัพธ์จะใช้เพียง 8 บิตต่ำสุด และส่วนขยายสัญลักษณ์ที่ขยับและการขยับที่ไม่มีสัญลักษณ์จะสอดคล้องกัน

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

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

ข้อมูลการเปลี่ยนแปลงสีที่เหลือประกอบด้วยอินสแตนซ์ ColorTransformElement ตามบล็อกของรูปภาพแต่ละบล็อก ระบบจะถือว่า 'cte' แต่ละรายการของ ColorTransformElement เป็นพิกเซลในรูปภาพความละเอียดย่อยที่มีคอมโพเนนต์อัลฟ่าเท่ากับ 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 รับข้อมูล x (ม็อด 2) ค่าสีเขียวที่ x จะจัดตำแหน่งเป็นบิตที่มีนัยสำคัญน้อยที่สุด 4 บิตของค่าสีเขียวที่ x / 2 และค่าสีเขียวที่ x + 1 จะจัดตำแหน่งให้บิตที่สำคัญที่สุด 4 บิตของค่าสีเขียวที่ x / 2
• width_bits = 2: สำหรับค่า x ทุกๆ ค่า โดยที่ x zh 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 (กำหนดไว้ใน "Color Transform") สำหรับบล็อกต่างๆ ของรูปภาพ
5. รูปภาพการจัดทำดัชนีสี: อาร์เรย์ขนาด color_table_size (ค่า ARGB สูงสุด 256 ค่า) ที่จัดเก็บข้อมูลเมตาสำหรับการเปลี่ยนรูปแบบการจัดทำดัชนีสี (ดู "การเปลี่ยนรูปแบบการจัดทำดัชนีสี")

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

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

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

6.1 ภาพรวม

ข้อมูลส่วนใหญ่เข้ารหัสโดยใช้รหัสนำหน้า Canonical ดังนั้นระบบจะส่งรหัสให้คุณโดยการส่งความยาวของรหัสคำนำหน้า ซึ่งตรงข้ามกับรหัสคำนำหน้าจริง

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

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

6.2 รายละเอียด

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

โค้ดนำหน้าเมตามี 2 แบบที่แสดงด้วยค่า 1 บิต ดังนี้

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

เนื่องจากกลุ่มรหัสคำนำหน้าแต่ละกลุ่มมีรหัสนำหน้า 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 ขึ้นอยู่กับค่าดังนี้

1. หาก S < 256
   1. ใช้ S เป็นองค์ประกอบสีเขียว
   2. อ่านสีแดงจาก Bitstream โดยใช้รหัสนำหน้า #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