Wydział Fizyki, Matematyki i Informatyki
Instytut Informatyki

Zakład Grafiki Komputerowej i Obliczeń Wysokiej Wydajności

Grafika Komputerowa

wykład 11:

Formaty plików rastrowych
Budowa przykładowego pliku

rastrowego (bmp)

Formaty grafiki rastrowej

BMP (Bit MaP) - format BMP jest standardowym formatem

bitmap w środowisku Windows i w systemie OS/2. Po
rozejściu się firm Microsoft i IBM powstały osobne standardy.
Zachowując pliki w „starym” formacie, istnieje możliwość wyboru
głębi bitowej koloru od 1, 4, 8 lub 24 bitów. W „nowym”
formacie kolor zapisywany może być w systemie RGBA (tu: BGRA
- 32 bity). W trybach poniżej 8 bitów występuje paleta kolorów.

Zapis obrazu zawiera informację o kolorze, a następnie obszar

danych pikseli opisywanych od lewego dolnego do prawego
górnego rogu.

W przypadku obrazów BMP można skorzystać z bezstratnej

kompresji Run-Length-Encoding (RLE). Wersja 5 została
wyposażona w możliwość obsługi kompresji stosowanej w JPEG i
PNG.

Zaletą tego formatu jest fakt, iż jest on rozpoznawany przez

wszystkie wersje systemu Windows. Podstawową wadą są duże
rozmiary plików.

Grafika komputerowa

– wykład 11

Do kompresji grafiki szczególnie nadaje się algorytm RLE (Run-Leght
Encoding). Jeśli znak (lub w tym przypadku wartość piksela) powtórzy
się więcej niż trzy razy z rzędu, to jest zapisywany tylko ten znak i
liczba powtórzeń. Można objaśnić to na przedstawionym schemacie.
Łańcuch danych do przetwarzania:
DDDDDDBBNNNNKKKKKOOO
po skompresowaniu:
6^DBB4^N5^KOOO
Przed znakiem ^ pojawia się liczba powtórzeń piksela o danej wartości.
W przytoczonym przykładzie oszczędność miejsca sięga 30%.
Algorytm jest wysoce efektywny w stosunku do obrazów o dużych
obszarach wypełnionych jednolitą barwą, a szczególnie o długich
ciągach poziomych pikseli.

Kompresja RLE

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

Kompresja RLE (Run Length Encoding)

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

GIF (Graphics Interchange Format) - definiuje protokół, który

umożliwia niezależną sprzętowo transmisję grafiki on-line. GIF
składa się z sekwencji bloków, wśród których można
wyróżnić 3 grupy: kontrolne, informacyjne oraz specjalne.

• Bloki kontrolne (np.: nagłówek czy opis ekranu logicznego)

zawierają informacje dla ustawienia parametrów sprzętu.

• Bloki informacyjne, np.: opis obrazu i rozszerzenie tekstowe,

mieszczą dane używane do wyświetlenia obrazu na ekranie
komputera.

• Bloki specjalne, np.: komentarze i rozszerzenie aplikacyjne,

służą jedynie ogólnej informacji.

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

GIF (Graphics Interchange Format)
Zaletami formatu są małe rozmiary plików oraz możliwość

obsługi przez wszystkie przeglądarki internetowe. Nadaje się do
publikacji grafiki w Internecie (w tym tworzenia obrazów
animowanych). Mimo swego podeszłego wieku wciąż cieszy się
popularnością, chociaż jest ostatnio wypierany przez animacje
Flasha. Umożliwia zastosowanie przezroczystości oraz interlacing
(przeplot).

Nie ma on jednak możliwości wykrywania błędów. Głębia barw

ograniczona jest do 8 bitów (256 kolorów). Paleta kolorów może
być optymalizowana. Do 2006 roku licencjonowany, ponieważ
obrazy są kompresowane bezstratną metodą LZW. Dlatego
stworzono konkurencyjny format PNG.

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

GIF (Graphics Interchange Format)

