ترميز الحساب الثنائي التكيفي مع السياق

الموسوعة الحرة

يُعدّ ترميز الحساب الثنائي التكيفي مع السياق ( CABAC ) أحد أشكال ترميز الإنتروبيا المستخدمة في معايير H.264/MPEG-4 AVC [ 1 ] [ 2 ] وترميز الفيديو عالي الكفاءة (HEVC). وهو تقنية ضغط غير ضائعة للبيانات ، على الرغم من أن معايير ترميز الفيديو التي تُستخدم فيها عادةً ما تكون لتطبيقات الضغط الضائع للبيانات . يتميز CABAC بقدرته على توفير ضغط أفضل بكثير من معظم خوارزميات ترميز الإنتروبيا الأخرى المستخدمة في ترميز الفيديو، وهو أحد العناصر الرئيسية التي تُعطي نظام ترميز H.264/AVC قدرة ضغط أفضل من الأنظمة السابقة. [ 3 ]

في معيار H.264/MPEG-4 AVC ، لا يُدعم ترميز CABAC إلا في الإصدار الرئيسي والإصدارات الأعلى ( وليس الإصدار الموسع)، نظرًا لأنه يتطلب معالجة أكبر لفك التشفير مقارنةً بالترميز الأبسط المعروف باسم ترميز الطول المتغير التكيفي مع السياق (CAVLC) المستخدم في الإصدار الأساسي. كما يصعب تطبيق CABAC بالتوازي أو تحويله إلى متجه، لذا قد تُستخدم معه أشكال أخرى من التوازي (مثل التوازي المكاني). أما في معيار HEVC، فيُستخدم CABAC في جميع إصداراته.

الخوارزمية

يعتمد CABAC على الترميز الحسابي ، مع بعض الابتكارات والتغييرات لتكييفه مع احتياجات معايير ترميز الفيديو: [ 4 ]

  • يقوم بتشفير الرموز الثنائية، مما يحافظ على انخفاض التعقيد ويسمح بنمذجة الاحتمالات للبتات الأكثر استخدامًا لأي رمز.
  • يتم اختيار نماذج الاحتمالات بشكل تكيفي بناءً على السياق المحلي، مما يسمح بنمذجة أفضل للاحتمالات، لأن أنماط الترميز عادة ما تكون مرتبطة بشكل جيد محليًا.
  • يستخدم هذا الأسلوب قسمة النطاق بدون ضرب باستخدام نطاقات احتمالية كمية وحالات احتمالية.

يحتوي CABAC على أنماط احتمالية متعددة لسياقات مختلفة. يبدأ بتحويل جميع الرموز غير الثنائية إلى رموز ثنائية. ثم، لكل بت، يختار المشفر نموذج الاحتمالية المناسب، ثم يستخدم معلومات من العناصر المجاورة لتحسين تقدير الاحتمالية. وأخيرًا، تُطبق عملية الترميز الحسابي لضغط البيانات.

طريقة CABAC لترميز الإنتروبيا المستخدمة في معيار ضغط الفيديو H264 باللغة الإنجليزية

يُقدّم نمذجة السياق تقديراتٍ للاحتمالات الشرطية لرموز الترميز. وباستخدام نماذج سياق مناسبة، يُمكن استغلال التكرار بين الرموز عن طريق التبديل بين نماذج احتمالية مختلفة وفقًا للرموز المُرمّزة مسبقًا في جوار الرمز الحالي المراد ترميزه. وتُعزى معظم وفورات معدل البتات التي يُحققها نظام CABAC، والتي تُقارب 10%، مقارنةً بطريقة ترميز الإنتروبيا CAVLC، إلى نمذجة السياق.

