WebP लॉसलेस बिटस्ट्रीम के लिए खास जानकारी

जर्कि अलाकुइजाला, पीएचडी, Google, Inc., 2023-03-09

खास जानकारी

WebP लॉसलेस, ARGB इमेज को कंप्रेस करने का एक इमेज फ़ॉर्मैट है. इसमें इमेज की क्वालिटी कम नहीं होती. लॉसलैस फ़ॉर्मैट में, पिक्सल वैल्यू को ठीक उसी तरह से सेव और रीस्टोर किया जाता है. इसमें पूरी तरह से पारदर्शी पिक्सल के लिए, कलर वैल्यू भी शामिल होती हैं. ज़्यादा डेटा को कंप्रेस करने के लिए, क्रम से लगे डेटा को कंप्रेस करने वाले यूनिवर्सल एल्गोरिदम (LZ77), प्रीफ़िक्स कोडिंग, और कलर कैश का इस्तेमाल किया जाता है. यह PNG से ज़्यादा तेज़ी से डिकोड होता है. साथ ही, इसे आज के PNG फ़ॉर्मैट की तुलना में 25% ज़्यादा कंप्रेस किया जा सकता है.

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 इमेज को चार अलग-अलग तरह से बदला जा सकता है. बिटस्ट्रीम में मौजूद ट्रांसफ़ॉर्मेशन की जानकारी में, संबंधित इनवर्स ट्रांसफ़ॉर्मेशन लागू करने के लिए ज़रूरी डेटा होता है.

2 नामकरण

ARGB

ऐल्फ़ा, लाल, हरे, और नीले रंग की वैल्यू से मिलकर बनी पिक्सल वैल्यू.

ARGB इमेज

ARGB पिक्सल वाला दो डाइमेंशन का अरे.

कलर कैश

यह एक छोटा हैश-ऐड्रेस वाला ऐरे होता है. इसमें हाल ही में इस्तेमाल किए गए रंगों को सेव किया जाता है, ताकि उन्हें छोटे कोड से वापस लाया जा सके.

कलर इंडेक्सिंग इमेज

यह रंगों की एक डाइमेंशनल इमेज होती है. इसे छोटे पूर्णांक का इस्तेमाल करके इंडेक्स किया जा सकता है. WebP लॉसलेस में यह पूर्णांक 256 तक हो सकता है.

इमेज के रंग बदलना

यह दो डाइमेंशन वाली कम रिज़ॉल्यूशन की इमेज होती है. इसमें कलर कॉम्पोनेंट के कोरिलेशन के बारे में डेटा होता है.

डिस्टेंस मैपिंग

LZ77 डिस्टैंस में बदलाव करता है, ताकि दो डाइमेंशन वाली प्रॉक्सिमिटी में पिक्सल के लिए सबसे छोटी वैल्यू मिल सकें.

एंट्रॉपी इमेज

यह दो डाइमेंशन वाली कम रिज़ॉल्यूशन की इमेज होती है. इससे पता चलता है कि इमेज के किसी स्क्वेयर में किस एंट्रॉपी कोडिंग का इस्तेमाल किया जाना चाहिए. इसका मतलब है कि हर पिक्सल एक मेटा प्रीफ़िक्स कोड होता है.

LZ77

यह डिक्शनरी पर आधारित स्लाइडिंग विंडो कंप्रेस करने का एल्गोरिदम है. यह या तो सिंबल दिखाता है या उन्हें पिछले सिंबल के क्रम के तौर पर दिखाता है.

मेटा प्रीफ़िक्स कोड

यह एक छोटा पूर्णांक (16 बिट तक) होता है. यह मेटा प्रीफ़िक्स टेबल में किसी एलिमेंट को इंडेक्स करता है.

पूर्वानुमान लगाने वाली इमेज

यह दो डाइमेंशन वाली कम रिज़ॉल्यूशन वाली इमेज होती है. इससे पता चलता है कि इमेज के किसी स्क्वेयर के लिए, किस स्पैटियल प्रेडिक्टर का इस्तेमाल किया गया है.

प्रीफ़िक्स कोड

यह एन्ट्रॉपी कोडिंग का क्लासिक तरीका है. इसमें, ज़्यादा बार इस्तेमाल होने वाले कोड के लिए कम बिट का इस्तेमाल किया जाता है.

उपसर्ग कोडिंग

यह बड़े पूर्णांकों को एन्ट्रॉपी कोड करने का एक तरीका है. इसमें एन्ट्रॉपी कोड का इस्तेमाल करके पूर्णांक के कुछ बिट कोड किए जाते हैं और बाकी बिट को रॉ कोड में बदल दिया जाता है. इससे एंट्रॉपी कोड के ब्यौरे को छोटा रखा जा सकता है. ऐसा तब भी किया जा सकता है, जब सिंबल की रेंज बड़ी हो.

स्कैन-लाइन ऑर्डर

पिक्सल को प्रोसेस करने का क्रम (बाईं से दाईं ओर और ऊपर से नीचे की ओर). यह क्रम, सबसे ऊपर बाईं ओर वाले पिक्सल से शुरू होता है. एक लाइन पूरी होने के बाद, अगली लाइन के बाईं ओर मौजूद कॉलम से शुरू करें.

3 RIFF हेडर

हेडर की शुरुआत में RIFF कंटेनर होता है. इसमें ये 21 बाइट शामिल हैं:

1. स्ट्रिंग 'RIFF'.
2. यह चंक की लंबाई की लिटिल-एंडियन, 32-बिट वैल्यू होती है. यह RIFF हेडर से कंट्रोल किए गए चंक का पूरा साइज़ होता है. आम तौर पर, यह पेलोड के साइज़ के बराबर होता है. पेलोड का साइज़, फ़ाइल के साइज़ से 8 बाइट कम होता है. इसमें 'RIFF' आइडेंटिफ़ायर के लिए 4 बाइट और वैल्यू सेव करने के लिए 4 बाइट होते हैं.
3. स्ट्रिंग 'WEBP' (आरआईएफ़ कंटेनर का नाम).
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✕16384 पिक्सल तक सीमित हो जाता है.

alpha_is_used बिट सिर्फ़ एक हिंट है और इससे डिकोडिंग पर कोई असर नहीं पड़ना चाहिए. अगर इमेज में सभी ऐल्फ़ा वैल्यू 255 हैं, तो इसे 0 पर सेट किया जाना चाहिए. अगर ऐसा नहीं है, तो इसे 1 पर सेट किया जाना चाहिए.

int alpha_is_used = ReadBits(1);

version_number, तीन बिट का कोड होता है. इसे 0 पर सेट करना ज़रूरी है. कोई दूसरी वैल्यू डालने पर गड़बड़ी का मैसेज दिखना चाहिए.

int version_number = ReadBits(3);

चार ट्रांसफ़ॉर्म

ट्रांसफ़ॉर्म, इमेज डेटा में किए गए ऐसे बदलाव होते हैं जिन्हें पहले जैसा किया जा सकता है. ये बदलाव, स्पेस और रंग के कोरिलेशन को मॉडल करके, बची हुई सिंबॉलिक एंट्रॉपी को कम कर सकते हैं. ये फ़ाइलें, फ़ाइनल कंप्रेस की गई फ़ाइल को ज़्यादा डेंस बना सकती हैं.

किसी इमेज में चार तरह के बदलाव किए जा सकते हैं. एक बिट से ट्रांसफ़ॉर्म की मौजूदगी का पता चलता है. हर ट्रांसफ़ॉर्म का इस्तेमाल सिर्फ़ एक बार किया जा सकता है. ट्रांसफ़ॉर्म का इस्तेमाल सिर्फ़ मुख्य लेवल की 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).

अगर कोई ट्रांसफ़ॉर्म मौजूद है, तो अगले दो बिट ट्रांसफ़ॉर्म टाइप के बारे में बताते हैं. ट्रांसफ़ॉर्म चार तरह के होते हैं.

enum TransformType {
  PREDICTOR_TRANSFORM             = 0,
  COLOR_TRANSFORM                 = 1,
  SUBTRACT_GREEN_TRANSFORM        = 2,
  COLOR_INDEXING_TRANSFORM        = 3,
};

ट्रांसफ़ॉर्म टाइप के बाद, ट्रांसफ़ॉर्म किया गया डेटा होता है. ट्रांसफ़ॉर्म किए गए डेटा में, इनवर्स ट्रांसफ़ॉर्म लागू करने के लिए ज़रूरी जानकारी होती है. यह जानकारी, ट्रांसफ़ॉर्म के टाइप पर निर्भर करती है. इनवर्स ट्रांसफ़ॉर्म, बिटस्ट्रीम से पढ़े गए क्रम के उलट क्रम में लागू होते हैं. इसका मतलब है कि सबसे आखिर में लागू होने वाला ट्रांसफ़ॉर्म सबसे पहले लागू होता है.

इसके बाद, हम अलग-अलग तरह के डेटा को बदलने के बारे में बताते हैं.

4.1 Predictor Transform

प्रेडिक्टर ट्रांसफ़ॉर्म का इस्तेमाल, एंट्रॉपी को कम करने के लिए किया जा सकता है. ऐसा इसलिए, क्योंकि आस-पास के पिक्सल अक्सर एक-दूसरे से जुड़े होते हैं. अनुमान लगाने वाले ट्रांसफ़ॉर्म में, मौजूदा पिक्सल वैल्यू का अनुमान पहले से डिकोड किए गए पिक्सल (स्कैन-लाइन के क्रम में) से लगाया जाता है. साथ ही, सिर्फ़ बची हुई वैल्यू (असल - अनुमानित) को एन्कोड किया जाता है. किसी पिक्सल का हरा कॉम्पोनेंट यह तय करता है कि ARGB इमेज के किसी ब्लॉक में, 14 में से कौनसा अनुमान लगाने वाला कॉम्पोनेंट इस्तेमाल किया गया है. अनुमान का मोड यह तय करता है कि किस तरह का अनुमान इस्तेमाल करना है. हम इमेज को स्क्वेयर में बांटते हैं. साथ ही, किसी स्क्वेयर में मौजूद सभी पिक्सल के लिए एक ही अनुमान लगाने वाले मोड का इस्तेमाल करते हैं.

अनुमान के डेटा के पहले तीन बिट, बिट की संख्या के हिसाब से ब्लॉक की चौड़ाई और ऊंचाई तय करते हैं.

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

बदले गए डेटा में, इमेज के हर ब्लॉक के लिए अनुमान लगाने का मोड होता है. यह सबरिज़ॉल्यूशन वाली इमेज होती है. इसमें किसी पिक्सल का हरा कॉम्पोनेंट यह तय करता है कि एआरजीबी इमेज के किसी खास ब्लॉक में मौजूद सभी block_width * block_height पिक्सल के लिए, 14 में से कौनसे अनुमान लगाने वाले फ़ंक्शन का इस्तेमाल किया जाएगा. इस सबरिज़ॉल्यूशन इमेज को अध्याय 5 में बताई गई तकनीकों का इस्तेमाल करके एन्कोड किया जाता है.

ब्लॉक कॉलम की संख्या, transform_width, का इस्तेमाल दो डाइमेंशन वाली इंडेक्सिंग में किया जाता है. किसी पिक्सल (x, y) के लिए, फ़िल्टर ब्लॉक का पता इस तरह से पता लगाया जा सकता है:

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

इसमें अनुमान लगाने के 14 अलग-अलग मोड होते हैं. हर अनुमान लगाने वाले मोड में, मौजूदा पिक्सल की वैल्यू का अनुमान, आस-पास के एक या उससे ज़्यादा पिक्सल से लगाया जाता है. इन पिक्सल की वैल्यू पहले से पता होती है.

हमने मौजूदा पिक्सल (P) के आस-पास के पिक्सल (TL, T, TR, और L) को इस तरह चुना है:

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	TR
4	TL
5	Average2(Average2(L, TR), T)
6	Average2(L, TL)
7	Average2(L, T)
8	Average2(TL, T)
9	Average2(T, TR)
10	Average2(Average2(L, TL), Average2(T, TR))
11	Select(L, T, TL)
12	ClampAddSubtractFull(L, T, TL)
13	ClampAddSubtractHalf(Average2(L, T), TL)

हर ARGB कॉम्पोनेंट के लिए, Average2 को इस तरह से तय किया जाता है:

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

Select predictor को इस तरह से परिभाषित किया गया है:

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

हर ARGB कॉम्पोनेंट के लिए, ClampAddSubtractFull और ClampAddSubtractHalf फ़ंक्शन इस तरह से काम करते हैं:

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

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

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

कुछ बॉर्डर पिक्सल के लिए, खास हैंडलिंग के नियम होते हैं. अगर कोई अनुमान लगाने वाला ट्रांसफ़ॉर्म है, तो इन पिक्सल के लिए मोड [0..13] कुछ भी हो, इमेज के सबसे ऊपर बाईं ओर वाले पिक्सल के लिए अनुमानित वैल्यू 0xff000000 होती है. सबसे ऊपर वाली लाइन के सभी पिक्सल L-पिक्सल होते हैं और सबसे बाईं ओर वाले कॉलम के सभी पिक्सल T-पिक्सल होते हैं.

सबसे दाईं ओर मौजूद कॉलम के पिक्सल के लिए टीआर-पिक्सल को ठीक करना बेहद ज़रूरी है. सबसे दाईं ओर मौजूद कॉलम के पिक्सल का अनुमान, मोड [0..13] का इस्तेमाल करके लगाया जाता है. ठीक वैसे ही जैसे बॉर्डर पर मौजूद पिक्सल का अनुमान लगाया जाता है. हालांकि, मौजूदा पिक्सल वाली लाइन में सबसे बाईं ओर मौजूद पिक्सल का इस्तेमाल, टीआर-पिक्सल के तौर पर किया जाता है.

प्रेडिक्ट की गई वैल्यू के हर चैनल को एन्कोड की गई रीज़िडुअल वैल्यू में जोड़ने पर, पिक्सल की फ़ाइनल वैल्यू मिलती है.

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) रंग की वैल्यू को बदलता है.

अनुमान लगाने वाले ट्रांसफ़ॉर्म की तरह ही, इमेज को पहले ब्लॉक में बांटा जाता है. इसके बाद, किसी ब्लॉक के सभी पिक्सल के लिए एक ही ट्रांसफ़ॉर्म मोड का इस्तेमाल किया जाता है. हर ब्लॉक के लिए, तीन तरह के कलर ट्रांसफ़ॉर्म एलिमेंट होते हैं.

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-फ़िक्स्ड-पॉइंट नंबर और साइंड 8-बिट आरजीबी कलर चैनल (c) [-128..127] को दिखाता है. इसे इस तरह से परिभाषित किया गया है:

int8 ColorTransformDelta(int8 t, int8 c) {
  return (t * c) >> 5;
}

ColorTransformDelta() को कॉल करने से पहले, 8-बिट के बिना हस्ताक्षर वाले (uint8) को 8-बिट के हस्ताक्षर वाले (int8) में बदलना ज़रूरी है. चिह्नित वैल्यू को 8-बिट के दो पूरक नंबर के तौर पर समझा जाना चाहिए. इसका मतलब है कि uint8 रेंज [128..255] को, बदली गई int8 वैल्यू की [-128..-1] रेंज पर मैप किया जाता है.

गुणा ज़्यादा सटीक तरीके से किया जाना चाहिए. इसके लिए, कम से कम 16-बिट की सटीक जानकारी का इस्तेमाल किया जाना चाहिए. शिफ़्ट ऑपरेशन की साइन एक्सटेंशन प्रॉपर्टी से यहां कोई फ़र्क़ नहीं पड़ता. नतीजे के सिर्फ़ सबसे कम आठ बिट इस्तेमाल किए जाते हैं. इन बिट में, साइन एक्सटेंशन शिफ़्टिंग और अनसाइंड शिफ़्टिंग एक-दूसरे के साथ मेल खाती हैं.

