[ALG] Ingekleurde vlakken vergelijken

[Deviruchi]

Ik ben momenteel bezig met een project voor school, en wij zijn bezig om een Paint-game te maken. De bedoeling is dat er doormiddel van een Wii-mote een tekening ingekleurd wordt. Vervolgens berekend het spel je score uit, door middel van hoeveel % je van een vlak hebt ingekleurd, en hoeveel je over de lijnen hebt gekleurd. De precieze berekening van de score hebben we nog niet, maar dat is momenteel nog niet het probleem.

Wij zitten momenteel met het vraagstuk hoe we dit moeten gaan doen. Ik heb ter illustratie de volgende afbeelding toegevoegd.



De bedoeling is dus dat de vakken ingevuld worden met de aangegeven kleur. We weten hoe we dit werkend moeten krijgen, en hebben dat op dit moment ook. Vervolgens is het de bedoeling dat aan de hand van de tekening van de gebruiken, een score berekend wordt. Wij kunnen echter geen manier bedenken om vast te stellen hoeveel procent van het vlak is ingekleurd, en hoeveel er over de lijnen is gegaan.

Ons eerste idee was om een grid van bijv. 10 bij 10px over het gehele speelveld heen te leggen. Bij elk vlak in de grid wordt dan de gemiddelde waarde berekend, en zo kunnen we kijken of een vlak goed ingekleurd is. Er zitten hier een aantal nadelen aan, bijvoorbeeld dat het bij een object wat geen vierkant is, het lastig te bepalen is wat de kleur is, omdat het grid altijd vierkant is.

We kunnen echter geen betere manier bedenken dan pixel voor pixel vergelijken, en omdat dat nogal een arbeidsintensieve klus is, lijkt het ons dat er hier wel een goed algoritme voor te bedenken is.

Mijn vraag in het kort is dus; Op welke manier kan ik het best bepalen voor hoeveel procent een vlak is ingekleurd, en hoeveel er over de lijnen gekleurd is. Of is hier misschien al een geschikt algorithme voor en proberen wij het wiel opnieuw uit te vinden?

Alle duwtjes in de goede richting worden gewaardeerd!

[ Voor 5% gewijzigd door Deviruchi op 12-04-2010 13:04 ]

[djluc]

Ik zat net iets wellicht heel geks te denken maar gewoon bruto force pixels tellen lijkt me simpel en relatief best snel te doen? Het patroon wat getekend wordt is totaal willekeurig en er kunnen losse punten in zitten dus iets slims lijkt me niet echt optimaal?

[odysseus]

Je zou misschien tijdens het tekenen al het scoreverloop kunnen bijhouden. Op die manier hoef je niet alle pixels af te lopen, maar heb je alleen een berekening voor elke pixel die echt gekleurd wordt. Daarbij ga ik er van uit dat je het oppervlak van de figuur waarbinnen getekend moet worden al weet.

Een volgende stap zou dan zijn om bij het tekenen niet pixel voor pixel te gaan tellen, maar direct van een lijn(stuk) uit te rekenen hoe veel juist gekleurde pixels (en dus punten) het aan elk gebied toevoegt .

[Hydra]

djluc schreef op maandag 12 april 2010 @ 13:03:
Ik zat net iets wellicht heel geks te denken maar gewoon bruto force pixels tellen lijkt me simpel en relatief best snel te doen? Het patroon wat getekend wordt is totaal willekeurig en er kunnen losse punten in zitten dus iets slims lijkt me niet echt optimaal?

Je zou ook alleen de even x/y coordinaten kunnen checken. De breedte van de 'kwast' zal waarschijnlijk meer dan 1 pixel zijn dus zou je op min of meer hetzelfde resultaat moeten komen, en het scheelt je 3/4 van het aantal pixels. Dergelijke 'brute force' methode is snel zat en makkelijk te implementeren.

[djluc]

Zeker als lijnen elkaar gaan kruisen of elkaar (deels) overlappen is het niet meer: breedte kwast x afstand en wordt het mijns inziens toch al snel complex. Enkele honderdduizenden pixels tellen lijkt me niet een heel zware klus wat redelijk geoptimaliseerd kan worden zelfs bij brute force.

Qua ontwikkelingsstrategie zou ik sowieso deze brute force methode maken zodat je weet hoeveel pixels er getekend zijn. Als je het algoritme wilt gaan testen moet je toch een referentiegetal hebben.

[ Voor 25% gewijzigd door djluc op 12-04-2010 13:31 ]

[Zoijar]