Obraz w formacie GIF (kolor 8-bitowy) i JPEG (kolor 24-bitowy)

Grafika komputerowa

– wykład 11

Nazwa algorytmu LZW pochodzi od pierwszych liter nazwisk jego
autorów: Jacob Ziv, Abraham Lempel i Terry A.Welch. Pierwsza wersja
algorytmu pochodzi z 1977 roku i znana jest jako LZ77. Rok później
pojawił się nieco zmieniony algorytm LZ78. Po publikacji w 1984 roku
przez Terrego Welcha praktycznej realizacji LZ78, algorytm otrzymał
ostateczna nazwe LZW. W pliku GIF stosowana jest jego
implementacja o nazwie Variable Length Code LZW.
Uwaga: Algorytm LZW jest chroniony patentem.
Właścicielem patentu jest firma Unisys Corporation. Od 1995 roku
producenci, którzy chcą sprzedawać oprogramowanie, używające
algorytmu LZW do przetwarzania danych muszą mieć licencję od
Unisys Corporation i licencja ta jest płatna. Zwolnieni od opłat są tylko
użytkownicy końcowi i organizacje nie komercyjne.

Kompresja bezstratna
LZW

Grafika komputerowa

– wykład 11

Idea algorytmu LZW jest stosunkowo prosta i polega na zastępowaniu
znalezionych ciągów danych specjalnymi kodami. W trakcie
przeglądania zbioru wejściowego program zapamiętuje w tablicy (lub
innej strukturze danych) znalezione ciągi danych i odpowiadające im
kody. Algorytm jest jednoprzebiegowy i nie wymaga zapisu tablicy z
kodami do zbioru wynikowego.
W zależności od konkretnej implementacji, algorytm może operować
na bajtach bądź na danych o innej długości. Taka elastyczność ma
szczególne znaczenie przy kompresji grafiki, w której opis jednego
piksela może być kodowany różną ilością bitów.

Kompresja LZW

Grafika komputerowa

– wykład 11

Wraz ze wzrostem ilości danych wejściowych rośnie wielkość tablicy
z sekwencjami danych. Dzięki temu rośnie także
prawdopodobieństwo, wzrostu stopnia kompresji kolejnych porcji
danych. Implementacja algorytmu LZW musi uwzględnić możliwość
przepełnienia się tablicy oraz koniec danych.

Kompresja LZW

Grafika komputerowa

– wykład 11

Podczas procesu dekompresji danych, program odtwarza tablice
kodów na podstawie odczytanych danych. Do poprawnego odczytu
dekompresor musi znać największy możliwy kod danych oraz kody
specjalne.

Dekompresja przeprowadzana jest w oparciu o kody zawarte w
tabeli i prowadzi do uzyskania ciągu analogicznego z
wejściowym.

Dekompresja danych

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

TIFF (Tagged Image File Format) – został opracowany do druku

postscriptowego. Znajduje zastosowanie w wymianie plików
między aplikacjami i platformami komputerowymi. Jest czytany
przez większość systemów operacyjnych.

Format TIFF może posługiwać się algorytmem kompresji

bezstratnej LZW. Oparty jest on na koncepcji tagów, które
dostarczają informacji na temat obrazu (typ kompresji, rozmiar,
kolejność bitów oraz autor, data i oprogramowanie
źródłowe). TIFF 5.0 definiuje 45 tagów. Ze względu na wysoką
jakość obrazu TIFF jest używany w poligrafii, fotografii,
profesjonalnym przetwarzaniu i analizie obrazu. Jego podstawową
wadą jest duży rozmiar plików.

W przypadku zastosowania pewnych metod kompresji mogą

występować trudności z rozpoznawaniem przez różne programy
graficzne.

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

PNG (Portable Network Graphics - "ping") – elastyczny,

przenośny format opracowany jako alternatywa dla standardu
GIF. Nie zawiera żadnych rozwiązań patentowanych.

Podobnie jak GIF, jest on używany do wyświetlania obrazów na

