Wykrywanie prawie zduplikowanego obrazu [zamknięte]

Zalecałbym rozważenie odejścia od używania histogramu RGB.

Lepsze strawienie obrazu można uzyskać, jeśli weźmiesz falkę Haara 2D obrazu (jest o wiele łatwiejsza niż się wydaje ,ma tylko dużo uśredniania i kilka kwadratowych korzeni używanych do ważenia współczynników) i po prostu zachowasz największe współczynniki ważone K w Falce jako rzadki wektor, znormalizujesz go i zachowasz, aby zmniejszyć jego rozmiar. Należy przeskalować R G i B używając wag percepcyjnych wcześniej przynajmniej lub zalecałbym przejście na YIQ (lub YCoCg, aby uniknąć szumu kwantyzacji), aby można było próbkować informacje o chrominancji ze zmniejszonym znaczeniem.

Możesz teraz użyć iloczynu kropkowego dwóch z tych rzadkich znormalizowanych wektorów jako miary podobieństwa. Pary obrazów z największymi produktami dot będą miały bardzo podobną strukturę. Ma to tę zaletę, że jest lekko odporny na zmianę rozmiaru, zmianę barwy i znak wodny, a także jest naprawdę łatwy do wdrożenia i Kompaktowy.

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

Sortowanie według pojedynczego wyniku numerycznego będzie trudne do rozwiązania dla tego rodzaju problemu klasyfikacji. Jeśli się nad tym zastanowić, to wymagałoby to, aby obrazy mogły "zmieniać się" tylko wzdłuż jednej osi, ale tak nie jest. dlatego potrzebny jest wektor funkcji. W przypadku fal Haara to w przybliżeniu miejsce, w którym występują najostrzejsze nieciągłości obrazu. Możesz obliczyć odległość między obrazami parami, ale ponieważ wszystko, co masz, to metryka odległości, kolejność liniowa nie ma sposobu, aby wyrazić "trójkąt" z 3 obrazów, które są równie odległe. (tj. pomyśl o obrazie, który jest cały zielony, obraz, który jest cały czerwony i obraz, który jest cały niebieski.)

Oznacza to, że każde rzeczywiste rozwiązanie twojego problemu będzie wymagało operacji O (N^2) w liczbie posiadanych obrazów. Natomiast gdyby możliwe było linearyzowanie miary, można by wymagać tylko O(n log n), lub O (n), gdyby miara była nadaje się do, powiedzmy, rodzaju radix. To powiedziawszy, nie musisz wydawać O (n^2), ponieważ w praktyce nie musisz przesiać całego zestawu, wystarczy znaleźć rzeczy, które są bliżej niż jakiś próg. Tak więc, stosując jedną z kilku technik, aby podzielić swoją małą przestrzeń wektorową, możesz uzyskać znacznie szybszą asymptotykę dla problemu "znalezienie mnie k obrazów, które są bardziej podobne niż dany próg", niż naiwne porównywanie każdego obrazu z każdym obrazem, dając ci to, co prawdopodobnie potrzeba... jeśli nie dokładnie to, o co prosiłeś.

W każdym razie korzystałem z tego kilka lat temu z dobrym skutkiem osobiście, próbując zminimalizować liczbę różnych tekstur, które przechowywałem, ale było również wiele szumów badawczych w tej przestrzeni pokazujących jego skuteczność (i w tym przypadku porównując go do bardziej wyrafinowanej formy klasyfikacji histogramu): {]}

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

Jeśli potrzebujesz lepszej dokładności w algorytmy minHash i TF-idf mogą być używane z falką Haara (lub histogramem), aby skuteczniej 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 bardziej ekstrakcji funkcji z fal, aby znaleźć obracane lub skalowane sekcje obrazów itp., ale to prawdopodobnie wykracza poza ilość pracy, którą chciałbyś wykonać.

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

Zaimplementowałem bardzo niezawodny algorytm do tego o nazwie Fast Multiresolution Image Querying. Mój (starożytny, niezabezpieczony) kod na to jest Tutaj .

