Jyrki Alakuijala, Ph.D., Google, Inc., 2023-03-09
বিমূর্ত
WebP লসলেস হল ARGB ছবিগুলির ক্ষতিহীন কম্প্রেশনের জন্য একটি ইমেজ ফরম্যাট। ক্ষতিহীন বিন্যাস সম্পূর্ণরূপে স্বচ্ছ পিক্সেলের জন্য রঙের মান সহ পিক্সেল মানগুলিকে সঠিকভাবে সঞ্চয় করে এবং পুনরুদ্ধার করে। সিকুয়েন্সিয়াল ডেটা কম্প্রেশন (LZ77), প্রিফিক্স কোডিং এবং একটি কালার ক্যাশে বাল্ক ডেটা কম্প্রেশনের জন্য একটি সার্বজনীন অ্যালগরিদম ব্যবহার করা হয়। PNG এর চেয়ে দ্রুত ডিকোডিং গতি প্রদর্শন করা হয়েছে, সেইসাথে আজকের PNG ফর্ম্যাট ব্যবহার করে অর্জন করা যেতে পারে 25% ঘন সংকোচন।
1 ভূমিকা
এই নথিটি একটি WebP ক্ষতিহীন চিত্রের সংকুচিত ডেটা উপস্থাপনা বর্ণনা করে। এটি WebP লসলেস এনকোডার এবং ডিকোডার বাস্তবায়নের জন্য একটি বিশদ রেফারেন্স হিসাবে উদ্দিষ্ট।
এই নথিতে, আমরা বিটস্ট্রিম বর্ণনা করতে এবং ReadBits(n) পড়ার জন্য একটি ফাংশনের অস্তিত্ব অনুমান করতে ব্যাপকভাবে C প্রোগ্রামিং ভাষা সিনট্যাক্�� ব্যবহার করি। বাইটগুলিকে ধারণ করা স্ট্রিমের স্বাভাবিক ক্রমে পড়া হয়, এবং প্রতিটি বাইটের বিটগুলি কম-উল্লেখযোগ্য-বিট-প্রথম ক্রমে পড়া হয়। যখন একাধিক বিট একই সময়ে পড়া হয়, তখন পূর্ণসংখ্যা মূল ক্রমে মূল ডেটা থেকে তৈরি হয়। প্রত্যাবর্তিত পূর্ণসংখ্যার সবচেয়ে উল্লেখযোগ্য বিটগুলিও মূল ডেটার সবচেয়ে উল্লেখযোগ্য বিট। সুতরাং, বিবৃতি
b = ReadBits(2);
নীচের দুটি বিবৃতি সঙ্গে সমতুল্য:
b = ReadBits(1);
b |= ReadBits(1) << 1;
আমরা অনুমান করি যে প্রতিটি রঙের উপাদান, অর্থাৎ আলফা, লাল, নীল এবং সবুজ, একটি 8-বিট বাইট ব্যবহার করে উপস্থাপন করা হয়েছে। আমরা সংশ্লিষ্ট ধরনটিকে uint8 হিসাবে সংজ্ঞায়িত করি। একটি সম্পূর্ণ ARGB পিক্সেলকে uint32 নামক একটি প্রকার দ্বারা উপস্থাপিত করা হয়, যা 32 বিট সমন্বিত একটি স্বাক্ষরবিহীন পূর্ণসংখ্যা। রূপান্তরগুলির আচরণ দেখানো কোডে, এই মানগুলি নিম্নলিখিত বিটে কোডিফাই করা হয়েছে: বিটগুলিতে আলফা 31..24, বিটে লাল 23..16, বিটে সবুজ 15..8 এবং বিটগুলিতে নীল 7.. 0; যাইহোক, বিন্যাসের বাস্তবায়ন অভ্যন্তরীণভাবে অন্য উপস্থাপনা ব্যবহার করার জন্য বিনামূল্যে।
বিস্তৃতভাবে, একটি ওয়েবপি ক্ষতিহীন ছবিতে হেডার ডেটা, ট্রান্সফর্ম তথ্য এবং প্রকৃত চিত্র ডেটা থাকে। হেডারে ছবির প্রস্থ এবং উচ্চতা থাকে। একটি WebP ক্ষতিহীন ছবি এনট্রপি এনকোড হওয়ার আগে চারটি ভিন্ন ধরনের রূপান্তরের মধ্য দিয়ে যেতে পারে। বিটস্ট্রিমের ট্রান্সফর্ম তথ্যে সংশ্লিষ্ট ইনভার্স ট্রান্সফর্ম প্রয়োগ করার জন্য প্রয়োজনীয় ডেটা থাকে।
2 নামকরণ
- এআরজিবি
- আলফা, লাল, সবুজ এবং নীল মান সমন্বিত একটি পিক্সেল মান।
- ARGB ছবি
- ARGB পিক্সেল সমন্বিত একটি দ্বি-মাত্রিক বিন্যাস।
- রঙ ক্যাশে
- একটি ছোট হ্যাশ-অ্যাড্রেসেড অ্যারে যা সম্প্রতি ব্যবহৃত রঙগুলিকে সংক্ষিপ্ত কোডগুলির সাথে স্মরণ করতে সক্ষম হবে।
- কালার ইনডেক্সিং ইমেজ
- রঙের একটি এক-মাত্রিক চিত্র যা একটি ছোট পূর্ণসংখ্যা ব্যবহার করে সূচিবদ্ধ করা যেতে পারে (WebP লসলেস এর মধ্যে 256 পর্যন্ত)।
- রঙ রূপান্তর ইমেজ
- রঙের উপাদানগুলির পারস্পরিক সম্পর্ক সম্পর্কে ডেটা ধারণকারী একটি দ্বি-মাত্রিক সাব-রেজোলিউশন চিত্র।
- দূরত্ব ম্যাপিং
- দ্বি-মাত্রিক প্রক্সিমিটিতে পিক্সেলের জন্য ক্ষুদ্রতম মান থাকতে LZ77 দূরত্ব পরিবর্তন করে।
- এনট্রপি ইমেজ
- একটি দ্বি-মাত্রিক সাবরেজোলিউশন ইমেজ ইঙ্গিত করে যে কোন এনট্রপি কোডিং ইমেজের একটি বর্গাকারে ব্যবহার করা উচিত, অর্থাৎ প্রতিটি পিক্সেল একটি মেটা প্রিফিক্স কোড।
- LZ77
- একটি অভিধান-ভিত্তিক স্লাইডিং উইন্ডো কম্প্রেশন অ্যালগরিদম যা হয় প্রতীক নির্গত করে বা অতীতের প্রতীকগুলির ক্রম হিসাবে বর্ণনা করে।
- মেটা উপসর্গ কোড
- একটি ছোট পূর্ণসংখ্যা (16 বিট পর্যন্ত) যা মেটা উপসর্গ টেবিলের একটি উপাদানকে সূচী করে।
- ভবিষ্যদ্বাণীকারী চিত্র
- একটি দ্বি-মাত্রিক উপ-রেজোলিউশন চিত্র যা নির্দেশ করে যে চিত্রের একটি নির্দিষ্ট বর্গক্ষেত্রের জন্য কোন স্থানিক ভবিষ্যদ্বাণী ব্যবহার করা হয়েছে।
- উপসর্গ কোড
- এনট্রপি কোডিং করার একটি ক্লাসিক উপায় যেখানে আরও ঘন ঘন কোডের জন্য অল্প সংখ্যক বিট ব্যবহার করা হয়।
- উপসর্গ কোডিং
- বৃহত্তর পূর্ণসংখ্যার এনট্রপি কোড করার একটি উপায়, যা একটি এনট্রপি কোড ব্যবহার করে পূর্ণসংখ্যার কয়েকটি বিট কোড করে এবং অবশিষ্ট বিটগুলিকে কাঁচা কোড করে। এটি এনট্রপি কোডের বর্ণনাকে অপেক্ষাকৃত ছোট রাখার অনুমতি দেয় এমনকি যখন প্রতীকের পরিসর বড় হয়।
- স্ক্যান-লাইন অর্ডার
- পিক্সেলের একটি প্রক্রিয়াকরণ ক্রম (বাম থেকে ডান এবং উপরে থেকে নীচে), বাম-হাত-শীর্ষ পিক্সেল থেকে শুরু করে। একবার একটি সারি সম্পন্ন হলে, পরবর্তী সারির বাম হাতের কলাম থেকে চালিয়ে যান।
3 RIFF হেডার
হেডারের শুরুতে RIFF কন্টেইনার আছে। এটি নিম্নলিখিত 21 বাইট নিয়ে গঠিত:
- স্ট্রিং 'RIFF'।
- সামান্য-এন্ডিয়ান, খণ্ডের দৈর্ঘ্যের 32-বিট মান, যা RIFF শিরোনাম দ্বারা নিয়ন্ত্রিত অংশ��র সম্পূর্ণ আকার। সাধারণত, এটি পেলোড আকারের সমান (ফাইলের আকার বিয়োগ 8 বাইট: 'RIFF' শনাক্তকারীর জন্য 4 বাইট এবং মান নিজেই সংরক্ষণ করার জন্য 4 বাইট)।
- স্ট্রিং 'WEBP' (RIFF ধারক নাম)।
- স্ট্রিং 'VP8L' (লসলেস-এনকোডেড ইমেজ ডেটার জন্য ফোরসিসি)।
- লসলেস স্ট্রীমে বাইটের সংখ্যার সামান্য-এন্ডিয়ান, 32-বিট মান।
- 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);
সংস্করণ_সংখ্যাটি একটি 3 বিট কোড যা অবশ্যই 0 তে সেট করা উচিত। অন্য যেকোনো মানকে একটি ত্রুটি হিসাবে বিবেচনা করা উচিত।
int version_number = ReadBits(3);
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).
যদি একটি ট্রান্সফর্ম উপস্থিত থাকে, তাহলে পরবর্তী দুটি বিট ট্রান্সফর্ম টাইপ নির্দিষ্ট করে। চার ধরনের রূপান্তর আছে।
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টি ভবিষ্যদ্বাণীকারীর মধ্যে কোনটি ARGB ছবির একটি নির্দিষ্ট ব্লকের মধ্যে সমস্ত block_width * block_height পিক্সেলের জন্য ব্যবহৃত হয় তা নির্ধারণ করে। এই সাব-রেজোলিউশন ইমেজটি অধ্যায় 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 | এল |
| 2 | টি |
| 3 | টিআর |
| 4 | টিএল |
| 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(গড়2(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-পিক্সেল, এবং সমস্ত পিক্সেল বামদিকের কলামে রয়েছে টি-পিক্সেল।
ডানদিকের কলামে পিক্সেলের জন্য টিআর-পিক্সেল সম্বোধন করা ব্যতিক্রমী। ডানদিকের কলামের পিক্সেলগুলি মোডগুলি [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) মানকে রূপান্তরিত করে এবং তারপরে লাল মানের উপর।
ভবিষ্যদ্বাণীকারী ট্রান্সফর্মের ক্ষেত্রে যেমনটি হয়, প্রথমে ছবিটিকে ব্লকে ভাগ করা হয় এবং ব্লকের সমস্ত পিক্সেলের জন্য একই ট্রান্সফর্ম মোড ব্যবহার করা হয়। প্রতিটি ব্লকের জন্য, তিনটি ধরণের রঙ রূপান্তর উপাদান রয়েছে।
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 একটি 3.5-স্থির-বিন্দু সংখ্যা এবং একটি স্বাক্ষরিত 8-বিট RGB রঙের চ্যানেল (c) [-128..127] প্রতিনিধিত্ব করে একটি স্বাক্ষরিত 8-বিট পূর্ণসংখ্যা ব্যবহার করে গণনা করা হয় এবং নিম্নরূপ সংজ্ঞায়িত করা হয়:
int8 ColorTransformDelta(int8 t, int8 c) {
return (t * c) >> 5;
}
ColorTransformDelta() কল করার আগে 8-বিট স্বাক্ষরবিহীন প্রতিনিধিত্ব (uint8) থেকে 8-বিট স্বাক্ষরিত একটি (int8) তে একটি রূপান্তর প্রয়োজন। স্বাক্ষরিত মানটিকে 8-বিট দুই-এর পরিপূরক সংখ্যা হিসাবে ব্যাখ্যা করা উচিত (অর্থাৎ: uint8 পরিসর [128..255] রূপান্তরিত int8 মানের [-128..-1] পরিসরে ম্যাপ করা হয়েছে)।
গুণটি আরও নির্ভুলতা ব্যবহার করে (অন্তত 16-বিট নির্ভুলতা সহ) করতে হবে। শিফট অপারেশনের সাইন এক্সটেনশন সম্পত্তি এখানে কোন ব্যাপার নয়; ফলাফল থেকে শুধুমাত্র সর্বনিম্ন 8 বিট ব্যবহার করা হয়, এবং এই বিটগুলিতে, সাইন এক্সটেনশন স্থানান্তর এবং স্বাক্ষরবিহীন স্থানান্তর একে অপরের সাথে সামঞ্জস্যপূর্ণ।
এখন, আমরা কালার ট্রান্সফর্ম ডেটার বিষয়বস্তু বর্ণনা করি যাতে ডিকোডিং ইনভারস কালার ট্রান্সফর্ম প্রয়োগ করতে পারে এবং আসল লাল এবং নীল মান পুনরুদ্ধার করতে পারে। কালার ট্রান্সফর্ম ডেটার প্রথম 3 বিটগুলিতে বিটের সংখ্যায় ইমেজ ব্লকের প্রস্থ এবং উচ্চতা থাকে, ঠিক যেমন ভবিষ্যদ্বাণীকারী রূপান্তর:
int size_bits = ReadBits(3) + 2;
int block_width = 1 << size_bits;
int block_height = 1 << size_bits;
কালার ট্রান্সফর্ম ডেটার অবশিষ্ট অংশে ColorTransformElement দৃষ্টান্ত রয়েছে, ইমেজের প্রতিটি ব্লকের সাথে সম্পর্কিত। প্রতিটি ColorTransformElement 'cte' একটি সাবরেজোলিউশন ইমেজে একটি পিক্সেল হিসাবে ধরা হয় যার আলফা উপাদান হল 255 , লাল উপাদান হল cte.red_to_blue , সবুজ উপাদান হল cte.green_to_blue এবং নীল উপাদান হল cte.green_to_red ।
ডিকোডিংয়ের সময়, ব্লকগুলির ColorTransformElement উদাহরণগুলি ডিকোড করা হয় এবং পিক্সেলের ARGB মানগুলিতে বিপরীত রঙের রূপান্তর প্রয়োগ কর�� হয়। পূর্বে উল্লিখিত হিসাবে, সেই বিপরীত রঙের রূপান্তরটি লাল এবং নীল চ্যানেলগুলিতে শুধুমাত্র ColorTransformElement মান যোগ করছে। আলফা এবং গ্রিন চ্যানেলগুলি যেমন রয়েছে তেমনই রেখে দেওয়া হয়েছে।
void InverseTransform(uint8 red, uint8 green, uint8 blue,
ColorTransformElement *trans,
uint8 *new_red, uint8 *new_blue) {
// Transformed values of red and blue components
int tmp_red = red;
int tmp_blue = blue;
// Applying the inverse transform is just adding the
// color transform deltas
tmp_red += ColorTransformDelta(trans->green_to_red, green);
tmp_blue += ColorTransformDelta(trans->green_to_blue, green);
tmp_blue +=
ColorTransformDelta(trans->red_to_blue, tmp_red & 0xff);
*new_red = tmp_red & 0xff;
*new_blue = tmp_blue & 0xff;
}
4.3 সবুজ রূপান্তর বিয়োগ করুন
বিয়োগ করা সবুজ রূপান্তর প্রতিটি পিক্সেলের লাল এবং নীল মান থেকে সবুজ মান বিয়োগ করে। যখন এই রূপান্তরটি উপস্থিত থাকে, তখন ডিকোডারকে লাল এবং নীল উভয় মানের সাথে সবুজ মান যোগ করতে হবে। এই রূপান্তরের সাথে সম্পর্কিত কোন তথ্য নেই। ডিকোডার নিম্নরূপ বিপরীত রূপান্তর প্রয়োগ করে:
void AddGreenToBlueAndRed(uint8 green, uint8 *red, uint8 *blue) {
*red = (*red + green) & 0xff;
*blue = (*blue + green) & 0xff;
}
এই রূপান্তরটি অপ্রয়োজনীয়, কারণ এটি কালার ট্রান্সফর্ম ব্যবহার করে মডেল করা যেতে পারে, কিন্তু যেহেতু এখানে কোনও অতিরিক্ত ডেটা নেই, তাই বিয়োগ করা সবুজ ট্রান্সফর্মটি সম্পূর্ণ-বিকশিত রঙের রূপান্তরের চেয়ে কম বিট ব্যবহার করে কোড করা যেতে পারে।
4.4 কালার ইনডেক্সিং ট্রান্সফর্ম
যদি অনেকগুলি অনন্য পিক্সেল মান না থাকে তবে একটি রঙ সূচক অ্যারে তৈরি করা এবং অ্যারের সূচকগুলির দ্বারা পিক্সেল মানগুলি প্রতিস্থাপন করা আরও কার্যকর হতে পারে। কালার ইনডেক্সিং ট্রান্সফর্ম এটি অর্জন করে। (WebP লসলেস প্রসঙ্গে, আমরা বিশেষভাবে এটিকে প্যালেট ট্রান্সফর্ম বলি না কারণ WebP লসলেস এনকোডিং-এ একই রকম কিন্তু আরও গতিশীল ধারণা বিদ্যমান: কালার ক্যাশে।)
কালার ইনডেক্সিং ট্রান্সফর্ম ইমেজে অনন্য ARGB মানের সংখ্যা পরীক্ষা করে। যদি সেই সংখ্যাটি একটি থ্রেশহোল্ডের নিচে থাকে (256), এটি সেই ARGB মানগুলির একটি অ্যারে তৈরি করে, যা পিক্সেল মানগুলিকে সংশ্লিষ্ট সূচকের সাথে প্রতিস্থাপন করতে ব্যবহৃত হয়: পিক্সেলগুলির সবুজ চ্যানেল সূচকের সাথে প্রতিস্থাপিত হয়, সমস্ত আলফা মানগুলি 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 এর মান নির্দেশ করে যে দুটি পিক্সেল একত্রিত হয়েছে, এবং প্রতিটি পিক্সেলের একটি পরিসর রয়েছে [0..15]। 2 এর মান নির্দেশ করে যে চারটি পিক্সেল একত্রিত হয়েছে এবং প্রতিটি পিক্সেলের একটি পরিসর রয়েছে [0..3]। 3 এর মান নির্দেশ করে যে আটটি পিক্সেল একত্রিত হয়েছে এবং প্রতিটি পিক্সেলের একটি পরিসর রয়েছে [0..1], অর্থাৎ একটি বাইনারি মান।
মানগুলি নিম্নরূপ ��বুজ উপাদানে প্যাক করা হয়:
-
width_bits= 1: প্রতিটি x মানের জন্য, যেখানে x ≡ 0 (mod 2), x-এ একটি সবুজ মান x/2-এ সবুজ মানের 4টি সর্বনিম্ন উল্লেখযোগ্য বিটে অবস্থান করা হয় এবং x + 1-এ একটি সবুজ মান স্থাপন করা হয় x/2-এ সবুজ মানের 4টি সবচেয়ে উল্লেখযোগ্য বিটের মধ্যে। -
width_bits= 2: প্রতিটি x মানের জন্য, যেখানে x ≡ 0 (mod 4), x-এ একটি সবুজ মান x/4-এ সবুজ মানের 2টি সর্বনিম্ন-গুরুত্বপূর্ণ বিটে এবং x + 1 থেকে x-এ সবুজ মান স্থাপন করা হয় x/4-এ সবুজ মানের আরও তাৎপর্যপূর্ণ বিটগুলির জন্য + 3-এর অবস্থান। -
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 ইমেজ ডেটার ভূমিকা
আমরা পাঁচটি ভিন্ন ভূমিকায় ইমেজ ডেটা ব্যবহার করি:
- ARGB ইমেজ: ছবির প্রকৃত পিক্সেল সংরক্ষণ করে।
- এনট্রপি ইমেজ: মেটা প্রিফিক্স কোড সংরক্ষণ করে ( "মেটা প্রিফিক্স কোডের ডিকোডিং" দেখুন)।
- ভবিষ্যদ্বাণীকারী চিত্র: ভবিষ্যদ্বাণীকারী রূপান্তরের জন্য মেটাডেটা সংরক্ষণ করে ( "ভবিষ্যদ্বাণী রূপান্তর" দেখুন)।
- কালার ট্রান্সফর্ম ইমেজ: ইমেজের বিভিন্ন ব্লকের জন্য
ColorTransformElementমান ( "Color Transform" -এ সংজ্ঞায়িত) দ্বারা তৈরি। - কালার ইন্ডেক্সিং ইমেজ:
color_table_size(256 ARGB মান পর্যন্ত) আকারের একটি অ্যারে যা কালার ইন্ডেক্সিং ট্রান্সফর্মের জন্য মেটাডেটা সঞ্চয় করে ( "কালার ইনডেক্সিং ট্রান্সফর্ম" দেখুন)।
5.2 ইমেজ ডেটার এনকোডিং
ইমেজ ডেটার এনকোডিং এর ভূমিকা থেকে স্বাধীন।
ছবিটি প্রথমে নির্দিষ্ট আকারের ব্লকের একটি সেটে বিভক্ত করা হয় (সাধারণত 16x16 ব্লক)। এই ব্লকগুলির প্রতিটি তাদের নিজস্ব এনট্রপি কোড ব্যবহার করে মডেল করা হয়। এছাড়াও, বেশ কয়েকটি ব্লক একই এনট্রপি কোড শ��য়ার করতে পারে।
যুক্তি: একটি এনট্রপি কোড সংরক্ষণ করার জন্য একটি খরচ হয়। এই খরচ কমানো যেতে পারে যদি পরিসংখ্যানগতভাবে অনুরূপ ব্লকগুলি একটি এনট্রপি কোড ভাগ করে, যার ফলে সেই কোডটি শুধুমাত্র একবার সংরক্ষণ করা হয়। উদাহরণস্বরূপ, একটি এনকোডার তাদের পরিসংখ্যানগত বৈশিষ্ট্যগুলি ব্যবহার করে ক্লাস্টার করে অনুরূপ ব্লকগুলি খুঁজে পেতে পারে বা বারবার এলোমেলোভাবে নির্বাচিত ক্লাস্টারগুলির একটি জোড়া যোগ করে যখন এটি চিত্রটিকে এনকোড করার জন্য প্রয়োজনীয় বিটের সামগ্রিক পরিমাণ হ্রাস করে।
প্রতিটি পিক্সেল তিনটি সম্ভাব্য পদ্ধতির একটি ব্যবহার করে এনকোড করা হয়:
- উপসর্গ-কোডেড আক্ষরিক: প্রতিটি চ্যানেল (সবুজ, লাল, নীল এবং আলফা) স্বাধীনভাবে এনট্রপি-কোডেড।
- LZ77 ব্যাকওয়ার্ড রেফারেন্স: পিক্সেলের একটি ক্রম চিত্রের অন্য কোথাও থেকে অনুলিপি করা হয়েছে।
- রঙের ক্যাশে কোড: সম্প্রতি দেখা রঙের একটি সংক্ষিপ্ত গুণগত হ্যাশ কোড (কালার ক্যাশে সূচক) ব্যবহার করে।
নিম্নলিখিত উপবিভাগগুলি এগুলির প্রত্যেকটি বিশদভাবে বর্ণনা করে।
5.2.1 উপসর্গ-কোডেড লিটারেল
পিক্সেলটি সবুজ, লাল, নীল এবং আলফা (সেই ক্রমে) প্রিফিক্স-কোডেড মান হিসাবে সংরক্ষণ করা হয়। বিস্তারিত জানার জন্য বিভাগ 6.2.3 দেখুন।
5.2.2 LZ77 ব্যাকওয়ার্ড রেফারেন্স
ব্যাকওয়ার্ড রেফারেন্স হল দৈর্ঘ্য এবং দূরত্বের কোডের টিপল:
- দৈর্ঘ্য নির্দেশ করে কত পিক্সেল স্ক্যান-লাইন ক্রমে কপি করা হবে।
- দূরত্ব কোড হল একটি সংখ্যা যা পূর্বে দেখা একটি পিক্সেলের অবস্থান নির্দেশ করে, যেখান থেকে পিক্সেলগুলি কপি করা হবে। সঠিক ম্যাপিং নীচে বর্ণিত হয়েছে।
দৈর্ঘ্য এবং দূরত্বের মানগুলি LZ77 উপসর্গ কোডিং ব্যবহার করে সংরক্ষণ করা হয়।
LZ77 উপসর্গ কোডিং বড় পূর্ণসংখ্যার মানকে দুটি ভাগে ভাগ করে: উপসর্গ কোড এবং অতিরিক্ত বিট । প্রিফিক্স কোডটি একটি এনট্রপি কোড ব্যবহার করে সংরক্ষণ করা হয়, যখন অতিরিক্ত বিটগুলি যে��ন রয়েছে (এনট্রপি কোড ছাড়াই) সংরক্ষণ করা হয়।
যুক্তি : এই পদ্ধতিটি এনট্রপি কোডের জন্য স্টোরেজ প্রয়োজনীয়তা হ্রাস করে। এছাড়াও, বড় মান সাধারণত বিরল, তাই চিত্রের খুব কম মানের জন্য অতিরিক্ত বিট ব্যবহার করা হবে। এইভাবে, এই পদ্ধতির ফলাফল সামগ্রিকভাবে ভাল সংকোচন হয়।
নিম্নলিখিত সারণীটি উপসর্গ কোড এবং অতিরিক্ত বিটগুলিকে বোঝায় যা মানগুলির বিভিন্ন পরিসর সংরক্ষণের জন্য ব্যবহৃত হয়।
| মান পরিসীমা | উপসর্গ কোড | অতিরিক্ত বিট |
|---|---|---|
| 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) অফসেট নির্দেশ করে, অর্থাৎ বর্তমান পিক্সেলের উপরে পিক্সেল (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 এ বর্ণিত)।
রঙ ক্যাশে কোড নিম্নরূপ সংরক্ষণ করা হয়. প্রথমত, একটি 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 রঙ সঞ্চয় করে। রঙগুলিকে (0x1e35a7bd * color) >> (32 - color_cache_code_bits) দ্বারা সূচীকরণ করে দেখা হয়। একটি রঙ ক্যাশে শুধুমাত্র একটি সন্ধান করা হয়; কোন দ্বন্দ্ব সমাধান আছে.
একটি চিত্রের ডিকোডিং বা এনকোডিংয়ের শুরুতে, সমস্ত রঙের ক্যাশে মানগুলির সমস্ত এন্ট্রি শূন্যতে সেট করা হয়। রঙের ক্যাশে কোড ডিকোডিং সময়ে এই রঙে রূপান্তরিত হয়। প্রতিটি পিক্সেল ঢোকানোর মাধ্যমে কালার ক্যাশের অবস্থা বজায় রাখা হয়, সেটি ব্যাকওয়ার্ড রেফারেন্সিং বা আক্ষরিক হিসাবে উত্পাদিত হোক না কেন, স্ট্রীমে প্রদর্শিত ক্রমে ক্যাশেতে।
6 এনট্রপি কোড
6.1 ওভারভিউ
বেশিরভাগ ডেটা একটি ক্যানোনিকাল প্রিফিক্স কোড ব্যবহার করে কোড করা হয়। তাই, প্রকৃত উপসর্গ কোডের বিপরীতে প্রিফিক্স কোড দৈর্ঘ্য পাঠিয়ে কোডগুলি প্রেরণ করা হয়।
বিশেষ করে, বিন্যাসে স্থানিক বৈকল্পিক উপসর্গ কোডিং ব্যবহার করা হয়। অন্য কথায়, ছবির বিভিন্ন ব্লক সম্ভাব্যভাবে বিভিন্ন এনট্রপি কোড ব্যবহার করতে পারে।
যুক্তি : চিত্রের বিভিন্ন ক্ষেত্রের বিভিন্ন বৈশিষ্ট্য থাকতে পারে। সুতরাং, তাদের বিভিন্ন এনট্রপি কোড ব্যবহার করার অনুমতি দেওয়া আরও নমনীয়তা এবং সম্ভাব্য ভাল কম্প্রেশন প্রদান করে।
6.2 বিশদ
এনকোডেড ইমেজ ডেটাতে কয়েকটি অংশ থাকে:
- প্রিফিক্স কোডগুলি ডিকোডিং এবং তৈরি করা।
- মেটা উপসর্গ কোড.
- এনট্রপি-কোডেড ইমেজ ডেটা।
যেকোনো প্রদত্ত পিক্সেলের জন্য (x, y), এটির সাথে যুক্ত পা������ি প���������িক্স কোড���র একটি সেট রয়েছে। এই কোডগুলি হল (বিটস্ট্রিম ক্রমে):
- প্রিফিক্স কোড #1 : সবুজ চ্যানেল, ব্যাকওয়ার্ড-রেফারেন্স দৈর্ঘ্য এবং রঙের ক্যাশের জন্য ব্যবহৃত হয়।
- প্রিফিক্স কোড #2, #3, এবং #4 : যথাক্রমে লাল, নীল এবং আলফা চ্যানেলের জন্য ব্যবহৃত হয়।
- উপসর্গ কোড #5 : ব্যাকওয়ার্ড-রেফারেন্স দূরত্বের জন্য ব্যবহৃত হয়।
এখান থেকে, আমরা এই সেটটিকে একটি প্রিফিক্স কোড গ্রুপ হিসাবে উল্লেখ করি।
6.2.1 ডিকোডিং এবং প্রিফিক্স কোড তৈরি করা
এই বিভাগটি বর্ণনা করে কিভাবে বিটস্ট্রিম থেকে প্রিফিক্স কোডের দৈর্ঘ্য পড়তে হয়।
প্রিফিক্স কোডের দৈর্ঘ্য দুটি উপায়ে কোড করা যেতে পারে। ব্যবহৃত পদ্ধতিটি একটি 1-বিট মান দ্বারা নির্দিষ্ট করা হয়।
- এই বিট 1 হলে, এটি একটি সাধারণ কোড দৈর্ঘ্য কোড ।
- যদি এই বিটটি 0 হয় তবে এটি একটি সাধারণ কোড দৈর্ঘ্যের কোড ।
উভয় ক্ষেত্রেই, অব্যবহৃত কোড দৈর্ঘ্য থাকতে পারে যা এখনও স্ট্রিমের অংশ। এটি অদক্ষ হতে পারে, তবে এটি বিন্যাস দ্বারা অনুমোদিত। বর্ণিত গাছ একটি সম্পূর্ণ বাইনারি গাছ হতে হবে. একটি একক লিফ নোডকে একটি সম্পূর্ণ বাইনারি ট্রি হিসাবে বিবেচনা করা হয় এবং সাধারণ কোড দৈর্ঘ্য কোড বা সাধারণ কোড দৈর্ঘ্য কোড ব্যবহার করে এনকোড করা যেতে পারে। সাধারণ কোড দৈর্ঘ্য কোড ব্যবহার করে একটি একক লিফ নোড কোডিং করার সময়, একটি কোডের দৈর্ঘ্য ব্যতীত সমস্ত শূন্য থাকে এবং একক পাতার নোডের মান 1 এর দৈর্ঘ্য দিয়ে চিহ্নিত করা হয় -- এমনকি যখন সেই একক পাতার নোড গাছটি ব্যবহার করা হয় তখন কোনো বিট ব্যবহার করা হয় না। .
সরল কোড দৈর্ঘ্য কোড
এই বৈকল্পিকটি বিশেষ ক্ষেত্রে ব্যবহার করা হয় যখন শুধুমাত্র 1 বা 2টি উপসর্গ চিহ্ন কোড দৈর্ঘ্য 1 সহ [0..255] পরিসরে থাকে। অন্যান্য সমস্ত প্রিফিক্স কোড দৈর্ঘ্য অন্তর্নিহিতভাবে শূন্য।
প্রথম বিটটি চিহ্নের সংখ্যা নির্দেশ করে:
int num_symbols = ReadBits(1) + 1;
নিম্নলিখিত প্রতীক মান আছে.
এই প্রথম প্রতীকটি is_first_8bits এর মানের উপর নির্ভর করে 1 বা 8 বিট ব্যবহার করে কোড করা হয়েছে। পরিসীমা যথাক্রমে [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;
}
দুটি প্রতীক আলাদা হতে হবে। ডুপ্লিকেট প্রতীক অনুমোদিত, কিন্তু অদক্ষ.
দ্রষ্টব্য: আরেকটি বিশেষ ক্ষেত্রে যখন সমস্ত প্রিফিক্স কোডের দৈর্ঘ্য শূন্য হয় (একটি খালি উপসর্গ কোড)। উদাহরণস্বরূপ, দূরত্বের জন্য একটি প্রিফিক্স কোড খালি হতে পারে যদি কোন পশ্চাদগামী রেফারেন্স না থাকে। একইভাবে, রঙ ক্যাশে ব্যবহার করে একই মেটা প্রিফিক্স কোডের মধ্যে সমস্ত পিক্সেল তৈরি করা হলে আলফা, লাল এবং নীলের উপসর্গগুলি খালি হতে পারে। যাইহোক, এই ক্ষেত্রে বিশেষ পরিচালনার প্রয়োজন নেই, কারণ খালি প্রিফিক্স কোডগুলিকে একটি একক চিহ্ন 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 মেটা প্রিফিক্স কোডের ডিকোডিং
আগেই উল্লেখ করা হয়েছে, বিন্যাসটি ছবির বিভিন্ন ব্লকের জন্য বিভিন্ন উপসর্গ কোড ব্যবহার করার অনুমতি দেয়। মেটা প্রিফিক্স কোড হল ইমেজের বিভিন্ন অংশে কোন প্রিফিক্স কোড ব্যবহার করতে হবে তা চিহ্নিত করে।
মেটা প্রিফিক্স কোডগুলি শুধুমাত্র তখনই ব্যবহার করা যেতে পারে যখন ছবিটি একটি ARGB ছবির ভূমিকায় ব্যবহার করা হচ্ছে৷
একটি 1-বিট মান দ্বারা নির্দেশিত মেটা উপসর্গ কোডগুলির জন্য দুটি সম্ভাবনা রয়েছে:
- যদি এই বিটটি শূন্য হয়, তবে চিত্রের সর্বত্র শুধুমাত্র একটি মেটা প্রিফিক্স কোড ব্যবহার করা হয়। আর কোন তথ্য ��ংরক্ষণ করা হয় না.
- এই বিটটি এক হলে, ছবিটি একাধিক মেটা প্রিফিক্স কোড ব্যবহার করে। এই মেটা প্রিফিক্স কোডগুলি একটি এনট্রপি ইমেজ হিসাবে সংরক্ষণ করা হয় (নীচে বর্ণিত)।
একটি পিক্সেলের লাল এবং সবুজ উপ��������গুলি ARGB ছবির একটি নির্দিষ্ট ব্লকে ব্যবহৃত একটি 16-বিট মেটা প্রিফিক্স কোড সংজ্ঞায়িত করে।
এনট্রপি ইমেজ
এনট্রপি ইমেজ ইমেজের বিভিন্ন অংশে কোন প্রিফিক্স কোড ব্যবহার করা হয়েছে তা নির্ধারণ করে।
প্রথম 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) এনট্রপি ইমেজে সংরক্ষিত বৃহত্তম প্রিফিক্স কোড নির্দেশ করে।
যেহেতু প্রতিটি প্রিফিক্স কোড গ্রুপে পাঁচটি প্রিফিক্স কোড থাকে, প্রিফিক্স কোডের মোট সংখ্যা হল:
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 এর ব্যাখ্যা তার মানের উপর নির��ভর করে:
- যদি S < 256
- সবুজ উপাদান হিসাবে S ব্যবহার করুন।
- প্রিফিক্স কোড #2 ব্যবহার করে বিটস্ট্রিম থেকে লাল পড়ুন।
- প্রিফিক্স কোড #3 ব্যবহার করে বিটস্ট্রিম থেকে নীল পড়ুন।
- প্রিফিক্স কোড #4 ব্যবহার করে বিটস্ট্রিম থেকে আলফা পড়ুন।
- যদি S >= 256 এবং S < 256 + 24 হয়
- একটি দৈর্ঘ্য প্রিফিক্স কোড হিসাবে S - 256 ব্যবহার করুন।
- বিটস্ট্রিম থেকে দৈর্ঘ্যের জন্য অতিরিক্ত বিট পড়ুন।
- দৈর্ঘ্য প্রিফিক্স কোড থেকে পশ্চাদগামী-রেফারেন্স দৈর্ঘ্য L নির্ধারণ করুন এবং অতিরিক্ত বিটগুলি পড়ুন।
- প্রিফিক্স কোড #5 ব্যবহার করে বিটস্ট্রিম থেকে দূরত্ব উপসর্গ কোড পড়ুন।
- বিটস্ট্রিম থেকে দূরত্বের জন্য অতিরিক্ত বিট পড়ুন।
- দূরত্বের উপসর্গ কোড থেকে পশ্চাদগামী-রেফারেন্স দূরত্ব D নির্ধারণ করুন এবং অতিরিক্ত বিটগুলি পড়ুন।
- বর্তমান অবস্থান বিয়োগ ডি পিক্সেল থেকে শুরু হওয়া পিক্সেলের ক্রম থেকে L পিক্সেল (স্ক্যান-লাইন ক্রমে) অনুলিপি করুন।
- S >= 256 + 24 হলে
- রঙ ক্যাশে সূচক হিসাবে S - (256 + 24) ব্যবহার করুন।
- সেই সূচকে রঙ ক্যাশে থেকে ARGB রঙ পান।
7 বিন্যাসের সামগ্রিক কাঠামো
নীচে অগমেন্টেড ব্যাকাস-নাউর ফর্ম (ABNF) RFC 5234 RFC 7405 ফর্ম্যাটের একটি দৃশ্য রয়েছে। এটি সমস্ত বিবরণ কভার করে না। ইমেজ-এর শেষ (EOI) শুধুমাত্র পিক্সেলের সংখ্যার (ছবির_প্রস্থ * চিত্র_উচ্চতা) মধ্যে অন্তর্নিহিতভাবে কোড করা হয়।
উল্লেখ্য যে *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