Wrocław, 14 marca 2011r.
Wyszukiwanie i indeksowanie
wideo
Rafał Poniatowski 164761
Plan prezentacji
1. Podstawowe pojęcia
2. COBRA - indeksowanie meczy tenisowych
3. System indeksujÄ…cy mecz baseballowy
4. Prosty system indeksacji dla bibliotek
cyfrowych
5. Indeksowanie
6. Bibliografia
1/42
 Indexowanie wideo jest kluczem do
przyszłości internetu.
- Mark Randall, szef strategiczny firmy Adobe
2/42
Indeksowanie danych
" Indeksowanie  pojęcie ściśle związane z
bazami danych. Polega na tworzeniu
struktury danych w bazie danych, której
celem będzie poprawa szybkości operacji
pobierania danych.
" Bezpośrednio wynika z tego fakt
wydłużenia czasu zapisu tych danych do
bazy oraz zwiększenie ilości
zajmowanego na dysku miejsca.
3/42
Wideo
" Poprzez  wideo rozumiemy dane
audiowizualne, kolokwialne określane po prostu
jako  filmy , czy  filmiki . Jak każdy wie jest
to ważna część współczesnego internetu.
" Trzecia najczęściej odwiedzana witryna
internetowa na świecie, YouTube, zajmuje się
niemal wyłącznie hostingiem oraz
indeksowaniem wideo.
4/42
Indeksowanie wideo
" Znaczenie indeksowania w obrębie danych
audiowizualnych jest szersze i nieco inne niż w
odniesieniu do innych przypadków.
" Indeksowanie wideo ma umożliwić nie tylko
przyspieszenie wyszukiwania żądanych zasobów, ale
przede wszystkim pozwolić użytkownikom na
odnalezienie skomplikowanych treści.
" Definicja indeksowania wideo [C. Snoek, M. Worring,
Multimodal Video Indexing, 2005] mówi, że  jest to
proces automatycznego przypisywania etykiet
odnoszących się do treści .
5/42
Popularne sposoby indeksowania
" Większość spotykanych filmów video indeksowana
jest jedynie po tagach nadawanych przez autora
filmu lub przez innych użytkowników.
" Sprowadza się to w dużej mierze do wyszukiwania
danych tekstowych, podczas gdy możliwości związane
z danymi wideo są znacząco większe.
" Istnieje szereg podejść do problemu. Jest to
dziedzina stale rozwijająca się, a poszczególne
rozwiązania różnią się zazwyczaj nie tylko pod
względem złożoności, ale i podejścia do problemu.
6/42
Możliwości indeksowania wideo
" Zapytania typu:  Pokaż mi filmy z
leworęcznymi zawodniczkami tenisowymi, które
w przeszłości wygrały Australian Open, w
których podbiegają pod siatkę .
7/42
COBRA
Constraint-Based Awareness Management Framework
" Framework stworzony na Uniwersytecie
Twente w Niderlandach.
" Opracowany z myślą o indeksowaniu meczów
tenisowych.
" Zgodny ze standardem MPEG-7.
" Zastosowano kilka modeli i technik
rozpoznawania zawartości obrazu.
Zwiększyło to możliwości obsługi zdarzeń
różnego rodzaju.
8/42
Budowa modelu COBRA
" W celu zautomatyzowania wydobywania
konceptów (obiektów i zdarzeń) do COBRA y
dodane zostały moduły rozszerzające, które
przechowujÄ… konkretnÄ… wiedzÄ™.
" Istnieje np.: rozszerzenie dodające obsługę
gramatyk, w Cobrze pomagającej opisywać
wysokopoziomowe koncepty poprzez
formalizacjÄ™ sposobu ich zapisu.
9/42
Zasada działania modelu COBRA
" Na samej górze znajduje się detektor obiektów
(Feature Detector Engine - FDE). ZarzÄ…dza on procesem
rozpoznawania obrazu i jest odpowiedzialny za
uruchamianie innych modułów.
" FDE znajduje obiekt (nasze wideo) dla którego
uruchamia moduł segmentatora.
" Jego zadaniem jest podział video na pojedyncze ujęcia.
Granice ujęć rozpoznawane są na podstawie różnic w
histogramach kolorów sąsiednich klatek.
" Tym samym sposobem odbywa się klasyfikowanie ujęć
do czterech kategorii: gra (zwykłe ujęcie od góry),
zbliżenie (na zawodnika), widownia, inne.
10/42
Schemat wstępnego działania Cobry
11/42
Sposób klasyfikacji ujęć
" Ujęcia  gra rozpoznawane są na podstawie
dominacji jednego koloru (problemem są różne
kolory nawierzchni).
" Ujęcia  zbliżenia rozpoznawane są gdy
wykryjemy nagromadzenie koloru bliskiego
pigmentowi skóry (znowuż- różne rasy ludzkie).
" Dodatkowo do klasyfikacji wykorzystywane sÄ…
takie cechy obrazu jak charakterystyka
entropii, średni kolor i średnie odchylenie.
12/42
Rozpoznano ujęcie  gry
" Detektor obiektów uruchamia detektor tenisowy.
Zadaniem tego drugiego jest podział obrazu na
kort oraz na zawodników.
" By to zrobić wykorzystuje przybliżone statystyki
koloru kortu i wstępnie dzieli klatkę na
podprostokÄ…ty.
" W następnych klatkach algorytm próbuje
przewidzieć pozycję zawodnika i szuka go w
wyliczonym miejscu.
" Tym samym algorytmem rozpoznajemy detale
13/42
dotyczÄ…ce zawodnika.
Rozpoznawanie detali zawodnika
" Zawodnik jest wyrażony binarnie
(monochromatycznie).
" Znając kształt sylwetki zawodnika podczas gry
staramy się zmaksymalizować liczbę wydobytych
informacji poprzez gruntownÄ… analizÄ™ uzyskanego
obrazu zawodnika.
" Chcielibyśmy znać nie tylko jego obecną pozycję na
obrazku (x;y), ale także położenie na korcie (np.:
prawe pole serwisowe), jego środek masy,
kierunek, mimośród.
14/42
Rozpoznawanie rodzajów zagrań
" Położenie zawodnika i jego ruch w czasie definiują konkretne
zdarzenia np.: granie przy siatce, gra z daleka (baseline).
" Takie zdarzenie jest relacją czasoprzestrzenną, ponieważ
zarówno czas jak i miejsce w którym znajduje się zawodnik
definiujÄ… typ zdarzenia.
" Analiza ruchów zawodnika pozwala na określenie typu
zdarzenia (np.: zawodnik biegnie do siatki  gra przy siatce),
które to określane jest poprzez pewne reguły i warunki.
" Za sprawdzanie faktu spełnienia warunków, bądz
nie,
odpowiadają detektory zdarzeń.
" Zostały one zaimplementowane wg. koncepcji białych i
czarnych skrzynek (znów- dla większej skuteczności,
odporności na zróżnicowane dane wejściowe).
15/42
Schemat rozpoznawania zdarzeń
16/42
Podsumowanie systemu COBRA
" Po przetworzeniu meczu tenisowego
dysponujemy dogłębną wiedzą na temat jego
szczegółów.
" Mamy na przykład możliwość obejrzenia samych
zagrań przy siatce.
" W przypadku zastosowania systemu na stronie
internetowej użytkownicy mogą zgłaszać
szczegółowe zapytania, które zostaną
błyskawicznie obsłużone (takie jak to o
leworęczne zawodniczki).
17/42
Prosty system wspomagajÄ…cy VIVO
" VIVO (A Video Indexing and Visualization
Organizer)  proste narzędzie dedykowane dla
małych bibliotek cyfrowych. Służy do
wprowadzania danych video, ich edycji i
zarzÄ…dzania meta-danymi.
" Może zarządzać zarówno danymi video, jak i
danymi tekstowymi.
18/42
Okno aplikacji VIVO
19/42
Struktura danych w VIVO
" Do reprezentacji danych wykorzystuje siÄ™
wielopoziomowÄ… strukturÄ™ (np.: video Ä…ð segment Ä…ð
klatka), dzięki czemu każdemu z obiektów
przekazywane mogą być przypisane do wyższych warstw
meta-dane (np.: autor, data dodania).
" Dla każdego video wykorzystywane są tzw. storyboardy,
które jak udowodniły badania przeprowadzone na
Uniwersytecie Północnej Karoliny w 2002, zwiększają
efektywność szukania zasobów wideo.
20/42
Przykład storyboardu
21/42
Możliwości zastosowania VIVO
" Pomijając aspekt wydajności (niepewna dla
bardzo dużych środowisk) jest to dobre, a
przede wszystkim darmowe, rozwiÄ…zanie dla
małych stron zajmujących się indeksowaniem
danych wideo.
" Funkcjonalność jest porównywalna z
przeciętnym serwisem tego typu.
" Jest to rozwiązanie przestarzałe, proste i nie
kontynuowane. VIVO jest rodzajem prototypu i
miało na celu wskazać drogę rozwoju.
22/42
System indeksowania meczy
baseballowych
" Opracowany przez NHK (Japan Broadcasting
Corporation)
" Celem było zautomatyzowanie procesu
przypisywania indeksów do poszczególnych ujęć
z meczy baseballowych.
" Do rozwiązania problemu użyto wzorcowania
(patternization) scen oraz Ukrytych Modeli
Markowa (HMM - Hidden Markov Models),
których działanie opiera się na sieci
bayesowskiej.
23/42
Trzy problemy indeksowania
" CO indeksować? Np.: cały dokument,
pojedynczÄ… ramkÄ™?
" JAK indeksować? Wybór sposobu
przypisywania wydobytych informacji.
" JAKIE informacje zawrzeć? Np.:
nazwiska piłkarzy, co w obecnej chwili
robiÄ…, oba na raz.
24/42
Indeksowanie baseballu - idea
" Ideą rozwiązania problemu jest podział ujęć meczu na
prostokąty, które zawierają pewien obraz oraz na
przypisane do nich wektorów ruchu.
" Ujęcia wyrażone są jako ciągi symboli powiązane z
kadrami i odpowiednio zaklasyfikowane do
poszczególnych wydarzeń meczowych. Są to zagrania
baseballowe np.: home-run, single-hit, walk.
" Chcemy przypisać odpowiednie meta-indeksy do
poszczególnych scen. Pomogają w tym Ukryte Modele
Markowa, które zostały do tego celu odpowiednio
zaprojektowane, tak by system potrafił rozróżniać
zdarzenia.
25/42
Indeksowanie baseballu - zdarzenia
" Przykładowe ujęcia zostały wycięte z wielu meczów baseballu.
Utworzono w taki sposób zbiory uczące oraz testowe. A
Ä…cznie
zgromadzono ponad 480 ujęć.
" Każde z ujęć zostało manualnie przypisane do jednej z siedmiu
kategorii  indeksów-zdarzeń :
1. home-run
2. double
3. single-hit,
4. walk
5. fly-out
6. infield-grounder
7. strike-out
" Taki zestaw indeksów zdarzeń uzasadniony jest względną łatwością ich
rozróżnienia i ostatecznie poprawnego zaklasyfikowania ujęć.
26/42
Przykładowe ujęcie meczowe
Kadry przedstawiajÄ… zdarzenie- zagranie  double
27/42
Uczenie Ukrytych Modeli Markowa
" Schemat uczenia i kroki trenowania:
- wykryj zmiany kadrów w ujęciach i przypisz indeks wydarzenia
do każdego z nich
- opisz każde z ujęć ciągiem symboli
- ustaw parametry HMM używając sekwencji symboli
odpowiedniej dla każdego zdarzenia
" Po tym etapie następuje proces analizy
kadrów poprzez nałożenie na obraz
punktów śledzących obiekty
(tracking points), co ma na celu
przypisanie obiektu do jednego z
istniejących wzorców.
28/42
Przykładowe wzorcowanie kadru
29/42
Podsumowanie skuteczności
rozponawania zagrań baseballowych
30/42
Semantyczne indeksowanie wideo
1/2
" Obecnie popularnym kierunkiem rozwoju
indeksowania wideo jest tzw. semantyczne
indeksowania wideo (semantic video indexing).
" By pokazać czym ono jest zastanówmy się
chwilę nad pytaniem: co widzimy na poniższym
obrazku?
31/42
Semantyczne indeksowanie wideo
2/2
" Z pewnością większość ludzi
stwierdzi, że są tu pokazane
palmy, plaża i zachód słońca.
" Jednak dla przeciętnej
wyszukiwarki obrazów czy wideo
będzie to tym z czym zostało to
zdjęcie skojarzone np.: prognozą
pogody na stronie BBC, ponieważ
taki meta-znacznik przypisany został do tego obrazu.
" Popatrzmy na 3 możliwości opisania tego obrazu pod względem
jego zawartości, rożniące się stopniem złożoności:
- zachód słońca (trywialny przypadek- nawet średni kolor o tym mówi)
- palmy (trudny przypadek)
32/42
- Hawaje (niemożliwe do zgadnięcia)
Idea semantycznego indeksowania
wideo
" Czym jest zatem semantyczne indeksowanie wideo? Po
poprzednich slajdach i analizie obrazu Å‚atwiej jest
zrozumieć istotę zagadnienia.
" Podczas gdy przy zwykłym indeksowaniu skupiamy się na
słowach kluczowych, przy indeksowaniu content-based
skupiamy się na zawartości wideo, którego się
spodziewamy w indeksowaniu semantycznym operujemy
na konceptach- obiektach których rodzaju nie znamy.
Operujemy na wyższym poziomie abstrakcji, próbujemy
zidentyfikować te koncepty.
" Potrafiąc wyszczególnić z klatki obrazu poszczególne
obiekty chcemy być w stanie określić ich typ (są
drzewami, palmami, plażą, prognozą pogody?).
33/42
Definicja semantycznego
indeksowania wideo
 Jest to proces automatycznego
