Komprejsa obrazu - kod Huffmana

Witam

Mam zadanie, polegające na napisaniu programu kompresującego bitmapę z wykorzystaniem algorytmu Huffmana (oraz dekompresującego). Bitmapa jest 8-bitowa (8 bitów na piksel, paleta kolorów lub odcienie szarości).
Stworzyłem ogólny algorytm. Bardzo proszę o sprawdzenie toku rozumowania i wskazanie błędów :)

Kodowanie:

1. Tworzę w programie tablicę, składającą się z 256 elementów.
2. Z nagłówka pliku BMP odczytuję wysokość i szerokość obrazu
3. Przechodzę do tablicy pikseli i odczytuje ją po jednym bajcie.
4. Inkrementuję w mojej tablicy indeks, odpowiadający odczytanemu bajtowi.
5. Gdy dochodzę do końca pliku to w tablicy mam zliczone wsytąpienia poszczególnych kolorów.
6. Dane z tablicy "przekazuję" do algorytmu Huffmana i dla każdego indeksu (koloru) otrzymuję jego kod.
7. Tworzę nowy plik (skompresowany) i umieszczam w jego nagłówku wysokość i szerokość obrazu.
8. Tworzę nową paletę barw - składowe pobieram z "oryginalnej" palety, jednak zamiast indeksów daję kod.
9. "Przepisuję" tablicę pikselów z oryginalnego obrazu, uwzględniając kody znajdujące się w nowej (skompresowanej) palecie barw.

Pozdrawiam

Moim zdaniem w znacznej większości twój tok rozumowania jest poprawny. Nie jestem tylko pewien, po co pobierać wymiary obrazu. Jeśli nie chcesz wyświetlać skompresowanego pliku jako obrazu (chyba, że chcesz) to imo nie bardzo ma to sens.
Pozdrawiam

Witam ponownie :)

Dziękuję za odpowiedzi.
Okazało się, że kompresowana ma być bitmapa 4-bitowa (a nie jak pisałem na początku 8-bitowa). Jest jednak pewien problem - pliki źródłowe, które mają być poddane kompresji nie zawierają palety barw, lecz każdy piksel opisywany jest za pomocą trzech bajtów (składowe kolejno B, G, R). Trochę to dziwne, bo choć obrazek jest 4-bitowy to zapisany jest jak 24-bitowy. W związku z tym w skompresowanym pliku będę musiał sam stworzyć paletę barw - i tu pojawia się problem :) Nie do końca wiem w jaki sposób to uczynić
Moim pierwszym pomysłem było stworzenie tablicy czterowymiarowej (np. int[16][4]) i dla każdego indeksu (od 0 do 15) zapisywać ilość wystąpień danego koloru (np. tab[0][0] - składowa B, tab[0][1] - składowa G, tab[0][2] - składowa R, tab[0][3] - ilość wystąpień). Nie wiem w jaki sposób można byłoby to jeszcze zrealizować?
Jeśli chodzi o samo tworzenie tablicy kolorów to trzeba chyba odczytywać po trzy bajty, następnie sprawdzać czy taka kombinacja znajduje się już w tablicy, jeśli tak to należy ją inkrementować, a jeśli nie to dopisać?

Mam nadzieję, że udało mi się wyjaśnić w miarę zrozumiale o co mi chodzi. Będę bardzo wdzięczny za wszelkie wskazówki.

Pozdrawiam

Mając te informacje powiem tak. Nie musisz zbierać palety barw ani wymiarów obrazu. Po prostu odczytuj plik bajt po bajcie i zapisuj w tablicy ilość wystąpień poszczególnych bajtów i zakoduj pojedyncze bajty Huffmanem

Ale mając paletę barw kompresja powinna być skuteczniejsza (bo kodujemy tylko 16 wartości, a nie 48).

Pojawił się kolejny problem :)
Plik źródłowy zdefiniowałem jako fstream wejscie; Dane pobieram z niego bajt po bajcie, zapisując je do zmiennej typu unsigned char (wejscie >> zmienna). Niestety, gdy w pliku znajduje się bajt o wartości 0x20 to jest pomijany i odczytywany jest kolejny bajt (jest to znak spacji z ASCII). Nie wiem jak sobie z tym poradzić

fstream wejscie("plik",ios::in|ios::binary);
int znak;
while((znak=wejscie.get())!=EOF) ...

micha_l napisał(a):

Plik źródłowy zdefiniowałem jako fstream wejscie; Dane pobieram z niego bajt po bajcie, zapisując je do zmiennej typu unsigned char (wejscie >> zmienna)

Jeśli chcesz czytać binarnie to użyj funkcji read() z flagą ios::binary.

Dziękuję :)
Dopisanie ios::binary i używanie funkcji get(), zamiast operatora ">>" pomogło