Стиснення зображень

Сти́снення зобра́жень — використання алгоритмів стиснення даних до зображень, що зберігаються в цифровому виді. В результаті стиснення зменшується розмір зображення, що зменшує час передачі зображення по мережі і економить простір для зберігання. Стиснення зображень розділяють на стиснення з втратами якості і стиснення без втрат. Стиснення без втрат більш підходить для штучно побудованих зображень, таких як графіки, іконки програм, або для спеціальних випадків, наприклад, якщо зображення призначені для подальшої обробки алгоритмами розпізнавання зображень. Алгоритми стиснення з втратами при збільшенні степені стиснення, як правило, породжують добре помітні людському оку артефакти.

Діаграма, що відображає відносну якість різних налаштувань jpg, а також порівнює нормальне збереження файлу jpg і з застосуванням техніки «збереження для web»

Класи додатків, що використовують стиснення

В загальному виділяють 3 класи додатків, що використовують алгоритми компресії:

• Клас 1. Характеризуються високими вимогами до часу архівації та розархівації. Нерідко потрібно виконати перегляд зменшеної копії зображення і пошук у базі даних зображень.
• Клас 2. Характеризується високими вимогами до ступеня архівації та часу розархівації. Час архівації ролі не грає.
• Клас 3. Характеризується дуже високими вимогами до ступеня архівації.

Можна навести безліч більш вузьких класів додатків. Так, своє застосування машинна графіка знаходить і в різних інформаційних системах. Наприклад, вже стає звичним досліджувати ультразвукові та рентгенівські знімки не на папері, а на екрані монітора. Поступово в електронний вигляд переводять та історії хвороб. Зрозуміло, що зберігати ці матеріали логічніше в єдиній картотеці. При цьому без використання спеціальних алгоритмів більшу частину архівів займуть фотографії. Тому при створенні ефективних алгоритмів вирішення цього завдання потрібно врахувати специфіку рентгенівських знімків — переважання розмитих ділянок. У геоінформаційних системах — при зберіганні аерофотознімків місцевості — специфічними проблемами є великий розмір зображення і необхідність вибірки лише частини зображення на вимогу. Крім того, може знадобитися масштабування. Це неминуче накладає свої обмеження на алгоритм компресії. В електронних картотеках і досьє різних служб для зображень характерно подібність між фотографіями в профіль, і подібність між фотографіями в фас, яке також необхідно враховувати при створенні алгоритму архівування. Подібність між фотографіями спостерігається і в будь-яких інших спеціалізованих довідниках. Як приклад можна навести енциклопедії птахів чи квітів.

Вимоги до алгоритмів компресії

Характер використання зображень визначає ступінь важливості наведених нижче суперечливих вимог до алгоритму:

• Високий ступінь компресії.
• Висока якість зображень. Виконання цієї вимоги напряму суперечить виконанню попередньої.
• Висока швидкість компресії. Ця вимога для деяких алгоритмів з втратою інформації є взаємовиключною з першими двома. Що більше часу необхідно витратити на аналіз зображення з метою отримання найвищої ступені компресії, тим кращим буде результат. І, відповідно, чим менше буде витрачено на компресію (аналіз), тим нижчою буде якість зображення і більшим його розмір.
• Висока швидкість декомпресії.
• Масштабування зображень. Дана вимога передбачає легкість зміни розмірів зображення до розміру вікна активного додатку. Одні алгоритми дозволяють легко масштабувати зображення під час декомпресії, в той час як інші не тільки не дозволяють легко масштабувати, але і збільшують вірогідність появи «неприємних» артефактів після застосування стандартних алгоритмів масштабування до декомпресованих зображень. Приміром можна навести приклад «поганого» зображення для алгоритму JPEG — це зображення з досить дрібним регулярним малюнком (піджак в дрібну клітку). Характер внесених алгоритмом JPEG спотворень такий, що зменшення або збільшення зображення може дати неприємні ефекти.
• Стійкість до помилок. Дана вимога означає локальність порушень у зображенні при пошкодженні або втраті фрагмента переданого файлу. Дана вимога суперечить вимозі високого ступеня архівації, оскільки необхідно вводити надлишкову інформацію. Однак для різних алгоритмів обсяг цієї надлишкової інформації може істотно відрізнятися.
• Редагованість. Під редагованістю розуміється мінімальна ступінь погіршення якості зображення при його повторному збереженні після редагування. Багато алгоритмів з втратою інформації можуть істотно пошкодити зображення за декілька ітерацій редагування.
• Незначна вартість апаратної реалізації. Ефективність програмної реалізації. Ці вимоги до алгоритму пред'являють виробники багатьох інформаційних систем. Так, декомпресор фрактального алгоритму дуже ефективно реалізується з використанням технології MMX і розпаралелюванням обчислень, а стиснення за стандартом CCITT Group 3 легко реалізується апаратно.