rozpoznawania obecności
semantycznego konceptu w strumieniu
wideo
" Rozumiane jako dogłębna analiza zawartości
strumienia wideo.
34/42
Problemy zwiÄ…zane z zagadnieniem
" Małe podobieństwo tych samych obiektów oglądanych
z różnej perspektywy.
Ten sam obiekt
" Duże podobieństwo różnych obiektów oglądanych z
podobnej perspektywy.

Różne obiekty
35/42
Generyczne indeksowanie semantyczne
" Rozwinięciem semantycznego indeksowania jest zagadnienie
generycznego indeksowania semantycznego (general semantic
video indexing).
" Jest jednym ze szczytowych osiągnięć technik wyszukiwania
informacji, ale wciąż jest jeszcze intensywnie rozwijane i nie
występuje poza fazą beta.
" Polega na zwracaniu filmów video (jedynie samych
interesujących nas ujęć) dla niemal każdego zapytania np.:
 pokaż mi filmy na których widać idącego George W. Busha .
" Wyszukiwanie semantyczne jest problemem wymagajÄ…cym
zastosowania komponentów najwyższej jakości (moduły
rozpoznawania obrazu) oraz potężnych zasobów finansowych.
" Końcowy efekt z pewnością zwróci się bardzo szybko ze względu
na nieosiągalną wcześniej jakość wyników zapytań.
36/42
Dlaczego jest to takie trudne?
Ponieważ jest tak wiele obiektów, które należy rozróżniać
37/42
Algorytm znajdowania ścieżek
" Przebiegiem procesu steruje algorytm znajdowania
ścieżek (ang. semantic pathfinder algorithm).
" W generycznym indeksowaniu semantycznym system
składa się z wielu niezależnych algorytmów detekcji
obiektów (np.: drzew, samochodów, twarzy). Wymaga
to możliwie najwyższej jakości każdego z komponentów.
" Obraz obok przedstawia przykładową
strukturę hierarchii detektorów.
" Wierzchołki to obiekty, a linie to
relacje między nimi np.: detektor
chmur jest specjalizacjÄ… obiektu
niebo itd.
38/42
Algorytm znajdowania ścieżek
" Odpowiedni algorytm pozwala na:
- przyspieszenie pracy (nie bierzemy pod uwagÄ™
wszystkich możliwości, lecz działamy  logicznie 
jeśli obiekt nie jest zielony to staramy się nie
sprawdzać czy jest to trawa)
- unikanie błędów związanych z niepoprawnym
przypisaniem indeksu (decyzje podejmujemy
stopniowo np.: czy obiekt jest bardziej niebiem, czy
bardziej ziemiÄ…, potem przechodzimy dalej)
- ułatwienie procesu wizualizacji dochodzenia do
rozwiązania i zwrócenia podobnych wyników
39/42
Przykładowy interfejs
40/42
Podsumowanie indeksowania semantycznego
" Generyczne indeksowanie semantyczne otwiera nowÄ…
drogÄ™ w dziedzinie wyszukiwania informacji
audiowizualnych.
" Zasada jego działania zaczyna przypominać pracę
ludzkiego mózgu, przez co podnosi istotnie trafność
zwracanych wyników.
" Aby opracować najlepszy system uczeni z różnych
dziedzin muszą dać z siebie wszystko co najlepsze i
działać we wspólnym celu. Potrzeba świetnie
działających detektorów obiektów, dobrego algorytmu
znajdowania ścieżek, koordynacji oraz motywacji i
chęci działania.
41/42
Bibiografia
" M. Petkovic, R. van Zwol, H.E. Blok, Content-based Video Indexing for the
Support of Digital Library Search, 2002
" Meng Yang, Xiangming Mu & Gary Marchionini, VIVO -A Video Indexing and
Visualization Organizer
" Takahiro Mochizuki, Makoto Tadenuma, Nobuyuki Yagi, BASEBALL VIDEO
INDEXING USING PATTERNIZATION OF SCENES AND HIDDEN MARKOV
MODEL, 2005
" Dr Marcel Worring, University of Amsterdam, Semantic Video Search Indexing
and Concept Detection, 2008
" Cees Cees G.M. G.M. Snoek Snoek & Arnold W.M. & Arnold W.M. Smeulder,
Video Search Engines, 2010
" Mark Randall, Beep.TV, www.beet.tv/2008/04/ndexing-is-key.html
" http://www.reelseo.com/semantic-video-indexing/
Koniec
Dziękuję za uwagę i zachęcam do zadawania pytań
XX/YY