[algoritme] punt berekenen vanuit een vervormd vlak

[stereohead]

Dag,

Ik ben bezig met een projectje in VB6.
Ik krijg via een webcam coördinaten door in de vorm van een witte stip, het beeld van de webcam wordt eerst bewerkt, gefiltert enz. Uiteindelijk krijg ik netjes de x,y positie van de witte stip. Deze positie bepaald de positie van de muis op mijn scherm

Het probleem is alleen dat de webcam niet altijd recht staat, dus ik ben van plan om een soort kalibratie systeempje te maken. Zie de afbeelding hieronder:



Links is te zien hoe ik het beeld binnenkrijgt, alle lijnen zijn in het echt niet zichtbaar, maar voor de duidelijkheid. Punt P is dus de witte stip, en A,B,C,D bepalen wat de hoeken zijn van mijn scherm.

De vraag is nu alleen hoe ik het linker gedeelte omzet naar het rechter gedeelte.

In het linker gedeelte zijn alle afstanden tussen de punten A,B,C,D en de afstanden van die punten naar P bekent. Aan de rechterkant zijn de afstanden tussen de punten A',B',C',D' bekend. P' moet dus op de een of andere manier berekend worden, de vraag is alleen hoe.

[giMoz]

je zou iets met verhoudingen kunnen doen tussen de verschillende hoeken
De verhouding tussen Hoek DAB vs DAP
en CBA vs CBP
dan kan je gaan berekenen wat de eigenlijke hoeken van DAP en CBP zou moeten zijn en dan twee lijnen trekken vanuit A met de juiste hoek richting P en van B met de juiste hoek richting P
het snijpunt tussen die twee lijnen is de positie van P...

toch?

[Janoz]

Bijna, het probleem daarbij is dat je geen rekening houd met perspectief. Ik denk echter dat dit, bij een relatief kleine verdraaiing, verwaarloosbaar is.

[RobIII]

Dit ziet er wel interessant uit:

Wikipedia: Projective geometry
Wikipedia: Projective transformation

Helaas is het voor mij grotendeels chinees

[ Voor 38% gewijzigd door RobIII op 20-03-2008 14:38 ]

[Cascade]

Leuk probleem.

Zo even uit de losse pols:
Je hebt hier dus een rechthoek met willekeurige orientatie die je met de webcam bekijkt. Ik zou dan proberen een lijn te trekken vanuit P naar het verdwijnpunt (lijnperspectief) en het snijpunt bepalen met de zijkant (AD of BC) -> noem die even P_v. Je weet dan de verhouding tussen bijvoorbeeld AP_v en AD, die verhouding is hetzelfde in je 'rechte' versie. Hetzelfde kan met het snijpunt P_h met lijnstuk AB of CD. Niet ideaal, je krijgt problemen als de lijnstukken die je ziet parallel beginnen te lopen... moet wel beter kunnen.

Nog even verder gekeken, dit is wel een bekend probleem en best wel veel over te vinden. Vond deze zo snel via Google: http://www.iiit.ac.in/techreports/2007_107.pdf.

[giMoz]

Janoz schreef op donderdag 20 maart 2008 @ 14:32:
Bijna, het probleem daarbij is dat je geen rekening houd met perspectief. Ik denk echter dat dit, bij een relatief kleine verdraaiing, verwaarloosbaar is.

Hoezo hou je geen rekening met perspectief.
Dat hou je dan toch juist wel?
omdat je van 90 graden als werkelijke hoek CBA uitgaat en er nu bv.geprojecteerd 70 graden is, 70 staat tot 90 als huidige hoek CBP staat tot nieuwe hoek CBP

dan maakt het qua draaing toch niet uit? omdat de draaing beide geprojecteerde hoeken aanpast met dezelfde 'afwijking'?

[Janoz]

Door het perspectief schaalt de hoek niet lineair. Neem maar een vierkant met daarop de diagonalen en bekijk deze redelijk van de zijkant. De diagonaal heeft een hoek van 45gr met de zeiden, maar in het geprojecteerde plaatje zijn de hoeken niet even groot. Ik heb zo snel even niet wat teken gerei en upload bij de hand om een plaatje te maken, maar ik hoop dat je iets met de beschrijving kunt.

[stereohead]

@giMoz
Heb ik geprobeerd, het komt er wel in de buurt, maar zit er telkens net naast, komt waarschijnlijk door dat wat Janoz zegt.

@Cascade
Dat werkt inderdaad. Alleen.. hoe kun je de coördinaten van het verdwijnpunt berekenen?

[giMoz]

de coordinaten van de verdwijnpunten liggen op het snijpunt van de lijnen AB CD (voor horizontaal)

en het snijpunt vna lijn DA CB.

[Not Pingu]

RobIII schreef op donderdag 20 maart 2008 @ 14:35:
Dit ziet er wel interessant uit:

Wikipedia: Projective geometry
Wikipedia: Projective transformation

Helaas is het voor mij grotendeels chinees

Juist, als je diepteinformatie zou weten over polygoon ABCD zou je hier een vlak V voor kunnen definieren. Dan kun je met behulp van projectieve transformatie (kies vooral de matrixvorm onder Spatial transformations of planes) punt P op vlak V kunnen transformeren naar punt P' op vlak V' (die gebaseerd is op polygoon A'B'C'D' oftewel gewoon het XY-vlak).

Helaas is de grootste uitdaging (naar mijn idee) juist het verkrijgen van die diepteinformatie. Je zou polygoon ABCD kunnen schalen zodat het binnen polygoon A'B'C'D' past en de afstand tussen de punten (in het 2D vlak) kunnen gebruiken om diepteinformatie te achterhalen. Als je weet wat de FOV van je camera is, moet dat lukken.

[Voutloos]

Cascade schreef op donderdag 20 maart 2008 @ 14:36:
Niet ideaal, je krijgt problemen als de lijnstukken die je ziet parallel beginnen te lopen... moet wel beter kunnen.

Dus je moet vooral niet de webcam perfect opstellen.

Kwestie van twee methodes implementeren: indien lengte van de twee relevante zijkanten ongeveer gelijk, een evenwijdige lijn door P trekken en de relatieve afstanden gebruiken. Indien ongelijk, verdwijnpunt gebruiken. En dit voor beide dimensies.

[Rekcor]

gieuwsnierig vraagje: hoe ziet de calibratieprocedure er precies uit? moet ik zo'n rood vierkantje recht voor de webcam houden?

[engelbertus]

calibratie is denk ik een stukje code die zelf bekijkt wat de randen van het scherm zijn in het beeld, en aan de hand daarvan het beeld dus zegmaar "onthoekt"

stel je hebt een vierkant en bekijkt dat han 1 zijkant .dan wordt het beeld trapeziumvormig. het snijpunt van de diagonalen komt in hettrapezium dicht bij de korte evenwijdige zijd te liggen itt wanneer je het vierkant recht van voor zou bekijken, in welk geval het snijpunt van de diagonalen natuurlijk precies in het midden zou zijn.

het zou in mijn beleving niet zo erg zijn als je geen verdwijnpunt kunt vinden want in dat geval ligt het in iedergeval op de helft van de hoogte of de breedte, en daarmee stel je dan vast dat er geen vertekening in het beeld is over die as. dan weet je dus dat je de afstand verhouding over die as dus niet hoeft te calibreren/corrigeren.
i een geval waarbij er wel een verdwijnpunt gevonden wordt, hoe ver dat ook weg mag zijn, kun je het dus altijd uitrekenen de methode moet je allen nog even uitzoeken. hou der rekening mee dat je dus verhouding van de hoek in de bijv. de x richting dus ook moet corrigeren met de verhouding tussen de hoek in de y richting. en dus lijtk ht me dus best te doen. als je dat eens hebt gedaan, ciontroleer dat dan eens aan de hand van de projectiemethode. het tekeningetje wat je nu hebt gemaakt moet je dan alleen even voorstellen in 3D en dan is het wel uit te rekenen. en wellicht ontdek je dan hoe je "diepte" informatie kunt vinden om daarmee de correctie makkelijker uit te kunnen voern.

[Janoz]

Rood vierkantje, of hoeken aanwijzen. Dat maakt natuurlijk niet zo heel veel uit. Als je een willekeurig punt p kunt detecteren dan kun je die ook detecteren als je die bij A, B, C of D houdt.

@TS: Ik denk dat je inderdaad het beste 2 methoden kunt implementeren. Zodra de verdwijnpunten te ver weg beginnen te liggen neem je gewoon de lineaire manier.

