Jak znaleźć Waldo z Mathematica?

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

Znalazłem Waldo!

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

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.

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 !

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.

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.

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

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: