1. 13.1. Необхідність стиснення зображень
2. 13.2. Неіснування ідеального алгоритму
3. 13.3. Алгоритми кодування довжини повторення (RLE)
4. RLE - бітовий рівень
5. RLE - байтовий рівень

Анотація: Необхідність стиснення зображень. Неіснування ідеального алгоритму. Алгоритми кодування довжини повторення (RLE): RLE - бітовий рівень, RLE - байтовий рівень. Словникові алгоритми: алгоритм LZ77, алгоритм LZW. Алгоритми статистичного кодування: Алгоритм Хаффмена. Арифметичне кодування.

13.1. Необхідність стиснення зображень

Типове зображення, отримане цифровою фотокамерою, має дозвіл порядку 3000x2000, тобто близько 6 мегапікселів; для передачі кольору зазвичай використовується 24 біта на піксель. Таким чином, обсяг вихідних даних складає близько 17 мегабайт. Для професійних пристроїв введення зображень розмір одержуваного растра може бути значно більше, а глибина кольору - досягати 48 біт на піксель ( "Сучасні апаратні засоби растрової графіки" ). Відповідно, розмір одного зображення може бути більше 200 мегабайт. Тому дуже актуальними є алгоритми стиснення зображень, або, іншими словами, алгоритми, які дозволяють зменшити обсяг даних, що представляють зображення.

Існують два основні класи алгоритмів:

1. A називається алгоритмом стиску без втрат (англ. Lossless compression), якщо існує алгоритм A-1 (зворотний до A) такий, що для будь-якого зображення IA (I) = I1 і A-1 (I1) = I. Зображення I задано як безліч значень атрибутів пікселів; після застосування до I алгоритму A одержуємо набір даних I1. Стиснення без втрат застосовується в таких графічних форматах представлення зображень, як: GIF, PCX, PNG, TGA, TIFF1, безліч власних форматів від виробників цифрових фотокамер, і т.д.);
2. A називається алгоритмом стиску c втратами (англ. Lossy compression), якщо він не забезпечує можливість точного відновлення вихідного зображення. Парний до A алгоритм, що забезпечує зразкову відновлення, будемо позначати як A *: для зображення IA (I) = I1, A * (I1) = I2 і при цьому отримане відновлене зображення I2 не обов'язково точно збігається з I. Пара A, A * підбирається так, щоб забезпечити великі коефіцієнти стиснення і тим не менше зберегти візуальну якість, тобто домогтися мінімальної різниці в сприйнятті між I і I2. Стиснення з втратами застосовується в наступних графічних форматах: JPEG, JPEG2000 і т.д.

Ця лекція присвячена стиску без втрат, що потрібно у випадках, коли така інформація була отримана великою ціною (наприклад, медичні зображення або знімки з супутників), або в інших випадках, коли навіть найменші спотворення небажані [2] .

13.2. Неіснування ідеального алгоритму

Як уже було згадано в попередньому пункті, зображення I розглядається як безліч (послідовність) значень атрибутів пікселів. Надалі в цій лекції всі алгоритми і затвердження відносяться як до зображень, так і до довільних послідовностей, елементи яких можуть брати кінцеве кількість значень.

Затвердження 13.2.1. Не існує алгоритму, який стискає без втрат будь-який набір даних.

Існує 2N послідовностей розміру N бітів (Будемо розглядати біт як мінімальний носій інформації). Нехай знайдеться алгоритм A такий, що , Де | I | - обсяг даних (довжина послідовності). Нехай M = max Mk, тоді M <N. Існує 21 + 22 + ... + 2M послідовностей довжини, меншою або рівною M. Але 21 + 22 + ... + 2M = 2M + 1-2 <2N. Протиріччя.

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

13.3. Алгоритми кодування довжини повторення (RLE)

Цей тип алгоритмів (алгоритми кодування довжини повторенія2 (RLE3)) базується на найпростішому принципі: будемо замінювати повторювані групи елементів вихідної послідовності на пару (кількість, елемент), або тільки на кількість.

RLE - бітовий рівень

Будемо розглядати вихідні дані на рівні послідовності бітів; наприклад, що представляють чорно-біле зображення. Поспіль зазвичай йде кілька 0 або 1, і можна пам'ятати лише кількість йдуть підряд однакових цифр. Тобто послідовності 0000 11111 000 11111111111 відповідає набір чисел кількостей повторень 4 5 3 11. Виникає наступне нюанс: числа, що позначають кількість повторень, також треба кодувати битами. Можна вважати, що кожне число повторень змінюється від 0 до 7 (тобто можна закодувати рівно трьома бітами), тоді послідовності 11111111111 можна зіставити числа 7 0 4, тобто 7 одиниць, 0 нулів, 4 одиниці. Для прикладу, послідовність, що складається з 21 одиниці, 21 нуля, 3 одиниць і 7 нулів закодується так: 111 000 111 000 111 111 000 111 000 111 011 111, тобто з вихідної послідовності, яка має довжину 51 біт, отримали послідовність довжиною 36 біт.

Ідея цього методу використовується при передачі факсів.

RLE - байтовий рівень

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

Будемо розбивати вхідний потік на байти (букви) і кодувати повторювані букви парою (кількість, буква).

Тобто AABBBCDAA кодируем (2A) (3B) (1C) (1D) (2A). Однак можуть зустрічатися довгі відрізки даних, де нічого не повторюється, а ми кодируем кожну букву парою (цифра, буква).

Нехай у нас є фіксоване число (буква) M (від 0 до 255). Тоді одиночну букву можна закодувати нею самою, - вихід = S, а якщо букв кілька або , То вихід = CS, де C> M, а C - M - кількість йдуть підряд букв S. Для прикладу наведемо лише алгоритм декодування.

// M - фіксована межа // зчитуємо символи послідовно із вхідного потоку // in - вхід - стисла послідовність // out - вихід - розціпленого послідовність while (in.Read (c)) {if (c> M) {// випадок лічильника n = c - M; in.Read (c); for (i = 0; i <n; i ++) out.Write (c); } Else // випадок просто символу out.Write (c); } Лістинг 13.1. Алгоритм декодування RLE - байтовий рівень

Число M звичайно дорівнює 127. Найчастіше використовується модифікація цього алгоритму, де ознакою лічильника служить наявність одиниць в 2 старших бітах зчитувального символу. Решта 6 бітів суть значення лічильника.

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