Podstawy Informatyki II

Projekt 1 – Grafika wektorowa (wersja Acrobat Reader projekt.pdf)

Celem projektu jest skonstruowanie szkieletu aplikacji pozwalającej na tworzenie grafiki wektorowej w sposób zbliżony do popularnych programów typu CorelDraw, Adobe Illustrator, Shockwave Flash, czy AutoCAD. Grafika wektorowa w przeciwieństwie do grafiki rastrowej, gdzie obraz zapamiętywany jest w postaci siatki pikseli zawierającej kolor każdego piksela w postaci składowych RGB, do opisu obrazu wykorzystuje bardziej złożone obiekty postaci linia, wielokąt, elipsa, itp. (patrz rys. 1).

Rys. 1. Wektorowy obraz twarzy wyrysowany przy pomocy pięciu elips

Takie rozwiązanie pozwala na znaczną redukcję długości plików przy jednoczesnych zachowaniu poziomu szczegółowości, wystarczającym w wielu przypadkach do przekazania niezbędnej informacji. Państwa zadanie zakłada oczywiście pewne uproszczenia i koncentrować się będzie jedynie na konstrukcji szkieletu umożliwiającego przechowywanie składowych obiektów obrazu oraz wykonywanie na nich prostych przekształceń. Do wspomnianych uproszczeń należą:

Rysunki mają być wyswietlane w trybie tekstowym*,
Do grupy obiektów składowych obrazu zaliczamy: punkt, linię, kwadrat i elipsę,
Należy zaimplementować jedynie przykładowe operacje typu skalowanie, odbicie w pionie czy w poziomie.

Aplikacja powinna zawierać dodatkowo obiekty:

Obraz, służy do przechowywania wszystkich obiektów wchodzących w skład grafiki wektorowej,
Ekran, zawiera wynik otrzymany po wyrysowaniu wszystkich obiektów. W realizowanym przypadku będzie to oczywiście tablica znaków,
Przekształcenie, pozwala na wykonywanie wspomnianych operacji na elementach składowych obrazu.

Użytkownik programu powinien mieć możliwość dodawania do obrazu nowych obiektów oraz definiowania ich parametrów, a także możliwość przyłączania i odłączania od obiektów już istniejących, wybranych przez siebie przekształceń. Ponadto należy użytkownikowi umożliwić zapis obrazu w postaci tekstu opisującego obiekty składowe i przyporządkowane im przekształcenia oraz w postaci zrzutu ekranu tekstowego. Wraz z programem należy oddać sprawozdanie, którego szablon będzie wkrótce dostępny.

*Dla osób zainteresowanych udostępniam bibliotekę do wizualizacji obrazów w trybie graficznym.

Biblioteka graficzna

Dla osób zainteresowanych wyświetlaniem obrazów w trybie graficznym proponuję specjalną bibliotekę, która udostępnia funkcje rysujące obiekty typu: punkt, linia, wielokąt oraz elipsa. Obiekty te wyrysowywane są w automatycznie otwierającym się oknie aplikacji Windows API. Poniżej znajduje się dokładny opis dostępnych funkcji oraz przykładowy program rysujący „twarz” (z rysunku 1).
Opis funkcji:


void UstawRozmiar(int szer, int wys);

Funkcja ustala szerokość (szer) i wysokość (wys) części okna przeznaczonej do rysowania.


void Czysc(KOLOR k);

Funkcja czyści okno zapisując jego zawartość jednolitym tłem w zadanym kolorze k, gdzie KOLOR to struktura definiowana jako


struct KOLOR 

{ 
int         red;

int         green;

int         blue;
};

i zawierające składowe RGB koloru.


void ZmienNazwe(string nazwa);

Funkcja ta ustala nazwę okna podaną jako obiekt klasy string.


void UstawPunkt(int x, int y, KOLOR k);

Funkcja rysuje piksel w punkcie o współrzędnych x i y i w zadanym kolorze k.


void RysujElipse(int x0, int y0, int x1, int y1, KOLOR k_ramki, KOLOR k_tla);

