Wat zijn fractals en hoe zien we ze terug in de IT?
Ooit leken fractals niet meer dan een wiskundige curiositeit met een hoog esthetisch gehalte. Maar door de jaren werden er vele praktische toepassingen gevonden en tegenwoordig kan ook de IT niet meer zonder. Aan de hand van Visions of Chaos nemen we een kijkje in de wondere wereld van fractals en aanverwante zaken, want wat zijn fractals eigenlijk?
In 1904 bedacht de Zweedse wiskundige Helge von Koch een uiterst eenvoudige procedure die als volgt gaat: neem een gelijkzijdige driehoek en gum van elke zijde het middelste derde deel uit. Teken nu boven elk uitgegumd deel twee zijden van een nieuwe gelijkzijdige driehoek. Herhaal deze procedure op alle lijnen die je nu hebt en doe dat steeds opnieuw. Het resultaat is de Koch-sneeuwvlok: een figuur met een eindig oppervlak, maar een oneindige omtrek.
Je kunt de procedure overigens ook loslaten op een enkele lijn en ook daarvan wordt de lengte uiteindelijk oneindig lang. In dat geval spreken we van de Koch-kromme. Hoewel het woord nog niet bestond, was dit een van de eerste fractals.
Een Koch-kromme kun je beschrijven met een wiskundige procedure die L-systeem wordt genoemd (de letter L verwijst naar bedenker Aristid Lindenmayer, een theoretisch bioloog). Een handvol simpele regels vormt hierin het recept om objecten te maken waarvan het uiterlijk verbluffend gevarieerd is en die we dan ook nog vaker zullen tegenkomen. Sommige van deze vormen lenen zich uitstekend voor het maken van de zeer compacte antennes die nodig zijn in mobieltjes en die in staat zijn om met meerdere frequentiebereiken te werken.
Al sinds de oudheid kennen we allerlei soorten symmetrie. Symmetrie speelt dan ook een belangrijke rol in zowel de kunsten als de (natuur)wetenschappen. Symmetrieën die iedereen kent zijn translaties (verschuivingen), rotaties en spiegelingen. Samen kun je daarmee allerlei interessante herhalende patronen maken die je bijvoorbeeld vindt in behang, tapijten en kledingdessins.
Maar de Koch-kromme bevat een geheel nieuw soort symmetrie: zoom je erop in, dan lijkt het detail op het geheel en dat blijft zo, ongeacht hoever je inzoomt.
Dit verschijnsel kennen we ook van kustlijnen, al heeft het daar niet de perfecte regelmaat die de figuur van Koch heeft. Vanaf grote hoogte kun je een kustlijn fotograferen en de lengte berekenen. Kom je dichterbij, dan zie je onregelmatigheden die eerst onzichtbaar waren en die de lengte vergroten. Omdat een kustlijn betekenisloos wordt op het niveau van atomen en moleculen, kun je er eigenlijk geen absolute lengte aan toekennen. Bij perfect gevormde wiskundige figuren kan dat juist wel en zulke figuren met dit type symmetrie noemen we fractals.
Aan de analogie tussen de Koch-sneeuwvlok en kustlijnen zien we dat de natuur zich in een bepaald opzicht soms als fractal lijkt te gedragen.
©PXimport
Chaostheorie
Fractals vormden nauwelijks een onderwerp van studie, omdat ze aanvankelijk geen praktisch nut leken te hebben en met de hand nauwelijks te produceren waren. Met de komst van de computer, met alle grafische mogelijkheden van dien, kwam daar verandering in.
Een tweede gevolg van de computerrevolutie was de ontdekking door de Amerikaanse wiskundige en meteoroloog Edward Lorenz dat betrekkelijk simpele weermodellen, bestaande uit slechts een handvol gekoppelde vergelijkingen, een totaal andere uitkomst kunnen hebben als de startwaarden een heel klein beetje afwijken (het ‘vlindereffect’).
De grafieken die dit fenomeen opleverde, leken verdacht veel op fractals. Daarmee bleken die wonderlijke objecten ineens een direct verband te hebben met de echte wereld en dat zorgde weer voor de geboorte van een geheel nieuwe wetenschap die in de volksmond chaostheorie heet en die neerkomt op de studie van zogeheten niet-lineaire systemen.
Dat je zeer complexe patronen kunt beschrijven door middel van een handvol compacte en simpele regels, roept natuurlijk de vraag op of het omgekeerde ook kan.
De vroegste (lossless) compressie-algoritmen waren gebaseerd op het feit dat elke aaneenschakeling van bits de nodige symmetrie bevat in de vorm van translatie of spiegeling. Heb je een blok met bits gevonden waarvoor dat geldt, dan kun je in elk volgend identiek blok daarnaar verwijzen. Mag er wel sprake zijn van enig verlies, zoals bij foto’s, video’s en audio, dan kan fractale symmetrie ook ineens worden benut. Er zijn dan ook inderdaad compressie-algoritmen die hiervan gebruikmaken. De zoektocht naar goede algoritmen is daarbij werk in uitvoering, omdat compressie langs deze weg vaak tijdrovend is. Een groot voordeel is wel dat je afbeeldingen die met dit soort technieken zijn gecodeerd onbeperkt kunt uitvergroten.
©PXimport
Chaostheorie werd pas bekend bij een breed publiek toen James Gleick in 1987 zijn bestseller Chaos uitbracht. De populariteit van het boek was deels te danken aan de intrigerende schoonheid van de vele Mandelbrot-fractals die erin te bewonderen waren.
Deze bijzondere en fraaie objecten (zie beeld bovenaan dit artikel) zijn het resultaat van een zeer simpele wiskundige procedure, waarbij je het resultaat van een berekening telkens als nieuwe invoer voor diezelfde berekening gebruikt. Zo’n procedure is uiteraard gesneden koek voor de computer die inmiddels overal opdook. Een stortvloed aan programma’s om zelf fractals mee te maken was het gevolg.
Hét programma uit die beginjaren was het gratis Fractint dat in leven wordt gehouden via opvolger WinFract. De gratis alleskunner van nu heet Visions of Chaos (kortweg VoC), dat ook de bron vormde voor de meeste illustraties bij dit artikel. Naast de vele soorten fractals die door de jaren zijn ontwikkeld, stelt VoC je in staat om te experimenteren met allerlei aanverwante complexe systemen.
©PXimport
Game of Life en de Turing Machine
In 1970 bedacht de Britse wiskundige John Conway Game of Life. Op een rooster kunnen vakjes aan of uit staan en aan de hand van een paar simpele regels met betrekking tot het aantal buren dat aan of uit staat, wordt bepaald hoe het rooster in de tijd verandert. Dit bleek een dusdanige rijkdom aan vormen en structuren op te leveren dat er al snel studie werd gemaakt van allerlei vergelijkbare sets met regels, ook in meer dan twee dimensies. Al snel werd duidelijk wat de kracht was van deze zogeheten cellulaire automaten.
De Britse wiskundige Stephen Wolfram (ontwikkelaar van Mathematica) speelde zelfs met een eendimensionale variant. Deze allersimpelste automaat begint met drie vakjes op een rij die aan of uit kunnen staan en 256 mogelijke regels voor de ontwikkeling van volgende generaties. De complexiteit die sommige van deze regels laten zien, leidde tot Wolframs (tamelijk omstreden) idee dat een vergelijkbaar maar uiteraard veel ingewikkelder systeem van regels in veel meer dan één dimensie een vervanging zou kunnen vormen voor de bekende natuurwetten.
©PXimport
De Britse wiskundige Alan Turing, wiens bewogen leven meermaals is verfilmd, speelde al voor de komst van de eerste computers met ideeën die beschreven hoe een geautomatiseerd rekensysteem zou moeten werken. Die gedachten leidden tot het definiëren van de zogeheten Universele Turingmachine (UTM), de wiskundige beschrijving van een theoretische computer die alles kan wat echte computers kunnen.
Van Game of Life werd al snel ontdekt dat het een UTM kan nabootsen en zo werden bijvoorbeeld patronen met roosterpunten gevonden die als programma konden dienen om priemgetallen te genereren en zelfs complexe patronen die zichzelf kunnen kopiëren!
Misschien nog wel verrassender is het feit dat ook sommige regels van de eendimensionale automaat van Wolfram complex genoeg bleken om een UTM te vormen. Dergelijke systemen vormen dan ook een actief studiegebied binnen de theoretische informatica.
Iteratief
Eerder zagen we al dat de Mandelbrot-fractal het resultaat is van een iteratieve procedure en dat geldt ook voor de Koch-kromme en andere L-systemen. Een soortgelijke techniek kun je ook toepassen in meerdere dimensies.
Zo kun je bijvoorbeeld starten met een vierkant van N*N roosterpunten en daarvan het middelpunt bepalen. Dat punt verplaats je vervolgens een willekeurige afstand omhoog of omlaag, waardoor je een (al dan niet omgekeerde) piramide krijgt. Het vierkant is nu ook verdeeld in vier kleinere vierhoeken, waarop je de procedure kunt herhalen. In plaats van het wijzigen van de hoogte kun je beginnen met een vierkant dat bestaat uit zwarte pixels en aan het gevonden middelpunt een willekeurige grijswaarde toekennen.
Het plaatje dat zo na een aantal iteraties ontstaat, heet een plasmafractal en is voor allerlei doeleinden bruikbaar, bijvoorbeeld als hoogtekaart in een 3D-ontwerpprogramma.
In films en games zien we soms de meest adembenemende landschappen. In games zijn die altijd computergegenereerd (al dan niet op basis van echte data) en in films soms ook, bijvoorbeeld wanneer dat goedkoper is of wanneer de actie zich afspeelt in een fantasiewereld. Waar Captain Kirk zijn Star Trek-bemanning in de jaren 60 nog moest laten landen in een decor van rotsblokken gemaakt van piepschuim, kunnen filmmakers van nu hun acteurs via greenscreen-technologie op een planeet neerzetten die helemaal in de computer is ontstaan. Het terrein en de bewolking van die wereld komen tot stand via plasmafractals en aanverwante methoden. Een programma als Terragen geeft een mooi voorbeeld van dergelijke technieken. Het principe is ook in VoC te zien (Fractals, Plasma-Clouds of Fractals, Terrain of Fractals, Planet).
Eerder stelden we al vast dat kustlijnen een fractalachtige structuur hebben en zagen we hoe op basis van fractals complete planeten en wolkenluchten kunnen worden gemaakt. Maar ook de levende natuur zit vol met fractale symmetrie. Kijk je naar het wortelstelsel van een boom of naar het vaatstelsel in het menselijk lichaam, dan is niet meteen duidelijk wat de schaal is. Kijk je naar een ingezoomd plaatje van haarvaten? Of is het een beeld van grotere afstand, waardoor de kleine structuren juist niet meer zichtbaar zijn?
Het systeem dat we zagen bij de Koch-kromme plaatst steeds dezelfde structuren in een verkleinde versie in de ontstane lege ruimtes. Daardoor blijven hoeken tussen lijnen op elk niveau hetzelfde. Voegen we juist – net als bij de plasmafractals – een beetje willekeur toe aan elke stap van de procedure, dan maak je van een overduidelijk geometrisch object een voorwerp dat zo uit Moeder Natuur lijkt te komen.
De fantasiewerelden in games en films zouden wel heel saai zijn zonder vegetatie. Dankzij fractals beschikken we inmiddels gelukkig over een breed scala aan technieken om levensechte bomen en planten te maken. De L-systemen die we al eerder zagen, kunnen worden gebruikt om de basisvorm van een boom of plant te maken. Een andere mogelijkheid vinden we in het gebruik van IFS-fractals (Iterated Function Systems).
Voor het modelleren van dieren in 3D bieden fractals geen oplossing, maar voor de fraaie patronen in de vacht van bepaalde diersoorten zijn sommige cellulaire automaten zeer geschikt (zie VoC Cellular Automata, 2D, Smooth Life).
©PXimport
Kunstig
Behalve dat fractals op allerlei manieren nut hebben bij het creëren van de bouwstenen voor een creatieve productie, vormen ze van meet af aan ook van zichzelf al een rijke bron voor het maken van fraaie beelden of objecten.
Aanvankelijk beperkten de mogelijkheden zich tot stilstaande plaatjes. Fabrikanten van posters vonden inspiratie in de standaard Mandelbrot-fractal, terwijl kunstenaars probeerden om deze op allerlei manieren naar hun hand te zetten. Meer rekenkracht bracht ons de mogelijkheid om filmpjes te maken waarin wordt ingezoomd op de Mandelbrot- en aanverwante fractals. YouTube bevat er inmiddels tienduizenden.
Nog krachtiger pc’s brachten ons 3D-fractals (zie VoC Hypercomplex Fractals, Mandelbulb of het gespecialiseerde Mandelbulber). Op basis van deze en aanverwante fractals produceer je complete 3D-animaties met objecten die niet alleen mooi en interessant zijn, maar die je bovendien met geen mogelijkheid zelf zou kunnen modelleren.
Een logische volgende stap is dat kunstenaars en hobbyisten inmiddels ook 3D-printtechnologie gebruiken om de schoonheid van hun creaties tastbaar te maken.
Brein
Eerder zagen we al dat het vaatstelsel een fractale structuur heeft. Dat geldt tot op zekere hoogte ook voor het brein, waarin stelsels van grote verbindingen bestaan naast telkens kleinere vertakkingen. Het complexe en onvoorspelbare gedrag van onze hersenen valt hieruit ook deels te verklaren.
Iets dergelijks zien we ook terug in grootschalige computernetwerken. In de studie daarvan spelen fractals dan ook een rol. Wanneer dergelijke complexiteit kan optreden bij de handvol simpele vergelijkingen uit de weermodellen van Lorenz, dan zal het niemand verbazen dat iets dergelijks zich zéker voordoet bij de neurale netwerken die gebruikt worden voor kunstmatige intelligentie (AI). Zelfs de best getrainde visuele AI kan een voorwerp waarvan het er al duizenden heeft herkend op zeker moment aanzien voor iets anders, net zoals onze hersenen af en toe de fout in gaan.
Een nieuwe ontwikkeling in de creatie van op fractals gebaseerde kunst is dan ook de combinatie van fractals en van het beeld dat AI daarin ‘meent’ te zien.
Visuele AI kan niet alleen objecten herkennen, maar ook de visuele stijl van een afbeelding veranderen op basis van de stijl van een andere, bijvoorbeeld van een bekend schilderij. Op www.deepdreamgenerator.com kun je daarmee online experimenteren.
Wie over een Nvidia-videokaart beschikt, kan VoC ook uitbreiden met de mogelijkheid om lokaal AI los te laten op fractals of gewoon op eigen afbeeldingen. Het installeren van de benodigde componenten kost al snel een uur, maar is zeer de moeite waard.
©PXimport
Fractals in audio
Ruim 2500 jaar geleden ontdekte de Griekse wiskundige Pythagoras al dat klanken die voor ons aangenaam klinken frequenties hebben die in een eenvoudige rekenkundige verhouding tot elkaar staan. Zo horen we twee verschillende tonen als dezelfde noot wanneer de frequentieverhouding 1:2 is (een octaaf) en geeft een verhouding 2:3 een zuivere kwint; de eerste en laatste noot van elk majeur- of mineurakkoord.
Behalve dat je muziek kunt analyseren aan de hand van de gebruikte toonhoogtes, kun je ook naar de structuur van een muziekstuk kijken. Naast een overkoepelende structuur zoals ABA (bijvoorbeeld couplet, refrein, couplet), zie je dan kleinere structuren. Zo kan het couplet een eigen ABA-structuur hebben van twee identieke regels en een afwijkende in het midden. Zelfs deze regels hebben vaak nog een interne structuur die hetzelfde stramien kan volgen en dat alles doet sterk denken aan een fractal.
Er wordt daarom al jaren geëxperimenteerd met het genereren van aangename muziek op basis van fractals. Naast specialistische software zoals Aural Fractals biedt VoC de mogelijkheid om op basis van sommige soorten fractals midimuziek op te slaan.
Conclusie
Het gebruik van fractals voor allerlei toepassingen in de IT heeft inmiddels een grote vlucht genomen en voortdurend worden er nieuwe technieken mee ontwikkeld. Daarnaast hebben ze hun nut bewezen binnen allerlei vakgebieden, variërend van biologie en geneeskunde tot geologie en economie.
Los daarvan zijn fractals vaak objecten met een grote visuele schoonheid en met een variatie waarover je je eindeloos kunt verbazen. Dus zelfs wie niet geïnteresseerd is in de achterliggende wetenschap, kan er toch volop van genieten.