تتضمن عملية ترميز رمز البيانات المراحل التالية.

  • التحويل إلى النظام الثنائي: يستخدم نظام CABAC ترميزًا حسابيًا ثنائيًا، ما يعني أنه يتم ترميز القرارات الثنائية فقط (1 أو 0). يتم تحويل الرموز غير الثنائية (مثل معامل التحويل أو متجه الحركة) إلى رمز ثنائي قبل الترميز الحسابي. تشبه هذه العملية عملية تحويل رمز البيانات إلى رمز متغير الطول، ولكن يتم ترميز الرمز الثنائي بشكل إضافي (بواسطة المرمز الحسابي) قبل الإرسال.
  • تتكرر المراحل لكل بت (أو "خانة") من الرمز الثنائي.
  • اختيار نموذج السياق: نموذج السياق هو نموذج احتمالي لخانة واحدة أو أكثر من خانات الرمز الثنائي. يمكن اختيار هذا النموذج من بين مجموعة من النماذج المتاحة بناءً على إحصائيات رموز البيانات المشفرة حديثًا. يخزن نموذج السياق احتمال أن تكون كل خانة "1" أو "0".
  • التشفير الحسابي: يقوم مشفر حسابي بتشفير كل خانة وفقًا لنموذج الاحتمالية المُختار. لاحظ أن هناك نطاقين فرعيين فقط لكل خانة (يُقابلان "0" و"1").
  • تحديث الاحتمالية: يتم تحديث نموذج السياق المحدد بناءً على القيمة المشفرة الفعلية (على سبيل المثال، إذا كانت قيمة الفئة "1"، فسيتم زيادة عدد مرات ظهور "1").

مثال

MVD xالتحويل إلى ثنائي
00
110
2110
31110
411110
5111110
61111110
711111110
8111111110

1. قم بتحويل قيمة MVDx، وهي فرق متجه الحركة في اتجاه x ، إلى قيمة ثنائية.

البت الأول من الكلمة المشفرة الثنائية هو bin 1؛ البت الثاني هو bin 2؛ وهكذا.

إي كيهنموذج السياق للفئة 1
0 ≤ e k < 3النموذج 0
3 ≤ e k < 33النموذج 1
33 ≤ e kالنموذج 2

2. اختر نموذج سياق لكل خانة. يتم اختيار أحد النماذج الثلاثة للخانة 1، بناءً على قيم MVD المشفرة سابقًا. يتم حساب معيار L1 لقيمتين مشفرتين سابقًا، e k .

سلة المهملاتنموذج السياق
10 أو 1 أو 2 حسب e k
23
34
45
5 وما فوق6

إذا كانت قيمة e k صغيرة، فمن المرجح أن يكون حجم MVD الحالي صغيرًا؛ وعلى العكس، إذا كانت قيمة e k كبيرة، فمن المرجح أن يكون حجم MVD الحالي كبيرًا. نختار جدول احتمالات (نموذج سياق) وفقًا لذلك. تُرمّز الفئات المتبقية باستخدام أحد نماذج السياق الأربعة الإضافية:

3. ترميز كل خانة. يوفر نموذج السياق المُختار تقديرين للاحتمالية: احتمال احتواء الخانة على القيمة "1" واحتمال احتواء الخانة على القيمة "0". يحدد هذان التقديران النطاقين الفرعيين اللذين يستخدمهما مُرمِّز العمليات الحسابية لترميز الخانة.

٤. تحديث نماذج السياق. على سبيل المثال، إذا تم اختيار نموذج السياق ٢ للفئة ١ وكانت قيمة الفئة ١ هي "٠"، فسيتم زيادة عدد مرات ظهور "٠". هذا يعني أنه في المرة القادمة التي يتم فيها اختيار هذا النموذج، ستكون احتمالية ظهور "٠" أعلى قليلاً. عندما يتجاوز العدد الإجمالي لظهور نموذج ما قيمة عتبة معينة، سيتم تقليل عدد مرات ظهور "٠" و"١"، مما يعطي في الواقع أولوية أعلى للملاحظات الحديثة.

محرك فك التشفير الحسابي

