🚺 👲🏼 🏜️ كيف تعلمنا كيفية تقسيم الفيديو إلى مشاهد باستخدام الرياضيات الذكية 🕐 📄 ⬆️

على مدى 10 سنوات من وجود ivi ، قمنا بتجميع قاعدة بيانات تحتوي على 90.000 مقطع فيديو بأطوال وأحجام وجودة مختلفة. تظهر مئات جديدة كل أسبوع. لدينا غيغابايت من البيانات الوصفية ، وهي مفيدة للتوصيات ، وتبسيط التنقل في الخدمة وإعداد الإعلانات. لكننا بدأنا في استخراج المعلومات مباشرة من الفيديو قبل عامين فقط.

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

مما يتكون الفيديو؟

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

تسمى الصور الثابتة إطارات - تحل محل بعضها البعض وتخلق تأثير الحركة.

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

يتم تجميع اللقطات حسب المعنى ، ويطلق عليها المشاهد.يتميز المشهد بوحدة المكان والزمان والشخصيات.

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

يصعب الحصول على حدود اللقطات والمشاهد. قد تساعد المصادر من برامج التثبيت ، لكنها غير متاحة لنا.

لحسن الحظ ، يمكن للخوارزميات أن تفعل ذلك ، وإن لم يكن بشكل دقيق. سأخبرك عن خوارزمية التقسيم إلى مشاهد.

لماذا نحتاج هذا؟

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

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

نظام التوصية مفيد أيضًا للانقسام في المشاهد. ومنهم ، يتم الحصول على علامات تصف الأفلام التي يحبها المستخدمون في الهيكل.

ما هي طرق حل المشكلة؟

يتم حل المشكلة من جانبين:

يأخذون الفيديو كله ويبحثون عن حدود المشاهد.
أولاً ، يقسمون الفيديو إلى لقطات ، ثم يجمعونها في مشاهد.

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

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

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

في عام 2016 ، اقترح دانييل روثمان وزملاؤه IBM خوارزمية تأخذ في الاعتبار بنية الوقت وصياغة الجمع بين اللقطات في المشاهد كمهمة تجميع متسلسل مثالية:

نظرا لتسلسل $N$ طلقات
بحاجة لتقسيمها إلى $K$ شرائح بحيث يكون هذا الفصل هو الأمثل.

ما هو الفصل الأمثل؟

حتى الآن ، نفترض ذلك

K

$K$ بالنظر إلى أن عدد المشاهد معروف. فقط حدودهم غير معروفة.

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

الخطوات التحضيرية هي كما يلي:

نقوم بتحويل اللقطات إلى متجهات (رسم بياني أو مخرجات للطبقة قبل الأخيرة من الشبكة العصبية)
أوجد المسافات الزوجية بين المتجهات (الإقليدية ، جيب التمام ، أو غيرها)
نحصل على مصفوفة مربعة $D$ حيث أن كل عنصر هو المسافة بين اللقطات $i$ و $j$ .

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

يتم تتبع المربعات الداكنة على طول القطر - وهي المناطق التي تتشابه فيها اللقطات المجاورة مع بعضها البعض ، وبالتالي تكون المسافة أقل.

إذا اخترنا التضمينات الجيدة التي تعكس دلالات اللقطات واخترت وظيفة مسافة جيدة ، فإن هذه المربعات هي المشاهد. ابحث عن حدود المربعات - سنجد حدود المشاهد.

بالنظر إلى المصفوفة ، صاغ الزملاء الإسرائيليون ثلاثة معايير للتقسيم الأمثل:

\begin{matrix} (1) & H_{a d d} (\bar{t}) = \sum_{д л я к а ж д о г о к в а д р а т а} [с у м м а р а с с т о я н и й в н у т р и к в а д р а т а] \end{matrix}

$H_{add}(\overline{t})=\sum\limits_{\:\:}[\:\:\:]\tag{1}$

\begin{matrix} (2) & H_{a v g} (\bar{t}) = \sum_{д л я к а ж д о г о к в а д р а т а} [с р е д н е е р а с с т о я н и е в н у т р и к в а д р а т а] \end{matrix}

$H_{avg}(\overline{t})=\sum\limits_{\:\:}[\:\:\:]\tag{2}$

