Jak znaleźć Waldo z Mathematica?

1542

Martwiło mnie to w weekend: co to jest dobry sposób na rozwiązanie problemu Where's Waldo? Zagadki [ „Wally” poza Ameryką Północną] przy użyciu Mathematica (przetwarzanie obrazu i inne funkcje)?

Oto, co mam do tej pory, funkcja, która nieco zmniejsza złożoność wizualną, ściemniając niektóre nie-czerwone kolory:

whereIsWaldo[url_] := Module[{waldo, waldo2, waldoMask},
    waldo = Import[url];
    waldo2 = Image[ImageData[
        waldo] /. {{r_, g_, b_} /;
          Not[r > .7 && g < .3 && b < .3] :> {0, 0,
          0}, {r_, g_, b_} /; (r > .7 && g < .3 && b < .3) :> {1, 1,
          1}}];
    waldoMask = Closing[waldo2, 4];
    ImageCompose[waldo, {waldoMask, .5}]
]

I przykład adresu URL, w którym to „działa”:

whereIsWaldo["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"]

(Waldo jest przy kasie):

Oryginalny obraz

Grafika matematyczna

Arnoud Buzing
źródło
31
@yoda - lewy górny róg, stół z dużą ilością butów, kasa i Waldo w pobliżu rogu stołu.
Arnoud Buzing,
8
Jako doktorant w dziedzinie komputerowej wizji jestem tak pokusą, by spróbować, ale muszę się opierać. Do tego, co warto, wybrałbym histogram zorientowanych gradientów + przesuwne okno SVM, jak w tej bardzo wpływowej pracy (ostrzeżenie: pdf).
dimatura
54
„Where's Wally ”. >. <
Wyścigi lekkości na orbicie
2
Czy możemy zmienić pytanie, aby obsługiwać również inne języki? Myślałem o zrobieniu tego z
Matlabem
2
@ArnoudBuzing: W swoim pytaniu możesz znaleźć Waldo, patrząc na wybór, który ma najwięcej bieli. : /
Tamara Wijsman

Odpowiedzi:

1640

Znalazłem Waldo!

Waldo zostało znalezione

Jak to zrobiłem

Najpierw odfiltrowuję wszystkie kolory, które nie są czerwone

waldo = Import["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"];
red = Fold[ImageSubtract, #[[1]], Rest[#]] &@ColorSeparate[waldo];

Następnie obliczam korelację tego obrazu za pomocą prostego czarno-białego wzoru, aby znaleźć czerwono-białe przejścia w koszuli.

corr = ImageCorrelate[red, 
   Image@Join[ConstantArray[1, {2, 4}], ConstantArray[0, {2, 4}]], 
   NormalizedSquaredEuclideanDistance];

Używam, Binarizeaby wybrać piksele na obrazie z wystarczająco wysoką korelacją i narysować wokół nich biały okrąg, aby podkreślić je za pomocąDilation

pos = Dilation[ColorNegate[Binarize[corr, .12]], DiskMatrix[30]];

Musiałem trochę pobawić się poziomem. Jeśli poziom jest zbyt wysoki, wybieranych jest zbyt wiele fałszywych alarmów.

Wreszcie łączę ten wynik z oryginalnym obrazem, aby uzyskać wynik powyżej

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]
Heike
źródło
52
@MikeBantegui Chociaż rozwiązanie Heike jest świetne, nie byłbym tak szybki w pakowaniu go w WhereIsWaldofunkcję, ponieważ nie jest to ogólne rozwiązanie. Heike sama zwróciła uwagę, że poziomy należy rozegrać, aby uzyskać pozytywny wynik. Aby zobaczyć, co mam na myśli, wypróbuj swoją spakowaną funkcję w takiej postaci, w jakiej jest dostępna. "http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/AtTheBeach.jpg"Z tym jest trudniej.
abcd
17
To zdjęcie jest trudniejsze: Waldo . Myślę jednak, że posiadanie czegoś, co może podkreślić potencjalnego Waldosa, jest nadal przydatne (dla pewnej definicji „użyteczne”.) (Przypomina mi to niektóre rzeczy, które iPhoto czasami rozpoznaje jako twarz w naszej kolekcji zdjęć ...)
Brett Champion,
33
Proszę zobaczyć ten post Meta: meta.stackexchange.com/questions/116401/…
Bill the Lizard
155
Wygląda na to, że źle zrozumiałeś zasady Where's Waldo. To wyraźnie oszustwo.
Stefan Kendall,
91
Chociaż jest to dobry hack, po prostu nie działa. Wymaga ręcznego strojenia i działa tylko na jednym zdjęciu. Nie rozumiem, dlaczego jest to głosowane, a nawet wybrane jako odpowiedź. Odradza to wszystkim, którzy próbują odpowiedzieć przy pomocy lepszych metod pracy.
sam hocevar,
144

