Image Compression Using Burrows-Wheeler Transform

Abstract

Tämän työn tarkoituksena on tutkia kuvan pakkausta Burrows-Wheelerin muunnosta käyttämällä. Kuvan tiivistämisessä tarkoituksena on tiivistää kuva muotoon, joka tallennetaessa saatetaan mahdollisimman pieneen tilaan, sekä nopeuttaa kuvan siirtämistä tietoliikenteen välityksellä. Burrwos-Wheeler muunnos perustuu annettuun datan uudelleenjärjestämiseen, niin että muunnoksen jälkeen data on helpompi pakata.

Ennen kuin voidaan käyttää Burrows-Wheelerin muunnosta, kuva pitäisi ensin esikäsitellä diskreettillä kosinimuunnoksellä, diskreettillä aallokemuunnosellä tai ennustuskoodauksellä. Tämän jälkeen 2D-kuvan pikseliit skannataan käyttämällä esilaisia skannausmenetelmiä, ja voidaan hyödyntää Burrows-Wheelerin menetelmällä.

Burrows-Wheelerin yhteydessä käytetään hyväksi esim. move-to-front ja run-length-koodaus menetelmiä ennen varsinaista entropiakoodausta, jotta kuva voitaisiin tiivistää mahdollisimman pieneen tilaan. Työssä tutkitaan sekä häviöllistä että häviötöntä kuvan pakkausta.

The purpose of this thesis was to study image compression using the Burrows-Wheeler transform. The aim of image compression is to compress the image into a format which saves the storage space and provides an efficient format for transmission via telecommunication channels. The Burrows-Wheeler transform is based on block sorting, which rearranges data into an easier format for compressing.

Before utilizing the Burrows-Wheeler transform, the image need to be pre-process by using a discrete cosine transform, a discrete wavelet transform or predictive coding. Then the image is converted from a 2-dimensional to a 1-dimensional pixel sequence with different scanning methods. The forward Burrows-Wheeler transform is applied on block of the image data.

While compressing the image into the smallest storage space, the move-to-front and run-length encoding can be used to improve the compression ratio before entropy encoding. This thesis studies both lossless and lossy image compression.