For 40 år siden lavede Tom Oslo-algoritmen: Alle bruger den, men få ved det

I år er det 40 år siden, den såkaldte Oslo-algoritme lagde grundlaget for blandt andet de teknikker, der ligger bag animationsfilmen Toy Story.

Denne artikel er fra Titan.uio.no, en netavis udgivet af Universitetet i Oslo (UiO). Originalen kan læses her.

»Vi lagde sidste hånd på den første videnskabelige artikel om Oslo-algoritmen i juni 1979, og vi var meget stolte, da artiklen blev antaget og publiceret året efter. Det er jo skønt at tænke på, at hele verden sidder i dag og ser på de ting, vi arbejdede med,« fortæller professor emeritus Tom Lyche fra Matematisk institutt på Universitetet i Oslo, UiO.

Postscript

Med spline-software blev det pludselig muligt at tegne bogstaver, som havde glatte og fine omrids. Det fremskridt skete i 1980’erne. Illustration: UiO

Han tænker helt konkret på de glatte og fine bogstaver, som fylder computerskærme over hele verden. Mange kan måske huske, at bogstaverne på computerne i gamle dage var hakkede og grimme – men så skete der noget i 1980’erne.

Da kom programmeringssproget Postscript, som blandt andet gjorde det muligt at tegne glatte og fine bogstaver i alle mulige størrelser.

»Jeg vil ikke sige, at Oslo-algoritmen direkte ligger inde i alle moderne fonte. Men softwaren, som laver fontene, bygger på den samme filosofi, som du finder i Oslo-algoritmen,« præciserer Lyche.

Her er det på sin plads med en lille ordforklaring: En algoritme er en ‘regneregel’, en matematisk opskrift på, hvordan et eller andet skal beregnes. Du bruger en enkel algoritme, når du dividerer et flercifret tal, og Skat bruger en lidt mere kompliceret algoritme, når de udregner din skat på grundlag af indtægten og fradragene.

»Oslo-algoritmen er en regneregel, som gjorde det muligt at tegne kurver og former, akkurat som du ønsker, at de skal være. Du kan starte med nogle enkle polynomier, som giver dig en glat og sammenhængende kurve, og så kan du ændre kurvens form ved hjælp af Oslo-algoritmen. Resultatet bliver stadig en glat kurve,« forklarer Lyche.

Oslo-algoritmens succes

Begrebet polynomium er nærmere forklaret i faktaboksen.

Baggrunden for Oslo-algoritmens succes er, at den kan bruges til meget mere end at tegne linjer, kurver og flader. De færdige tegninger kan nemlig blandt andet bruges til at styre fræsemaskiner, svejserobotter og deslige.

Så er vi pludselig over i det, som bliver kaldt CAD/CAM – Computer Aided Design/Computer Aided Manufacturing – og Oslo-algoritmen bruges fortsat i stort omfang på dette felt: til bildesign, flydesign, arkitektur, korttegning, turbineproduktion, skibsbyggeri og så videre.

Varianter af Oslo-algoritmen ligger også bag kameraføringen og tegningen af figurerne i den banebrydende animationsfilm Toy Story.

»Det amerikanske tegnefilmstudie Pixar gik senere over til en anden og mere grafisk teknik, men spline-kurver og Oslo-lignende algoritmer bruges stadig i andre tegnefilm,« fortæller forskningsleder Tor Dokken fra Sintef Digitals afdeling for matematik og kybernetik. En spline er en funktion, som er stykvis defineret af forskellige polynomier.

»Da Oslo-algoritmen kom for 40 år siden, var det på præcis det rigtige tidspunkt, når det gjaldt computernes udvikling og behovet i industrien. Der havde været en kamp om at udvikle den rette algoritme, men Oslo-algoritmen blev stående som den rigtige måde at gøre det på. Det her var algoritmen, som virkelig gjorde computerassisteret konstruktion og produktion mulig,« siger Dokken.

Sintef Digital

Han fortæller, at Oslo-algoritmen fik stor betydning for det, som nu er matematik- og kybernetik-afdelingen ved Sintef Digital.

»Det var et helt grundlæggende numerisk værktøj, som kom på plads der, og som gav os en mulighed for at få store projekter og arbejde med anvendelser. Algoritmen lagde et grundlag for, at vi kunne få succes kommercielt med software, som bruger splines.«

»Og 40 år senere har vi stadig godt med aktiviteter på dette område. I alle disse år har vi haft et godt og tillidsfuldt samarbejde med Tom Lyche og miljøet på UiO,« fortæller Dokken.

Denne røde parabel viser, hvordan andengradsligningen y = x2 , med én karakteristisk ‘bulk’, ser ud i en grafisk fremstilling. Illustration: UiO

Tom Lyche (født 1943) begyndte at studere matematik ved UiO i 1964. Han fuldførte en kandidatgrad i Oslo og rejste derefter til USA for at tage en doktorgrad ved University of Texas.

