Vraag Hoe vind ik Waldo met Mathematica?


Dit irriteerde me tijdens het weekend: wat is een goede manier om die op te lossen Waar is Waldo?  ['Wally' buiten Noord-Amerika] puzzels, met behulp van Mathematica (beeldverwerking en andere functionaliteit)?

Dit is wat ik tot nu toe heb gedaan, een functie die de visuele complexiteit een beetje verlaagt door te dimmen enkele van de niet-rode kleuren:

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

En een voorbeeld van een URL waar dit 'werkt':

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

(Waldo is bij de kassa):

Mathematica graphic


1511
2017-12-12 18:29


oorsprong


antwoorden:


Ik heb Waldo gevonden!

waldo had been found

Hoe ik het heb gedaan

Eerst filter ik alle kleuren eruit die niet rood zijn

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

Vervolgens bereken ik de correlatie van deze afbeelding met een eenvoudig zwart-wit patroon om de rode en witte overgangen in het shirt te vinden.

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

ik gebruik Binarize om de pixels in de afbeelding uit te kiezen met een voldoende hoge correlatie en een witte cirkel om hen heen te tekenen om ze te benadrukken met Dilation

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

Ik moest een beetje met het niveau spelen. Als het niveau te hoog is, worden te veel valse positieven gekozen.

Eindelijk combineer ik dit resultaat met de originele afbeelding om het resultaat hierboven te krijgen

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]

1624
2017-12-12 19:32



Mijn gok op een "kogelvrije manier om dit te doen" (denk aan de CIA die Waldo op elk moment in een satellietbeeld vindt, niet alleen een enkel beeld zonder concurrerende elementen, zoals gestreepte shirts) ... Ik zou een Boltzmann-machine op veel afbeeldingen van Waldo - alle variaties van hem zittend, staand, verstopt, enz .; shirt, hoed, camera en alle werken. Je hebt geen groot corpus Waldos nodig (misschien is 3-5 voldoende), maar hoe meer hoe beter.

Hierdoor worden wolken van waarschijnlijkheden toegewezen aan verschillende elementen die voorkomen in de juiste opstelling, en vervolgens (via segmentatie) vaststellen wat een gemiddelde objectgrootte is, het bronbeeld fragmenteren in cellen van objecten die het meest op individuele personen lijken (rekening houdend met mogelijke occlusies en posewijzigingen) ), maar omdat Waldo-foto's over het algemeen VEEL mensen op ongeveer dezelfde schaal bevatten, zou dit een zeer eenvoudige taak moeten zijn, en dan deze segmenten van de vooraf opgeleide Boltzmann-machine voeden. Het geeft je de kans dat iedereen Waldo is. Neem er een met de hoogste waarschijnlijkheid.

Dit is hoe OCR, ZIP-codelezers en strokenloze handschriftherkenning vandaag werken. Eigenlijk weet je dat het antwoord er is, je weet min of meer hoe het eruit moet zien, en al het andere kan gemeenschappelijke elementen hebben, maar het is zeker "not it", dus je hoeft je niet druk te maken over de "not it" s, jij kijk gewoon naar de waarschijnlijkheid van "it" tussen alle mogelijke "it" s die je eerder hebt gezien "(in ZIP-codes bijvoorbeeld, zou je BM trainen voor slechts 1 sec, slechts 2 sec, slechts 3 sec, enz., dan elke feed voeden cijfer voor elke machine en kies er een die het meeste vertrouwen heeft.) Dit werkt een stuk beter dan een enkele leerfunctie van alle nummers van het neurale netwerk.


140
2017-12-12 20:25



Ik ben het eens met @GregoryKlopper dat de rechts manier om het algemene probleem op te lossen van het vinden van Waldo (of een object van belang) in een willekeurige afbeelding zou zijn om een ​​onder toezicht staande machine te leren classificator te trainen. Met behulp van veel positieve en negatieve gelabelde voorbeelden, een algoritme zoals Ondersteuning Vector Machine, Boosted Decision Stump of Boltzmann Machine kan waarschijnlijk worden getraind om een ​​hoge nauwkeurigheid van dit probleem te bereiken. Mathematica bevat zelfs deze algoritmen in zijn Machine Learning Framework.

