У перших зберігають, згідно назві, растрову графіку, застосовуючи різні алгоритми кодування та стиснення інформації.

Якщо інформацію про зображення просто кодувати та розміщувати у фалі без стиснення, то об’єми їх будуть вражаючими. Тому слід розглянути деякі алгоритми стиснення графічних файлів. Стиснення може бути з втратами та без втрат кодованої інформації. Стиснення може здійснюватись за допомогою словників найбільш вживаних слів, і тут словники можуть бути адитивні та неадитивні (постійні словники та динамічні відповідно).

GIF (Graphic Interchange Format) – растровий з обмеженою колірністю: 2 – 256 кольорів. Використовує LZW стиснення, має обмеження на розмір зображення: 64К х 64К пікселів. Підтримує анімацію, найбільш

підходить для плашкових зображень.

EPS (Encapsulated PostScript) – метафайловий формат, базується на використанні мови опису сторінок PostScript. Цей файл є монохромним, при збереженні кольорового CMYK зображення у файлі буде по одному зображенню на кожний колірний канал. Ще надається можливість зберігання екранної копії зображення та піктограми для відтворення у файлі. Може бути двох форматів – ASCII або двійковому. Не використовує стискання, не має обмежень на розмір. Використовується для поліграфічного відтворення, в програмах макетування.

JPEG – растровий, колірність 24 біта, має обмеження на розмір, що і *.gif. Власне стискання – ефект стиснення 10-15 разів без помітної оком різниці. Не підтримує анімації. Використовується для збереження на півтонових сірих і кольорових фотографічних зображень.

TIFF (Tag Image File Format) – найбільш вживаний формат обміну, передає всю інформацію, що створила програма. Не підтримує багатошаровості, максимальний розмір файлу 232. Колірність до 24 бітів, використовує всі можливі алгоритми стиснення (RLE, CCITT, LZW).

Проаналізувавши різні типи графічних форматів, я зупинився на BMP-форматі. Тому в даній дипломній роботі буде кодуватись саме такі зображення. Розглянемо його докладніше.

Структура BMP файлу така. Перших 54 байти складає заголовок. У перших 2 байтах заголовку записані символи B та M, за цим можна відрізнити, що ми працюємо саме з BMP-файлом. У байтах 10–13 записане 4–байтне ціле, яке вказує зміщення від початку файлу до початку піксельних даних. Якщо це число більше за 54, значить, після заголовку йде таблиця кольорів, і тому BMP-файл не є 24–бітним. У байтах 18–21 записана ширина зображення, у байтах 22–25 — висота, у байтах 28–29 буде бітність, у байтах 30–33 — тип компресії. Для незтиснутого зображення рівна нулю.

Незжаті піксельні дані записані в форматі BGR по рядках знизу вверх.

На відміну від PCX-формату, дані рядка пікселів тут записуються послідовно, а не покомпонентно. Рядок пікселів повинен бути кратним 4 байтам. Тому, якщо, наприклад, зображення є шириною 9 пікселів, то довжина рядку при 24–бітному кольорі повинна була б бути 9*3=27 байт. 27 не є кратним четвірці, тому після даних рядка 1 байт заповнюється нулем.

1.3 Методи кодування

Кодування (encoding) має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потока на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи.

Перший підхід: продивитися вхідний потік і побудувати кодування на основі зібраної статистики (це потребу двох проходів по файлу, що звужує сферу застосування таких алгоритмів). У вихідний потік в такому випадку має бути записано схему кодування, що застосовувалося. Цією схемою потім скористається декодер. Приклад – статистичне кодування Хаффмена.

Другий підхід – використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних.

Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена.

Кодування Хаффмена

Розглянемо статистичне кодування Хаффмена. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символа не є префіксом коду жодного іншого символа. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ.

При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці.

Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).

Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}.

Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від’ємних