Der kom han i kontakt med Larry Schumaker, som vejledte ham frem til en doktorgrad i spline-teori. Forskerne, som arbejder med dette, bruger forresten helst den engelske flertalsform splines, af forståelige årsager.

I 1972 blev Lyche ansat som universitetslektor i numerisk analyse ved Institutt for informatikk, mens han var i gang med at skrive doktorgraden færdig. Han etablerede også et hovedfagskursus, som efterfølgende fik mange dygtige hovedfagsstudenter.

Spline-funktioner

En af dem var Tor Dokken, som blev færdig i 1978 og straks fik job på norske Senter for industriforskning (SI) – som senere blev en del af forskningsstiftelsen Sintef. Der er han stadig – som en ivrig bruger af splines og Oslo-algoritmen.

»På SI kom jeg med i en gruppe, som skulle arbejde med at modellere former, og en dag kom det amerikanske forsker-ægtepar Elaine Cohen og Richard Riesenfeld fra University of Utah på besøg. De havde hørt om Tom og ville gerne møde ham, så det blev til, at jeg fulgte dem ned på hans kontor,« mindes Dokken.

Amerikanerne var interesserede i at bruge spline-funktioner til at modellere fysiske objekter, og de etablerede senere et firma, som brugte både splines og Oslo-algoritmen til at designe og udfræse fysiske objekter.

De havde allerede skrevet en videnskabelig artikel om opsplitning og splejsning af kurver, som er grundlaget for arbejdet med splines. Men de antog, at der måtte findes en mere effektiv måde at gøre dette på, og at Lyche var manden, som kunne løse problemet – og det stemte.

»Tom var en rigtig god teoretisk spline-matematiker, efter min mening blandt de bedste i verden. Jeg tror ikke, han havde tænkt så meget på, at hans teorier kunne have praktisk værdi, men så viste det sig altså, at Oslo-algoritmen gik direkte ind i et industrielt behov,« forklarer Dokken.

Toy Story

Polynomier med tilstrækkelig høj grad kan i princippet tegne meget komplicerede kurver. Men polynomier af høj grad har også nogle ulemper, så hvis du vil kunne tegne generelle kurver uden disse ulemperne, skal du finde på noget andet – og det var det, Tom Lyche og kollegerne gjorde med Oslo-algoritmen.

»Du behøver ikke forstå matematik for at glæde dig over ‘Toy Story’ eller et digitalt tegneprogram. Men der ligger virkelig meget matematik bag produktioner som den, selv om de fleste kan se dem uden at tænke på matematik overhovedet,« siger professor Knut Mørken.

Han tog sit hovedfag i matematik med Lyche som vejleder, og han har senere haft stor glæde af Oslo-algoritmen i en karriere, som i dag har gjort ham til vicedekan for uddannelse ved MN-fakultetet.

Ideen bag splines og Oslo-algoritmen er tilsyneladende enkel: Det er ikke nødvendigt at bruge meget komplicerede polynomier for at tegne en kompliceret kurve; du kan i stedet opdele kurven i mange småbidder og beskrive hver enkelt bid med enklere polynomier. Det, Oslo-algoritmen gør, er at sammensplejse bidder af polynomier på en enkel og effektiv måde.

»Du kan for eksempel bruge et tredjegradspolynomium på det ene interval og et andet tredjegradspolynomium på næste interval. Og så videre. Det unikke ved Oslo-algoritmen er, at den håndterer dette, samtidig med at den kan ‘oversætte’ noget, som er tegnet på en grov skala, til en fin skala uden at ændre på beskrivelsen. Dette har vist sig at være meget slagkraftigt,« fortæller Mørken.

Troppede op på kontoret

Richard Riesenfeld havde allerede skrevet en algoritme for at gøre dette, men den havde begrænsede muligheder. Hans algoritme førte til, at det var nødvendigt at indsætte nye bidder overalt i polynomiet, selv om det bare var en detalje, som skulle ændres. Dermed blev det matematiske udtryk meget stort og uhåndterbart.

»Da Elaine og Rich kom ind på mit kontor i 1979, ønskede de at kunne gøre dette lokalt. Det lyder måske banalt, men det var ikke så let at gøre.«

»Pointen med Oslo-algoritmen er, at polynomierne bliver repræsenteret på en speciel måde: Vi brugte noget, som hedder B-splines, som altså følger et polynomium, til et nyt polynomium overtager. To spline-kurver, som mødes, får samme værdi og tangent i mødepunktet, og så får vi en helt glat kurve, som kan skaleres op og ned,« forklarer Lyche.

Tom Lyche er en beskeden mand, som er optaget af at fremhæve dem, som havde lagt grundlaget for den matematiske udvikling af Oslo-algoritmen. På Akers Mekaniske Verksted brugte de for eksempel fysiske modeller af splines til at lave de former, som skulle bruges i skibsbygningen.

De fysiske modeller var store, bøjelige metalstænger, en slags linealer, og så brugte skibsbyggerne lodder med forskellig vægt til at bøje stængerne til den form, de ønskede.

