Kompresja obrazu wraz wraz z implementacją - przygotowania

2008-08-23 , Papiewski Łukasz , Programowanie / Kodzenie

UPDATE:Poniższe nabazgrałem parę lat temu przy implementacji projektu picpac. Jeszcze wisi na repozytoriach. Głównie mi to było potrzebne na polibudę ale projekt został sam przeze mnie wymyślony w ramach dowolnego wyboru.

Jest to pierwsza część artykuły poświęcona kompresji obrazu i projektu picpac. Kod powinien być na obecnym repozytorium

Dane graficzne w pamięci komputera przechowywane są jako tablice jedno bajtowe. Dlatego kompresja bezstratna obrazu wcale nie przyspieszy jego wczytywanie, ale wręcz przeciwnie może nałożyć na procesor dodatkowe obliczenia.

Jednakże jeżeli priorytetem jest miejsce na dysku czy przepustowość łącza internetowego, a nie szybkość otwarcia obrazu kompresja może być przydatna, a czasem nawet jak to pokazuje rzeczywistość niezbędna. Gdyż obraz to także filmy a bez takich formatów jak np. DivX w dzisiejszych czasach byśmy się nie obyli (bo kto by ściągał paro gigabajtowy film). Jednak niepozornie niewdzięczna i trochę przerastająca formę nad treścią kompresja w swej implementacji, jest zagadnieniem słusznym i ciekawym.

Poniżej mój wywód nad wyimaginowanym problem szukania dziury w całym, czyli niepotrzebnie zużytego miejsca w danych.

Niektóre swoje programy w swej prostocie (jak przykładowy MTPaint na systemie Linux) pomija całkowicie reprezentacje mniejszą niż jednego bajta. Domyślnie najmniejszą reprezentacją w formacie BMP jest tam 8 bitów na piksel. Skupiając się dalej na BMP należy zapamiętać, że każda linijka obrazu musi mieć co najmniej 4 bajty (taka jest specyfikacja) . Oznacza to że małe obrazki typu 8x8, 4x4, 1x1 piksela będą miały ten sam rozmiar w linijce:

Dla 1 bita na piksel:  
32x32  rozmiar = 32 x 4 bajty =128 bajty  
XXXXXXX XXXXXXXXX XXXXXXXX XXXXXXXX  
16x16 rozmiar = 16 x 4 bajty = 64 bajty 
XXXXXXXX XXXXXXXX UUUUUUUU UUUUUUUU ...  
8x8    rozmiar = 8 x 4 bajty = 32 bajty 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXXXXX UUUUUUUU UUUUUUUU UUUUUUUU  
4x4  rozmiar= 4 x 4 bajty = 16 bajtów 
XXXXUUUU UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXUUUU UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXUUUU UUUUUUUU UUUUUUUU UUUUUUUU 
XXXXUUUU UUUUUUUU UUUUUUUU UUUUUUUU  
2x2 8 bajtów 
XXUUUUUU UUUUUUUU UUUUUUUU UUUUUUUU 
XXUUUUUU UUUUUUUU UUUUUUUU UUUUUUUU  
1x1  1 bajt 
XUUUUUUU UUUUUUUU UUUUUUUU UUUUUUUU

Oczywiście poniżej 32x32 piksele monochromatyczne obrazki można poddać pedantycznej kompresji :)

Następny aspektem jest liczba kolorów, która logicznie rzecz ujmując jest uzależniona od tego ile miejsca (bitów) przeznaczyliśmy na piksel. Oczywiście najwydajniej przydzielić potęgi 2 na piksel nie np. 3 bit na piksel, (9 kolorów). Spowodowane jest to tym, że kompletnie nam to psuje wyłuskanie kolorów z bajta, czyli jednostki podstawowej dla procesora. W ogóle jak wcześniej wspomniałem problemy już są nawet dla potęg dwójki mniejszych od 8. Standard BMP w ogóle nie uwzględnia innych wielkości piksela niż potęga 2 (zaczynając od 1 kolejno mamy 2 4 8 16 32 64 128 itd.). Mapa koloru zapisana jest w kodowaniu BGR + 1 bajt.

Istnieje wiele technik kompresji. Chyba najbardziej znaną jest JPG, ale jest to bardzo trudny do implementacji algorytm, do tego jeszcze stratny co nie zawsze może być atutem. Skupiając się na sposobach bezstratnych należy wyróżnić RLE oraz kompresje Huffmana. 'Run Lenght Encoding' koduje powtarzające się wystąpienia bitów. Sprawdza się gdy np. mamy jakieś jednokolorowe tło. Warto zwrócić uwagę na to z której strony rozpoczynamy kompresje ( od góry, od dołu) , gdyż ma to wpływ na jej wydajność. Można sobie wyobrazić jednobitowe paski pionowe, które maja zerowy stopień kompresji, wręcz ujemny, gdy zaczniemy zliczać wystąpienia w kierunku poziomym. Rozwiązaniem jest przeprowadzenie wstępnej analizy (taka analiza może być dość rozbudowana) i dopasowania optymalnych algorytmów i ich wersji.

