Rozpoznawanie podobnych kształtów w losowej skali i tłumaczeniu

Question

Podczas zabawy ze znajdowaniem rzeczy na ekranie graficznym, nie mam pojęcia, jak znaleźć dany kształt w obrazie. Kształt na obrazku może mieć inną skalę i będzie oczywiście przy nieznanym przesunięciu x, y.

Oprócz artefaktów pikseli pochodzących z różnych skal, na obu zdjęciach występuje również niewielki hałas, więc potrzebuję nieco tolerancyjnego wyszukiwania.

Oto obraz, którego szukam.

Powinna pokazać się gdzieś w zrzucie ekranu mojego bufora (podwójna) ekranem, około 3300 x 1200 pikseli. Oczywiście spodziewam się, że znajdę go w oknie przeglądarki, ale ta informacja nie powinna być konieczna.

Celem tego ćwiczenia (do tej pory) jest wymyślić wyniku, który mówi:

• Tak, drewniana rama (tej przybliżonej kolorze i że ewentualnie lekko ścięty, kształt) została znaleziona na moim ekranie (lub nie); i
• obszar roboczy gry (czarny obszar wewnątrz ramki) zajmuje prostokąt od (x1,y1) do (x2,y2).

Chciałbym być odporny na skalowanie i hałas, który prawdopodobnie zostanie wprowadzony przez dithering. Z drugiej strony mogę wykluczyć niektóre zwykłe wyzwania związane z CV, takie jak rotacja czy brak sztywności. Ten kształt ramki jest łatwy do zrozumienia dla ludzkiego mózgu, jak trudny może być dla dedykowanego oprogramowania? Jest to aplikacja Adobe Flash i do niedawna uważałem, że postrzeganie obrazów z GUI gry powinno być łatwe jak ciasto.

Szukam algorytmu, który jest w stanie znaleźć translację x, y, przy której występuje największe możliwe nakładanie się igły i stogu siana, i jeśli to możliwe, bez konieczności przeprowadzania iteracji przez szereg możliwych współczynników skalowania. W idealnej sytuacji algorytm może wykluczyć "kształtowanie" obrazów w sposób niezależny od skali.

Przeczytałem kilka interesujących rzeczy o transformacjach Fouriera, aby osiągnąć coś podobnego: Biorąc pod uwagę obraz docelowy w tej samej skali, FFT i matematyka macierzowa oddały punkty w większym obrazie, który odpowiadał wzorcowi wyszukiwania. Ale nie mam podstaw teoretycznych, aby to zastosować, ani też nie wiem, czy to podejście z wdziękiem poradzi sobie z problemem skali. Pomoc byłaby doceniona!

Technologia: programuję w Clojure/Java, ale mogę dostosować algorytmy w innych językach. Myślę, że powinienem być w stanie łączyć się z bibliotekami, które stosują konwencje wywoływania C, ale wolałbym czyste rozwiązanie Javy.

---

Być może będziesz w stanie zrozumieć, dlaczego odrzuciłem prezentowanie rzeczywistego obrazu. To tylko głupia gra, ale zadanie jej czytania na ekranie okazuje się o wiele trudniejsze, niż myślałem.

Oczywiście jestem w stanie przeprowadzić wyczerpujące wyszukiwanie bufora ekranowego dla samych pikseli (z wyjątkiem czarnego), które tworzą mój obraz, a to nawet trwa poniżej minuty. Moją ambicją było jednak odnalezienie drewnianej ramy za pomocą techniki pasującej do kształtu, niezależnie od różnic, które mogą powstać w wyniku skalowania i ditheringu.

Roztrząsanie jest jedną z wielu frustracji związanych z tym projektem. Pracowałem nad wyodrębnianiem niektórych użytecznych wektorów przez ekstrakcję krawędzi, ale krawędzie są żałośnie nieuchwytne, ponieważ piksele z dowolnego obszaru mają bardzo niespójne kolory - tak więc trudno odróżnić prawdziwe krawędzie od lokalnych artefaktów ditheringu. Nie miałem pojęcia, że ​​taka prosta gra będzie produkować grafiki, które są tak trudne do postrzegania przez oprogramowanie.

Czy powinienem zacząć od lokalnych uśredniania pikseli, zanim zacznę szukać funkcji? Czy powinienem zmniejszyć głębię kolorów, wyrzucając najmniej znaczące bity wartości kolorów pikseli?

jestem próbuje dla czystego roztworu Java (faktycznie Programowanie w mieszance Clojure/Java), więc nie jestem dzikie o OpenCV (który instaluje DLL lub .so-tych z kodem C). Proszę nie martwić się o mój wybór języka, doświadczenie uczenia się jest dla mnie o wiele bardziej interesujące niż wydajność.

Answer 1

