[Java] Grootste afstand tot lijn uit plaatje halen

[ernstblaauw]

Voor mijn afstuderen ben ik bezig met een robotsimulatie. Deze robots lopen rond in een virtuele wereld, en laten daarbij een spoor achter. Na een simulatie heb ik een figuur als deze:



Een van de doelen van de robots is om alle plaatsen in de wereld te bezoeken. Ik wil dus in dit plaatje de grootste afstand tot de zwarte lijn halen, om zo de prestaties van de robots te evalueren; immers, hoe groter die afstand, hoe slechter ze rondlopen.

Nu wil ik dus in een algoritme:
- Eerste alle zwarte pixels een waarde 0 geven
- vervolgens alle pixels die grenzen aan een '0' waarde, de waarde 1 geven
- alle pixels die nog geen waarde hebben en aan 1 grenzen, een waarde 2 geveb,
etc

Nu heb ik alleen helemaal geen ervaring met het manipuleren van plaatjes. Is er hier iemand die me wat kan helpen met dit soort berekeningen doen?
Het gaat dus om:
- het inladen van een plaatje
- bepalen welke pixels buren zijn (misschien triviaal in een dubbel array?)
- kleur bepalen

Het liefst doe ik dit in Java. Kan iemand mij hierbij helpen? Alvast bedankt!

[Nick_S]

Heb je al gegoogled? Dan kom ik vrij snel op de site van java.net uit.

[ernstblaauw]

Nick_S schreef op dinsdag 03 februari 2009 @ 17:40:
Heb je al gegoogled? Dan kom ik vrij snel op de site van java.net uit.

Ik heb gezocht naar methodes om eenvoudig een plaatje als int[][] te laden, dat kon ik niet vinden. Ik kan inderdaad het plaatje laden als BufferedImage, maar ik weet niet of dat de beste manier is om te bereiken wat ik wil. Zo krijg je bij de link die jij geeft, een int[].

[Verwijderd]

Meestal als men een 2-dimensionale grid in 1-dimensionale array stopt kom je op deze manier aan de data:

C:

int pixel = data[x*y];

[Janoz]

Ik denk dat java.awt.image.Raster in eerste instantie de class is die je zoekt. Daarnaast is het handig om eens wat te gaan lezen over Morphological Image Processing. Dat is het vakgebied wat zich richt op dergelijke image manipulation.

[Plecky]

Je plaatje ziet er uit als een top-down shot van een 3d omgeving. Heb je alleen een plaatje of ook daadwerkelijk een 3d omgeving? Want in het tweede geval is de afstand uitrekenen een stuk makkelijker.

[ThomasClay]

Verwijderd schreef op dinsdag 03 februari 2009 @ 21:08:
Meestal als men een 2-dimensionale grid in 1-dimensionale array stopt kom je op deze manier aan de data:

C:

int pixel = data[x*y];

Volgens mij gaat dat niet helemaal werken, aangezien (1,2) bijvoorbeeld hetzelfde oplevert als (2,1). Iets als het volgende is volgens mij gebruikelijker:

C:

int pixel = data[y*width+x]

[Not Pingu]

De afbeelding lijkt me slechts een visuele weergave van het resultaat van je simulatie. Heb je beschikking over de originele simulatiedata? Het lijkt me wat omslachtig om de afbeelding te gaan reverse-engineeren.

[ernstblaauw]

De simulatie is gedaan in Webots; daarmee beschrijf je eerst de 3D-wereld in een soort van XML file, en vervolgens kan je de (eerder gedefinieerde) robots besturen met een controller die geschreven kan worden in Java, C++ of Python.
De gegevens over de 3D-wereld zijn niet zo makkelijk toegankelijk; De support van Webots adviseerde me dan ook om het op deze manier te doen.

Ik gebruik nu inderdaad een raster, waarna ik met getPixel de gegevens er een voor een uit kan halen.

[Knutselsmurf]