تم وصف وحدة فك التشفير الحسابي بتفصيلٍ ما في المعيار. ولها ثلاث خصائص مميزة:

  1. يتم تقدير الاحتمالية من خلال عملية انتقال بين 64 حالة احتمالية منفصلة لـ "الرمز الأقل احتمالية" (LPS، وهو الأقل احتمالية من بين القرارين الثنائيين "0" أو "1").
  2. يتم تحديد النطاق R الذي يمثل الحالة الحالية للمشفر الحسابي إلى نطاق صغير من القيم المحددة مسبقًا قبل حساب النطاق الجديد في كل خطوة، مما يجعل من الممكن حساب النطاق الجديد باستخدام جدول بحث (أي بدون ضرب).
  3. تم تعريف عملية تشفير وفك تشفير مبسطة لرموز البيانات ذات التوزيع الاحتمالي شبه المنتظم.

صُمم تعريف عملية فك التشفير لتسهيل تنفيذ عمليات التشفير وفك التشفير الحسابي بكفاءة منخفضة. وبشكل عام، يوفر CABAC كفاءة تشفير محسّنة مقارنةً بالتشفير القائم على CAVLC، على حساب زيادة التعقيد الحسابي.

تاريخ

في عام 1986، قدّم الباحثان في شركة IBM ، كوتاپورام إم إيه محي الدين وجورما يوهانس ريسانين، براءة اختراع لخوارزمية ترميز حسابي ثنائي لا تتطلب عمليات ضرب. [ 5 ] [ 6 ] وفي عام 1988، قدّم فريق بحثي من IBM، ضمّ آر بي آربس، وتي كي ترونغ، ودي جيه لو، ودبليو بي بينيباكر، وإل ميتشل، وجي جي لانغدون، خوارزمية ترميز حسابي ثنائي تكيفي (ABAC) تُعرف باسم Q-Coder. [ 7 ] [ 8 ]

استُشهد لاحقًا ببراءات الاختراع والأبحاث المذكورة أعلاه، إلى جانب العديد من الأبحاث الأخرى من شركتي IBM و Mitsubishi Electric ، من قِبل لجنة الاتصالات وتقنية المعلومات (CCITT) ومجموعة خبراء التصوير المشتركة كأساس لخوارزمية الترميز الحسابي الثنائي التكيفي لتنسيق ضغط الصور JPEG في عام 1992. [ 5 ] ومع ذلك، فإن برامج التشفير وفك التشفير لتنسيق ملف JPEG، الذي يتضمن خيارات لكل من ترميز هوفمان والترميز الحسابي، تدعم عادةً خيار ترميز هوفمان فقط، وكان ذلك في الأصل بسبب مخاوف تتعلق ببراءات الاختراع، على الرغم من أن براءات اختراع الترميز الحسابي لـ JPEG [ 9 ] قد انتهت صلاحيتها منذ ذلك الحين نظرًا لقدم معيار JPEG. [ 10 ] كان أول استخدام مُبلغ عنه للترميز الحسابي الثنائي التكيفي في ضغط الفيديو المتحرك في اقتراح قدمه باحثون من IBM إلى مجموعة MPEG في عام 1989. [ 11 ] [ 12 ] وقد وسّع هذا الاقتراح استخدام الترميز الحسابي من ترميز JPEG داخل الإطار إلى ترميز الفيديو بين الإطارات.

في عام ١٩٩٩، قدّم يونغجون يو ( من شركة تكساس إنسترومنتس )، ويونغ غاب كوون، وأنطونيو أورتيغا ( من جامعة جنوب كاليفورنيا ) شكلاً من أشكال الترميز الحسابي الثنائي المُكيَّف مع السياق. [ ١٣ ] وطُرحت خوارزمية الترميز الحسابي الثنائي المُكيَّف مع السياق (CABAC) تجاريًا مع تنسيق H.264/MPEG-4 AVC في عام ٢٠٠٣. [ ١٤ ] وتملك شركات باناسونيك ، وغودو كايشا آي بي بريدج ، وإل جي إلكترونيكس غالبية براءات اختراع تنسيق AVC . [ ١٥ ]

انظر أيضاً