Fra 1700-tallet

Det er også på sin plads at nævne Even Mehlum, som lavede det hulkortbaserede program Autokon allerede i 1965. På Kongsberg Våpenfabrikk havde de tegnemaskiner, som kunne tegne cirkler og rette linjer, og Mehlums system gjorde, at disse kunne tegnes meget hurtigt.

Autokon var så vellykket, at systemet på et tidspunkt havde hele 70 procent af verdensmarkedet for modellering af skibsskrog, fortæller Lyche.

Typisk for Oslo-algoritmen: Figuren illustrerer beregninger som foretages i et tilfælde med et tredjegradspolynomium. Illustration: Tom Lyche/UiO

Den franske matematiker Joseph Fourier begyndte så småt at udvikle den nødvendige teori allerede omkring 1700-tallet, da han viste, at alle periodiske funktioner kan fremstilles som en sum af sinus- og cosinusfunktioner.

Den moderne udvikling begyndte under Anden Verdenskrig, da den rumænsk-amerikanske matematiker Isaac Jacob Schoenberg arbejdede med nøjagtig tabulering og udjævning af data, som beskrev en bombes bane, når den blev kastet.

I 1960’erne begyndte de franske bilfabrikker Renault og Citroën at bruge computere til at modellere bilkarosserier.

Citroën-matematikeren Paul de Fajet de Casteljeau og Renault-ingeniøren Pierre Bézier har indskrevet sig i matematik-historien, fordi de udviklede et specialtilfælde af spline-funktionerne til netop at modellere karosserier.

Det hører også med til historien, at en tysk kollega til Lyche, Wolfgang Böhm, omtrent samtidig udviklede en alternativ variant af Oslo-algoritmen.

Tre sammensplejsede parabler – en spline – bliver pludselig til en helt ny kurve. Illustration: UiO

75 år

Tom Lyche har haft mange studerende, som senere har gjort karriere, ud over Tor Dokken og Knut Mørken. Også MN-fakultetets dekan, Morten Dæhlen, har studeret hos Lyche.

»Jeg har været velsignet med mange gode studerende, og Ragnar Winther var faktisk min første hovedfagsstuderende. Han har netop afsluttet et stort EU-projekt,« fortæller Lyche.

»Hvis ikke Tom Lyche og de to amerikanere havde opfundet Oslo-algoritmen, ville nogle andre have gjort det. Den kan forresten også bruges til at komprimere lydfiler og billeder ned til mindst en tiendedel af størrelsen, uden at du hører eller ser nogen særlig forskel. I USA bruger politiet fortsat dette til at komprimere fingeraftryk,« siger Knut Mørken.

Tom Lyche er 75 år gammel, men har ingen planer om at lade sig pensionere. I stedet kommer han stadig til sit kontor på 12. etage i Abels tårn – den såkaldte emeritus-etage – hver eneste dag, undtagen i ferierne, og når han er på en international konference.

Det er sådan, det er med folk, som elsker deres job. Matematikere kan nemlig blive meget engagerede i det, de er i gang med.

»I vores miljø fortæller vi stadig om første gang, Stanford-professoren Donald Knuth var i Oslo, da arbejdede han med at lave digitale skrifttyper. Tom og Donald skulle spise middag hos Ole Johan Dahl i Asker, og Tom skulle køre. Men undervejs blev de så optaget af en matematisk diskussion, at de glemte at tage afkørslen til Asker. De opdagede ingenting, før de var kommet helt til Drammen, så den middag blev lidt forsinket,« fortæller Knut Mørken og ler højt.

Denne artikel er fra Titan.uio.no, en netavis udgivet af Universitetet i Oslo (UiO). Originalen kan læses her.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (2)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Torben Mogensen Blogger

Det er meget uklart af artiklen, hvad Osloalgoritmen faktisk gør, så jeg lavede lidt research.

B-splines er defineret ud fra nogle styrepunkter, som vist i figuren med S-bogstavet. Kurven går ikke (nødvendigvis) gennem styrepunkterne, men de "trækker" groft sagt i kurven. En liste af 2N styrepunkter bruges til at definere et polynomium, der definerer den del af kurven, der ligger tættest på de to midterste af disse styrepunkter. Når man fjerner et styrepunkt i den ene ende af listen og tilføjer et i den anden ende, definerer de et polynomium for den næste del af kurven osv. B-splines er defineret, sådan at kurven dermed bliver kontinuert og glat.

Osloalgoritmen går ud på at indsætte ekstra styrepunkter mellem de eksisterende uden at kurven dermed ændrer form. Det bruges blandt andet til at tegne kurven: Man indsætter rekursivt flere og flere styrepunkter, indtil de ligger i afstand af en pixel fra hinanden, hvorefter de plottes. Det er hurtigere end at bruge polynomierne direkte.

  • 4
  • 0
Log ind eller Opret konto for at kommentere
IT Company Rank
maximize minimize