Komprejsa obrazu - kod Huffmana

Komprejsa obrazu - kod Huffmana
ML
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 9 lat
  • Postów:5
0

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

MateuszS
Wydaje mi sie ze jest ok (o ile dobrze wszystko zrozumialem). Napisz Huffmana optymalnie i powinno ladnie dzialac. Sam mialem podobny projekt wiec moge pomoc
BA
  • Rejestracja:około 11 lat
  • Ostatnio:ponad 6 lat
  • Postów:36
1

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

ML
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 9 lat
  • Postów:5
0

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

BA
Mówisz o tworzeniu palety w skompresowanym pliku, prawda?
ML
Tak, przy dekompresji będę musiał zapisać w formacie bez palety (3 bajty na piksel)
BA
To powiedz mi jeszcze, czy chcesz wyświetlać ten skompresowany plik jako obraz, czy to ma być plik w stylu .rar albo zip, który służy tylko do zmniejszenia objętości obrazu?
ML
Wyświetlanie nie jest konieczne. Ważnie jest tylko to, aby była możliwość dekompresji do pliku bmp :)
BA
  • Rejestracja:około 11 lat
  • Ostatnio:ponad 6 lat
  • Postów:36
1

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

ML
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 9 lat
  • Postów:5
0

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

BA
Nie jestem w tej kwestii specem, ale wydaje mi się, że im większy potencjalny słownik, tym lepiej Huffman koduje (pod warunkiem, że prawdopodobieństwo wystąpień nie jest nadmiernie zróżnicowane)
ML
W sumie masz racje :) Mój błąd. Ale paleta, niestety, jest konieczna (takie wymagania projektu)
Azarien
"prawdopodobieństwo wystąpień nie jest nadmiernie zróżnicowane" - chyba "nie jest nadmiernie równomierne"? :-) bo przy równym p-stwie wszystkich znaków kompresja jest niemożliwa.
BA
To prawda, ale też kiedy prawdopodobieństwo wystąpienia pewnego symbolu jest bliskie 1 albo po prostu duże to Huffman jest nieefektywyny (a przynajmniej nie tak efektywny, gdy prawdopodobieństwo jest bardziej "wypośrodkowane").
ML
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 9 lat
  • Postów:5
0

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ć

_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
2
Kopiuj
fstream wejscie("plik",ios::in|ios::binary);
int znak;
while((znak=wejscie.get())!=EOF) ...

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
several
  • Rejestracja:ponad 15 lat
  • Ostatnio:około 9 godzin
2
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.


edytowany 1x, ostatnio: several
ML
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 9 lat
  • Postów:5
0

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

Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)