Wykrywanie prawie duplikatów obrazu [zamknięte]

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?

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.

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

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.

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.

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.

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.

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

Pytanie Dobry sposób na identyfikację podobnych obrazów? wydaje się zapewniać rozwiązanie na Twoje pytanie.

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);

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.

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

Na przykład używając rozszerzenia IMMI i IMMI możesz zbadać wiele różnych sposobów mierzenia podobieństwa między obrazami: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension- for-rapidminer-5

Definiując jakiś próg i wybierając jakąś metodę, możesz zmierzyć podobieństwo.