Gewoon alle pixels aflopen als je je score berekent; dat is zo snel dat het waarschijnlijk binnen een tiende seconde gaat. Iets met root of all evil

[ Voor 10% gewijzigd door Zoijar op 12-04-2010 13:36 ]

[Wolfboy]

Dit zou zo'n kleine hoeveelheid data moeten zijn dat je het eenvoudig live kan berekenen. En dat zou misschien zelfs nog wel een voordeel kunnen zijn, als je tijdens het tekenen direct berekent hoe goed iemand bezig is kan je eventueel nog wat extra feedback geven wat weer motiverend kan werken

[Stoffel]

En als je er vanuit gaat dat de meeste mensen een beetje hun best doen kun je nog gaan tellen hoeveel pixels er niet gekleurd zijn in plaats van wel in een bepaald vlak. Dat zou je ook nog wat tijd besparen

[Hydra]

Stoffel schreef op maandag 12 april 2010 @ 13:40:
En als je er vanuit gaat dat de meeste mensen een beetje hun best doen kun je nog gaan tellen hoeveel pixels er niet gekleurd zijn in plaats van wel in een bepaald vlak. Dat zou je ook nog wat tijd besparen

Je zult echt hetzelfde aantal pixels af moeten lopen hoor.

[Stoffel]

Ohja, ik zat even te denken dat je niet perse sprongen van 1 pixel hoeft te maken, maar aangezien je een heel grillig patroon kunt krijgen van zo'n brush kan dat inderdaad niet anders. Nevermind

[roy-t]

Hydra schreef op maandag 12 april 2010 @ 13:27:
[...]


Je zou ook alleen de even x/y coordinaten kunnen checken. De breedte van de 'kwast' zal waarschijnlijk meer dan 1 pixel zijn dus zou je op min of meer hetzelfde resultaat moeten komen, en het scheelt je 3/4 van het aantal pixels. Dergelijke 'brute force' methode is snel zat en makkelijk te implementeren.

Dit zette me even aan het denken.

Ik weet niet hoe je figuren op dit moment geimplementeerd zijn, maar op een of andere manier zul je iig de kwast moeten plaatsen en de kleur moeten opslaan.

Deze informatie heb je dus al tijdens het tekenen:
-Pixelcoordinaten en kleur.

Als je dvm preprocessing of op een andere slimme manier aangeeft welke pixel bij welk figuur hoort dan weet je ook hoeveel pixels er in een figuur zitten. Als je tijdens het veranderen van kleur van een pixel dan eerst even controleerd of deze nog niet de goede kleur heeft kun je voor elke pixel dat dit gebeurt een punt geven.

[Nic]

<getekende vorm> XOR <het gewenste ingekleurde vlak> (zonder de lijnen) = <de fouten die je gemaakt hebt>

tenmiste, als 'buiten de lijntjes kleuren' evenveel punten kost als 'een stukje van het vlak niet ingekleurd hebben.

De XOR operatie kun je eenvoudig doen met bv imagemagick, en als je er een bitmap van maakt (alleen zwart/wit voor goed/fout), kun je ook het tellen van het percentage 'zwart' eenvoudig met die library doen. Lijkt me dus niet nodig om alle pixels te moeten doorlopen, met alle ellende van dien als je onregelmatige vormen hebt.

[djluc]

Heb even een testje gemaakt omdat ik er benieuwd was naar de snelheid.
http://dev.tentoday.com/tweakers/colors.php

Een grote afbeelding wordt in een seconde of 2 gedaan, dit betreft een afbeelding met vele kleuren (screenshotje).

Bron, super simpel:
http://dev.tentoday.com/tweakers/colors.phps

Afbeelding is 487 KB.

[ Voor 3% gewijzigd door djluc op 12-04-2010 14:19 ]

[Jaap-Jan]

Reken de print_r() eens niet bij de processing time, dan krijg je een wat realistischer beeld. 3 seconden vind ik best veel en ik denk dat het meeste tijd gaat zitten in het outputten, niet in het opbouwen.

[Deviruchi]

Bedankt voor de vele reacties, we zijn nu bezig met een brute-force implementatie. Snelheid is bij deze implementatie niet de bottleneck, ben nu bij een scherm van 1280 * 1024 binnen een seconde klaar. Misschien dat het later nog sneller te maken is, maar zoals djluc aangaf is het handig om eerst een referentie te hebben.

De breedte van de kwast is overigens niet altijd gelijk in ons spel, en hangt af van de voorkeur van de speler, dus we hebben besloten om dit vooralsnog niet mee te nemen, en het pixel-voor-pixel door te lopen.

