Úloha 042: Prediktivní bezeztrátová komprese monochromatického obrázku

Cílem je navrhnout co nejlepší bezeztrátovou kompresi monochromatického (šedotónového) rastrového obrazu (typicky 8 bitů na pixel). Vstupem je rastrový obraz (8bpp), výstupem binární soubor na disku.

Entropický kodek

Je k dispozici standardní algoritmus pro kanálovou (entropickou) kompresi: DeflateStream (Zlib) používaný pomocí našeho API IEntropyCodec. Třída, která Deflate algoritmus používá, se jmenuje DeflateCodec a je použita v pilotní implementaci PreCodec.cs. Případné lepší kanálové komprese si můžete implementovat (a dostat za to bonusové body, viz úloha 043entropycodec) např. podle modulů z JaGrLib:

adaptivní Huffmanovo kódování
LZW kodek (ten mám v plánu sám)
adaptivní aritmetické kódování - potřebuje navíc datovou strukturu kumulativního histogramu, např. CF-tree

Úkol

Musíte navrhnout vlastní kompresní algoritmus a vyzkoušet jeho bezeztrátovost - tj. implementovat kódování i dekódování. Celý kodek (kodér i dekodér) je implementován ve třídě PreCodec - v jediném zdrojovém souboru PreCodec.cs.
Ignorujte případné barvy vstupního obrázku, pixely převádějte na jasové hodnoty např. pomocí funkce Raster.Draw.RgbToGray(). Rozměry bitmapy spolu s magickým číslem MAGIC ukládejte do hlavičky vašeho formátu.

Metody k implementaci: EncodeImage() a DecodeImage().

Náměty

Měli byste použít prediktivní kompresi (1D nebo 2D), chybu prediktoru (reziduum) pak budete kódovat nějakým entropickým kodérem, přičemž využijete velmi nerovnoměrné PDF těchto dat.

Srovnání: komprese v PNG formátu nebo TIFF - LZW (jsou dost kvalitní, ale měli byste být schopni se s nimi aspoň řádově srovnat).

Aplikace

Pilotní program je připraven tak, že dokáže načíst libovolný vstupní rastrový obrázek, spustit kompresi, změřit velikost zakódovaného souboru a potom zpátky kód přečíst (dekódovat), a porovnat s originálem.

Termín

Odevzdat do: 4. 1. 2015

Body

Základ: 25 bodů
příp. prémie za vlastní entropický kodek nebo umístění v soutěži

Projekt

Visual Studio 2010 projekt: 042compressionpre

Zdrojový soubor

Modifikujte a odevzdejte soubor: PreCodec.cs
Do komentáře na první řádce napište své jméno!
Nezapomeňte alespoň stručně popsat metodu, kterou jste vymysleli.

Testovací data

V repository jsou dva vhodné obrázky - masa512g.png a santa.png (ten druhý neodpovídá přesně specifikaci, je jenom černobílý), další obrázky pro testování: janssen-19111g.png (533x400), kodim07sg.png (465x375)