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 ไบต์ต่อไปนี้
- สตริง "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 ถัดจาก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 / 2width_bits
= 2: สำหรับค่า x ทุกๆ ค่า โดยที่ x zh 0 (ม็อด 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
(ค่า ARGB สูงสุด 256 ค่า) ที่จัดเก็บข้อมูลเมตาสำหรับการเปลี่ยนรูปแบบการจัดทำดัชนีสี (ดู "การเปลี่ยนรูปแบบการจัดทำดัชนีสี")
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) จะมีชุดรหัสนำหน้า 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 ขึ้นอยู่กับค่าดังนี้
- หาก S < 256
- ใช้ S เป็นองค์ประกอบสีเขียว
- อ่านสีแดงจาก Bitstream โดยใช้รหัสนำหน้า #2
- อ่านสีน้ำเงินจากบิตสตรีมโดยใช้รหัสนำหน้า #3
- อ่านอัลฟ่าจาก บิตสตรีมโดยใช้รหัสนำหน้า #4
- หาก S >= 256 และ S < 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