stronach WWW i w serwisach interaktywnych. Jest niezależny od
platformy. PNG zawiera pełną informację o kolorze (do 48 bitów);
w celu zmniejszenia rozmiaru plików posługuje się algorytmem
kompresji bezstratnej DEFLATE, który łączy LZ77 i kodowanie
Hufmanna, co zapewnia wydajniejszą kompresję niż GIF.

Jego zaletą jest pełna kontrola poprawności pliku i trójstopniowa

korekcja błędów.

Wyświetlanie może odbywać się z przeplotem w obu kierunkach,

co daje lepszy efekt niż jednokierunkowy przeplot w formacie GIF.

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

PNG (Portable Network Graphics - "ping")
PNG nie daje możliwości zastosowania animacji. Umożliwia za to

wyświetlanie

barw

o

zadanym,

dowolnym

stopniu

przezroczystości oraz dodatkowych informacji o obrazie. Jego
wadą jest brak obsługi przez niektóre przeglądarki. Uwzględnia
także korekcję gamma.

Plik PNG składa sie z serii bloków (chunk). Po bloku PNG file

signature, który rozpoczyna plik PNG, obowiązkowo występują:
IHDR (nagłówek), IDAT (dane obrazu) oraz IEND (zakończenie).
Wszystkie pola liczbowe w pliku PNG zapisywane są w
układzie Big-Endian, czyli poszczególne bajty zapisywane są od
najstarszego do najmłodszego.

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

Kompresja LZ77

Algorytm LZ77 jest metodą bezstratnej kompresji słownikowej,

opracowanej w 1977 roku przez Abrahama Lempela i Jacoba
Ziva. Opiera się on na zasadzie, iż poszczególne słowa lub ich
fragmenty powtarzają się w danym tekście. W słowniku jest
zatem zapamiętywana pewna liczba ostatnio kodowanych
danych, następnie w przypadku powtórzenia się jakiegoś ciągu
znaków, jest on zastępowany dwiema liczbami, z których
pierwsza określa jego pozycję w słowniku, a druga długość
ciągu.

Grafika komputerowa

– wykład 11

Kodowanie Huffmana

Dla danego zbioru symboli S = {x

1

, …, x

n

} istnieje zbiór

stowarzyszonych z nim prawdopodobieństw P = {p

1

, …, p

n

}.

Symbolami są najczęściej bajty, lecz mogą nimi być np.: pary znaków.
Prawdopodobieństwa mogą zostać z góry określone dla danego
zestawu

danych,

np.:

poprzez

wyznaczenie

częstotliwości

występowania znaków w tekstach danego języka. Częściej jednak
wyznacza się je indywidualnie dla każdego zestawu danych.
Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów
bitowych), których długość jest odwrotnie proporcjonalna do
prawdopodobieństwa p

i

. Tzn. im częściej dane słowo występuje (może

wystąpić) w ciągu danych, tym mniej zajmie bitów.

Kompresja JPEG

Grafika komputerowa

– wykład 11

Kodowanie Huffmana

Własności kodu:
• kod Huffmana jest kodem prefiksowym - żadne słowo kodowe nie
jest początkiem innego słowa;
• jeśli prawdopodobieństwa są różne, tzn. p

j

> p

i

, to długość kodu dla

symbolu x

j

jest nie większa od kodu dla symbolu x

i

;

• słowa kodu dwóch najmniej prawdopodobnych symboli mają równą
długość;
• dwa najdłuższe symbole różnią się tylko jednym, ostatnim bitem.
Kompresja polega na zastąpieniu symboli otrzymanymi kodami.

Kompresja JPEG

Grafika komputerowa

– wykład 11

Drzewo Huffmana

A

0.1

Mamy symbole A,B,C,D
o prawdopodobieństwach
wystąpienia odpowiednio [0.1,
0.2, 0.3, 0.4].

Łączymy węzły odpowiadające
symbolom (A) i (B). Teraz
mamy (A + B) = 0.3, (C) =
0.3, (D) = 0.4