W algorytmie Huffman'a dzielimy obraz an pewne cząstki. Wręcz neizowna w tym wypadku analiza wstępna powinna ustalić z jaką wielkością obrazu mamy do czynienia, jak powinny wyglądać bloki podstawowe itp ). Niestety w większości wypadków taka analiza opiera się na algorytmie brute force, czyli serii kompresji i porównywania ich stopnia, i prostego wyboru najlepszej opcji.
Następnie takie bloki zostają poddane zliczaniu, a na podstawie posortowanej tablicy ilości ich wystąpień dokonujemy przekształcenia Huffmana. Opiera się ono na trywialnym fakcie, iż to co występuje najczęściej powinno zostać zakodowane krótszym znakiem.
Jakie trudności mogą wystąpić w przypadku dwóch powyższych kompresji w praktyce. Przede wszystkim dobór szybkiego algorytmu oraz posiadanie dość dobrej biblioteko operacji na bitach.

Zacznijmy od początku. Dokonujemy wczytania obrazu. Jak wiemy każdy jest zakodowany w jakimś określonym formacie. Dość łatwo możemy poradzić sobie z prostym wczytywaniem BMP - jego format jest dość prosty i logiczny, choć jak pokazało doświadczenie, możemy natknąć się na pewne niespodzianki w postaci obrazków czarno białych i zaokrąglania do 4 bajtów, czy też różnorakich tablic kolorów. Aby nie walczyć z wiatrakami, chyba że chcemy nabrać niebywałego 'skilla' w implementacji tak złożonych algorytmów, najlepiej jest skorzystać z bibliotek rozkodowujących dane formaty. W FLTK istnieją takie dodatki (mimo tego iż jest to sprzeczne z postanowieniem języka jak najbardziej prostego i serwującego tylko proste kontrolki) i możemy z nich śmiało skorzystać przy wczytywaniu i wyświetlaniu plików formatu BMP i Jpeg.

Obraz wyświetlany na monitorze ma także tzw. standard przechowywania w pamięci niezależnie od tego co wyświetlamy, czy jakie różnorakie formaty wszystko składa się tu z pikseli a te z czterech pól (R - natężenie koloru czerwonego, G - zielonego, B- niebieskiego oraz A - alpha czyli przezroczystość ). Po wczytaniu w FLTK, ale także przy wykorzystaniu różnorakich bibliotek graficznych, zazwyczaj do takich danych mamy dostęp. I w tym tutorialu tak będą reprezentowane nasze dane wejściowe do dalszej kompresji.

Po zastosowaniu algorytmu Huffmana, mamy dane jak należy zakodować każdy blok. Teraz należy to w prostej formie zapisać do pliku ( rożnej długości bity) oraz pomyśleć w jaki sposób można je rozkodować. Skąd mam wiedzieć, że ten plik właśnie jest zakodowany w ten a w ten sposób, przy wykorzystaniu takich to, a tkich bloków itd.

Jak przystało na nowy format kompresji należy umieścić w nagłówku wszystkie dane potrzebne do rozkodowania. Przede wszystkim należy powiadomić o tym, który blok odpowiada danemu kodowi. Innym sposobem jest przeprowadzenie odwrotnej kompresji Huffmana.

Aby się w tej całej złożoności zagadnień nie pogubić, przy implementacji naszego całościowego programu ze wszystkimi funkcjami rozpinającymi się pomiędzy graficznym interfejsem, wyświetlaniem obrazu, jego zmianą i modyfikacją, a następnie zapisem i odczytem proponowałbym utworzenie silnie obiektowych klas. Pozwoli to na dowolne ich dostosowywanie, zwłaszcza przy stylu programowania bottom-up. Wszystkie strukturalne podejścia przy objętości kodu powyżej 2 tysięcy linijek są niejako ciężkie do zarządzania oraz ulepszania.

Komentarze:(1)

< poprzednia strona | 1 | następna strona >

root w dniu 2012/03/30 o godz.22:47 : napisał :
hmm

Cytaty

- Simplicity is the ultimate sophistication. - Leonardo da Vinci,
- Popularny człowiek wzbudza zawiść potężnych - Thufir Hawat o Leto Atrydzie (na Kaladanie),
- Szczęście następuje po smutku, a smutek po szczęściu; człowiek jest naprawdę wolny, gdy przestaje rozróżniać między smutkiem a szczęściem, między dobrem a złem - Aforyzmy buddyjskie.