Критерії порівняння алгоритмів

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

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

Алгоритми архівації без втрат

Алгоритм RLE

Алгоритм RLE (Run Length Encoding) — один з найстаріших і найпростіших алгоритмів архівації графіки. Зображення в ньому витягується в ланцюжок байт по рядках растра. Саме стиснення в RLE відбувається за рахунок того, що у вихідному зображенні зустрічаються ланцюжки однакових байт. Алгоритм орієнтований на зображення з невеликою кількістю кольорів: ділову та наукову графіку. До позитивних сторін алгоритму можна віднести тільки те, що він не вимагає додаткової пам'яті при архівації та розархівації, а також швидко працює.

Алгоритм LZW

Назву алгоритм LZW отримав за першими літерами прізвищ його розробників — Lempel, Ziv і Welch. Стиснення в ньому, на відміну від RLE, здійснюється за рахунок однакових ланцюжків байт. Процес стиснення виглядає досить просто. Ми зчитуємо послідовно символи вхідного потоку і перевіряємо, чи є у створеній нами таблиці рядків такий рядок. Якщо рядок є, то ми зчитуємо наступний символ, а якщо рядка немає, то ми заносимо в потік код для попередньої знайденої рядки, заносимо рядок в таблицю і починаємо пошук знову. Алгоритм LZW орієнтований на 8-бітові зображення. LZW є універсальним алгоритмом — саме його варіанти використовуються у звичайних архіваторах.

Алгоритм Хаффмана

Алгоритм Хаффмана — один з класичних алгоритмів, відомих з 60-х років. Використовує тільки частоту появи однакових байт в зображенні. Зіставляє символам вхідного потоку, які зустрічаються більше число раз, ланцюжок біт меншої довжини. І, навпаки, тим, які зустрічається рідко — ланцюжок більшої довжини. Для збору статистики вимагає двох проходів по зображенню. Алгоритм Хаффмана практично не застосовується до зображень у чистому вигляді. Зазвичай використовується як один з етапів стиснення в складніших схемах. Цей алгоритм реалізований у форматі TIFF. Він є надзвичайно простим у реалізації, швидким і може бути легко реалізований апаратно.

JBIG

Алгоритм JBIG розроблений групою експертів ISO (Joint Bi-level Experts Group) спеціально для стиснення однобітних чорно-білих зображень, наприклад, факсів або відсканованих документів. Може також застосовуватися і до 2-х, і до 4-х бітових зображень. При цьому алгоритм розбиває їх на окремі бітові площини. JBIG дозволяє управляти такими параметрами, як порядок розбиття зображення на бітові площини, ширина смуг в зображенні, рівні масштабування.

Lossless JPEG

Алгоритм Lossless JPEG розроблений групою експертів в області фотографії (Joint Photographic Expert Group). На відміну від JBIG, Lossless JPEG орієнтований на повнокольорові 24-бітні або 8-бітові зображення в градаціях сірого без палітри. Він являє собою спеціальну реалізацію JPEG без втрат. Lossless JPEG рекомендується застосовувати в тих додатках, де необхідно побітова відповідність вихідного і декомпресованого зображень.

Алгоритми архівації з втратами

Алгоритм JPEG