B

0.2

C

0.3

D

0.4

A

0.1

B

0.2

C

0.3

D

0.4

0.3

A

0.1

B

0.2

C

0.3

D

0.4

0.3

Łączymy węzły
odpowiadające drzewku (A +
B) oraz (C). Teraz mamy ((A
+ B) + C)=0.6 i (D) = 0.4

0.6

Grafika komputerowa

– wykład 11

Drzewo Huffmana

A

0.1

B

0.2

C

0.3

D

0.4

0.3

Łączymy węzły
odpowiadające drzewku ((A
+ B) + C) oraz (D). Teraz
mamy tylko jeden wolny
węzeł - drzewko (((A + B) +
C) + D) = 1.0
Obliczamy kody znaków:
A = lewo, lewo, lewo= 000
B = lewo, lewo, prawo = 001
C = lewo, prawo = 01
D = prawo = 1

0.6

1.0

0

1

0

0

1

1

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

JPEG (Joint Photographic Expert Group) - umożliwia

zastosowanie stratnej kompresji danych o regulowanym stopniu.
Algorytm zastosowany w formacie JPEG opiera się o DCT
(Discrete Cosinus Transformation). Przy wyborze wysokiego
poziomu kompresji pliki mają niewielkie rozmiary, co umożliwia
ich publikację na stronach www. Są odczytywane przez wszystkie
przeglądarki. Podstawową wadą jest pogorszenie jakości obrazu
(różnice na granicach bloków, zakłócenia na granicach obszarów)
przy dużym stopniu kompresji oraz brak przezroczystości.

Format pozwala na zapis plików o rozdzielczości barw do 24

bitów (16,7 mln kolorów) w systemach CMYK i RGB, nadaje się
zatem do prezentacji zdjęć i obrazów ciągłotonalnych. Nie
zapewnia dobrych efektów w przypadku koloru 1-
bitowego oraz obrazów zawierających wyraźne linie czy granice
między obszarami.

Grafika komputerowa

– wykład 11

JPEG jest

najpowszechniejszym algorytmem kompresji obrazów.

Wiele rozwiązań tu zastosowanych jest używanych także w innych
algorytmach.

Kolejne kroki algorytmu JPEG to:
• zamiana przestrzeni kolorów z RGB na kanał jasności i dwa kanały
koloru. Ludzie znacznie dokładniej postrzegają drobne różnice jasności
od drobnych różnic barwy, a więc użyteczne jest tutaj użycie różnych
parametrów kompresji. (Krok nie jest obowiązkowy)
• obniżenie rozdzielczości kanałów koloru, zwykle odrzuca się co drugą
wartość wzdłuż osi poziomej, i każdą na pionowej, choć możliwe są też
inne ustawienia. Tak radykalne cięcie danych nieznacznie wpływa na
jakość, ponieważ rozdzielczość postrzegania kolorów przez ludzkie oko
jest słaba. (Krok nie jest obowiązkowy)

Kompresja JPEG

Grafika komputerowa

– wykład 11

• Podzielenie każdego kanału obrazka na bloki 8x8. W przypadku
kanałów kolorów, jest to 8x8 aktualnych danych, a więc zwykle
16x8.
• Transformata kosinusowa każdego z bloków. Zamiast wartości
pikseli mamy teraz średnią wartość wewnątrz bloku oraz
częstotliwości zmian wewnątrz bloku, obie wyrażone przez liczby
zmiennoprzecinkowe. Transformata DCT jest odwracalna, więc na
tym etapie nie ma utraty żadnych danych.
• Zastąpienie średnich wartości bloków przez różnice wobec
wartości poprzedniej. Poprawia to w pewnym stopniu współczynnik
kompresji.
• Kwantyzacja, czyli zastąpienie danych zmiennoprzecinkowych
przez liczby całkowite. To właśnie tutaj występują straty danych.
Zależnie od parametrów kompresora, odrzuca się mniej lub więcej
danych. Zasadniczo większa dokładność jest stosowana do danych
dotyczących niskich częstotliwości niż wysokich.
Kompresja algorytmem bezstratnym, w tym przypadku algorytmem
Huffmana.