\begin{matrix} (3) & H_{n r m} (\bar{t}) = \frac{\sum_{д л я к а ж д о г о к в а д р а т а} [с у м м а р а с с т о я н и й в н у т р и к в а д р а т а]}{\sum_{д л я к а ж д о г о к в а д р а т а} [п л о щ а д ь к в а д р а т а]} \end{matrix}

$H_{nrm}(\overline{t})=\dfrac{\sum\limits_{\:\:}[\:\:\:]}{\sum\limits_{\:\:}[\:]}\tag{3}$

\bar{t}

$\overline{t}$ هو ناقل الحدود المشهد.

أي من معايير التقسيم الأمثل للاختيار؟

وظيفة خسارة جيدة لمهمة التجميع التسلسلي الأمثل لها خاصيتان:

إذا كان الفيلم يتكون من مشهد واحد ، فعندما نحاول تقسيمه إلى قسمين ، ستكون قيمة الوظيفة هي نفسها دائمًا.
إذا تم تقسيمها بشكل صحيح إلى مشاهد ، فستكون القيمة أقل مما لو لم تكن صحيحة.

اتضح

H_{a d d}

$H_{add}$ و

H_{a v g}

$H_{avg}$ لا تتأقلم مع هذه المتطلبات ولكن

H_{n r m}

$H_{nrm}$ التأقلم. لتوضيح هذا ، سنجري تجربتين.

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

H_{a d d}

$H_{add}$ يقول أنه في منتصف الفيديو يوجد تغيير في المشاهد ، وهذا غير صحيح في الواقع. في

H_{a v g}

$H_{avg}$ قفزات غير طبيعية إذا تم وضع القسم في بداية الفيديو أو نهايته. فقط

H_{n r m}

$H_{nrm}$ يتصرف على النحو المطلوب.

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

للكشف عن هذا اللصق ، يجب أن تأخذ الوظيفة قيمة دنيا عند

t = 70

$t=70$ . لكن الحد الأدنى

H_{a d d}

$H_{add}$ لا يزال أقرب إلى منتصف الجزء بينما

H_{a v g}

$H_{avg}$ - إلى البداية. في

H_{n r m}

$H_{nrm}$ الحد الأدنى الواضح مرئي في

t = 70

$t=70$ .

تظهر الاختبارات أيضًا أنه يتم تحقيق التقسيم الأكثر دقة باستخدام

H_{n r m}

$H_{nrm}$ . يبدو أنك بحاجة إلى تناوله ، وسيكون كل شيء على ما يرام. ولكن دعونا أولاً ننظر إلى مدى تعقيد خوارزمية التحسين.

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

[2.. K]

$[2..K]$ جميع تركيبات الأقسام من اللقطات 0 إلى Nth واختيار الأفضل. هنا

K

$K$ - عدد المشاهد و

N

$N$ - عدد اللقطات.

لا التحسينات والتسريع

H_{a d d}

$H_{add}$ ستعمل في الوقت المناسب

O (N K)

$O(NK)$ . في

H_{n r m}

$H_{nrm}$ هناك معلمة أخرى للتعداد - منطقة القسم ، وفي كل خطوة ، من الضروري التحقق من جميع قيمه. وفقا لذلك ، يزيد الوقت إلى

O (N K N^{2})

$O(NKN^2)$ .

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

كيف تقدر عدد المشاهد؟

اقترحت مجموعة من شركة IBM أنه نظرًا لأن العديد من صفوف المصفوفة تعتمد خطيًا ، فإن عدد العناقيد المربعة على طول القطر سيكون تقريبًا مساوٍ لرتبة المصفوفة.

للحصول عليها وفي نفس الوقت تصفية الضوضاء ، تحتاج إلى تحليل مفرد للمصفوفة

D

$D$ .

من بين القيم المفردة ، مرتبة ترتيبًا تنازليًا ، نجد نقطة المرفق - النقطة التي يتباطأ فيها انخفاض القيم بشكل حاد. مؤشر نقطة المرفق هو العدد التقريبي للمشاهد في الفيلم.

بالنسبة للتقريب الأول ، هذا يكفي ، ولكن يمكنك استكمال الخوارزمية بالاستدلال لأنواع مختلفة من السينما. في أفلام الحركة ، هناك المزيد من المشاهد ، وفي المنزل - أقل.

الاختبارات

أردنا أن نفهم شيئين:

هل فرق السرعة مثير للغاية؟
ما مقدار الدقة التي يعانيها عند استخدام خوارزمية أسرع؟

تم تقسيم الاختبارات إلى مجموعتين: البيانات الاصطناعية والحقيقية. في الاختبارات التركيبية ، تمت مقارنة جودة وسرعة الخوارزميتين ، وفي الاختبارات الحقيقية ، قاما بقياس جودة أسرع خوارزمية. تم إجراء اختبارات السرعة على MacBook Pro 2017 ، 2.3 جيجاهرتز Intel Core i5 ، 16 جيجابايت 2133 ميجاهرتز LPDDR3.

اختبارات الجودة الاصطناعية

لقد أنشأنا 999 مصفوفة لمسافات زوجية تتراوح في الحجم من 12 إلى 122 لقطة ، وقسمناها عشوائيًا إلى مشاهد 2-10 وأضفنا ضوضاء عادية من الأعلى.

لكل مصفوفة ، تم العثور على الأقسام المثلى من حيث

H_{a d d}

$H_{add}$ و

H_{n r m}

$H_{nrm}$ ، ومن ثم حساب مقاييس الدقة والاستدعاء و F1 و IoU.

نعتبر الدقة والاستدعاء للفترة الزمنية باستخدام الصيغ التالية:

\begin{matrix} (4) & P r e c i s i o n_{i n t e r v a l} = \frac{д л и н а п е р е с е ч е н и я и с т и н н о г о и п р е д с к а з а н н о г о о т р е з к о в}{д л и н а п р е д с к а з а н н о г о о т р е з к а} \end{matrix}

$Precision_{interval}=\dfrac{\:\:\:\:\:}{\:\:}\tag{4}$

\begin{matrix} (5) & R e c a l l_{i n t e r v a l} = \frac{д л и н а п е р е с е ч е н и я и с т и н н о г о и п р е д с к а з а н н о г о о т р е з к о в}{д л и н а и с т и н н о г о о т р е з к а} \end{matrix}

$Recall_{interval}=\dfrac{\:\:\:\:\:}{\:\:}\tag{5}$

نعتبر F1 كالمعتاد ، واستبدال الدقة الفاصلة واستدعاء:

\begin{matrix} (6) & F 1_{i n t e r v a l} = 2 \frac{P r e c i s i o n_{i n t e r v a l} R e c a l l_{i n t e r v a l}}{P r e c i s i o n_{i n t e r v a l} + R e c a l l_{i n t e r v a l}} \end{matrix}

$F1_{interval}=2\dfrac{Precision_{interval}Recall_{interval}}{Precision_{interval}+Recall_{interval}}\tag{6}$

لمقارنة المقاطع المتوقعة والحقيقية داخل الفيلم ، لكل مقطع متوقع ، نجد المقطع الحقيقي الذي يحتوي على أكبر تقاطع ونأخذ في الاعتبار المقياس لهذا الزوج.

فيما يلي النتائج:

تحسين الوظيفة

H_{n r m}

$H_{nrm}$ فاز بجميع المقاييس ، كما هو الحال في اختبارات مؤلفي الخوارزمية.

اختبارات السرعة الاصطناعية

لاختبار السرعة ، أجرينا اختبارات اصطناعية أخرى. الأول هو كيف يعتمد وقت تشغيل الخوارزمية على عدد اللقطات

N

$N$ مع عدد ثابت من المشاهد:

أكد الاختبار تقييمًا نظريًا

O (N K N^{2})

$O(NKN^2)$ : وقت التحسين

H_{n r m}

$H_{nrm}$ ينمو كثير الحدود مع النمو

N

$N$ مقارنة بالوقت الخطي

O (N K)

$O(NK)$ في

H_{a d d}

$H_{add}$ .

إذا قمت بإصلاح عدد اللقطات

N

$N$ وزيادة عدد المشاهد تدريجيًا

K

$K$ ، نحصل على صورة أكثر إثارة للاهتمام. في البداية ، من المتوقع أن ينمو الوقت ، ولكن بعد ذلك يبدأ في الهبوط. الحقيقة هي أن عدد قيم المقام المحتملة (الصيغة

3

$3$ ) أننا بحاجة إلى التحقق بما يتناسب مع عدد الطرق التي يمكننا كسرها

