لقد ثبت فعّالة تقنيات تقدير الحركة Motion Estimation في مجالات الفيديو الرقمي وبذلك أصبحت عنصراً ومعياراً أساسياً في تقنيات ضغط الفيديو مثل المعيار MPEG والمعيار H.26X.
تعريف تقدير الحركة Motion Estimation:
هي عملية البحث عن منطقة ثابتة للإطار السابق من الفيديو لإيجاد كتلة من النقاط (block of pixels) متجانسة ومن نفس حجم في الإطار الحالي. وسنرمز في هذا المقال لتقدير الحركة بـ (ME).
هذه العملية تقتضي البحث المفصّل عن عدة كتل متجاورة للكتلة الحالية من الإطار السابق.
إن عملية تقدير الحركة هي عملية مكثفة للحاسوب تستخدم لتحقيق نسبة ضغط عالية للفيديو.
يبين الشكل (1) كيف يمكن لنظام فيديو رقمي استخدام تقنية تقدير الحركة ليميز الأهداف وكيف أن مواقعها تتغير في سلسلة من الصور.
الشكل (1) استخدام تقنية تقدير الحركة لتمييز الأهداف في نظام فيديو رقمي
في كل إطار صورة يقوم نظام تقدير الحركة بالبحث عن كتل تشبه تقريباً كتل أخرى في الصورة السابقة، وبمرور الزمن فإن تقدير الحركة للفيديو الرقمي يجد الكتل المتشابهة ويحدد المسارات (أشعة الحركة) التي تأخذها هذه الأهداف.
تقدير الحركة (ME) وأشعة الحركة:
يمكن أيضاً تعريف تقدير الحركة (ME): بأنها عملية تحديد أشعة الحركة والتي تصف التحول من صورة ثنائية البعد (2D) إلى أخرى، وعادةً ما تكون إطارات متجاورة في سياق سلسلة الفيديو.
يمكن لأشعة الحركة أن تخص كامل الصورة (فتدعى تقدير حركة شامل)، أو يمكن أن تخص منطقة أجزاء محددة مثل كتل مستطيلة الشكل، أو أجزاء عشوائية الشكل أو حتى نقاط (pixel).
في الشكل (2) نلاحظ أن الإطارات الداخلية (A1, A2, A3, …) يتم بناؤها بالاعتماد على الإطارات الخارجية (A, B) وذلك بالاعتماد على حقل شعاع الحركة الناتج عن تقدير الحركة (ME).
الشكل (2) يبين بناء الإطارات الداخلية بالاعتماد على الإطارات الخارجية وشعاع الحركة
إن تطبيق أشعة الحركة على صورة لتقوم بالتحويل إلى الصورة التالية يدعى: تعويضات الحركة Motion Compensation.
إن دمج تقنيات (توقع الحركة) و (تعويضات الحركة) هو الجزء الرئيس في عملية ضغط الفيديو، كما هو مستخدم في MPEG 1,2,and 4، بالإضافة إلى استخدامه في العديد من تقنيات تشفير الفيديو Video codecs.
الخوارزميات المستخدمة:
إن طرق إيجاد أشعة الحركة يمكن أن تصنّف إلى:
- مباشرة (direct): طرق معتمدة على النقاط Pixel based Methods
- غير مباشرة (indirect): طرق معتمدة على الملامح Feature based Methods
1- الطرق المباشرة Direct Methods:
أ. خوارزمية مطابقة الكتل Block Matching Algorithm (BMA):
هي طريقة لإيجاد كتل متطابقة في سلسلة إطارات الفيديو الرقمي لاستخدامها في تقدير الحركة.
إن الهدف من استعمال خوارزمية مطابقة الكتل هو لإيجاد كتل متطابقة من إطار i في إطارات أخرى j، والتي يمكن أن تكون قبل أو بعد الإطار i، وهذا يستخدم لاكتشاف التكرار في سلسلة الفيديو مما يزيد في كفاءة ضغط الفيديو.
ويبين الشكل (3) عملية مقارنة الكتل بين الإطارين iو j لتحقيق أقل قيمة للفرق.
الشكل (3) عملية البحث في الإطارات المتتابعة عن الكتل المتقابلة
ب. تقدير الحركة الهرمي:
وهي إحدى الطرق المستعملة في تقليل التعقيدات الحسابية الموجودة في خوارزمية مطابقة الكتل (BMA) السابقة، وتعتمد على النمذجة الفرعية للصورة من أجل الحصول على أحجام أصغر مما يخفّض من سرعة الحركة حسب معدّل النمذجة، تطبّق هذه العملية بشكل هرمي متعدد المستويات، وتعرف بخوارزمية مطابقة الكتل الهرمية (Hierarchical Block Matching Algorithm HMBA) .
يتم إعادة بناء الهرم المشكّل من إطارات الصورة عن طريق الترشيح ثنائي البعد المتتابع والنمذجة الفرعية للإطارات الحالية والسابقة، ويبين الشكل (4) هرم مكون من ثلاث مستويات.
الشكل (4) هرم يمثل خوارزمية HMBA
تعويض الحركة للكتلة:
يتم تعويض الحركة للكتلة وفق المراحل التالية:
· تقدير الحركة للكتلة وإيجاد أفضل تطابق.
· طرح الكتلة الحالية من الكتلة المقابلة في الإطار السابق من أجل تشكيل كتلة الفرق.
· ترميز الفرق وإرساله.
تعويض الحركة بالكتلة الماكروية:
الكتلة الماكروية هي عبارة عن منطقة تضم 16×16 نقطة (Pixel)، حيث تعتمد كلاً من تقنية MPEG4 و H.264 الكتلة الماكروية في معالجة الفيديو.
حجم كتلة تعويض الحركة:
نلاحظ أنه بتقليل حجم الكتلة الماكروية المستعمل في تقدير الحركة نحصل على نتائج أفضل من خلال تقليل الطاقة في الكتلة الماكروية المعبرة عن الفرق بين الإطارات،
هناك العديد من التقنيات لإيجاد الكتل المتقابلة ضمن الإطارات المتتابعة نذكر منها:
ج. تابع الترابط المتعارض Cross Correlation Function CCF
إن طريقة تابع الترابط المتعارض CCF هي طريقة قياسية لتقدير الزاوية لسلسلتين متعارضتين.
بفرض أن لدينا سلسلتين: x(i) and y(i) where i=0,1,2...N-1
فإن تابع الترابط المتعارض r بتأخير زمني قدره d يعرّف كما يلي:
د. متوسط الخطأ التربيعي Mean Square Error MSE
هـ. القيمة المطلقة لمتوسط الخطأ Mean Absolute Error MAE
في الحياة العملية غالباً ما يستعمل كلاً من MSE & MAE لأن تابع الترابط لا يستطيع متابعة التغيرات الناتجة عن الحركة بشكل جيد، وخصوصاً إذا كان هذا التغيير ليس كبيراً.
2- الطرق غير المباشرة Indirect Methods:
تستعمل الطرق غير المباشرة الميزات مثل زوايا هاريس Harris corners، وتطابق الميزات المتشابهة بين الإطارات، عادةً باستخدام توابع إحصائية تطبّق على منطقة موضعية أو شاملة.
والهدف من استعمال التابع الإحصائي هو لإزالة التطابق والذي لا يتوافق مع الحركة الحقيقية.
المراجع :
1) MPEG Motion Estimation
2) Motion estimation,
3) MPEG Fundamentals and Protocol Analysis, Tektronix, www.tektronix.com/
4) SIGGRAPH2010, http://and.intercon.ru/rtfrucvg_html_slides/#slide7
5) تقنيات ضغط الفيديو MPEG-4 ))، علاء غزال و عمر عكش
ليست هناك تعليقات:
إرسال تعليق