Kompresja JPEG

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

Kompresja JPEG

Grafika komputerowa

– wykład 11

Kompresja JPEG

Typowe zakłócenia wynikające z algorytmu kompresji JPEG –
widoczne nieciągłości pomiędzy poszczególnymi blokami pikseli

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

Kompresja JPEG

Kompresja ze
współczynnikiem
jakości 0% - 2 kB

Kompresja ze
współczynnikiem
jakości 10% - 3 kB

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

Kompresja JPEG

Kompresja ze
współczynnikiem
jakości 50% - 8 kB

Kompresja ze
współczynnikiem
jakości 100% - 48 kB

Grafika komputerowa

– wykład 11

Formaty grafiki rastrowej

Opcje

BMP

GIF

PNG

JPEG

Liczba

kolorów

(bity)

24

8

48

24

Przezroczysto

ść

NIE

TAK

(jest-nie ma dla

kolorów)

TAK

(256 stopni dla

każdego piksela)

NIE

Przeplot/

Progresja

NIE/NIE

TAK/NIE

TAK/TAK

NIE/TAK

Animacja

NIE

TAK

NIE

NIE

Kompresja

NIE

(z małym wyjątkiem)

TAK

(bezstratna, LZW)

TAK

(bezstratna, LZ77)

TAK

(stratna)

Rozmiar pliku

BARDZO DUŻY

ŚREDNI

MAŁY

BARDZO MAŁY

Zastosowanie

Zdjęcia do dalszej

obróbki

Ozdobniki graficzne,

przyciski, bannery

Ozdobniki graficzne,

przyciski

Zdjęcia do prezentacji

w Internecie

Grafika komputerowa

– wykład 11

Optymalne formaty grafiki rastrowej dla publikacji na

stronach www

Obiekt graficzny Cechy charakterystyczne

Optymalny format

Banery reklamowe Animacje z napisami, niewielką liczbą

kolorów

GIF 32 kolory

Przyciski,

odnośniki

Napisy, różna liczba kolorów

W zależności od cech:
GIF, JPG 40% jakości

Animacje

Średnia liczba kolorów, mała

rozdzielczość

GIF

Galerie

internetowe

Duża liczba kolorów, łagodne przejścia

tonalne, wysokie rozdzielczości

JPG 40% - 50%

Miniatury
(thumbnails)

Duża liczba kolorów, niskie

rozdzielczości
funkcja podglądu

GIF, JPG 30% jakości

Tła

Mała liczba kolorów

GIF

Tła

Duża liczba kolorów, mała jakość

JPG 20% - 40%

Grafika komputerowa

– wykład 11

Budowa pliku rastrowego na przykładzie

formatu BMP

Nagłówek pliku BMP (BITMAPFILEHEADER) zajmuje 14
bajtów:

— bfType/usType - pole identyfikacji rodzaju pliku ( „BM”),
— bfSize/cbSize - liczba określająca długość pliku (w
bajtach),
— bfReserved1/xHotspot oraz bfReserved2/yHotspot –
każdorazowo po cztery bajty zarezerwowane i nie używane
w bitmapach (wartość 0),
— bfOBits/oBits - liczba określająca położenie obszaru
danych względem początku pliku.

Grafika komputerowa

– wykład 11

Budowa pliku BMP

Struktura BITMAPCOREHEADER (w starym formacie BMP,
bezpośrednio po nagłówku, zawiera informacje o obrazie
zapisanym w pliku):

— bcSize/cbFix - liczba zawierająca wielkość struktury
(definicja wersji; w starej wersji wartość ta wynosi 12),
— bcWidth/cx - liczba określająca szerokość obrazu (w
pikselach),
— bcHeight/cy - wysokość obrazu (w pikselach),
— bcPlanes/cPlanes - liczba określająca ilość płatów
urządzenia docelowego, wartość 1,
— bcBitCount/cBitCount - liczba bitów na piksel obrazu,
dopuszczalne wartości to: 1, 4, 8 i 24.

