Biorąc pod uwagę dwa różne pliki graficzne (w dowolnym wybranym przeze mnie formacie), muszę napisać program przewidujący prawdopodobieństwo, że jeden z nich będzie nielegalną kopią innego. Autor kopii może wykonywać takie czynności, jak obracanie, robienie negatywu lub dodawanie błahych szczegółów (a także zmiana wymiarów obrazu).
Czy znasz jakiś algorytm do tego rodzaju pracy?
algorithm
image
image-processing
image-recognition
Salvador Dali
źródło
źródło
Odpowiedzi:
To są po prostu pomysły, które myślałem o problemie, nigdy go nie próbowałem, ale lubię myśleć o takich problemach!
Zanim zaczniesz
Rozważ normalizację obrazów, jeśli jeden z nich ma wyższą rozdzielczość niż drugi, rozważ opcję, że jeden z nich jest skompresowaną wersją drugiego, dlatego zmniejszenie rozdzielczości może zapewnić dokładniejsze wyniki.
Rozważ skanowanie różnych perspektywicznych obszarów obrazu, które mogą przedstawiać powiększone części obrazu oraz różne pozycje i obroty. Zaczyna się komplikować, jeśli jeden z obrazów jest wypaczoną wersją innego, są to ograniczenia, które należy zidentyfikować i z którymi należy się pogodzić.
Matlab to doskonałe narzędzie do testowania i oceny obrazów.
Testowanie algorytmów
Powinieneś przetestować (jako minimum) duży zestaw danych testowych przeanalizowanych przez ludzi, jeśli dopasowania są wcześniej znane. Jeśli na przykład w danych testowych masz 1000 obrazów, w których 5% z nich jest zgodnych, masz teraz dość wiarygodny test porównawczy. Algorytm, który znajduje 10% pozytywów, nie jest tak dobry, jak ten, który znajduje 4% pozytywów w naszych danych testowych. Jednak jeden algorytm może znaleźć wszystkie dopasowania, ale ma również duży, 20% współczynnik fałszywych trafień, więc istnieje kilka sposobów oceny algorytmów.
Dane testowe powinny być zaprojektowane tak, aby obejmowały jak najwięcej typów dynamiki, których można się spodziewać w rzeczywistym świecie.
Należy pamiętać, że każdy algorytm, aby był użyteczny, musi działać lepiej niż przypadkowe zgadywanie, w przeciwnym razie jest on dla nas bezużyteczny!
Następnie możesz w kontrolowany sposób zastosować swoje oprogramowanie w świecie rzeczywistym i zacząć analizować uzyskane wyniki. Jest to rodzaj projektu oprogramowania, który może trwać w nieskończoność, zawsze można wprowadzić poprawki i ulepszenia, ważne jest, aby o tym pamiętać podczas projektowania, ponieważ łatwo wpaść w pułapkę niekończącego się projektu.
Wiadra kolorów
Za pomocą dwóch zdjęć zeskanuj każdy piksel i policz kolory. Na przykład możesz mieć „wiadra”:
(Oczywiście miałbyś wyższą rozdzielczość liczników). Za każdym razem, gdy znajdziesz „czerwony” piksel, zwiększasz czerwony licznik. Każde wiadro może być reprezentatywne dla spektrum kolorów, im wyższa rozdzielczość, tym dokładniejsza, ale należy poeksperymentować z dopuszczalnym współczynnikiem różnicy.
Gdy masz już swoje sumy, porównaj je z sumami dla drugiego obrazu. Może się okazać, że każdy obraz ma dość unikalny ślad, wystarczający do zidentyfikowania dopasowań.
Wykrywanie krawędzi
Co powiesz na używanie wykrywania krawędzi . (źródło: wikimedia.org )
Przy dwóch podobnych obrazach wykrywanie krawędzi powinno zapewnić użyteczny i dość niezawodny unikalny ślad.
Zrób oba zdjęcia i zastosuj wykrywanie krawędzi. Może zmierzyć średnią grubość krawędzi, a następnie obliczyć prawdopodobieństwo, że obraz może zostać przeskalowany i w razie potrzeby przeskalować. Poniżej znajduje się przykład zastosowanego filtra Gabora (rodzaj wykrywania krawędzi) w różnych obrotach.
Porównaj obraz piksel za piksel, policz dopasowania i niezgodności. Jeśli mieszczą się w pewnym progu błędu, masz dopasowanie. W przeciwnym razie możesz spróbować zmniejszyć rozdzielczość do określonego punktu i sprawdzić, czy prawdopodobieństwo dopasowania się poprawi.
Regiony zainteresowania
Niektóre obrazy mogą mieć charakterystyczne segmenty / obszary zainteresowania. Te regiony prawdopodobnie silnie kontrastują z resztą obrazu i są dobrym elementem do wyszukiwania na innych obrazach, aby znaleźć dopasowania. Weźmy na przykład ten obraz:
(źródło: meetthegimp.org )
Pracownik budowlany zaznaczony na niebiesko to obszar zainteresowania i może być używany jako obiekt wyszukiwania. Prawdopodobnie istnieje kilka sposobów wyodrębnienia właściwości / danych z tego obszaru zainteresowania i wykorzystania ich do przeszukiwania zbioru danych.
Jeśli masz więcej niż 2 interesujące regiony, możesz zmierzyć odległości między nimi. Weź ten uproszczony przykład:
(źródło: per2000.eu )
Mamy 3 wyraźne obszary zainteresowania. Odległość między regionem 1 i 2 może wynosić 200 pikseli, od 1 do 3 400 pikseli oraz od 2 do 3 200 pikseli.
Przeszukuj inne obrazy pod kątem podobnych obszarów zainteresowania, znormalizuj wartości odległości i sprawdź, czy masz potencjalne dopasowania. Ta technika może dobrze działać w przypadku obróconych i przeskalowanych obrazów. Im więcej interesujących Cię regionów, tym prawdopodobieństwo dopasowania rośnie wraz z dopasowaniem każdego pomiaru odległości.
Ważne jest, aby pomyśleć o kontekście zbioru danych. Jeśli na przykład Twój zbiór danych jest sztuką współczesną, to obszary zainteresowania działałyby całkiem dobrze, ponieważ obszary zainteresowania zostały prawdopodobnie zaprojektowane jako podstawowa część ostatecznego obrazu. Jeśli jednak masz do czynienia ze zdjęciami placów budowy, obszary zainteresowania mogą być interpretowane przez nielegalną kopiarkę jako brzydkie i mogą być dowolnie przycinane / edytowane. Pamiętaj o wspólnych cechach zbioru danych i spróbuj wykorzystać tę wiedzę.
Morphing
Morfowanie dwóch obrazów to proces przekształcania jednego obrazu w drugi za pomocą zestawu kroków:
Zwróć uwagę, że różni się to od przechodzenia jednego obrazu w inny!
Istnieje wiele pakietów oprogramowania, które mogą morfować obrazy. Jest tradycyjnie używany jako efekt przejściowy, dwa obrazy zwykle nie przekształcają się w coś w połowie drogi, jeden skrajny przekształca się w drugi skrajny jako wynik końcowy.
Dlaczego to może być przydatne? W zależności od używanego algorytmu morfingu może istnieć związek między podobieństwem obrazów a niektórymi parametrami algorytmu morfingu.
W znacznie przesadnie uproszczonym przykładzie jeden algorytm może działać szybciej, gdy jest mniej zmian do wprowadzenia. Wtedy wiemy, że istnieje większe prawdopodobieństwo, że te dwa obrazy mają ze sobą wspólne właściwości.
Technika ta może dobrze działać w przypadku obróconych, zniekształconych, pochylonych, powiększonych i wszystkich typów kopiowanych obrazów. Znowu to tylko pomysł, który miałem, nie jest oparty na żadnym badanym środowisku akademickim, o ile wiem (chociaż nie wyglądam zbyt mocno), więc może to być dla ciebie dużo pracy z ograniczonymi / żadnymi wynikami.
Zapinanie
Odpowiedź Ow na to pytanie jest doskonała, pamiętam, że czytałem o tego rodzaju technikach studiowania sztucznej inteligencji. Jest dość skuteczny w porównywaniu leksykonów korpusu.
Interesującą optymalizacją podczas porównywania korpusów jest to, że można usunąć słowa uważane za zbyt powszechne, na przykład „The”, „A”, „And” itd. Te słowa osłabiają nasz wynik, chcemy sprawdzić, jak różne są te dwa korpusy aby można je było usunąć przed przetworzeniem. Być może w obrazach są podobne wspólne sygnały, które można usunąć przed kompresją? Może warto się temu przyjrzeć.
Współczynnik kompresji to bardzo szybki i dość skuteczny sposób określenia, jak podobne są dwa zestawy danych. Czytanie o tym, jak działa kompresja , da dobry pomysł, dlaczego może to być tak skuteczne. Byłby to prawdopodobnie dobry punkt wyjścia dla szybkiego do wydania algorytmu.
Przezroczystość
Ponownie nie jestem pewien, w jaki sposób dane przezroczystości są przechowywane dla niektórych typów obrazów, gif png itp., Ale będzie to możliwe do wyodrębnienia i posłuży jako skuteczne uproszczone wycięcie do porównania z przezroczystością zestawów danych.
Odwracanie sygnałów
Obraz to tylko sygnał. Jeśli odtwarzasz dźwięk z jednego głośnika i odtwarzasz przeciwny hałas w innym głośniku w doskonałej synchronizacji z dokładnie taką samą głośnością, wzajemnie się one znoszą.
(źródło: themotorreport.com.au )
Odwróć jeden z obrazów i dodaj go do drugiego obrazu. Skaluj to / zapętlaj pozycje wielokrotnie, aż znajdziesz wynikowy obraz, w którym wystarczająca liczba pikseli jest białych (lub czarnych? Nazywam to neutralnym płótnem), aby zapewnić dopasowanie pozytywne lub częściowe.
Rozważ jednak dwa obrazy, które są równe, z wyjątkiem tego, że jeden z nich ma zastosowany efekt rozjaśnienia:
(źródło: mcburrz.com )
Odwrócenie jednego z nich, a następnie dodanie go do drugiego nie zaowocuje neutralnym płótnem, do którego dążymy. Jednak porównując piksele z obu oryginalnych obrazów, z pewnością możemy zobaczyć wyraźny związek między nimi.
Nie badałem koloru od kilku lat i nie jestem pewien, czy widmo kolorów jest w skali liniowej, ale jeśli określiłeś średni współczynnik różnicy kolorów między oboma obrazami, możesz użyć tej wartości do znormalizowania danych przed przetworzeniem za pomocą ta technika.
Drzewiaste struktury danych
Na początku wydaje się, że nie pasują do problemu, ale myślę, że mogą działać.
Możesz pomyśleć o wyodrębnieniu pewnych właściwości obrazu (na przykład skrzynek kolorów) i wygenerowaniu drzewa Huffmana lub podobnej struktury danych. Możesz porównać dwa drzewa pod względem podobieństwa. Nie działałoby to dobrze w przypadku danych fotograficznych, na przykład o dużym spektrum kolorów, ale może to zadziałać w kreskówkach lub innych obrazach o zredukowanej liczbie kolorów.
To prawdopodobnie nie zadziała, ale to pomysł. Trie datastructure jest wielki na przechowywanie leksykonów, na przykład dictionarty. To drzewo przedrostków. Być może da się zbudować obrazowy odpowiednik leksykonu (znowu myślę tylko o kolorach), aby skonstruować próbę. Jeśli zredukowałeś, powiedzmy, obraz 300x300 do kwadratów 5x5, a następnie rozłożyć każdy kwadrat 5x5 na sekwencję kolorów, z których można by zbudować próbkę. Jeśli kwadrat 2x2 zawiera:
Mamy dość unikalny kod trie, który rozszerza 24 poziomy, zwiększając / zmniejszając poziomy (IE zmniejszając / zwiększając rozmiar naszego kwadratu) mogą dać dokładniejsze wyniki.
Porównywanie drzew trie powinno być dość łatwe i może zapewnić skuteczne wyniki.
Więcej pomysłów
Natknąłem się na interesujący artykuł dotyczący klasyfikacji zdjęć satelitarnych , który przedstawia:
Warto zbadać te pomiary bardziej szczegółowo, chociaż niektóre z nich mogą nie być odpowiednie dla zestawu danych.
Inne kwestie do rozważenia
Prawdopodobnie jest wiele artykułów na ten temat, więc przeczytanie niektórych z nich powinno pomóc, chociaż mogą być bardzo techniczne. Jest to niezwykle trudna dziedzina informatyki, z wieloma bezowocnymi godzinami pracy spędzonej przez wiele osób na podobnych rzeczach. Najlepszym sposobem byłoby zachowanie prostoty i budowanie na podstawie tych pomysłów. Stworzenie algorytmu o współczynniku dopasowania lepszym niż przypadkowe powinno być dość trudnym wyzwaniem, a rozpoczęcie ulepszania tego naprawdę zaczyna być dość trudne do osiągnięcia.
Każda metoda prawdopodobnie wymagałaby dokładnego przetestowania i dopracowania, jeśli masz jakieś informacje o typie obrazu, który będziesz sprawdzać, byłoby to przydatne. Na przykład reklamy, wiele z nich zawierałoby tekst, więc rozpoznawanie tekstu byłoby łatwym i prawdopodobnie bardzo niezawodnym sposobem znajdowania dopasowań, zwłaszcza w połączeniu z innymi rozwiązaniami. Jak wspomniano wcześniej, spróbuj wykorzystać typowe właściwości zestawu danych.
Połączenie alternatywnych pomiarów i technik, z których każda może mieć głos ważony (w zależności od ich skuteczności), byłoby jednym ze sposobów stworzenia systemu, który generuje dokładniejsze wyniki.
Jeśli stosuje się wiele algorytmów, jak wspomniano na początku tej odpowiedzi, można znaleźć wszystkie pozytywne wyniki, ale mieć współczynnik fałszywie pozytywnych wyników wynoszący 20%, byłoby interesujące zbadanie właściwości / mocnych / słabych stron innych algorytmów, ponieważ inny algorytm może skutecznie eliminować fałszywe alarmy zwracane przez inne osoby.
Uważaj, aby nie popaść w próbę ukończenia niekończącego się projektu, powodzenia!
źródło
Przeczytaj artykuł: Porikli, Fatih, Oncel Tuzel i Peter Meer. „Śledzenie kowariancji przy użyciu aktualizacji modelu opartej na średnich z rozmaitości riemannowskiej”. (2006) IEEE Computer Vision and Pattern Recognition.
Udało mi się wykryć nakładające się obszary na obrazach przechwyconych z sąsiednich kamer internetowych przy użyciu techniki przedstawionej w tym artykule. Moja macierz kowariancji składała się z wyjść Sobela, sprytnego i SUSAN wykrywania obrazu / krawędzi, a także oryginalnych pikseli w skali szarości.
źródło
Pomysł:
Krok 2 nie jest trywialny. W szczególności może być konieczne użycie inteligentnego algorytmu, aby znaleźć najbardziej podobny punkt kluczowy na drugim obrazie. Deskryptory punktów są zwykle bardzo wielowymiarowe (jak sto parametrów) i istnieje wiele punktów, które należy przejrzeć. drzewa kd mogą być tutaj przydatne, wyszukiwanie skrótów nie działa dobrze.
Warianty:
źródło
Jest to rzeczywiście dużo mniej proste, niż się wydaje :-) Sugestia Nicka jest dobra.
Na początek należy pamiętać, że każda opłacalna metoda porównania będzie zasadniczo działać poprzez konwersję obrazów do innej formy - formy, która ułatwia wybieranie podobnych funkcji. Zwykle te rzeczy nie są bardzo łatwe do czytania ...
Jednym z najprostszych przykładów, jakie przychodzi mi do głowy, jest po prostu użycie przestrzeni kolorów każdego obrazu. Jeśli dwa obrazy mają bardzo podobne rozkłady kolorów, możesz być dość pewny, że pokazują to samo. Przynajmniej możesz mieć wystarczającą pewność, aby ją oznaczyć lub przeprowadzić więcej testów. Porównywanie obrazów w przestrzeni kolorów będzie również odporne na takie rzeczy, jak obracanie, skalowanie i przycinanie. Oczywiście nie oprze się on ciężkiej modyfikacji obrazu lub intensywnemu ponownemu kolorowaniu (a nawet prosta zmiana odcienia będzie nieco trudna).
http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace
Inny przykład dotyczy czegoś, co nazywa się transformacją Hougha. Ta transformacja zasadniczo rozkłada obraz na zestaw linii. Następnie możesz wziąć niektóre z „najsilniejszych” linii na każdym zdjęciu i sprawdzić, czy się pokrywają. Możesz wykonać dodatkową pracę, aby spróbować skompensować obrót i skalowanie - w tym przypadku, ponieważ porównanie kilku linii to DUŻO mniej pracy obliczeniowej niż zrobienie tego samego z całymi obrazami - nie będzie tak źle.
http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/ Hough_transform
źródło
W opisanej przez Ciebie formie problem jest ciężki. Czy rozważasz skopiowanie i wklejenie części obrazu do innego większego obrazu jako kopii? itp.
Jeśli zrobisz krok wstecz, łatwiej będzie to rozwiązać, dodając znak wodny do obrazów wzorcowych. Będziesz musiał użyć schematu znaków wodnych, aby osadzić kod w obrazie. Aby zrobić krok wstecz, w przeciwieństwie do niektórych podejść niskiego poziomu (wykrywanie krawędzi itp.) Sugerowanych przez niektórych ludzi, metoda znaku wodnego jest lepsza, ponieważ:
Jest odporny na ataki przetwarzania sygnału ► Wzmocnienie sygnału - wyostrzanie, kontrast itp. ► Filtrowanie - mediana, dolnoprzepustowy, górnoprzepustowy itp. ► Szum addytywny - Gaussian, uniform itp. ► Kompresja stratna - JPEG, MPEG itp.
Jest odporny na ataki geometryczne ► Transformacje afiniczne ► Redukcja danych - kadrowanie, przycinanie itp. ► Losowe zniekształcenia lokalne ► Wypaczenie
Poszukaj informacji na temat algorytmów znaków wodnych, a będziesz na właściwej drodze do rozwiązania problemu. (Uwaga: Możesz porównać swoją metodę z wykorzystaniem zestawu danych STIRMARK . Jest to przyjęty standard dla tego typu aplikacji.
źródło
To tylko sugestia, może nie zadziałać i jestem przygotowany na wezwanie.
Spowoduje to wygenerowanie fałszywych alarmów, ale miejmy nadzieję, że nie fałszywie negatywnych.
Zmień rozmiar obu obrazów, aby miały ten sam rozmiar (zakładam, że stosunki szerokości do długości są takie same na obu obrazach).
Kompresuj mapę bitową obu obrazów za pomocą bezstratnego algorytmu kompresji (np. Gzip).
Znajdź pary plików o podobnych rozmiarach. Na przykład możesz po prostu posortować każdą posiadaną parę plików według tego, jak podobne są rozmiary plików i pobrać górne X.
Jak powiedziałem, z pewnością wygeneruje to fałszywe alarmy, ale miejmy nadzieję, że nie fałszywie negatywne. Możesz to zaimplementować w pięć minut, podczas gdy Porikil et. glin. prawdopodobnie wymagałoby rozległej pracy.
źródło
Uważam, że jeśli chcesz zastosować podejście do każdej możliwej orientacji i do negatywnych wersji, dobrym początkiem do rozpoznawania obrazu (z dobrą niezawodnością) jest użycie własnych twarzy: http://en.wikipedia.org/wiki/Eigenface
Innym pomysłem byłoby przekształcenie obu obrazów w wektory ich składników. Dobrym sposobem na zrobienie tego jest utworzenie wektora działającego w wymiarach x * y (x to szerokość obrazu, a y to wysokość), przy czym wartość każdego wymiaru ma zastosowanie do wartości (x, y) piksela. Następnie uruchom wariant K-Nearest Neighbours z dwiema kategoriami: dopasowanie i brak dopasowania. Jeśli jest wystarczająco blisko oryginalnego obrazu, będzie pasował do kategorii dopasowania, jeśli nie, to nie będzie.
K Nearest Neighbours (KNN) można znaleźć tutaj, są też inne dobre wyjaśnienia tego zagadnienia w Internecie: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
Zaletą KNN jest to, że im więcej wariantów porównujesz z oryginalnym obrazem, tym dokładniejszy staje się algorytm. Wadą jest to, że najpierw potrzebujesz katalogu obrazów, aby nauczyć system.
źródło
Jeśli chcesz rozważyć zupełnie inne podejście do wykrywania nielegalnych kopii swoich zdjęć, możesz rozważyć znak wodny . (od 1.4)
Chociaż jest to również złożona dziedzina, istnieją techniki, które pozwalają zachować informacje o znaku wodnym dzięki znacznym zmianom obrazu: (od 1.9)
oczywiście, często zadawane pytania mówią o implementacji tego podejścia: „... bardzo trudne”, ale jeśli ci się to uda, uzyskasz dużą pewność, czy obraz jest kopią, czy nie, a nie procentowe prawdopodobieństwo.
źródło
Jeśli używasz Linuksa, zasugerowałbym dwa narzędzia:
align_image_stack z pakietu hugin-tools - to program wiersza poleceń, który może automatycznie korygować obrót, skalowanie i inne zniekształcenia (jest przeznaczony głównie do komponowania zdjęć HDR, ale działa również dla ramek wideo i innych dokumentów). Więcej informacji: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html
porównaj z pakietem imagemagick - program, który może znaleźć i policzyć liczbę różnych pikseli na dwóch obrazach. Oto fajny tutorial: http://www.imagemagick.org/Usage/compare/ uising the -fuzz N% możesz zwiększyć tolerancję błędów. Im wyższe N, tym wyższa tolerancja błędu, aby nadal liczyć dwa piksele jako takie same.
align_image_stack powinno skorygować wszelkie przesunięcia, aby polecenie porównania faktycznie miało szansę na wykrycie tych samych pikseli.
źródło