Cilpveida GIFi internetā ir plaši izplatīti, tiem ir veltītas neskaitāmas lapas un blogi, un bieži ar tiem var sastapties vietnēs, kur cilvēki dalās ar attēliem. Tomēr šādu GIFu veidošana prasa krietnu piepūli. Video klips, kurā gribi atrast šādu ciklisku fragmentu ir uzmanīgi un pacietīgi jāskata cauri un jāmēģina uzķert vietas, kas šķiet, ka varētu labi izskatīties, ja tās laistu uz riņķi. Foršāk būtu šādu piņķerīgu nodarbi uzticēt datoram.

Kā pateikt, vai video segments ir cilpveida?

Par cilpveida video segmentu sauksim tādu segmentu, kam pirmais un pēdējais kadrs ir ļoti līdzīgs. Katru video kadru var aprakstīt ar N veseliem skaitļiem. Piemēram, , kur pirmie trīs skaitļi nosaka pirmā pikseļa krāsu (sarkanās, zaļās un zilās krāsas vērtības), nākamie trīs skaitļi nosaka nākamā pikseļa krāsu u.t.t.

Diviem kadriem var definēt attālumu:

Uzskatīsim kadrus par ļoti līdzīgiem, ja attālums starp tiem ir mazāks par kādu pašu noteiktu slieksni T. var iedomāties kā vektorus N dimensionālā telpā un kā šo vektoru starpības moduli.

 

Cilpveida video segmentu atrašana

Mēs gribam atrast cilpveida segmentu, kas ilgst 3 sekundes vai mazāk. Vienkāršs veids, kā to dabūt gatavu ir vienkārši katru video kadru salīdzināt ar visiem kadriem iepriekšējās trīs sekundēs. Kad atrasti divi kadri, kas ir ļoti līdzīgi (t.i. tādi, starp kuriem attālums ir mazāks par mūsu definēto slieksni T), mēs piefiksējam to laikus.

Vienīgā problēma ir tāda, ka šī metode aizņemtu ļoti daudz laika. Būtu jāsalīdzina milzīgs daudzums kadru (25 kadri sekundē · 1 stundu 20 minūšu gara filma = 120000 kadri), kur katrā kadrā jāsalīdzina daudzie pikseļi. Tas aizņemtu stundas. Par laimi ir daži paņēmieni, kas paātrinātu skaitļošanu.

1. Samazinām video izmērus. HD video kadri var sastāvēt no miljoniem pikseļu un attāluma noteikšana prasītu miljoniem operāciju. Reducējot šādu milzīgu briesmoni uz 150 pikseļiem platumā, joprojām tiek saglabāta pietiekama precizitāte mūsu mērķiem, taču tagad attālums starp kadriem būs aprēķināms krietni ātrāk.

2. Izmantojam trijstūru nevienādības. Šis ir ļoti efektīvs paņēmiens, jo ļauj izsecināt, vai divi kadri ir ļoti līdzīgi, neaprēķinot attālumu starp tiem. Tā kā ir attālums starp diviem punktiem, tad trim šādiem attālumiem izpildās šādas nevienādības:

 

Pirmā nevienādība mums pasaka, ka, ja A ir ļoti tuvu B, un B ir ļoti tuvu C, tad A arī ir tuvu C. Otrā nevienādība pasaka, ka, ja A ir ļoti tuvu B, un B ir tālu no C, tad A arī ir tālu no C. Izmantojot nevienādības attālumam starp kadriem, iegūst:

 

Izmantojot šīs nevienādības, mēs varam iegūt informāciju, kādās robežās ir attālumi starp kadriem. Šī informācija tiks atjaunota katru reizi, kad kāds attālums starp diviem kadriem tiks aprēķināts. Piemēram, pēc attāluma izskaitļošanas, attāluma augšējā robeža un apakšējā robeža ir novērtējamas:

 

