Porównanie obrazów - szybki algorytm

393

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.

Meade
źródło

Odpowiedzi:

459

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

Kyle Simek
źródło
Podejście do histogramu wydaje się najbardziej sensowne. Zakładam, że możesz obrócić obraz, aby wykonać to ze wszystkich stron, na wypadek gdyby obraz porównany został odwrócony (traktując ten sam obraz jako 4) - dzięki
meade
4
@meade Zgadza się. Coś jeszcze do rozważenia: w zależności od problemu może nie być konieczne użycie wszystkich 5 histogramów w algorytmie. Odrzucenie histogramu kierunku tekstury pozwoli dopasować obrócone wersje obrazu. Odrzucenie histogramu skali tekstury pozwoli dopasować przeskalowane wersje obrazu. Stracisz zdolność porównywania podobieństwa, ale w zależności od sytuacji może to nie stanowić problemu. Ponieważ obliczanie informacji o teksturach jest najbardziej kosztowną częścią algorytmu, sprawi to, że algorytm też będzie szybki.
Kyle Simek
@redmoskito: Mam pytanie. Jak uzyskać na przykład wartość liczbową histogramu zieleni? Więc możesz odjąć to z innym histogramem obrazu? Załóżmy, że mamy zielony histogram z 3 pikselami należącymi do segmentu 0-63 i 5 pikselami należącymi do 64-127. Jaka jest wartość?
dynamiczny
3
@Ikaso, jeśli jego dokładnie ten sam obraz, prawdopodobnie nie chcesz używać czegoś takiego i rozważ użycie prostego porównania CRC lub MD5. Jeśli to nie wystarczy, tak jak w przypadku pojedynczych pikseli, które się różnią lub metadane uległy zmianie, wystarcza również metoda histogramu. jeśli twoje obrazy są takie same, ale obrócone lub skalowane, metoda oparta na histogramie może być wystarczająca, ale może się nie powieść. jeśli twoje obrazy zmieniły kolory, musisz użyć algorytmów opartych na punktach zainteresowania.
reox
5
Chciałbym dodać, że obecnie istnieje wiele szybkich alternatyw dla SIFT, takich jak detektor FAST i deskryptory binarne (KRÓTKI, BRISK, ORB, FREAK, BinBoost), aby wymienić tylko kilka. Samouczek na temat deskryptorów binarnych można znaleźć tutaj: gilscvblog.wordpress.com/2013/08/26/…
GilLevi
85

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.

redcalx
źródło
Kto jest ciekawy w tej metodzie, może znaleźć realizację Objective-C Perceptual Hash przez link github.com/ameingast/cocoaimagehashing
Alexey Voitenko
@AlexeyVoitenko Czy jest to zgodne z hashami produkowanymi przez phash.org w domyślnej konfiguracji?
Michael
1
Z mojego doświadczenia wynika, że ​​phash dobrze sprawdza się w znajdowaniu różnych rozmiarów tego samego obrazu, ale nie w przypadku podobnych obrazów. Np. Dwa różne zdjęcia tego samego obiektu mogą mieć bardzo różne wartości skrótów.
Rena
39

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.

wally
źródło
8

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ę.

Tobiesque
źródło
7

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.

Denis C.
źródło
7

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!

Tanner Clark
źródło
6

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ń.

Tanoshimi
źródło
3

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 ...

HarryM
źródło
Jeśli szukasz dokładnych duplikatów, ale z różnymi formatami / metadanymi, możesz wykonać skrót (np. MD5) rzeczywistych wartości pikseli. Imagemagick nazywa to podpisem (niezwiązanym z podpisywaniem kryptograficznym). Możesz także najpierw go zmniejszyć, np. Obcięcie do 4 bitów na piksel w celu zmniejszenia wpływu artefaktów JPEG lub konwersję do skali szarości w celu dopasowania lekko zmienionych kolorów obrazów.
Rena
2

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.

jdigital
źródło
Więc (próbując zrozumieć filtr Blooma) - czy to oznacza, że ​​wybierasz losowe punkty pikseli na obrazie podstawowym, losowo otrzymujesz albo czerwoną / zieloną / niebieską wartość piksela - a następnie porównujesz z nowym obrazem? a następnie użyj poziomu prawdopodobieństwa (dopasowanie 90%), aby określić, jak podobne są te dwa obrazy?
Meade
5
To nie jest kontrola podobieństwa, to kontrola równoważności. Jeśli potrzebujesz podobieństwa, haszowanie nie jest właściwym podejściem. Ideą Bloom jest wykorzystanie wielu algorytmów mieszających, aby zwiększyć prawdopodobieństwo unikalnej identyfikacji. Wybieranie losowych punktów nie jest najlepszym podejściem dla algorytmu mieszającego, ponieważ za każdym razem da różne wyniki.
jdigital