Porównanie obrazów-szybki algorytm

Najlepszą metodą, jaką znam, jest użycie haszu percepcyjnego. Wydaje się, że istnieje dobra implementacja open source takiego hasha dostępna pod adresem:

Http://phash.org/

Główną ideą jest to, że każdy obraz jest zredukowany do małego kodu skrótu lub "odcisku palca" poprzez identyfikację najważniejszych cech w oryginalnym pliku obrazu i haszowanie zwartej reprezentacji tych cech (zamiast haszowania danych obrazu bezpośrednio). Oznacza to, że wskaźnik fałszywych alarmów jest znacznie zmniejszono za pomocą uproszczonego podejścia, takiego jak redukcja obrazów do obrazu o małym rozmiarze i porównywanie odcisków kciuka.

Phash oferuje kilka rodzajów skrótu i może być używany do obrazów, audio lub wideo.

Ten post był punktem wyjścia mojego rozwiązania, wiele dobrych pomysłów tutaj, więc pomyślałem, że podzielę się moimi wynikami. Głównym wglądem jest to, że znalazłem sposób, aby obejść powolność dopasowania obrazu opartego na punktach kluczowych, wykorzystując szybkość phash.

Dla ogólnego rozwiązania, najlepiej zastosować kilka strategii. Każdy algorytm najlepiej nadaje się do pewnych typów transformacji obrazu i można z tego skorzystać.

Na górze najszybsze algorytmy; na dole najwolniejszy (choć dokładniejszy). Możesz pominąć te powolne, jeśli dobry mecz zostanie znaleziony na szybszym poziomie.

• plik-hash oparty (md5, sha1, itp.) dla dokładnych duplikatów
• perceptual hashing (phash) dla przeskalowanych obrazów
• feature-based (SIFT) for modified images

Mam bardzo dobre wyniki z phash. Dokładność jest dobra dla przeskalowanych obrazów. Nie jest to dobre dla (percepcyjnie) zmodyfikowanych obrazów (przyciętych, obróconych, lustrzanych, itp.). Aby poradzić sobie z szybkością haszowania, musimy użyć pamięci podręcznej dysku/bazy danych, aby utrzymać hasze dla stogu siana.

Naprawdę fajną rzeczą w phash jest to, że po zbudowaniu bazy danych hash (która dla mnie wynosi około 1000 zdjęć / sek), wyszukiwanie może być bardzo, bardzo szybkie, w szczególności, gdy można trzymać całą bazę danych hash w pamięci. Jest to dość praktyczne, ponieważ hash wynosi tylko 8 bajtów.

Na przykład, jeśli masz 1 milion obrazów, wymagałoby to tablicy 1 miliona 64-bitowe wartości skrótu (8 MB). Na niektórych procesorach mieści się to w pamięci podręcznej L2 / L3! W praktycznym użyciu widziałem porównanie corei7 z ponad 1 Giga-hamm/s, to tylko kwestia przepustowości PAMIĘCI do procesora. Baza danych o wielkości 1 miliarda obrazów jest praktyczna na 64-bitowym procesorze (potrzebny 8GB RAM) i wyszukiwanie nie przekroczy 1 sekundy!

Dla zmodyfikowanych / przyciętych obrazów wydaje się, że transformator-niezmienny detektor funkcji/punktów kluczowych, jak SIFT, jest drogą do zrobienia. SIFT będzie produkować dobre klawiatury, które wykryją przycinanie/obracanie / lustro itp. Jednak porównywanie deskryptorów jest bardzo powolne w porównaniu z odległością Hamminga używaną przez phash. Jest to poważne ograniczenie. Istnieje wiele porównań do wykonania, ponieważ istnieje maksymalny deskryptor IxJxK porównujący jeden obraz (i=liczba obrazów stogów siana, J=docelowe punkty na obraz stogów siana, K = docelowe punkty na obraz igły).

Aby obejść problem z prędkością, próbowałem użyć phash wokół każdego znalezionego punktu kluczowego, używając rozmiaru funkcji/promienia do określenia podprostka. Sztuczka, aby to działa dobrze, jest zwiększenie / zmniejszenie promienia, aby wygenerować różne poziomy sub-rect (na obrazie igły). Zazwyczaj pierwszy poziom (bez szwu) będzie pasować, jednak często zajmuje to kilka więcej. Nie jestem w 100% pewien, dlaczego to działa, ale mogę sobie wyobrazić, że umożliwia funkcje, które są zbyt małe, aby phash działał (phash skaluje obrazy do 32x32).

Kolejną kwestią jest to, że SIFT nie rozdzieli optymalnie punktów klawiszowych. Jeśli istnieje sekcja obrazu z wieloma krawędziami, punkty kluczowe skupią się tam i nie otrzymasz żadnych w innym obszarze. Używam GridAdaptedFeatureDetector w OpenCV, aby poprawić dystrybucję. Nie wiem, jaki rozmiar siatki jest najlepszy, używam małej siatki (1x3 lub 3x1 w zależności od orientacji obrazu).

Prawdopodobnie chcesz przeskalować wszystkie obrazy stogów siana (i igły) do mniejszych rozmiarów przed wykryciem funkcji (używam 210px wzdłuż maksymalnego wymiaru). Zmniejszy to szum w obrazie (zawsze problem dla algorytmów widzenia komputerowego), również skupi detektor na bardziej znanych cechach.

W przypadku obrazów osób można spróbować wykryć twarz i użyć jej do określenia rozmiaru obrazu do skalowania i rozmiaru siatki (na przykład największa twarz skalowana do 100px). Detektor funkcji uwzględnia wiele poziomów skali (za pomocą piramid), ale istnieje ograniczenie do tego, ile poziomów będzie używał (jest to oczywiście dostrajalne).

Wykrywacz punktów kluczowych działa prawdopodobnie najlepiej, gdy zwraca mniej niż liczba funkcji chciałeś. Na przykład, jeśli poprosisz o 400 i otrzymasz 300 z powrotem, to dobrze. Jeśli otrzymasz 400 za każdym razem, prawdopodobnie niektóre dobre funkcje musiały zostać pominięte.

Obraz igły może mieć mniej punktów klawiszowych niż obrazy stogów siana i nadal uzyskać dobre wyniki. Dodanie więcej nie musi ci ogromne zyski, na przykład z J = 400 I K = 40 mój wskaźnik trafień jest o 92%. Przy J = 400 i K = 400 wskaźnik trafień wzrasta tylko do 96%.

Możemy wykorzystać ekstremalną prędkość Hamminga funkcja rozwiązywania skalowania, obracania, dublowania itp. Można zastosować technikę wielokrotnego przejścia. Przy każdej iteracji przekształć pod-prostokąty, Zmień hash i ponownie uruchom funkcję wyszukiwania.

Mam pomysł, który może zadziałać i najprawdopodobniej będzie bardzo szybki. Możesz poddawać próbce obraz o rozdzielczości 80x60 lub porównywalnej, i przekonwertować na skalę szarości(po podpróbkowaniu będzie szybciej). Przetwarzaj oba obrazy, które chcesz porównać. Następnie uruchom znormalizowaną sumę kwadratowych różnic między dwoma obrazami (obraz zapytania i każdy z db), lub jeszcze lepiej znormalizowaną korelację krzyżową, co daje odpowiedź bliższą 1, jeśli oba obrazy są podobne. Następnie, jeśli obrazy są podobne, możesz przejdź do bardziej wyrafinowanych technik aby sprawdzić, czy są to te same obrazy. Oczywiście algorytm ten jest liniowy pod względem liczby obrazów w bazie danych więc nawet jeśli będzie to bardzo szybkie do 10000 obrazów na sekundę na nowoczesnym sprzęcie. Jeśli potrzebujesz niezmienniczości do obrotu, to można obliczyć gradient dominujący dla tego małego obrazu, a następnie cały układ współrzędnych może być obrócony do kanonicznego orientacja będzie jednak wolniejsza. I nie, nie ma niezmienności dla skaluj tutaj.

Jeśli chcesz czegoś bardziej ogólnego lub korzystania z dużych baz danych( milionów zdjęć), to musisz przyjrzeć się teorii pobierania obrazów (mnóstwo prac pojawiło się w ciągu ostatnich 5 lat). Istnieją pewne wskazówki w innych odpowiedziach. Ale to może być przesada, a sugerowane podejście histogramu załatwi sprawę. Chociaż myślę, że połączenie wielu różnych szybkie podejścia będą jeszcze lepsze.

Jak zauważył cartman, możesz użyć dowolnego rodzaju wartości skrótu do znalezienia dokładnych duplikatów.

Punktem wyjścia do znalezienia bliskich obrazów może być TUTAJ . Jest to narzędzie używane przez firmy CG do sprawdzania, czy odświeżone obrazy nadal pokazują zasadniczo tę samą scenę.

Uważam, że zmniejszenie rozmiaru obrazu do prawie rozmiaru ikony, powiedzmy 48x48, a następnie konwersja do skali szarości, a następnie wzięcie różnicy między pikselami, lub Delta, powinno działać dobrze. Ponieważ porównujemy zmianę koloru pikseli, a nie rzeczywisty kolor pikseli, nie ma znaczenia, czy obraz jest nieco jaśniejszy czy ciemniejszy. Duże zmiany będą miały znaczenie, ponieważ piksele zbyt jasne/ciemne zostaną utracone. Możesz zastosować to w jednym wierszu lub tyle, ile chcesz, aby zwiększyć dokładność. Co najwyżej będziesz miał 47x47=2209 odejmowań, aby utworzyć porównywalny klucz.

Wybranie 100 losowych punktów może oznaczać, że podobne (lub czasami nawet odmienne) obrazy będą oznaczone jako takie same, co zakładam, że nie jest tym, czego chcesz. Skróty MD5 nie zadziałałyby, gdyby obrazy były w różnych formatach (png, jpeg itp.), miały różne rozmiary lub miały inne metadane. Redukcja wszystkich obrazów do mniejszych rozmiarów jest dobrym rozwiązaniem, porównanie pikseli do pikseli nie powinno trwać zbyt długo, o ile używasz dobrej biblioteki obrazów / szybkiego języka , a rozmiar jest wystarczająco mały.

Możesz spróbować zrobić je malutkimi, a jeśli są takie same, wykonaj kolejne porównanie na większym rozmiarze - może to być dobre połączenie szybkości i dokładności...

Jeśli masz dużą liczbę obrazów, spójrz na filtr Bloom , który używa wielu skrótów dla prawdopodobnego, ale wydajnego wyniku. Jeśli liczba obrazów nie jest duża, wówczas hash kryptograficzny, taki jak md5, powinien być wystarczający.