Ja mēs secinām, ka , tad var teikt, ka un ir ļoti līdzīgi kadri. Un, ja secinām, ka , tad var teikt, ka un ir atšķirīgi kadri. Ja ar šīs metodes palīdzību mēs nevaram pateikt, vai un ir ļoti līdzīgi vai nē, mums galu galā būs jāaprēķina , taču tad, zinot vērtību, varam atjaunot informāciju par pārējo attālumu augšējām un apakšējām robežām u.t.t.

Ilustrācijai pieņemam, ka kādam video ir kadri šādā secībā:

Kad algoritms sasniedz kadru , tas vispirms izrēķina attālumu starp to un kadru un izsecina, ka tie ir atšķirīgi. Šajā brīdī algoritms jau ir noskaidrojis, ka ir samērā līdzīgs un , tātad tas izsecina, ka ne , ne nesakrīt ar . Praksē šī metode ļauj izvairīties no 80% līdz 90% attāluma aprēķinu starp kadriem.

3. Izmantojam efektīvāku attāluma aprēķināšanas formulu. Izmantojot attāluma aprēķināšanas formulu, kas dota augstāk, mums ir nepieciešamas aptuveni 3N darbības (N atņemšanas, N reizināšanas un N-1 saskaitīšana). Izdevīgāk ir attālumu starp kadriem rēķināt, izmantojot kosinusu teorēmu :

kur lietoti šādi apzīmējumi:

 

Šādi izsakot attālumu starp kadriem, mums katra kadra norma ir jāaprēķina tikai vienreiz, un tālāk katram kadru pārim attālumu var aprēķināt, vienkārši izrēķinot , kas prasa tikai 2N darbības un tātad ir par trešdaļu ātrāk nekā iepriekš.

Vēl viena priekšrocība normu rēķināšanai ir, ka katriem diviem kadriem ir spēkā:

kas jau dod sākuma vērtības augšējai un apakšējai robežai attālumam starp kadriem, kuras var izmantot 2. paņēmienā.

Skaitļošanas laiks var atšķirties atkarībā no izmantotā video kvalitātes. Tipiska garuma filmu var apstrādāt apmēram 20 minūtēs - krietni ātrāk nekā tas būtu, ja pats skatītos filmu un mēģinātu izlasīt cilpveida segmentus.

Interesantāko segmentu izvēle

Augstāk aprakstītais algoritms atrod visus ļoti līdzīgos kadrus tai skaitā secīgus kadrus (kas bieži ir līdzīgi) un kadrus no ainām, kur nekas nekustās (parasti melns ekrāns). Galu galā mums ir simts tūkstoši video segmentu, no kuriem interesanti ir tikai daži. Ir nepieciešams izsijāt neinteresantos segmentus pirms GIFa veidošanas. Šī sijāšana prasa vien pāris sekundes un tās rezultāts ir atkarīgs no kritērijiem, kas tiek izmantoti. Daži piemēri:

• Starp pirmo un pēdējo kadru jābūt vismaz 0,5 sekundēm.
• Kadru sekvencē jābūt vismaz vienam kadram, kas atšķiras no pārējiem.
• Pirmajam kadram ir jāsākas ne ātrāk kā 0,5 sekundes pēc iepriekšējā cilpveida segmenta sākuma. Tas novērš dublēšanos (segmentus, kas sākās un beidzās gandrīz tai pašā laikā).

Šajos kritērijos nevajadzētu būt pārāk stingram, lai netīšām neizsijātu labus segmentus. Galā sagaidāmi ap 200 GIFi, liela daļa no kuriem ir tikai nedaudz interesanti (acu mirkšķināšana u.tml.). Pēdējais solis ir manuāla GIFu pārskatīšana, kas varētu izskatīties apmēram šādi:

Šāds algoritms tomēr nav perfekts. Tas ne pārāk labi darbojas ar vāji apgaismotiem klipiem, dažreiz tas izlaidīs segmentus, kur kamera vai arī kāds objekts fonā nedaudz izkustās. Šādus segmentus cilvēks varētu samērā viegli noteikt, kamēr datoram tas sagādā grūtības. Varbūt tev ir idejas, kā šo algoritmu uzlabot?

Avots: Zulko, kurš arī ir izstrādājis Python bibliotēku, kurā ir iekļauts augstākminētais algoritms.