Domyślam się, że jest to „kuloodporny sposób” (pomyśl CIA znajdując Waldo na dowolnym zdjęciu satelitarnym w dowolnym momencie, a nie tylko na jednym zdjęciu bez konkurujących elementów, takich jak koszule w paski) ... Trenowałbym maszynę Boltzmanna na wielu zdjęciach Waldo - wszystkie jego odmiany siedzące, stojące, okludowane itp .; koszula, kapelusz, aparat i wszystkie prace. Nie potrzebujesz dużego korpusu Waldosa (może 3-5 wystarczy), ale im więcej, tym lepiej.

Spowoduje to przypisanie chmur prawdopodobieństwa różnym elementom występującym w dowolnym prawidłowym układzie, a następnie ustalenie (poprzez segmentację), jaki jest średni rozmiar obiektu, fragment obrazu źródłowego na komórki obiektów, które najbardziej przypominają poszczególne osoby (biorąc pod uwagę możliwe niedrożności i zmiany pozy) ), ale ponieważ zdjęcia Waldo zwykle obejmują dużą liczbę osób w mniej więcej tej samej skali, powinno to być bardzo łatwe zadanie, a następnie nakarmić te segmenty wstępnie przeszkolonej maszyny Boltzmann. To da ci prawdopodobieństwo, że każdy będzie Waldo. Wybierz jedno z najwyższym prawdopodobieństwem.

Tak działają dziś OCR, czytniki kodów pocztowych i rozpoznawanie pisma ręcznego. Zasadniczo wiesz, że odpowiedź jest dostępna, wiesz mniej więcej, jak powinna ona wyglądać, i wszystko inne może mieć wspólne elementy, ale zdecydowanie jest to „nie to”, więc nie zawracaj sobie głowy „nie to”, wystarczy spojrzeć na prawdopodobieństwo „tego” spośród wszystkich możliwych „to, co widzieliście wcześniej” (na przykład w kodach pocztowych trenowałbyś BM tylko przez 1s, tylko przez 2s, tylko przez 3s itd., a następnie nakarmiłeś każdego cyfry na każdej maszynie i wybierz tę, która ma największą pewność). Działa to znacznie lepiej niż funkcje uczenia wszystkich sieci neuronowych wszystkich liczb.

Gregory Klopper
źródło
13
Czy nie wystarczą do tego zwykłe sieci neuronowe? Poza tym artykuł w Wikipedii twierdzi, że maszyny Boltzmanna nie są praktyczne.
GClaramunt,
2
Bez próby nie jestem pewien, ale jeśli wystarczająco duża i wystarczająco złożona, sieć neuronowa powinna wystarczyć na WSZYSTKO. Zwłaszcza w przypadku nawrotów. Maszyny Boltzmann radzą sobie BARDZO BARDZO BARDZO BARDZO BARDZO BARDZO dobrze w rozpoznawaniu dość uproszczonego zestawu danych z dużym poziomem szumów w morzu danych w przeciwieństwie do siebie.
Gregory Klopper,
14
Kody pocztowe są odczytywane przez maszyny Boltzmann przez cały czas, a dokładność dostarczania poczty przeszła przez dach.
Gregory Klopper,
47

Zgadzam się z @GregoryKlopper, że właściwym sposobem rozwiązania ogólnego problemu znalezienia Waldo (lub dowolnego przedmiotu będącego przedmiotem zainteresowania) na dowolnym obrazie byłoby wyszkolenie nadzorowanego klasyfikatora uczenia maszynowego. Korzystając z wielu przykładów oznaczonych pozytywnie i negatywnie, algorytm, taki jak maszyna wektorów wsparcia , kikut decyzyjny lub maszyna Boltzmanna, można prawdopodobnie wyszkolić w celu uzyskania wysokiej dokładności tego problemu. Mathematica zawiera nawet te algorytmy w swoim Machine Learning Framework .

Dwa wyzwania związane ze szkoleniem klasyfikatora Waldo to:

  1. Określanie właściwej transformacji funkcji obrazu. W tym miejscu przydatna byłaby odpowiedź @ Heike: czerwony filtr i wykrywacz pasków (np. Rozkład falkowy lub DCT) byłyby dobrym sposobem na przekształcenie surowych pikseli w format, z którego algorytm klasyfikacji mógłby się uczyć. Wymagany byłby również rozkład oparty na blokach, który ocenia wszystkie podsekcje obrazu ... ale ułatwia to fakt, że Waldo jest a) zawsze mniej więcej tego samego rozmiaru ib) zawsze występuje dokładnie raz na każdym obrazie.
  2. Uzyskanie wystarczającej liczby przykładów szkoleń. Maszyny SVM działają najlepiej z co najmniej 100 przykładami każdej klasy. Komercyjne zastosowania wzmocnienia (np. Ustawianie ostrości w aparatach cyfrowych) są szkolone na milionach pozytywnych i negatywnych przykładów.

Szybka wyszukiwarka grafiki Google ujawnia kilka dobrych danych - spróbuję zebrać kilka przykładów szkoleniowych i teraz je kodować!

Jednak nawet podejście oparte na uczeniu maszynowym (lub oparte na regułach sugerowane przez @iND) będzie walczyć o wizerunek taki jak Kraina Waldos !

lubar
źródło
Komputerowy system wizyjny oparty na uczeniu maszynowym, który próbuje rozwiązać problem „Where's Waldo” w świecie rzeczywistym (tj. Znalezienie konkretnej osoby na zdjęciach tłumu na Flickr) został zaprezentowany na konferencji Computer Vision and Pattern Recognition w zeszłym roku. Trochę oszukują, dodając informacje o lokalizacji 3D, używając wielu zdjęć tej samej sceny.
lubar
41

Nie znam Mathematiki. . . szkoda. Ale w większości podoba mi się powyższa odpowiedź.

Nadal istnieje poważna wada polegania na samych paskach , aby uzyskać odpowiedź (osobiście nie mam problemu z jedną ręczną regulacją). Jest to przykład (wymienione Brett Champion o ) przedstawiono w którym pokazano, że czasami przerywają wzór koszuli. Zatem staje się bardziej złożonym wzorcem.

Spróbowałbym podejścia do identyfikatora kształtu i kolorów oraz relacji przestrzennych. Podobnie jak rozpoznawanie twarzy, możesz szukać wzorów geometrycznych w określonych proporcjach od siebie. Zastrzeżenie polega na tym, że zwykle jeden lub więcej z tych kształtów jest zasłonięty.

Uzyskaj balans bieli na obrazie, a czerwony - balans czerwony na obrazie. Uważam, że Waldo ma zawsze tę samą wartość / odcień, ale obraz może pochodzić ze skanu lub złej kopii. Następnie zawsze odwołuj się do tablicy kolorów, którą faktycznie jest Waldo: czerwony, biały, ciemnobrązowy, niebieski, brzoskwiniowy, {kolor buta}.

Jest wzór koszuli, a także spodnie, okulary, włosy, twarz, buty i czapka, które definiują Waldo. Ponadto, w porównaniu do innych osób na zdjęciu, Waldo jest chudy.

Znajdź przypadkowych ludzi, aby uzyskać wzrost osób na tym zdjęciu. Zmierz średnią wysokość wiązki rzeczy w losowych punktach obrazu (prosty kontur da całkiem sporo pojedynczych osób). Jeśli każda rzecz nie mieści się w jakimś standardowym odchyleniu od siebie, na razie są one ignorowane. Porównaj średnią wysokości z wysokością obrazu. Jeśli stosunek jest zbyt duży (np. 1: 2, 1: 4 lub podobnie zamknięty), spróbuj ponownie. Uruchom to 10 (?) Razy, aby upewnić się, że próbki są całkiem blisko siebie, z wyłączeniem jakiejkolwiek średniej, która jest poza pewnym odchyleniem standardowym. Możliwe w Mathematica?

To jest twój rozmiar Waldo. Walso jest chudy, więc szukasz czegoś 5: 1 lub 6: 1 (lub cokolwiek) ht: wd. To jednak nie wystarczy. Jeśli Waldo jest częściowo ukryty, wysokość może się zmienić. Więc szukasz bloku czerwono-białego, który ~ 2: 1. Ale musi być więcej wskaźników.

  1. Waldo ma okulary. Wyszukaj dwa okręgi 0,5: 1 nad czerwono-białym.
  2. Niebieskie spodnie. Każda ilość niebieskiego na tej samej szerokości w dowolnej odległości między końcem czerwono-białym a odległością do jego stóp. Pamiętaj, że nosi krótką koszulę, więc stopy nie są zbyt blisko.
  3. Kapelusz Czerwono-biała w dowolnej odległości do dwukrotności czubka głowy. Pamiętaj, że musi mieć ciemne włosy poniżej i prawdopodobnie okulary.
  4. Długie rękawy. czerwono-biały pod pewnym kątem od głównego czerwono-białego.
  5. Ciemne włosy.
  6. Kolor buta. Nie znam koloru.

Każdy z nich może mieć zastosowanie. Są to również kontrole negatywne w stosunku do podobnych osób na zdjęciu - np. # 2 neguje noszenie czerwono-białego fartucha (zbyt blisko butów), # 5 eliminuje jasne włosy. Również kształt jest tylko jednym wskaźnikiem dla każdego z tych testów. . . sam kolor w określonej odległości może dać dobre wyniki.

To zawęzi obszary do przetworzenia.

Przechowywanie tych wyników wytworzy zestaw obszarów, w których powinien znajdować się Waldo. Wyklucz wszystkie pozostałe obszary (np. Dla każdego obszaru wybierz krąg dwa razy większy niż średni rozmiar osoby), a następnie uruchom proces, który @Heike określił, usuwając wszystkie oprócz czerwonego i tak dalej.

Masz jakieś przemyślenia na temat tego, jak to kodować?


Edytować:

Myśli, jak to zakodować. . . wyklucz wszystkie obszary oprócz Waldo czerwonego, szkieletuj czerwone obszary i przycinaj je do jednego punktu. Zrób to samo dla włosów brązowych Waldo, niebieskich spodni Waldo, koloru butów Waldo. W przypadku koloru skóry Waldo wyklucz, a następnie znajdź kontur.

Następnie wyklucz inne niż czerwone, rozszerz (wszystkie) wszystkie czerwone obszary, a następnie szkieletuj i przycinaj. Ta część da listę możliwych punktów środkowych Waldo. Będzie to marker do porównania wszystkich innych sekcji kolorów Waldo.

Stąd, używając szkieletowych czerwonych obszarów (nie rozszerzonych), policz linie w każdym obszarze. Jeśli jest poprawna liczba (cztery, prawda?), Jest to z pewnością możliwy obszar. Jeśli nie, wydaje mi się, że po prostu go wykluczam (ponieważ jest to ośrodek Waldo… może to być jego kapelusz).

Następnie sprawdź, czy powyżej znajduje się kształt twarzy, punkt włosów powyżej, spodnie poniżej, buty poniżej itd.

Nie ma jeszcze kodu - nadal czytam dokumenty.

iND
źródło
8
Być może możesz pokazać dowód koncepcji w dowolnym znanym systemie / języku. Dzięki temu poczujesz, gdzie mogą pojawić się trudności.
Szabolcs
1
Och, po prostu cieszę się z tego wyzwania. Daje mi to coś pomiędzy spacerami po plaży i ubieraniem się na obiad.
iND
1
Więc. . . dlaczego opinie negatywne? Czym różni się to od innej spekulatywnej odpowiedzi tutaj? Czy to sugeruje, że pytanie to należy potraktować poważniej? A może po prostu powinienem wydawać się poważniejszy w moim dochodzeniu? Czy moje podejście jest rzeczywiście złe?
iND
3
Nie głosowałem za tobą i nie uważam, by opinie oddane były odpowiednie dla uczciwych prób udzielenia odpowiedzi (chyba że zawierają one błędne informacje). Najbardziej prawdopodobnym powodem głosów negatywnych jest to, że nie wypróbowałeś (dość skomplikowanego brzmienia) podejścia, a znalezienie dobrego rozwiązania prawdopodobnie wymagałoby sporo praktycznych eksperymentów i wykluczenia wielu pomysłów. Druga odpowiedź spekulatywna sugeruje ogólną metodę (jako punkt wyjścia), która była stosowana w przeszłości do podobnych problemów i jest w niej sporo literatury. Próbuję tylko wyjaśnić, co się stało.
Szabolcs
Dziękuję za wyjaśnienie. Chyba nie skupiam się na historii pomysłów.
iND
2

Mam szybkie rozwiązanie do znalezienia Waldo za pomocą OpenCV.

Użyłem funkcji dopasowania szablonu dostępnej w OpenCV, aby znaleźć Waldo.

Aby to zrobić, potrzebny jest szablon. Więc wyciąłem Waldo z oryginalnego obrazu i użyłem go jako szablonu.

wprowadź opis zdjęcia tutaj

Następnie wywołałem cv2.matchTemplate()funkcję wraz ze znormalizowanym współczynnikiem korelacji jako zastosowaną metodą. Zwrócił wysokie prawdopodobieństwo w jednym regionie, jak pokazano na biało poniżej (gdzieś w lewym górnym obszarze):

wprowadź opis zdjęcia tutaj

Pozycja najwyższego prawdopodobnego regionu została znaleziona za pomocą cv2.minMaxLoc()funkcji, której następnie użyłem do narysowania prostokąta, aby podświetlić Waldo:

wprowadź opis zdjęcia tutaj

Jeru Luke
źródło
7
Próbujesz rozwiązać najsłynniejsze pytania SO dotyczące przetwarzania obrazu? ;) Twoje rozwiązanie jest ładne i łatwe, ale a / działa tylko dla tego konkretnego obrazu ib / potrzebuje dokładnego obrazu Waldo, który chcesz wcześniej znaleźć, podczas gdy myślę, że pytanie dotyczyło znalezienia dowolnego Waldo w dowolnym „Where's Waldo image”, takim jak grałbyś w normalną grę: nie wiedząc wcześniej, jak on wygląda. To pytanie i tak sprawia dużo radości
Soltius
@Solitus ha dokładnie !!! Pracowałem tylko dla tego obrazu. Praca nad różnymi obrazami byłaby jednak wyzwaniem !!
Jeru Luke,