Będąc komputerowym gościem w wizjerze, zwykle wskazywałbym na wyodrębnianie i porównywanie funkcji (SIFT, SURF, LBP itp.), Ale to prawie na pewno przesada, ponieważ większość z tych metod oferuje więcej niezmienności (= tolerancje względem przekształceń), niż jest to wymagane (np. przed rotacją, zmianą luminancji, ...). Ponadto używanie funkcji wymagałoby albo programowania OpenCV, albo partii.

Więc tutaj jest moja propozycja dla prostego rozwiązania - ocenić, czy przechodzi on na spryt próg:

To wygląda jak na zdjęciu, którego szukasz ma bardzo różne struktury (litery, loga, itp) . Sugerowałbym, aby dopasować piksel do piksela dla każdego możliwego tłumaczenia i dla wielu różnych skal (zakładam, że zakres skal jest ograniczony) - ale tylko dla małej wyróżniającej się łatki obrazu, który jesteś szukając (powiedzmy kwadratową część żółtego tekstu). Jest to znacznie szybsze niż dopasowanie całości. Jeśli chcesz mieć na to fantazyjną nazwę: w przetwarzaniu obrazu jest nazywany dopasowywaniem szablonów przez korelację. "Szablon" jest tym, czego szukasz.

Po znalezieniu kilku lokalizacjach kandydujących dla małych charakterystycznym plaster można zweryfikować że masz potrącony przez testowanie albo cały obraz lub bardziej skutecznie, kilka inne charakterystyczne plamy obrazu (używając oczywiście tłumaczenia/skali znalezionej). To sprawia, że ​​twoje wyszukiwanie jest odporne na przypadkowe dopasowania oryginalnej łatki bez kradzieży zbyt dużej wydajności.

Jeśli chodzi o tolerancję na roztrząsanie, chciałbym przejść do wstępnego filtrowania obu obrazów (szablon, którego szukasz, i obraz, który jest twoją przestrzenią wyszukiwania). W zależności od właściwości ditheringu, możesz zacząć eksperymentować z prostym rozmyciem w pudełku i prawdopodobnie przejść do filtra medianowego z małym jądrem (3 x 3), jeśli to nie działa. Dzięki temu nie uzyskasz 100% identyczności między szablonem a wyszukiwanym obrazem, ale solidne wyniki liczbowe, które możesz porównywać.

Edycja w świetle uwag

Rozumiem, że (1) chcesz coś bardziej solidnego, bardziej „CV-like” i trochę bardziej fantazyjny jako rozwiązanie, i że (2), które są sceptycznie nastawiony do uzyskania niezmienności skali, po prostu skanując duży stos różnych skal.

Jeśli chodzi o (1), podejściem kanonicznym jest, jak wspomniano powyżej, stosowanie deskryptorów cech. Deskryptory funkcji nie opisują pełnego obrazu (lub kształtu), ale niewielką część obrazu w sposób niezmienny względem różnych transformacji. Spójrz na SIFT i SURF i VLFeat, który ma dobrą implementację SIFT, a także implementuje MSER i HOG (i jest znacznie mniejszy niż OpenCV). SURF jest łatwiejszy do wdrożenia niż SIFT, oba są mocno opatentowane. Oba mają wersję "pionową", która nie ma niezmienności obrotu. To powinno zwiększyć solidność w twojej sprawie.

Strategia opisana w komentarzu idzie bardziej w kierunku deskryptorów kształtu niż deskryptorów cech obrazu. Upewnij się, że rozumiesz różnicę między nimi! Deskryptory kształtu 2D mają na celu kształty, które są zazwyczaj opisywane przez obrys lub maskę binarną. Deskryptory cech obrazu (w znaczeniu użycia powyżej) mają na celu obrazy o wartościach intensywności, zwykle fotografie. Ciekawym deskryptorem kształtu jest shape context, wiele innych inne są podsumowane here. Nie sądzę, że twój problem najlepiej rozwiązują deskryptory kształtu, ale może coś źle zrozumiałem. Byłbym bardzo ostrożny z deskryptorami kształtu na krawędziach obrazu, ponieważ krawędzie, będące pierwszymi pochodnymi, mogą być silnie zmienione przez dithering noise.

Odnośnie (2): Chciałbym Cię przekonać, że skanowanie w wielu różnych skalach to nie tylko głupi hack dla tych, którzy nie znają Computer Vision! Właściwie to ma dużo wizji, mamy po prostu wymyślną nazwę, aby wprowadzić w błąd niezainicjowane wyszukiwanie - scale space. To trochę uproszczenie, ale tak naprawdę tylko trochę. Większość deskryptorów cech obrazu, które są używane w praktyce, pozwala uzyskać niezmienność skali przy użyciu przestrzeni skali, która jest stosem coraz bardziej przeskalowanych (i filtrowanych dolnoprzepustowo) obrazów. Jedyną sztuczką, którą dodają, jest szukanie ekstremów w przestrzeni skali i obliczanie deskryptorów tylko w tych ekstremach. Wciąż jednak cała przestrzeń skalowania jest obliczana i przesuwana, aby znaleźć te ekstrema. Zajrzyj do original SIFT paper, aby uzyskać dobre wyjaśnienie.

Answer 2

Nice. Kiedyś zaimplementowałem cheat w grze flash przechwytując ekran także :). Jeśli chcesz znaleźć dokładną granicę, którą dałeś na obrazku, możesz utworzyć filtr kolorów, usuwając całą resztę, a skończysz z obrazem binarnym, który możesz wykorzystać do dalszego przetwarzania (zadaniem, które należy wykonać, będzie znalezienie pasujący prostokąt z pewnym współczynnikiem granicy.Możesz także zaimplementować cztery jądra, które znajdą narożniki w kilku różnych skalach:

Jeśli masz strumień obrazów i wiesz, że jest ruch, możesz także monitorować różnicę między ramki do przechwytywania części akcji na ekranie za pomocą rozwiązania do modelowania tła Połącz je, a otrzymasz dość daleko, jak sądzę, bez uciekania się do bardziej egzotycznych metod, takich jak analiza wielowariantowa i takie tam ...

Czy wydajność jest problemem? Mój cheat używał około 20 fps jako to musiałem szybko kliknąć piłkę.

Answer 3

Odpowiadam z odpowiedzią na moje własne pytanie, aby ludzie wiedzieli, gdzie skończyłem.

---

nie Stwierdziwszy lub zdobyć jakieś wskazówki na temat mojego poszukiwanego magia skalę niezmienny kształt deskryptorze, postanowiłem pójść z radą DCS”i wykonać prawie prostą wyszukiwanie pikseli w całym ekranie.

Najpierw szukałem kawałka 512 x 60 logo. Ale okazuje się, że to, co w końcu jest quadową pętlą zagnieżdżoną (wiersze/kolumny pełnego obrazu x wierszy/kolumn obrazu wyszukiwania) działałoby przez ponad godzinę, w najgorszym przypadku.Gorszący.

Udało mi się zmniejszyć skalę problemu, wybierając mniejszy obraz wyszukiwania, o rozmiarze około 48 x 32 pikseli. Zabrało mi to, jak sądzę, około 30 sekund i było wolniejsze, niż bym chciał. Poza tym czas będzie wzrastał, gdy później spróbowałem szukać innych funkcji.

Moim rozwiązaniem było wyszukiwanie tylko pojedynczej linii skanowania mojego obrazu wyszukiwania, a nawet tego przez serwer proxy, a nie całkowicie. Ze względu na komiksową naturę obrazu, którego szukałem, zdecydowałem, że średnie odcienie kolorów przyniosą porządne proxy dla pikseli, których szukałem. Wybrałem "środkową" linię obrazu wyszukiwania, wyodrębniłem barwę (jako liczbę całkowitą od 0 do 7200) dla każdego piksela i obliczyłem sumę tych wartości odcienia. W obrazie ekranowym obliczyłem ruchomy wynik względem liczby pikseli odpowiadającej szerokości szukanego obrazu, więc dla każdej pozycji piksela wystarczy odjąć najstarszy piksel i dodać jeden nowy. Wykorzystanie Java Color.rgbToHSB pozostawia pewien potencjał optymalizacji, szczególnie w świetle konwersji na float iz powrotem, ale cały ekran może być wstępnie próbkowany w kilkaset ms.

Tak więc utworzyłem listę różnic między sumami odcieni ekranu i dla mojej środkowej linii wyszukiwania, znalazłem najlepszą (tj. Najmniejszą) różnicę, a następnie zrobiłem pełne porównanie piksel po piksie dla pozycji, które podzieliły pierwsze miejsce dla najlepszej różnicy. Zwykle było mniej niż 10 takich optymalnych dopasowań kolorów, więc porównanie 10 pikseli po pikselu trwało niewiele dłużej.

Teraz znajduję mój obraz wyszukiwania w ciągu około pół sekundy, przy wciąż niewykorzystanym potencjale optymalizacji. Jeśli potrzebuję "zrobić" więcej różnych skal, mam nadzieję, że różne rozdzielczości pozwolą mi wybrać inny obraz wyszukiwania bez prób i błędów, ale w najgorszym przypadku tylko niewielka część pracy porównawczej musi zostać uruchomiona wiele razy, a ja spodziewaj się, że pozostaniesz pod sekundą.

Nie spotkałem się z moim pierwotnym celem, jakim jest bardzo duża odporność na różne roztoki (tj. Szczegółowe interpretacje pikseli) moich poszukiwanych obrazów; mój algorytm wymaga dobrego dopasowania kolorów. Ale biorąc pod uwagę, jak trudny byłby to problem, zdecydowałem, że przekroczę ten most, jeśli kiedykolwiek będę musiał.