अब हम कलर ट्रांसफ़ॉर्म डेटा के कॉन्टेंट के बारे में बताते हैं, ताकि डिकोडिंग, इनवर्स कलर ट्रांसफ़ॉर्म लागू कर सके और लाल और नीले रंग की ओरिजनल वैल्यू वापस पा सके. कलर ट्रांसफ़ॉर्म डेटा के पहले तीन बिट में, इमेज ब्लॉक की चौड़ाई और ऊंचाई होती है. यह जानकारी बिट की संख्या में होती है. यह जानकारी, प्रेडिक्टर ट्रांसफ़ॉर्म की तरह ही होती है:

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 इंस्टेंस डिकोड किए जाते हैं. साथ ही, पिक्सल की एआरजीबी वैल्यू पर इनवर्स कलर ट्रांसफ़ॉर्म लागू किया जाता है. जैसा कि पहले बताया गया है, कलर ट्रांसफ़ॉर्म को उलटने से, लाल और नीले चैनलों में सिर्फ़ 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 लॉसलेस एन्कोडिंग में एक ऐसा ही, लेकिन ज़्यादा डाइनैमिक कॉन्सेप्ट मौजूद है: कलर कैश.)

कलर इंडेक्सिंग ट्रांसफ़ॉर्म, इमेज में मौजूद यूनीक एआरजीबी वैल्यू की संख्या की जांच करता है. अगर यह संख्या थ्रेशोल्ड (256) से कम है, तो यह उन एआरजीबी वैल्यू का एक कलेक्शन बनाता है. इसके बाद, इसका इस्तेमाल पिक्सल वैल्यू को उससे जुड़े इंडेक्स से बदलने के लिए किया जाता है: पिक्सल के हरे चैनल को इंडेक्स से बदल दिया जाता है, सभी ऐल्फ़ा वैल्यू को 255 पर सेट कर दिया जाता है, और सभी लाल और नीली वैल्यू को 0 पर सेट कर दिया जाता है.

बदले गए डेटा में, कलर टेबल का साइज़ और कलर टेबल में मौजूद एंट्री शामिल होती हैं. डिकोडर, कलर इंडेक्सिंग ट्रांसफ़ॉर्म डेटा को इस तरह पढ़ता है:

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

कलर टेबल को इमेज स्टोरेज फ़ॉर्मैट का इस्तेमाल करके सेव किया जाता है. कलर टेबल को इमेज पढ़कर हासिल किया जा सकता है. इसके लिए, RIFF हेडर, इमेज का साइज़, और ट्रांसफ़ॉर्मेशन की ज़रूरत नहीं होती. हालांकि, इसके लिए इमेज की ऊंचाई 1 पिक्सल और चौड़ाई color_table_size होनी चाहिए. कलर टेबल को हमेशा सब्ट्रैक्शन-कोड किया जाता है, ताकि इमेज एंट्रॉपी को कम किया जा सके. पैलेट के रंगों के डेल्टा में, रंगों की तुलना में आम तौर पर बहुत कम एंट्रॉपी होती है. इससे छोटी इमेज के लिए, काफ़ी बचत होती है. डिकोडिंग में, कलर टेबल में मौजूद हर आखिरी रंग को, हर एआरजीबी कॉम्पोनेंट के हिसाब से पिछले रंग के कॉम्पोनेंट की वैल्यू जोड़कर हासिल किया जा सकता है. साथ ही, नतीजे के सबसे कम अहम 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 का मतलब है कि दो पिक्सल को एक साथ जोड़ा गया है. साथ ही, हर पिक्सल की रेंज [0..15] है. वैल्यू 2 का मतलब है कि चार पिक्सल को एक साथ जोड़ा गया है. साथ ही, हर पिक्सल की रेंज [0..3] है. वैल्यू 3 से पता चलता है कि आठ पिक्सल को एक साथ जोड़ा गया है और हर पिक्सल की रेंज [0..1] है. इसका मतलब है कि यह एक बाइनरी वैल्यू है.

वैल्यू को हरे कॉम्पोनेंट में इस तरह पैक किया जाता है:

• width_bits = 1: हर x वैल्यू के लिए, जहां x ≡ 0 (mod 2) है, x पर मौजूद ग्रीन वैल्यू को x / 2 पर मौजूद ग्रीन वैल्यू के चार सबसे कम सिग्निफ़िकेंट बिट में रखा जाता है. साथ ही, x + 1 पर मौजूद ग्रीन वैल्यू को x / 2 पर मौजूद ग्रीन वैल्यू के चार सबसे ज़्यादा सिग्निफ़िकेंट बिट में रखा जाता है.
• width_bits = 2: हर x वैल्यू के लिए, जहां x ≡ 0 (mod 4) है, x पर मौजूद हरे रंग की वैल्यू को 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 इमेज डेटा की भूमिकाएं

हम इमेज डेटा का इस्तेमाल पांच अलग-अलग भूमिकाओं में करते हैं:

1. ARGB इमेज: इसमें इमेज के असल पिक्सल सेव होते हैं.
2. एंट्रॉपी इमेज: यह मेटा प्रीफ़िक्स कोड सेव करती है ("मेटा प्रीफ़िक्स कोड डिकोड करना" देखें).
3. अनुमान लगाने वाले की इमेज: यह अनुमान लगाने वाले की इमेज के मेटाडेटा को सेव करता है. इसके बारे में जानने के लिए, "अनुमान लगाने वाले की इमेज" लेख पढ़ें.
4. कलर ट्रांसफ़ॉर्म इमेज: इसे इमेज के अलग-अलग ब्लॉक के लिए, ColorTransformElement values ("Color Transform" में तय की गई) से बनाया जाता है.
5. कलर इंडेक्सिंग इमेज: यह color_table_size साइज़ का एक ऐरे होता है. इसमें ज़्यादा से ज़्यादा 256 एआरजीबी वैल्यू होती हैं. यह कलर इंडेक्सिंग ट्रांसफ़ॉर्म के लिए मेटाडेटा सेव करता है. इसके बारे में जानने के लिए, "कलर इंडेक्सिंग ट्रांसफ़ॉर्म" देखें.

