Zadanie Projektowe
Realizacja systemu indeksowania dokumentów multimedialnych z uwzględnieniem takich cech indeksu jak:
  • słownik cech
  • listy obiektowe zapisywane w postaci skompresowanej
  • słownik obiektów
Koncepcja rozwiązania zadania
Wybór deskryptora wizualnego
W projekcie został zrealizowny deskryptor koloru dominującego zgodny z MPEG-7. Zgodnie ze standardem deskryptor ten składa się ze zmiennej liczby kolorów reprezentatywnych danego obrazu wraz z ich procentowym udziałem.
Przykład wyekstrahowanego koloru dominującego
Przykład wyekstrahowanego koloru dominującego
Struktura Indeksu
W procesie wyszukiwania i porównywania obrazów przy użyciu deskryptora koloru dominującego wymagane jest sprawdzenie odległości między kolorami dominującymi występującymi w analizowanych obrazach (każdy z każdym). Co więcej odległości te są skalowane przez czynnik procentowy ich wystąpienia. Dlatego wybór struktury do przechowywania takiej kolekcji danych jest dość problematyczny. W swoim projekcie posłużyłem się drzewem 2-3-4. Drzewo to cechują następujące własności:
  • Zawsze jest to drzewo zrównoważone
  • Każdy węzeł może przechowywać jeden, dwa lub trzy elementy danych.
  • Węzeł z jednym elementem danych zawsze ma dwóch potomków (analogicznie z dwoma elementami - trzech, trzema - czterech)
Klucze i węzły potomne
Klucze i węzły potomne
Do podziału cech wektorowych składników kolorów dominujących została wykorzystana metoda przedziałów wektorowych. Każdemu kolorowi dominującemu z przestrzenio kolorymetrycznej L*u*v* przydzielam numer przedziału wektorowego zgodnie z zależnością:
  1      public int[] getColorClosestBoxesLUV(){
  2       int ltmp=(int)Math.round((l-PixelColor.Lmin)/(PixelColor.Lmax - PixelColor.Lmin)*255);
  3       int utmp=(int)Math.round((u-PixelColor.Umin)/(PixelColor.Umax - PixelColor.Umin)*255);
  4       int vtmp=(int)Math.round((v-PixelColor.Vmin)/(PixelColor.Vmax - PixelColor.Vmin)*255);
  5
  6       int lq=(ltmp >>> 5)*64;
  7       int uq=(utmp >>> 5)*8;
  8       int vq=(vtmp >>> 5);
  9
 10       int[] box=new int[1];
 11       box[0]=lq+uq+vq;
 12
 13       return box;
 14       }
W drzewie w węzłach o wartościach kluczy równych numerowi przedziałów wektorowych przechowuję listy obiektowe obrazów, które w zestawie kolorów dominujących zawierają te które należą do danego przedziału wektorowego. W procesie wyszukiwania dal każdego składowego koloru dominującego wyszukuję w drzewie listy obiektów, które zawierają dany skłądowy kolor dominujący. Następnie listy są łączone i na wybranym podzbiorze zostaje wykonane zapytanie K-NN (k najbliższych sąsiadów).
Charakterystyka przykładowego indeksu
W celu przetestowania możliwości programu wykorzystałem udostępnioną bazę ponad 1300 zdjęć o różnorodnej kolorystyce. Policzone deskryptory dla tej kolekcji:
Deskryptory dla obrazów zostału zapisane w postaci binarnej w formacie:
\left[ nazwa pliku \right] \left[ ilosc kolorow \right] \left[ kolor dominujacy ( czestotliwosc wystapienia, R, G, B ) \right]
Kompresja list obiektowych
Listy obiektowe przechowywane w węzłach drzewa zostały skompresowane metodą interpolacyjną. Globalny stopień kompresji wyniósł ponad 600% (przyjąłem, że liczba int w JAVA zajmuje 32 bity).
Wyniki wyszukiwania
Wynikiem działania programu jest lista K najbardziej podobnych obrazów z bazy danych do obrazu zapytania (obraz może nie pochodzić z bazy danych):
Skuteczność działania struktury indeksu
Dzięki zastosowaniu struktury drzewiastej do przechowywania indeksu, w procesie wyszukiwania zostalo sprawdzone (porównane) 836 z całkowitej liczby 1316 obrazów. Należy zauważyć, że w procesie optymalizacyjnym można wynik ten poprawić. Jednym z pomysłów mogłoby być branie pod uwagę składowych kolorów dominujących, których procentowe wystąpienie jest większe od ustalonego progu.
Ciekawe rozwinięcie projektu
Napisany projekt postanowiłem rozwinąć o możliwość generowania mozaiki. W tym trybie zdjęcie wejściowe dzielone jest na podobszary i dla każdego z poodbszarów znajdowane jest najbardziej odpowiadające zdjęcie z kolekcji obrazów. Dodatkowo kilkanaście obrazów zwróconych w zapytaniu K-NN dla danego podobszaru jest z nim korelowan, by wybrać najbardziej odpowiednie.
Plik wejściowy
Plik wejściowy
Przykład wygenerowanej mozaiki
Przykład wygenerowanej mozaiki


Twój komentarz:
podpis:
e-mail:
komentarz:


Komentarze: