Porównanie obrazów - szybki algorytm

Chcę utworzyć tabelę podstawową obrazów, a następnie porównać z nią wszystkie nowe obrazy, aby ustalić, czy nowy obraz jest dokładną (lub bliską) kopią bazy.

Na przykład: jeśli chcesz ograniczyć przechowywanie tego samego obrazu 100 razy, możesz zapisać jedną jego kopię i podać do niej linki referencyjne. Po wprowadzeniu nowego obrazu chcesz porównać z istniejącym obrazem, aby upewnić się, że nie jest to duplikat ... pomysłów?

Jednym z moich pomysłów było zmniejszenie do małej miniatury, a następnie losowe wybranie 100 pikseli lokalizacji i porównanie.

Poniżej znajdują się trzy podejścia do rozwiązania tego problemu (i jest wiele innych).

• Pierwszym z nich jest standardowe podejście do widzenia komputerowego, dopasowanie kluczowych punktów. Może to wymagać pewnej wiedzy w celu wdrożenia i może być powolne.

• Druga metoda wykorzystuje tylko elementarne przetwarzanie obrazu i jest potencjalnie szybsza niż pierwsze podejście i jest łatwa do wdrożenia. Jednak to, co zyskuje na zrozumiałości, nie ma solidności - dopasowanie nie powiedzie się na skalowanych, obracanych lub przebarwionych obrazach.

• Trzecia metoda jest zarówno szybka, jak i niezawodna, ale potencjalnie najtrudniejsza do wdrożenia.

Dopasowywanie kluczowych punktów

Lepsze niż wybranie 100 losowych punktów jest wybranie 100 ważnych punktów. Niektóre części obrazu zawierają więcej informacji niż inne (szczególnie na krawędziach i rogach), a te z nich będziesz chciał wykorzystać do inteligentnego dopasowania obrazu. Google „ wyodrębnianie kluczowych punktów ” i „ dopasowywanie kluczowych punktów ”, a znajdziesz sporo artykułów naukowych na ten temat. Obecnie kluczowe punkty SIFT są prawdopodobnie najpopularniejsze, ponieważ mogą dopasowywać obrazy w różnych skalach, obrotach i oświetleniu. Niektóre implementacje SIFT można znaleźć tutaj .

Jednym minusem dopasowania kluczowych punktów jest czas działania naiwnej implementacji: O (n ^ 2m), gdzie n to liczba kluczowych punktów na każdym obrazie, a m to liczba obrazów w bazie danych. Niektóre sprytne algorytmy mogą znaleźć najbliższe dopasowanie szybciej, takie jak kwadraty lub partycjonowanie przestrzeni binarnej.

Alternatywne rozwiązanie: metoda histogramu

Innym mniej niezawodnym, ale potencjalnie szybszym rozwiązaniem jest zbudowanie histogramów cech dla każdego obrazu i wybranie obrazu z histogramem najbliższym histogramowi obrazu wejściowego. Zaimplementowałem to jako licencjat i zastosowaliśmy 3 kolorowe histogramy (czerwony, zielony i niebieski) oraz dwa histogramy tekstury, kierunek i skalę. Podam szczegóły poniżej, ale powinienem zauważyć, że działało to dobrze tylko w przypadku dopasowywania obrazów BARDZO podobnych do obrazów w bazie danych. Dzięki tej metodzie przeskalowane, obrócone lub przebarwione obrazy mogą się nie powieść, ale niewielkie zmiany, takie jak kadrowanie, nie złamią algorytmu

Obliczanie histogramów kolorów jest proste - wystarczy wybrać zakres wiader histogramu, a dla każdego zakresu wyliczyć liczbę pikseli z kolorem w tym zakresie. Weźmy na przykład „zielony” histogram i załóżmy, że wybraliśmy 4 wiadra dla naszego histogramu: 0-63, 64-127, 128-191 i 192-255. Następnie dla każdego piksela patrzymy na zieloną wartość i dodajemy tally do odpowiedniego wiadra. Po zakończeniu sumowania dzielimy każde wiadro ogółem przez liczbę pikseli na całym obrazie, aby uzyskać znormalizowany histogram dla zielonego kanału.

W przypadku histogramu kierunku tekstury zaczęliśmy od wykrycia krawędzi na obrazie. Każdy punkt krawędzi ma normalny wektor wskazujący w kierunku prostopadłym do krawędzi. Skwantyzowaliśmy kąt wektora normalnego do jednego z 6 segmentów między 0 a PI (ponieważ krawędzie mają symetrię 180 stopni, przekonwertowaliśmy kąty między -PI i 0, aby były między 0 a PI). Po zsumowaniu liczby punktów krawędziowych w każdym kierunku, mamy unormalizowany histogram reprezentujący kierunek tekstury, który znormalizowaliśmy dzieląc każde wiadro przez całkowitą liczbę punktów krawędziowych na obrazie.

Aby obliczyć histogram skali tekstury, dla każdego punktu krawędzi zmierzyliśmy odległość do najbliższego punktu krawędzi o tym samym kierunku. Na przykład, jeśli punkt krawędzi A ma kierunek 45 stopni, algorytm idzie w tym kierunku, aż znajdzie inny punkt krawędzi z kierunkiem 45 stopni (lub w rozsądnym odchyleniu). Po obliczeniu tej odległości dla każdego punktu krawędzi zrzucamy te wartości na histogram i normalizujemy je, dzieląc przez całkowitą liczbę punktów krawędzi.

Teraz masz 5 histogramów dla każdego obrazu. Aby porównać dwa obrazy, weź bezwzględną wartość różnicy między każdym segmentem histogramu, a następnie zsumuj te wartości. Na przykład, aby porównać obrazy A i B, obliczymy

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

dla każdego segmentu na zielonym histogramie i powtórz dla pozostałych histogramów, a następnie zsumuj wszystkie wyniki. Im mniejszy wynik, tym lepsze dopasowanie. Powtórz te czynności dla wszystkich obrazów w bazie danych, a wygra mecz o najmniejszym wyniku. Prawdopodobnie chciałbyś mieć próg, powyżej którego algorytm stwierdza, że ​​nie znaleziono dopasowania.

Trzeci wybór - punkty kluczowe + drzewa decyzyjne

Trzecie podejście, które jest prawdopodobnie znacznie szybsze niż pozostałe dwa, polega na użyciu semantycznych lasów tekstowych (PDF). Obejmuje to wyodrębnienie prostych punktów kluczowych i użycie drzew decyzyjnych kolekcji do sklasyfikowania obrazu. Jest to szybsze niż proste dopasowanie punktów kluczowych SIFT, ponieważ pozwala uniknąć kosztownego dopasowywania punktów kluczowych, a punkty kluczowe są znacznie prostsze niż SIFT, więc ekstrakcja punktów kluczowych jest znacznie szybsza. Zachowuje jednak niezmienność metody SIFT względem obrotu, skali i oświetlenia, ważną cechę, której brakowało w histogramie.

Aktualizacja :

Mój błąd - praca Semantic Texton Forests nie dotyczy wyłącznie dopasowywania obrazów, ale raczej oznaczania regionu. Oryginalny papier, który pasuje, to ten: Rozpoznawanie kluczowych punktów za pomocą losowych drzew . Ponadto poniższe artykuły nadal rozwijają pomysły i przedstawiają najnowszy stan wiedzy (c. 2010):

• Szybkie rozpoznawanie kluczowych punktów za pomocą losowych paproci - szybsze i bardziej skalowalne niż Lepetit 06
• KRÓTKI: Binarne, solidne, niezależne podstawowe funkcje - mniej solidne, ale bardzo szybkie - myślę, że celem tutaj jest dopasowanie w czasie rzeczywistym na smartfonach i innych urządzeniach przenośnych

Najlepszą znaną mi metodą jest użycie Percepcyjnego skrótu. Wydaje się, że istnieje dobra implementacja takiego skrótu dostępna pod adresem:

http://phash.org/

Główną ideą jest to, że każdy obraz sprowadza się do małego kodu skrótu lub „odcisku palca” poprzez identyfikację istotnych cech w oryginalnym pliku obrazu i mieszanie zwięzłej reprezentacji tych funkcji (zamiast mieszania danych obrazu bezpośrednio). Oznacza to, że częstość fałszywych trafień jest znacznie mniejsza w porównaniu z uproszczonym podejściem, takim jak redukcja obrazów do małego rozmiaru odcisku palca i porównywanie odcisków palców.

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

Ten post był punktem wyjścia do mojego rozwiązania, jest tu wiele dobrych pomysłów, więc pomyślałem, że podzielę się z tobą wynikami. Główny wgląd jest taki, że znalazłem sposób na obejście powolności dopasowywania obrazu opartego na kluczowych punktach, wykorzystując szybkość phash.

W przypadku ogólnego rozwiązania najlepiej zastosować kilka strategii. Każdy algorytm najlepiej nadaje się do niektórych rodzajów transformacji obrazu i możesz z tego skorzystać.

Na górze najszybsze algorytmy; na dole najwolniejszy (choć dokładniejszy). Możesz pominąć wolne, jeśli na wyższym poziomie zostanie znalezione dobre dopasowanie.

• oparty na haszowaniu plików (md5, sha1 itp.) dla dokładnych duplikatów
• haszowanie percepcyjne (phash) dla przeskalowanych obrazów
• oparty na funkcjach (SIFT) dla zmodyfikowanych obrazów

Mam bardzo dobre wyniki z phash. Dokładność jest dobra w przypadku przeskalowanych obrazów. Nie nadaje się do (percepcyjnie) zmodyfikowanych obrazów (przyciętych, obróconych, dublowanych itp.). Aby poradzić sobie z szybkością mieszania, musimy zastosować pamięć podręczną dysku / bazę danych w celu utrzymania skrótów dla stogu siana.

Naprawdę fajną rzeczą w phash jest to, że po zbudowaniu bazy danych hash (która dla mnie wynosi około 1000 obrazów / s), wyszukiwanie może być bardzo, bardzo szybkie, szczególnie gdy możesz przechowywać całą bazę danych hash w pamięci. Jest to dość praktyczne, ponieważ skrót ma tylko 8 bajtów.

Na przykład, jeśli masz 1 milion obrazów, wymagałoby to tablicy 1 miliona 64-bitowych wartości skrótu (8 MB). Na niektórych procesorach pasuje to do pamięci podręcznej L2 / L3! W praktyce widziałem porównanie corei7 z prędkością powyżej 1 Giga-hamm / s, to tylko kwestia przepustowości pamięci procesora. Baza danych z 1 miliardem obrazów jest praktyczna na 64-bitowym procesorze (potrzeba 8 GB pamięci RAM), a wyszukiwania nie przekroczą 1 sekundy!

W przypadku zmodyfikowanych / przyciętych obrazów wydaje się, że najlepszym rozwiązaniem jest detektor niezmiennej transformacji / detektor punktów kluczowych, taki jak SIFT. SIFT wytworzy dobre punkty kluczowe, które wykrywają kadrowanie / obracanie / odbicie lustrzane itp. Jednak porównanie deskryptorów jest bardzo wolne w porównaniu do odległości hamowania używanej przez phash. To jest główne ograniczenie. Istnieje wiele porównań do zrobienia, ponieważ istnieje maksymalna liczba deskryptorów IxJxK w porównaniu do wyszukiwania jednego obrazu (I = liczba obrazów stogu siana, J = docelowe punkty kluczowe na obrazie stogu siana, K = docelowe punkty kluczowe na obrazie 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 / promienia elementu do określenia pod-prostokąta. Sztuką, aby to dobrze działało, jest zwiększenie / zmniejszenie promienia w celu wygenerowania różnych poziomów pod-prostokątnych (na zdjęciu igły). Zazwyczaj pierwszy poziom (nieskalowany) 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 włącza funkcje, które są zbyt małe, aby mógł działać Phash (Phash skaluje obrazy do 32 x 32).

Inną kwestią jest to, że SIFT nie rozdzieli optymalnie punktów kluczowych. Jeśli jest fragment obrazu z wieloma krawędziami, punkty kluczowe zostaną tam skupione i nie dostaniesz ich w innym obszarze. Korzystam z GridAdaptedFeatureDetector w OpenCV, aby poprawić dystrybucję. Nie jestem pewien, jaki rozmiar siatki jest najlepszy, używam małej siatki (1x3 lub 3x1 w zależności od orientacji obrazu).

Prawdopodobnie zechcesz przeskalować wszystkie obrazy stogu siana (i igły) do mniejszego rozmiaru przed wykryciem funkcji (używam 210 pikseli wzdłuż maksymalnego wymiaru). Zmniejszy to szum na obrazie (zawsze stanowi to problem dla algorytmów widzenia komputerowego), a także skupi detektor na bardziej znaczących funkcjach.

W przypadku zdjęć ludzi możesz 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 100 pikseli). Detektor cech uwzględnia wiele poziomów skali (przy użyciu piramid), ale istnieje ograniczenie liczby używanych poziomów (jest to oczywiście dostrajane).

Detektor punktów kluczowych prawdopodobnie działa najlepiej, gdy zwraca mniej niż żądana liczba funkcji. Na przykład, jeśli poprosisz o 400 i odzyskasz 300, to dobrze. Jeśli odzyskujesz 400 za każdym razem, prawdopodobnie pewne dobre funkcje musiały zostać pominięte.

Obraz igły może mieć mniej punktów kluczowych niż obrazy stogu siana i nadal osiągać dobre wyniki. Dodanie więcej niekoniecznie przyniesie ogromne zyski, na przykład przy J = 400 i K = 40 mój wskaźnik trafień wynosi około 92%. Przy J = 400 i K = 400 wskaźnik trafień wzrasta tylko do 96%.

Możemy wykorzystać ekstremalną prędkość funkcji Hamminga do rozwiązania skalowania, obrotu, odbicia lustrzanego itp. Można zastosować technikę wielokrotnego przejścia. Na każdej iteracji przekształć pod-prostokąty, ponownie hashuj i ponownie uruchom funkcję wyszukiwania.

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

Punktem wyjścia do znalezienia bliskich zdjęć może być tutaj . Jest to narzędzie używane przez firmy z branży komputerowej do sprawdzania, czy przerobione obrazy nadal pokazują zasadniczo tę samą scenę.

Mam pomysł, który może zadziałać i najprawdopodobniej będzie bardzo szybki. Możesz podpróbkować obraz z rozdzielczością 80x60 lub porównywalną i przekonwertować go na skalę szarości (po podpróbkowaniu będzie on szybszy). Przetwarzaj oba obrazy, które chcesz porównać. Następnie uruchom znormalizowaną sumę kwadratów różnic między dwoma obrazami (obrazem zapytania i każdym z bazy danych) lub jeszcze lepiej znormalizowaną korelacją krzyżową, która daje odpowiedź bliższą 1, jeśli oba obrazy są podobne. Następnie, jeśli obrazy są podobne, możesz przejść do bardziej wyrafinowanych technik, aby sprawdzić, czy są to te same obrazy. Oczywiście ten algorytm jest liniowy pod względem liczby obrazów w bazie danych, więc nawet na bardzo nowoczesnym sprzęcie będzie on bardzo szybki do 10000 obrazów na sekundę. Jeśli potrzebujesz rotacji niezmienniczości, wówczas dla tego małego obrazu można obliczyć dominujący gradient, a następnie cały układ współrzędnych można obrócić do orientacji kanonicznej, jednak będzie to wolniejsze. I nie, nie ma tu niezmienności do skalowania.

Jeśli chcesz czegoś bardziej ogólnego lub używasz dużych baz danych (milionów zdjęć), musisz przyjrzeć się teorii odzyskiwania obrazów (mnóstwo artykułów pojawiło się w ciągu ostatnich 5 lat). Istnieją inne wskazówki w innych odpowiedziach. Ale może to być przesada, a sugerowane podejście histogramu wykona zadanie. Myślę jednak, że połączenie wielu różnych szybkich podejść będzie jeszcze lepsze.

Moja firma ma około 24 milionów zdjęć przychodzących od producentów każdego miesiąca. Szukałem szybkiego rozwiązania, aby zdjęcia, które przesyłamy do naszego katalogu, były nowe .

Chcę powiedzieć, że przeszukałem Internet szeroko i starałem się znaleźć idealne rozwiązanie. Opracowałem nawet własny algorytm wykrywania krawędzi.
Oceniłem szybkość i dokładność wielu modeli. Moje obrazy, które mają białe tło, działają wyjątkowo dobrze przy phashingu. Jak powiedział redcalx , polecam phash lub ahash. NIE używaj skrótu MD5 ani żadnych innych skrótów kryptograficznych. Chyba że chcesz tylko DOKŁADNE dopasowanie obrazu. Wszelkie zmiany rozmiaru lub manipulacje występujące między obrazami spowodują inny skrót.

W przypadku phash / ahash, sprawdź to: imagehash

Chciałem przedłużyć post * redcalx *, publikując mój kod i moją dokładność.

Co robię:

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

Oto niektóre z moich wyników:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

Mam nadzieję że to pomoże!

Uważam, że zmniejszenie rozmiaru obrazu do prawie ikony, powiedzmy 48x48, a następnie konwersja do skali szarości, a następnie uwzględnienie różnicy między pikselami lub Delta, powinno działać dobrze. Ponieważ porównujemy zmianę koloru pikseli, a nie rzeczywisty kolor pikseli, nie będzie miało znaczenia, czy obraz jest nieco jaśniejszy czy ciemniejszy. Duże zmiany będą miały znaczenie, ponieważ piksele stają się zbyt jasne / ciemne zostaną utracone. Możesz zastosować to w jednym rzędzie lub w dowolnej liczbie, aby zwiększyć dokładność. Aby utworzyć porównywalny klucz, musisz wykonać maksymalnie 47 x 47 = 2 209 odejmowań.

Wybranie 100 losowych punktów może oznaczać, że podobne (lub czasami nawet różne) obrazy zostaną oznaczone jako takie same, co, jak zakładam, nie jest tym, czego chcesz. Skróty MD5 nie działałyby, gdyby obrazy były w różnych formatach (png, jpeg itp.), Miały różne rozmiary lub różne metadane. Zmniejszenie wszystkich zdjęć do mniejszych rozmiarów jest dobrym rozwiązaniem, wykonanie porównania piksel po pikselu nie powinno zająć zbyt długo, o ile korzystasz z dobrej biblioteki obrazów / szybkiego języka, a rozmiar jest wystarczająco mały.

Możesz spróbować zrobić je malutkie, 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 Blooma , który używa wielu skrótów dla uzyskania prawdopodobieństwa, ale wydajnego wyniku. Jeśli liczba obrazów nie jest duża, to wystarczy szyfr kryptograficzny taki jak md5.