Grafika komputerowa

– wykład 11

Budowa pliku BMP

Struktura BITMAPINFOHEADER (w nowym formacie BMP,
bezpośrednio po nagłówku, tylko dla Windows):

— bcSize - liczba zawierająca wielkość struktury (numer
wersji);
w „nowym” formacie BMP dla Windows wynosi 40,
— bcWidth - liczba określająca szerokość obrazu (w
pikselach),
— bcHeight - wysokość obrazu (w pikselach),
— bcPlanes - ilość płatów urządzenia docelowego (wartość
1),
— bcBitCount - ilość bitów na piksel obrazu (1, 4, 8, 16, 24
lub 32),
— biCompression – sposób kompresji obrazu:
0 - brak kompresji,
1 - kompresja RLE8 (ang. Run Length Encoding 8-Bits),
2 - kompresja RLE4 (ang. Run Length Encoding 4-Bits),
3 - brak kompresji,
4 - obraz jest w formacie JPEG,
5 - obraz jest w formacie PNG;

Grafika komputerowa

– wykład 11

Budowa pliku BMP

Struktura BITMAPINFOHEADER (c.d.):

— biSizeImage - liczba określająca wielkość obszaru danych
obrazu (w bajtach),
— biXPelsPerMeter – rozdzielczość pozioma obrazu (w
punktach na metr),
— biYPelsPerMeter – rozdzielczość pionowa (w punktach na
metr),
— biClrUsed - liczba określająca, ile kolorów z mapy kolorów
jest wykorzystywanych w obrazie (0, gdy wykorzystywana jest
cała mapa kolorów),
— biClrImportant - liczba określająca, ile kolorów wystarcza,
aby możliwie poprawnie wyświetlić obraz zawarty w pliku.

Grafika komputerowa

– wykład 11

Budowa pliku BMP

Mapa kolorów
„Stary format”:
Mapa kolorów składa się z trzybajtowych struktur nazywanych
w Windows RGBTRIPLE (trójka RGB). Struktury te
zawierają definicje składowych barw w układzie BGR
(niebieski, zielony i czerwony).
Mapa ta nie występuje w obrazach o głębokości bitowej
koloru24.
„Nowy” format:
Każda pozycja mapy kolorów opisywana jest czterobajtowymi
strukturami nazywanymi w Windows RGBQUAD. Struktury te
zawierają
definicje składowych barw w układzie BGRA (niebieski, zielony,
czerwony oraz nieużywany atrybut).
Jeżeli pole biClrUsed struktury BITMAPINFOHEADER jest
większe od zera, to jego wartość wyznacza ilość definicji
kolorów zawartych
w mapie kolorów. W przeciwnym wypadku o wielkości mapy
kolor decyduje ilość bitów na piksel. Mapa kolorów nie
występuje w obrazach o głębokości bitowej barwy 16, 24 i 32.

Grafika komputerowa

– wykład 11

Budowa pliku BMP

Dane obrazu
W pliku BMP po palecie kolorów następuje obszar danych
poszczególnych pikseli obrazu. Piksele są zapisywane
wierszami od najniższego do najwyższego i w kolejności od
lewej do prawej, zatem lewy dolny róg obrazu jest zapisany na
początku obszaru danych, a prawy górny - na końcu.

Kolejne wersje plików BMP (4 oraz 5) zawierają odpowiednio
struktury
BITMAPV4HEADER oraz BITMAPV5HEADER, które pojawiają się
bezpośrednio po nagłówku pliku (BITMAPFILEHEADER). Dają
one nie tylko możliwość zastosowania korekcji gamma dla
poszczególnych kanałów koloru, ale także zapisu barwy w
niezależnym sprzętowo systemie CIE XYZ.

Grafika komputerowa

– wykład 11