Podręcznik

Indeksowanie multimediów to w pierwszym przybliżeniu tworzenie formalnego w sensie reprezentacji cyfrowej opisu treści multimedialnej, zawartej w różnego typu zbiorach i bazach danych, zbiorach obiektów lub ogólniej -- kolekcjach multimedialnych, czy nawet strumieniach multimedialnych (indeksowanie i wyszukiwanie on-line. 

Atrybutem obiektu multimedialnego nazywana jest ustalona, istotna jego właściwość, służąca specyficznej (różnicującej) charakterystyce obiektu w odniesieniu do przeglądanych zasobów (kolekcji obiektów). Cecha to wartość danego atrybutu przypisana obiektowi. Dana cecha $c$ obiektu $o$ uwzględnia więc określony aspekt obiektu  definiowany atrybutem $a$.  Atrybut $a: \mathcal{O}\rightarrow \mathcal{C}_a$ przypisuje cechę $c\in \mathcal{C}_a$ obiektowi $o\in \mathcal{O}$, gdzie $\mathcal{O}$ jest kolekcją obiektów multimedialnych.

Dobór atrybutu efektywnie różnicującego obiekty może być niekiedy zadaniem niełatwym, mało intuicyjnym. Często rozważa się w takich przypadkach cały zestaw możliwych właściwości, przy czym dopiero ich połączenie pozwala uzyskać zadawalający opis kolekcji. Atrybut przyjmuje wtedy postać atrybutu złożonego, tj. wieloelementowego. Może to być atrybut listowy, zawierający zestaw cech tego samego typu - np. kolory dominujące, opisujący kilka kolorów przeważających lokalnie (przykładowo w blokach sztywnego podziału obrazu) lub statystycznie w skali całego obrazka (np. na podstawie histogramu kolorów). Lista cech kolorów dominujących skonstruowana jest wtedy na podstawie atrybutu podstawowego - kolor obrazu. Ten sam alfabet wartości koloru przypisywany jest poszczególnym elementom atrybutu listowego.  

Każdy obiekt $o \in \mathcal{O}$ charakteryzowany jest wtedy  za pomocą zestawu atrybutów $\{a_k\}_{k=1,\ldots,K}$, tj. właściwości istotnych np. ze względu na sposób użytkowania. W przypadku danego obiektu właściwości przyjmują określoną postać tworząc wektor cech obiektu: $\mathcal{C}_{\mathbf{a}}=[a_1(o),\ldots,a_K(o)]=[c_1,\ldots,c_K]$, gdzie zestaw cech pojedynczych $c_k=a_k(o)$ stanowi numeryczny deskryptor obiektu danej kolekcji, względem ustalonego zestawu atrybutów.

Na podstawie opisów właściwości poszczególnych elementów bazy tworzona jest struktura indeksu. Indeks konstruowany jest wokół ustalonego atrybutu (atrybut jest argumentem indeksu) jako zestaw (lista) cech przypisanych obiektom opisywanej kolekcji. Każda z cech odnosi się z kolei do listy wskaźników obiektów posiadających daną cechę. Dwa obiekty są podobne, jeśli posiadają daną cechę lub cechę ''zbliżoną'' (w przybliżeniu podobną). Przy opisie obiektów za pomocą zestawu atrybutów, indeks danej kolekcji budowany jest dla każdego rozpatrywanego atrybutu z osobna. 

Przykładowo, jeśli atrybutem jest procentowa (np. z dokładnością do 5\%) zawartość scen z przemocą w filmach danej kolekcji, to kolejne pozycje indeksu obok precyzyjnych zakresów procentowych wartości zawierają bazodanowe identyfikatory filmów, zgodnie z określoną przez atrybut scen przemocy ich charakterystyką. Idąc dalej, indeks zasobów przykładowej wypożyczalni filmów może zostać zaprojektowany według zestawu atrybutów (atrybutu złożonego), składającego się dodatkowo z kategorii opisującej charakter filmu, jego treść, dozwolony przedział wiekowy potencjalnych widzów, gwiazdkową skalę atrakcyjności według ocen ekspertów oraz wskaźnik popularności wypożyczeń czy orientacyjny czas trwania filmu (z listą cech: krótki - czas trwania do godziny, średni - czas trwania od 1h do 2h, długi - 2h $<$ czas $\leq$ 3h , bardzo długi - czas $>$ 3h).

Zależnie od rodzaju atrybutu, a także oczekiwanej zdolności różnicowania obiektów opisanych indeksem można opracować zestaw mniej lub bardziej szczegółowych cech, które stają się cechami reprezentatywnymi. Przykładowo, lista cech atrybutu dominujący kolor obrazu  może zawierać jedynie pozycję zielony lub też bardziej szczegółowe: jasnozielony, zielony, ciemnozielony czy turkusowy. W każdym z tych przypadków należy precyzyjnie określić przedziały wartości np. trzech składowych RGB, które odpowiadają poszczególnym barwom. Dwa obiekty są podobne w sensie dominującego koloru, jeśli ich barwa opisana liczbowo w przestrzeni RGB przyporządkowana zostaje tej samej cesze z listy atrybutu indeksu. Mamy w tym przypadku określenie subiektywnej cechy pojęciowej (opisanej tekstowo) za pomocą obliczeniowo obiektywnej cechy numerycznej, inaczej deskryptora numerycznego. Taka definicja nie musi być jednak jednoznaczna (niekoniecznie ustalone przedziały liczbowe zostaną uznane przez wszystkich użytkowników; subiektywne wrażenie barwy zależy niekiedy od kontekstu, więc odczytanie lokalnej barwy pikseli może być odmienne przy tych samych wartościach pikseli w  przestrzeni RGB itp.). 

Podobieństwo cech obiektów jest pojęciem bardzo istotnym przy konstrukcji indeksów oraz organizacji całej procedury wyszukiwania treści multimedialnej.  Podobieństwo obiektów ze względu na określony atrybut dotyczy bliskości ich cech lub też jest funkcją odwrotną ich odległości (metryki). Podobieństwo w sensie metrycznym określane jest za pomocą znormalizowanej funkcji podobieństwa cech atrybutu $a$ jako $\rho_a\colon \mathcal{C}_a\times \mathcal{C}_a\leftarrow [0,1]$. Dwa obiekty są więc bardziej podobne ze względu na określoną ich właściwość, jeśli $\rho_a(c1,c2)=\rho_a(a(o_1),a(o_2))$ jest bliższe wartości 1. Ustawiając sztywną wartość progową, np. $t=0,9$ definiujemy jako podobne względem siebie te obiekty, dla których $\rho_a(c1,c2) \geq t$. Z kolei jeśli ze zbioru obiektów $\{o\}_{1,2\ldots}$ chcemy wybrać najbardziej podobny do $o$ (w sensie określonego $a$), wtedy 
\begin{equation*}
o_{\mathrm{naj\_pod}}=\arg \max_{\{o_i;i=1,2\ldots\}} \{\rho_a(a(o),a(o_i))\}
\end{equation*}

Przykładowo, jeśli cechami są liczby różniące się maksymalnie o $M$, wówczas funkcję podobieństwa można ogólnie zdefiniować jako:

$\rho (c1,c2)\triangleq 1-\frac{|c1-c2|}{M}$

Ukonkretniając, jeśli cechami są dowolne punkty w kwadracie o boku 1, wtedy $\rho (c1,c2)\triangleq 1-\frac{\|c1-c2\|}{\sqrt{2}}$, gdzie metryka $\|\cdot\|$ rozumiana jest w sensie euklidesowej odległości na płaszczyźnie dwóch wektorów wskazujących cechy obiektów.

Ogólniej, podobieństwo opisywane za pomocą odległości cech $\delta(c1,c2)$ można zapisać jako

Przy określaniu podobieństwa wyrazów czy ogólniej danych typu tekstowego użyteczne jest podobieństwo typu edycyjnego czy też rangowego (dotyczącego pozycji cechy w ustalonym porządku). Funkcję podobieństwa edycyjnego można wyznaczyć za pomocą (3.1), przy czym odległość $\delta(c1,c2)$ pomiędzy wyrazami (słowami, terminami) określana jest jako najmniejsza liczba operacji zmiany, usuwania i dołączania pojedynczego symbolu (litery) w dowolnym miejscu, dzięki którym sekwencja $c1$ przekształcana jest w sekwencję $c2$. Normalizująca wartość $\max_c |c|$ uwzględnia największą możliwą długość słowa w danym zbiorze cech.  

Przykładowo, obliczając podobieństwo słów $c1=Mama$ oraz $c2=Matka$ minimalna liczba operacji przekształcenia $c1$ i $c2$ wynosi 3, bo aby przekształcić Mama w Matka wystarczy wykonać kolejno: USUŃ m,3 (usuń m na pozycji 3, licząc od 1); DODAJ t,3; DODAJ k,4 (symetrycznie trzy odwrotne operacje przekształcają Matka w Mama). Tak więc podobieństwo wynosi 

$\rho (Mama,Matka)=1-\frac{3}{25}=0,88$

Określając podobieństwo rangowe wykorzystuje się określenie pozycji cechy $r(c)$:

Przykładem może być obliczenie rangowego podobieństwa planet naszego układu słonecznego. Przyjmując, że mamy 8 planet układu -- od Merkurego po Neptuna, na podstawie odległości trzeciej Ziemi od piątego Jowisza możemy policzyć

$\rho (Ziemia,Jowisz)=1-\dfrac{|3-5|}{8-1}\approxeq 0,714$

Przy opisie terminów cyklicznych, jak np. miesięcy roku, podobieństwo rangowe należałoby zmodyfikować do postaci 

Wtedy podobieństwo  czerwca do października wynosi 
$\rho (\textit{czerwiec,październik})=1-\dfrac{\min(|6-10|,12-|6-10|)}{12-1}=\approxeq 0,636$
zaś stycznia do grudnia 
$\rho (\textit{styczeń,grudzień})=1-\dfrac{\min(|1-12|,12-|1-12|)}{12-1}=1-\dfrac{\min(12,1|)}{11}\approxeq 0,91$
W procesie indeksowania konieczne jest uwzględnienie zarówno manualnego, pojęciowego, jak i automatycznego mechanizmu wyznaczania wartości atrybutu dla danego obiektu z kolekcji. Proces ekstrakcji cech atrybutu $a$ sprowadza się do wyznaczenia podzbioru wszystkich możliwych wartości $a$ w postaci tzw. cech reprezentatywnych: $\mathcal{C}_a^{\tau}\subset \mathcal{C}_a$. Reprezentatywność cech oznacza istnienie funkcji reprezentacji $\tau_a : \mathcal{C}_a\rightarrow \mathcal{C}_a^{\tau}$, przypisującej dowolnej wartości atrybutu jego cechę reprezentatywną. Mają tutaj zastosowanie m.in. efektywne metody kwantyzacji danych. Przybliżenie danej cechy obiektu $c=a(o)$ za pomocą cechy reprezentatywnej $c^{\tau} =\tau_a(c)=\tau_a(a(o))$ powinno przynieść następujące efekty:

• uprościć strukturę indeksu (zredukować zajętość pamięci przechowującej indeks, przyspieszyć operacje na indeksie),
• uprościć i uczynić bardziej przejrzystym kryterium podobieństwa cech poprzez możliwe jednoznaczne odniesienie wartości liczbowych do reprezentowanej treści, zgodnie z oczekiwaniem użytkownika,
• zachować, a nawet zwiększyć selektywność wyszukiwania poprzez precyzyjniejszy opis semantyczny.

Przykładowo, kształt guza w obrazach mammograficznych można opisać całym zestawem parametrów badających kolistość, relację długości obwodu do pola powierzchni, pole powierzchni odniesione do pola wpisanego prostokąta, gładkość konturu i jego symetryczność, itd. Znormalizowane wartości liczbowe tych parametrów można następnie zredukować usuwając nadmiarowość takiej reprezentacji (np. metodą analizy składowych głównych PCA). Zredukowaną liczbę tak uzyskanych parametrów można ustawić w wektor liczbowy, kwantowany następnie do kilkunastu możliwych postaci wektora reprezentującego guzy. Schemat kwantyzacji można zaprojektować odnosząc się do analogicznej charakterystyki wzorców guzów złośliwych i łagodnych zapewniając, by dobrane poziomy kwantyzacji dawały największe zróżnicowanie przypadków zdrowych i chorobowych.

Cechami reprezentatywnymi atrybutów o wartościach typu tekstowego mogą być np. rdzenie wyrazów, np. matur, będący rdzeniem słów przedmaturalny, pomaturalny, maturą, maturze, matury itp.

Deskryptorem jest słowo, fraza, znaki alfanumeryczne, zestawy liczb lub też  metoda czy algorytm służące charakterystyce czy wręcz identyfikacji obiektów (składników treści) sygnałów naturalnych w systemach gromadzenia i przeszukiwania informacji. Deskryptor dotyczy określonego atrybutu, czyli wybranej właściwości obiektów. W konwencji standardu MPEG-7 jest numerycznym sposobem opisu atrybutów pojęciowych, czy też realizatorem numerycznego opisu danego atrybutu. Są to meta-dane wyznaczane automatycznie na bazie sygnału cyfrowego przenoszącego treść multimedialną.

W przypadku deskryptorów numerycznych możliwe jest dokładniejsze różnicowanie podobieństwa obiektów z listy danej cechy pojęciowej. Przykładowo, euklidesowa odległość \footnote{Odległość definiowana zgodnie z metryką euklidesową: $||x-y||=\sqrt{(R_x-R_y)^2+(G_x-G_y)^2+(B_x-B_y)^2}$ w przestrzeni kolorów RGB.} wektorów opisujących obiekty w przestrzeni RGB i definiujących  de facto ich kolor pozwala precyzyjnie ustalić podobieństwo cech - mniejsza odległość wskazuje na większe podobieństwo koloru obiektów. Możliwe jest wtedy zbudowanie indeksu wartości numerycznych deskryptorów koloru dominującego, z  przypisaną dodatkowo kategorią cechy pojęciowej. Algorytm pozwala ustalić precyzyjnie kolor dominujący danego obrazu czy regionu, który zostaje skwantowany zgodnie z przedziałami pojęciowego opisu barw (tj. zielony, niebieski}itd.). Mamy wtedy do czynienia z indeksem tekstowo-numerycznym, który może być przeszukiwany z kryterium bliskości cech numerycznych, jak też identyczności cech pojęciowych (np. $zielony=zielony$).  

Proces znakowania treści określonych zasobów danych z wykorzystaniem struktury indeksu nazywamy indeksowaniem. Indeksowanie multimediów dotyczy metod konstrukcji indeksów kolekcji (zbiorów) obiektów multimedialnych. Ze względu na bogactwo zawartej informacji, szczególnie interesującym zagadnieniem jest indeksowanie obrazów. Stosowną od kilkudziesięciu lat praktyką syntetycznej charakterystyki treści obrazów jest manualne tworzenie opisów alfanumerycznych. Do ich przeszukiwania wykorzystywano zwykle silnik bazodanowy DBMS (Database Management System) . Opracowano wiele technik związanych w oceną efektywności zapytań, strukturami danych, metodami przeszukiwania i przechowywania indeksów.