5.2 इमेज डेटा की एन्कोडिंग

इमेज डेटा की एन्कोडिंग, उसकी भूमिका से अलग होती है.

इमेज को सबसे पहले, तय किए गए साइज़ के ब्लॉक (आम तौर पर 16x16 ब्लॉक) के सेट में बांटा जाता है. इनमें से हर ब्लॉक को, उनके अपने एंट्रॉपी कोड का इस्तेमाल करके मॉडल किया जाता है. इसके अलावा, कई ब्लॉक एक ही एंट्रॉपी कोड शेयर कर सकते हैं.

वजह: एंट्रॉपी कोड को सेव करने पर शुल्क लगता है. अगर आंकड़ों के हिसाब से मिलते-जुलते ब्लॉक, एंट्रॉपी कोड शेयर करते हैं, तो इस लागत को कम किया जा सकता है. इससे उस कोड को सिर्फ़ एक बार सेव किया जाता है. उदाहरण के लिए, कोई एनकोडर, सांख्यिकीय प्रॉपर्टी का इस्तेमाल करके या इमेज को कोड में बदलने के लिए ज़रूरी बिट की कुल संख्या कम होने पर, बार-बार रैंडम तरीके से चुने गए क्लस्टर के किसी जोड़े को जोड़कर, मिलते-जुलते ब्लॉक ढूंढ सकता है.

हर पिक्सल को तीन में से किसी एक तरीके का इस्तेमाल करके कोड में बदला जाता है:

1. प्रीफ़िक्स-कोडेड लिटरल: हर चैनल (हरा, लाल, नीला, और ऐल्फ़ा) को अलग-अलग एंट्रॉपी-कोड किया जाता है.
2. LZ77 बैकवर्ड रेफ़रंस: पिक्सल के किसी क्रम को इमेज में कहीं और से कॉपी किया जाता है.
3. कलर कैश कोड: हाल ही में देखे गए रंग के छोटे मल्टीप्लिकेटिव हैश कोड (कलर कैश इंडेक्स) का इस्तेमाल करना.

यहां दिए गए सब-सेक्शन में, इन सभी के बारे में पूरी जानकारी दी गई है.

5.2.1 प्रीफ़िक्स-कोडेड लिटरल

पिक्सेल को हरे, लाल, नीले, और ऐल्फ़ा (इसी क्रम में) के प्रीफ़िक्स-कोड वाले मानों के तौर पर सेव किया जाता है. ज़्यादा जानकारी के लिए, सेक्शन 6.2.3 देखें.

5.2.2 LZ77 बैकवर्ड रेफ़रंस

बैकवर्ड रेफ़रंस, लंबाई और दूरी कोड के टपल होते हैं:

• लंबाई से पता चलता है कि स्कैन-लाइन के क्रम में कितने पिक्सल कॉपी किए जाने हैं.
• डिस्टेंस कोड एक ऐसा नंबर होता है जो पहले देखे गए पिक्सल की पोज़िशन दिखाता है. पिक्सल को इसी पोज़िशन से कॉपी किया जाता है. मैपिंग के बारे में यहां बताया गया है.

लंबाई और दूरी की वैल्यू को LZ77 प्रीफ़िक्स कोडिंग का इस्तेमाल करके सेव किया जाता है.

LZ77 प्रीफ़िक्स कोडिंग, बड़ी पूर्णांक वैल्यू को दो हिस्सों में बांटती है: प्रीफ़िक्स कोड और एक्स्ट्रा बिट. प्रीफ़िक्स कोड को एंट्रॉपी कोड का इस्तेमाल करके सेव किया जाता है. वहीं, अतिरिक्त बिट को बिना किसी एंट्रॉपी कोड के सेव किया जाता है.

वजह: इस तरीके से, एंट्रॉपी कोड के लिए स्टोरेज की ज़रूरत कम हो जाती है. साथ ही, बड़ी वैल्यू आम तौर पर कम होती हैं. इसलिए, इमेज में बहुत कम वैल्यू के लिए अतिरिक्त बिट का इस्तेमाल किया जाएगा. इसलिए, इस तरीके से इमेज को बेहतर तरीके से कंप्रेस किया जा सकता है.

यहां दी गई टेबल में, वैल्यू की अलग-अलग रेंज को सेव करने के लिए इस्तेमाल किए गए प्रीफ़िक्स कोड और अतिरिक्त बिट के बारे में बताया गया है.

ध्यान दें: बैकवर्ड रेफ़रंस की ज़्यादा से ज़्यादा लंबाई 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 इस तरह के पिक्सल].

दूरी के कोड 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) के ऑफ़सेट को दिखाता है. इसका मतलब है कि मौजूदा पिक्सल के ऊपर मौजूद पिक्सल (X दिशा में 0 पिक्सल का अंतर और Y दिशा में 1 पिक्सल का अंतर). इसी तरह, दूरी का कोड 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 कलर कैश कोडिंग

कलर कैश में, ऐसे रंगों का सेट सेव होता है जिनका इस्तेमाल हाल ही में इमेज में किया गया है.

वजह: इस तरीके से, हाल ही में इस्तेमाल किए गए रंगों को कभी-कभी अन्य दो तरीकों (5.2.1 और 5.2.2 में बताया गया है) की तुलना में ज़्यादा आसानी से रेफ़र किया जा सकता है.