[pkuppens]

Not Pingu schreef op donderdag 20 maart 2008 @ 15:48:
[...]


Juist, als je diepteinformatie zou weten over polygoon ABCD zou je hier een vlak V voor kunnen definieren. Dan kun je met behulp van projectieve transformatie (kies vooral de matrixvorm onder Spatial transformations of planes) punt P op vlak V kunnen transformeren naar punt P' op vlak V' (die gebaseerd is op polygoon A'B'C'D' oftewel gewoon het XY-vlak).

Helaas is de grootste uitdaging (naar mijn idee) juist het verkrijgen van die diepteinformatie. Je zou polygoon ABCD kunnen schalen zodat het binnen polygoon A'B'C'D' past en de afstand tussen de punten (in het 2D vlak) kunnen gebruiken om diepteinformatie te achterhalen. Als je weet wat de FOV van je camera is, moet dat lukken.

Iets makkelijker: zie het als affine transformation:
Wikipedia: Affine transformation
sectie:
Affine transformation of the plane

Of deze:
http://www.imagemagick.org/Usage/distorts/affine/

Disclaimer: volgens mij

[stereohead]

giMoz schreef op donderdag 20 maart 2008 @ 15:40:
de coordinaten van de verdwijnpunten liggen op het snijpunt van de lijnen AB CD (voor horizontaal)

en het snijpunt vna lijn DA CB.

Dat snap ik, maar hoe kan ik nu die coördinaten berekenen


En de kalibratie procedure, wordt gewoon iets dat je hoeken moet aanwijzen.

[ Voor 11% gewijzigd door stereohead op 20-03-2008 17:28 ]

[pkuppens]

Nog beter:
Wikipedia: Homography

Computing the plane to plane homography:
http://www.robots.ox.ac.u.../criminispaper/node3.html

Met deze methode kun je ook een beetje least squares inbakken, door meer dan 4 punten te gebruiken je afbeelding beter maken.

[stereohead]

Hmm al die matrices zeggen mij eigenlijk niets

(HAVO-5 WB12)

[mithras]

stereohead schreef op donderdag 20 maart 2008 @ 17:28:
[...]


Dat snap ik, maar hoe kan ik nu die coördinaten berekenen

Je hebt:
f(x) = a₁x + b₁. Die gaat door a: (x_a, y_a)
g(x) = a₂x + b₂. Die gaat door b: (x_b, y_b)

f(x) = g(x) geeft je een oplossing (vergelijking functie van eerste orde). Maar zoals pkuppens inderdaad zegt kan je hier beter met een matrixrepresentatie werken

[ Voor 9% gewijzigd door mithras op 20-03-2008 17:40 ]

[Verwijderd]

Hoewel niet in VB6 is het misschien handig om als referentie eens te kijken naar de implementatie van de PerspectiveTransform van de Java Advanced Imaging API. Deze doet alles al wat je wilt, maar is dus alleen nog niet bruikbaar in VB6 . Ik gebruik deze zelf overigens om speelkaarten te herkennen via een webcam, en 't transformeren werkt prima.

[.oisyn]

Cascade schreef op donderdag 20 maart 2008 @ 14:36:
Leuk probleem.

Zo even uit de losse pols:
Je hebt hier dus een rechthoek met willekeurige orientatie die je met de webcam bekijkt. Ik zou dan proberen een lijn te trekken vanuit P naar het verdwijnpunt (lijnperspectief) en het snijpunt bepalen met de zijkant (AD of BC) -> noem die even P_v. Je weet dan de verhouding tussen bijvoorbeeld AP_v en AD, die verhouding is hetzelfde in je 'rechte' versie. Hetzelfde kan met het snijpunt P_h met lijnstuk AB of CD. Niet ideaal, je krijgt problemen als de lijnstukken die je ziet parallel beginnen te lopen... moet wel beter kunnen.

Parallelle lijnen zijn helemaal geen probleem. Je zou dit kunnen zien alsof het snijpunt dan in het oneindige ligt. In feite komt het erop neer dat je gewoon een lijn moet trekken met dezelfde richting als de parallelle lijnen om het snijpunt met de zijkanten te berekenen.

