Odcisk palca obrazu do porównania podobieństwa wielu obrazów

Muszę utworzyć odciski palców wielu obrazów (około 100 000 istniejących, 1000 nowych dziennie, RGB, JPEG, maksymalny rozmiar 800x800), aby bardzo szybko porównać każdy obraz z każdym innym. Nie mogę użyć binarnych metod porównywania, ponieważ powinny zostać rozpoznane również obrazy, które są prawie podobne.

Najlepsza byłaby istniejąca biblioteka, ale również kilka wskazówek dotyczących istniejących algorytmów bardzo by mi pomogło.

Zwykłe algorytmy haszowania lub obliczania CRC nie działają dobrze z danymi obrazu. Należy wziąć pod uwagę wymiarowy charakter informacji.

Jeśli potrzebujesz wyjątkowo solidnych odcisków palców, takich jak transformacje afiniczne (skalowanie, obrót, translacja, odwracanie), możesz użyć transformacji Radona na źródle obrazu, aby utworzyć normatywne mapowanie danych obrazu - przechowuj to z każdym obrazem i następnie porównaj tylko odciski palców. To złożony algorytm, który nie jest przeznaczony dla osób o słabym sercu.

możliwych jest kilka prostych rozwiązań:

1. Utwórz histogram jasności dla obrazu jako odcisk palca
2. Utwórz pomniejszone wersje każdego obrazu jako odcisk palca
3. Połącz technikę (1) i (2) w podejście hybrydowe w celu poprawy jakości porównania

Histogram jasności (szczególnie taki, który jest podzielony na komponenty RGB) to rozsądny odcisk palca dla obrazu - i można go wdrożyć dość wydajnie. Odejmowanie jednego histogramu od drugiego utworzy nowy historgram, który możesz przetworzyć, aby zdecydować, jak podobne są dwa obrazy. Histogramy, ponieważ jedyni oceniają rozkład i występowanie informacji o jasności / kolorze całkiem dobrze radzą sobie z transformacjami afinicznymi. Jeśli skwantyzujesz informacje o jasności każdego składnika koloru do wartości 8-bitowej, 768 bajtów pamięci wystarczy na odcisk palca obrazu o niemal każdym rozsądnym rozmiarze. Histogramy jasności dają fałszywe negatywy, gdy manipuluje się informacjami o kolorze na obrazie. Jeśli zastosujesz transformacje, takie jak kontrast / jasność, posteryzacja, przesunięcie kolorów, zmiany jasności.

Korzystanie ze skalowanych obrazów to kolejny sposób na zmniejszenie gęstości informacji obrazu do poziomu, który jest łatwiejszy do porównania. Redukcje poniżej 10% oryginalnego rozmiaru obrazu generalnie powodują utratę zbyt dużej ilości informacji, aby można je było wykorzystać - więc obraz o rozdzielczości 800x800 pikseli można zmniejszyć do 80x80 i nadal zapewniać wystarczającą ilość informacji, aby wykonać przyzwoity odcisk palca. W przeciwieństwie do danych histogramu, musisz przeprowadzić anizotropowe skalowanie danych obrazu, gdy rozdzielczości źródła mają różne współczynniki proporcji. Innymi słowy, zmniejszenie obrazu 300x800 do miniatury 80x80 powoduje deformację obrazu, tak że w porównaniu z obrazem 300x500 (to jest bardzo podobne) spowoduje fałszywe negatywy. Odciski palców w postaci miniatur również często dają fałszywie ujemne wartości, gdy występują transformacje afiniczne. Jeśli odwrócisz lub obrócisz obraz,

Połączenie obu technik to rozsądny sposób na zabezpieczenie zakładów i ograniczenie występowania zarówno fałszywych trafień, jak i fałszywie negatywnych wyników.

Istnieje znacznie mniej ad-hoc podejścia niż przeskalowane warianty obrazu, które zostały tutaj zaproponowane, które zachowują swój ogólny smak, ale dają znacznie bardziej rygorystyczne matematyczne podstawy tego, co się dzieje.

Weź falkę Haar z obrazu. Zasadniczo falka Haara to ciąg różnic między obrazami o niższej rozdzielczości i każdym obrazem o wyższej rozdzielczości, ale ważony według tego, jak głęboko jesteś w „drzewie” mipmap. Obliczenie jest proste. Następnie, gdy falka Haara jest już odpowiednio wyważona, wyrzuć wszystkie oprócz k największych współczynników (w kategoriach wartości bezwzględnej), znormalizuj wektor i zapisz go.

Jeśli weźmiemy iloczyn skalarny dwóch z tych znormalizowanych wektorów, otrzymamy miarę podobieństwa, gdzie 1 jest prawie identyczne. Tutaj zamieściłem więcej informacji .

Zdecydowanie powinieneś rzucić okiem na phash .

Do porównania obrazów służy ten projekt php : https://github.com/kennethrapp/phasher

I mój mały klon javascript : https://redaktor.me/phasher/demo_js/index.html

Niestety jest to oparte na "bitcount", ale rozpoznaje obrócone obrazy. Innym podejściem w javascript było zbudowanie histogramu jasności z obrazu za pomocą płótna. Możesz zwizualizować histogram wielokąta na płótnie i porównać ten wielokąt w swojej bazie danych (np. MySQL przestrzenny ...)

Dawno temu pracowałem nad systemem, który miał podobne cechy i jest to przybliżenie algorytmu, który stosowaliśmy:

1. Podziel obraz na strefy. W naszym przypadku mieliśmy do czynienia z wideo w rozdzielczości 4: 3, więc użyliśmy 12 stref. W ten sposób rozdzielczość obrazów źródłowych zostaje usunięta z obrazu.
2. Dla każdej strefy oblicz ogólny kolor - średnią wszystkich pikseli w strefie
3. Dla całego obrazu oblicz ogólny kolor - średnią wszystkich stref

Więc dla każdego obrazu przechowujesz n + 1wartości całkowite, gdzie njest liczba stref, które śledzisz.

W celu porównania należy również spojrzeć na każdy kanał koloru osobno.

1. W przypadku całego obrazu porównaj kanały kolorów dla ogólnych kolorów, aby sprawdzić, czy mieszczą się w określonym progu - powiedzmy 10%
2. Jeśli obrazy mieszczą się w progu, następnie porównaj każdą strefę. Jeśli wszystkie strefy również znajdują się w progu, obrazy są na tyle silne, że można je przynajmniej oznaczyć do dalszego porównania.

Pozwala to szybko odrzucić obrazy, które nie pasują; możesz także użyć większej liczby stref i / lub zastosować algorytm rekurencyjnie, aby uzyskać silniejszą pewność dopasowania.

Podobnie jak odpowiedź Ic - możesz spróbować porównać obrazy w wielu rozdzielczościach. Zatem każdy obraz zostanie zapisany jako 1x1, 2x2, 4x4 .. 800x800. Jeśli najniższa rozdzielczość nie pasuje (podlega progowi), możesz ją natychmiast odrzucić. Jeśli tak, możesz je porównać w następnej wyższej rozdzielczości i tak dalej.

Ponadto - jeśli obrazy mają podobną strukturę, na przykład obrazy medyczne, możesz wyodrębnić tę strukturę w opisie, który jest łatwiejszy / szybszy do porównania.

Więc chcesz zrobić „dopasowywanie odcisków palców”, które jest całkiem inne niż „dopasowywanie obrazów”. Analiza odcisków palców była dogłębnie badana w ciągu ostatnich 20 lat i opracowano kilka interesujących algorytmów zapewniających właściwy współczynnik wykrywania (w odniesieniu do miar FAR i FRR - współczynnik fałszywej akceptacji i współczynnik fałszywych odrzuceń ).

Sugeruję, abyś lepiej przyjrzał się klasie technik wykrywania LFA (Local Feature Analysis) , głównie opartej na inspekcji drobiazgów. Minucje to specyficzne cechy każdego odcisku palca i zostały sklasyfikowane w kilku klasach. Odwzorowanie obrazu rastrowego na mapę drobiazgów jest tym, co w rzeczywistości robi większość władz publicznych, aby zgłosić przestępców lub terrorystów.

Zobacz tutaj, aby uzyskać dalsze referencje

W przypadku porównania obrazów iPhone'a i rozwoju podobieństwa obrazów sprawdź: http://sites.google.com/site/imagecomparison/

Aby zobaczyć to w akcji, sprawdź eyeBuy Visual Search w iTunes AppStore.

Od 2015 r. (Wracając do przyszłości ... w sprawie tego pytania z 2009 r., Które jest obecnie wysoko oceniane w Google) podobieństwo obrazów można obliczyć za pomocą technik głębokiego uczenia. Rodzina algorytmów znana jako Auto Encoders może tworzyć reprezentacje wektorowe, które można przeszukiwać pod kątem podobieństwa. Jest tutaj demo .

Jednym ze sposobów jest zmiana rozmiaru obrazu i znaczne obniżenie rozdzielczości (może do 200x200?), Zapisując mniejszą (uśrednioną w pikselach) wersję do porównania. Następnie określ próg tolerancji i porównaj każdy piksel. Jeśli RGB wszystkich pikseli mieści się w tolerancji, masz dopasowanie.

Twój początkowy przebieg to O (n ^ 2), ale jeśli skatalogujesz wszystkie dopasowania, każdy nowy obraz jest tylko algorytmem O (n) do porównania (wystarczy porównać go z każdym wcześniej wstawionym obrazem). W końcu jednak się rozpadnie, gdy lista obrazów do porównania stanie się większa, ale myślę, że przez chwilę będziesz bezpieczny.

Po 400 dniach działania będziesz mieć 500 000 obrazów, co oznacza (pomijając czas potrzebny na zmniejszenie rozmiaru obrazu) 200(H)*200(W)*500,000(images)*3(RGB)= 60 000 000 000 porównań. Jeśli każdy obraz jest dokładnie dopasowany, zostaniesz w tyle, ale prawdopodobnie tak nie będzie, prawda? Pamiętaj, że możesz zdyskontować obraz jako dopasowanie, gdy tylko pojedyncze porównanie przekroczy Twój próg.

Czy chcesz dosłownie porównać każdy obraz z innymi? Jaka jest aplikacja? Może potrzebujesz po prostu indeksowania i pobierania obrazów na podstawie określonych deskryptorów? Następnie możesz na przykład spojrzeć na standard MPEG-7 dla interfejsu opisu treści multimedialnych. Następnie możesz porównać różne deskryptory obrazów, które nie będą tak dokładne, ale znacznie szybsze.

Wydaje się, że wyspecjalizowane algorytmy haszowania obrazów są obszarem aktywnych badań, ale być może zwykłe obliczanie skrótu bajtów obrazu załatwi sprawę.

Czy szukasz obrazów identycznych bajtowo, a nie obrazów pochodzących z tego samego źródła, ale mogą mieć inny format lub rozdzielczość (co wydaje mi się raczej trudnym problemem).