Co szybkie Multiresolution Image Querying robi jest podzielić obraz na 3 części w oparciu o YIQ colorspace (lepiej 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ą przez ten sam proces, a najważniejsze funkcje obrazu zapytania są dopasowywane do tych w przechowywanej bazie danych. Im więcej dopasowań, tym bardziej prawdopodobne, że obrazy są podobne.

Algorytm jest często używany do funkcji "zapytanie przez szkic". Moje oprogramowanie zezwalało tylko na wprowadzanie obrazów zapytań przez URL, więc nie było interfejsu użytkownika. Jednak okazało się, że działa wyjątkowo dobrze, dopasowując miniatury do dużej wersji tego obraz.

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

Obraz ma wiele cech, więc jeśli nie zawęzisz się do jednej, jak średnia jasność, masz do czynienia z N-wymiarową przestrzenią problemową.

Jeśli poprosiłbym 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ą być również w tej samej strefy czasowej, mimo że znajdują się na przeciwległych 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 dla podobieństwa obrazu.

Wszystko to powiedziawszy, istnieją algorytmy, które starają się klasterować podobne obrazy razem, co jest skutecznie to, o co prosisz. Tak się dzieje, gdy wykonujesz detekcję twarzy za pomocą programu Picasa. Nawet zanim zidentyfikujesz jakieś twarze, klastry podobne ze sobą, dzięki czemu łatwo aby przejść przez zestaw podobnych twarzy i dać większości z nich to samo imię.

Istnieje również technika zwana zasadą analizy składowej, która pozwala zredukować dane n-wymiarowe do dowolnej mniejszej liczby wymiarów. Tak więc obraz z N funkcji można zredukować do jednej funkcji. Jednak nadal nie jest to najlepsze podejście do porównywania obrazów.

Istnieje biblioteka C ("libphash" - http://phash.org/) to obliczy "percepcyjny hash" obrazu i pozwoli wykryć podobne obrazy przez porównanie hashów (więc nie musisz porównywać każdego obrazu bezpośrednio z każdym innym obrazem), ale niestety nie wydawało się to zbyt dokładne, kiedy próbowałem go.

Musisz zdecydować, co jest " podobne."Kontrast? Hue?

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

Założę się, że można znaleźć wiele "bliskich połączeń", dzieląc obrazy na kawałki 4x4 i uzyskując średni kolor dla każdej komórki siatki. Miałbyś szesnaście punktów na zdjęcie. Aby ocenić podobieństwo, wystarczy zrobić sumę kwadratów różnic między obrazami.

Nie wydaje mi się, żeby pojedynczy hash miał sens, chyba, że jest przeciwny pojedynczemu pojęciu jak hue, albo jasność lub kontrast.

Oto twój pomysł:

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

Po pierwsze, zakładam, że są to liczby dziesiętne, które są R*(2^16)+G*(2^8)+B, czy coś w tym stylu. Oczywiście nie jest to dobre, ponieważ czerwony jest nadmiernie ważony.

Przeniesienie w Przestrzeń HSV byłoby lepsze. Możesz rozłożyć bity HSV na hash, lub możesz po prostu rozstrzygnąć h, S lub V pojedynczo, lub możesz mieć trzy hasze na obraz.

Jeszcze jeden rzecz. Jeśli masz wagę R, G I B. Waga Zielona najwyższa, a następnie czerwona, a następnie niebieska, aby dopasować ludzką wrażliwość wzrokową.

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

Pytanie Dobry sposób na identyfikację podobnych obrazów? wydaje się być rozwiązaniem dla Twojego pytania.

Założyłem, że inne oprogramowanie do wyszukiwania duplikató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żna porównać dwa obrazy dla 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 wykonanie RMS/RSS porównania na każdej parze zdjęć wymaganych do wykonania sortowania bąbelkowego. Po drugie, możesz wykonać FFT na każdym obrazie i wykonać uśrednianie osi, aby pobrać pojedynczą liczbę całkowitą dla każdego obrazu, której chcesz użyć jako indeksu do sortowania według. Możesz rozważyć wykonanie dowolnego porównania na zmienionym rozmiarze (25%, 10%) wersji oryginału w zależności od tego, jak mała różnica zdecydujesz się zignorować i jak dużo przyspieszenia potrzebujesz. Daj mi znać, jeśli te rozwiązania są interesujące i możemy omówić lub Mogę dostarczyć przykładowy kod.

Większość nowoczesnych metod wykrywania prawie zduplikowanych obrazów wykorzystuje detekcję interesujących punktów i deskryptory opisujące obszar wokół takich punktów. Często stosuje się SIFT . Następnie możesz kwatalizować deskryptory i używać klastrów jako wizualnego słownictwa.

Więc jeśli widzimy na stosunek wspólnych słów wizualnych dwóch obrazów do wszystkich słów wizualnych tych obrazów szacujemy podobieństwo między obrazami. Istnieje wiele ciekawych artykułów. Jednym z nich jest prawie zduplikowany Obraz Detekcja: minHash i waga TF-idf

Na przykład za pomocą IMMI extension i IMMI można zbadać wiele różnych sposobów pomiaru 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żna zmierzyć podobieństwo.