Als ik je afbeelding zo zie, vraag ik mij af of je werkelijk wilt weten of de robot werkelijk ieder plekje bezocht heeft. Dat zou namelijk betekeken dat een robot als een dronkelap al zigzaggend iedere muur onderweg heeft geraakt.

Bedoel je niet dat je graag wil weten of de robot alle GEBIEDEN binnen je virtuele wereld heeft bewandeld?
In dat geval zou je bijvoorbeeld een lijst met cirkels (middelpunt+ straal) kunnen definieren en dan deze lijst aflopen om te kijken of het spoor van de robot door het betreffende gebied loopt.

[Not Pingu]

Ik snapte de vraagstelling ook niet helemaal.

Ik wil dus in dit plaatje de grootste afstand tot de zwarte lijn halen, om zo de prestaties van de robots te evalueren;

Wat bedoel je precies met de zwarte lijn? Ik zie een lange lijn met een gradient die volgens mij de gelopen route van de robot weergeeft, maar niet iets zoals een ideale lijn waarmee je zou kunnen vergelijken.

Welke metric wil je gebruiken voor het scoren van je resultaat? Hausdorff distance lijkt me voor de hand te liggen.

[Cavorka]

Not Pingu schreef op woensdag 04 februari 2009 @ 14:10:
Ik snapte de vraagstelling ook niet helemaal.
[...]
Wat bedoel je precies met de zwarte lijn? Ik zie een lange lijn met een gradient die volgens mij de gelopen route van de robot weergeeft, maar niet iets zoals een ideale lijn waarmee je zou kunnen vergelijken.

Inderdaad, welke afstand wil je precies berekenen? Van waar tot waar. Want 'de afstand tot de (de? welke dan? en vanaf waar) zwarte lijn' is best onspecifiek.

[.oisyn]

Not Pingu schreef op woensdag 04 februari 2009 @ 14:10:
Welke metric wil je gebruiken voor het scoren van je resultaat? Hausdorff distance lijkt me voor de hand te liggen.

Dat lijkt me een onhandige metric eigenlijk. Sowieso zijn er geen twee sets om te vergelijken, en als je van een willekeurig punt uitgaat dan is het altijd de langste afstand tot de set van punten waar de robot wel is geweest (dit noemen we even S). Maar als de robot overal is geweest dan is die afstand alsnog erg lang. Voor een willekeurig punt wil je dus eerder de kortste afstand tot S. En de TS wil nu van al die korste afstanden de langste

[Not Pingu]

.oisyn schreef op woensdag 04 februari 2009 @ 15:40:
[...]

Dat lijkt me een onhandige metric eigenlijk. Sowieso zijn er geen twee sets om te vergelijken, en als je van een willekeurig punt uitgaat dan is het altijd de langste afstand tot de set van punten waar de robot wel is geweest (dit noemen we even S). Maar als de robot overal is geweest dan is die afstand alsnog erg lang. Voor een willekeurig punt wil je dus eerder de kortste afstand tot S. En de TS wil nu van al die korste afstanden de langste

Ik ben er even vanuit gegaan dat je de gelopen lijn uit het plaatje destilleert tot een polyline met een aantal nodes. Je kunt dan node-voor-node vergelijken met de (hypothetische) ideaallijn.

Het is me even niet duidelijk wat TS precies wil evalueren (wat is het doel dat de robot moet zien te behalen oid.) en waartegen hij het gelopen pad wil afzetten. De gebruikte metric is daar sterk van afhankelijk lijkt me.

[link0007]

doet de robot meer dan rondlopen? als het erom gaat dat hij een camera heeft, en de hele omgeving moet scannen, zou ik eerder een "fog of war" principe implementeren. wanneer je weet wat de camera kan zien, en je de vaste obstakels weet, dan kan je eenvoudig bepalen of je camera iets gemist heeft of niet.

Als het erom gaat dat hij alle kamers afgaat in een gebouw, kan je de kamers verdelen in sectors, en in de software die dat plaatje bijhoud van waar de robot is geweest, kan je dan ook bijhouden of de robot een sector ingaat of uitgaat. Zo kan je bijhouden welke sectoren geweest zijn.