Wszystkie pliki zrodlowe, troche zabalaganione, znajduja sie tutaj:
http://dl.dropbox.com/u/2545858/lzw.zip
Cel.
Ogolna idea naszej dzialalnosci, napiszmy funkcje im2fd(), ktora musi:
-wczytac obrazek w odcieniach szarosci z pliku i zapamietac jego wymiary,
-przeksztalcic z macierzy odcieni szarosci na wektor,
-przeksztalcic z wektora odcieni szarosci na wektor znakow 8-bit char,
-skompresowac wektor znakow char algorytmem lzw,
-utworzyc plik do ktorego zapisze rozmiary obrazka i otrzymany kod z kompresji lzw.
Skoro bedziemy mieli funkcje im2fd, przyda sie tez fd2im(), ktora musi:
-wczytac z pliku ktory jest efektem dzialania funkcji im2fd rozmiar obrazka i kodo z kompresji lzw,
-zdekodowac kod z kompresji lzw na wektor znakow char,
-przeksztalcic z wektora znakow char na wektor odcieni szarosci,
-przeksztalcic z wektora odcieni szarosci na macierz dwuwymiarowa korzystajac z wczytanych wymiarow obrazka.
-zapisac otrzymana macierz odcienia szarosci jako obraz do pliku.
Cel jest jasny i prosty.
Plan.
Zaprojektujmy w takim razie funkcje im2fd:
void im2fd(string imagefile, string output) {
IMAGE= imageread(imagefile); %wczytac obrazek
SIZE= size(IMAGE); %wczytac jego rozmiary
IMAGE= m2v(IMAGE); %macierz -> wektor
IMAGE= int2char(IMAGE); %konwesja na wetkor char
CODE= lzw_encode(IMAGE); %kompresja
TOFILE= vector_concatenate(SIZE,CODE); %przygotowanie danych do zapisu: polaczenie wektora rozmiaru obrazka z wektorem kodu z kompresji
filewrite(output,TOFILE); %zapisanie do pliku output
}
Rozbilismy im2fd na kroki postepowania i kazdemu przypisalismy funkcje. Przerobienie takiego ideowego pseudokodu na dzialajacy kod w Matlabie, jest raczej banalne:
%pcygan 09.11.2011
% in -> out: str, str -> void
% purpose: compress imagefile using lzw algorithm and write generated code to output text file
function im2fd(imagefile,output)
disp(['Loading image: ' imagefile]);
IMAGE= imread(imagefile); %wczytac obrazek
PREIMAGE= IMAGE;
disp('Reading image size.');
[rows_ cols_]= size(IMAGE); %wczytac jego rozmiary
disp(['Image size: ' num2str(rows_) 'x' num2str(cols_)]);
disp('Image vectorization.');
IMAGE= IMAGE(:)'; %macierz -> wektor
[o p]= size(IMAGE);
disp(['Data vector size is: ' num2str(o) 'x' num2str(p)]);
disp(['Max value: ' num2str(double(max(IMAGE))) ', min value: ' num2str(double(min(IMAGE)))]);
disp('Converting int2char');
IMAGE= char(IMAGE); %konwesja na wetkor char
disp('Coding image.');
CODE= lzw_encode(IMAGE); %kompresja
disp(['Code size' num2str(size(CODE))]);
disp('Code generated.');
disp(['Saving to file ' output '.']);
FILE= fopen(output,'w');
%przygotowanie danych do zapisu: polaczenie wektora rozmiaru obrazka z wektorem kodu z kompresji + zapisanie do pliku
fprintf(FILE,num2str([rows_ cols_ double(CODE)]));
fclose(FILE);
disp('Save ok!');
imshow(PREIMAGE);
end
Bedziemy schludni i dodamy odrobine komentarzy, zeby po czasie gdy wrocimy do kodu, bylo latwiej go ogarnac. Ponadto dopisalismy troche wypisywania wiadomosci na konsole. :) Wszystkie funkcje dostepne sa w Matlabie, oprocz lzw_encode, ktora napiszemy sami.
lzw_encode
Jak mozemy sie dowiedziec z Wikipedii, pseudokod algorytmu kodowania LZW przedstawia sie nastepujaco:
1. Wypełnij słownik alfabetem źródła informacji.
2. c := pierwszy symbol wejściowy
3. Dopóki są dane na wejściu:
Wczytaj znak s.
Jeżeli ciąg c + s znajduje się w słowniku,
przedłuż ciąg c, tj. c := c + s
Jeśli ciągu c + s nie ma w słowniku, wówczas:
wypisz kod dla c (c znajduje się w słowniku)
dodaj ciąg c + s do słownika
przypisz c := s.
4. Na końcu wypisz na wyjście kod związany c.
W prosty sposob zaimplementujemy to w Matlabie, jako zapisanie (niemal) wprost pseudokodu w kod:
%pcygan 11.2011
%in->out: char vector -> int vector
%purpose: compress string(char vector) DATA using lzw algorithm and save compressed code in CODE (int vector)
%example:
%octave:33> lzw_encode('abrakadabra!')
%ans =
%
% 98 99 115 98 108 98 101 257 259 34
%
function CODE= lzw_encode(DATA)
DICT= lzw_initDict();
m= length(DATA);
c= DATA(1); %char
CODE= [];
%TODO HANDLE 1-ELEMENT OR 2-ELEMENT DATA
for i= 2:m
%get s char
s= DATA(i); %char
%if c + s is in dict
if lzw_findInDict(DICT,[c s])
c= [c s];
else
CODE= [CODE lzw_findInDict(DICT,c)];
c= [c s];
DICT= [DICT {c}];
c= s;
end
end
CODE= [CODE lzw_findInDict(DICT,c)];
end
Pozostaja dwie funkcje do zdefiniowania:
-lzw_initDict(), odpowiedzialna za inicjalizacje slownika.
-lzw_findInDict(), odpowiedzialna za wyszukiwanie stringu w slowniku i zwracanie jego indeksu (badz 0 w przypadku gdy nie ma w slowniku).
Inicjalizacja slownika polega na wypelnieniu go alfabetem danych. W naszym przypadku, alfabetem danych jest zasieg 8-bitowej zmiennej char, poniewaz taki jest nasz Cel. Daje nam to 256 mozliwych znakow. Kod w Matlabie jest krotki i prosty, z jednym malym 'ale':
%pcygan 11.2011
%in->out: void->char vector
%purpose: create 1:256 char table containing all possible char values
function DICT= lzw_initDict()
DICT= {0:255};
for i=1:256
DICT(i)= {char(i-1)};
end
%disp(DICT)
end
Ale polega na sposobie w jakim przechowujemy slownik. Przechowujemy jakby wskazniki na dane, zamiast samych danych - dlatego ciagi znakow w slowniku moga miec rozna dlugosc, co jest konieczne zeby algorytm zadzialal. Zwroc uwage na klamry '{' i '}' zamiast '[' i ']' w DICT.
Chemy, zeby lzw_findInDict(dict,str) zwrocila indeks wystapienia stringu str w slowniku dict lub 0 w przypadku, gdy nie wystepuje. Szukanie najprosciej zrobic jako porownywanie kazdego elementu slownika z szukanym stringiem i zwroceniem wartosci indeksu w razie sukcesu:
%pcygan 11.2011
%in->out: vector of strings, string->integer
%purpose: find whether string STR(char vector) is in dictionary(strings vector) DICT, if is, return it's index, if is not, return 0
function INDEX= lzw_findInDict(DICT,STR)
INDEX= 0;
[n m]= size(DICT);
for i=1:m
if strcmp(STR,DICT(i))
INDEX= i;
return;
end
end
end
Mamy teraz wszystko co jest potrzebne zeby nasza funkcja im2fd zadzialala. :)
fd2im
Teraz zrealizujemy drugi cel, jakim jest funkcja odwrotna do im2fd. Postepujemy analogicznie jak poprzednio - najpierw plan (ktory pomine), potem implementacja glownej funkcji fd2im, nastepnie implementacja funkcji 'skladowych'.
%pcygan 09.11.2011
% in -> out: str -> void
% purpose: read output lzw_file generated using im2fd function and create image
function fd2im(lzw_file)
disp(['Opening lzw .txt file: ' lzw_file '.']);
FILE= fopen(lzw_file);
disp('Copying data to memory.');
code= str2num(fread(FILE, '*char')');
disp('Closing file.');
fclose(FILE);
disp('File closed.');
rows_= code(1);
cols_= code(2);
disp(['Image size is: ' num2str(rows_) 'x' num2str(cols_)]);
[m n]= size(code);
code= code(3:n);
[m n]= size(code);
disp(['Code size is: ' num2str(m) 'x' num2str(n)]);
data= double(lzw_decode(code));
[o p]= size(data);
disp(['Data vector size is: ' num2str(o) 'x' num2str(p)]);
disp('Recovering matrix from vector by image size.');
data= v2m(data,rows_,cols_);
[r s]= size(data);
disp(['Data size is: ' num2str(r) 'x' num2str(s)]);
imshow(data,[0,255]);
disp(['Decompressed image size is: ' num2str(o*p) ', should be: ' num2str(rows_*cols_) '.']);
end
fd2im dziala odwrotnie jak im2fd, wiec nie ma sie tu nad czym zbytnio rozwodzic. Wyjasnienia wymagaja tylko dwie funkcje: v2m i lzw_decode. v2m jest banalne, poniewaz zamienia wektor w macierz:
%%
%AUTHOR
%%
% pcygan 2011.10.28
%%
%DECLARATION INPUT -> OUTPUT
%%
% VECTOR, ROWS_, COLS_ -> MATRIX[ROWS_,COLS_]
%%
%PURPOSE
%%
% CREATE MATRIX X EQUAL TO MATRIX M FROM VECTOR V,
% WHEN VECTOR V WAS CREATED FROM MATRIX M: V= M(:)
% THIS FUNCTION REVERSE OPERATION M(:)
% V= M(:), X= v2m(V,M_rows,M_columns);
% X == M -> true, after MATRIX X IS EQUAL TO MATRIX M.
%%
%EXAMPLE
%%
% $in$ F= [1 2 3 4; 5 6 7 8]
% $out$
% F =
%
% 1 2 3 4
% 5 6 7 8
% $in$ [rows_ cols_]= size(F)
% $out$
% rows_ = 2
% cols_ = 4
% $in$ F= F(:)
% $out$
%
% F =
%
% 1
% 5
% 2
% 6
% 3
% 7
% 4
% 8
% $in$ v2m(F,2,4)
% $out$
% ans =
%
% 1 2 3 4
% 5 6 7 8
function MATRIX= v2m(VECTOR,r,c)
MATRIX= ones(r,c); %preallocate memory for better performance
m= length(VECTOR); %remember VECTOR's number of rows
i= 0; %set starting variables
j= 1;
for it=1:m %iterate through VECTOR
i= i+1; %increment row pointer
if i > r %if row pointer is greater restored matrix* then number of rows
i= 1; %then reset row pointer to first row
end
%copy data from VECTOR(it) to proper position in MATRIX
MATRIX(i,j)= VECTOR(it);
if mod(it,r) == 0 %this mean we went through restored matrix column
j= j+1; %so increment column pointer
end
end
end
% *restored matrix is M in %EXAMPLE
Troche duzo kodu, a dowiedzialem sie ostatnio, ze nie musialem deklarowac nowej funkcji, bo wystarczylo zamiast niej napisac (:
MATRIX(:)= VECTOR;
Natomiast lzw_decode to juz inna bajka:
%pcygan 11.2011
%in->out: int vector->char vector
%purpose: decode char string(char vector) DATA from CODE (int vector). we assume CODE was generated using LZW compression algorithm
%example:
%octave:34> lzw_decode(lzw_encode('abrakadabra!'))
%ans =
%
% abrakadabra!
%
function DATA= lzw_decode(CODE)
DICT= lzw_initDict();
pk= CODE(1);
k= 1;
[n m]= size(CODE);
DATA= DICT{pk};
for i= 2:m
%wczytaj kod k
k= CODE(i);
%ciag skojarzony z poprzednim kodem
pc= DICT{pk};
%jezeli slowo o kodzie k jest w slowniku
[o p]= size(DICT);
if k <= p
tmp= DICT{1,k};
pc= [pc tmp(1)]; %dodaj do slownika pc + slownik[k][0]
DICT= [DICT {pc}];
DATA= [DATA tmp]; %na wyjsciu wypisz slownik[k]
else
pc= [pc pc(1)];
DICT= [DICT {pc}];
DATA= [DATA pc];
end
pk= k;
end
end
