Jest to ogromny problem, więc zdecydowałem się napisać dość długą odpowiedź, aby spróbować rozłożyć problem na części, które mogą być łatwiejsze do rozwiązania.
Ważne jest, aby porównania były wykonywane przy użyciu dostępnych zasobów obliczeniowych i czasu: Wątpię, aby rozwiązanie, którego realizacja potrwa miesiące, będzie bardzo przydatne w dynamicznej bazie danych wideo. Rozmiar bazy danych prawdopodobnie uniemożliwia wykorzystanie zasobów chmury obliczeniowej. Tak więc bardzo zależy nam na kosztach lokalnych każdego porównania w kilku różnych domenach: 1) przechowywanie danych, 2) obliczanie zasobów i 3) czas.
Jednym z kluczowych kosztów, które należy rozważyć, jest wyodrębnienie danych potrzebnych z każdego filmu wideo w celu wykorzystania danych porównawczych. Gdy dostępne dane są dostępne, należy wziąć pod uwagę koszt wykonania porównania. Na koniec należy przeprowadzić porównania, aby dopasować wszystkie filmy do siebie.
Koszt pierwszych dwóch kroków to O (1) na liczbę filmów. Koszt ostatniego kroku musi być gorszy niż O (1), potencjalnie znacznie gorszy. Dlatego naszym głównym celem powinno być minimalizowanie kosztów ostatniego kroku, nawet jeśli oznacza to dodanie wielu wczesnych, prostych kroków.
Optymalne algorytmy dla tego procesu będą w dużym stopniu zależeć od charakterystyki bazy danych, poziomu, na którym istnieją pojedyncze i wielokrotne dopasowania. Jeśli 100% filmów pasuje do innych filmów, będziemy chcieli zminimalizować koszty udanego meczu. Jednak bardziej prawdopodobne jest, że mecze będą rzadkie, więc będziemy chcieli zminimalizować koszt nieudanego meczu. To znaczy, jeśli istnieje szybki i brudny sposób na powiedzenie "te dwa filmy wideo nie mogą być zgodne", to powinniśmy go najpierw użyć, zanim jeszcze zaczniemy potwierdzać dopasowanie.
Scharakteryzować bazę danych najpierw wykonaj próbkowanie i dopasowywanie ręczne, aby oszacować stopień dopasowania w bazie danych. Ten eksperyment powinien pokazać, w jaki sposób zbędne filmy są "zbite": jeśli dane wideo pasowało, jak prawdopodobnie było więcej niż jeden mecz ? Jaki odsetek wszystkich dopasowań był również częścią dopasowania wielokrotnego? Ten proces da "model" bazy danych (rozkład statystyczny), który zostanie użyty do pomocy w doborze algorytmu i dostrojeniu systemu. założy, że mecze są stosunkowo rzadkie, w końcu, jeśli jest wiele meczów, vide OS będzie "zbijać", skutecznie zmniejszając bazę danych, a przez to upraszczając problem. Załóżmy, że problem pozostaje tak trudny, jak to możliwe.
Proponuję wielopoziomowe podejście do kategoryzacji, w którym będziemy budować sekwencję algorytmów, które wielokrotnie wykonują binarną decyzję "te dwa filmy nie pasują"/"te dwa filmy mogą pasować". Tylko ostatni algorytm w łańcuchu musi wygenerować odpowiedź "Te dwa filmy pasują do siebie".
Algorytmy klasyfikacji/dopasowywania mogą się nie udać na jeden lub oba z dwóch sposobów: Fałszywy pozytyw (niepasujące filmy są błędnie interpretowane jako pasujące) i Fałszywy negatyw (dopasowane filmy są błędnie oznaczone jako niezgodne). Każda z tych błędnych decyzji ma zakres prawdopodobieństw z nią związanych i chcemy zminimalizować obie te kwestie.
Ponieważ budujemy algorytm, chcemy algorytmy, które są bardzo dobre w identyfikowaniu niezgodności bez błędów, co oznacza, że muszą mieć bardzo niską wartość Fałszywego Odrzucenia, a my nie dbają o współczynnik Fałszywe Akceptowanie . Na przykład klon filmu wideo Wierd Al może wyglądać i brzmi bardzo podobnie do oryginału, a może nie być w stanie pokazać, że nie jest zgodny z oryginałem, aż do późniejszego etapu algorytmu.
Najpierw należy uruchomić najprostszy, najszybszy, najbardziej niezawodny algorytm, ponieważ przeważająca większość testów przyniesie wynik "nie pasować". Najprostszym sprawdzeniem będzie wyszukanie identycznych plików w bazie danych, wykonanych przez wiele szybkich i prostych narzędzi do obsługi systemów plików i baz danych. Po uruchomieniu tego skanowania możemy założyć, że będziemy musieli otworzyć i przeczytać pliki wideo, aby wykryć różnice.
Ponieważ porównywanie wideo jest stosunkowo trudne, zacznijmy od dźwięku. Pomyśl o bazie danych jako o pierwszej kolekcji MP3, która może zawierać duplikaty. W końcu, jeśli otrzymamy dobre dopasowanie dźwięku, najprawdopodobniej będziemy mieli mecz wideo i na odwrót. Możemy śmiało powiedzieć, że audio jest "uczciwym" reprezentantem filmu.Na szczęście szybkie wyszukiwanie w Internecie przyniesie wiele odcisków palców i pakietów porównawczych, które są niezawodne, szybkie i dojrzałe. Odciski palców audio muszą być generowane dla każdego wideo w bazie danych. Filmy pozbawione ścieżki dźwiękowej automatycznie znajdą się w zestawie "można dopasować".
Ale jest tu "gotcha": co z lekturami głosowymi? Jeśli dany film jest zakodowany dwa razy, z lub bez głosu, czy pasuje czy nie? A co z francuskim audio vs hiszpańskim lub angielskim? Jeśli wszystkie powinny być uważane za pasujące, może być konieczne pominięcie testów dźwiękowych.
W tym momencie wiemy, że wszystkie wpisy w systemie plików są "wystarczająco różne" i wiemy, że ścieżki audio są "wystarczająco różne" (jeśli testowane), co oznacza, że nie możemy odkładać oglądania danych wideo dłużej. Na szczęście powinno to być zrobione tylko dla niewielkiej części bazy danych wideo, więc możemy znieść pewne koszty. Tak jak poprzednio, nadal będziemy chcieli najpierw szybko wyeliminować więcej niezgodnych z nami elementów, zanim spróbujemy pozytywnie oznaczyć dopasowanie.
Ponieważ musimy wziąć pod uwagę zmiany rozdzielczości (np. Z 1080p na iPoda), będziemy potrzebować sposobu, aby scharakteryzować informacje wideo, które nie są niezależne od rozdzielczości, ale także tolerują hałas dodany i/lub dane utracone w ramach zmiany rozdzielczości. Musimy tolerować zmiany szybkości klatek (np. Z 24 klatek na sekundę do 30 klatek na sekundę). Rozważane są również zmiany proporcji, takie jak od 4: 3 NTSC do 16: 9 HD. Chcielibyśmy poradzić sobie ze zmianami przestrzeni kolorów, np. Z kolorowego na monochromatyczny.
Następnie są transformacje, które wpływają na wszystkie te naraz, takie jak transkodowanie między HD i PAL, które może jednocześnie wpływać na przestrzeń kolorów, liczbę klatek na sekundę, współczynnik proporcji i rozdzielczość. Charakterystyka powinna również być tolerancyjna na pewien stopień przycinania i/lub wypełniania, tak jak ma to miejsce w przypadku przełączania w przód iw tył pomiędzy proporcjami 4: 3 i 16: 9 (format letterbox, ale nie skanowanie panoramiczne &). Powinniśmy również traktować filmy, które zostały przycięte, takie jak usunięcie napisów z końca filmu fabularnego. I, oczywiście, musimy również poradzić sobie z różnicami stworzonymi przez różne kodery, które były karmione identycznym strumieniem wideo.
To dość lista! Zastanówmy się nad niektórymi rzeczami, których możemy nie uwzględniać: podejrzewam, że nie można znaleźć dopasowania, gdy występuje zniekształcenie obrazu, mimo że anamorficzne wypaczanie nie jest niczym niezwykłym, zwłaszcza w filmach 35 mm z szerokim ekranem, które były bezpośrednio zeskanowane bez anamorficznej rekonstrukcji (ludzie szczupli). Możemy również zdecydować się na niepowodzenie, gdy duże znaki wodne są obecne w środku kadru, choć będziemy chcieli tolerować mniejsze znaki wodne w rogach. I na koniec, nie można dopasować filmów, które zostały czasowo zniekształcone lub odwrócone przestrzennie, na przykład gdy jeden z nich jest slo-mo na drugim lub został odwrócony z lewej na prawą.
Czy chodzi tu tylko o pokrycie przestrzeni wideo? Mam nadzieję, że jest jasne, dlaczego ważne jest, aby zacząć od systemu plików i audio! Oznacza to, że najpierw należy pomyśleć o swojej bazie danych bardziej jak o kolekcji MP3, zanim uzna się ją za kolekcję wideo.
Ignorowanie dźwięku, wideo to po prostu uporządkowana sekwencja zdjęć. Dlatego właśnie szukamy jednego lub więcej algorytmów porównywania obrazów w połączeniu z jednym lub kilkoma algorytmami porównywania szeregów czasowych. Może to być albo para oddzielnych algorytmów (scharakteryzować każdą ramkę, następnie scharakteryzować sekwencję ramek), albo może zostać połączona w jeden algorytm (spójrz na różnice między ramkami).
Same obrazy mogą zostać dalej rozłożone, tworząc monochromatyczny "strukturalny" obraz i "nakładkę" koloru. Sądzę, że możemy bezpiecznie zignorować informacje o kolorach, jeśli jest to wygodne pod względem obliczeniowym.
Z powyższego może się wydawać, że zakładam, że będziemy musieli w pełni odkodować film, aby przeprowadzić porównania.Niekoniecznie tak jest, chociaż porównanie zakodowanych danych ma wiele trudności, które ograniczają jego użyteczność. Jedynym istotnym wyjątkiem jest kodowanie wideo na poziomie obiektu, takie jak MP4, gdzie przeprowadzono bardzo wysokie poziomy porównań wielopłaszczyznowych. Niestety, porównywanie obiektów między strumieniami MP4 nie przyniosło wielu badań i nie znam pakietów, które mogłyby wykonać tę funkcję. Ale jeśli znajdziesz, użyj go!
Większość innych cyfrowych strumieni wideo wykorzystywać systemy kodowania, takie jak MPEG-2, Quicktime'ie, lub coś podobnego. Wszystkie te schematy używają pojęcia klatek kluczowych i ramek różnicowych, chociaż każda z nich implementuje je inaczej. Gdy porównywane są różne filmy wideo (te, które nie mają tego samego rozmiaru), jest mało prawdopodobne, że klatki kluczowe i ramki różnicowe będą pasować do dowolnego użytecznego stopnia. Nie oznacza to jednak, że jest to niemożliwe i istnieją pakiety, które próbują wyodrębnić użyteczne informacje z takich strumieni bez wykonywania pełnego dekodowania. Jeśli znajdziesz taki, który jest szybki, może należeć do kategorii testów "dlaczego nie spróbować?".
Jedną z sztuczek, której użyję, zamiast dekodować klatki całkowicie, będę dekodować je tylko na oddzielne kanały składowe (HSV, HSL, YUV, cokolwiek), a nie całą drogę do bufora ramki RGB (chyba że to, co było zakodowane, oczywiście). Stąd chciałbym stworzyć oddzielne ramki luminancji i chrominancji (koloru), aby możliwe było porównywanie w powiązanych domenach. Dekodowanie do bufora ramki RGB może wprowadzać błędy, które mogą utrudniać znajdowanie dopasowań.
Następnie odrzuć informacje o kolorach. Ponieważ monochromatyczne wideo powinno pasować do jego kolorowego oryginału, po prostu nie dbamy o kolor!
Jak może uzyskana sekwencja klatek monochromatycznych najlepiej porównać do innej sekwencji, które mogą pojawić się bardzo różne, ale nadal może ewentualnie być mecz? Odnotowano dziesięciolecia badań w tej dziedzinie, z których znaczna część została zaklasyfikowana jako "niezmienna w skali detekcja". Niestety, bardzo niewiele z tych badań zostało bezpośrednio zastosowanych do określenia, kiedy filmy są lub nie pasują do siebie.
Dla naszych celów możemy podejść do tego problemu z kilku stron. Po pierwsze musimy sami wiedzieć, co jest i nie jest pasujące w domenie monochromatycznej. Na przykład nie dbamy o różnice w poziomie pikseli, ponieważ nawet jeśli dwa pasujące do siebie filmy mają tę samą rozdzielczość, musimy tolerować pewien poziom szumu z powodu różnic między koderami.
Prosta (ale powolny) rozwiązaniem jest przekształcenie każdego obrazu w formie, która jest niezależna od obu rozdzielczości i proporcji. Jedna z takich transformacji mieści się w dziedzinie częstotliwości, a 2D FFT jest do tego idealna. Po odrzuceniu wyimaginowanego komponentu, rzeczywisty komponent może zostać obcięty przy wysokich częstotliwościach, aby usunąć szum i przy niskich częstotliwościach, aby usunąć efekty proporcji, a następnie znormalizowany do standardowej skali, eliminując różnice w rozdzielczości. Uzyskane dane wyglądają jak dziwny malutki obraz, który można bezpośrednio porównać ze strumieniami wideo.
Istnieje wiele innych strategii możliwe transformacji rama, wiele znacznie bardziej wydajne niż FFT i poszukiwanie literatury należy je podświetlić. Niestety, wiem o kilku, które zostały zaimplementowane w bibliotekach oprogramowania, które są tak łatwe w użyciu jak FFT.
Kiedy zmieniły ramki monochromatycznych do mniejszych i bardziej użytecznej domeny, nadal musi wykonać porównanie do innego takiego strumienia z innego filmu. A ten film jest prawie pewny, że nie jest dopasowaniem ramka do ramki, więc proste porównanie na pewno się nie powiedzie. Potrzebujemy porównania, które uwzględni różnice w dziedzinie czasu, w tym dodanych/usuniętych klatek i różnic w liczbie klatek na sekundę.
Jeśli spojrzeć na sekwencji klatek FFT, można zauważyć pewną bardzo wyraźną zachowanie.Zanikanie sceny jest gwałtowne i niezwykle łatwe do wykrycia, można także rozróżnić cięcia, a w FFT zazwyczaj występują powolne zmiany. Z sekwencji FFT możemy oznaczyć każdą klatkę jako pierwszą po wycięciu/zaniknięciu lub jako ramkę pomiędzy odcięciami/zanikami. Ważny jest czas pomiędzy każdym cięciem/zaniknięciem, niezależnie od ramek liczbowych między nimi, co tworzy sygnaturę lub odcisk palca, który jest w dużej mierze niezależny od szybkości klatek.
Wykonanie tego odcisku palca całego filmu powoduje, że dane są znacznie mniejsze niż sam film. Jest to również liniowa sekwencja liczb, prosty wektor z szeregiem czasowym, podobnie jak audio, i może być analizowana za pomocą wielu tych samych narzędzi.
Pierwsze narzędzie polega na wykonaniu korelacji w celu ustalenia, czy wzór cięć w jednym filmie jest zbliżony do tego w innym filmie. Jeśli występują znaczne różnice, filmy są inne. Jeśli są one zbliżone, to należy porównać tylko kilka FFT po każdym skorelowanym cięciu, aby określić, czy ramki są do siebie podobne, aby pasowały.
Nie będę tutaj porównywał 2D FFT, ponieważ istnieją obszerne referencje, które wykonują pracę o wiele lepiej niż ja.
Uwaga: Istnieje wiele innych operacji (poza funkcją 2D FFT), które można zastosować do klatek monochromatycznych w celu uzyskania dodatkowych odcisków palców. Reprezentacje rzeczywistej zawartości obrazu mogą być tworzone przez wyodrębnianie wewnętrznych krawędzi obrazu (dosłownie jak odcisk palca FBI) lub poprzez selektywne progowanie obrazu i wykonywanie operacji "blobowania" (tworzenie połączonej listy pokrewnych deskryptorów regionu). Śledzenie ewolucji krawędzi i/lub obiektów blobowych między ramkami może być używane nie tylko do generowania list cięcia, ale może być również użyte do wyodrębnienia dodatkowych charakterystyk obrazu wysokiego poziomu, które zostałyby utracone za pomocą 2D FFT.
Opracowaliśmy sekwencję algorytmów porównawczych, które powinny być bardzo szybkie w wyszukiwaniu niezgodności i nie wymagają zbyt wiele czasu, aby jednoznacznie określić dopasowanie. Niestety, posiadanie algorytmów nie rozwiązuje problemu! Musimy rozważyć kilka kwestii związanych z najlepszym sposobem wdrożenia tych algorytmów.
Po pierwsze, nie chcemy otwierać i czytać każdego pliku wideo dłużej, niż to konieczne, w przeciwnym razie procesor mógłby zatrzymać oczekiwanie na dane z dysku. Nie chcemy też czytać dalej w pliku, niż jest to potrzebne, ale nie chcemy zbyt szybko przestać czytać i potencjalnie przegapić późniejszy mecz. Czy informacje dotyczące każdego filmu wideo powinny zostać zapisane, czy też powinny zostać ponownie obliczone w razie potrzeby? Rozwiązanie tych problemów pozwoli na opracowanie, przetestowanie i wdrożenie wydajnego i skutecznego systemu porównywania wideo.
Pokazaliśmy, że możliwe jest porównywanie filmów z pewną nadzieją na znalezienie dopasowania w bardzo zmiennych warunkach, z wydajnością obliczeniową.
Reszta została pozostawiona jako ćwiczenie dla czytelnika. ; ^)
+1 za bardzo interesujące pytanie - ale to zdecydowanie wymaga różnych tagów. PHP nie będzie tu językiem wyboru. –
Zgadzam się z @Pekka. – Josh
Zgadzam się też: Nie wiem, dlaczego to tam umieściłem: D –