Combinatie DCT en Monte Carlo

Een tweede mogelijkheid (naast subpixelsampling en het verschoven grid) om ervoor te zorgen dat minder artefacten gemist worden bij het DCT algoritme bestaat erin om in verschillende fases te werken:

1. Eerst wordt voor elke pixel een aantal samples genomen
2. Daarna wordt adhv de DCT per blokje van 8x8 beslist of er meer samples genomen
3. Neem opnieuw voor elke pixel een aantal samples
enz...

De resultaten van deze methode:

Oplossing geen convergentie naar referentieprentje

De presentatie die ik gegeven heb tijdens de Paasvakantie met de resultaten tot dan is hier te vinden. Het probleem was dat de methode die gebruik maakt van de DCT, randeffecten mistte. Een illustratie van die randgevallen is hier te vinden.
Er zijn twee mogelijke oplossingen voor dat probleem.
* Enerzijds is het mogelijk om het beeld op te delen ipv op pixel niveau in subpixel niveau. Dat heeft als voordeel dat een blokje van 8x8 dan niet overeenkomt met 8x8 pixels maar op een kleiner stuk van het beeld. Zo kan het aantal pixels dat volledig gemist wordt drastisch verkleind worden. Het probleem van het missen van de artefacten blijft natuurlijk bestaan. De verwachting is dus dat er nog steeds geen convergentie zal zijn naar het referentie beeldje maar dat er toch uiteindelijk een kleinere fout behaald wordt.
* Een betere oplossing bestaat erin om met twee grids te werken: één op het gewone niveau en één grid 4 pixels verschoven in de diagonale richting. Zo is het niet meer mogelijk dat een artefact een randgeval is elk blokje.
De resultaten van de theepot met puntlichtbron zijn weergegeven in onderstaande grafiek:



We zien dat zoals verwacht beide methodes een beter resultaat geven. De methode van de subpixel bemonstering volgt in eerste instantie het traject van standaard monte carlo. Dit is omdat in elk subpixel segment monsters moeten genomen alvorens een schatting van de DCT kan worden berekend. Het samplen van elk subpixelsegment is net wat gestratifieerde bemonstering doet dus is het normaal dat die twee grafieken bij elkaar aansluiten.

Resultaten

Na een lange periode van stilzwijgen zal ik de resultaten bekendmaken van mijn Raytracer gebaseerd op de DCT.
Om de voortgang en de verbetering van het algoritme in beeld te brengen heb ik voor een aantal stappen de vergelijking gemaakt met een referentieprentje (200 stralen per pixel)


Referentieprentje
200 stralen per pixel

Wanneer we nu 1M samples nemen (het equivalent van 4 samples per pixel op een 512*512 prentje) dan krijgen we:



We kunnen nu eenvoudig het verschil berekenen met het referentieprentje:


Wanneer we nu hetzelfde doen voor verschillend aantal stralen en we berekenen het gemiddelde verschil dan krijgen we volgende grafiek:



Wanneer we nu hetzelfde doen voor standaard monte carlo raytracing. Dan zien we dat de fout bij standaard monte carlo, linear afneemt en dat we met behulp van de DCT analyse ervoor kunnen zorgen dat het verschil sneller afneemt omdat we uiteraard concentreren op de plaatsen waar de grootste verschillen optreden.

Een klein eureka moment...

Ik ben verheugd u te verkondigen dat mijn algoritme zich voor het eerst gedraagt zoals ik verwacht dat zich gedraagt :-).
Aanvankelijk dacht ik dat het probleem zich wel zou bevinden bij het omzetten naar het frequentie domein. Dat heb ik dan ook volledig nagegaan en elke stap van het algoritme in debugmode bekeken. Nu de stap die ik telkens oversloeg was het berekenen van het verschil met de vorige waarden. Nu daar zat nu net het probleem. Omdat ik initieel alle frequentietermen op 0.0 zette werd in de eerste adaptieve stap de nieuwe waarden met 0.0 vergeleken. Daar zit nu net het probleem want stel dat we een volledig wit (1,1,1) blokje hebben dan is de DCT daarvan een 8 in de linkerbovenhoek en 0 elders. Nu omdat 8-0 hoogstwaarschijnlijk het grootste verschil zal zijn, wordt dit blokje als eerste gekozen, terwijl het volledig effen is.

Hieronder de resultaten. Bovenaan zien we het beeld dat pbrt geeft met 1,4M stralen, daaronder staat het beeldje dat mijn algoritme geeft. Bij de buddha zien we dat de ruis op de sokkel en de buddha zelf gevoelig lager ligt dan bij de standaard ray-tracer. Nogmaals daaronder staat de verdeling van het aantal stralen. We zien duidelijk dat het algoritme nu correct de plaatsen met meer ruis detecteert en bijgevolg daar meer stralen schiet.
Bij de glazen bol zien we dat de caustic en de zachte rand meer samples krijgen (zoals te verwachten valt).

Het is al weer een tijd geleden dat ik hier nog eens gepost heb.
Het heeft nogal wat voeten in de aarde gehad maar ik heb nu een correct werkende basis implementatie.

Eerst nog even kort herhalen wat het algoritme juist doet:

• In een eerste stap wordt het beeld opgedeeld in vakjes van 8x8 pixels. Naar analogie met jpeg-algoritmes.


• Vervolgens wordt een eerste bemonstering genomen van het beeldje. (In mijn geval neem ik 128 (8x8x2) samples. Dit komt overeen met 2 samples per pixel. Dit doe ik om toch zeker elke pixel van het beeldje minstens 2 samples te hebben).


• In de derde stap wordt voor elk blokje de DCT (Discrete Cosinus Transformatie toegepast). De waarde (=het verschil met de vorige benadering) wordt op maximum gezet omdat we nog geen vorige benadering hebben. (dus eigenlijk komt elk blokje nog minstens 1x aan de beurt in het iteratieve stadium).


• Vanaf hier begint het iteratieve proces:


• Het blokje met de grootste waarde wordt genomen.


• Neem X samples op dat blokje.


• Bereken de DCT op de nieuwe pixelwaarden.


• Bereken het verschil met de vorige benadering. Als er een groot verschil is, is dit een indicatie dat pixelwaarden veel gewijzigd zijn, dus dat er waarschijnlijk nog meer samples nodig zijn. Daarom krijgt het blokje in dat geval een grote waarde. In het andere geval wanneer de cosinustermen weinig van elkaar verschillen krijgt het blokje een kleine waarde.




• Het iteratieve proces stopt wanneer de maximale waarde over alle blokjes kleiner is dan een bepaalde stopconditie of wanneer een vooraf bepaald aantal stralen verdeeld zijn.

Het algoritme zoals het nu geïmplementeerd is verschilt in een aantal opzichten van wat Bolin & Meyer doen:

• Het grootste verschil is dat mijn implementatie los staat van elke mogelijke sampler. Dat betekend dat mijn algoritme ook perfect werkt bij random sampling e.a. Bij Bolin & Meyer wordt strak vastgehouden aan vast sample patroon per blokje. Dat heeft op zich dezelfde nadelen als een vast samplepatroon per pixel. Hun samplepatroon neemt tevens veel samples op de rand van het blokje zodat eigenlijk veel samples meermaals worden genomen in naburige blokjes. Zij hebben die keuze gemaakt omdat ze dan voor elk blokje dezelfde transformatiematrix kunnen gebruiken.


• Verder wordt bij Bolin & Meyer voor elk blokje alle samples expliciet bijgehouden. Dat zorgt bij een groot aantal stralen al snel tot een paar Mb aan geheugen. De samples worden bijgouden omdat bij het berekenen van de DCT transformatie een least square fit wordt toegepast op alle samples van het blokje en die moet dus ook telkens opnieuw berekend worden. Ik daarentegen neem de cosinustransformatie van de pixelwaarden. Dat heeft als voordeel dat de samples niet meer hoeven bijgehouden te worden en dat er geen matrices hoeven bijgehouden te worden. Het nadeel is dat samples niet exact worden gebruikt omdat ze reeds samengevoegd zijn in een pixel.

Een aantal resultaten: (Boven zien we telkens het prentje en onder de verdeling van het aantal samples)

Bij een diffuus beeldje en een puntlichtbron krijgen we een goed resultaat:

Vorderingen implementatie

Na de presentatie van vorige week (de slides zijn hier te vinden) ben ik verder gegaan met de implementatie van mijn ray tracer.
Ik heb nog verschillende problemen met de representatie in het frequentie domein. Het beeld wordt opgedeeld in blokken van 8x8 pixels en wordt voorgesteld in het frequentie domein adhv 64 cosinus termen. Wanneer er te weinig samples in een blok genomen worden draait het algoritme in de soep wanneer de cosinus termen geëvalueerd worden. In de paper wordt voorgesteld om het aantal cosinus termen te verhogen telkens er 2 à 3 samples bijkomen. Ik heb die extra moeilijkheid omzeild door geen omzetting te doen naar het frequentie domein voordat ik 128 samples heb genomen per 8x8 blok. Wat betekent dat er genoeg informatie is om het blokje adhv 64 cosinus termen voor te stellen. Dit komt overeen met 2 samples per pixel en heeft als voordeel dat er geen blokken zullen zijn die te weinig samples krijgen.
Doordat ik een vast sample patroon per blok gebruik kan ik de matrices die nodig zijn om de transformatie naar het frequentie domein uit te voeren, voor elk blok hergebruiken. Voorlopig bereken ik 1000 matrices in een pre-processing stap. Dit heeft als nadeel dat er maximaal 1128 samples per 8x8 pixels kunnen genomen worden maar wat een groter nadeel is het geheugen gebruik: 1000*64*64 = 4 096 000 doubles die in het geheugen moeten worden opgeslagen enkel voor de transformatie naar frequentiedomein.

Waarom adaptieve raytracing?

Klassieke raytracing, zoals het typisch in een cursus Computer Graphics wordt aangeleerd:


Gebruiker Hendrik van Wikipedia.

Een straal vertrekt van de Camera en gaat door een pixel van het beeld (Image) tot het op een object terecht komt. Vanaf dat punt worden dan één of meerdere schaduw stralen (shadow ray) geschoten naar de lichtbron(nen).


Het probleem met dergelijke techniek is dat we veel stralen per pixel moeten gaan schieten om ruis en aliasing problemen te verwijderen.


De beeldjes zijn gegenereerd met pbrt:
Beeldje 1: 1 straal per pixel: 7,8 Seconden, 131.000 stralen.
Beeldje 2: 4 stralen per pixel: 32 Seconden, 532.000 stralen.
Referentie: 128 stralen per pixel: 1003 Seconden, 17.000.000 stralen


We willen het aantal stralen zo laag mogelijk houden. Op positie 1 zien dat we al een goede benadering hebben voor de eigenlijke kleur. Hier meer stralen naar schieten heeft niet veel zin omdat extra stralen weinig bijdragen tot een verbetering van het kleur op die pixel. Op positie 2 daarentegen is duidelijk nog heel veel ruis te zien. Adaptief bemonsteren bestaat er nu in posities zoals 2 te detecteren en daar meer samples te nemen.