كيف قمت بإنشاء مرشح لا يفسد الصورة حتى بعد تشغيل مليون - الجزء 2

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

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

ولكن الآن بعد أن وجدت وقتًا للعودة إلى هذا الفلتر وكتابة مقال عنه ، يجب أن أطرح أخيرًا سؤالًا: هل هناك مرشح أقل وضوحًا لا يزال يحتفظ بخاصية "الاستقرار اللانهائي"؟

المفسد تحذير: الجواب الصحيح هو "ربما لا" و "بالتأكيد هناك." ولكن قبل أن نصل إلى سبب وجود إجابتين على هذا السؤال وماذا يعنيان ، دعونا نعد بشكل أفضل طاولة اختبار.

تعديل الأوفست

عندما عملت في البداية على هذه المشكلة ، لم يكن لدي أي فكرة عما كنت أبحث عنه. لم أكن أعرف حتى أن هناك شيئًا ما مثل عامل التصفية halfpel "غير المحدود" ، لذلك لم أقم بإنشاء نظام في بحثه. كنت أبحث فقط عن شيء من شأنه أن يقاوم التكرارات "العديدة" دون تشويه الصورة. تعكس جميع الصور من الجزء الأول هذه المنهجية: يتم نقل الصورة من اليمين إلى اليسار بمقدار نصف بكسل في كل مرة ، أي إذا قمت بتطبيق المرشح 100 مرة ، سيتم إزاحة الصورة الناتجة بمقدار 50 بكسل.

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

سيسمح لنا ذلك باختبار المرشحات تلقائيًا. نحن ببساطة نطبق المرشح عدة مرات ونرى أحد أمرين: إما التقارب مع صورة غير متغيرة ، مما يشير إلى أن المرشح مستقر بلا حدود ، أو انحراف كبير بشكل كبير عن الصورة الأصلية ، مما يشير إلى أن الفلتر "مكسور". بالنسبة لهذه الاختبارات ، اخترت متوسط ​​الخطأ لكل قناة 64 (من أصل 255) ، أو الحد الأقصى للخطأ في أي من القنوات إلى 255 كاملة كـ "كبير بشكل كبير". إذا كان أي من هذه الشروط صحيحًا ، فسنفترض أن المرشح "كسر" ".

إعادة اختبار المرشحات من الجزء الأول

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


هذه صورة بعد 244 تكرارًا. كما تتوقع ، فإن الصورة "تتكسر" تدريجياً بسبب متوسط ​​ثابت للبكسل. ولكن حتى يصل تدريجيا إلى الحد من الخطأ المتوسط.

هنا h.264:


لكسر الصورة ، 78 التكرار كافية بالنسبة له. يتصرف مرشح HEVC المكون من 8 عينات بشكل أفضل قليلاً ، ولكنه لا يزال يتكسر بعد 150 تكرارًا:


Lanczos مع 6 عينات فواصل بعد 166 التكرار:


هذا كل ما لدينا مرشحات مكسورة. كل ما تبقى هو مرشح عدد صحيح بلدي:


كما هو متوقع ، لم يكن الوحيد الذي يكسر. يتحول إلى صورة ثابتة بشكل لا نهائي بعد 208 تكرار.

ما نعرفه رائع هنا: على الأقل بالنسبة لمجموعة واسعة من صور الاختبار ، يكون هذا الفلتر ثابتًا إلى ما لا نهاية ، أي أنه لن يخلق قطعة أثرية أبدًا ، بغض النظر عن عدد مرات استخدامه.

هذا يعيدنا إلى السؤال الأصلي: هل هو حقًا الأفضل؟ وأنت تعرف الإجابات بالفعل ، لأنه في بداية المقال كتبت أيضًا: "ربما لا" و "بالتأكيد ، نعم".

دعنا أولاً نلقي نظرة على الجزء "ربما لا" أولاً.

مرشحات عدد صحيح

لذلك ، في الجزء الأول من المنشور ، ذكرت أن جوهر المرشح الذي وجدته هو "الأفضل من الذي تم اكتشافه" ، وهذا هو خصوصياته. وهنا هي الميزة:

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

ربما لاحظت أنه عندما عرضت معاملات h.264 و HEVC وفلتر الخط الثنائي ، وكذلك الفلتر الخاص بي ، كتبت عليها كأرقام عدد صحيح على مقام عدد صحيح ، مثل هذا:

MyKernel[] = {1.0/32.0, -4.0/32.0, 19.0/32.0, 19.0/32.0, -4.0/32.0, 1.0/32.0}; 

ولكن في حالة windowed sinc ، لقد تصرفت بشكل مختلف وكتبت مثل هذا:

 LanczosKernel[] = {0.02446, -0.13587, 0.61141, 0.61141, -0.13587, 0.02446}; 

السبب في ذلك هو حقيقة أن window window sinc يستدل عليها فعليًا من وظيفة رياضية مستمرة لا علاقة لها بالكسور الصحيحة الصحيحة. عند استخدام هذا الفلتر ، يتم استخدام أرقام الفاصلة العائمة (بأكبر قدر ممكن من الدقة) التي تتوافق مع قيم الوظيفة الصادقة. إذا كنت تسعى جاهدة لتطبيقها بدقة ، فعليك ألا تقريبها إلى كسور عادية ، لأن هذا سيضيف خطأ.

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

علاوة على ذلك ، حتى إذا قمت بتنفيذها على وحدة المعالجة المركزية (CPU) ، فإن مجموعات التعليمات الحديثة تعتمد على SIMD ، أي أنه لا يزال من الممكن إجراء عمليات عدد صحيح على وحدة المعالجة المركزية بشكل أسرع: يمكنك دمج اثنين من الأعداد الصحيحة 16 بت في مساحة تعويم 32 بت ، ومضاعفة أداء العمليات بشكل أساسي ، لذلك ، إذا أخذنا في الاعتبار العدد الدقيق للدورات لكل عملية ، فإن النقطة العائمة ليست دائمًا الخيار الأسرع.

الآن ترى سبب أهمية هذه الميزة. نظرًا لأنني كنت بحاجة إلى عمليات عدد صحيح بسيطة 16 بت فقط ، فقد بحثت عن تلك النوى التي يمكن التعبير عنها كعدد صحيح صغير على المقسومات في قوة من 2 إلى 64 وليس أكثر. هذه مجموعة محدودة أكثر من المرشحات مقارنةً إذا كنت أفكر في أي مجموعة من 6 معاملات الفاصلة العائمة.

وبالمثل ، لأسباب الكفاءة ، لم أفكر في أي عدد آخر من العينات. كان الخيار الوحيد 6 أو أقل ، لذلك لم أختبر الإصدارات التي تحتوي على 8 أو 10 عينات.

وهكذا توصلنا إلى الإجابة الأولى: "ربما لا". إذا التزمنا بهذه القيود ، فعلى الأرجح لن نجد مرشحًا أفضل يمكن تطبيقه على عدد غير محدود من المرات دون تدهور. ربما يكون لب المرشح من الجزء الأول أفضل ما يمكن العثور عليه ، على الرغم من أنني يجب أن أعترف أنه لا يمكنني إثبات ذلك بشكل شامل.

ولكن ماذا لو لم نكن بحاجة إلى الالتزام بهذه القيود؟

نسخة النقطة العائمة

إذا تخلصنا من القيود الخاصة بالإصدار الأصلي من Bink 2 (والتي أصبحت قديمة جدًا - تم إصدار الكثير من المراجعات منذ ذلك الحين) ، واستخدمنا معاملات الفاصلة العائمة التعسفية ، كيف يمكننا تحسين النتائج؟

حسنًا ، نظرًا لأننا نعلم أن نواة الأعداد الصحيحة لا تتحلل أبدًا ، ونعلم أن Lanczos أكثر حدة ، ولكنها تتحلل ، فمن المنطقي أن نجد مكانًا بين مجموعتي المعاملات التي يبدأ فيها التدهور. لذلك كتبت برنامجًا ساعدني في العثور على هذه النقطة بالذات ، وهنا ما وجدته kernel:

 MyFloatKernel6[] = {0.027617, -0.130815, 0.603198, 0.603198, -0.130815, 0.027617}; 

تتطلب هذه النواة 272 تكرارًا ، لكنها مستقرة بلا حدود وتبدو أكثر وضوحًا من مرشح عدد صحيح:


في الواقع ، لا يمكن تمييزه تقريبًا عن الأصل:


تقريبا ... ولكن ليس تماما. إذا نظرت عن كثب ، فلا يزال بإمكانك رؤية التوهين والتوهين في المناطق شديدة التباين. أسهل طريقة لرؤية ذلك هي في عين "ديناصور" برتقالي وفي مناطق مشرقة خلف الخيزران.