مراجع

  1. ↑ ريتشاردسون، إيان إي جي، ورقة بيضاء H.264 / MPEG-4 الجزء 10 ، 17 أكتوبر 2002.
  2. ↑ ريتشاردسون، إيان إي جي (2003). ضغط الفيديو H.264 وMPEG-4: ترميز الفيديو للجيل القادم من الوسائط المتعددة . تشيتشستر: جون وايلي وأولاده المحدودة.
  3. ↑ زي-نيان لي؛ مارك إس. درو؛ جيانغتشوان ليو (9 أبريل 2014). أساسيات الوسائط المتعددة . سبرينغر ساينس آند بيزنس ميديا. ISBN 978-3-319-05290-8.
  4. ↑ ماربي، د.، شوارتز، هـ.، وويغاند، ت.، ترميز الحساب الثنائي التكيفي القائم على السياق في معيار ضغط الفيديو H.264/AVC ، معاملات IEEE للدوائر والأنظمة لتكنولوجيا الفيديو ، المجلد 13، العدد 7، الصفحات 620-636، يوليو 2003.
  5. 1 2 "T.81 - الضغط الرقمي وتشفير الصور الثابتة ذات النغمات المتواصلة - المتطلبات والإرشادات" (ملف PDF) . CCITT . سبتمبر 1992. تم الاطلاع عليه بتاريخ 12 يوليو 2019 .
  6. ↑ براءة اختراع أمريكية رقم 4,652,856
  7. ↑ آربس، آر بي؛ ترونغ، تي كي؛ لو، دي جيه؛ باسكو، آر سي؛ فريدمان، تي دي (نوفمبر 1988). "شريحة VLSI متعددة الأغراض لضغط البيانات التكيفي للصور ثنائية المستوى". مجلة IBM للبحوث والتطوير . 32 (6): 775-795 . doi : 10.1147/rd.326.0775 . ISSN 0018-8646 . 
  8. ↑ بينيباكر، دبليو بي؛ ميتشل، جيه إل؛ لانغدون، جي جي؛ آربس، آر بي (نوفمبر 1988). "نظرة عامة على المبادئ الأساسية لمشفّر الحساب الثنائي التكيفي Q-Coder". مجلة IBM للبحوث والتطوير . 32 (6): 717-726 . doi : 10.1147/rd.326.0717 . ISSN 0018-8646 . 
  9. ↑ "التوصية T.81 (1992) التصحيح 1 (01/04)" . التوصية T.81 (1992) . الاتحاد الدولي للاتصالات. 9 نوفمبر 2004. تم الاطلاع عليه في 3 فبراير 2011 .
  10. ↑ معيار ضغط بيانات الصور الثابتة JPEG ، دبليو بي بينيباكر وجيه إل ميتشل ، دار نشر كلوير الأكاديمية، 1992. ISBN 0-442-01272-1
  11. ↑ ترميز DCT لتخزين الفيديو المتحرك باستخدام الترميز الحسابي التكيفي ، CA Gonzales. L. Allman، T. McCarthy، P. Wendt و AN Akansu، معالجة الإشارات: اتصالات الصور، 2، 145، 1990.
  12. ↑ ترميز تسلسلات الفيديو المتحركة لبيئة MPEG باستخدام الترميز الحسابي ، إي. فيسيتو وسي. غونزاليس، SPIE الاتصالات المرئية ومعالجة الصور '90، 2-4 أكتوبر 1990.
  13. ↑ أورتيغا، أ. (أكتوبر 1999). "ضغط مجال الصورة المضمن باستخدام نماذج السياق". وقائع المؤتمر الدولي لمعالجة الصور لعام 1999 (رقم التصنيف 99CH36348) . المجلد 1. الصفحات 477-481. doi : 10.1109/ICIP.1999.821655 . ISBN   0-7803-5467-2. S2CID 27303716 . 
  14. ↑ "الترميز الحسابي الثنائي التكيفي القائم على السياق (CABAC)" . معهد فراونهوفر هاينريش هيرتز . تم الاطلاع عليه بتاريخ 13 يوليو 2019 .
  15. ↑ "قائمة براءات اختراع AVC/H.264" (ملف PDF) . MPEG LA . تم الاطلاع عليه بتاريخ 6 يوليو 2019 .