Most recent comments
Liveblogg nyttårsaften 2017
Tor, 11 months, 2 weeks
Jogging og blogging
Are, 1 year, 11 months
Liveblogg nyttårsaften 2016
Are, 1 year, 11 months
Reading in dark times
Are, 2 years
Moldejazz 2016
Camilla, 2 years, 4 months
Dørskilt
Karoline, 2 years, 5 months
Halifax
Tor, 2 years, 5 months
Sony Smartwatch 3 review
Tor, 2 years, 6 months
Numerikk, takk
Tor, 2 years, 6 months
Topp tur
Camilla, 2 years, 8 months
50 book challenge
Camilla, 11 months, 2 weeks
Five years ago
Endelig \(\LaTeX\)-støtte
Tor
Controls
Register

Jpeg-komprimering

Her en dag gjorde jeg en øving i Numerisk fysikk, som gikk ut på å gjøre noe som heter wavelet compression. Det var egentlig meningen at vi skulle bruke noe som heter DAUB4 wavlets, men jeg aner ikke hva det er, og når jeg slo det opp så det ut som noe som ville ta mer enn to minutter å sette seg inn i, så jeg brukte bare FFT, og satser på at det er noe av det samme.

FFT står for Fast Fourier Transform. Det går ut på at man tar en funksjon, eller man kan kalle det et signal, og finner ut hvilke frekvenser det består av. Alle kontinuerlige funksjoner kan nemlig skrives som en uendelig sum av sinuser og cosinuser, og fouriertransformasjon går da ut på å finne koeffisientene til disse bølgene. Akkurat hva den medfølgende FFT-rutinen til Python gjør, er jeg ikke helt sikker på, men det som kommer ut er i alle fall en liste med koeffisienter som inneholder like mange datapunkter som signalet hadde i utgangspunktet.

Disse koeffisientene vil variere i størrelse, og det er åpenbart slik at små koeffisienter har mindre å si for signalet enn store. Komprimeringen går derfor ut på å hive alle koeffisienter som er mindre enn for eksempel 0.5% av den største koeffisienten. Med mindre signalet ditt er hvitt støy, vil dette kunne gi ganske ok kompresjon, og et ganske ok resultat når du gjør invers FFT på de gjenværende koeffisientene.

Etter at jeg hadde gjort dette, begynte jeg å tenke litt, og jeg innså at det må være slik jpeg-komprimering funker. Jeg har nemlig alltid lurt på det, skjønt jeg har ikke lurt nok til å slå det opp. Men det forklarer i alle fall hvor jpeg-artifacts kommer fra.

Jeg satte med derfor ned i dag, og skrev et program som henter ut kanalene fra et bmp-bilde, gjør FFT på dem, hiver de minste koeffisientene, og lagrer alle de andre i en txt. Og så skrev jeg et program til, som henter ut tallene fra tekstfilen, og setter det sammen til en bmp igjen. Til venstre kan man se bildet jeg tok utgangspunkt i for å teste, og til høyre er resultatet etter konvertering tilbake. Hvis man sammenligner med kurvene i artikkelen om fourier-rekker er det ganske lett å se likheten, vil jeg si.



Dessverre, på grunn av at jeg lagrer koeffisientene med ganske mange siffer, blir den komprimerte txt-filen faktisk større enn det opprinnelige bildet. Det kunne jeg nok fikset ved å definere filformatet bedre enn å bare skrive ut koeffisientene direkte, men det gidder jeg ikke. Det er jo prinsippet som er poenget, og det føler jeg at jeg har skjønt. For den som måtte være interessert ligger de to programmene her. De har ikke kommentarer, og er sikkert litt uleselige. Det programmet som heter jpeg.py tar en fil som heter test.bmp, og putter resultatet i en fil som heter testbildezip.txt. Programmet som heter antijpeg.py leser fra txt-filen, og skriver til et bilde som heter testjpg.bmp.

Det kreves at man har Python Imaging Library installert.

-Tor Nordam

Comments

B,  02.06.08 01:06

Oh my! You fast fourier transformed my cat!

Tor,  02.06.08 14:24

Er det virkelig ingen som synes dette er spennende og funky? Makan til gjeng, sier jeg bare.

Christer,  02.06.08 20:47

Apropos fouriertransformerte katter (fin xkcd-referanse forresten!): Her har dere faktisk en!







(Fra denne siden.)