Jakiego algorytmu używa Google w swojej witrynie „Wyszukaj według obrazu”?

Jak najlepiej zgadnąć, jak działa Wyszukiwarka grafiki Google? Mogę przesłać zdjęcie i wyszukiwać podobne obrazy. Jakiego algorytmu używa do identyfikacji podobnych obrazów?

Nie wiem, jakiego algorytmu używa Google. Ale skoro chciałeś zgadnąć, pozwól, że przedstawię kilka pomysłów na to, jak można zbudować podobny system .

Całe pole zajmujące się wyszukiwaniem-obraz-baza-po-obrazku nosi nazwę Content Based Image Retrieval (CBIR) . Chodzi o to, aby w jakiś sposób zbudować reprezentację obrazu (niekoniecznie zrozumiałą dla ludzi), która zawiera informacje o treści obrazu .

Istnieją dwa podstawowe podejścia:

• wyszukiwanie przy użyciu funkcji niskiego poziomu (lokalnych): koloru, tekstury, kształtu w określonych częściach obrazów (obraz jest zbiorem deskryptorów funkcji lokalnych )
• podejścia semantyczne, w których obraz jest w pewien sposób reprezentowany jako zbiór przedmiotów i ich relacji

Lokalne podejście na niskim poziomie jest bardzo dobrze zbadane. Najlepsze obecne podejście wyodrębnia funkcje lokalne (istnieje tu wybór algorytmu wyodrębniania funkcji) i używa ich lokalnych deskryptorów (ponownie wybór deskryptorów) do porównywania obrazów.

W nowszych pracach lokalne deskryptory są najpierw grupowane, a następnie klastry traktowane jako słowa wizualne - technika jest wówczas bardzo podobna do wyszukiwania dokumentów Google, ale używa słów wizualnych zamiast słów literowych.

Możesz myśleć o słowach wizualnych jako odpowiednikach wyrazów w języku: na przykład słowa: praca, praca, przepracowane należą do tego samego słowa root.

Jedną z wad tego rodzaju metod jest to, że zwykle działają one słabo na obrazach o niskiej teksturze.

Dałem już i widziałem wiele odpowiedzi szczegółowo opisujących te podejścia, więc podam tylko linki do tych odpowiedzi:

• CBIR: 1 , 2
• ekstrakcja / opis funkcji: 1 , 2 , 3 , 4

Podejścia semantyczne są zazwyczaj oparte na hierarchicznych reprezentacjach całego obrazu. Te podejścia nie zostały jeszcze udoskonalone, szczególnie w przypadku ogólnych typów obrazów. Odnoszenie sukcesów w stosowaniu tego rodzaju technik do określonych domen obrazów.

Ponieważ obecnie prowadzę badania nad tymi podejściami, nie mogę wyciągać żadnych wniosków. To powiedziawszy, wyjaśniłem w tej odpowiedzi ogólny pogląd na te techniki .

Jeszcze raz, krótko: ogólną ideą jest przedstawienie obrazu ze strukturą w kształcie drzewa, gdzie liście zawierają szczegóły obrazu, a obiekty można znaleźć w węzłach bliżej korzenia takich drzew. Następnie w jakiś sposób porównujesz poddrzewa, aby zidentyfikować obiekty zawarte na różnych obrazach.

Oto kilka odniesień do różnych reprezentacji drzew. Nie przeczytałem ich wszystkich, a niektóre z nich używają tego rodzaju reprezentacji do segmentacji zamiast CBIR, ale nadal są:

• drzewa partycji binarnych i wzmianka o drzewach min / max: P. Salembier, MHF Wilkinson: Connected Operators
• drzewa partycji binarnych: V. Vilaplana, F. Marques, P. Selembier: Drzewa partycji binarnych do wykrywania obiektów
• drzewo kształtów (drzewo składowe): P. Monasse, F. Guichard: Szybkie obliczanie reprezentacji obrazu niezmiennie kontrastowego , C. Ballester, V. Castellis, P. Monasse: Drzewo kształtów obrazu
• drzewa monotoniczne: Y. Song, A. Zhang: Analiza obrazów scenerii za pomocą drzewa monotonicznego
• edycja: dalsze kopanie pokazuje, że drzewo kształtów i drzewo monotoniczne są równoważne , z wyjątkiem przetwarzania obrazu w 4- / 8- (drzewo kształtów) lub 6-łączność (monotoniczny)
• drzewo z ekstremalnym przełomem: A. Vichik, R. Keshet, D. Malah: Morfologia podwójna na półkulach i zastosowaniach drzew
• ograniczona łączność, drzewa alfa, ultradźwiękowe sadzawki wodne: P. Soille, L. Najman: O morfologicznych reprezentacjach hierarchicznych do przetwarzania obrazów i grupowania danych przestrzennych

Oprócz odpowiedzi na penelope istnieją dwa podejścia: percepcyjne mieszanie i model worka słów, których podstawową funkcjonalność można łatwo zaimplementować i dlatego można z nimi grać lub uczyć się przed wyruszeniem na bardziej zaawansowane terytorium.