De twee uitdagingen met het trainen van een Waldo-classifier zouden zijn:

  1. Bepaling van de juiste beeldfunctie-transformatie. Dit is waar het antwoord van @ Heike nuttig zou zijn: een rood filter en een gestripte patroondetector (bijvoorbeeld rimpel- of DCT-decompositie) zou een goede manier zijn om onbewerkte pixels om te zetten in een indeling die het classificatie-algoritme zou kunnen leren. Een blokgebaseerde decompositie die alle subsecties van de afbeelding beoordeelt, zou ook nodig zijn ... maar dit wordt gemakkelijker gemaakt door het feit dat Waldo a) altijd ongeveer dezelfde grootte heeft en b) altijd exact één keer in elke afbeelding aanwezig is.
  2. Het verkrijgen van voldoende trainingsvoorbeelden. SVM's werken het beste met minstens 100 voorbeelden van elke klas. Commerciële toepassingen van boosting (bijvoorbeeld face-focusing in digitale camera's) worden getraind in miljoenen positieve en negatieve voorbeelden.

Een snelle Google afbeeldingen zoeken levert goede gegevens op - ik ga een aantal trainingsvoorbeelden verzamelen en dit nu coderen!

Zelfs een machine-leerbenadering (of de op regels gebaseerde benadering voorgesteld door @iND) zal echter worstelen met een afbeelding als de Land van Waldos!


46
2018-04-01 01:23



Ik ken Mathematica niet. . . jammer. Maar ik vind het antwoord hierboven voor het grootste deel leuk.

Toch is er een grote fout in het vertrouwen op de strepen alleen om het antwoord te verzamelen (ik heb er persoonlijk geen probleem mee een handmatige aanpassing). Er is een voorbeeld (vermeld door Brett Champion, hier) gepresenteerd waaruit blijkt dat ze soms het shirtpatroon doorbreken. Dus dan wordt het een complexer patroon.

Ik zou een benadering van vorm-id en kleuren proberen, samen met ruimtelijke relaties. Heel erg zoals gezichtsherkenning, kon u geometrische patronen bij bepaalde verhoudingen van elkaar zoeken. Het voorbehoud is dat meestal een of meer van die vormen zijn geoccludeerd.

Krijg een witbalans op de afbeelding en rood een rode balans in de afbeelding. Ik geloof dat Waldo altijd dezelfde waarde / tint heeft, maar de afbeelding kan afkomstig zijn van een scan of een slechte kopie. Raadpleeg dan altijd een reeks kleuren die Waldo eigenlijk is: rood, wit, donkerbruin, blauw, perzik, {schoenkleur}.

Er is een hemdpatroon, en ook de broek, bril, haar, gezicht, schoenen en hoed die Waldo bepalen. Ook ten opzichte van andere mensen in de afbeelding, Waldo is aan de magere kant.

Zoek dus willekeurige mensen om de hoogte van mensen in deze foto te krijgen. Meet de gemiddelde hoogte van een aantal dingen op willekeurige punten in de afbeelding (een eenvoudige omtrek levert nogal wat individuele mensen op). Als elk ding niet binnen een standaardafwijking van elkaar valt, worden ze voorlopig genegeerd. Vergelijk het gemiddelde van de hoogte met de hoogte van het beeld. Als de verhouding te groot is (bijvoorbeeld 1: 2, 1: 4 of vergelijkbaar sluiten), probeert u het opnieuw. Voer het 10 (?) Van de tijd uit om te zorgen dat de monsters allemaal vrij dicht bij elkaar staan, met uitzondering van een gemiddelde dat buiten een standaardafwijking valt. Mogelijk in Mathematica?

Dit is jouw Waldo-maat. Walso is mager, dus je bent op zoek naar iets 5: 1 of 6: 1 (of wat dan ook) ht: wd. Dit is echter niet voldoende. Als Waldo gedeeltelijk verborgen is, kan de hoogte veranderen. Dus je bent op zoek naar een blok rood-wit dat ~ 2: 1 is. Maar er moeten meer indicatoren zijn.

  1. Waldo heeft een bril. Zoek naar twee cirkels 0,5: 1 boven het rood-wit.
  2. Blauwe broek. Elke hoeveelheid blauw op dezelfde breedte binnen elke afstand tussen het einde van het rood-witte en de afstand tot zijn voeten. Merk op dat hij zijn hemd kort draagt, zodat de voeten niet te dichtbij zijn.
  3. De hoed. Rood-wit op elke afstand tot tweemaal de bovenkant van zijn hoofd. Merk op dat het donker haar hieronder en waarschijnlijk een bril moet hebben.
  4. Lange mouwen. rood-wit onder een bepaalde hoek van het hoofd rood-wit.
  5. Donker haar.
  6. Schoen kleur. Ik ken de kleur niet.

Al deze kunnen van toepassing zijn. Dit zijn ook negatieve controles tegen vergelijkbare mensen op de foto - bijv. # 2 ontkent het dragen van een rood-witte schort (te dicht bij schoenen), # 5 elimineert licht gekleurd haar. De vorm is ook slechts één indicator voor elk van deze tests. . . kleur alleen binnen de opgegeven afstand kan goede resultaten opleveren.

Dit verkleint de te verwerken gebieden.

Als u deze resultaten opslaat, krijgt u een aantal gebieden die dat zijn moeten heb Waldo erin. Sluit alle andere gebieden uit (selecteer bijvoorbeeld voor elk gebied een cirkel die twee keer zo groot is als de gemiddelde persoonslengte) en voer vervolgens het proces uit dat @Heike opgemaakt heeft met alles behalve rood, enzovoort.

Eventuele gedachten over hoe dit te coderen?


Bewerk:

Gedachten over hoe dit te coderen. . . sluit alle gebieden behalve Waldo-rood uit, skeletoniseer de rode gebieden en snijd ze tot een enkel punt. Doe hetzelfde voor Waldo-haarbruin, Waldo-broekblauw, Waldo-schoenkleur. Voor Waldo huidskleur, exclusief, zoek dan de omtrek.

Sluit vervolgens niet-rood uit, verwijd (veel) alle rode gebieden, skeletoniseer vervolgens en snoei. Dit deel geeft een lijst met mogelijke Waldo-middelpunten. Dit is de markering om alle andere Waldo-kleursecties te vergelijken met.

Vanaf hier tel je de lijnen in elk gebied met behulp van de gerafelde rode gebieden (niet de uitgezette). Als er het juiste aantal is (vier, toch?), Is dit zeker een mogelijk gebied. Zo niet, dan denk ik dat ik het gewoon uitsluit (omdat het een Waldocentrum is ... het kan nog steeds zijn hoed zijn).

Controleer vervolgens of er een gezichtsvorm hierboven is, een haarpunt erboven, de punt van de broek eronder, de schoenpunten eronder, enzovoort.

Nog geen code - nog steeds de documentatie lezen.


40
2018-01-10 09:36



Ik heb een snelle oplossing voor het vinden van Waldo met behulp van OpenCV.

Ik gebruikte de sjabloonafstemming functie beschikbaar in OpenCV om Waldo te vinden.

Hiervoor is een sjabloon nodig. Dus ik heb Waldo uit de originele afbeelding gesneden en als sjabloon gebruikt.

enter image description here

Vervolgens belde ik de cv2.matchTemplate() functie samen met de genormaliseerde correlatiecoëfficiënt als de gebruikte methode. Het keerde terug naar een enkele regio, zoals hieronder in het wit wordt weergegeven (ergens in de regio linksboven):

enter image description here

De positie van het hoogst waarschijnlijke gebied werd gevonden met behulp van cv2.minMaxLoc() functie, die ik toen gebruikte om de rechthoek te tekenen om Waldo te laten zien:

enter image description here


3
2018-04-11 11:11