[alg] 2D objectmetingen

[Verwijderd]

Ik ben al een tijdje aan het denken, maar ik kom er toch niet helemaal uit. Ik probeer in een 2D-plattegrond verschillende objecten te herkennen, maar ik zit een beetje vast met denken... De plattegrond zal er ongeveer zo uitzien:



Wat ik wil weten is de hoeken tussen de uiterste punten gezien vanuit het punt op de map. Iemand heeft me in de richting geduwd van raycasting/tracing, en dan kijken welke kleur de pixel krijgt (istie blauw, dan kijk je in de richting van een object), maar als ik daar iets over zoek, krijg ik mega-complexe 3D algoritmes, terwijl iets als dit toch niet heel moeilijk moet zijn?

Kan iemand mij in een richting duwen waar ik naar kan zoeken, of heeft iemand zelf ervaring met zoiets? Ik zat zelf nog even na te denken, en waar ik toen op uit kwam is van elk object (waarvan de afmetingen/locaties bekend zijn) langs de contouren lopen en van elk punt de hoek met de "Noord" lijn berekenen. Dan hiervan eenvoudig de Max/Min bepalen. Maar dat betekent dat van elk punt de hoek bepaald moet worden, en aangezien er meer en complexere objecten aanwezig zullen zijn, zal dit veel rekenwerk vragen, terwijl dit (misschien) vermeden kan worden?

[Verwijderd]

Je gaat er nu dus vanuit dat de objecten in je map niet bekend zijn bij je map en dat je dus echt je objecten moet gaan opzoeken?

[Verwijderd]

Die map is gewoon een map, waarin objecten staan. Maar wat ik bedoel is dat bij een bewegend punt, alle uiterste hoeken van objecten veranderen. Maar hoe krijg ik die hoeken nou wiskundig bij MIJ bekend.

Door elke hoek van alle pixels op de contouren van een object af te lopen of iets dergelijks, is een optie natuurlijk. Maar dit moet makkelijker kunnen toch?

[Janoz]

Hoe ziet de datastructuur er uit? Is de map een bitmap of een verzameling wiskundig gedefinieerde figuren (Als in polygonen ed). Dat maakt nogal uit voor het te gebruiken algoritme.

[Verwijderd]

Op dit moment bestaan de delen uit bitmaps. Maar aangezien deze alleen 'simpele' vormen als cirkels/rechthoeken en (slechts enkele) combinaties daarvan zullen bestaan, zijn de wiskundige beschrijvingen daarvan ook een optie. Maar het idee zal nog steeds hetzelfde blijven toch? Hoe bepaal je de uiterste punten (met de kleinste/grootste alpha)?

[Henk007]

edit:
Deze reply was iets te simpel

[ Voor 84% gewijzigd door Henk007 op 10-07-2005 17:11 ]

[MrBucket]

Omdat je het ook hebt over een bewegend kijkpunt, lijkt me het makkelijkste om die bitmap-map eerst te converteren naar een andere datastructuur waarin bijv. elk figuur wordt gerepresenteerd door een verzameling vertices* (of iig een omschrijving die minder elementen kent als een berg pixels).
Met behulp van deze conversieslag zou je de complexiteit van de hoek-bepaal-fase sterk kunnen terugbrengen. Daar staat tegenover dat je een soort van line-trace algoritme zult moeten gebruiken om de pixeldata om te zetten naar vectordata...

Dus: tenzij je weet dat de brute-force manier echt een onacceptabele performance zal geven, is het denk ik ook zeker de moeite waard om het eerst op een brute-force manier uit te werken en te kijken naar de benodigde tijd. Want het is misschien minder elegant en niet-optimaal, het is wel een stuk makkelijker om uit te werken.

* Je kunt hier volstaan met alleen de vertices die deel uitmaken van de zgn. 'Convex hull' van het figuur.

[Zoijar]

