Artikkel

40 år med algoritmen du ikke vet om, men som alle bruker

Professor Tom Lyche har utsikt over byen som den 40 år gamle algoritmen er oppkalt etterq
Professor Tom Lyche med utsikt over byen som den 40 år gamle - men evig unge - algoritmen hans er oppkalt etter. Foto: Bjarne Røsjø, UiO. Bruk bildet.

40 år med algoritmen du ikke vet om, men som alle bruker

Du trenger ikke forstå matematikk for å glede deg over Toy Story, et digitalt tegneprogram, et nettbasert kart eller en elegant sportsbil. Uansett ligger det veldig mye matematikk bak applikasjonene som kan skape slike produkter, og i år er det 40 år siden Oslo-algoritmen la grunnlaget for mye av det vi kan glede oss over i dag. 

Med spline-programvare blir bokstaver glatte og fine.
Med spline-programvare ble det plutselig mulig å tegne bokstaver som hadde glatte og fine omriss: Det fremskrittet skjedde på 1980-tallet. Illustrasjon: UiO Bruk bildet.

– Vi la siste hånd på den første vitenskapelige artikkelen om Oslo-algoritmen i juni 1979, og så var vi veldig stolte da artikkelen ble antatt og publisert året etter. Det er jo hyggelig å tenke på at i dag sitter hele verden og ser på sånne ting som vi jobbet med, forteller professor emeritus Tom Lyche ved Matematisk institutt på UiO.

Han tenker helt konkret på de glatte og fine bokstavene som fyller dataskjermer over hele verden. De som har levd en stund, husker at bokstavene på dataskjermene i gamle dager var hakkete og stygge, men så skjedde det noe på 1980-tallet. Da kom programmeringsspråket Postscript, som blant annet gjorde det mulig å tegne glatte og fine bokstaver i alle mulige størrelser.

– Jeg vil ikke akkurat si at Oslo-algoritmen direkte ligger inne i alle moderne fonter. Men programvaren som lager fontene, bygger på den samme filosofien som du finner i Oslo-algoritmen, presiserer Lyche.

Her er det på plass med en liten ordforklaring: En algoritme er en «regneregel», en matematisk oppskrift på hvordan et eller annet skal beregnes. Du bruker en enkel algoritme når du dividerer et flersifret tall, og Skatteetaten bruker en litt mer komplisert algoritme når de regner ut skatten din på grunnlag av inntekten og fradragene.

– Oslo-algoritmen er en regneregel som gjorde det mulig å tegne kurver og former akkurat slik du ønsker at de skal være. Du kan starte med noen enkle polynomer som gir deg en glatt og sammenhengende kurve, og så kan du endre kurvens form ved hjelp av Oslo-algoritmen. Resultatet blir fortsatt en glatt kurve, forklarer Lyche.

Begrepet polynom er nærmere forklart i faktaboksen (se under).

Åpnet døren for DAK/DAP

Den røde parabelen viser hvordan en annengradslikning ser ut i en grafisk fremstilling.
Denne røde parabelen viser hvordan annengradslikningen y = x2 , med én karakteristisk "bulk", ser ut i en grafisk fremstilling. Illustrasjon: UiO Bruk bildet.

Bakgrunnen for Oslo-algoritmens suksess er at den kan brukes til mye mer enn å tegne linjer, kurver og flater. De ferdige tegningene kan nemlig blant annet brukes til å styre fresemaskiner, sveiseroboter og slike ting. Da er vi plutselig over i det som blir kalt DAK/DAP – dataassistert konstruksjon og produksjon – og Oslo-algoritmen brukes fortsatt i stort omfang på dette feltet. Til bildesign, flydesign, arkitektur, karttegning, turbinproduksjon, skipsbygging og så videre.

Varianter av Oslo-algoritmen ligger også bak kameraføringen og tegningen av figurene i den banebrytende animasjonsfilmen Toy Story.

– Det amerikanske tegnefilmstudioet Pixar gikk senere over til en annen og mer grafisk teknikk, men spline-kurver og Oslo-liknende algoritmer brukes fortsatt i andre tegnefilmer, forteller forskningsleder Tor Dokken ved SINTEF Digitals avdeling for matematikk og kybernetikk. En spline er en funksjon som er stykkevis definert av ulike polynomer.

polynomer og splines

Et polynom («mange navn») er et matematisk uttrykk med et endelig antall ledd. Polynomet er definert ved hjelp av addisjon, subtraksjon og multiplikasjon.

  • De såkalte førstegradspolynomene (for eksempel f(x) = x +2) danner en rett linje hvis du tegner dem inn i en graf.
  • Annengradspolynomer (for eksempel f(x) = 2x2 + 3x + 5) danner en parabel, det vil si en kurve med én «bulk».
  • Tredjegradspolynomer, hvor minst ett av leddene med x er opphøyd i tredje potens, danner en kurve med to «bulker». Og så videre.

