Van foto's tot 3-dimensionale modellen : de wiskunde achter virtuele realiteit
Theo Moons 1. Computermodellen en virtuele realiteit. Computermodellen van bestaande 3-dimensionale (3D) omgevingen worden steeds belangrijker bij de besluitvorming in verschillende maatschappelijke domeinen. Voorbeelden hiervan zijn het gebruik van 3D-stadsmodellen in ruimtelijke ordening (bv. om het e ect van een gepland bouwwerk op het omliggende landschap te beoordelen; of, als basis voor computersimulaties om de geluidsoverlast in de naburige woningen van een nieuw aan te leggen weg in te schatten of om de optimale positionering van antennes voor mobiele telefonie te bepalen). Een ander belangrijk toepassingsdomein van 3-dimensionale computermodellen is bij de planning en uitvoering van chirurgische ingrepen: een levensgevaarlijke operatie wordt eerst uitgeprobeerd op een 3-dimensionaal model van de patient dat geconstrueerd werd door volumetrische gegevens verkregen met CT, MR, PET, . . . scanners te combineren. De occasionele computergebruiker is zeker reeds in aanraking gekomen met virtuele werelden in computerspellen of bij een virtueel museum- of stadsbezoek via internet. En, wie heeft nog niet gehoord van de technologische evoluties in de lmwereld waar adembenemende visuele e ecten verkregen worden door beelden van levende personen en bestaande omgevingen te combineren met door de computer gegenereerde objecten? Deze module wil de (wiskundige) basisprincipes uitleggen die toelaten om een 3-dimensionaal computermodel van een bestaande omgeving te construeren uit een aantal 2-dimensionale beelden (foto's, lm- of videobeelden).
2. Beeldvorming in een digitale camera. De meest eenvoudige voorstelling van het beeldvormigsproces in een (foto-, lm- of video) camera is die van een camera obscura. In een camera obscura wordt het beeld van de omgeving (de scene genaamd) gevormd door de lichtstralen die door de voorwerpen in de scene weerkaatst worden en via het centrum van de lens op het beeldvlak invallen (cf. Figuur 1). Dit beeldvlak kan het oppervlak van een lichtgevoelige lm (zoals bij een foto- of lmcamera) of van een CCD (zoals bij een digitale camera of bij een videocamera) zijn. Het beeld dat op die manier gevormd wordt, is het foto-negatieve beeld van de scene. Het foto-positieve beeld dat men waarneemt wanneer men naar een foto of 1
dia-positief beeld
f
Figuur 1:
In een
f
camera obscura wordt het beeld van de scene gevormd door de lichtstralen
die door de voorwerpen in de sc ene weerkaatst worden en via het centrum van de lens op het beeldvlak invallen. Het foto-positief beeld situeert zich in een (hypothetisch) vlak v o or de camera.
een televisiescherm kijkt, komt daarentegen overeen met de projectie van de scene op een (hypothetisch) vlak dat gesitueerd is voor de camera op dezelfde afstand van het centrum van de lens als het beeldvlak. In het vervolg van deze tekst zal met de term \beeldvlak" steeds dit hypothetische vlak voor de camera bedoeld worden. Wiskundig gesproken, is een scene een verzameling punten, lijnstukken en oppervlakken in de Euclidische ruimte IR3 ; en, een beeld van een voorwerp in de scene is de perspectiefprojectie van dat voorwerp op het beeldvlak. Hoewel de camera obscura een overgesimpli eerde voorstelling van de beeldvorming in een echte camera geeft, kan men toch vaststellen dat de betere lenzensystemen die tegenwoordig in de handel verkrijgbaar zijn, een zeer goede benadering van een perspectiefprojectie realiseren. Voor onze doeleinden is het dus niet nodig om een geso stikeerder camera-model te gebruiken. In formulevorm wordt het beeldvormingsproces in een camera obscura het eenvoudigst beschreven ten opzichte van een zogenaamd camera-gecentreerd assenstelsel. Dit is een rechtsdraaiend, orthonormaal assenstelsel voor de scene dat als volgt gede nieerd wordt (zie Figuur 2 (links)) : de oorsprong van het assenstelsel valt samen met het centrum van de lens van de camera (d.i. het projectiecentrum), de Z-as is de optische as van de lens, en het XY -vlak is het vlak door de oorsprong en loodrecht op de Z-as. Het beeldvlak is het vlak met vergelijking Z = 1. Het beeld van een punt P in de scene is dan het snijpunt p van de rechte door P en door de oorsprong van het camera-gecentreerd assenstelsel en het vlak met vergelijking Z = 1. Als (X; Y; Z) 2 IR3 het stel coodinaten van het scenepunt P t.o.v. het camera-gecentreerd assenstelsel is, dan heeft het beeldpunt p als coordinaten (u; v; 1) met X Y u= en v = : (1) Z Z 2
X
Z
u
x
(X,Y,Z)
(u,v) v
0
Z=1 y
Y
Figuur 2: Links: In een camera-gecentreerd assenstelsel heeft de projectie van een scenepunt (X; Y; Z) in het beeldvlak als coordinaten (u; v; 1) = ( XZ ; YZ ; 1). Rechts: De positie van een beeldpunt in een digitaal beeld wordt uitgedrukt in pixelco ordinaten.
origineel Figuur 3:
2
4
8
16
Een digitaal beeld is opgebouwd uit een groot aantal minuscule beeldelementjes,
pixels genaamd.
Wanneer men werkt met digitale beelden, dan is het handiger om de positie van een beeldpunt aan te geven met zogenaamde pixelcoordinaten. De reden hiervoor is dat een digitaal beeld is opgebouwd uit een groot aantal minuscule beeldelementjes, pixels genaamd. Het woord \pixel" is een contractie van de Engelse woorden \picture element". In Figuur 3 werd een digitaal beeld uitvergroot zodat de pixels zichtbaar worden. Om een digitaal beeld op een computerscherm te visualiseren, wordt elke pixel van het beeldscherm belicht met een lichtstraal van een intensiteit (en kleur) die evenredig is aan de intensiteit (en de kleur) van de lichtstraal die op die positie in het beeldvlak inviel tijdens opname van het beeld. In een computergeheugen wordt een digitaal (grijswaarden)beeld dus opgeslagen in de vorm van een m n-matrix van gehele getallen die voor elke pixel de nodige lichtintensiteit weergeven1 ; en de positie van elke pixel in het beeld wordt bepaald door het rij- en het kolomnummer van die pixel in deze matrix (cf. Figuur 2 (rechts)). Dit rijen kolomnummer, meestal genoteerd met (x; y), noemt men de pixelcoordinaten van de 1 Voor een kleurbeeld worden voor elke pixel 3 gehele getallen gegeven die elk de intensiteit van de lichtstraal in 3 welbepaalde kleurbanden (nl. rood, groen en blauw) weergeven.
3
beschouwde pixel. Het verband tussen de meetkundige (u; v)-coordinaten hierboven en de pixelcoordinaten van een beeldpunt is gegeven door : (
x = kx u + s v + x0 y = ky v + y0
(2)
Hierin zijn (x0 ; y0 ) de pixelcoordinaten van het optisch centrum van het beeld (d.i. het punt waarin de optische as van de camera het beeldvlak snijdt) en geven kx en ky het aantal pixels per lengte-eenheid in de horizontale en de vertikale richting weer. kx en ky bepalen dus impliciet de lengte en de breedte van een pixel. De parameter s tenslotte geeft aan hoe sterk de vorm van een pixel afwijkt van een rechthoek. Bij de betere digitale camera's zijn de pixels meestal rechthoekig en is s = 0. De getallen kx , ky , s, x0 en y0 noemt men de interne cameraparameters of ook wel de calibratiegegevens van de camera. Vooraleer verder te gaan, herschrijven wij de bovenstaande formules nog even in matrixvorm. Als men een punt p met pixelcoordinaten (x; y) in het beeldvlak voorstelt door de kolomvector p = (x; y; 1)t 2 IR3 , dan kan men formule (2) schrijven als: 0 1 0 10 1 x kx s u0 u B C B C B p = @ y A = @ 0 ky v0 A @ v C A ;
1
0
0
1
1
(3)
waarbij de kolomvector (u; v; 1)t 2 IR3 de Euclidische coordinaten van het beeldpunt t.o.v. het camera-gecentreerd assenstelsel weergeeft. Uit formule (1) volgt nu onmiddellijk dat 0 1 0 1 0 X 1 X Z C u C 1 B B B v C=B B C Y B Y C C ; @ A B Z C= A @ A Z @ 1 Z 1 met (X; Y; Z) het stel coordinaten van het punt P in de scene waarvan p het beeld is. Indien wij nu ook het scenepunt P identi ceren met de kolomvector (X; Y; Z)t , dan kan deze laatste formule geschreven worden als 0 1 0 1 u X C B C B @ v A=@ Y A=P
1
Z
(4)
met = Z. Samen met formule (3) geeft dit de volgende projectievergelijkingen : p = K P ; waarbij
de calibratiematrix
0 1 kx s u0 C K=B @ 0 ky v0 A
0 0 1 van de camera genoemd wordt. 4
(5)
3. De epipolaire relatie tussen beelden van dezelfde scene. Het doel van deze module is om te onderzoeken hoe men de ruimtelijke struktuur van een scene kan reconstrueren uit een of meerdere beelden van die scene. Wiskundig gezien, kan men dit probleem nu vertalen als: bepaal voor elk punt p in het beeld de coordinaten van het punt P in de sc ene waarvan p de projectie in het beeldvlak is. Een blik op de projectievergelijkingen (5) toont duidelijk aan dat dit probleem in die vorm onoplosbaar is. Immers, P oplossen uit vergelijking (5) geeft
P = K 1p : Dus, wanneer alleen het beeldpunt p gegeven is, of zelfs indien ook de calibratiegegevens van de camera (d.i. de matrix K) gekend zouden zijn, dan nog ligt het scenepunt P niet volledig vast, want de parameter kan theoretisch elk (positief) reeel getal zijn. Dit hoeft ons niet te verwonderen, want het is bekend dat men met slechts een oog geen dieptezicht heeft. Men kan dus verwachten dat er minstens 2 beelden nodig zijn om de scene te kunnen reconstrueren. En, inderdaad, als p de projectie van een scenepunt P in het beeldvlak is, dan ligt P op de rechte door het projectiecentrum en het beeldpunt p. Deze rechte noemt men de projecterende rechte van P voor de gegeven camera. Indien nu de projecties p1 en p2 van P in twee beelden gegeven zijn, dan kan men de positie van P in de scene bepalen als het snijpunt van de projecterende rechten van P in de twee camera's, zoals gellustreerd in Figuur 4 (links). Het bepalen van dit snijpunt | en dus ook het stel coordinaten van het scenepunt P | is vrij gemakkelijk op voorwaarde dat men de positie, de orientatie en de calibratiegegegevens van beide camera's kent, Wanneer daarentegen alleen de beelden gegeven zijn en men dus de positie, de orientatie en de calibratiegegevens van de camera's niet kent, dan wordt het reconstrueren van de scene een heel stuk minder eenvoudig. Maar laat ons Figuur 4 eens wat systematischer analyseren. Beschouw een (willekeurig) punt p1 in het eerste beeld. p1 is de projectie van een punt P in de scene; en, belangrijker nog, dit scenepunt P ligt op de projecterende rechte L van p1 in de eerste camera. De projectie p2 van P in het tweede beeldvlak kan bijgevolg niet eender waar in het tweede beeld terechtkomen, maar p2 moet liggen op de rechte `2 die de projectie van L in het tweede beeld is (zie Figuur 4 (rechts)). De rechte `2 noemt men de epipolaire rechte van p1 in het tweede beeld. Meetkundig gezien, is de epipolaire rechte `2 niets anders dan de snijlijn met het tweede beeldvlak van het vlak door L en het projectiecentrum van de tweede camera. Het is duidelijk dat de richting van de epipolaire rechte `2 in het beeldvlak bepaald wordt door de orientatie van de tweede camera t.o.v. de eerste. Dus, indien men op een of andere manier de epipolaire rechten in het tweede beeld zou kunnen berekenen, dan kan men daaruit misschien ook nuttige informatie over de relatieve orientatie van de camera's a eiden. Wij zullen hieronder nu aantonen dat men de epipolaire relaties tussen twee beelden van een stationaire scene kan berekenen uit de beelden zelf. Maar daarvoor moeten wij eerst de projectievergelijkingen voor de tweede camera opstellen. Neem als assenstelsel voor de scene het camera-gecentreerd assenstelsel van de eerste 5
P x1
P p
x2
1
p
2
y2
y1
Z
beeld 1
C2
C1 Y
beeld 2 l2
p
p
1
2
0
Figuur 4: Links:
C
O
X
Als de positie, ori entatie en cameraparameters van beide camera's ge-
P berekend worden uit de p2 in de beelden. Rechts: Het punt p2 in het tweede beeld dat overeenkomt met een punt p1 in het eerste beeld ligt op de epipolaire rechte ` die de projectie in het tweede beeld is van de projecterende rechte van p1 in de eerste
kend zijn, dan kunnen de 3D co ordinaten van het sc enepunt pixelco ordinaten van hun projecties
p1
en
camera.
camera en laat ons dit assenstelsel het \wereldassenstelsel " noemen. De positie van de tweede camera in de scene kan dan weergegeven worden door het stel coordinaten van het projectiecentrum C van de tweede camera t.o.v. het wereldassenstelsel en de orientatie van de tweede camera kan voorgesteld worden door drie eenheidsvectoren ~r1 , ~r2 en ~r3 , die de richting van respectievelijk de X-, de Y - en de Z-as van het camera-gecentreerd assenstelsel van de tweede camera t.o.v. het wereldassenstelsel aangeven (zie Figuur 5). De projectie p2 van het punt P in het tweede beeld wordt volgens formule (5) gegeven door 2 p2 = K2 co2 (P) met co2 (P) 2 IR3 het stel coordinaten van P t.o.v. het cameragecentreerd assenstelsel van de tweede camera. co2 (P) wordt gevonden door de vector ~ loodrecht te projecteren op elk van de coordinaatassen van het camera-gecentreerd CP assenstelsel van de tweede camera. Herinner u dat de abscis van de loodrechte projectie van een vector ~v 2 IR3 op de rechte met eenheidsrichtingsvector ~r gegeven wordt door het scalair product ~r ~v . Indien men de reele drietallen ~r en ~v als kolomvectoren noteert, dan komt het scalair product ~r ~v neer op het matrixproduct ~r ~v = ~rt~v. Toegepast op de bovenstaande situatie, impliceert dit dat het stel coordinaten co2 (P) van P t.o.v. het camera-gecentreerd assenstelsel van de tweede camera gelijk zijn aan 0 ~r1 (P co2 (P) = B @ ~r2 (P
1
0
1
0
1
C) ~r1t (P C) ~r1t C B C B t C) A = @ ~r2 (P C) A = @ ~r2t C A(P C) t t ~r3 (P C) ~r3 (P C) ~r3 6
=
~r1 ~r2 ~r3
t
(P
C ) = Rt ( P C )
met R = ( ~r1 ~r2 ~r3 ) de 3 3-matrix waarvan ~r1 , ~r2 en ~r3 de respectievelijke kolommen zijn. De projectievergelijkingen voor de tweede camera zijn dus 2 p2 = K2 Rt ( P
C) :
(6)
Met deze formule ter beschikking kan men nu de epipolaire relatie tussen twee beelden van eenzelfde scene a eiden. Beschouw dus een (willekeurig) punt p1 in het eerste beeld. p1 is dan de projectie van een punt P in de scene; en, volgens formule (5) moet 1 p1 = K1 P
voor een welbepaald (positief) reeel getal 1
(7)
en met K1 de calibratiematrix van de eerste camera. P hieruit oplossen, geeft P = 1 K1 1 p1 . Merk op dat deze laatste vergelijking een stel parametervergelijkingen voor de projecterende rechte L van p1 in de eerste camera geeft. Volgens formule (6) is de projectie van P in het tweede beeld bepaald door 2 p2 = K2 Rt ( P C ) = K2 Rt ( 1 K 1 p1 1
C)
= 1 K2 Rt K1 1 p1 + K2 Rt ( O
C) :
(8)
De laatste term in vergelijking (8) heeft precies dezelfde vorm als het rechterlid van de projectievergelijkingen (6) van de tweede camera en geeft bijgevolg de projectie e2 van de oorsprong O van het wereldassenstelsel in het tweede beeld: e e2 = K2 Rt ( O
C)
met e een (positief) reeel getal.
(9)
Maar het wereldassenstelsel is het camera-gecentreerd assenstelsel van de eerste camera. De oorsprong van dit assenstelsel is dus het projectiecentrum van de eerste camera, zodat e2 dus de projectie van de positie van de eerste camera in het tweede beeld is. Met andere woorden, e2 duidt de positie in het tweede beeld aan waar men de eerste camera in de scene ziet staan. Dit punt e2 noemt men de epipool van de eerste camera in het tweede beeld. Stel verder A = K2 Rt K1 1 . Dan is A een inverteerbare 33-matrix die de relatieve orientatie en de calibratiegegevens van de beide camera's bevat. Vergelijking (8) kan dan herschreven worden als 2 p2 = 1 A p1 + e e2 : (10) Deze laatste vergelijking drukt algebrasch uit dat p2 op de rechte door de epipool e2 en het punt Ap1 in het tweede beeld ligt (zie ook Figuur 5 (rechts)). Ap1 is het vluchtpunt in het tweede beeld van de projecterende rechte van p1 (en dus ook van P) voor de eerste camera. Herinner u dat de epipolaire rechte van p1 in het tweede beeld meetkundig gezien de snijlijn is van het tweede beeldvlak met het vlak door de projecterende rechte L van p1 en het projectiecentrum C van de tweede camera. Dit laatste vlak bevat echter ook de 7
P
p
u Z
r3
r1
v
r2
P
C Y 0
l2 Ap
p
1
1
e1
X Figuur 5: Links:
e2
p
2
C
O
De positie en de ori entatie van een tweede camera in de sc ene is volledig
C en een 3 3-rotatiematrix R t.o.v. het wereldassenstelsel. p2 van het scenepunt P in het tweede beeld ligt op de rechte `2 door de epipool e2 en het vluchtpunt A p1 van de projecterende rechte van p1 voor de eerste camera.
bepaald door een positievector
Rechts:
De projectie
rechte OC | die het tweede beeldvlak snijdt in de epipool e2 | en de rechte door C en p | die evenwijdig is met de projecterende rechte L van p1 . Vergelijking (10) zegt dus niets anders dan dat de epipolaire rechte `2 in het tweede beeld die correspondeert met het punt p1 in het eerste beeld precies de rechte door de epipool e2 en het vluchtpunt Ap1 van de projecterende rechte L van p1 is. Eigenschap 1 hieronder drukt dit verband eleganter uit.
De nitie 1. Zij I1 en I2 twee beelden van dezelfde scene.
p1 2 I1 en p2 2 I2 heten corresponderende punten van het beeldenpaar f I1 ; I2 g als en slechts als p1 en p2 de projecties zijn in respectievelijk I1 en I2 van e en en hetzelfde punt P in de sc ene. Twee punten
Eigenschap 1 (epipolaire relatie). Zij I1 en I2 twee beelden van dezelfde scene. elk paar corresponderende punten p1 2 I1 en p2 2 I2 geldt de volgende relatie: pt2 F p1 = 0 ;
waarbij
F = [e2 ] A
van het beeldenpaar
een re ele
f I1 ; I2 g
3 3-matrix
met rang 2 is die men de
Voor
(11) fundamentele matrix
noemt.
Bewijs. Herinner u dat p1 , p2 en e2 reele drietallen zijn die de pixelcoordinaten van de gelijknamige beeldpunten bevatten. Bijgevolg kunnen met p1 , p2 en e2 alle gekende 8
bewerkingen met reele drietallen uitgevoerd worden. Welnu, neem van beide leden van vergelijking (10) het vectorieel product met e2 . Daar e2 e2 = O, volgt dat 2 e2 p2 = 1 e2 A p1 :
Aangezien e2 p2 een vector in IR3 is die loodrecht staat op e2 en ook op p2 , moet het scalair product van deze vector met p2 gelijk aan 0 zijn. Van beide leden in de vorige vergelijking het scalair product met p2 nemen, geeft dus 1 pt ( e2 A p1 ) = 2 pt ( e2 p2 ) = 2 p2 ( e2 p2 ) = 0 ; 2
2
of, daar 1 > 0,
pt2 ( e2 A p1 ) = 0 :
Om de uitdrukking (11) van de eigenschap te verkrijgen, herschrijft men het linkerlid van de bovenstaande vergelijking op de volgende manier: e2 is van de vorm e2 = (xe ; ye; 1)t 2 IR3 . Veronderstel nu even dat A p1 = (a1 ; a2 ; a3 )t 2 IR3 . Dan is
e2 A p1
0 =B @
1
0
ye a3 1 a2 B xe a3 + 1 a1 C A=@ xe a2 yea1
waarbij [e2 ] de 3 3-matrix
0 [e2 ] = B @
0 1 ye 0 1 ye
1 0 xe 1 0 xe
10
1
ye a1 B C xe C A @ a2 A = [e2 ] Ap1 ; 0 a3 1
ye xe C A 0
2
is. Dit bewijs de eigenschap.
Gevolg 1. Zij I1
en
van dit beeldenpaar.
I2
twee beelden van dezelfde sc ene en zij
Voor elk punt
corresponderende beeldpunt
(a; b; c)t = F p1 .
Gevolg 2.
Zij
het beeldenpaar
I1 I2 f I1 ; I2 g en
p2
p1
van
I1
F
de fundamentele matrix
heeft de epipolaire rechte
bevat als vergelijking
ax +by +c = 0
`2
in
I2
p2 2 I2
2
twee beelden van dezelfde sc ene. De fundamentele matrix
F
van
kan op een constante factor na berekend worden uit de gegeven
beelden indien de pixelco ordinaten van ten minste 8 corresponderende puntenparen en
die het
, waarbij
p1 2 I1
gekend zijn.
Bewijs. Veronderstel dat p1 = (x1 ; y1 ; 1)t en dat p2 = (x2 ; y2 ; 1)t corresponderende punten van respectievelijk I1 en I2 zijn. Noteer verder de componenten van F met fij . Dan is p2 t F p1 = f11 x1 x2 + f12 y1 x2 + f13 x2 + f21 x1 y2 + f22 y1 y2 + f23 y2 + f31 x1 + f32 y1 + f33 :
Als dus p1 = (x1 ; y1; 1)t en p2 = (x2 ; y2; 1)t gekend zijn, dan geven de bovenstaande formule en vergelijking (11) samen een lineaire vergelijking in de componenten fij van de fundamentele matrix F . 8 paren van corresponderende punten p1 en p2 geven dus aanleiding tot 9
Figuur 6:
De computer zoek voor elk punt
p1 in het linkerbeeld een overeenkomstig punt p2
langsheen de overeenkomstige epipolaire rechte in het rechterbeeld door het grijswaardenpatroon in de omgeving van dat punt te vergelijken.
een homogeen stelsel van 8 lineaire vergelijkingen in de 9 onbekende componenten fij van F . Daar dit stelsel homogeen is, kunnen de fij slechts op een constante factor na bepaald worden uit de beelden alleen. 2 Dit laatste gevolg is een belangrijke stap voorwaarts naar onze doelstelling, namelijk een 3-dimensionale reconstructie van de scene berekenen op basis van (alleen maar) de gegeven beelden. Het gevolg geeft immers aan hoe je de fundamentele matrix van een beeldenpaar kan bepalen uit de beelden zelf. De 8 corresponderende puntenparen die hiervoor nodig zijn, kunnen automatisch door de computer gevonden worden met behulp van correspondentie-algoritmen of ze kunnen manueel ingegeven worden. Eens de fundamentele matrix F bepaald, geeft Gevolg 1 voor elk punt p1 in het ene beeld de vergelijking van de overeenkomstige epipolaire rechte in het andere beeld. De computer zoekt dan het corresponderende punt p2 door het punt q op deze epipolaire rechte te zoeken waarvoor het grijswaarden- (of kleur-)patroon in de omgeving van q de meeste gelijkenis vertoont met het grijswaarden- (of kleur-)patroon in de omgeving van p1 in het eerste beeld (cf. Figuur 6). Op die manier bepaalt de computer voor (bijna) alle punten p1 in het ene beeld het corresponderende punt p2 in het andere beeld. In de volgende paragraaf zullen wij onderzoeken hoe men uit die corresponderende puntenparen de coordinaten van het onderliggende scenepunt P kan berekenen. De fundamentele matrix F zal ook hier een cruciale rol spelen. Maar eerst willen wij nog even de kracht van de vorige gevolgen illustreren. Veronderstel dat je twee beelden I1 en I2 van dezelfde scene ter beschikking hebt. Je kan dan de vraag stellen wat die twee beelden je vertellen over een mogelijk derde beeld I3 . Welnu, veronderstel dat je de fundamentele matrices F13 en F23 van respectievelijk het eerste en het tweede naar het derde beeld kent (bv. omdat je minstens 8 correspondende punten met het 10
derde beeld kent). Beschouw nu twee corresponderende punten p1 2 I1 en p2 2 I2 in de eerste twee beelden. Het punt p3 in het derde beeld dat de projectie van het onderliggende scenepunt P in I3 is, moet enerzijds op de epipolaire rechte `1 van p1 in I3 liggen en anderzijds ook op de epipolaire rechte `2 van p2 in I3 . Met andere woorden, p3 is het snijpunt van de epipolaire rechten `1 en `2 in het derde beeld. Indien de pixelcoordinaten van p1 en p2 en de fundamentele matrices F13 en F23 gekend zijn, dan zegt Gevolg 1 dat de coeÆcienten in de vergelijking van `1 gegeven worden door F13 p1 en die van `2 door F23 p1 . Dus, als F13 en F23 gekend zijn, dan kan men voor elk paar corresponderende punten p1 2 I1 en p2 2 I2 de vergelijking van hun epipolaire rechten in het derde beeld berekenen; en, het snijpunt van die twee rechten is dan het overeenkomstige punt p3 in I3 . In formules geeft dit de volgende eigenschap.
Eigenschap 2. matrices
F13
en
Zij
F23
I1 I 2 ,
p3
in
I3
I3
drie beelden van dezelfde sc ene.
van respectievelijk
corresponderende punten stige punt
en
I1
en
I2
met
I3
Als de fundamentele
gekend zijn, dan kan voor elk paar
p1 2 I1 en p2 2 I2 het stel pixelcoordinaten van het overeenkom-
berekend worden met de formule:
p3 = F13 p1 F23 p2 waarbij
2 IR
een evenredigheidsfactor is die door de vergelijking zelf bepaald wordt.
Bewijs. Wegens Gevolg 1 is de vergelijking van de epipolaire rechte `1 van p1 in I3 gegeven door a1 x + b1 y + c1 = 0 met (a1 ; b1 ; c1 )t = F13 p1 . En, wegens hetzelfde gevolg, is de vergelijking van de epipolaire rechte `2 van p2 in I3 gegeven door a2 x + b2 y + c2 = 0 met (a2 ; b2 ; c2 )t = F23 p2 . Het stel coordinaten (x; y; 1)t 2 IR3 van het snijpunt p3 van `1 en `2 is dan een oplossing van het stelsel (
a1 x + b1 y + c1 = 0 a2 x + b2 y + c2 = 0
De eerste vergelijking kan in matrixvorm geschreven worden als 0 = a1 x + b1 y + c1 =
a1 b1
0 1 B x C c1 @ y A = at1 p3 = a1 p3 ;
1
waarbij a1 = (a1 ; b1 ; c1 )t 2 IR3 is. De tweede vergelijking kan op dezelfde manier geschreven worden als a2 p3 = 0 met a2 = (a2 ; b2 ; c2 )t 2 IR3 . Maar dit betekent dat de kolomvector p3 loodrecht staat op zowel het reele drietal a1 als a2 . Bijgevolg moet p3 een scalair veelvoud zijn van het vectorieel product a1 a2 = F13 p1 F23 p2 , namelijk p3 = F13 p1 F23 p2 voor een bepaalde 2 IR. Daar de derde coordinaat van p3 gelijk is aan 1, is de evenredigheidsfactor gelijk aan de derde coordinaat van het drietal F13 p1 F23 p2 . Dit bewijst de eigenschap. 2 11
Figuur 7:
Twee originele digitale beelden van een buste en vier kunstmatig gegenereerde
beelden m.b.v. Eigenschap 2.
Eigenschap 2 beweert dus dat, wanneer de fundamentele matrices F13 en F23 gekend zijn (bv. door de positie van 8 punten in het derde beeld aan te duiden), dat men dan het derde beeld I3 volledig kan reconstrueren uit de twee gegeven beelden I1 en I2 van de scene. Figuur 7 bewijst deze bewering: Op de bovenste rij staan twee echte beelden van een buste. De onderste rij toont zes andere, kunstmatige beelden die op basis van de twee echte beelden door de computer berekend werden. Uiteraard kan de computer alleen maar de projectie in het derde beeld bepalen van scenepunten die in de twee gegeven beelden zichtbaar zijn. Dit verklaart waarom de linker helft van de buste niet volledig gereconstrueerd werd. Bemerk dat de kunstmatig gegenereerde beelden zeer realistisch zijn zolang men niet meer dan 30Æ van de oorspronkelijke kijkrichting van de twee gegeven beelden afwijkt. Deze kennis opent heel wat nieuwe mogelijkheden voor eÆciente beeldcompressie voor stockage en transmissie van beeldmateriaal bij internettoepassingen en videofonie: Twee beelden en de pixelco ordinaten van 8 beeldpunten volstaan om een nieuw zicht vanuit een willekeurige kijkrichting van de sc ene te genereren
!
4. 3-Dimensionale reconstructie uit meerdere beelden. De conclusie van de vorige paragraaf bevestigt het vermoeden dat de 3-dimensionale vorm van een scene impliciet vervat zit in twee beelden van die scene en de bijbehorende fundamentele matrix. Laten wij nu onderzoeken hoe deze 3-dimensionale informatie expliciet gemaakt kan worden. Wiskundig gezien, vertaalt het 3D-reconstructieprobleem zich als volgt: Gegeven twee
I1 I2 p2 2 I2
beelden en
en
van eenzelfde sc ene. Bepaal voor elk paar corresponderende punten
het stel co ordinaten van het punt
p1 2 I1
P in de scene waarvan p1 en p2 de projecties
. In de vorige paragraaf werd het wiskundig verband tussen het stel coordinaten van het scenepunt P en de pixelcoordinaten van de beeldpunten p1 en p2 afgeleid. Volgens vergelijking (7) is
in de respectievelijke beelden zijn
P = 1 K1 1 p1 12
met 1 een (welbepaald, maar onbekend) positief reeel getal en met K1 de calibratiematrix van de eerste camera. Het reconstructieprobleem zal dus opgelost zijn, indien men 1 en K1 kan bepalen. De matrix K1 bevat uitsluitend technische gegevens betre ende de eerste camera (cf. x 2) en heeft niets te maken met de 3-dimensionale vorm van de scene. Laat ons daarom even veronderstellen dat de calibratiematrix K1 gekend is (bv. omdat men de calibratiegegevens van de camera overgenomen heeft uit de technische che van de camera). Op het einde van deze paragraaf zullen wij zien dat K1 ook uit de beeldinformatie kan afgeleid worden. Als K1 gekend is, dan maakt het niets uit of men nu rechtstreeks P ^ = K1 P bepaalt en vervolgens hieruit P oplost met P = berekent dan wel of men eerst P 1^ K1 P. De laatste optie is wiskundig echter eleganter, omdat de projectievergelijkingen (7) van de eerste camera zich vertalen in ^ = K1 P = 1 p1 : P ^ van het scenepunt P kan direct berekend worden Met andere woorden, de reconstructie P uit de pixelcoordinaten van het beeldpunt p1 op voorwaarde dat men ook nog het reeel getal 1 kan bepalen. Welnu, de a eiding van de epipolaire relatie tussen de beelden I1 en I2 in x 3 is gebaseerd op vergelijking (10), namelijk 2 p2 = 1 A p1 + e e2 ;
(12)
waarbij 1 , 2 en e de (onbekende) evenredigheidsfactoren voor de beeldpunten p1 en p2 en de epipool e2 zijn en waarbij e2 en A volgens Eigenschap 1 de fundamentele matrix F de nieren. 1 kan uit deze vergelijking opgelost worden, zoals aangegeven in de volgende eigenschap.
Eigenschap 3. Eigenschap 1.
Zij
I1
en
I2
Dan wordt voor elk paar corresponderende punten
3-dimensionale reconstructie
^ = 1 p1 P
twee beelden van dezelfde sc ene; en, zij
^ = K1 P P
waarbij
1 = e met
e
p1
A
2 I1
van het onderliggende sc enepunt
en en
P
( p2 A p1 ) ( e2 p2 ) ( p2 A p1 ) ( p2 A p1 )
e2 p2
zoals in
2 I2
de
bepaald door
(13)
een positieve constante.
Bewijs. Neem van de beide leden van vergelijking (12) het vectorieel product met p2 . Daar p2 p2 = O, volgt dat O = 1 p2 A p1 + e p2 e2 : Gebruik makend van het feit dat p2 e2 = e2 p2 kan deze laatste vergelijking herschreven worden als 1 p2 A p1 = e e2 p2 : Van beide leden van deze vergelijking het scalair product met p2 A p1 nemen, geeft dan 1 ( p2 A p1 ) ( p2 A p1 ) = e ( p2 A p1 ) ( e2 p2 ) : 13
2
Dit bewijst formule (13).
^ van het scenepunt P kan nu met behulp van Eigenschap 3 berekend De reconstructie P worden uit de projecties p1 en p2 van P in de beelden I1 en I2 . Om formule (13) te kunnen gebruiken, moet men echter het reeel getal e , de epipool e2 en de 3 3-matrix A kennen. Het reeel getal e is geassocieerd met de epipole e2 in het tweede beeld (cf. vergelijking (9)) en is dus volledig onafhankelijk van de beeldpunten p1 en p2 en het scenepunt P. e kan dus beschouwd worden als een (positieve) constante in het 3-dimensionale model van de scene. Een andere waarde kiezen voor e impliceert dat het 3-dimensionaal model van de scene met een welbepaalde factor vergroot of verkleint. e bepaalt dus de schaal van de reconstructie. Vermits e niet uit de beeldinformatie alleen kan afgeleid worden, kan men ook de absolute schaal van de sc ene niet bepalen aan de hand van de beelden alleen. Dit is intutief duidelijk, want indien men de scene 2 keer zo groot zou maken, en tegelijkertijd ook de camera's 2 keer zo ver uit elkaar en 2 keer zo ver verwijderd van de scene zou opstellen, dan zou men toch identiek dezelfde beelden van de scene verkrijgen als voordien. Deze vaststelling wordt regelmatig gebruikt voor visuele e ecten en truckages in de lmindustrie. De andere, niet-beeld-componenten in formule (13) zijn de epipool e2 en de 3 3matrix A. Maar dit zijn net ook de componenten waaruit, volgens Eigenschap 1, de fundamentele matrix F van het beeldenpaar f I1 ; I2 g opgebouwd is. F kan volgens Gevolg 2 rechtstreeks uit de beelden berekend worden. Indien men dus F op een unieke manier zou kunnen ontbinden in F = [ e2 ] A, dan zou het reconstructieprobleem opgelost zijn. De volgende eigenschap leert echter dat dit niet zo eenvoudig is.
Eigenschap 4.
Zij
I1
en
matrix van het beeldenpaar
(a)
I2 f I1 ; I2 g
twee beelden van dezelfde sc ene; en, zij
de fundamentele
.
De (pixelco ordinaten van de) epipool de
F
e2
in het tweede beeld
I2
worden gevonden als
unieke oplossing van het homogeen stelsel F t e2 = O, met laatste coordinaat gelijk
aan 1.
(b)
De inverteerbare
3 3-matrix A
vorm
met
a 2 IR3
uit Eigenschap 1, waarvoor
A = [ e2 ] F + e2 at ;
F = [ e2 ] A
is van de
(14)
een re eel drietal.
Bewijs. (a) Schrijf e2 als e2 = (xe ; ye; 1)t 2 IR3 . Herinner u uit het bewijs van Eigenschap 1 dat 0 [ e2 ] = B @
1
0 1 ye 1 0 xe C A : ye xe 0 Het is nu eenvoudig na te rekenen dat et2 [ e2 ] = Ot . Bewering (a) volgt dus uit het feit dat F = [ e2 ] A. 14
(b) Het is eenvoudig na te rekenen dat A~ = [ e2 ] F een 33-matrix is waarvoor [ e2 ] A~ = F . Bewering (b) volgt nu onmiddellijk uit de volgende observatie: [ e2 ] A1 = [ e2 ] A2
als en slechts als
A1 = A2 + e2 at voor een zekere a 2 IR3 ,
wat men als volgt bewijst: [ e2 ] A1 = [ e2 ] A2 als en slechts als [ e2 ] ( A1 A2 ) = O3 . Noteer de jde kolom van A1 A2 met kj . De jde kolom van het matrixproduct [ e2 ] ( A1 A2 ) is dan gelijk aan [ e2 ] kj = e2 kj , per de nitie van [ e2 ] . Daar [ e2 ] ( A1 A2 ) = O3 , volgt dat e2 kj = O voor elke j. Maar dan moet kj een scalair veelvoud van e2 zijn; d.w.z. kj = aj e2 voor een zekere aj 2 IR. Bijgevolg is A1
h
i
h
i
h
A2 = k1 k2 k3 = a1 e2 a2 e2 a3 e2 = e2 a1 a2 a3
voor een zekere a = (a1 ; a2 ; a3 )t 2 IR3 .
i
= e2 at
2
Eigenschap 4 toont aan dat de matrix A die nodig is voor de berekening van de 3dimensionale reconstructie van de scene, slechts op 3 onbekende parameters na uit twee beelden van de scene bepaald kan worden. Met andere woorden, iedere keuze van a 2 IR3 die de 3 3-matrix [ e2 ] F + e2 at inverteerbaar maakt, is een mogelijke kandidaat voor de matrix A en geeft aanleiding tot een (verschillende) 3-dimensionale reconstructie van de scene via Eigenschap 3. Al deze reconstructies verschillen van elkaar en van de scene door een projectieve transformatie. Ruwweg gezegd, betekent dit dat in een dergelijke reconstructie alleen maar de meetkundige beperkingen van collineariteit en van coplanariteit van punten in de scene bewaard gebleven zijn, maar dat alle andere meetkundige eigenschappen van de scene zoals evenwijdigheid en de onderlinge verhoudingen van lengten en hoeken volledig verloren gegaan zijn. Anders gezegd, punten die in de scene op een bepaalde rechte liggen, zullen ook in elke reconstructie van de scene op de reconstructie van die bepaalde rechte liggen, en alle punten die in de scene in een bepaald vlak liggen zullen ook in elke reconstructie van de scene in de reconstructie van dat vlak liggen, maar alle andere meetkundige relaties tussen de punten in de scene gelden niet noodzakelijk meer in de reconstructie. Om een \nauwkeuriger" reconstructie van de scene te verkrijgen, zal men dus bijkomende eisen moeten opleggen. Welnu, in de praktijk worden de beelden van de scene meestal opgenomen met dezelfde camera. Het is dus niet onrealistisch om te veronderstellen dat de interne cameraparameters tussen de opnamen door niet gewijzigd zijn; of, met andere woorden, dat K1 = K2 . Noteer deze gemeenschappelijke cameramatrix met K. Herinner u uit x 3 dat A = K2 Rt K1 1 met R de 33-rotatiematrix die de relatieve orientatie van de tweede camera t.o.v. de eerste weergeeft. Wanneer K1 = K2 = K, dan is A = K Rt K 1 of, anders gezegd, de matrix A is gelijkvormig met een rotatiematrix. De voorwaarde dat de beelden opgenomen moeten zijn met dezelfde camera (of met twee identieke camera's) levert dus een bijkomende eis op voor de matrix A. Deze eis is echter niet voldoende om A eenduidig te bepalen. Maar met behulp van meer gevorderde technieken uit de lineaire 15
(a) Figuur 8:
(b)
Een kubus in de sc ene
als een willekeurig zesvlak een kubus
(d),
(b).
(c) (a)
(d)
kan uit twee beelden slechts gereconstrueerd worden
Uit drie beelden opgenomen met dezelfde camera vindt men
maar de zijde van de sc enekubus kan niet uit de beeldinformatie bepaald
worden. De intermediaire reconstrucie
^ levert echter een parallellepipedum (c) op. P
algebra en de algebrasche meetkunde is het niet zo moeilijk om aan te tonen dat het componenten a1 , a2 en a3 van het drietal a = ( a1 ; a2 ; a3 ) 2 IR3 waarvoor [ e2 ] F + e2 at = A aan een veeltermvergelijking van de 4de graad voldoen. Wanneer er dus drie beelden I1 , I2 en I3 van de scene beschikbaar zijn, die allen opgenomen werden met dezelfde camera, dan geeft elke beeldenpaar f I1 ; I2 g, f I1 ; I3 g en f I2 ; I3 g aanleiding tot een (andere) 4 de-graadsvergelijking in a1 , a2 en a3 . Deze drie veeltermvergelijkingen hebben slechts een eindig aantal gemeenschappelijke oplossingen. Elke oplossing a = ( a1 ; a2 ; a3 ) geeft dan met behulp van Eigenschappen 3 en 4 aanleiding tot een 3-dimensionale reconstructie van de scene. Een eenvoudige visuele inspectie van de verkregen modellen volstaat nu om de correcte reconstructie van de scene te identi ceren. Meer nog, wanneer er meer dan drie beelden van de scene, opgenomen met dezelfde camera, beschikbaar zijn, dan is het reele drietal a uniek bepaald door de 4de-graadsvergelijkingen verkregen uit alle beeldenparen, zodat de correcte reconstructie van de scene onmiddellijk wordt gevonden. Het feit dat K een bovendriehoeksmatrix is, maakt het bovendien ook mogelijk om, met behulp van gevorderde technieken uit de lineaire algebra, de calibratiematrix K te berekenen uit de relatie A = K Rt K 1 . Samen geeft dit de volgende stelling.
Stelling 1.
De ruimtelijke struktuur van de sc ene kan (op een gelijkvormigheid na) ge-
reconstrueerd worden uit puntcorrespondenties tussen (minstens) 3 beelden van de sc ene die opgenomen werden met een camera waarvan de interne cameraparameters tussen de opnamen door ongewijzigd gebleven zijn.
5 Enkele praktische toepassingen. De mogelijkheid om automatisch nauwkeurige 3-dimensionale computermodellen van bestaande voorwerpen en omgevingen te genereren uit een aantal beelden ervan, zoals in de vorige paragrafen werd beschreven, opent nieuwe perspectieven in verschillende toepassingsgebieden. In deze paragraaf bespreken wij enkele beloftevolle nieuwe toepassingen die 16
recent aan het Centrum voor Beeld- en Spraakverwerking van de Leuven met deze technologie ontwikkeld werden.
Katholieke Universiteit
5.1. Computermodellen van historische en archeologische sites voor archivering en conservatie.
Figuur 9: Boven:
Enkele foto's van een Ja n-tempel te Ranakpur (India).
Onder:
De
3-dimensionale reconstructie (links) en enkele details van het model.
Wegens het destructieve karakter van archeologische opgravingen en van restauratieprocedures bij de conservering van historische monumenten, is het uitermate belangrijk voor latere studies om zeer nauwkeurige rapporten van elk stadium van het opgravings- of conservatieproces te hebben. Immers, om het leven op een historische site in een bepaalde tijd te kunnen reconstrueren, moet men niet alleen zeer zorgvuldig de gevonden artefacten bestuderen, maar heel wat belangrijke informatie valt ook af te leiden uit de precieze plaats en de volgorde waarin deze voorwerpen op de site gevonden werden. Daarom worden de exacte vindplaatsen en de preciese afmetingen van de blootgelegde structuren nauwkeurig opgemeten en gedocumenteerd met fotogra sch materiaal en met topogra sche kaarten. Dit is echter een arbeidsintensieve en tijdrovende aangelegenheid. Daarom is men recent met experimenten gestart om het nut van 3-dimensionale site-modellen en computermodellen van artefacten, gegenereerd uit foto's en video-opnamen met de hierboven beschreven 17
Figuur 10:
E en beeld uit een stereopaar van twee frontale foto's van een persoon, opgenomen
met een translerende camera, en twee aanzichten van het gereconstrueerde gezichtsmodel.
methode, voor dergelijke doeleinden te evalueren. Figuur 9 toont bovenaan drie foto's van de historische Jan-tempel van Ranakpur (India), die opgenomen werden met een pocketcamera. Onderaan in dezelfde guur wordt links de berekende 3-dimensionale reconstructie en vervolgens enkele detail-beelden van het model vanuit een kijkrichting die volledig verschilt van de originele opnamen.
5.2. Gezichtsmodellen voor lmanimatie en forensische toepassingen. Een van de grootste uitdagingen in lmanimatie en speciale e ecten bestaat in het modelleren van het menselijk gelaat. Daar men personen het gemakkelijkst herkent aan hun gelaat, zal een menselijke waarnemer onmiddellijk de tekortkomingen aan een kunstmatig gezichtsmodel opmerken. De hierboven uitgelegde methode voorziet in een eenvoudige oplossing om 3-dimensionale snapshots van bestaande personen in een virtuele omgeving te genereren en de discrepanties tussen het computermodel en de realiteit zo klein mogelijk te houden. In de gecontroleerde omstandigheden van een lmstudio kan de procedure zelfs nog vereenvoudigd worden door de camerabeweging te controleren. Inderdaad, als de camera een eenvoudige verschuiving ondergaat tussen de twee opnamen door (of wanneer men een stereo-opstelling gebruikt), dan is de rotatiematrix R in formule (6) gelijk aan de eenheidsmatrix I3 en wordt A = K R K 1 = I3 . De expliciete kennis van de matrix A in dit geval laat toe om, met behulp van Eigenschap 3, rechtstreeks een 3-dimensionale reconstructie te berekenen uit slechts twee beelden. Figuur 10 (links) toont een beeld van een stereopaar bestaande uit twee frontale foto's van een persoon, opgenomen met een translerende camera. Dezelfde guur (midden en rechts) toont ook twee aanzichten van het 3-dimensionaal gezichtsmodel dat uit deze foto's berekend werd. Recentelijk werden er door internationale politiediensten een reeks experimenten opgezet om het mogelijk nut van dergelijke 3-dimensionale gezichtsmodellen bij het herkennen van misdadigers door slachto ers en getuigen te ondersteunen en te vergemakkelijken. Dergelijke modellen geven veel 18
c Eyetronics n.v.
Figuur 11: Boven: Enkele frames uit een videosequentie van een persoon die grimassen maakt. Onder: Een geanimeerde dynamische 3D reconstructie van de videosequentie. meer exibiliteit in kijkrichting dan de traditionele voor- en zij-aanzichten van criminelen in de huidige politiebestanden. Maar wanneer men toch onder gecontroleerde omstandigheden werkt, dan kan men nog een stapje verder gaan en een 3-dimensionaal model genereren uit slechts een foto. De onderliggende gedachte is de volgende: vervang de eerste camera door een diaprojector die een jn rasterpatroon projecteert op het voorwerp dat je wil reconstrueren; en, neem een foto van het voorwerp met het geprojecteerde patroon. De dia in de projector enerzijds en de foto van het voorwerp met het geprojecteerde patroon anderzijds vormen samen een beeldenpaar waaruit een 3-dimensionale reconstructie van het op het voorwerp geprojecteerde patroon kan berekend worden Dit 3-dimensionaal grid is een goede benadering van het oppervlak van het voorwerp. Door de textuur van het voorwerp tussen de rasterlijnen uit de foto te lteren en te projecteren op het model, verkrijgt men een zeer realistische reconstructie van het voorwerp in kwestie. Meer nog, daar men op die manier een 3-dimensionaal model van een voorwerp kan genereren uit slechts een beeld (met het geprojecteerde rasterpatroon), kan met een 3-dimensionale \video" maken. Inderdaad, door elk frame van een videosequentie in 3D te reconstrueren, en deze reconstructies snel na elkaar te tonen vanuit de kijkrichting aangeduid door de toeschouwer, verkrijgt men een dynamische 3-dimensionale reconstructie van de videosequentie. Dergelijke dynamische, 3-dimensionale reconstructies kunnen dan verder geanimeerd worden om allerlei visuele effecten te genereren. Figuur 11 toont bovenaan enkele frames uit een videosequentie van een persoon die een grimas trekt (met het raster op zijn gelaat geprojecteerd). Onderaan in dezelfde guur worden er enkele frames uit een geanimeerde dynamische 3D reconstructie van die opname getoond. Deze techniek wordt onder patent geexploiteerd door Eyetronics n.v.. 19
