Get best of the week

متى تتوقف عملية التعرف على تسلسل الفيديو؟

مرحباً هبر! نود اليوم أن نخبرك عن مهمة مثيرة للاهتمام للغاية كنا نتعامل معها منذ بداية بحثنا حول التعرف على المستندات في دفق الفيديو - مشكلة العثور على وقت التوقف الأمثل.



تين. 1. صور الحقول النصية لوثائق الهوية على إطارات تسلسل الفيديو.

كما يعلم الكثير من الناس ، فإن المنتج الرئيسي لـ Smart Engines هو نظام التعرف على وثائق الهوية ، Smart IDReader ، ينطبق على كل من الخوادم وأجهزة الكمبيوتر المكتبية ، وعلى الأجهزة المحمولة. في عدد كبير من الحالات ، يجب أن يتم التعرف على المستندات على الهاتف المحمول في وضع عدم الاتصال ، وغالبًا لا يمكننا التحكم في ظروف التصوير ونوعيته ، وتكلفة أخطاء التعرف ، خاصة عند التعرف على وثائق الهوية ، مرتفعة جدًا. في الوقت نفسه ، لدينا ميزة مهمة - لا يمكننا استخدام صورة واحدة ، ولكن سلسلة من الإطارات الملتقطة (انظر الشكل 1) ، لزيادة دقة التعرف.

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

السؤال الثاني الذي يطرح بشكل مستقل عن الأول هو متى تتوقف عملية المراقبة؟ وبعبارة أخرى ، ما المعيار الذي تقرر أنه يمكن إيقاف عملية الالتقاط وأن النتيجة المتراكمة في اللحظة الحالية تعتبر نهائية؟ كيف يمكن مقارنة هذه المعايير ببعضها البعض وهل هناك معيار أمثل؟

يتعلق الأمر بمشكلة إيجاد لحظة إيقاف عملية المراقبة التي سيتم مناقشتها في هذه المقالة.

ما نريد تحقيقه


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


تين. 2. لمحات عن كفاءة التعرف على سطر النص في تسلسل فيديو (الأقل هو الأفضل). الخط الأسود المنقط هو جودة إطار بإطار ، والخط الأسود الصلب هو نتيجة الجمع بين الإطارات. الخط البرتقالي هو ما نريده من قاعدة التوقف "الجيدة".

في التين. يوضح الشكل 2 ملامح الكفاءة للتعرف على سلسلة نصية - اعتماد متوسط ​​الخطأ (من حيث مسافة Levenshtein إلى الإجابة الصحيحة) على عدد الإطارات المعالجة. تم الحصول على الرسوم البيانية السوداء باستخدام Tesseract v4.0.0 في الحقول النصية لمجموعة بيانات MIDV-500 . يمكن ملاحظة أن استخدام الإطار البيني للجمع بين نتائج التعرف يسمح للمرء بتحقيق قيمة خطأ أقل بكثير (والتي ، بشكل عام ، ليست مفاجئة).

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

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

ماذا تقول النظرية


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

نشير إلى خطأ النتيجة المجمعة في نالخطوة ith من العملية كـ \ إبسيلون (R_n). نفترض أنه إذا توقفنا عند نالخطوة ith ، فسوف نتحمل خسارة النموذج التالي :، L_n = \ epsilon (R_n) + c \ cdot nأينج- بعض التكلفة النسبية المحددة سلفاً لكل ملاحظة. يمكن صياغة مهمة العثور على وقت التوقف الأمثل كبحث عن متغير عشوائي ن- وقت التوقف ، الذي يعتمد توزيعه على ملاحظات الإدخال (في بعض الأدبيات نتسمى القيمة لحظة ماركوف ) ، والتي يتم عندها تقليل الخسارة المتوقعة \ mathrm {E} (L_N).

مشاكل رتيبة


في ظل ظروف معينة ، في مثل هذه المشاكل ، يمكن التعبير عن قاعدة التوقف المثلى بشكل صريح. ومن الأمثلة على ذلك ما يسمى مشكلة رتيبة. المعيار لالرتابه في الصوت من المشكلة هو هذا: إذا كان في بعض خطوة على نخسارة L_nلا تتجاوز الخسارة المتوقعة في الخطوة التالية، ثم وهذا سوف يتم تنفيذها في جميع الخطوات اللاحقة. وبعبارة أخرى ، مما حدث حدث L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {وردت} ~ n ~ \ text {إطارات})بعد ذلك الحدث سيحدث L_ {n + 1} \ le \ mathrm {E} (L_ {n + 2} | \ text {وردت} ~ n + 1 ~ \ text {إطارات}). بالنسبة للمشكلات الرتيبة ، فإن ما يسمى بقاعدة التوقف "قصيرة النظر" هي الأمثل: توقف عند الخطوة الأولى حيث يتم الوفاء بالشرط L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {وردت} ~ n ~ \ text {إطارات}).

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