– Da Oslo-algoritmen kom for 40 år siden, var det akkurat til rett tid når det gjaldt datamaskinenes utvikling og behovet i industrien. Det hadde pågått en kamp om å utvikle den rette algoritmen, men Oslo-algoritmen ble stående som den riktige måten å gjøre det på. Dette var algoritmen som virkelig gjorde datamaskin-assistert konstruksjon og –produksjon mulig, tilføyer Dokken.

Han forteller at Oslo-algoritmen fikk stor betydning for det som nå er matematikk og kybernetikk-avdelingen ved SINTEF Digital.

– Det var et helt grunnleggende numerisk verktøy som da kom på plass og som ga oss en mulighet til å få store prosjekter og jobbe med anvendelser. Algoritmen la et grunnlag for at vi lyktes kommersielt med programvare som bruker splines mot industrien. Og 40 år senere har vi fortsatt bra med aktiviteter på dette området. I alle disse årene har vi hatt et godt og tillitsfullt samarbeid med Tom Lyche og miljøet på UiO, forteller Dokken.

Algoritmens forhistorie

Tre sammenskjøtte parabeler - en spline - blir plutselig til en helt ny kurve.
Tre sammenskjøtte parabeler - en spline - blir plutselig til en helt ny kurve. Illustrasjon: UiO.

Tom Lyche (født 1943) begynte å studere matematikk ved UiO i 1964. Han fullførte en cand.real. i Oslo og reiste deretter til USA for å ta en doktorgrad ved University of Texas. Der kom han i kontakt med Larry Schumaker, som veiledet ham fram til en doktorgrad i spline-teori. Forskerne som jobber med dette, bruker forresten helst den engelske flertallsformen splines, av forståelige årsaker.

I 1972 ble Lyche ansatt som universitetslektor i numerisk analyse ved Matematisk institutt ved Universitetet i Oslo, mens han var i ferd med å skrive ferdig doktorgraden. Han etablerte også et hovedfagskurs, som etter hvert fikk mange dyktige hovedfagsstudenter. En av disse var Tor Dokken, som ble ferdig i 1978 og straks fikk jobb på Senter for industriforskning (SI) – som senere gikk inn i forskningsstiftelsen SINTEF. Der er han fortsatt, som en ivrig bruker av splines og Oslo-algoritmen.

– På SI ble jeg med i en gruppe som skulle jobbe med å modellere form, og en dag kom det amerikanske forsker-ekteparet Elaine Cohen og Richard Riesenfeld fra University of Utah på besøk. De hadde hørt om Tom og ville gjerne møte ham, så da ble det til at jeg fulgte dem ned til kontoret hans, minnes Dokken.

Amerikanerne var interessert i å bruke spline-funksjoner til å modellere fysiske objekter, og de etablerte senere et firma som brukte både splines og Oslo-algoritmen til å designe og frese ut fysiske objekter. De hadde allerede skrevet en vitenskapelig artikkel om splitting og skjøting av kurver, som er grunnlaget for arbeidet med splines. Men de ante at det måtte finnes en mer effektiv måte å gjøre dette på og at Lyche var mannen som kunne løse problemet – og det stemte.

– Tom var en veldig god teoretisk spline-matematiker, etter min mening blant de beste i verden. Jeg tror ikke han hadde tenkt så mye på at teoriene hans kunne ha praktisk verdi, men så viste det seg altså at Oslo-algoritmen gikk rett inn i et industrielt behov, forklarer Dokken.

Matematisk teori til praktisk bruk

Richard Riesenfeld, Tom Lyche og Elaine Cohen
Oslo-algoritmens to fedre og moren: Richard Riesenfeld, Tom Lyche og Elaine Cohen – på Oslos tak for snart 20 år siden. Foto: Ståle Skogstad Bruk bildet.

Polynomer med tilstrekkelig høy grad kan i prinsippet tegne veldig kompliserte kurver. Men polynomer av høy grad har også noen ulemper, så hvis du vil kunne tegne generelle kurver uten disse ulempene, må du finne på noe annet – og det var det Tom Lyche og kollegene gjorde med Oslo-algoritmen.

– Du trenger ikke forstå matematikk for å glede deg over Toy Story eller et digitalt tegneprogram. Men det ligger veldig mye matematikk bak disse produksjonene, selv om folk flest kan bruke dem uten å tenke på matematikk i det hele tatt, sier professor Knut Mørken.

Han tok sitt hovedfag i matematikk med Lyche som veileder, og han har senere hatt stor glede av Oslo-algoritmen i en karriere som i dag har gjort ham til visedekan for utdanning ved MN-fakultetet.

Ideen bak splines og Oslo-algoritmen er tilsynelatende enkel: Det er ikke nødvendig å bruke veldig kompliserte polynomer for å tegne en komplisert kurve; du kan isteden dele opp kurven i mange småbiter og beskrive hver enkelt bit med enklere polynomer. Det Oslo-algoritmen gjør, er å skjøte sammen biter av polynomer på en enkel og effektiv måte.

– Du kan for eksempel bruke ett tredjegradspolynom på det ene intervallet og et annet tredjegradspolynom på neste intervall. Og så videre. Det unike med Oslo-algoritmen er at den håndterer dette samtidig som den kan «oversette» noe som er tegnet på en grov skala til en fin skala uten å endre på beskrivelsen. Dette har vist seg å være veldig slagkraftig, forteller Mørken.

Richard Riesenfeld hadde allerede skrevet en algoritme for å gjøre dette, men den hadde begrensede muligheter. Hans algoritme førte til at det var nødvendig å sette inn nye biter overalt i polynomet, selv om det bare var en detalj som skulle endres. Dermed ble det matematiske uttrykket veldig stort og uhåndterlig.

– Da Elaine og Rich kom inn på mitt kontor i 1979, ønsket de å kunne gjøre dette lokalt. Det høres kanskje banalt ut, men det var ikke så lett å få til. Poenget med Oslo-algoritmen er at polynomene blir representert på en spesiell måte; vi brukte noe som heter B-splines, som altså følger ett polynom til et nytt polynom overtar. To spline-kurver som møtes får samme verdi og tangent i møtepunktet, og da får vi en helt glatt kurve som kan skaleres opp og ned, forklarer Lyche.

Bygde på tidligere kunnskap

Figuren illustrerer hvordan en beregning kan gjøres i et tilfelle med et tredjegradspolynom.
Typisk for Oslo-algoritmen: Figuren illustrerer beregninger som gjøres i et tilfelle med et tredjegradspolynom. Illustrasjon: Tom Lyche Bruk bildet.

Tom Lyche er en beskjeden mann som er opptatt av å løfte fram dem som hadde lagt grunnlaget for den matematiske utviklingen av Oslo-algoritmen. På Akers Mekaniske Verksted brukte de for eksempel fysiske modeller av splines for å lage de formene som skulle brukes i skipsbyggingen. De fysiske modellene var store, bøyelige metallstenger, en slags linjaler, og så brukte skipsbyggerne lodd av ulik vekt for å bøye stengene til den formen de ville ha.

Det er også på sin plass å nevne Even Mehlum, som lagde det hullkortbaserte programmet Autokon allerede i 1965. På Kongsberg Våpenfabrikk hadde de tegnemaskiner som kunne tegne sirkler og rette linjer, og Mehlums system gjorde at disse kunne tegnes ut veldig fort. Autokon var så vellykket at systemet på et tidspunkt hadde hele 70 prosent av verdensmarkedet for modellering av skipsskrog, forteller Lyche.

Den franske matematikeren Joseph Fourier begynte så smått å utvikle den nødvendige teorien allerede på 1700-tallet, da han viste at alle periodiske funksjoner kan framstilles som en sum av sinus- og cosinusfunksjoner. Den moderne utviklingen startet under annen verdenskrig, da den rumensk-amerikanske matematikeren Isaac Jacob Schoenberg arbeidet med nøyaktig tabulering og glatting av data som beskrev en bombekasterbane.

På 1960-tallet begynte de franske bilfabrikkene Renault og Citroën å bruke datamaskiner til å modellere bilkarosserier. Citroën-matematikeren Paul de Fajet de Casteljeau og Renault-ingeniøren Pierre Bézier har skrevet seg inn i matematikk-historien fordi de utviklet et spesialtilfelle av spline-funksjonene for å få til dette.

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

Studenter har gjort karriere

Spline-konferansen i 2012
Oslo-miljøet har arrangert konferanser om modellering av kurver og flater hvert fjerde år helt siden 1988. På dette bildet fra 2012 sitter Tom Lyche foran til høyre. Larry Schumaker (mørk genser, armene i kors) står et trinn høyere og litt til venstre. Daværende IFI-bestyrer Morten Dæhlen står ytterst til høyre på rad to. Foto: UiO. Bruk bildet.

Tom Lyche har hatt mange studenter som senere har gjort karriere, i tillegg til Tor Dokken og Knut Mørken. Også MN-fakultetets dekan Morten Dæhlen har studert hos Lyche.

– Jeg vært velsignet med mange gode studenter, og Ragnar Winther var faktisk min første hovedfagsstudent. Han har nettopp avsluttet et stort EU-prosjekt, forteller Lyche.

– Hvis ikke Tom Lyche og de to amerikanerne hadde funnet opp Oslo-algoritmen, måtte noen andre gjort det. Den kan forresten også brukes til å komprimere lydfiler og bilder ned til minst en tidel av størrelsen, uten at du hører eller ser noen særlig forskjell. I USA bruker politiet fortsatt dette til å komprimere fingeravtrykk, sier Knut Mørken.

Glemte seg og havnet i Drammen

Tom Lyche er 75 år gammel, men har ingen planer om å pensjonere seg. Isteden kommer han fortsatt til kontoret sitt i 12. etasje i Abels tårn – den såkalte emeritus-etasjen – hver eneste dag, unntatt i feriene og når han er på en internasjonal konferanse. Det er sånn det blir med folk som elsker jobben sin. Matematikere kan nemlig bli veldig engasjert i det de holder på med.

– I miljøet vårt forteller vi fortsatt om første gang Stanford-professoren Donald Knuth var i Oslo, da jobbet han med å lage digitale fonter. Tom og Donald skulle spise middag hos Ole Johan Dahl i Asker, og Tom skulle kjøre. Men underveis ble de så engasjert i en matematisk diskusjon at de glemte avkjøringen til Asker. De oppdaget ingenting før de var kommet helt til Drammen, så den middagen ble litt forsinket, forteller Knut Mørken og ler høyt.

Kontaktpersoner:

Professor emeritus Tom Lyche, Matematisk institutt

Forskningsleder Tor Dokken, SINTEF

Professor og visedekan Knut Mørken, MN-fakultetet

Den første vitenskapelige artikkelen om Oslo-algoritmen:

Elaine Cohen, Tom Lyche and Richard Riesenfeld: Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics. Computer Graphics and Image Processing, Volume 14, Issue 2, October 1980.

Utvalgte senere artikler:

Lyche, T., E. Cohen, and K. Mørken: Knot line refinement algorithms for tensor product B-spline surfaces. Computer-Aided Geometric Design, 2 (1985), 133–139.

Tom Lyche and Knut Mørken: Making the Oslo Algorithm More Efficient. SIAM Journal on Numerical Analysis, 1986, Vol. 23, No. 3.

Cohen, E., Lyche, T., and L. L. Schumaker: Degree raising for splines. Journal of Approximation Theory 46 (1986), 170–181.

Cohen, E., Lyche, T., and L. L. Schumaker: Algorithms for degree-raising of splines. ACM Transactions on Graphics 4 (1986), 171–181.

Lyche, T., and K. Mørken: Knot removal for parametric B-spline curves and surfaces. Computer-Aided Geom. Design 4 (1987), 217–230.

Arge, E., M. Dæhlen, T. Lyche, and K. Mørken: Constrained spline approximation of functions and data based on constrained knot removal. In Algorithms for Approximation II, J. C. Mason and M. G. Cox (eds.), Chapman and Hall, London, 1990, 4–20.

Sederberg, T. W., Cardon, D. L., Finnigan, G. T. North, N. S., Zheng J., and T. Lyche: T-spline Simplification and Local Refinement. ACM Transactions on Graphics, 23 (2004), 276–283.

Dokken, T., Lyche, T. and Pettersen, K.F.: Polynomial splines over locally refined box-partitions. Computer Aided Geom. Design, 30 (2013), 331–356.

Les også

Professor Nils Christian Stenseth blar andektig i Mendels gamle manuskript

– Fantastisk opplevelse å få bla i Mendels manuskript

Professor Nils Chr. Stenseth har opplevd mye i løpet av en lang forskerkarriere, men besøket i St. Thomas-klosteret i den tsjekkiske byen Brno ble likevel noe utenom det vanlige. Der fikk Stenseth nemlig lov til å bla i et av biologiens aller viktigste verk: Munken Gregor Mendels håndskrevne originalmanuskript fra 1865.

Eva Lena Fjeld Estensmo undersøker hvor mye støv som har samlet seg på Kristine Bonnevie

Enkle støvprøver avslører hvem andre som bor i huset ditt

Eva Lena Fjeld Estensmo undersøker støvprøver fra barnehager og private hjem, for å kartlegge hva slags mikroskopiske sopper – både skadelige og harmløse – som vokser innendørs i Norge. Men analysemetodene er så fintfølende at støvprøvene til og med kan avsløre hva folk har i kjøleskapet.