कलर कैश कोड इस तरह से सेव किए जाते हैं. सबसे पहले, एक बिट की वैल्यू होती है. इससे पता चलता है कि कलर कैश का इस्तेमाल किया गया है या नहीं. अगर यह बिट 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 रंग सेव होता है. रंगों को (0x1e35a7bd * color) >> (32 - color_cache_code_bits) के हिसाब से इंडेक्स करके देखा जाता है. कलर कैश में सिर्फ़ एक लुकअप किया जाता है. इसमें किसी भी तरह की समस्या को हल नहीं किया जाता.

किसी इमेज को डिकोड या कोड करने की शुरुआत में, सभी कलर कैश वैल्यू में मौजूद सभी एंट्री को शून्य पर सेट किया जाता है. डिकोडिंग के समय, कलर कैश कोड को इस रंग में बदल दिया जाता है. कलर कैश की स्थिति को बनाए रखने के लिए, हर पिक्सल को कैश में डाला जाता है. भले ही, वह बैकवर्ड रेफ़रंसिंग से बनाया गया हो या लिटरल के तौर पर. पिक्सल को कैश में उसी क्रम में डाला जाता है जिस क्रम में वे स्ट्रीम में दिखते हैं.

6 एंट्रॉपी कोड

6.1 खास जानकारी

ज़्यादातर डेटा को कैननिकल प्रीफ़िक्स कोड का इस्तेमाल करके कोड किया जाता है. इसलिए, प्रीफ़िक्स कोड भेजने के बजाय, प्रीफ़िक्स कोड की लंबाई भेजकर कोड ट्रांसमिट किए जाते हैं.

खास तौर पर, इस फ़ॉर्मैट में स्पेशली वैरिएंट प्रीफ़िक्स कोडिंग का इस्तेमाल किया जाता है. दूसरे शब्दों में कहें, तो इमेज के अलग-अलग ब्लॉक, अलग-अलग एंट्रॉपी कोड का इस्तेमाल कर सकते हैं.

वजह: इमेज के अलग-अलग हिस्सों की विशेषताएं अलग-अलग हो सकती हैं. इसलिए, उन्हें अलग-अलग एंट्रॉपी कोड इस्तेमाल करने की अनुमति देने से, ज़्यादा आसानी होती है और बेहतर कंप्रेशन मिल सकता है.

6.2 जानकारी

कोड किए गए इमेज डेटा में कई हिस्से होते हैं:

1. प्रीफ़िक्स कोड को डिकोड करना और बनाना.
2. मेटा प्रीफ़िक्स कोड.
3. एंट्रॉपी कोडिंग का इस्तेमाल करके एन्कोड किया गया इमेज डेटा.

किसी भी पिक्सल (x, y) के लिए, उससे जुड़े पांच प्रीफ़िक्स कोड का एक सेट होता है. ये कोड (बिटस्ट्रीम के क्रम में) हैं:

• प्रीफ़िक्स कोड #1: इसका इस्तेमाल ग्रीन चैनल, बैकवर्ड-रेफ़रंस की लंबाई, और कलर कैश के लिए किया जाता है.
• प्रीफ़िक्स कोड #2, #3, और #4: इनका इस्तेमाल क्रमशः लाल, नीले, और ऐल्फ़ा चैनल के लिए किया जाता है.
• प्रीफ़िक्स कोड #5: इसका इस्तेमाल बैकवर्ड-रेफ़रंस दूरी के लिए किया जाता है.

इसके बाद, हम इस सेट को प्रीफ़िक्स कोड ग्रुप कहते हैं.

6.2.1 प्रीफ़िक्स कोड को डिकोड करना और बनाना

इस सेक्शन में, बिटस्ट्रीम से प्रीफ़िक्स कोड की लंबाई पढ़ने का तरीका बताया गया है.

प्रीफ़िक्स कोड की लंबाई को दो तरीकों से कोड किया जा सकता है. इस्तेमाल किए गए तरीके को 1-बिट वैल्यू से दिखाया जाता है.

• अगर यह बिट 1 है, तो यह कोड की लंबाई का सामान्य कोड है.
• अगर यह बिट 0 है, तो यह सामान्य कोड लेंथ कोड है.

दोनों ही मामलों में, स्ट्रीम में ऐसे कोड हो सकते हैं जिनका इस्तेमाल नहीं किया गया है. यह तरीका असरदार नहीं हो सकता, लेकिन फ़ॉर्मैट के हिसाब से इसका इस्तेमाल किया जा सकता है. बताया गया ट्री, फ़ुल बाइनरी ट्री होना चाहिए. एक लीफ़ नोड को पूरा बाइनरी ट्री माना जाता है. इसे सामान्य कोड की लंबाई वाले कोड या सामान्य कोड की लंबाई वाले कोड का इस्तेमाल करके एन्कोड किया जा सकता है. सामान्य कोड की लंबाई वाले कोड का इस्तेमाल करके, किसी एक लीफ़ नोड को कोड में बदलने पर, कोड की लंबाई के सभी मान शून्य होते हैं. साथ ही, एक लीफ़ नोड की वैल्यू को 1 के तौर पर मार्क किया जाता है. भले ही, उस एक लीफ़ नोड ट्री का इस्तेमाल करने पर कोई बिट इस्तेमाल न किया गया हो.

आसान कोड लेंथ कोड

