Kva gjer Askeladden i verdsrommet dersom han ikkje kan sj? rundt seg og finne ut kvar han befinn seg? Det kan ikkje vere enkelt ? navigere seg fram utan ? sj? noko. Men kva er det som kan hjelpe Askeladden med ? navigere? Heldigvis var det mor hans som hadde pakka sekken. Askeladden var stor gut og pissa sj?lv, men det ? pakke eigen sekk kunne han vente nokre ?r til med. Mor til Askeladden hadde nemleg pakka med eit toppmoderne kamera! Med dette kameraet montert p? ei roterande skive p? toppen av masta, kunne han ta bilete rundt seg og endeleg finne ut kvar han var.
Men hadde mor hans tenkt s?pass langt som ? lage programvare til dette kolossale kameraet? Neida! Her m?tte Askeladden tr? til sj?lv!
Merk: Denne bloggposten vert lang, s? sl?yng fr? deg t?flane, len deg godt attende, og la hovudet synke inn i eventyrmodus der alt fr? troll og hekser til fysikkens lovar er ekte.
S? kvar skal v?r kj?re Askeladden byrje? Han har alts? ei himmelkule han skal ta bilete av, men korleis ser denne himmelkula ut? Sj? for deg at du svevar ?leine i verdsrommet. Kanskje litt einsamt, men la oss anta at det er triveleg. Du er d? i sentrum av ei kule, ei sf?re om du vil, og alle stjernane, planetane og alt anna av omgjevnadar dekkjer heile innsida av denne kula. P? ein m?te m?la p? innsida av kula. Det er dette som er himmelkula, og for ? gjera det noko enklare ? drive med, vil vi berre bekymre oss for regionen rundt ekvator p? denne kula. Sj? Figur 1 nedanfor for ei skisse av himmelkula.
Med andre ord: kameraet er posisjonert i sentrum medan det roterar \(360^\circ\) og tek bilete av ekvatorregion.
"Panoramabilete vil fungere fjell her", tenkte Askeladden.
"Har du sedd p? utstyret ditt, gut? Kameraet ditt er da ein Nokia 3310. Dei kjem ikkje med panoramafunksjon", svarte Tuslingen som plutseleg kom p? at han kunne lese tankar.
Kva med ? dele opp ekvator i 360 delar? Ikkje dumt! D? kan vi byrja p? \(\phi_0 = 0^\circ\), ta eit bilete, flytte oss til \(\phi_0 = 1^\circ\) og ta eit bilete, osv. Sj? figuren nedanfor.
Men s? m? vi òg vite kor stort dette bilete skal vere. Heldigvis hadde Askeladden f?tt med seg eit d?mebilete av Reodor som han kan bruke som mal. S? her er det berre ? hive seg igang!
Som sagt s? m? vi fyrst vite kor stort dette d?mebiletet er. Det kan gjerast ved ? opne biletet i koda og s? lage ein array av sj?lve biletet. D? st?r vi med ei matrise som inneheld alle pikslane i biletet. Med ein funksjon som heiter Numpy.shape() kan vi finne storleiken av biletet i x- og y-retning, som viser seg ? vere h?vesvis 640 og 480 pikslar. Det er mange pikslar ? g? gjennom! Kvar og ein av desse pikslane skal vi nemleg bruke til ? finne RGB-verdiane til biletet vi skal ta, men det kjem vi tilbake til seinare. For dei som lurar st?r RGB for Red, Green, Blue, som er prim?rfargane.
Men f?r det m? vi rekne ut minimums- og maksimumsverdiane av x og y. Vi kjem ikkje langt med berre storleiken. Likninga for \(x_{max/min}\) og \(y_{max/min}\) hadde Askeladden kome fram til p? f?rehand i ein draum han hadde. Den ivrige matematikaren kan finne ei s?rs rask utleiing her.
\(x_{max/min} = \pm \frac{2 \sin(\alpha_{\phi}/2)}{1 + \cos(\alpha_{\phi}/2)} \\ y_{max/min} = \pm \frac{2 \sin(\alpha_{\theta}/2)}{1 + \cos(\alpha_{\theta}/2)}\)
I bruksanvisninga p? Nokia'n st?r det at \(\alpha_{\theta}=\alpha_{\phi}=70^\circ\) som er synsfeltet (field of view) til kameraet. Det er dette som er grensa til kvart enkelt bilete. Nokia'n er ikkje s? god at han kan ta eitt bilete av alt skj?nar du.
"Men akk og ve!", st?nna Tuslingen. "Dette gjev oss da eit vanleg flatt bilete. Korleis i reine skafte verd skal vi bruke dette til ? f? fram bilete av noko sf?risk? Himmelkula er sf?risk, Askeladden!"
Men s? positiv og roleg som Askeladden er s? var det enkelt ? ignorere bekymringane til Tuslingen. Askeladden hadde nemleg l?rt litt om stereografisk projeksjon like f?r dei la ned skulen i bygda. Denne teknologien vil f?re til at mannskapet ombord veit i hvilken retning skipet peker i. Fra den informasjonen kan man f? full kontroll over b?de hastighetsvektor og sikt for ? komme seg fram i det tre-dimensjonale rommet.
N?r Askeladden no tek eit bilete, vil det bilete han f?r vere flatt. Heng med s? langt? Flott! Dette flate biletet er ein s?kalla stereografisk projeksjon av himmelkula han tek bilete av, sj? figurane over. Men korleis veit kameraet kva for fargar som er i kvar piksel p? biletet? Det er det vi m? rekne ut! Vi m? omgjere kvar kartesiske koordinat \((x, y)\), alts? kvar piksel, i denne stereografiske projeksjonen til sf?riske koordinatar \((\theta, \phi)\), for s? ? hente ut RGB-verdiane for alle pikslane. Desse RGB-verdiane vil vi d? bruke for ? sette saman biletet. Merk at vi her driv i eit todimensjonalt system. Vi let sentrum av bilete vere i \(x = y = 0\). Koordinattransformasjonen fr? \((x, y)\) til \((\theta, \phi)\) blir d?
\(\theta = \theta_0 - \arcsin \left[\cos\beta \cos\theta_0 + \frac{y}{\rho} \sin\beta \sin\theta_0 \right] \\ \phi = \phi_0 + \arctan \left[\frac{x \sin\beta}{\rho \sin\theta_0 \cos\beta - y \cos\theta_0 \sin\beta} \right]\) ,der \(\rho = \sqrt{x^2 + y^2} \\ \beta = 2 \arctan \left(\frac{\rho}{2} \right)\).
Korleis kom Askeladden fram til denne, lurar du sikkert p? no. Dette var noko av det nyttige Tuslingen kom med ein sjeldan gong, s? dette m? Askeladden berre godta.
Dersom Askeladden lagar seg eit grid, eller nett som vi seier p? godt norsk, kan han no ved hjelp av koordinattransformasjonane gjere dette nettet om til eit sf?risk nett, hente ut RGB-verdiane i alle rutanen (pikslane) i dette nettet, for s? ? leggje dei til i biletet sitt.
D? er det berre for Askeladden ? dengje dette inn i furumaskina som han m?tte spikke ny Backspace-knapp til f?rre veke, og ...
... poof!
"Men kva i alle dagar", mumlar Askeladden i det han tek opp referansebiletet fr? Reodor og samanliknar det med det han nettopp fekk. "Tusling! Vi har eit problem!"
Biletet er feil veg! Kva skal Askeladden gjere no?
"Neimen, sj? d?r. N? pratar vi!", seier han plutseleg.
Tuslingen ser bort p? Askeladden som sit der med datamaskina opp og ned i fanget sitt.
"No veit eg det!", utbryt Askeladden. Modulen han brukar for ? produsere desse bileta er kalla PIL, ein slags modul spesifikt for bilete i Python. Kanskje inneheld den noko som kan snu bilete for han? Det gjer det! Ein funksjon kalla ImageOps som han kan importere har noko som heiter ImageOps.flip(). Her er det berre ? leggje til biletet og ... voila!
"Eg m? innr?mme at eg er s?rs kreativ til tider", seier Askeladden, tydeleg stolt over sin eiga innsats. "Det var ein enkel m?te ? ordne problemet p?. Nesten for enkelt. Eg har p? f?linga at dette sikkert kjem til ? kome attende som nok eit problem for meg seinare, men det er eit problem for framtidige meg. No er det kaffepause!"
Denne bloggposten tek til ? bli s?rs lang, s? da kan det kanskje vere lurt ? ta seg ei lita pause med noko godt i koppen.
Etter ei alt for lang kaffepause, ein liten blund og nokre lefserullar med spekeskinke teken fr? stabburet heime p? garden, hiv Askeladden seg inn i det vidare arbeidet med ny giv.
Han g?r n? eit steg vidare og set kameraet til ? ta bilete for alle \(\phi \in [0^\circ , 360^\circ]\). Det var jo det som var den originale tanken. Resultatet ser du i den nydelege videoen under, der du kan skimte 360 forskjellige bilete satt saman til ein liten video:
"D? var me endeleg ferdige med det", sa Askeladden og ga seg sj?lv ein klapp p? skuldra.
"Ferdig?", spurte Tuslingen forundra. "Kva meiner du med ferdig? Vi veit da ikkje kva for ei retning vi ser i p? bileta"
"Sj?lvsagt veit vi det!", svara Askeladden medan han tok opp eit av bileta. "Vi ser den vegen".
"Og kva for ein veg er det?"
"Den vegen"
"Kvar?"
"Dit"
Det er berrsynt at det er noko som manglar her. Det er berre Askeladden som ikkje vil innr?mme det, lat som han er.
Askeladden sat seg ned og f?lte seg tufsete og dom, men s? h?yrte han eit sus som over furukrona kom.
"Eg ga deg fleire referansebilete", sa suset med noko som likna veldig p? stemma til Reodor.
Tuslingen s?g seg fortusta rundt om p? skipet f?r han fekk auge p? datamaskina til Askeladden. Den hadde byrja ? vekse p? seg ei ny krone p? toppen av skj?rmen.
Med fleire referansebilete ? ta utgangspunkt i, kan vi ved hjelp av minste kvadraters metode g? over alle bileta og samanlikne dei med kvart enkelt referansebilete. N?r programmet finn ein match, eller fyrstikk som vi seier p? norsk, kan vi f? det til ? printe ut verdien til \(\phi\) som bileta matcha p?. La oss halde oss til ordet match, fyrstikk h?yrer ikkje heilt rett ut. Ved minste kvadraters metode tek vi ? minimaliserar skilnaden mellom ein modell vi har og dataa vi f?r. For ? finne den minste skilnaden tek vi dataa minus modellen og opph?gjer denne skilnaden i andre potens, derav namnet "minste kvadrat". Vi kvadrerar for ? f? absoluttverdien. Vi er ikkje interessert i forteiknet til skilnaden.
Og d? kjem det store sp?rgesm?let. KVA skal vi samalikne? Kva er det vi skal finne skilnaden mellom p? desse bileta? Kan du gjette deg fram til det? Du kan det nok. Njaaa, n?rmar deg n?. Nesten..... Yes! RGB-verdiane! Her er referansebileta modellen v?r, dei bileta vi tek med kameraet er dataa vi samlar inn, og RGB-verdiane er dei vi skal samanlikne.
Er ikkje det ein enkel sak? Jauda, men ikkje gl?ym at vi m? g? gjennom RGB-verdiane i kvar piksel... i kvart einaste bilete! Dette gjer vi ved ? f? programmet til ? ta utgangspunkt i det fyrste referansebiletet, lèt det g? over bileta vi tek og samanliknar. Og n?r det finn eit som har ein skilnad lik null i RGB-verdiane f?r vi programmet til ? spytte ut \(\phi\)-verdien, for s? ? ta neste referansebilete og byrje p? nytt.
Dette kjem nok til ? ta ei stund.
Men no st?ytar vi p? eit problem. Hugsar du ImageOps.flip()? Vi brukte det til ? koste problemet om at bilete vi fekk var opp og ned under teppet, men no har teppet plutseleg drege opp skj?rtet og g?tt sin veg. Og problemet ligg der n? og blottar seg p? skipsgolvet for alle ? sj?!
ImageOps.flip() viser seg ? fungere berre p? det ferdige produktet, alts? p? det ferdige biletet vi har laga. Og n? skal vi ikkje bruke biletet, men det det er bygd opp av, nemleg matrisa med alle RGB-verdiane, eller nettet med alle pikslane som inneheld alle RGB-verdiane er vel kanskje meir rett ? seie. Dette nettet blir ikkje snudd av flip'en v?r. Vi m? tenkje nytt.
Transponering av matriser! Det er noko dykk ikkje vil l?re f?r dykk er p? det store universitetet, men kort og godt handlar det om ? "snu" p? ei matrise. N? er det ikkje slik at vi snur matrisa opp og ned, men vi snur slik at vi f?r eit rett nett av pikslar til biletet. Slik kan Askeladden endeleg f? orden p? problemet sitt. Askeladden gjer s? dette, og endeleg er alt slik det skal vere. Eller er det? Time vil shj?vv.
Programmet k?yrer, Nokia'n dirrar som ein gammal Saab som har st?tt brisen i to timar, og ut blir det printa ein \(\phi\)-verdi som skal samsvare med det fyrste referansebiletet, \(\phi = 0\). No er det berre ? vente p? det neste, som tek ei god stund. Neste verdi blir utprinta! \(\phi = 20\), som skal samsvare med det andre referansebiletet. D? er det berre ? vente p? neste!
...
Men s? g?r det ei stund.
...
S? g?r det nok ei stund.
Plutseleg kjem det end? ei stund ? g?r forbi.
Etter at den fjerde stunda kjem tuslande forbi kahyttglaset, tenkjer Askeladden som s? at her m? det vere noko gale. Programmet k?yrer og k?yrer, men inga ny \(\phi\) dukkar opp. Askeladden kjem til bilete 240 f?r han gjev opp. Programmet klarer alts? ? matche dei to fyrste referansebileta, men ikkje det neste. Kva kan vere feil her tru? Askeladden pr?var seg fram med ? hoppe over referansebilete nummer tre og pluggar nummer fire direkte inn i programmet.
Og tida g?r...
... det tek si tid dette programmet her. Det er noko vi kan ta til etterretning. Programmet kan nok mest sannsynleg effektiviserast ein del, men det er det inga tid til akkurat no. Det ser heller ikkje ut til at det er noko bilete som vil matche med det fjerde referansebilete.
Askeladden gjev opp etter ? ha sedd gjennom nesten 300 av dei 360 bileta sine. "Dette er h?plaust", seier han, "men vi har da to \(\phi\)-verdiar! Det er meir enn nok synes eg!"
"Nja", svarar Tuslingen skeptisk, "men alle gode ting er tre".
"Her er litt tre", seier Askeladden medan han sagar av den nyvokste krona p? datamaskina og kastar den bort til Tuslingen.
Det er berrsynt at det er noko som ikkje stemmer i programmet. Etter at Tuslingen fekk overtala Askeladden til ? sj? over kodinga si ein gong til, som var ein s?rs tidkrevjande prosess som inneheldt b?de blod, svette og t?rer vel ? merke, fann Askeladden til slutt ut at noko m?tte vere gale med m?ten han samanliknar RGB-verdiane.
M?ten vi eigentleg tenkte ? samanlikne desse p? var ? plukke ut kvar enkelt av dei tre grunnfargane, og sj? om skilnaden til kvar enkelt var lik null. Det kan hende at det kanskje er eit for trangt n?lauge ? tre noko gjennom. Kanskje skilnaden i RGB-verdiane ikkje treng ? vere lik null, men berre vere s?rs liten for at bileta skal matche. Men om dei da ikkje er lik null, er bileta dei same?
Dette er sp?rsm?l stakkars Askeladden ikkje har tid eller hjernekapasitet til ? tenkje over no. Han og Tuslingen m? nemleg kome seg vidare f?r problema hopar seg opp. Det er ikkje berre kvar og kva dei ser dei m? finne ut, men òg kva for ein hastigheit dei har!
Kjelder:
[1] /studier/emner/matnat/astro/AST2000/h21/undervisningsmateriell/prosjektlop/prosjektdeler/part4.pdf