Mieszanie percepcyjne

Algorytmy haszowania percepcyjnego mają na celu zbudowanie skrótu, który w przeciwieństwie do skrótu kryptograficznego da podobne lub prawie podobne wartości skrótu dla identycznych obrazów, które zostały nieco zniekształcone, na przykład przez skalowanie lub kompresję JPEG. Służą one pożytecznemu celowi do wykrywania w pobliżu duplikatów w kolekcji obrazów.

W najbardziej podstawowej formie możesz to zaimplementować w następujący sposób:

1. Konwertuj obraz na skalę szarości

2. Uczyń swój obraz zerowym

3. Zmiażdż obraz do rozmiaru miniatury, powiedz [32x32]
4. Uruchom dwuwymiarową dyskretną transformację kosinusową
5. Trzymaj lewy górny róg [8 x 8], najbardziej znaczące komponenty niskiej częstotliwości
6. Binaryzuj blok na podstawie znaku komponentów

Wynikiem jest sprężysty, 64-bitowy skrót, ponieważ jest on oparty na komponentach obrazu o niskiej częstotliwości. Wariantem tego tematu byłoby podzielenie każdego obrazu na 64 podbloki i porównanie globalnej średniej obrazu z lokalną średnią podbloku i wypisanie odpowiednio 1 lub 0.

Hashowanie percepcyjne jest implementowane na przykład przez phash

Model worka słów

Model worka słów ma na celu semantyczną identyfikację obrazu, np. Wszystkich obrazów z psami. Robi to, używając pewnych poprawek graficznych w tym samym duchu, w którym klasyfikuje się dokument tekstowy na podstawie występowania określonych słów. Można kategoryzować słowa, powiedzieć „pies” i „psy” i przechowywać je jako identyfikator w odwróconym pliku, w którym kategoria „pies” wskazuje teraz na wszystkie dokumenty zawierające albo „pies”, albo „psy”.

W najprostszej formie można to zrobić z obrazami w następujący sposób:

1. Wdróż tak zwane funkcje SIFT, na przykład za pomocą doskonałej biblioteki vlfeat , która wykryje punkty funkcji SIFT i deskryptor SIFT na punkt. Ten deskryptor jest w zasadzie inteligentnie skonstruowanym szablonem łatki obrazu otaczającej ten punkt funkcji. Te deskryptory to twoje surowe słowa.
2. Zbierz deskryptory SIFT dla wszystkich odpowiednich obrazów

Masz teraz ogromną kolekcję deskryptorów SIFT. Problem polega na tym, że nawet z prawie identycznych obrazów, będzie pewne niedopasowanie między deskryptorami. Chcesz zgrupować identyczne, mniej więcej tak, jakby traktować niektóre słowa jako „pies” i „psy” jako identyczne i musisz zrekompensować błędy. Tutaj właśnie pojawia się klastrowanie.

1. Weź wszystkie deskryptory SIFT i zgrupuj je, na przykład za pomocą algorytmu typu k-średnich. To znajdzie wcześniej określoną liczbę klastrów z centroidami w danych deskryptora. Te centroidy to twoje nowe wizualne słowa.
2. Teraz dla każdego obrazu i jego oryginalnych znalezionych deskryptorów możesz zobaczyć klastry, do których przypisano te deskryptory. Dzięki temu wiesz, które centroidy lub słowa wizualne „należą” do twojego obrazu. Te centroidy lub słowa wizualne stają się nowym semantycznym deskryptorem obrazu, który można przechowywać w odwróconym pliku.

Zapytanie graficzne, np. Znajdź mi podobne obrazy do zapytania-obrazu, jest następnie rozwiązywane w następujący sposób:

1. Znajdź punkty SIFT i ich deskryptory na obrazie zapytania
2. Przypisz deskryptory zapytań do centroidów znalezionych wcześniej w fazie rejestracji. Masz teraz zestaw centroidów lub słów wizualnych, które dotyczą obrazu zapytania
3. Dopasuj wizualne słowa zapytania do wizualnych słów w odwróconym pliku i zwróć pasujące obrazy

Innym interesującym podejściem, które wydaje się być zaniedbywane w powyższych odpowiedziach, są Deep Convolutional Neural Networks. Wygląda na to, że Google używa go teraz do wyszukiwania obrazów i usługi tłumaczenia . CNN są niezwykle potężne w zadaniach poznawczych, takich jak znajdowanie podobieństwa. Wydaje się, że CNN przeprowadza podobną procedurę Bag-of-worlds, która jest osadzona w jej warstwach sieciowych. Minusem tych technik jest niemożność oduczenia się i wymagania ogromnego zestawu danych do szkolenia oraz oczywiście duże koszty obliczeniowe na etapie szkolenia.

Sugerowany artykuł na ten temat:

• Głębokie uczenie się dla podobieństwa semantycznego
• Uczenie się drobnoziarnistego podobieństwa obrazu z głębokim rankingiem

i implementacja pobierania obrazów w głębokim uczeniu typu open source (późniejszy artykuł): https://github.com/paucarre/tiefvision