Funkcja rysuje elipsę o kolorze wypełnienia k_tla oraz kolorze ramki k_ramki, wpisaną w prostokąt opisany za pomocą współrzędnych górnego lewego rogu (x0, y0) oraz prawego dolnego rogu (x1, y1).


void RysujWielokat(int liczba, PUNKT* punkty, KOLOR k_ramki, KOLOR k_tla);

Funkcja rysuje wielokąt w kolorze wypełnienia k_tla i ramce w kolorze k_ramki, opisany za pomocą punktów (wierzchołków), których współrzędne zapisane są w liczba- elementowej tablicy punkty obiektów typu PUNKT


struct PUNKT

{
int         x;

int         y;
};


void RysujLinie(int x0, int y0, int x1, int y1, KOLOR k);

Funkcja rysuje linię w kolorze k od punktu o współrzędnych (x0, y0) do punktu (x1, y1).

Biblioteka graficzna składa się z trzech plików, które muszą się znaleźć w katalogu tworzonego projektu.
Okno.h – plik nagłówkowy, który należy dołączyć do pliku aplikacji za pomocą dyrektywy #include ”Okno.h”.
Okno.o – plik ten należy dołączyć do projektu poprzez zakładkę: Projekt -> Opcje projektu -> Parametry -> Dodaj plik.
wndcon.ovl – plik aplikacji okienkowej Windows API.

Przykładowe programy i pliki biblioteki graficznej:


#include <cstdlib>

#include <iostream>

#include <conio.h>

#include "Okno.h"



using namespace std;



int main(int argc, char *argv[])

{

KOLOR szary, zolty, niebieski;

Okno          okno(256, 256, "Aplikacja przykladowa - Twarz");

szary.red     = 220; szary.green     = 255; szary.blue     = 220; 

zolty.red     = 255; zolty.green     = 255; zolty.blue     = 128;

niebieski.red = 128; niebieski.green = 128; niebieski.blue = 255;

okno.Czysc(szary);

okno.RysujElipse(32,  32,  224, 224, niebieski, niebieski);

okno.RysujElipse(64,  160, 192, 196, zolty, zolty);

okno.RysujElipse(64,  140, 192, 176, niebieski, niebieski);

okno.RysujElipse(64,  64,  96,  128, zolty, zolty);

okno.RysujElipse(160, 64,  192, 128, zolty, zolty);

system("PAUSE");

return EXIT_SUCCESS;

}

Listing 1. Kod programu Twarz.

Biblioteka: Biblioteka.rar
Program "Twarz": Twarz.rar
Program "Fraktal": Fraktal.rar

Projekt 2 – Kodowanie Huffmana (wersja Acrobat Reader projektII.pdf)

Kodowanie Huffmana polega na zastępowaniu symboli występujących w strumieniu wejściowym specjalnymi sekwencjami bitów stanowiących tzw. słowa kodowe. Słowa kodowe dobiera się w taki sposób, by najkrótsze z nich przyporządkować symbolom najczęściej występującym w strumieniu wejściowym, a najdłuższe symbolom o najniższych częstotliwościach wystąpień. Ponadto żadna sekwencja bitów nie może być przedłużeniem innej, co zapewnia jednoznaczność pomiędzy reprezentacją naturalną a zbiorem danych przedstawionym w postaci zakodowanej. Dzięki swej konstrukcji kody Huffmana znajdują szerokie zastosowanie w bezstratnej kompresji danych, w szczególności tam, gdzie występują znaczne różnice pomiędzy częstotliwościami wystąpień symboli, a słaba korelacja pomiędzy sąsiednimi elementami wyklucza użycie metod słownikowych. Stąd kody Huffmana stosuje się powszechnie w formatach kompresji obrazu i dźwięku, np. JPEG, MPEG oraz MP3.

Klasyczny algorytm wyznaczania słów kodowych bazuje na drzewie binarnym. Załóżmy, że w strumieniu wejściowym występują 8-bitowe liczby całkowite, tzn. dane typu „unsigned char”. Niech przykładowy ciąg symboli do zakodowania przyjmie następującą postać:

aaaabbccaaaaccbbaddaaaaaaabbbbcccaaaaaabbbb
Wówczas:

Zliczamy częstotliwości wystąpień poszczególnych symboli tworząc tzw. las, w którym każde drzewo (tutaj posiadające tylko jeden węzeł) zawiera jeden symbol oraz wagę będącą liczbą wystąpień danego symbolu. Ponieważ w naszym przykładzie litera a wystąpiła 22 razy, b 12 razy, c 7 razy oraz d 2 razy, to wspomniany las przyjmie postać:

Następnie z lasu utworzonego w punkcie 1 wybieramy dwa drzewa o najniższych wagach i łączymy je, tworząc nowe drzewo o wadze będącej sumą wag drzew składowych. Operację tę powtarzamy aż do uzyskania jednego drzewa. Dla naszego przykładu mamy:

unsigned char

Następnie dla każdego symbolu wyznaczamy słowo kodowe, będące ścieżką od korzenia do liścia zawierającego dany symbol, przy czym przejściu w lewo przyporządkowujemy bit '0' a przejściu w prawo bit '1'. W naszym przykładzie po przyjęciu tej zasady drzewo kodów Huffmana przyjmie postać:

Symbol	Kod
a	0
b	10
c	110
d	111

Opracowano na podstawie [1].

Specyfikacja zadania

Państwa zadanie sprowadza się do wyznaczenia słów kodowych wg. powyższego algorytmu dla symboli występujących w pliku, którego nazwę wprowadza użytkownik programu. Słowa kodowe należy zapisać do drugiego pliku (tzw. pliku słownika) wskazanego przez użytkownika, zgodnie z następującą zasadą:

Najpierw zapisujemy symbol jako liczbę typu „unsigned char”, tzn. jako liczbę całkowitą z przedziału od 0 do 255 w postaci kodów ASCII poszczególnych cyfr.
Następnie wstawiamy znak ':'.
Dalej podajemy kod Huffmana dla danego symbolu w postaci ciągu zer i jedynek zapisanych również za pomocą kodów ASCII.
Na końcu takiego wpisu wstawiamy znak nowej linii, tzn. liczby 13 i 10.

gen.exe

Tutaj kończy się obowiązkowy dla Państwa zakres prac.

Następnie należałoby zakodować wejściowy plik (plik_we) przy użyciu wcześniej wyznaczonych kodów (zamieszczonych w pliku słownika plik_slownika) zapisując do pliku wynikowego (plik_wy) zamiast symboli wejściowych, odpowiadające im ciągi bitów, oczywiście już nie jako kody ASCII. Operację tę wykonuje załączony program demonstracyjny „kom.exe”.

Dekodowanie pliku umożliwia program „dek.exe”. Operację tę realizuje się również w oparciu o drzewo kodów Huffmana przechodząc drzewo od korzenia do liści wg. ścieżek zapisanych w zakodowanym pliku. Dzięki jednoznaczności kodów odtworzenie zbioru danych wejściowych jest możliwe.

W praktyce należałoby oczywiście zapamiętywać słownik w sposób bardziej optymalny niż w postaci kodów ASCII oraz zamieścić nagłówek w zakodowanym pliku zawierający długość oryginalnego zbioru danych, co uniemożliwi doklejanie dodatkowych znaków na końcu pliku podczas dekompresji.

Pomimo długiego opisu projekt drugi nie jest projektem bardzo czasochłonnym. Zakłada znajomość podstawowych pojęć związanych z budową drzew binarnych, w tym przechodzenia wg. kolejności preorder, inorder oraz postorder, a także umiejętności dynamicznego tworzenia danych. Ze względu na spóźnione zamieszczenie specyfikacji projektu termin zaliczenia zostanie przesunięty.

Załączone programy

Generator kodów Huffmana - gen.exe
Program kompresujący dane - kom.exe
Program dekompresujący - dek.exe

Literatura

[1] pod redakcją W. Skarbka, „MULTIMEDIA. Algorytmy i standardy kompresji”, Akademicka Oficyna Wydawnicza PLJ, Warszawa 1998.