Wykrywanie prawie duplikatów obrazu [zamknięte]


93

Co to jest szybki sposób na sortowanie danego zestawu obrazów według ich podobieństwa do siebie.

W tej chwili mam system, który wykonuje analizę histogramu między dwoma obrazami, ale jest to bardzo kosztowna operacja i wydaje się zbyt przesadna.

Optymalnie szukam algorytmu, który dałby każdemu obrazowi ocenę (na przykład wynik w postaci liczby całkowitej, takiej jak średnia RGB) i mogę po prostu sortować według tego wyniku. Możliwe są identyczne wyniki lub wyniki obok siebie.

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994 

Średnia RGB na obraz jest do niczego, czy jest coś podobnego?


5
Kluczowe pytanie, myśląc o tym, co napisałeś i o niektórych odpowiedziach na powiązane pytanie, które wskazał Naaff, możesz chcieć dokładniej zdefiniować, co oznacza „podobieństwo”. Czy obraz, który jest identyczny, ale przesunięty o pięć pikseli, byłby „podobny”? Wizualnie tak ... ale dla algorytmu ... prawdopodobnie nie, chyba że pomyślałeś o tym i uwzględniłeś to. Czy możesz podać więcej szczegółów? Czy duplikaty byłyby dokładne, czy po prostu „zamknięte”? Czy patrzysz na skany, na których mogą się różnić pod niewielkim kątem? A co z intensywnością? Zmiennych jest tu dużo ...
Beska

Czym różnią się „duplikaty”? np. czy byłyby to obrazy tego samego miejsca z różnymi pozami / przesunięciem? Wydaje się, że chcesz czegoś, co jest O (nlog (n)) z liczbą obrazów. Czy ktoś wie, czy to jest możliwe? Wygląda na to, że może być ...
Justin Scheiner

@ The Unknown: Jeśli nie jesteś zadowolony z żadnej z obecnych odpowiedzi, czy możesz udzielić nam dodatkowych wskazówek? Zrobiliśmy co w naszej mocy, aby odpowiedzieć na Twoje pytanie, ale bez opinii jest mało prawdopodobne, aby wymyślili coś lepszego.
Naaff

Jest to obecnie jeden z największych nierozwiązanych problemów w informatyce. Powodzenia kolego.
john ktejik

Odpowiedzi:


70

Przeprowadzono wiele badań dotyczących wyszukiwania obrazów i miar podobieństwa. To nie jest łatwy problem. Ogólnie rzecz biorąc, pojedynczy pojedynczy intnie wystarczy, aby określić, czy obrazy są bardzo podobne. Będziesz mieć wysoki odsetek wyników fałszywie dodatnich.

Ponieważ jednak przeprowadzono wiele badań, możesz rzucić okiem na niektóre z nich. Na przykład ten artykuł (PDF) zawiera kompaktowy algorytm pobierania odcisków palców obrazu, który jest odpowiedni do szybkiego wyszukiwania duplikatów obrazów bez przechowywania dużej ilości danych. Wygląda na to, że jest to właściwe podejście, jeśli chcesz czegoś solidnego.

Jeśli szukasz czegoś prostszego, ale zdecydowanie bardziej ad-hoc, to pytanie SO ma kilka przyzwoitych pomysłów.


3
ten artykuł pochodzi z 2004 roku, nie jesteś pewien, czy to nadal jest najlepsza odpowiedź?
Andrew,

50

Zalecałbym rozważenie odejścia od zwykłego korzystania z histogramu RGB.

Lepsze podsumowanie obrazu można uzyskać, jeśli weźmiesz falkę 2d Haar obrazu (jest o wiele łatwiejsza niż się wydaje, jest po prostu dużo uśredniania i kilka pierwiastków kwadratowych używanych do ważenia współczynników) i po prostu zachowasz k największych ważone współczynniki w falce jako rzadkim wektorze, znormalizuj go i zapisz, aby zmniejszyć jego rozmiar. Powinieneś przeskalować RG i B, używając przynajmniej wag percepcyjnych, lub zaleciłbym przejście na YIQ (lub YCoCg, aby uniknąć szumu kwantyzacji), abyś mógł próbkować informacje o chrominancji o mniejszym znaczeniu.

Możesz teraz użyć iloczynu skalarnego dwóch z tych rzadkich znormalizowanych wektorów jako miary podobieństwa. Pary obrazów z największymi iloczynami skalarnymi będą miały bardzo podobną strukturę. Ma to tę zaletę, że jest nieco odporny na zmianę rozmiaru, zmianę odcienia i znaki wodne, a także jest naprawdę łatwy do wdrożenia i kompaktowy.

Możesz wymienić miejsce na przechowywanie i dokładność, zwiększając lub zmniejszając k.

Sortowanie według pojedynczego wyniku liczbowego będzie trudne do rozwiązania tego rodzaju problemu klasyfikacyjnego. Jeśli się nad tym zastanowić, wymagałoby to, aby obrazy mogły „zmieniać się” tylko wzdłuż jednej osi, ale tak się nie dzieje. Dlatego potrzebujesz wektora funkcji. W przypadku falki Haara jest to mniej więcej miejsce, w którym występują najostrzejsze nieciągłości obrazu. Możesz obliczyć odległość między obrazami parami, ale ponieważ jedyne, co masz, to metryka odległości, uporządkowanie liniowe nie ma możliwości wyrażenia „trójkąta” trzech obrazów, które są jednakowo oddalone. (tj. pomyśl o obrazie, który jest cały zielony, obrazie, który jest cały czerwony i obraz, który jest cały niebieski).

Oznacza to, że każde rzeczywiste rozwiązanie problemu będzie wymagało operacji O (n ^ 2) na liczbie posiadanych obrazów. Gdyby jednak można było zlinearyzować miarę, można by wymagać tylko O ​​(n log n) lub O (n), jeśli miara nadaje się, powiedzmy, do sortowania metodą radix. To powiedziawszy, nie musisz wydawać O (n ^ 2), ponieważ w praktyce nie musisz przeszukiwać całego zestawu, wystarczy znaleźć rzeczy, które są bliżej niż jakiś próg. Tak więc, stosując jedną z kilku technik podziału rzadkiej przestrzeni wektorowej, można uzyskać znacznie szybsze asymptotyki dla problemu `` znajdowania obrazów, które są bardziej podobne niż dany próg '', niż naiwne porównywanie każdego obrazu z każdym obrazem, co daje prawdopodobnie potrzebujesz ... jeśli nie dokładnie tego, o co prosiłeś.

W każdym razie użyłem tego kilka lat temu z dobrym skutkiem osobiście, próbując zminimalizować liczbę różnych tekstur, które przechowywałem, ale w tej przestrzeni było też dużo szumu badawczego pokazującego jego skuteczność (w tym przypadku porównując do bardziej wyrafinowanej formy klasyfikacji histogramu):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Jeśli potrzebujesz większej dokładności w wykrywaniu, algorytmy minHash i tf-idf mogą być używane z falką Haara (lub histogramem), aby lepiej radzić sobie z edycjami:

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

Wreszcie, Stanford ma wyszukiwanie obrazów oparte na bardziej egzotycznym wariancie tego rodzaju podejścia, opartym na robieniu większej ilości ekstrakcji cech z falek w celu znalezienia obróconych lub skalowanych sekcji obrazów itp., Ale to prawdopodobnie wykracza daleko poza ilość pracy, którą chciałbym zrobić.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi


Wygląda na to, że pośrednio opisujesz drzewa kd i tym podobne do wyszukiwania przestrzeni dla potencjalnych kandydatów. Warto to zauważyć.
Boojum

1
Cóż, powodem, dla którego nie określiłem technik poza niejasną aluzją, jest to, że drzewa kd działają dobrze, gdy masz stosunkowo niewielką liczbę wymiarów w swojej przestrzeni. Tutaj prawdopodobnie masz ~ 128 lub więcej wymiarów, które są rzadko wypełnione. Ponieważ są one rzadkie, większość wartości będzie równa zero, więc okrężne przechodzenie przez wymiary w celu podziału na kd jest właściwie prawie bezużyteczne. Z tego samego powodu rozpadają się R-drzewa, pozostawiając najprawdopodobniej najlepszy zakład: X-drzewa. Niestety, zbliżają się one również do granicy swoich osiągów w obliczu tak wielu wymiarów.
Edward KMETT

„i po prostu zachować k największych ważonych współczynników w falce jako rzadki wektor” - zachować dla każdego rzędu lub dla całej falki?
ivan.ukr

„Powinieneś przeskalować RG i B przy użyciu wag percepcyjnych przynajmniej wcześniej lub poleciłbym przejście na YIQ (lub YCoCg, aby uniknąć szumu kwantyzacji), abyś mógł próbkować informacje o chrominancji o mniejszym znaczeniu”. - I co potem? Czy wavelet jest tylko dla Y, czy dla wszystkich kanałów? Jeśli tak dla wszystkich kanałów - jak zmierzyć podobieństwo obrazów z wieloma kanałami? dodać iloczyn skalarny każdego kanału i uznać to za miarę podobieństwa, czy też powinien to być dodatek ważony?
ivan.ukr

15

Zaimplementowałem bardzo niezawodny algorytm o nazwie Fast Multiresolution Image Querying . Mój (starożytny, nieużywany) kod do tego jest tutaj .