N

$N$ شرائح يوم

K

$K$ . يتم حسابها باستخدام مجموعة

N

$N$ بواسطة

K

$K$ :

\begin{matrix} (7) & C_{N}^{K} = \frac{N!}{K! (N - K)!} \end{matrix}

$C_N^K=\dfrac{N!}{K!(N-K)!}\tag{7}$

مع النمو

K

$K$ ينمو عدد المجموعات أولاً ، ثم ينخفض مع اقترابك

N

$N$ .

يبدو هذا رائعًا ، ولكن عدد المشاهد نادرًا ما يكون مساوياً لعدد اللقطات ، وسيستمر دائمًا في الحصول على هذه القيمة التي توجد بها العديد من المجموعات. في "آفينجرز" المذكورة 2700 طلقة و 105 مشاهد. عدد المجموعات:

C_{2700}^{105} = \frac{2700!}{105! (2700 - 105)!} = 2.3410751551031162 e + 191

$C_{2700}^{105}=\dfrac{2700!}{105!(2700-105)!}=2.3410751551031162e+191$

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

H_{n r m}

$H_{nrm}$ بطيئة جدًا في التحسين وغير مناسبة لمقاطع الفيديو التي تزيد مدتها عن 10 دقائق

H_{a d d}

$H_{add}$ في الممارسة يعطي نتائج مقبولة.

اختبارات البيانات الحقيقية

لذا ، اخترنا مقياسًا

H_{a d d}

$H_{add}$ ، والتي ، على الرغم من أنها أقل دقة ، تعمل بشكل أسرع. نحتاج الآن إلى مقاييس ، سنبني منها على البحث عن خوارزمية أفضل.

قمنا باختبار 20 فيلماً من مختلف الأنواع والأعوام للاختبار. تم الترميز على خمس مراحل:

:
- , .
, .
. « ?»
CV. — , .
, « ».

هذه هي الطريقة التي تبدو بها الشاشة الخربشة وشاشة المفتش:

وهذه هي الطريقة التي تنقسم فيها أول 300 لقطة من فيلم "Avengers: Infinity War" إلى مشاهد. على اليسار توجد المشاهد الحقيقية ، وعلى اليمين المشاهد التي تنبأت بها الخوارزمية:

للحصول على مصفوفة المسافة الزوجية ، قمنا بما يلي:

قسمنا الفيلم إلى 2700 لقطة
تم أخذ طلقة واحدة من كل طلقة.
قمنا بتخطي الإطارات من خلال الشبكة العصبية Xception المدربة على مجموعة بيانات Imagenet وأخذنا قيم الإخراج من الطبقة قبل الأخيرة
ل مسافات زوجيا الإقليدية حسبت بين ناقلات النار

لكل فيديو من مجموعة البيانات ، أنشأنا مصفوفات لمسافات زوجية ، وكما هو الحال بالنسبة للبيانات الاصطناعية ، قمنا بحساب أربعة مقاييس. فيما يلي الأرقام التي خرجت:

الدقة : 0.4861919030708739
أذكر : 0.8225937459424839
F1 : 0.513676858711775
IoU : 0.37560909807842874

وماذا في ذلك؟

لقد حصلنا على خط أساسي لا يعمل بشكل مثالي ، ولكن الآن يمكنك البناء عليه بينما نبحث عن طرق أكثر دقة.

بعض الخطط الإضافية:

جرب بنى CNN الأخرى لاستخراج الميزات.
جرب مقاييس المسافة الأخرى بين اللقطات.
جرب طرق التحسين الأخرى $H_{nrm}$ ، على سبيل المثال ، الخوارزميات الجينية.
في محاولة لتقليل انهيار الفيلم كله إلى أجزاء منفصلة التي $H_{nrm}$ يحقق في وقت معقول ، ومقارنة ما سيكون خسارة في الجودة.

تم نشر كود كل من الطرق والتجارب على البيانات الاصطناعية على Github . يمكنك لمس ومحاولة تسريع نفسك. طلبات الإعجاب والسحب مرحب بها.

وداعا للجميع ، نراكم في المقالات القادمة!

كيف تعلمنا كيفية تقسيم الفيديو إلى مشاهد باستخدام الرياضيات الذكية