Od Pikseli do Przestrzeni Semantycznych:

Wyszukiwanie Obrazów wg Zawartości

(Content-Based Image Retrieval)

W sierpniu 2006, Nielsen//NetRatings podał, że 5 z 10 najszybciej rosnących dziedzin Web to były tworzone przez użytkowników platformy do udostępniania foto lub wideo oraz blogi

(www.nielsen-netratings.com/pr/PR_060810.PDF).

Wcześniejsze statystyki podawały, że tylko kwietniu 2006 pięć najważniejszych witryn do wymiany zdjęć odwiedziło 34 miliony użytkowników z USA

(http://pic.photobucket.com/press/2006-06-PopPhoto.pdf).

Liczby te ilustrują dobrze znane stwierdzenie dotyczące rewolucji informacyjnej:

wzrasta liczba użytkowników, którzy nie tylko korzystają przygotowanych informacji, ale sami aktywnie tworzą zawartość Web.

Postęp technologiczny w dziedzinie obrazów cyfrowych, szerokopasmowego Internetu oraz pamięci zachęciły miliony zwykłych ludzi do komunikowania się między sobą i prezentowanie się przez wymianę:

zdjęć, wideo i innych rodzajów mediów online.

Jednak pewne możliwości są ciągle niedostępne.

W obszarze wyszukiwania obrazów, gromadzenie, pamiętanie i transmisja zdjęć są obecnie trywialne,

Ale znacznie trudniej jest manipulować, indeksować, sortować, filtrować, podsumowywać lub przeszukiwać je.

Nowoczesne silniki wyszukiwawcze i ich image/video udogodnienia wyszukiwawcze umożliwiły znaczny postęp w przypadku gdy zawartość obrazu posiada tagi z opisem tekstowym

Ale analizują one jedynie metadane, a nie zawartość obrazów, więc są bardzo ograniczone w wielu praktycznych zastosowaniach.

Na przykład możemy użyć jeden z głównych silników do pobrania 17 700 obrazków "dzieci grające w piłkę nożną".

Jednak są one wszystkie bezużyteczne jeśli ja szukam obrazków: my „kids playing soccer”.

Chociaż znajdują się na twardym dysku mojego komputera, pod ręką, to nie są dostępne w żaden zorganizowany sposób.

Mogę oczywiście ręcznie zaindeksować je aby computer mógł wykonać bardziej efektywne wyszukiwanie, ale to dziwny sposób.

Przede wszystkim, to maszyna powinna pracować dla mnie a nie odwrotnie.

Statistical Visual Computing Laboratory na University of California, San Diego (www.svcl.ucsd. edu), zajmuje się problemami wyszukiwania obrazów wg zawartości od wielu lat.

Jednym z celów SVCL jest budowa systemów wyszukujących obrazy w sposób podobny do ludzkiego wyszukiwania.

Prowadząc badania w dziedzinie wizualizacji komputerowej i uczenia maszynowego osiąga wyniki dotyczące reprezentacji obrazów i projektowania systemów inteligentnych:

Ocena podobieństwa obrazów, automatyczne annotacje obrazów za pomocą podpisów, rozumienie sprzężenia zwrotnego w czasie wyszukiwania obrazów przez użytkownika i projektowania struktur indeksów ułatwiających efektywne wyszukiwanie.

Pytanie jako obraz

(QUERY BY VISUAL EXAMPLE - QBVE)

Klasycznym paradygmatem dla content-based image retrieval jest query by visual example.

QBVE wyszukuje obrazy stosując ich dopasowanie oraz tworząc ranking wyszukanych obrazów wg podobieństwa do obrazu-pytania.

System tworzy wzorzec z pytania, porównuje ten wzorzec ze wzorcami obrazów w bazie i zwraca te najbliższe do pytania.

Jest wiele metod tworzenia wzorca obrazu lub oceny ich podobieństwa [1].

Wczesne rozwiązania łącznie z pionierskim systemem query by image kontent [2] bazowały na prostych technikach przetwarzania obrazów takich jak: dopasowywanie histogramów kolorów w obrazach.

Współczesne systemy opierają się na bardziej skomplikowanych reprezentacjach i mają za cel optymalną efektywność wyszukiwania.

Wyszukiwanie z Minimalnym Prawdopodobieństwem Błędu

Minimum Probability of Error (MPE)

Zbudowany w SVCL system wyszukiwania minimalnym prawdopodobieństwem błędu ilustruje tę ewolucję.

Rys. 1. Wyszukiwanie z minimalnym prawdopodobieństwem błędu. (a) Architektura wyszukiwania MPE. System dekomponuje obrazy na grupy lokalnych cech i charakteryzuje je przez ich rozkład w przestrzeni cech. Obrazy z bazy danych są uporządkowane wg prawdopodobieństwa a posteriori wygenerowania cech pytania. (b) Wyniki wyszukiwania. Każda kolumna pokazuje trzy najlepsze dopasowania (spośród 1500) do pytania pokazanego na górze.

Projektując ten system sformułowano problem wyszukiwania jako problem klasyfikacji i zaprojektowano wszystkie składowe system tak, aby osiągnąć optymalność w sensie MPE.

Jak pokazano na rys.1a, system dekomponuje obrazy na grupy cech lokalnych, które mierzą takie właściwości jak tekstura, krawędzie i kolory a następnie uczą Gaussowski Mieszany Model (Gaussian Mixture Model) GMM za pomocą każdej z grup.

Wzorzec obrazu jest więc zwartą reprezentacją probabilistyczną pokazującą jak obraz wygląda w przestrzeni cech.

Po otrzymaniu pytania system pobiera z niego grupę cech i oblicza w jakim stopniu każdy GMM w bazie danych pasuje do tej grupy.

W szczególności system tworzy ranking modeli z bazy danych wg prawdopodobieństwa a posteriori wygenerowania cech pytania.

Można pokazać, że ta procedura jest MPE optymalna [3].

Dodatkowo, aby znaleźć najlepsze dopasowanie, system przypisuje prawdopodobieństwo dopasowania do wszystkich obrazów w bazie danych.

Pozwala to na łączenie wyniku wizualnego dopasowania z innymi źródłami informacji, które mogą wpływać na relewancję każdego obrazu z bazy danych, np.:

Tekst znajdujący się na stronie, jak ten obraz pasował do poprzednich pytań, jak zewnętrzne wydarzenia mogą zwiększyć relewancję pewnych obrazów w pewnych dniach: np.: takie jak wysoki liczba żądań fotografii piłkarskich w niedzielę wieczorem.

Stosując probabilistyczne łączenie informacji, system wyszukiwawczy jest jednocześnie kompatybilny z technikami projektowania systemów inteligentnych.

Jak większość systemów QBVE jest on najbardziej dokładny jeśli podobieństwo wizualne odpowiada podobieństwu ocenianemu przez człowieka [3].

Ilustruje to rys. 1b, który przedstawia najlepsze dopasowania z bazy 1500 obrazów dla trzech pytań.

Baza danych zawiera obrazy różnego typu czyli nie ma określonych ściśle warunków oświetlenia czy ustawienia obiektów itd.

Wszystkie one są jednak dobrej jakości obrazami wykonanymi przez profesjonalnych fotografów.

System identyfikuje różne wizualne atrybuty, które w każdym przypadku są brane pod uwagę przy określaniu podobieństwa obrazów.

Np.: podobny rozkład kolorów wydaje się być decydujący przy dopasowywaniu w pierwszej kolumnie, tekstura odegrała bardziej znaczącą rolę w drugiej kolumnie, a kształt (płatki kwiatów) prawdopodobnie odegrały największą role w trzeciej kolumnie.

Rys. 2. Likwidowanie luki semantycznej. (a) Ludzie często pomijają mocne wizualne powiązania w ocenie podobieństwa co tłumaczy poważne błędy dla metody query-by-visual-example takie, jak wyszukiwanie mostów w odpowiedzi na pytanie "pociąg". (b) Ponieważ dobre dopasowanie wymaga zgodności między różnymi wymiarami w przestrzeni semantycznej to pytania query by semantic example (QBSE) powodują znacznie mniej błędów niż QBVE.

Semantyczna luka

Jest jednak wiele pytań, dla których wizualne podobieństwo nie jest mocno skorelowane z ludzką oceną podobieństwa.

Może to prowadzić do luki semantycznej między człowiekiem i maszyną.

Rys. 2a pokazuje dobry przykład jak ludzie często odrzucają mocne wizualne powiązanie w swoich ocenach podobieństwa.

Pytanie "pociąg" zawiera dominującą strukturę łuku i patrząc ze ściśle wizualnego punktu widzenia jest ono bardzo podobne do konceptów takich jak "most" lub "łuk."

System QBVE będzie zwracał jako najbardziej dopasowane obrazy te cztery pokazane na rysunku - trzy z nich zawierają mosty i struktury podobne do łuków.

Jednak ludzie spodziewają się obrazów pociągu między wynikami wyszukiwania przypisują małe prawdopodobieństwo do alternatywnych interpretacji takich, jak "most" lub "łuk".

Wydaje się, że decydują że obraz przedstawia pociąg i używają "podobieństwo do pociągu" jako wymiar określający podobieństwo obrazów.

Czy inne pociągi są wizualnie podobne do pociągu z pytania - np.: pod względem koloru, kształtu czy rozmiaru - jest niezbyt istotne.

Te różnice w ocenie podobieństwa mogą być bardzo frustrujące dla użytkownika system QBVE.

Większość ludzi nie akceptuje trafień zwróconych na rys.2a pomimo oczywistych podobieństw wizualnych.

ANNOTACJA OBRAZÓW I WYSZUKIWANIE

W ostatnich latach, semantyczna luka między użytkownikiem a maszyną spowodowała znaczne zainteresowanie semantycznym wyszukiwaniem obrazów.

Semantyczny system wyszukiwania ma dwa uzupełniające się cele: annotację obrazów i wyszukiwanie.

Semantyczne etykietowanie

The starting point for a semantic retrieval system is a training databasc of images, each annotared with a nat-ural-language caption. From this database, the system learns to create a mapping between words and visual features. The system then uses this mapping to

• annotate unseen images with thc captions that best
  describe them, and

• find the database images that best satisfy a natural-
  language query.

Usually, the training corpus is weakly labeled, meaning that

• the absence of a label from a caption does not nec-
  essarily mean that the associated visual concept is
  absent from the image, and

• it is not known which image regions are associated
  with each label.

8

---