Het stomme is dat we dit dus al eerder geprobeerd hadden, maar door onze brakke implementatie ( en vele logs ) liep dit enorm traag. Zoals we het nu hebben loopt het lekker vlug. Enorm bedankt allemaal!

[Nic]

djluc schreef op maandag 12 april 2010 @ 14:17:
Heb even een testje gemaakt omdat ik er benieuwd was naar de snelheid.

2 seconden vind ik nog best redelijk, maar het op die manier doen met PHP is echt erg inefficient.

Dit gaat in in imagemagick in ongeveer 1 seconde, en schaalt waarschijnlijk beter bij grotere plaatjes (al zal dat in dit geval niet nodig zijn, want ik neem aan dat het probleem van TS zich afspeelt bij schermresolutie).
Zie hieronder; 'histogram' is gesorteerd op de kleur die het meeste voorkomt (28141 pixels in dit plaatje met kleur #A5823B

code:

E:\temp>identify -verbose test2.png
Image: test2.png
  Format: PNG (Portable Network Graphics)
  Class: PseudoClass
  Geometry: 1340x850+0+0
  Resolution: 72x72
  Print size: 18.6111x11.8056
  Units: Undefined
  Type: Palette
  Endianess: Undefined
  Colorspace: RGB
  Depth: 8-bit
  Channel depth:
    red: 8-bit
    green: 8-bit
    blue: 8-bit
  Channel statistics:
    red:
      min: 12 (0.0470588)
      max: 238 (0.933333)
      mean: 156.471 (0.613612)
      standard deviation: 47.8626 (0.187696)
    green:
      min: 11 (0.0431373)
      max: 226 (0.886275)
      mean: 128.518 (0.503991)
      standard deviation: 48.031 (0.188357)
    blue:
      min: 7 (0.027451)
      max: 213 (0.835294)
      mean: 88.5619 (0.347302)
      standard deviation: 51.0161 (0.200063)
  Histogram:
     28141: (165,130, 59) #A5823B rgb(165,130,59)
     23112: (170,132, 59) #AA843B rgb(170,132,59)
     22542: (166,129, 54) #A68136 rgb(166,129,54)
     20343: (162,125, 58) #A27D3A rgb(162,125,58)
     19897: (158,121, 53) #9E7935 rgb(158,121,53)
     19837: (163,124, 53) #A37C35 rgb(163,124,53)
     18402: (163,130, 56) #A38238 rgb(163,130,56)
     17435: (173,137, 61) #AD893D rgb(173,137,61)
     17240: (168,125, 54) #A87D36 rgb(168,125,54)
     17236: (155,116, 51) #9B7433 rgb(155,116,51)
     17228: (207,200,172) #CFC8AC rgb(207,200,172)
     16569: (206,200,179) #CEC8B3 rgb(206,200,179)
enz.

[Hydra]

Ik weet trouwens niet of de API die je gaat gebruiken methoden heeft om te testen of een punt binnen een shape valt maar bijvoorbeeld Java kan dit voor je doen (java.awt.geom). Dan kun je voor alle pixels (of een subset daarvan) die binnen dat vlak zouden kunnen liggen (je kunt simpel de rechthoek uitrekenen waarbinnen je shape valt) eerst testen of ze binnen het vlak liggen en daarna welke kleur ze hebben. Dat moet in no time te doen zijn (kwa rekentijd) en ook vrij simpel te implementeren.

dsltv schreef op maandag 12 april 2010 @ 14:33:
...

Lijkt me een beetje overkill.

[ Voor 12% gewijzigd door Hydra op 12-04-2010 14:37 ]

[Verwijderd]

djluc schreef op maandag 12 april 2010 @ 13:03: maar gewoon bruto force pixels tellen

offtopic: misschien netto force wel

[djluc]

dsltv schreef op maandag 12 april 2010 @ 14:33:
[...]


2 seconden vind ik nog best redelijk, maar het op die manier doen met PHP is echt erg inefficient.

Dit gaat in in imagemagick in ongeveer 1 seconde, en schaalt waarschijnlijk beter bij grotere plaatjes (al zal dat in dit geval niet nodig zijn, want ik neem aan dat het probleem van TS zich afspeelt bij schermresolutie).
Zie hieronder; 'histogram' is gesorteerd op de kleur die het meeste voorkomt (28141 pixels in dit plaatje met kleur #A5823B
[...]

Had sneller verwacht van een C implementatie. PHP is nou toch niet echt een snelheidsduivel op dit gebied, best grappig. Wat zeg ik, het kan nog sneller in PHP zonder de print_R:

code:

Image size: 1340x850

5 done in :

4.99344611168 seconds

[Verwijderd]

Brute force is het simpelst, idd. Je hebt twee images, een correct image dat gemaakt is met flood fill, en het door de speler gemaakte image, en je loopt door alle pixels heen en noteert het aantal keer dat de waarde verschilt. Eerst gaan testen of een pixel binnen een shape valt maakt alles alleen maar trager.

Maar het beste is om de score bij te houden tijdens het tekenen. Op het moment dat je een pixel van kleur verandert kun je ook simpel checken wat dat doet met de score van de speler, dat kost geen merkbare tijd, en je hebt altijd een up to date score.

[Verwijderd]

Je kan de afbeelding natuurlijk ook 50% verkleinen, waardoor het veel sneller gaat en ongeveer hetzelfde eruit komt (hetzelfde als elke 2 px langsgaan ipv 1 px).

Eerst: 6.56s met dsltv php script 10 runs
Imagemagick resize 50% elke run: 4.7s 10 runs
Elke 2px: 1.6s 10 runs

@Janoz: Resizen is nauwkeuriger dan elke 2px 'tellen', maar toch sneller dan alle pixels tellen. Imagemagick is een stuk sneller dan php/gd volgens mij en zoiets zal je op de WII ook wel hebben. Ik zou zeggen: gebruik de image library die je voor handen hebt op de WII linux/windows/... want die werkt waarschijnlijk het snelst met die cpu.

[ Voor 39% gewijzigd door Verwijderd op 12-04-2010 16:29 ]

[Janoz]

Grappig. Al die opmerkingen over 'doe eerst bewerking X op het plaatje, dan hoef je veel minder pixels te tellen'

Denken jullie daadwerkelijk dat operatie X op 1 of andere magische manier een kleiner plaatje uit het geheel goocheld zonder naar alle pixels in het origineel te kijken? Nog even los van alle voorstellen om externe programma's in te zetten voor een simpele bewerking op een image buffer.

[Wolfboy]

Janoz schreef op maandag 12 april 2010 @ 16:19:
Grappig. Al die opmerkingen over 'doe eerst bewerking X op het plaatje, dan hoef je veel minder pixels te tellen'

Denken jullie daadwerkelijk dat operatie X op 1 of andere magische manier een kleiner plaatje uit het geheel goocheld zonder naar alle pixels in het origineel te kijken? Nog even los van alle voorstellen om externe programma's in te zetten voor een simpele bewerking op een image buffer.

Ik denk dat de meeste mensen hier refereren vanuit scripting talen (zoals PHP) die dit soort bewerkingen gewoon vele malen trager doen dan imagemagick oid.

In dat geval is je probleemgebied beperken zeker zinnig. Al moet ik toegeven dat ik ook zat toen ik de reacties las

[Janoz]

Verwijderd schreef op maandag 12 april 2010 @ 16:10:
@Janoz: Resizen is nauwkeuriger dan elke 2px 'tellen', maar toch sneller dan alle pixels tellen. Imagemagick is een stuk sneller dan php/gd volgens mij en zoiets zal je op de WII ook wel hebben. Ik zou zeggen: gebruik de image library die je voor handen hebt op de WII linux/windows/... want die werkt waarschijnlijk het snelst met die cpu.

Hoe denk je dat resizen werkt? Wat denk je dat er gebeurt tijdens een resize?

[djluc]

@TS: Ben je hier inmiddels uit gekomen?

[Davio]

Ik wil hier nog wel aan toevoegen dat een tijd van ongeveer 5 seconden echt wel acceptabel is voor het berekenen van de score.

Tover je gewoon een message "Uw score wordt berekend" op het scherm en laat je de gebruiker eventjes wachten, dat is helemaal niet erg. Als het nou meer dan 10 seconden was, dan zou het wel ergerlijk worden op den duur.

Je hoeft dit onderdeel van de applicatie niet veel moeilijker te maken dan het is.

[Deviruchi]

djluc schreef op vrijdag 16 april 2010 @ 10:39:
@TS: Ben je hier inmiddels uit gekomen?

We zijn er nog steeds mee bezig, maar we hebben al enorme progress gemaakt dankzij jullie allemaal, waarvoor dank. Ook hebben we de volgende oplossing gevonden om te kijken of een punt in een polygoon ligt; Wikipedia: Point in polygon hier zijn we nu mee aan het experimenteren om te kijken hoe snel dit gaat en of dit goed te implementeren is.

en @davio: Het zou mooi zijn als de score on-the-fly berekend kan worden, maar dit is inderdaad niet 100% nodig.