Basis av bilder
For ? snakke om og analysere bilder, er det kanskje greit ? vite noen standard ting om bilder f?rst. Jeg snakket ikke noe s?rlig om dette i forrige innlegg fordi jeg ikke tenkte det var kjempebehov for det der, men det er litt viktigere i dette innlegget. Et bilde er bygget opp av piksler, se for deg bitte-bittesm? firkanter som ligger p? for eksempel pc-skjermen eller mobilen din. Vi teller antall piksler langs X-aksen og Y-aksen, og skriver bildest?rrelsen som X x Y. For eksempel kan vi ha et 300 x 120 bilde, som tilsvarer et rektangul?rt bilde som har st?rre bredde enn h?yde, dvs. 300 piksler bortover, og 200 piksler oppover. Alle disse sm? pikslene er det som til sammen danner bildet du ser p? skjermen, i alle farger og detaljer.
Ja, hva med farger? Hver piksel har en verdi for enten r?d, gr?nn, eller bl? fargeverdier, som sier noe om hvor mye av den fargen som ligger i pikselen. Disse verdiene kan ligge mellom 0 eller 255, som sammen som en kombinasjon skal gi fargen i pikselen. Ofte er det representert i en tuppel, der f?rste verdi er r?d, andre er gr?nn, og siste er bl?, alts? RGB, eksempelvis som (255, 153, 51) (som blir denne fargen). Alts? vil en kombinasjon av disse kunne gi oss alle fargene vi ser og trenger (siden hver R, G, eller B kan v?re 256 ulike tall, finnes det \(256^3 = 16\;777\;216 \) forskjellige farger vi kan lage p? denne m?ten!).
Ekstra snacks: For de av dere som kan litt bin?re tall, s? ser dere at vi kan skrive 256 ulike tall i to-tallsystemet (0, 1) dersom vi bruker 8 tall (f.eks \(000000000_2=0_{10}\), \(00000001_2 = 1_{10}\), \(00000010_2 = 2_{10}\), ..., \(10011010_2 = 154_{10}\), ..., og \(11111111_2=255_{10}\)), alts? \(2^8\) ulike kombinasjoner, som betyr 8-bits tall. Siden fargeverdiene g?r fra 0-255 uten negative fortegn eller desimaler er det akkurat 256 tall, og vi kan representere fargedata med uint8 (unsigned integer 8-bits) som kan bli nyttig senere n?r vi jobber med bilder. Dersom vi gj?r det sparer vi mye lagringsplass i forhold til dersom vi skulle representert fargeverdiene som float64, dvs. 64-bits flyttall, som ville v?rt un?dvendig siden vi ikke trenger s? mye plass til ? lagre disse tallene.
Hvordan sammenlikner man bilder?
Det finnes mange metoder for ? sammenlikne bilder, men vi har tenkt til ? bruke en metode som benytter seg av bildene vi allerede har tatt, og som vi har v?rt litt borti f?r her p? bloggen da vi skulle se p? Radiell hastighetskurve. Vi skal bruke noe som kalles minste kvadraters metode, som er en metode som skal gi oss den beste sannsynligheten for at bildet vi bruker til ? sammenlikne med er det riktige bildet. Vi kan utlede metoden fra statistikk, og dermed se at minste verdi i minste kvadraters metode skal gi best sannsynlighet. Jeg skal ikke utlede den her, men ideen eller essensen bak minste kvadraters metode er at dersom vi ikke kan finne en eksakt l?sning for det vi er ute etter med dataen vi har, skal vi finne det settet med data som minimerer feilen vi har.
V?re bilder fra verdensrommet
Ideen i v?rt tilfelle er at vi skal se hvor like fargeverdiene mellom bildene er, alts? ser vi p? hvor like RGB-verdier hver piksel i bildene vi sammenlikner er. Dermed bruker vi minste kvadraters metode p? RGB-verdiene i hver piksel. S? gj?r vi noe lurt: vi legger sammen minste kvadrater av hver piksel i gridet og tar et gjennomsnitt. P? denne m?ten maksimerer vi f?rst sjansen for at RGB-verdien i hver piksel mellom bildene stemmer, ogs? f?r vi ett tall som representerer likheten gjennom hele bildet. Dette gj?r vi for hvert eneste bilde av de 360 bildene vi genererte fra forrige innlegg, ogs? finner vi hvilken grad \(\phi_0\) bildet er sentrert rundt, slik at vi vet hvilken retning bildet er tatt i. Siden vi genererte et bilde for hver grad \(\phi_0 = 0^\circ, 1^\circ,2^\circ,\dots,359^\circ\) kan vi laste dem inn i en array i rekkef?lge, og dermed vil indeksen i arrayen ogs? fortelle oss hvilken grad \(\phi_0\) bildet er blitt tatt i. Gj?r vi det p? denne m?ten har vi ogs? mulighet til ? gjennomf?re minste kvadraters metode p? alle bildene samtidig, og trenger dermed kun ? gj?re det én gang.
For ? bruke analogien om arrays fra Rakettmotor - boks for boks om array som en slags skuff/arkivskap med inndelinger, kan vi tenke oss at vi i stedet for med v?re pinglete, enkle, veike menneske-armer plukker ut én og én ting fra arkivskapet, bruker Numpy en slags superblekksprut med 360 armer til ? plukke ut bildedataen fra skuffen samtidig (eller i l?pet av superkort tid: i programmeringslingo kaller vi det vektorisering), og kj?re minste kvadrater for oss for og s? pent legge det tilbake igjen pent strukturert. P? denne m?ten kan programmet vi skal lage kj?re fortere enn dersom vi m?tte kj?rt minste kvadraters metode 360 ganger. Merk at p? grunn av inndelingen \(\phi_0\) har vi begrenset med vinkeloppl?sning, og svaret vi f?r er kun en approksimasjon, og ikke n?dvendigvis en eksakt l?sning.
Minste kvadraters metode for bilder kan skrives som:
\(\begin{align*} \Delta = \sum_{i}^3(P_{i} - P_{ref,i})^2 \end{align*}\)
der \(P\) er en piksel i bildet vi har tatt, \(P_{ref}\) er en piksel i et av referansebildene vi fikk fra forrige innlegg, og summasjonsindeksen er over RGB-verdiene, dvs. at \(i = 1,2,3\)hvor f.eks \(P_1\) da svarer til R-verdien og \(P_3\) svarer til B-verdien i den ene pikselen vi m?ler i bildet vi skal finne beste approksimasjon til. Vi kan tenke p? det som et slags avvik mellom to verdier, som vi kvadrerer slik at det blir positivt (og noen flere grunner). Det ville v?rt dumt om verdiene nullet hverandre ut, ta dette eksempelet: Vi m?ler fra et punkt som konstant er 0 og ut til to m?linger som er p? 4, og -4. Summerer vi differansen uten kvadrater f?r vi \(\Delta = 4 - 0 -?4 - 0 = 0\). Vi har ogs? to andre m?linger p? 1 og 2, som vil summere til vil vi f? \(\Delta = 2 - 0 + 1 - 0 = 3\). Men m?lingene p? 1 og 2 er jo n?rmere 0 enn m?lingene p? 4 og -4? Dermed blir ikke dette et riktig bilde. Kvadrerer vi inne i summen ville vi f?tt \(\Delta = (4 - 0)^2 +?(-4 - 0)^2 = 16+16=32\), og \(\Delta = (2-0)^2 + (1-0)^2 = 4 + 1 = 5\) i stedet, som gir et riktigere bilde av m?lingene. Da ville ogs? kun m?linger tatt i 0 og 0 gitt \(\Delta = 0\).
Dersom vi skal ha et gjennomsnitt av \(\Delta \) i alle pikslene i bildet, m? vi summere opp minste kvadrater p? hver piksel over hele gridet og dele p? st?rrelsen til bildet. Formelen for ? gj?re dette blir da:
\(\begin{align} \overline{\Delta} = \frac{\sum\limits_{i}^X\sum\limits_{j}^Y\sum\limits_{k}^3(P_{k} - P_{ref,k})_{ij}^2}{X\cdot Y} \end{align}\hspace{1cm}(1)\)
der \(X\) er antall piksler i "x-retning" av bildet og \(Y\) er antall piksler i "y-retning" av bildet. Dermed blir \(X\cdot Y\) st?rrelsen til bildet, alts? totalt antall piksler. I v?re bilder husker vi fra forrige innlegg at vi hadde bildest?rrelser p? 640 x 480, dvs. \(X = 640\) og \(Y=480\). Vi kan oppsummere hva vi har tenkt s? langt:
- Vi laster inn alle 360 referansebilder vi tok i forrige innlegg, og laster dem inn i en array i rekkef?lge fra 0-359. Arrayen vil da inneholde alle RGB-verdiene til hver piksel til alle 360 bilder.
- Vi laster inn bildet vi ?nsker ? approksimere mest sannsynlige \(\phi_0\) bildet er sentrert rundt.
- Vi bruker minste kvadraters metode p? RGB-verdiene mellom referansebildene og bildet vi lastet inn. Dermed finner vi snittverdien av det minste kvadratet for hele bildet, og dette gj?r vi for alle 360 bildene ved hjelp av likning (1).
- Vi finner det bildet som hadde minste snitt \(\overline{\Delta}\), og hvilken indeks den hadde i arrayen med alle referansebildene. Siden vi var lure sist og delte inn i grader \(\phi_0=0^\circ,1^\circ,\dots 359^\circ\) vil indeksen i arrayen ogs? v?ret graden \(\phi_0\) bildet ble tatt i (approksimert), og dermed har vi svaret vi ?nsker.
Med dette i tankene skriver vi et program som gj?r nettopp dette, og vi er klare til ? kj?re en test og avduke hvilke resultater vi f?r!
Bildeavduking, resultater og diskusjon
Fra forrige innlegg husker jeg at jeg sa meg forn?yd med at bildet fra satellitten og referansebildet vi genererte ser like ut. Jeg l?y. Det er ikke tilfredsstillende i det hele tatt, og ikke helt vitenskapelig heller. Dermed benytter jeg f?rste muligheten her n? til ? teste programmet p? bildet vi samplet fra satellitten og bildet vi genererte. Forh?pentligvis f?r vi et resultat som sier \(\overline{\Delta} = 0\), med tanke p? at begge bildene skal v?re sentrert om samme vinkel \(\phi_0=0\). Vi ruller film, og plotter noen resultater:
Dette plottet ser bra ut. Vi vet at bildet fra satellitten ble tatt p? \(\phi_0=0\), og verdiene fra plottet sier at \(\overline{\Delta}=0\) der \(\phi_0=0\), som betyr at alle RGB-verdiene i begge bildene er like n?r vi bruker referansebildet sentrert om \(\phi_0=0\). Vi f?r ogs? returnert at bildet fra satellitten ble tatt med \(\phi_0=0\), som vi tross alt allerede vet, men likevel kjekt ? se at den verdien kommer ut (ville v?rt bekymret om noe annet kom ut). I tillegg ser vi at \(\Delta \) dupper av mot slutten der \(\phi_0\) n?rmer seg \(359^\circ\), som gir mening siden vi nesten er tilbake til \(\phi_0=0^\circ\). Dette vil jo skje med alle bilder som er sentrert p? en \(\phi_0=0^\circ,1^\circ,\dots,359^\circ\), fordi vi har referansebilder som er generert med n?yaktig disse verdiene. Vi pr?ver ? generere et bilde til p? en desimal vinkel som ikke allerede finnes i arrayen med referansebilder, s? la oss pr?ve ? generere et bilde som er sentrert om en vinkel \(\phi_0 = 323.67^\circ\). Vi kj?rer dette inn i koden v?r, og f?r dette plottet:
?
Dette plottet ser ogs? greit ut, og verdiene vi f?r returnert er \(\overline{\Delta} = 10.47\) og \(\phi_0 = 324^\circ\), som er n?rmeste hele grad til \(\phi_0 = 323.67^\circ\), alts? en grei approksimasjon. Vi legger ogs? merke til at \(\overline{\Delta}\) minker n?r vi n?rmer oss riktig verdi, som gir mening med tanke p? at bildet blir likere og likere rundt beste approksimasjon. Slik kunne vi hold p? med evig mange \(\phi_0\) (og det har jeg da programmet kj?rte for f?rste gang), men jeg sier det er nok med testing av ulike \(\phi_0\) i dette innlegget (for n?). I stedet ?nsker jeg ? vise litt mer visuelt hva som skjer her n?r vi bruker minste kvadrater.
En litt mer visuell fremstilling
??????Vi kan pr?ve ? visualisere p? noen andre m?ter ogs?. La oss bruke \(\phi_0 = 234.8^\circ\). Vi f?r fra programmet at \(\overline{\Delta} = 3.27\) og \(\phi_0 = 235^\circ\), slik at det er p? plass. Bildet vi har generert ser slik ut:
med et \(\overline{\Delta}\)-plot som ser slik ut:
Veldig greit. Det vi derimot kan lese av er at den st?rste verdien for \(\overline{\Delta}\) er p? \(\phi_0 = 32^\circ\)(jeg zoomet skikkelig langt inn p? plottet lzzm). Hvordan ser forskjellen mellom verste og beste approksimasjon ut n?r vi regner er? Hvis jeg bare viser deg hvordan bildene der vi har brukt minste kvadraters metode p? hver piksel, ser man kanskje bedre hva som er forskjellen mellom en god og en d?rlig tiln?rming.
Siden vi tar en forskjell i verdien p? RGB og kvadrerer det, betyr det at lave verdier er piksler der RGB har v?rt like p? alle tre. For eksempel \(\sum[(122, 225, 81) - (120, 231, 79)]^2 = \sum(2, -6, 2)^2 = \sum(4,36,4) = 44\), som ville sl?tt ut som lilla p? plottene i figur 4 og figur 5. H?ye verdier tilsvarer veldig ulikt p? alle tre RGB-verdier, og p? midten kan det v?re noen som trekker de andre opp/ned etc.
Litt diskusjon p? tampen - forrige innlegg og dette innlegget
I dette innlegget har vi ikke gjort mange antakelser eller approksimasjoner, men det er like vel noen ting vi kan snakke om. Det f?rste vi kan snakke om er vinkeloppl?sningen p? referansebildene, som begrenser hvor n?yaktige vinkler vi kan finne. Med m?ten vi har gjort det p? f?r vi opp til n?rmeste grad, som betyr at st?rste avviket vi kan ha fra en vinkel er \(0.5^\circ\). Dersom vi skal reise 1AU (snittavstanden mellom sola og jorda n?r jorda har gjort et oml?p rundt sola, 1AU=149598073km) med en vinkelfeil p? \(0.5^\circ\)kan vi med enkel trigonometri sette opp en likebent trekant og bruke cossinus-setningen (\(a^2 = b^2 + c^2 - 2bc\cos(A)\), der \(A\) er vinkelen p? motsatt side av lengden \(a\)), og finne ut at vi har havnet en avstand \(\sqrt{2\cdot(149598073\text{km})^2 - 2\cdot(149598073\text{km})^2\cdot\cos(0.5^\circ)} \approx 1\;305\;485\text{km}\) unna den opprinnelige kursen, som betyr at vi er skikkelig p? avveie. Dette kan man minimere ved ? ha flere m?linger med mindre vinkel mellom. For eksempel kan vi m?le hver \(0.1^\circ\) slik at vinkelavviket er maksimalt \(0.05^\circ\), som betyr at vi m? ta 10x antall bilder, men vi vil ogs? bare f? ca. \(\frac{1}{10}\) av lengden feil, dvs. ca \(130\;548\text{km}\).
I tillegg gjorde vi en antakelse i forrige innlegg: himmelbildet er konstant. Det er bare tiln?rmet sant dersom vi gj?r dette i en kort nok tidsperiode. Dersom vi hadde tatt referansebildene og s? ventet en laaang tid, ville jo himmelbildet faktisk ha endret seg, og vi kunne ikke brukt referansebildene til ? gj?re denne analysen. Vi m?tte alts? ha hentet ny data, slik at vi kunne sammenlikne igjen. Dette blir ikke noe problem for oss.
En annen ting vi ogs? b?r passe p? er antakelsen om vi kan bruke minste kvadraters metode. Det g?r som regel greit, men det er et par forutsetninger med den som vi ikke har g?tt gjennom her som fort kunne gjort at vi f?r merkelige resultater.
En siste m?ling - meningen bak alt v?set jeg n? har rablet og bablet om
Som avslutning p? det hele skal jeg gj?re det vi nettopp egentlig kom hit for: vi skal finne ut hvilken retning vi faktisk peker! *snufs* blir emosjonell av ? tenke p? at dette innlegget snart er slutt. Vi bruker romsonden p? raketten v?r og genererer et siste bilde, og resultatet blir f?lgende:
programmet spytter ut en \(\phi_0 = 270^\circ\)og en \(\overline{\Delta} = 0\), s? ganske n?yaktig \(\phi_0=270^\circ\) med andre ord! Jeg sender dette resultatet videre med dere til Johan, som skal gj?re noe helt annet!