\ epsilon (R_n) - \ mathrm {E} (\ epsilon (R_ {n + 1}) | \ text {استلام} ~ n ~ \ text {إطارات}) \ le c.

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

كيف يمكن استخدام قاعدة قصر النظر؟


لنفترض أن الدالة \ إبسيلون (R_n)هي المسافة \ rho (R_n، R ^ *)من نتيجة التعرف المجمعة R_nإلى "الإجابة الصحيحة" R ^ *، ومثل أي مسافة تحترم نفسها ، فإن عدم المساواة في المثلث يحمل. إن مسافة Levenshtein المذكورة أعلاه ترضي عدم المساواة في المثلث ، بالإضافة إلى وظيفة بسيطة في شكل "صواب / خطأ" (إذا افترضنا أنه \ rho (R_n، R ^ *)للإجابة الصحيحة هي صفر وللإجابة الخاطئة فهي ثابتة). وفقًا لعدم المساواة في المثلث ، لا يتجاوز الجانب الأيسر من معيار التوقف لدينا \ mathrm {E} (\ rho (R_n، R_ {n + 1}) | \ text {وردت} ~ n ~ \ text {إطارات})- المسافة المتوقعة من النتيجة المجمعة الحالية إلى النتيجة التالية.

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

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

هناك عدة طرق لتقييم المسافة المتوقعة من النتيجة المجمعة الحالية إلى النتيجة التالية. على سبيل المثال ، إذا تم استخدام مسافة Levenshtein كمقياس على النتائج ، فإن مجرد المسافة بين النتيجتين الأخيرتين للتخطيط هي تقريب جيد. نهج آخر محتمل هو محاكاة الملاحظة التالية المحتملة (على سبيل المثال ، بناءً على تلك التي تم الحصول عليها بالفعل) ، وإجراء مجموعات "خاملة" وحساب متوسط ​​المسافة إلى التنبؤات التي تم الحصول عليها.


تين. 3. مقارنة ملامح الأداء للعديد من قواعد التوقف.

في التين. يعرض 3 ملفات تعريف الأداء للعديد من قواعد التوقف. N_K- نفس القاعدة "المذكورة أعلاه" "التافهة" - مع حد أقصى لعدد المشاهدات المجهزة. N_ {CX}وN_ {CR}- فواصل عتبات للحد الأقصى لحجم الكتلة لنفس النتائج من الرتل بالإطار N_ {CX}( N_ {CR}) والنتائج المجمعة ( ). ن- القاعدة الموضحة في هذه الورقة ، مع تقدير للمسافة المتوقعة إلى النتيجة التالية باستخدام مجموعات النمذجة و "الخمول".

بدلا من الاستنتاج


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

-

تم إعداد المنشور على أساس المقالة حول استراتيجيات التوقف الأمثل للتعرف على النص في دفق فيديو ، K. Bulatov ، N. Razumnyi ، VV Arlazarov ، IJDAR 22 ، 303-314 (2019) 10.1007 / s10032-019-00333-0 .

إذا كان القارئ مهتمًا بنظرية وقت التوقف الأمثل ، على وجه الخصوص ، دليل على المثالية للقاعدة قصر النظر لمشاكل الرتابة ، فنحن نوصي بشدة بالدورة المنشورة التوقف الأمثل والتطبيقات المثلى (Thomas Ferguson، UCLA).

بعض المصادر الأخرى المثيرة للاهتمام حول هذا الموضوع:
Chow YS ، Siegmund D. توقعات كبيرة: نظرية التوقف الأمثل ، Houghton Mifflin ، 1971 ، 139 p.
Berezovsky B.A. ، Gnedin A.V. مشكلة الاختيار الأفضل ، العلوم ، 1984 ، 200 ص.
Ferguson TS ، Hardwick TS قواعد التوقف عن التدقيق ، مجلة الاحتمال التطبيقي. ، V. 26 ، N. 2 ، 1989 ، p. 303-313.
Ferguson TSالإحصائيات الرياضية: منهج القرار النظري . الصحافة الأكاديمية ، 1967 ، 396 ص.

More articles:


All Articles