Jyrki Alakuijala, Ph.D., Google Inc. 09-03-2023
บทคัดย่อ
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
- แคชสี
- อาร์เรย์ที่ระบุแฮชขนาดเล็กสำหรับจัดเก็บสีที่ใช้ล่าสุดเพื่อให้ ก็เรียกรหัสที่สั้นลง
- รูปภาพการจัดทำดัชนีสี
- รูปภาพขนาดเดียวของสีที่จัดทำดัชนีได้โดยใช้จำนวนเต็มขนาดเล็ก (สูงสุด 256 ภายใน WebP แบบไม่สูญเสียรายละเอียด)
- รูปภาพเปลี่ยนสี
- รูปภาพย่อยแบบ 2 มิติที่มีข้อมูลเกี่ยวกับสหสัมพันธ์ของ ส่วนประกอบของสี
- การแมประยะทาง
- เปลี่ยนระยะทาง LZ77 ให้มีค่าต่ำสุดสำหรับพิกเซลใน ความใกล้ชิดแบบ 2 มิติ
- รูปภาพเอนโทรปี
- รูปภาพย่อยแบบ 2 มิติที่ระบุว่าการเขียนโค้ดเอนโทรปีใดควร ใช้ในสี่เหลี่ยมจัตุรัสที่เกี่ยวข้องในรูปภาพ นั่นคือแต่ละพิกเซลคือเมตา รหัสนำหน้า
- LZ77
- อัลกอริทึมการบีบอัดหน้าต่างเลื่อนแบบพจนานุกรม ซึ่งจะปล่อย หรืออธิบายเป็นลำดับสัญลักษณ์ในอดีต
- รหัสคำนำหน้าเมตา
- จำนวนเต็มขนาดเล็ก (สูงสุด 16 บิต) ที่จัดทำดัชนีองค์ประกอบในคำนำหน้าเมตา ตาราง
- รูปภาพตัวคาดการณ์
- รูปภาพความละเอียดย่อย 2 มิติที่ระบุว่าตัวคาดการณ์เชิงพื้นที่ใด ที่ใช้กับสี่เหลี่ยมจัตุรัสในรูปภาพ
- รหัสนำหน้า
- วิธีการเข้ารหัสเอนโทรปีแบบคลาสสิกที่ใช้จำนวนบิตน้อย เพื่อดูรหัสบ่อยขึ้น
- การเข้ารหัสคำนำหน้า
- วิธีเข้ารหัสจำนวนเต็มที่ใหญ่กว่า ซึ่งจะเข้ารหัสจำนวนเต็มไม่กี่บิต โดยใช้โค้ดเอนโทรปีและเข้ารหัสบิตที่เหลือเป็นข้อมูลดิบ ซึ่งช่วยให้ คำอธิบายของโค้ดเอนโทรปีจะยังคง มีขนาดเล็กแม้ในขณะที่ สัญลักษณ์ที่ใช้จะมีช่วงสัญญาณเยอะ
- ลำดับบรรทัดสแกน
- ลำดับการประมวลผลของพิกเซล (จากซ้ายไปขวาและบนลงล่าง) เริ่มต้น จากพิกเซลด้านบนซ้าย เมื่อแถวเสร็จสมบูรณ์แล้ว ให้ดำเนินการต่อจาก คอลัมน์ด้านซ้ายของแถวถัดไป
ส่วนหัว RIFF 3 รายการ
จุดเริ่มต้นของส่วนหัวมีคอนเทนเนอร์ RIFF ซึ่งประกอบด้วย 21 ไบต์ต่อไปนี้
- สตริง "RIFF"
- ค่า 32 บิตของความยาวช่องที่เป็นช่องปลายน้อยซึ่งเป็นขนาดทั้งหมด ของกลุ่มที่ควบคุมโดยส่วนหัว RIFF โดยปกติแล้ว ค่านี้เท่ากับ ขนาดเพย์โหลด (ขนาดไฟล์ลบ 8 ไบต์: 4 ไบต์สำหรับ "RIFF" และ 4 ไบต์สำหรับจัดเก็บค่านั้น)
- สตริง "WEBP" (ชื่อคอนเทนเนอร์ RIFF)
- สตริง "VP8L" (FourCC สำหรับข้อมูลรูปภาพที่เข้ารหัสแบบไม่สูญเสียรายละเอียด)
- ค่า 32 บิตของจำนวนไบต์ใน แบบไม่สูญเสียรายละเอียด
- ลายเซ็น 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).
หากมีการเปลี่ยนรูปแบบ สองบิตถัดไปจะระบุประเภทการเปลี่ยนรูปแบบ การเปลี่ยนรูปแบบมี 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 โหมด ในโหมดการคาดการณ์แต่ละโหมด พารามิเตอร์ ค่าพิกเซลถูกคาดการณ์จากพิกเซลใกล้เคียงอย่างน้อยหนึ่งพิกเซลซึ่งมีค่าเท่ากับ อยู่แล้ว
เราเลือกพิกเซลใกล้เคียง (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 | เลือก(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-pixel และพิกเซลทั้งหมดในคอลัมน์ซ้ายสุดคือ T-pixel
การจัดการพิกเซล TR สำหรับพิกเซลในคอลัมน์ขวาสุดคือ ยอดเยี่ยม ระบบจะคาดการณ์พิกเซลในคอลัมน์ขวาสุดโดยใช้โหมด [0..13] เช่นเดียวกับพิกเซลที่ไม่ได้อยู่บนเส้นขอบ แต่เป็นพิกเซลด้านซ้ายสุดบน แถวเดียวกับพิกเซลปัจจุบันจะใช้เป็นพิกเซล TR แทน
ค่าพิกเซลสุดท้ายได้มาจากการบวกแต่ละแชแนลของค่าที่คาดการณ์ กับค่าที่เหลือที่เข้ารหัส
void PredictorTransformOutput(uint32 residual, uint32 pred,
uint8* alpha, uint8* red,
uint8* green, uint8* blue) {
*alpha = ALPHA(residual) + ALPHA(pred);
*red = RED(residual) + RED(pred);
*green = GREEN(residual) + GREEN(pred);
*blue = BLUE(residual) + BLUE(pred);
}
4.2 การเปลี่ยนสี
เป้าหมายของการเปลี่ยนรูปแบบสีคือการตกแต่งค่า R, G และ B ของแต่ละค่า พิกเซล การเปลี่ยนรูปแบบสีจะคงค่าสีเขียว (G) ไว้ตามเดิม และเปลี่ยนค่า สีแดง (R) โดยอิงตามค่าสีเขียวและแปลงค่าสีน้ำเงิน (B) ตาม ค่าสีเขียว ตามด้วยค่าสีแดง
เช่นเดียวกับกรณีของการแปลงตัวคาดการณ์ รูปภาพจะถูกแบ่งเป็น และใช้โหมดการเปลี่ยนรูปแบบเดียวกันสำหรับพิกเซลทั้งหมดในบล็อก สำหรับ ในแต่ละบล็อก จะมีองค์ประกอบการเปลี่ยนสีอยู่ 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()
ค่าที่ลงนาม
ควรแปลค่าว่าเป็นหมายเลขเสริมของ 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 แบบไม่สูญเสียรายละเอียด เรา อย่าเรียกสิ่งนี้ว่า Transform จานสีเพราะเหมือนกัน แนวคิดแบบไดนามิกมีอยู่ในการเข้ารหัสแบบไม่สูญเสียรายละเอียด 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) พิกเซลเป็นพิกเซลเดียว ซึ่งจะลดความกว้างของรูปภาพตามลำดับ พิกเซล bundling ทำให้สามารถเข้ารหัสเอนโทรปีในการกระจายร่วมของ ที่อยู่ข้างเคียง และให้ประโยชน์บางอย่างที่คล้ายการเข้ารหัสเลขคณิตกับ เอนโทรปีโค้ดได้ แต่จะสามารถใช้ได้เมื่อมีค่าที่ไม่ซ้ำกันไม่เกิน 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 / 2width_bits
= 2: สำหรับค่า x ทุกค่า โดย x ⋮ 0 (mod 4) สัญลักษณ์สีเขียว ค่าที่ x จะถูกวางไว้ใน 2 บิตที่มีนัยสำคัญน้อยที่สุดของ ค่าสีเขียวที่ x / 4 และค่าสีเขียวที่ x + 1 ถึง x + 3 มีตำแหน่งเป็น ให้เป็นบิตที่สำคัญมากกว่าของค่าสีเขียวที่ x / 4width_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 บทบาท ดังนี้
- รูปภาพ ARGB: จัดเก็บพิกเซลจริงของรูปภาพ
- อิมเมจเอนโทรปี: จัดเก็บโค้ดคำนำหน้าเมตา (โปรดดู "การถอดรหัสรหัสคำนำหน้าเมตา")
- อิมเมจตัวคาดการณ์: จัดเก็บข้อมูลเมตาสำหรับการแปลงตัวคาดการณ์ (โปรดดู "การเปลี่ยนรูปแบบการคาดการณ์")
- รูปภาพเปลี่ยนรูปแบบสี: สร้างด้วยค่า
ColorTransformElement
(มีคำจำกัดความใน "Color Transform") สำหรับบล็อกต่างๆ ของรูปภาพ - รูปภาพการจัดทําดัชนีสี: อาร์เรย์ขนาด
color_table_size
(สูงสุด 256 ARGB ) ที่จัดเก็บข้อมูลเมตาสำหรับการแปลงการจัดทำดัชนีสี (โปรดดู "การเปลี่ยนการจัดทำดัชนีสี")
5.2 การเข้ารหัสข้อมูลรูปภาพ
การเข้ารหัสข้อมูลรูปภาพไม่ขึ้นอยู่กับหน้าที่ของข้อมูล
ภาพจะถูกแบ่งออกเป็นชุดบล็อกขนาดคงที่ (โดยปกติคือ 16x16) บล็อก) บล็อกแต่ละรายการเหล่านี้สร้างโมเดลโดยใช้โค้ดเอนโทรปีของตัวเอง และ บล็อกหลายบล็อกอาจใช้โค้ดเอนโทรปีเดียวกัน
เหตุผล: การจัดเก็บโค้ดเอนโทรปีมีค่าใช้จ่าย ลดค่าใช้จ่ายนี้ลงได้ หากบล็อกที่มีลักษณะคล้ายกันทางสถิติใช้โค้ดเอนโทรปีร่วมกัน ก็จะเป็นการจัดเก็บโค้ดนั้น เพียงครั้งเดียวเท่านั้น เช่น โปรแกรมเปลี่ยนไฟล์จะค้นหาบล็อกที่คล้ายกันได้โดยการจัดกลุ่มบล็อกเหล่านั้น โดยใช้คุณสมบัติทางสถิติ หรือโดยการสุ่มจับคู่ คลัสเตอร์ที่เลือกเมื่อลดจำนวนบิตโดยรวมที่ต้องใช้ในการเข้ารหัส รูปภาพ
แต่ละพิกเซลจะเข้ารหัสโดยใช้ 1 ใน 3 วิธีที่เป็นไปได้ดังนี้
- ลิเทอรัลที่เข้ารหัสคำนำหน้า: แต่ละแชแนล (สีเขียว แดง น้ำเงิน และอัลฟา) คือ ด้วยการเข้ารหัสเอนโทรปีอย่างอิสระ
- LZ77 การอ้างอิงแบบย้อนหลัง: ลำดับพิกเซลถูกคัดลอกมาจากตำแหน่งอื่นใน รูปภาพ
- โค้ดแคชสี: การใช้รหัสแฮชแบบคูณสั้นๆ (แคชสี ดัชนี) ของสีที่ปรากฏล่าสุด
ส่วนย่อยต่อไปนี้จะอธิบายแต่ละข้ออย่างละเอียด
5.2.1 ลิเทอรัลที่มีโค้ดนำหน้า
พิกเซลจะจัดเก็บเป็นค่าที่เข้ารหัสด้วยคำนำหน้า ซึ่งประกอบด้วยสีเขียว แดง น้ำเงิน และอัลฟา (ใน คำสั่งซื้อนั้น) โปรดดูส่วนที่ 6.2.3 สำหรับ รายละเอียด
5.2.2 LZ77 ข้อมูลอ้างอิงย้อนหลัง
การอ้างอิงย้อนหลังคือคู่ของความยาวและรหัสระยะทาง ดังนี้
- ความยาวจะระบุจำนวนพิกเซลที่จะคัดลอกตามลำดับบรรทัดสแกน
- รหัสระยะทางคือตัวเลขที่ระบุตำแหน่งของสิ่งที่พบเห็นก่อนหน้านี้ พิกเซล ซึ่งจะคัดลอกพิกเซล การแมปที่ถูกต้องคือ ที่อธิบายไว้ด้านล่าง
ค่าความยาวและระยะทางจะจัดเก็บโดยใช้การเขียนโค้ดคำนำหน้า LZ77
การเขียนโค้ดคำนำหน้า LZ77 จะแบ่งค่าจำนวนเต็มขนาดใหญ่ออกเป็น 2 ส่วน ได้แก่ คำนำหน้า โค้ดและบิตพิเศษ โค้ดนำหน้าจัดเก็บโดยใช้เอนโทรปีโค้ด ในขณะที่จัดเก็บบิตพิเศษไว้ตามเดิม (โดยไม่มีโค้ดเอนโทรปี)
เหตุผล: วิธีนี้ช่วยลดความต้องการพื้นที่เก็บข้อมูลสำหรับเอนโทรปี โค้ด นอกจากนี้ ค่าที่มีขนาดใหญ่มักจะหายาก ดังนั้นจะมีการใช้บิตพิเศษ ในภาพมีไม่กี่ค่า ดังนั้นแนวทางนี้ส่งผลให้การบีบอัดได้ดีขึ้น โดยรวม
ตารางต่อไปนี้แสดงรหัสนำหน้าและบิตพิเศษที่ใช้ในการจัดเก็บ ช่วงของค่าที่แตกต่างกัน
ช่วงของค่า | โค้ดคำนำหน้า | บิตเพิ่มเติม |
---|---|---|
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 รายละเอียด
ข้อมูลรูปภาพที่เข้ารหัสประกอบด้วยส่วนต่างๆ ดังนี้
- การถอดรหัสและสร้างรหัสนำหน้า
- รหัสคำนำหน้าเมตา
- ข้อมูลรูปภาพที่เข้ารหัสเอนโทรปี
สำหรับพิกเซลหนึ่งๆ (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;
}
สัญลักษณ์ทั้งสองควรแตกต่างกัน อนุญาตให้ใช้สัญลักษณ์ซ้ำกันได้ แต่ ไม่มีประสิทธิภาพ
หมายเหตุ: กรณีพิเศษอีกกรณีคือเมื่อความยาวของโค้ดคำนำหน้าทั้งหมดเป็น 0er (an
ไม่มีรหัสนำหน้า) ตัวอย่างเช่น รหัสคำนำหน้าสำหรับระยะทางอาจเว้นว่างไว้ได้ในกรณีต่อไปนี้
จะไม่มีการอ้างอิงย้อนหลัง ในทำนองเดียวกัน รหัสคำนำหน้าสำหรับอัลฟ่า สีแดง และ
สีน้ำเงินอาจว่างเปล่าได้หากพิกเซลทั้งหมดภายในโค้ดคำนำหน้าเมตาเดียวกันมีการสร้าง
โดยใช้แคชสี แต่กรณีนี้ไม่จำเป็นต้องมีการจัดการพิเศษ
รหัสนำหน้าที่ว่างเปล่าสามารถเขียนโค้ดเป็นรหัสที่มีสัญลักษณ์เดียว 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 ทำให้เกิดความยาวเป็นศูนย์ [3..10] ติดต่อกัน
3 + ReadBits(3)
ครั้ง - โค้ด 18 กระจายความยาวเป็นศูนย์ [11..138] ซึ่งก็คือ
11 + ReadBits(7)
ครั้ง
เมื่ออ่านความยาวของรหัสแล้ว รหัสนำหน้าสำหรับสัญลักษณ์แต่ละประเภท (A, R, G, B และ ระยะทาง) จะสร้างขึ้นโดยใช้ขนาดตัวอักษรที่เกี่ยวข้อง
โค้ดความยาวโค้ดปกติต้องเขียนโค้ดโครงสร้างการตัดสินใจทั้งหมด ซึ่งก็คือผลรวมของ
2 ^ (-length)
สำหรับรหัสที่ไม่ใช่ 0 ทั้งหมดต้องเป็นรหัสเดียว อย่างไรก็ตาม มี
ข้อยกเว้นประการหนึ่งของกฎนี้คือต้นโหนด Leaf เดี่ยว
จะมีค่า 1 กำกับไว้ และค่าอื่นๆ เป็น 0s
6.2.2 การถอดรหัสโค้ดคำนำหน้าเมตา
ตามที่ระบุไว้ก่อนหน้านี้ รูปแบบนี้สามารถใช้รหัสนำหน้าที่แตกต่างกันสำหรับ บล็อกต่างๆ ของรูปภาพ โค้ดคำนำหน้าเมตา คือดัชนีที่ระบุว่า รหัสนําหน้าเพื่อใช้ในส่วนต่างๆ ของรูปภาพ
รหัสคำนำหน้าเมตาสามารถใช้ได้เฉพาะเมื่อมีการใช้รูปภาพใน role ของอิมเมจ 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) ตามที่อธิบายไว้ใน "การถอดรหัสเอนโทรปี-โค้ดรูปภาพ
Data"
6.2.3 การถอดรหัสข้อมูลรูปภาพที่เข้ารหัสเอนโทรปี
สำหรับตำแหน่งปัจจุบัน (x, y) ในรูปภาพ ตัวถอดรหัสจะระบุค่า กลุ่มโค้ดคำนำหน้าที่เกี่ยวข้อง (ตามที่อธิบายไว้ในส่วนสุดท้าย) เนื่องจาก พิกเซลจะอ่านและถอดรหัสดังนี้
ถัดไป ให้อ่านสัญลักษณ์ S จากบิตสตรีมโดยใช้รหัสนำหน้า #1 โปรดทราบว่า S คือ
จำนวนเต็มในช่วง 0
ถึง
(256 + 24 +
color_cache_size
- 1)
การตีความ S จะขึ้นอยู่กับค่า ดังนี้
- หาก S < 256 คน
- ใช้ S เป็นคอมโพเนนต์สีเขียว
- อ่านค่าสีแดงจากบิตสตรีมโดยใช้รหัสนำหน้า #2
- อ่านค่าสีน้ำเงินจากบิตสตรีมโดยใช้รหัสนำหน้า #3
- อ่านอัลฟ่าจากบิตสตรีมโดยใช้โค้ดนำหน้า #4
- หาก S >= 256 & วิ 256 + 24
- ใช้ S - 256 เป็นรหัสนำหน้าความยาว
- อ่านบิตเพิ่มเติมเพื่อความยาวจากบิตสตรีม
- กำหนดความยาวอ้างอิงย้อนหลัง L จากโค้ดคำนำหน้าความยาวและ จำนวนบิตที่เกินมา
- อ่านรหัสคำนำหน้าระยะทางจากบิตสตรีมโดยใช้รหัสนำหน้า #5
- อ่านบิตเพิ่มเติมระยะทางจากบิตสตรีม
- กำหนดระยะทางอ้างอิงย้อนหลัง D จากโค้ดคำนำหน้าระยะทาง และบิตพิเศษที่อ่านได้
- คัดลอกพิกเซล L (ตามลำดับบรรทัดสแกน) จากลำดับพิกเซลเริ่มต้น ที่ตำแหน่งปัจจุบันลบ D พิกเซล
- หาก S >= 256 + 24
- ใช้ S - (256 + 24) เป็นดัชนีในแคชสี
- หาสี 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