أي أن مرشح الفاصلة العائمة المكون من 6 عينات أفضل بالتأكيد ، لكنه ليس مثاليًا. هل يمكن تحسينه بعد؟

زيادة عرض المرشح

في البداية ، تم اختيار مرشح مع 6 عينات لنفس الأسباب مثل الكسور ذات الأعداد الصحيحة الصغيرة: كنت أبحث عن مرشح فعال للغاية. لكننا نجري الآن أبحاثًا وانتقلنا بالفعل إلى أرقام الفاصلة العائمة ، فلماذا لا تفكر في مرشح أوسع؟

عند جمع مرشح عدد صحيح من 6 عينات مع عينة Lanczos المكونة من 6 عينات ، حصلنا على مرشح جيد جدًا. لماذا لا نربطها مع Lanczos المكونة من 8 عينات؟

تبدو Lanczos المكونة من 8 عينات كالتالي:

 Lanczos8[] = {-0.01263, 0.05976, -0.16601, 0.61888, 0.61888, -0.16601, 0.05976, -0.01263}; 

مثل Lanczos المكون من 6 عينات ، إنه غير مستقر للغاية وينهار بعد 178 تكرارًا:


إذا بحثنا عن مرشح أفضل بين مرشح عدد صحيح من 6 عينات و 8 عينات من Lanczos ، فسنجد هذا الفلتر المكون من 8 عينات رائعًا:

 MyFloatKernel8[] = {-0.010547, 0.052344, -0.156641, 0.614844, 0.614844, -0.156641, 0.052344, -0.010547}; 

كمرشح مستقر بلا حدود ، فإنه يعمل بشكل جيد بشكل مثير للدهشة. يتقارب بعد 202 تكرار (التقارب أسرع من المرشحين الخاصين بي) ، وهو يشبه إلى حد كبير الأصل بحيث يصعب تحديد أي منهما هو:


هنا هو الأصل للرجوع إليها مرة أخرى:


مقارنة بمرشح عدد صحيح الأصلي ، هناك تحسن كبير.

كيف تعمل المرشحات المستقرة بلا حدود؟

كنت ذاهبا لإنهاء هذا المنصب شيء من هذا القبيل:

"لا أعرف بالضبط كيف يعمل كل شيء. في المجالات الأخرى التي عملت فيها مع التحولات القابلة للتطبيق بشكل لا نهائي ، أعرف كيف يتم إجراء الرياضيات الحدودية ويتم إنشاء تحليل مفيد. بادئ ذي بدء ، يتعلق الأمر بتحليل السطح الحدّي لأسطح التقسيمات الفرعية ، حيث يتم حساب القيم الذاتية والموجهات الذاتية لمصفوفة التقسيم الفرعي ، وبعد ذلك يمكن أخذ الحد الدقيق بدرجة لا نهائية. لكن ليس لدي أي خبرة في إجراء مثل هذا التحليل لمرشحات halfpel ، لأنها لا تترك وحدات البكسل في مكانها ، بل تقوم بتحويلها بشكل جانبي. "

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

ولكن يمكن تنفيذه بسهولة - في الواقع ، يتم تضمينه في برامج CAM كعملية تافهة من خطوة واحدة ويمكننا بالفعل أن ننظر إلى القيم الذاتية للمرشحات. إنه لا يعطينا إجابات كاملة ، لأن حقيقة التقريب (أو الاقتطاع) إلى 8 بت (أو 10 بت أو 12 بت) بعد كل تصفية أمر مهم ، لأن الاقتطاع يؤثر على طريقة تراكم الأخطاء بالمقارنة مع الجبر الدقيق بشكل لا نهائي.

لسوء الحظ ، نظرًا لأن هذا ليس مجال خبرتي على الإطلاق ، لا يمكنني حتى الحصول على نظرة عامة وثيقة على هذا التحليل. سألت فابيان وتشارلز عما إذا كان بإمكانهما كتابة منشورات تحتوي على معلومات جيدة أرسلوها إلي بالبريد (لديهما مدونات تقنية - مدونة ryg و cbloom rants ) ، وكتب فابيان سلسلة ممتازة من المقالات حول الأسس الرياضية للمرشحات المستقرة . إذا كنت مهتمًا بالهيكل النظري لما يحدث في منصبي ، فأنا أوصي بقراءة هذه السلسلة!