De wiskunde van de beeldherkenning Op zoek naar wat er niet verandert!
In het kader van: (Bij) de Faculteit Wiskunde en Informatica van de TU/e op bezoek
c Faculteit Wiskunde en Informatica, TU/e
Inhoudsopgave 1 Beeldherkenning (Computer vision)
1
2 De dubbelverhouding: een verhouding van verhoudingen
3
3 Wat zit er achter deze ‘invariantie’ ?
4
4 Het gebruik van de dubbelverhouding
7
5 De tripelverhouding
9
ii
1
Beeldherkenning (Computer vision)
Als je plaatjes bekijkt van spullen of personen valt het je niet meer op dat je bijvoorbeeld zonder moeite een tafel of een persoon herkent, terwijl het plaatje toch vanuit een bepaalde gezichtshoek is gemaakt en daarmee typische eigenschappen van bijvoorbeeld die tafel anders zijn weergegeven: op de foto zijn hoeken tussen blad en poten doorgaans niet meer 90◦ . In het gebied Beeldherkenning (Engels: Computer Vision) zoekt men naar eigenschappen van objecten die niet veranderen als bijvoorbeeld het gezichtspunt bij de opname verandert. Een eenvoudig voorbeeld: een rechte lijn blijft recht ook al verandert het gezichtspunt. Maar een cirkel blijft in de regel geen cirkel, maar verandert doorgaans in een ellips. In het algemeen veranderen de onderlinge verhoudingen van punten en rechten. Eigenschappen die niet veranderen (we spreken wel van invarianten) zijn van belang voor het herkennen van patronen in foto’s. Het kan dan gaan om het bepalen van afstanden op foto’s, het detecteren van randen van voorwerpen op foto’s, of zelfs het herkennen van gezichten. Het vakgebied kwam in de jaren ’60 van de vorige eeuw op en is inmiddels een bloeiende tak van wetenschap waarin wiskundigen en informatici actief onderzoek doen en steeds verder doordringen in de geheimen van de beeldherkenning. Vooral in de biomedische technologie is grote behoefte aan deze technieken om aan de hand van scans en andere medische opnamen conclusies te helpen trekken. In dit document gaan we in op de vraag hoe we afstanden uit foto’s kunnen reconstrueren met behulp van de zogenaamde dubbelverhouding.
Afstanden bepalen aan de hand van een foto Als je afstanden wilt bepalen vanaf een foto of vanaf een video-opname, kom je er al snel achter dat dat niet zo eenvoudig is. Dat komt omdat de verhoudingen ‘scheefgetrokken’ zijn. Onderstaande foto laat een opname van een voetbalveld zien. De lijnen van het veld zorgen natuurlijk voor aanknopingspunten.
Als je beschikt over de ware afmetingen van het veld, kun je misschien terugrekenen om de afstand tussen twee punten op het veld te bepalen. In de wiskunde heeft men gezocht naar een systematiek in dat terugrekenen. Centraal daarbij staat het begrip dubbelverhouding, dat we in deze les aan de orde stellen. De dubbelverhouding is een begrip uit de meetkunde en is een 1
generalisatie van de verhouding van twee lijnstukken. De dubbelverhouding is een voorbeeld van een zogenaamde invariant; samen met andere invarianten speelt de dubbelverhouding een essenti¨ele rol in de hedendaagse beeldherkenning.
Wat is het probleem? Een foto kun je zien als een (centrale) projectie van een voorstelling uit de realiteit op een plat vlak zoals in het bijgaande plaatje is ge¨ıllustreerd. vlak voorwerp
centrum
Het probleem is dat afstanden, verhoudingen en dergelijke in een plaatje anders zijn dan in het origineel. Laten we dit eens analyseren voor verhoudingen. In het plaatje hieronder bekijken we een centrale projectie (vanuit punt P ) van drie punten A, B en C. Voor het nu volgende gaan we er vanuit dat deze drie punten op een rechte lijn liggen (bijvoorbeeld markeringspunten van een lijn op een sportveld). De projecties van de drie punten noemen we A0 , B 0 en C 0 . Ze liggen ook op een rechte, bijvoorbeeld op een foto. P
C’ B’ A’ A
B
C
Aan dit plaatje kun je al aflezen dat verhoudingen veranderen bij centrale projectie: de verhouding AB/BC verschilt in de regel van de verhouding A0 B 0 /B 0 C 0 . Ga maar na. Toch hangen die verhoudingen met elkaar samen en de vraag is hoe? Opgave 1 (Veranderingen in verhoudingen) Ga na of de verhouding A0 B 0 /B 0 C 0 verandert als je de rechte A0 B 0 beweegt op een van de volgende manieren. a) Je beweegt A0 B 0 parallel aan zichzelf naar boven. b) Je draait A0 B 0 om A0 2
2
De dubbelverhouding: een verhouding van verhoudingen
Definitie van de dubbelverhouding In Opgave 1 heb je gezien dat de verhouding A0 B 0 /B 0 C 0 verandert. Opmerkelijk is dat als je vier punten in het spel betrekt er een ‘verhouding van verhoudingen’ te maken is die niet verandert! De zogenaamde dubbelverhouding. De dubbelverhouding van vier punten A, B, C en D op de rechte lijn ` is de volgende uitdrukking (verhouding van verhoudingen): AC AD : . BC BD We noteren deze dubbelverhouding met (ABCD). Het gaat hierbij om gerichte lijnstukken: als je de lengte AC positief telt, dan moet je CA negatief tellen. Voorbeeld De dubbelverhouding (ABCD) van de vier punten A = 0, B = 1, C = 4 en D = 7 op de x–as bereken je als volgt.
A
B
0
1
C 2
3
D
4
5
6
7
Eerst bepalen we AC = 4, BC = 3, AD = 7 en BD = 6. Voor de dubbelverhouding krijg je dan: AC AD 4 7 4 6 24 8 (ABCD) = : = : = · = = . BC BD 3 6 3 7 21 7 Opgave 2 (Een dubbelverhouding bepalen) Op de x–as zijn de punten A = −3, B = 0, C = −1 en D = 3 gegeven. Bepaal de dubbelverhouding (ABCD). Let op dat bijvoorbeeld BC = −1 negatief is. Wat verandert er nou precies niet bij de dubbelverhouding? De voor de beeldherkenning belangrijke eigenschap van de dubbelverhouding verwoorden we in de volgende stelling. Stelling (Invariantie van de dubbelverhouding). Als A, B, C, D punten op de rechte ` zijn en A0 , B 0 , C 0 en D0 punten op de rechte `0 zijn z´ o dat de rechten AA0 , BB 0 , CC 0 en DD0 door ´e´en punt gaan, dan geldt (ABCD) = (A0 B 0 C 0 D0 ). P
C’
B’
D’
A’ A
B
C
3
D
Men zegt wel dat de dubbelverhouding ‘invariant is onder centrale projectie’. De stelling gebruik je in de praktijk als volgt: A, B, C en D zijn bijvoorbeeld punten in de ‘echte’ wereld, en A0 , B 0 , C 0 en D0 zijn punten op een foto–opname en kunnen dus gemeten worden. In de volgende paragraaf gaan we in op het bewijs van deze stelling.
3
Wat zit er achter deze ‘invariantie’ ?
De stelling doet een uitspraak die niet zo voor de hand liggend is. Hoe kun je nu toch inzien dat de stelling waar is? Een manier die men heeft bedacht is de volgende. Door meetkundige redeneringen kun je inzien dat de dubbelverhouding (ABCD) geheel is uit te drukken in sinussen van hoeken bepaald door de vier lijnen door het centrum P (aangegeven in de figuur met `1 , `2 , `3 , `4 ). P
l1
A
l3
l2
B
l4
C
D
Er blijkt namelijk te gelden (straks meer over het waarom): (ABCD) =
sin ∠(`1 , `3 ) sin ∠(`1 , `4 ) : . sin ∠(`2 , `3 ) sin ∠(`2 , `4 )
Aan deze expressie met sinussen zie je dat de preciese positie van de punten A, B, C en D op de lijnen `1 , `2 , `3 , `4 niet van belang is, maar alleen de hoeken tussen de vier lijnen! Omdat A0 , B 0 , C 0 en D0 ook op achtereenvolgens `1 , `2 , `3 , `4 liggen, is de dubbelverhouding (A0 B 0 C 0 D0 ) gelijk aan dezelfde expressie met sinussen. Dus (ABCD) = (A0 B 0 C 0 D0 )! Als je wilt weten hoe die sinussen verschijnen, lees dan het volgende stuk.
Hoe kom je aan die sinussen? De sinussen verschijnen als we de volgende stappen doorlopen: • We vervangen de verhoudingen van lijnstukken door verhoudingen van oppervlakten (hier hebben we een formule voor de oppervlakte van een driehoek voor nodig). • Met een andere formule voor de oppervlakte verschijnen de sinussen. • In de herschreven uitdrukking voor de dubbelverhouding valt van alles tegen elkaar weg, behalve de sinussen. We hebben nodig: oppervlakte van een driehoek Hoe kom je nu van verhoudingen op de lijn door A, B, enz. naar hoeken bij P ? Via oppervlakten van driehoeken. Hier is wat we nodig hebben van oppervlakten van driehoeken. 4
• Oppervlakte van een driehoek I Ongetwijfeld weet je dat je de oppervlakte van een driehoek kunt berekenen uit ‘basis maal halve hoogte’. Maar we hebben ook een andere manier nodig om de oppervlakte te bepalen. • Oppervlakte van een driehoek II De oppervlakte van een driehoek is gelijk aan het halve product van twee zijden vermenigvuldigd met de sinus van de door de twee zijden ingesloten hoek. In formulevorm: O(4ABC) =
1 · |AB| · |AC| · sin(∠BAC), 2
waarin we met |AB| de lengte van het lijnstuk AB aangeven. Opgave 3 (De oppervlakte van een driehoek ) a) Ga na hoe je de nieuwe formule afleidt uit de formule ‘basis maal halve hoogte’. Neem bijvoorbeeld AB als basis. b) In de formule hebben we de zijden AB en AC ‘uitverkoren’. Formuleer formules voor de oppervlakte van 4ABC als we AB en CB kiezen of AC en BC. We hebben nodig: verhouding van lijnstukken en verhouding van oppervlakten Bekijk de volgende figuur met centrum P en de punten A, B en C. Aan de hand hiervan illustreren we hoe een verhouding van lengtes in verband kan worden gebracht met een verhouding van oppervlakten. P
A
B
C
Nemen we AC als basis van 4P AC, en noemen we de hoogte van de driehoek (de afstand van de rechte AC tot P ) h, dan is de oppervlakte van 4P AC gelijk aan 1 · |AC| · h. 2 Net zo is de oppervlakte van 4P BC gelijk aan 1 · |BC| · h 2 5
(dezelfde h). Dus de verhouding |AC|/|BC| is gelijk aan O(4P AC)/O(4P BC). Samengevat: AC O(4P AC) = . BC O(4P BC) Op soortgelijke wijze volgt (met D in plaats van C): AD O(4P AD) = . BD O(4P BD) En nu de sinussen... Deze laatste verhouding van oppervlakten herschrijven we door gebruik te maken van onze andere formule voor de oppervlakte: O(4P AC) = |P A| · |P C| · sin(∠AP C) en O(4P BC) = |P B| · |P C| · sin(∠BP C), enz. Met dit gereedschap gaan we de dubbelverhouding (ABCD) nu te lijf. P
l1
A
l3
l2
B
l4
C
D
Op ´e´en detail gaan we verder niet in: we zullen ons in de volgende berekening niet druk maken om het feit dat het geori¨enteerde lijnstukken betreft (zie blz. 3). • Stap 1: Omschrijven naar oppervlakten: AC AD O(4P AC) O(4P AD) : = : BC BD O(4P BC) O(4P BD) • Stap 2: Oppervlakteformule gebruiken: O(4P AC) O(4P AD) P A · P C · sin ∠(`1 , `3 ) P A · P D · sin ∠(`1 , `4 ) : = : O(4P BC) O(4P BD) P B · P C · sin ∠(`2 , `3 ) P B · P D · sin ∠(`2 , `4 ) • Stap 3: Breuk in het rechterlid vereenvoudigen tot: sin ∠(`1 , `3 ) sin ∠(`1 , `4 ) : sin ∠(`2 , `3 ) sin ∠(`2 , `4 ) • Conclusie:
AC AD sin ∠(`1 , `3 ) sin ∠(`1 , `4 ) : = : BC BD sin ∠(`2 , `3 ) sin ∠(`2 , `4 )
6
4
Het gebruik van de dubbelverhouding
Het gebruik van de dubbelverhouding om afstanden te bepalen, berust op de volgende twee observaties: • De dubbelverhouding legt de positie van het vierde punt vast Als je de dubbelverhouding van vier punten A, B, C, D op een rechte lijn weet en de positie van drie van de vier punten, dan kun je de positie van het vierde punt bepalen. • De dubbelverhouding van vier punten kun je uit een foto bepalen De dubbelverhouding van vier punten A, B, C, D op een rechte kun je bepalen met behulp van een foto (centrale projectie) van die vier punten. Op de foto kun je namelijk afstanden meten en de dubbelverhouding bepalen van de opname van de vier punten. Omdat de opname een centrale projectie van de oorspronkelijke vier punten is, heb je via bovenstaande stelling nu ook de dubbelverhouding (ABCD) van A, B, C, D te pakken. Als je in de praktijk de positie van een punt wilt weten of berekenen, dan ga je op zoek naar een rechte lijn waar dat punt op ligt en waar ook drie bekende punten op liggen, zogenaamde referentiepunten. Voorbeeld We nemen een rechte lijn waarvan we de punten beschrijven met behulp van re¨ele getallen. Veronderstel dat A, B en C de referentiepunten zijn, die horen bij de getallen 0, 1 en 100. Veronderstel dat D onze onbekende is, zeg x, maar dat (ABCD) = 2. We krijgen dan de volgende vergelijking: (ABCD) = 2 =
AC AD 100 x : = : BC BD 99 x − 1
We vinden hieruit 198x = 100(x − 1) zodat 98x = −100 en x = −50/49. Bij referentiepunten kun je denken aan punten die je om de een of andere reden kent, zoals hoekpunten van een zijlijn op een sportveld. De dubbelverhouding zou je kunnen weten via een opname waarop je eenvoudigweg alle afstanden hebt opgemeten. Zie Opgave 5 hieronder. Opgave 4 (De dubbelverhouding nader bekeken) We gaan uit van vier verschillende punten A, B, C en D op een rechte. In de expressie voor de dubbelverhouding komen vier gerichte lijnstukken voor: AC, BC, AD en BD. a) Veronderstel dat (ABCD) negatief is. Analyseer de dubbelverhouding om aan te tonen dat in dat geval precies ´e´en van de punten C en D tussen A en B ligt. b) Analyseer de dubbelverhouding om te laten zien dat (ABCD) = (BADC). Opgave 5 (De dubbelverhouding echt gebruiken) Tijd voor echte metingen. De afmetingen van voetbalvelden zijn niet precies vastgelegd, maar mogen binnen zekere grenzen vari¨eren. De breedte en de lengte van het veld zijn bijvoorbeeld niet geheel vastgelegd. Sommige maten op het veld zijn wel voorgeschreven, zoals de afmetingen van het doel en de straal van de middencirkel. Op bijgaande foto zie je dat de middencirkel behoorlijk vervormd is (wat voor figuur is het geworden denk je?). 7
Bepaal aan de hand van de foto de breedte van het veld (in yards of meters; een yard is 0, 9144 meter).
8
5
De tripelverhouding
De uitgebreide dubbelverhouding: de tripelverhouding We hebben tot dusverre de invariantie gezien van de dubbelverhouding van 4 punten op ´e´en rechte bij centrale projectie. Een nadeel hiervan is dat de punten op ´e´en rechte dienen te liggen. Bij de tripelverhouding vervalt dit bezwaar, zij het dat de punten nu in ´e´en vlak moeten liggen. Bij de dubbelverhouding is een voordeel dat het meten van afstanden relatief eenvoudig is. Bij de tripelverhouding kijken we naar oppervlakten, die wat moeilijker zijn uit te rekenen. We gaan nu verder met de definitie van tripelverhouding: Zeg we hebben 5 punten (A, B, C, D, E) in een plat vlak, C
D
E
A
B
We defini¨eren de tripelverhouding van de 5 punten (A, B, C, D, E) als de volgende verhouding van gerichte oppervlakten van driehoeken: (ABCDE) = (
Opp4ABD Opp4BCD Opp4CAD : : ) Opp4ABE Opp4BCE Opp4CAE
We bedoelen hierbij met gerichte oppervlakte: De gerichte oppervlakte is de oppervlakte voorzien van een plus of min-teken. Het plus of min-teken wordt bepaald door de ori¨entatie van de hoekpunten. De hoekpunten worden linksom of rechtsom doorlopen. De ‘gewone‘ oppervlakte is gelijk aan de absolute waarde van de gerichte oppervlakte.
9
Er blijkt nu, vergelijkbaar met de situatie bij de dubbelverhouding, bij centrale projectie invariantie van tripelverhoudingen te gelden, dat wil zeggen: We hebben 5 punten (A, B, C, D, E) in een vlak die door een centrale projectie afgebeeld worden op de punten (A0 , B 0 , C 0 , D0 , E 0 ) in een ander vlak, zie figuur.
P
C’ D’ E’
B’
A’
C
D
A
E
B
De tripelverhoudingen van (A, B, C, D, E) en (A0 , B 0 , C 0 , D0 , E 0 ) zij nu aan elkaar gelijk: (ABCDE) = (A0 B 0 C 0 D0 E 0 ) (Het bewijs laten we achterwege.) Als we nog even kijken naar de definitie van tripelverhouding, dan is deze genoteerd als (a : b : c). We bedoelen nu met (a : b : c) = (d : e : f ) het volgende: Er bestaat een λ zodanig dat λ a = d en λ b = e en λ c = f. Bijvoorbeeld, (2 : 3 : 7) = (8 : 12 : 28) Dit kunnen we ook gebruiken in de vorm, mits de noemers 6= 0 zijn: a/d = b/e = c/f.
10
Het nut van de invariantie van de tripelverhouding is ook nu gebaseerd op twee observaties: • Ken je de positie van 4 van de 5 punten in een vlak ´en de tripelverhouding van alle 5, dan kun je de positie van het 5e punt in dat vlak bepalen. Zoals we bij de dubbelverhouding een willekeurig punt op de rechte door de punten als oorsprong kozen, zo kiezen we nu een willekeurig punt in het vlak als oorsprong, en bepalen de positie ten opzichte van die oorsprong. (Zie opgave 6) • De tripelverhouding van 5 punten bepaal je met behulp van een afbeelding van de 5 punten. Op de afbeelding kun je alle posities van alle punten meten en daaruit de gerichte oppervlakten van de desbetreffende driehoeken bepalen. De eenheden waarin je de oppervlaktes meet zijn niet relevant omdat we werken met verhoudingen van oppervlakten. In onderstaande afbeelding zijn bekende punten A, B, C, D aangegeven. De posities van de punten E1 , E2 , .. zijn onbekend.
11
Opgave 6 (De tripelverhouding echt gebruiken) We hebben van onderstaande figuur oppervlakten van de driehoeken voor je uitgerekend bij de punten A, B, C, D, E, deze zijn achtereenvolgens: Opp4ABD = 23034, Opp4ABE = 5586, Opp4BCD = 14202, Opp4BCE = 16296, Opp4CAD = 13708, Opp4CAE = 29062. NB. De lengte eenheid is ‘pixel‘ vandaar de grootte-orde van de oppervlaktes.
In de figuur op de volgende pagina zien we de bekende grootheden aangegeven.
12
We hebben van de figuur van het speelveld de oppervlakten van de driehoeken voor je uitgerekend bij de corresponderende punten A, B, C, D, E, echter hebben we nu voor het onbekende punt E = A + (p, q) gekozen. (We bepalen de positie dus ten opzichte van het punt A.) We krijgen nu de oppervlakten, uitgedrukt in de onbekenden p en q: Opp4ABD = 105, Opp4ABE = 9q, Opp4BCD = 124, Opp4BCE = 389 − 22p, Opp4CAD = 160, Opp4CAE = 22p − 9q. Probeer met bovenstaande gegevens de onbekenden p en q te berekenen. De lengte eenheid waarin is gemeten is yard. Welke manieren ken je om de oppervlakte van een driehoek uit te rekenen? Opgave 7 (De quadrupelverhouding? ) Probeer samen met je wiskundeleraar te bedenken hoe het nog algemener zou kunnen dan de tripelverhouding en wat je daar dan mee zou kunnen berekenen.
13
Appendix: Invarianten De dubbelverhouding is een voorbeeld van wat men in de wiskunde een invariant noemt. De reden is dat de dubbelverhouding invariant is (dat wil zeggen niet verandert) onder een of andere operatie, in ons geval centrale projectie. Zonder dat je het als zodanig hebt leren kennen, heb je al eerder kennis gemaakt met invarianten, en wel bij kwadratische vergelijkingen. De discriminant van een kwadratische vergelijking is namelijk een voorbeeld van een invariant. In de volgende opgave kom je te weten hoe dit zit. Opgave De discriminant van de kwadratische vergelijking ax2 + bx + c = 0 is gelijk aan b2 − 4ac. Misschien herinner je je nog dat je met behulp van de discriminant kunt zien hoeveel (re¨ele) oplossingen een kwadratische vergelijking heeft: als bijvoorbeeld b2 − 4ac > 0, dan heeft de vergelijking twee verschillende nulpunten. a) De kwadratische functie f gegeven door f (x) = x2 − x − 2 heeft twee nulpunten: −1 en 2. Geef een schets van de grafiek. Bepaal het functievoorschrift van de functie g waarvan de grafiek uit die van f ontstaat door 10 naar rechts te transleren. Wat zijn de nulpunten van g? Bepaal de discriminant van beide kwadratische vergelijkingen. b) In onderdeel a) heb je als het goed is in beide gevallen dezelfde discriminant gevonden. Dit is geen toeval: als je een kwadratische uitdrukking transleert, krijg je een nieuwe kwadratische uitdrukking met precies dezelfde discriminant. c) Begin maar met de functie f gedefinieerd door f (x) = ax2 + bx + c, waarin a, b, c constanten zijn. Geef het functievoorschrift van de kwadratische functie g waarvan de grafiek uit die van f ontstaat door translatie over d. d) Laat door berekening zien dat de discriminanten van f en g aan elkaar gelijk zijn. We zeggen wel: ‘de discriminant is invariant onder translatie’. De discriminant van een kwadratische uitdrukking geeft informatie over het aantal nulpunten ervan. Omdat het aantal nulpunten van een kwadratische functie niet verandert onder translatie, is het niet verwonderlijk dat de discriminant ook niet verandert. Toch is deze laatste redenering alleen natuurlijk niet afdoende. Het zou nog best mogelijk zijn dat de precieze formule voor de discriminant anders wordt. Dat het aantal nulpunten niet verandert bij translatie, zegt je alleen dat de discriminant hetzelfde teken houdt of nul blijft. Als je dus alleen naar het aantal nulpunten kijkt, dan zou de discriminant D van een kwadratische functie bijvoorbeeld best kunnen veranderen in een formule als (d2 + 1) · D.
14