इस वैरिएंट का इस्तेमाल खास मामलों में किया जाता है. जैसे, जब कोड की लंबाई 1 के साथ रेंज [0..255] में सिर्फ़ एक या दो प्रीफ़िक्स सिंबल हों. अन्य सभी प्रीफ़िक्स कोड की लंबाई, डिफ़ॉल्ट रूप से शून्य होती है.

पहले बिट से सिंबल की संख्या का पता चलता है:

int num_symbols = ReadBits(1) + 1;

सिंबल की वैल्यू यहां दी गई हैं.

पहले सिंबल को 1 या 8 बिट का इस्तेमाल करके कोड किया जाता है. यह is_first_8bits की वैल्यू पर निर्भर करता है. रेंज क्रमशः [0..1] या [0..255] होती है. अगर दूसरा सिंबल मौजूद है, तो उसे हमेशा [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;
}

दोनों सिंबल अलग-अलग होने चाहिए. डुप्लीकेट सिंबल इस्तेमाल किए जा सकते हैं, लेकिन ये असरदार नहीं होते.

ध्यान दें: एक और खास मामला तब होता है, जब all प्रीफ़िक्स कोड की लंबाई शून्य होती है (खाली प्रीफ़िक्स कोड). उदाहरण के लिए, अगर पीछे की ओर कोई रेफ़रंस नहीं है, तो दूरी के लिए प्रीफ़िक्स कोड खाली हो सकता है. इसी तरह, अगर एक ही मेटा प्रीफ़िक्स कोड के सभी पिक्सल, कलर कैश का इस्तेमाल करके बनाए जाते हैं, तो ऐल्फ़ा, लाल, और नीले रंग के लिए प्रीफ़िक्स कोड खाली हो सकते हैं. हालांकि, इस मामले में खास तौर पर कुछ करने की ज़रूरत नहीं है, क्योंकि खाली प्रीफ़िक्स कोड को, एक सिंबल 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 है, तो हर सिंबल टाइप (A, R, G, B, और दूरी) के लिए, पढ़े गए अलग-अलग सिंबल (max_symbol) की ज़्यादा से ज़्यादा संख्या को उसके वर्णमाला के साइज़ पर सेट किया जाता है:

• 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, पिछली नॉन-ज़ीरो वैल्यू को [3..6] बार दोहराता है. इसका मतलब है कि यह 3 + ReadBits(2) बार दोहराता है. अगर शून्य से अलग वैल्यू के दिखने से पहले कोड 16 का इस्तेमाल किया जाता है, तो वैल्यू 8 को दोहराया जाता है.
• कोड 17, [3..10] लंबाई वाले शून्य की एक स्ट्रीक दिखाता है. इसका मतलब है कि यह 3 + ReadBits(3) बार दिखता है.
• कोड 18, [11..138] लंबाई वाले शून्य की एक स्ट्रीक दिखाता है. इसका मतलब है कि यह 11 + ReadBits(7) बार दिखता है.

कोड की लंबाई पढ़ने के बाद, हर सिंबल टाइप (A, R, G, B, और दूरी) के लिए एक प्रीफ़िक्स कोड बनाया जाता है. इसके लिए, उनके वर्णमाला के साइज़ का इस्तेमाल किया जाता है.

सामान्य कोड की लंबाई के कोड में, पूरे फ़ैसले के ट्री को कोड किया जाना चाहिए. इसका मतलब है कि सभी नॉन-ज़ीरो कोड के लिए, 2 ^ (-length) का योग ठीक एक होना चाहिए. हालांकि, इस नियम का एक अपवाद है. यह अपवाद, सिंगल लीफ़ नोड ट्री है. इसमें लीफ़ नोड की वैल्यू को 1 के तौर पर मार्क किया जाता है और अन्य वैल्यू 0 होती हैं.

6.2.2 मेटा प्रीफ़िक्स कोड डिकोड करना

जैसा कि पहले बताया गया है, इस फ़ॉर्मैट में इमेज के अलग-अलग ब्लॉक के लिए, अलग-अलग प्रीफ़िक्स कोड इस्तेमाल किए जा सकते हैं. मेटा प्रीफ़िक्स कोड ऐसे इंडेक्स होते हैं जिनसे यह पता चलता है कि इमेज के अलग-अलग हिस्सों में कौनसे प्रीफ़िक्स कोड इस्तेमाल करने हैं.

मेटा प्रीफ़िक्स कोड का इस्तेमाल सिर्फ़ तब किया जा सकता है, जब इमेज का इस्तेमाल एआरजीबी इमेज के रोल में किया जा रहा हो.

मेटा प्रीफ़िक्स कोड के लिए दो विकल्प होते हैं. इन्हें 1-बिट वैल्यू से दिखाया जाता है:

• अगर यह बिट शून्य है, तो इमेज में हर जगह सिर्फ़ एक मेटा प्रीफ़िक्स कोड का इस्तेमाल किया जाता है. अब कोई डेटा सेव नहीं किया जाता.
• अगर यह बिट एक है, तो इमेज में एक से ज़्यादा मेटा प्रीफ़िक्स कोड इस्तेमाल किए जाते हैं. ये मेटा प्रीफ़िक्स कोड, एंट्रॉपी इमेज के तौर पर सेव किए जाते हैं. इसके बारे में यहां बताया गया है.

किसी पिक्सल के लाल और हरे कॉम्पोनेंट, 16-बिट मेटा प्रीफ़िक्स कोड तय करते हैं. इसका इस्तेमाल ARGB इमेज के किसी ब्लॉक में किया जाता है.