Ik denk dat (slim) brute force het snelste is. Gewoon je edge langslopen, en voor elke pixel die hoek berekenen. Hoek berekening kost bijna geen tijd toch? Anders moet je een of andere edge detection filter eroverheen gooien, en daaruit je itmap omzetten naar een vertex representatie, en dan je dingen geometrisch berekenen. Maar die filters kosten denk ik al net zoveel tijd als brute force je hoeken bepalen. Als je oogpunt heel vaak beweegt, maar je itmap het zelfde blijft, dan kan je wel beter naar een vertex representatie gaan.

[Plecky]

Ik zou ook voor een vertex-representatie gaan, maar het hangt er een beetje vanaf waar je data vandaan komt of je edge detectie moet doen of gewoon de formules van de vormen kan gebruiken. Maar aangezien dit in een pre-processing stap kan gebeuren is de hiervoor gebruikte tijd misschien minder van belang en kan je gerust edge detectie doen.
Brute force per object lijkt me ook het handigste, je ontkomt er niet aan om elke tijdstap opnieuw te kijken of een andere vertex zorgt voor een grotere hoek.

Als je veel objecten heb zou je de ruimte eventueel ook nog kunnen segmenteren met een kd-tree ofzo.

[ Voor 6% gewijzigd door Plecky op 10-07-2005 19:13 ]

[MSalters]

Zoijar schreef op zondag 10 juli 2005 @ 17:52:
Ik denk dat (slim) brute force het snelste is. Gewoon je edge langslopen, en voor elke pixel die hoek berekenen. Hoek berekening kost bijna geen tijd toch? Anders moet je een of andere edge detection filter eroverheen gooien, en daaruit je itmap omzetten naar een vertex representatie, en dan je dingen geometrisch berekenen. Maar die filters kosten denk ik al net zoveel tijd als brute force je hoeken bepalen. Als je oogpunt heel vaak beweegt, maar je itmap het zelfde blijft, dan kan je wel beter naar een vertex representatie gaan.

Hoeken alleen red je het niet mee, als je convexe vormen hebt. Denk aan een C rondom je oorsprong, dat lijkt op een ) als je alleen de extremen uitrekent.

[RobIII]

(VB6) Voorbeeldje van simpele wiskunde/brute force manier:

Visual Basic 6:

Option Explicit

Private m_lngPlayerX As Long            'Player X pos
Private m_lngPlayerY As Long            'Player Y pos
Private m_lngObjects As Long            'Number of objects

Private Const cPI = 3.14159265358979    'PI
Private Const cTwoPi = 2 * cPI          'Two Pi
Private Const cPlayerSize = 150         'Player size in Twips
Private Const cStepSize = 150           'Size of a players' step

Private Const cRays = 100                   'Cast rays per scan
Private Const cScanAngle = cTwoPi / cRays   'Angle of rays to cast
Private Const cMaxDist = 5000               'Max distance a player can see in twips
Private Const cRPrecision = 100             'Radius precision of scan in twips


'Type to hold an object
Private Type tRect
    X As Long
    Y As Long
    Width As Long
    Height As Long
    Color As Long
End Type

Private arrObjects() As tRect   'Array of objects

Private Sub Form_KeyDown(KeyCode As Integer, Shift As Integer)
    'Handle keypress
    Select Case KeyCode
        Case vbKeyUp: m_lngPlayerY = m_lngPlayerY - cStepSize
        Case vbKeyDown:  m_lngPlayerY = m_lngPlayerY + cStepSize
        Case vbKeyLeft: m_lngPlayerX = m_lngPlayerX - cStepSize
        Case vbKeyRight: m_lngPlayerX = m_lngPlayerX + cStepSize
    End Select
    DrawScreen  'Update screen
End Sub

Private Sub DrawScreen()
    Dim T As Single
    Dim R As Long
    Dim bHit As Boolean
    Dim lX As Long, lY As Long
    Dim lSW As Long, lSH As Long
    Dim dColorStep As Double
    
    dColorStep = 255 / (cMaxDist + cPlayerSize)
    
    'Clear Screen
    Me.Cls
    
    'Get dimensions of form
    lSW = Me.ScaleWidth
    lSH = Me.ScaleHeight
    
    'Draw player
    Me.Line (m_lngPlayerX - (cPlayerSize \ 2), m_lngPlayerY - (cPlayerSize \ 2))-(m_lngPlayerX + (cPlayerSize \ 2), m_lngPlayerY + (cPlayerSize \ 2)), vbRed, BF
    
    'Draw objects
    For R = 0 To m_lngObjects
        With arrObjects(R)
            Me.Line (.X, .Y)-(.X + .Width, .Y + .Height), .Color, BF
        End With
    Next
    
    'Scan circle in cScanAngle steps
    For T = 0 To cTwoPi Step cScanAngle
        bHit = False                'No hit for this ray yet
        R = cPlayerSize + 1         'Radius size
        While (R <= cMaxDist) And (Not bHit)  'Scan Ray
            'Calc X/Y on ray
            lX = m_lngPlayerX + (Sin(T) * R)
            lY = m_lngPlayerY + (Cos(T) * R)
            'Check if X/Y in object
            If (lX > 0) And (lY > 0) And (lX < lSW) And (lY < lSH) Then bHit = InObject(lX, lY)
            R = R + cRPrecision 'Next radius
        Wend
        'Draw a ray
        Me.Line (m_lngPlayerX + (Sin(T) * cPlayerSize), m_lngPlayerY + (Cos(T) * cPlayerSize))-(m_lngPlayerX + (Sin(T) * R), m_lngPlayerY + (Cos(T) * R)), RGB(255 - (dColorStep * R), dColorStep * R, 0)
    Next T
End Sub

Private Function InObject(lX As Long, lY As Long) As Boolean
    Dim T As Long
    Dim bInObject As Boolean
    
    T = 0
    bInObject = False
    
    While (T <= m_lngObjects) And (Not bInObject)
        With arrObjects(T)
            bInObject = lX >= .X And lX <= .X + .Width And lY >= .Y And lY <= .Y + .Height
        End With
        T = T + 1
    Wend
    InObject = bInObject
End Function

Private Sub Form_Load()
    Me.BackColor = vbWhite

    Randomize Timer         'Seed randomizer
    
    m_lngPlayerX = 1500     'Player start position
    m_lngPlayerY = 1500
    
    InitObjects             'Init the random objects
    
    Me.Show                 'Show form
    
    DrawScreen              'Update screen
End Sub

Private Sub InitObjects()
    'Create a random amount of obejcts
    Dim T As Long
    
    m_lngObjects = 20 + (Rnd * 20)  'Number of objects
    ReDim arrObjects(m_lngObjects)  'Init Array
    
    For T = 0 To m_lngObjects       'Set all objects to random position and width/height
        With arrObjects(T)
            .X = Rnd * Me.ScaleWidth
            .Y = Rnd * Me.ScaleHeight
            .Width = 150 + (Rnd * (Me.ScaleWidth * 0.05))
            .Height = 150 + (Rnd * (Me.ScaleWidth * 0.05))
            .Color = RGB(Rnd * 255, Rnd * 255, Rnd * 255)
        End With
    Next
End Sub

Private Sub Form_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)
    m_lngPlayerX = X
    m_lngPlayerY = Y
    DrawScreen  'Update screen
End Sub

Copy / Pasten in een nieuw project...

Dit heb ik met wat MAVO wiskunde in 10 minuten in elkaar gebokst. Wat je doet is in een circel om de zoveel graden een ray (straal) "casten". Vervolgens ga je op X punten op die ray kijken of je een object raakt. Dit is redelijk brute-force en niet optimaal, maar geeft je wel een idee van de simpele methode.
In plaats van de InObject functie kun je natuurlijk ook gewoon een pixel van die X/Y positie lezen, maar om een of andere vage reden wou VB6 (m.b.v. Point*) daar niet aan meewerken...

Helaas zul je voor wat betere precisie wat meer wiskunde nodig hebben of deze code dusdanig aanpassen dat 't niet meer vooruit te fikken is (want je kunt hier hele hoge precisie mee halen, als je de parameters maar tweakt), maar dat hangt dus ook af van wat je met je project wil.
Kijk anders eens in het BotWars project hier op GoT, daar komt dit soort "wiskunde" ook veelvuldig aan te pas. Vooral deze WiKi kan dan van pas komen.

Screenshotje:

Je kunt met de pijltjes toetsen het rode blokje "besturen" of ergens klikken om het blokje neer te gooien...Hoe dichter bij het object, hoe "roder" de straal. Voor het screenshot zijn de volgende parameters getweaked: cRPrecision = 15 en cRays = 360

Overigens, een leuk experiment is om op regel 128 de kleur van de objecten op vbWhite te zetten (.Color = vbWhite) zodat je "radartje" kunt spelen. Je ziet de objecten dan niet, maar wel aan de hand van je rays waar ze zitten.

---

* Kan iemand mij verklaren waarom als ik de GetPixel API gebruik, of VB6 native .Point waarom er dan maar een paar lijnen worden getekend? Vervang de InObject functie maar eens door:

Visual Basic 6:

Private Function InObject(lX As Long, lY As Long) As Boolean
    InObject = Me.Point(lX, lY) <> vbWhite
End Function

Dat zou toch gewoon moeten werken? Als ik cRays op 360 zet zie ik er maar een paar van de 360

Dislaimer: Snel in elkaar geflanst projectje Geen productiecode van maken he?

[ Voor 94% gewijzigd door RobIII op 11-07-2005 03:34 ]

[.oisyn]

MSalters schreef op zondag 10 juli 2005 @ 22:23:
[...]

Hoeken alleen red je het niet mee, als je convexe vormen hebt. Denk aan een C rondom je oorsprong, dat lijkt op een ) als je alleen de extremen uitrekent.

Een C is dan ook niet convex maar concaaf

RobIII schreef op zondag 10 juli 2005 @ 23:48:
(VB6) Voorbeeldje van simpele wiskunde/brute force manier:

Een nadeel van een dergelijke discrete oplossing is dat je ook objecten kunt missen. In jouw voorbeeld wellicht niet, maar als je de plattegrond 10x zo groot maakt, en je hebt een object van een enkele pixel ergens langs de rand zitten, dan is de kans groot dat je 'm nooit zal raken. Je kunt de hoek verkleinen, maar dat is slechts symptoombestrijding.

Wat ik zelf zou doen is dmv edge detection de objecten omzetten in polygonen, en dan de vertices van de polygoon aflopen om te kijken of zij extreem zijn vanaf de oorsprong (dus of de lijn door de oorsprong en die vertex de polygoon niet doorsnijdt maar slechts raakt, ergo of alle overige vertices aan een kant van de lijn liggen). Uiteindelijk heb je dan de 2 extremen, en dan is het berekenen van de hoek een vrij simpele opgave

[ Voor 68% gewijzigd door .oisyn op 11-07-2005 13:18 ]

[alienfruit]

Er is hierover toch genoeg geschreven in wetenschappelijke tijdschriften? Ik bedoel er zijn ook artikelen over hoe je objecten kan herkennen met een troebele achtergrond etc.

Bijvoorbeeld in "Transactions on Pattern Analysis and Machine Intelligence", maar goed kijk ook eens naar vormperceptie (cognitieve psychologie ?) of patroon herkenning. Misschien is een artikel zoals "Generic Object Recognition: Building and Matching Coarse Descriptions from Line Drawings" interessant voor je?

Primal access recognition of visual objects (PARVO), a computer vision system that addresses the problem of fast and generic recognition of unexpected 3D objects from single 2D views, is considered. Recently, recognition by components (RBC), which is a new human image understanding theory, based on some psychological results, has been proposed as an explanation of how PARVO works. However, no systematic computational evaluation of its many aspects has yet been reported. The PARVO system discussed is a first step toward this goal, since its design respects and makes explicit the main assumptions of the proposed theory. It analyzes single-view 2D line drawings of 3D objects typical of the ones used in human image understanding studies. It is designed to handle partially occluded objects of different shape and dimension in various spatial orientations and locations in the image plane. The system is shown to successfully compute generic descriptions and then recognize many common man-made objects.

abstract

Dat maakt een discussie erover niet minder interessant

Zeker interessant! Het is leuk om over zulke onderwerpen ACM.org te door struinen

[ Voor 113% gewijzigd door alienfruit op 11-07-2005 11:15 . Reden: zucht :( ]

[.oisyn]

Dat maakt een discussie erover niet minder interessant

[RobIII]

.oisyn schreef op maandag 11 juli 2005 @ 11:00:
Een nadeel van een dergelijke discrete oplossing is dat je ook objecten kunt missen. In jouw voorbeeld wellicht niet, maar als je de plattegrond 10x zo groot maakt, en je hebt een object van een enkele pixel ergens langs de rand zitten, dan is de kans groot dat je 'm nooit zal raken. Je kunt de hoek verkleinen, maar dat is slechts symptoombestrijding.

Awel, ik zei ook niet dat dit de ideale oplossing was, maar voor TS misschien voldoende Dit was meer om aan te tonen dat je met wat MAVO wiskunde een heel eind kunt komen
En het is symptoombestrijding

[ Voor 9% gewijzigd door .oisyn op 11-07-2005 13:19 ]

[.oisyn]

Dat staat er toch ook?

[Verwijderd]

RobIII, superbedankt voor deze code! Niet verwacht dat iemand er zo veel tijd voor me in zou steken! Hij is alleen niet helemaal praktisch toepasbaar, omdat ik ook van objecten die 'achter' een ander object verstopt zitten de hoeken wil weten. Dan zou je dit systeem uit kunnen breiden met 'als je een object tegen bent gekomen, sla de coordinaten op en ga verder met de straal', maar het kent verder ook wat gebreken. Als bijvoorbeeld twee objecten tegen elkaar aanliggen, hoe maak je dan (makkelijk) onderscheid?

In ieder geval, ik heb er zelf nog even over nagedacht, en volgens mij is het eigenlijk best wel simpel. Als je alle figuren wiskundig beschrijft, dan kan je vrij eenvoudig de hoeken berekenen. Hiervoor ga ik uit van dat de 'speler' in het nulpunt (0,0) staat. Voor een rechthoek geld dan:


Een rechthoek is opgebouwd uit vier lijnen/vier hoekpunten. De extreme hoeken zullen altijd op de hoekpunten liggen, waardoor met deze beschrijving slechts vier hoekberekeningen nodig zijn. Dus vier keer alpha = arctan(...), en dan kijken wel de min/max zijn.

Voor de cirkel zijn iets meer berekeningen nodig, zie volgende plaatje:

Voor de beschrijving van de cirkel lijkt me de coordinaten tot het middelpunt (a,b) en de straal (R) de makkelijkste optie. Uit deze gegevens kunnen alpha1 en alpha2 bepaald worden uit respectievelijk (gamma - beta) en (gamma + beta). De gamma is eenvoudig te herlijden uit arctan(a/b), en de beta is te berekenen uit arctan(R/ {sqrt(a^2 + b^2)} ).

Eigenlijk zie ik zelf nog geen nadelen aan deze methoden, en zo hoeven maximaal vier hoeken bepaald te worden. Zie ik iets over het hoofd, of is het echt niet zo moeilijk? Voordeel van dit is, dat je in plaats van bitmaps slechts coordinaten hoeft te bewaren, wat ook ruimtebesparend zou moeten werken.

Er vanuit gaande dat dit systeem werkt, moeten de objecten nog makkelijk/klein/snel op te halen zijn. Het makkelijkst lijkt me dan een komma-gescheiden tekst bestand, maar een stemmetje in m'n achterhoofd zegt me dat dit simpele systeem, niet het snelste zal zijn. Hier ga ik nog wel fftjes naar zoeken, elke reactie over alles is uiteraard welkom!