To, co robi Fast Multiresolution Image Querying, to podzielenie obrazu na 3 części w oparciu o przestrzeń kolorów YIQ (lepsze dla dopasowania różnic niż RGB). Następnie obraz jest zasadniczo kompresowany za pomocą algorytmu falkowego, aż dostępne są tylko najbardziej widoczne cechy z każdej przestrzeni kolorów. Punkty te są przechowywane w strukturze danych. Obrazy zapytań przechodzą ten sam proces, a najważniejsze funkcje obrazu zapytania są dopasowywane do tych w przechowywanej bazie danych. Im więcej dopasowań, tym większe prawdopodobieństwo, że obrazy są podobne.

Algorytm jest często używany do funkcji „zapytania przez szkic”. Moje oprogramowanie pozwalało tylko na wprowadzanie obrazów zapytań za pośrednictwem adresu URL, więc nie było interfejsu użytkownika. Jednak okazało się, że działa to wyjątkowo dobrze w przypadku dopasowywania miniatur do dużej wersji tego obrazu.

O wiele bardziej imponujący niż moje oprogramowanie jest retrievr, który pozwala wypróbować algorytm FMIQ przy użyciu obrazów Flickr jako źródła. Bardzo fajny! Wypróbuj za pomocą szkicu lub używając obrazu źródłowego, a zobaczysz, jak dobrze to działa.


Czy nadal może rozpoznawać obrócone obrazy?
endolit

Wątpię, żeby to zadziałało bardzo dobrze. Prawdopodobnie chciałbyś zakodować obrazy dla każdego obrotu, aby zmaksymalizować trafne dopasowania.
Luke Francl

Wydaje się, że łącze do pobierania plików jest wyłączone - czy to jest gdzieś zarchiwizowane?
mmigdol

10

Obraz ma wiele cech, więc jeśli nie ograniczysz się do jednej, na przykład do średniej jasności, masz do czynienia z n-wymiarową przestrzenią problemową.

Gdybym poprosił cię o przypisanie jednej liczby całkowitej do miast na świecie, abym mógł stwierdzić, które z nich są blisko, wyniki nie byłyby świetne. Możesz na przykład wybrać strefę czasową jako pojedynczą liczbę całkowitą i uzyskać dobre wyniki w niektórych miastach. Jednak miasto w pobliżu bieguna północnego i inne miasto w pobliżu bieguna południowego mogą również znajdować się w tej samej strefie czasowej, mimo że znajdują się na przeciwnych krańcach planety. Jeśli pozwolę ci użyć dwóch liczb całkowitych, możesz uzyskać bardzo dobre wyniki z szerokością i długością geograficzną. Problem jest taki sam w przypadku podobieństwa obrazu.

Wszystko to powiedziawszy, istnieją algorytmy, które próbują grupować podobne obrazy razem, o co właściwie prosisz. Tak dzieje się, gdy wykrywasz twarze w programie Picasa. Jeszcze zanim zidentyfikujesz jakiekolwiek twarze, grupuje podobne twarze razem, dzięki czemu łatwo jest przejść przez zestaw podobnych twarzy i nadać większości z nich to samo imię.

Istnieje również technika zwana analizą podstawowych komponentów, która pozwala zredukować dane n-wymiarowe do dowolnej mniejszej liczby wymiarów. Zatem obraz z n cechami można zredukować do jednej cechy. Jednak nadal nie jest to najlepsze podejście do porównywania obrazów.


1
To kwestia sporna, ale MOŻESZ użyć jednej liczby całkowitej do reprezentowania kombinacji dowolnej liczby cech, jeśli na przykład cecha x = 2 i cecha y = 3 oraz cecha z = 5 i cecha aa = 7 i tak dalej, wtedy potęga, do której ta podstawa pierwsza została podniesiona w postaci faktoryzowanej pojedynczej liczby całkowitej, byłaby wartością cechy dla tego konkretnego obrazu. Znowu kwestia dyskusyjna, ponieważ wielkość liczby byłaby absurdalna. Chociaż ten rozmiar można jeszcze bardziej zmniejszyć ... mówimy tylko o danych strukturalnych.
argyle

Prawdziwe. Ale prawdziwym celem jest takie ułożenie liczb, aby podobne obrazy były zbliżone liczbowo. Wbrew temu, co powiedziałem powyżej, jest to możliwe. Krótko mówiąc, możesz rozwiązać problem podróżującego sprzedawcy, aby znaleźć minimalną (lub prawie minimalną) ścieżkę przez obrazy w przestrzeni n-wymiarowej (gdzie n to liczba funkcji, których chcesz użyć do porównania obrazów). Ale to jest drogie.
Neil

8

Istnieje biblioteka C („libphash” - http://phash.org/ ), która oblicza „percepcyjny hash” obrazu i pozwala wykryć podobne obrazy przez porównanie skrótów (więc nie musisz porównywać każdego obrazu bezpośrednio na każdym innym obrazie), ale niestety nie wydawało się to zbyt dokładne, gdy go wypróbowałem.


5

Musisz zdecydować, co jest „podobne”. Kontrast? Odcień?

Czy obraz jest „podobny” do tego samego obrazu do góry nogami?

Założę się, że można znaleźć wiele „bliskich rozmów”, dzieląc obrazy na części 4x4 i uzyskując średni kolor dla każdej komórki siatki. Otrzymasz szesnaście punktów za obraz. Aby ocenić podobieństwo, wystarczy zrobić sumę kwadratów różnic między obrazami.

Nie sądzę, aby pojedynczy hash miał sens, chyba że jest sprzeczny z pojedynczą koncepcją, taką jak odcień, jasność lub kontrast.

Oto twój pomysł:

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

Przede wszystkim zakładam, że są to liczby dziesiętne R * (2 ^ 16) + G * (2 ^ 8) + B lub coś w tym rodzaju. Oczywiście to nie jest dobre, ponieważ kolor czerwony jest nadmiernie obciążony.

Przeniesienie się w przestrzeń HSV byłoby lepsze. Możesz rozłożyć bity HSV na hash, możesz po prostu ustawić H, S lub V indywidualnie, lub możesz mieć trzy hashe na obraz.


Jeszcze jedna rzecz. Jeśli ważysz R, G i B. Waga najwyższa jest na zielono, następnie na czerwono, a następnie na niebiesko, aby dopasować się do ludzkiej wrażliwości wzrokowej.


5

W dobie serwisów internetowych możesz spróbować http://tineye.com


3
Wydaje się, że kod kryjący się za tineye jest dokładnie tym, o co chodzi pytającemu, ale nie sądzę, aby jako usługa internetowa była bardzo użyteczna, ponieważ nie ma (oczywistego) sposobu, aby nadać mu dwa obrazy i zapytać „czy to to samo? " - drugie zdjęcie musiało być na stronie internetowej i indeksowane przez tineye
dbr

1
Może udostępniają API dla użytkowników biznesowych? Należy się z nimi skontaktować w tej sprawie.
zproxy

Istnieje komercyjny interfejs API, który zapewnia dokładnie to services.tineye.com/MatchEngine .
Gajus,


1

Założyłem, że inne oprogramowanie do wyszukiwania zduplikowanych obrazów wykonuje FFT na obrazach i przechowuje wartości różnych częstotliwości jako wektory:

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

a następnie możesz porównać dwa obrazy pod kątem równości , obliczając odległość między wektorami wagi dwóch obrazów:

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

2
Większość obrazów naturalnych ma bardzo podobną zawartość częstotliwości, więc wątpię, czy byłaby to bardzo dobra miara.
Hannes Ovrén

1

Jednym z rozwiązań jest porównanie RMS / RSS dla każdej pary obrazów potrzebnych do sortowania bąbelkowego. Po drugie, możesz wykonać FFT na każdym obrazie i uśrednić trochę osi, aby pobrać jedną liczbę całkowitą dla każdego obrazu, której użyjesz jako indeksu do sortowania. Możesz rozważyć zrobienie dowolnego porównania na wersji oryginału o zmienionym rozmiarze (25%, 10%) w zależności od tego, jak niewielka różnica zdecydujesz się zignorować i jakiego przyspieszenia potrzebujesz. Daj mi znać, jeśli te rozwiązania są interesujące, a możemy omówić lub podać przykładowy kod.


FFT zapewnia jedynie informacje o kolorze, a nie informacje o pozycji. Zmiana rozmiaru ignoruje wszystkie elementy poniżej określonego rozmiaru, niezależnie od wpływu na wynikowy obraz. Pod tym środkiem szary obraz i szachownica mogą być identyczne. Podejście falkowe (Daubechies, Haar itp.) Ma tę zaletę, że dostarcza zarówno informacji o pozycji, jak i kolorze, wymieniając proporcje informacji o położeniu i kolorze w każdym punkcie danych.
Edward KMETT

2
Nie, FFT obrazu zawiera wszystkie informacje przestrzenne oryginału. Możesz zrekonstruować oryginał z FFT. homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm Jednak histogram, który może być tym, o czym myślałeś, nie.
Paul,

1

Większość nowoczesnych podejść do wykrywania wykrywania prawie duplikatów obrazu wykorzystuje wykrywanie interesujących punktów i deskryptory opisujące obszar wokół takich punktów. Często używany jest SIFT . Następnie możesz quatizować deskryptory i używać klastrów jako wizualnego słownictwa słów.

Więc jeśli widzimy stosunek wspólnych wizualnych słów dwóch obrazów do wszystkich wizualnych słów tych obrazów, oszacujesz podobieństwo między obrazami. Jest wiele interesujących artykułów. Jednym z nich jest wykrywanie bliskiego duplikatu obrazu: minHash i tf-idf Weighting


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.