एंट्रॉपी इमेज

एंट्रॉपी इमेज से पता चलता है कि इमेज के अलग-अलग हिस्सों में कौनसे प्रीफ़िक्स कोड इस्तेमाल किए गए हैं.

पहले तीन बिट में 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 ऊंचाई वाली एंट्रॉपी इमेज शामिल है.

मेटा प्रीफ़िक्स कोड का मतलब

एआरजीबी इमेज में प्रीफ़िक्स कोड ग्रुप की संख्या का पता लगाने के लिए, एंट्रॉपी इमेज से सबसे बड़ा मेटा प्रीफ़िक्स कोड ढूंढें:

int num_prefix_groups = max(entropy image) + 1;

यहां max(entropy image), एंट्रॉपी इमेज में सेव किया गया सबसे बड़ा प्रीफ़िक्स कोड दिखाता है.

हर प्रीफ़िक्स कोड ग्रुप में पांच प्रीफ़िक्स कोड होते हैं. इसलिए, प्रीफ़िक्स कोड की कुल संख्या यह है:

int num_prefix_codes = 5 * num_prefix_groups;

ARGB इमेज में दिए गए पिक्सल (x, y) के लिए, हम इससे जुड़े प्रीफ़िक्स कोड इस तरह से पा सकते हैं:

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 स्ट्रक्चर के मौजूद होने की बात मानी है. यह पांच प्रीफ़िक्स कोड के सेट को दिखाता है. साथ ही, prefix_code_groups, PrefixCodeGroup (num_prefix_groups साइज़ का) का एक कलेक्शन है.

इसके बाद, डिकोडर, पिक्सल (x, y) को डिकोड करने के लिए, प्रीफ़िक्स कोड ग्रुप prefix_group का इस्तेमाल करता है. इसके बारे में "एंट्रॉपी-कोडेड इमेज डेटा को डिकोड करना" में बताया गया है.

6.2.3 एंट्रॉपी कोडिंग वाली इमेज के डेटा को डिकोड करना

इमेज में मौजूद मौजूदा पोज़िशन (x, y) के लिए, डिकोडर सबसे पहले इससे जुड़े प्रीफ़िक्स कोड ग्रुप की पहचान करता है. इसके बारे में पिछले सेक्शन में बताया गया है. प्रीफ़िक्स कोड ग्रुप को देखते हुए, पिक्सल को इस तरह से पढ़ा और डिकोड किया जाता है.

इसके बाद, प्रीफ़िक्स कोड #1 का इस्तेमाल करके बिटस्ट्रीम से सिंबल S को पढ़ें. ध्यान दें कि S, 0 से (256 + 24 + color_cache_size- 1) के बीच का कोई भी पूर्णांक है.

S की वैल्यू के आधार पर, इसका मतलब यह होता है:

1. If S < 256
   1. हरे रंग के कॉम्पोनेंट के तौर पर S का इस्तेमाल करें.
   2. प्रीफ़िक्स कोड #2 का इस्तेमाल करके, बिटस्ट्रीम से लाल रंग की जानकारी पढ़ता है.
   3. प्रीफ़िक्स कोड #3 का इस्तेमाल करके, बिटस्ट्रीम से नीले रंग की जानकारी पढ़ो.
   4. प्रीफ़िक्स कोड #4 का इस्तेमाल करके, बिटस्ट्रीम से ऐल्फ़ा पढ़ें.
2. If S >= 256 & S < 256 + 24
   1. लंबाई के प्रीफ़िक्स कोड के तौर पर S - 256 का इस्तेमाल करें.
   2. बिटस्ट्रीम से लंबाई के लिए अतिरिक्त बिट पढ़ें.
   3. लेंथ प्रीफ़िक्स कोड और पढ़े गए अतिरिक्त बिट से, बैकवर्ड-रेफ़रंस की लंबाई L का पता लगाएं.
   4. प्रीफ़िक्स कोड #5 का इस्तेमाल करके, बिटस्ट्रीम से दूरी के प्रीफ़िक्स कोड को पढ़ता है.
   5. बिटस्ट्रीम से दूरी के लिए अतिरिक्त बिट पढ़ें.
   6. डिस्टेंस प्रीफ़िक्स कोड और पढ़े गए अतिरिक्त बिट से, बैकवर्ड-रेफ़रंस की दूरी D का पता लगाएं.
   7. मौजूदा पोज़िशन से D पिक्सल पहले से शुरू होने वाले पिक्सल के क्रम से, L पिक्सल (स्कैन-लाइन के क्रम में) कॉपी करता है.
3. अगर S >= 256 + 24
   1. कलर कैश में इंडेक्स के तौर पर S - (256 + 24) का इस्तेमाल करें.
   2. उस इंडेक्स पर मौजूद कलर कैश से एआरजीबी कलर पाएं.

7 फ़ॉर्मैट का पूरा स्ट्रक्चर

ऑगमेंटेड बैकस-नौर फ़ॉर्म (एबीएनएफ़) आरएफ़सी 5234 आरएफ़सी 7405 में फ़ॉर्मैट का व्यू यहां दिया गया है. इसमें पूरी जानकारी शामिल नहीं होती. एंड-ऑफ़-इमेज (ईओआई) को सिर्फ़ पिक्सल की संख्या (image_width * image_height) में कोड किया जाता है.

ध्यान दें कि *element का मतलब है कि element को 0 या उससे ज़्यादा बार दोहराया जा सकता है. 5element का मतलब है कि element को ठीक पांच बार दोहराया गया है. %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