Het feit is wel weer dat je hier wederom geen rekening houdt met perspectief, want de verhoudingen kloppen dan niet. Dit is echter wel te corrigeren, door eerst het midden te bepalen door het snijpunt van de diagonalen te berekenen, noem dit even punt Q. Als je nu voor punt Q op dezelfde manier bepaalt wat de verhoudingen met de lijnstukken zijn zoals je bij punt P al deed, kun je de correctie uitrekenen aangezien je weet dat Q altijd exact in het midden van het originele vierkant ligt.



Als je stelt dat de z van A gelijk is aan 1, dan is de z van D gelijk aan (AQ_ad / Q_adD). En derhalve kun je AP_ad / AD corrigeren door te doen:
y = AP_ad / AD
z = AQ_ad / Q_adD
y' = 1 / (z/y - z + 1)

En y' is dan de y-coordinaat in je originele vierkant (met 0=boven en 1=onder)

[ Voor 0% gewijzigd door .oisyn op 21-03-2008 11:42 . Reden: formule aangepast ]

[Cascade]

.oisyn schreef op vrijdag 21 maart 2008 @ 03:50:
[...]

Het feit is wel weer dat je hier wederom geen rekening houdt met perspectief, want de verhoudingen kloppen dan niet.

Ik zie het. Correctie is inderdaad nodig!

Ik denk dat de meest praktische oplossing voor TS de java PerspectiveTransform is die codetrotter voorstelde. Omzetten naar VB6 en toepassen is denk ik een stuk makkelijker/sneller dan eerst de theorie doorspitten.

Het 'waarom' is een ander punt, wel interessant dit.

[engelbertus]

@.oisin

je berekent nu wel een correctie, maar de correctie is volgens mij afhankelijk van waar piunt P zich bevind. en niet afhankelijk van waar de lijn van Q naar een verdwijnpunt zich op de rand van het beeld ligt.

ik heb je berekening niet verder gevolgd, dus misschien heb je dat ook zo gedaan natuurlijk.

de correctie is volgens mij dus 2 keer een lineaire functie. eerst voor de hoek van het scherm, en vervolgens voor de plek van het punt P.
en dat dan voor zowel de x als de y richting.

verder denk ik dat het onzin is om 2 manieren te gaan implementeren. omdat je voor jou berekening dus bijvoorbeeld altijd al een verdwijnpunt moet hebben. als dat heeeeeeeel ver weg licht , dan zijn de boven en onderrand bijvoorbeeld al evenwijdig. de kans dat iemand 2 ounten met een exact gelijke x of y coordinaat aanklikt is erg klein, en alsnog kun je dat dan detecteren. je maakt ze dan ongelijk, of je neemt zoals jij zegt een lijn evenwijdig aan de boven of onderrand en door het punt P

verder kun je eens zoeken over geodesie, landmeetkunde en onthoeken. dat doen ze ook bij luchtfotos om er een kaart van te maken bijvoorbeeld. wellicht dat er daar iets is te vinden is, of misschien is dat te ingewikkeld. als ze ook de bolling van de aarde in ogenschouw nemen.

[ Voor 43% gewijzigd door engelbertus op 21-03-2008 09:31 ]

[.oisyn]

engelbertus schreef op vrijdag 21 maart 2008 @ 09:23:
@.oisin

je berekent nu wel een correctie, maar de correctie is volgens mij afhankelijk van waar piunt P zich bevind. en niet afhankelijk van waar de lijn van Q naar een verdwijnpunt zich op de rand van het beeld ligt.

ik heb je berekening niet verder gevolgd, dus misschien heb je dat ook zo gedaan natuurlijk.

Natuurlijk
Q gebruik ik om de verhouding te bepalen van de diepte van punt A (die stel ik op 1) en de diepte van punt D (dat is de z die ik daar uitreken, uit de verhouding tussen de afstand A en Q_ad en de afstand D en Q_ad, die bij een gelijke z-waarde 1:1 zou moeten zijn aangezien hij dan precies op de helft ligt).

Nu je weet dat punt D z keer zo "diep" ligt als A, kun je de berekende y waarde van het snijpunt wat je gekregen hebt van P (met y=0 op punt A en y=1 op punt D) corrigeren aan de hand van y' = 1 / (z/y - z + 1)

[oeps nu ontdek ik een foutje in de vergelijking, hier staat ie nu goed en ik zal m'n vorige post even aanpassen]