JPEG — один з найновіших і досить потужних алгоритмів. Практично він є стандартом де-факто для повнокольорових зображень. Оперує алгоритм областями 8х8, на яких яскравість і колір змінюються порівняно плавно. Внаслідок цього, при розкладанні матриці такої області в подвійний ряд косинусів значущими виявляються тільки перші коефіцієнти. Таким чином, стиснення в JPEG здійснюється за рахунок плавності зміни кольорів у зображенні. Алгоритм розроблений групою експертів в області фотографії спеціально для стиснення 24-бітових зображень. JPEG — Joint Photographic Expert Group — підрозділ у рамках ISO — Міжнародної організації зі стандартизації. В цілому алгоритм заснований на дискретному косинусному перетворенні (надалі ДКП), що застосовується до матриці зображення для отримання деякої нової матриці коефіцієнтів. Для отримання початкового зображення застосовується зворотне перетворення.

Фрактальний алгоритм

Фрактальна архівація заснована на тому, що зображення представляють в компактнішій формі — з допомогою коефіцієнтів системи ітерованих функцій (Iterated Function System — IFS). IFS являє собою набір тривимірних афінних перетворень, які переводять одне зображення в інше. Перетворенню підлягають точки в тривимірному просторі (х_координата, у_координата, яскравість).

Найвідоміші два зображення, отриманих за допомогою IFS: «трикутник Серпінського» і «папороть Барнслі». «Трикутник Серпінського» задається трьома, а «папороть Барнслі» чотирма афінними перетвореннями. Кожне перетворення кодується кількома байтами, в той час як зображення, побудоване з їх допомогою, може займати і декілька мегабайт.

Алгоритм використовують при стисненні повнокольорових 24 бітних зображень або зображень у градаціях сірого без різких переходів кольорів (фотографії). Бажано, щоб області більшої значимості (для сприйняття) були більш контрастними і різкими, а області меншої значимості — неконтрастними і розмитими.

Рекурсивний (хвильовий) алгоритм

Англійська назва рекурсивного стиснення — wavelet. Цей вид архівації відомий досить давно і безпосередньо виходить з ідеї використання когерентності областей. Орієнтований алгоритм на кольорові і чорно-білі зображення з плавними переходами. Ідеальний для картинок типу рентгенівських знімків. Коефіцієнт стиснення задається і варіюється в межах 5-100. До переваг цього алгоритму можна віднести те, що він дуже легко дозволяє реалізувати можливість поступового «проявлення» зображення при передачі зображення по мережі. На відміну від JPEG і фрактального алгоритму даний метод оперує блоками 2х2, 4х4, 8х8 і т. д. За рахунок того, що коефіцієнти для цих блоків зберігаються незалежно, можна досить легко уникнути дроблення зображення на «мозаїчні» квадрати.

Параметри різних алгоритмів стиснення зображень

Алгоритм	Коефіцієнти стиснення	Симетричність за часом	На що орієнтований	Втрати	Розмірність
RLE	32, 2, 0.5	1	3,4-х бітні	Немає	1D
LZW	1000, 4, 5 / 7	1.2-3	1-8 бітні	Немає	1D
Хаффмана	8, 1.5, 1	1-1.5	8 бітними	Немає	1D
CCITT-3	213 (3), 5, 0.25	~ 1	1-бітні	Немає	1D
JBIG	2-30 разів	~ 1	1-бітні	Немає	2D
Lossless JPEG	2 рази	~ 1	24-бітові, сірі	Немає	2D
JPEG	2-20 разів	~ 1	24-бітові, сірі	Є	2D
Рекурсивний стиск	2-200 разів	1.5	24-бітові, сірі	Є	2D
Фрактальний	2-2000 разів	1000-10000	24-бітові, сірі	Є	2.5D

Див. також

• Стиснення відео
• Стиснення звуку

Примітки

1. «Progressive Bi-level Image Compression, Revision 4.1» / / ISO / IEC JTC1/SC2/WG9, CD 11544, September 16, 1991.
2. GKWallace «The JPEG still picture compression standard» / / Communication of ACM. Volume 34. Number 4 April 1991.

Посилання

• Image Coding Fundamentals
• A study about image compression (Основи стиснення зображень і порівняння різних методів стиснення, таких як JPEG2000, JPEG і JPEG XR / HD Photo)
• Data Compression Basics (включає порівняння форматів PNG, JPEG і JPEG-2000)
• з comp.compression
• IPRG Відкрита група, присвячена дослідженню обробки зображень