1.2. Аналіз існуючих методів стиснення зображень

У зв’язку з тенденцією розвитку комп'ютерної графіки бурхливо розвивається певна область теорії компресії — алгоритми стиснення зображень. Поява цієї області обумовлена тим, що зображення — це своєрідний тип даних, що характеризується трьома особливостями [4]:

1. Зображення (як і відео) займають|позичають| набагато більше місця|місце-милі| в пам'яті, ніж текст. Так, не дуже якісна ілюстрація на обкладинці книги розміром 500x800 точок, займає|позичає| 1.2 Мб — стільки ж, скільки художня книга з|із| 400 сторінок (60 знаків в рядку, 42 рядки на сторінці). Як приклад|зразок| можна розглянути|розглядувати| також, той факт, що на CD-ROM ми зможемо помістити декілька тисяч сторінок тексту|, і досить мало там якісних нестислих фотографій. Ця особливість зображень визначає актуальність алгоритмів стиснення графіки.

2. Другою особливістю зображень є|з'являється| те, що людський зір при аналізі зображення оперує контурами, загальним|спільним| переходом кольорів і порівняно нечутливий до малих змін в зображенні. Таким чином, ми можемо створити ефективні алгоритми стиснення зображень, в яких декомпресоване зображення не збігатиметься з|із| оригіналом, проте|однак| людина цього не помітить. Дана особливість людського зору дозволила створити спеціальні алгоритми стиснення, орієнтовані тільки|лише| на зображення. Ці алгоритми мають дуже високі характеристики.

3. Ми можемо легко відмітити|помітити|, що зображення, на відміну|відзнаку|, наприклад, від тексту, має надмірність в 2-х вимірах. Тобто як правило, сусідні точки, як по горизонталі, так і по вертикалі, в зображенні близькі за кольором. Крім того, ми можемо використовувати подібність|подобу| між колірною площиною R, G і B в алгоритмах, що дає можливість|спроможність| створити ще ефективніші алгоритми. Таким чином, при створенні|створінні| алгоритму компресії графіки ми використовуємо особливості структури зображення.

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

Для того, щоб говорити про алгоритми стиснення зображень, ми повинні визначитися з|із| декількома важливими|поважними| питаннями:

• Які критерії ми можемо запропонувати для порівняння різних алгоритмів?

• Які класи зображень існують?

• Які класи програм|застосувань|, що використовують алгоритми компресії графіки, існують, і які вимоги вони пред'являють до алгоритмів?

Розглянемо|розглядуватимемо| ці питання докладніше|детальний|.

1.2.1. Класи зображень

Статичні растрові зображення є двовимірним масивом чисел. Елементи цього масиву називають пікселами (від англійського pixel| — picture| element|). Всі зображення можна підрозділити на дві групи — з|із| палітрою і без неї. У|біля| зображень з|із| палітрою в пікселі зберігається число — індекс в деякому одновимірному|одномірному| векторі кольорів, званому палітрою. Найчастіше зустрічаються палітри з|із| 16 і 256 кольорів.

Зображення без палітри поділяються на зображення в якій-небудь системі колірного представлення| і в градаціях сірого (grayscale|). Для останніх значення кожного піксела інтерпретується як яскравість відповідної точки. Зустрічаються зображення з 2, 16 і 256 рівнями сірого. Одна з цікавих| практичних задач полягає в приведенні кольорового або чорно-білого зображення до двох градацій яскравості, наприклад, для друку|печатки| на лазерному принтері. При використанні деякої системи колірного представлення| | кожним пікселом є запис (структура), полями якого є|з'являються| компоненти кольору|цвіту|. Найпоширенішою є|з'являється| система RGB|, в якій колір|цвіт| представлений|уявляти| значеннями інтенсивності червоною (R), зеленою (G) і синьою (B) компонент. Існують і інші системи колірного представлення|||, такі, як CMYK|, HLS та інші.

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

Розглянемо|розглядуватимемо| наступні|слідуючі| приклади|зразки| неформального визначення класів зображень [4]:

1. Дворівневе (або монохромне) зображення. В цьому випадку всі піксели можуть мати тільки|лише| два значення, які зазвичай|звично| називають чорним (двійкова одиниця) і білим (двійковий нуль). Кожен піксел цього зображення представляється одним бітом.

2. Півтонове зображення. Кожен піксел такого зображення може мати 2ⁿ значень від 0 до 2ⁿ – 1, що позначають одну з 2ⁿ градацій сірого (або іншого) кольору. Число n зазвичай зрівняне з розміром байта, тобто, воно дорівнює 4, 8, 12, 16, 24 або інше кратне 4 або 8 число. Безліч найбільш значущих бітів всіх пікселів утворює значущу бітову площину або шар зображення. Отже, півтонове зображення з шкалою з 2ⁿ рівнів складене з n бітових шарів.

3. Кольорове зображення. Існує декілька методів задання кольору|цвіту|, але|та| в кожному з них беруть участь| три параметри. Отже, кольоровий піксел складається з трьох частин|часток|, зазвичай|звично| – з|із| трьох байтів. Типовими колірними моделями є|з'являються| RGB|, CMYK|, HLS|.

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

5. Дискретно-тонове зображення (синтетичне). Звичайно|звичний| це зображення виходить штучним шляхом. Воно може містити всього декілька або багато кольорів, але|та| в ньому немає шумів і плям природного зображення. Прикладами|зразками| таких зображень можуть бути креслення штучних об'єктів, механізмів або машин, сторінки тексту, карти або зображення на екрані комп'ютера. Штучні об'єкти, тексти, намальовані лінії мають форму, добре визначувані межі|кордони|. Вони сильно контрастують на фоні інших чатин|частки| зображення. Такі зображення погано стискаються методами з|із| втратами даних, оскільки спотворення всього декількох пікселів букви|літери| робить|чинить| її нерозбірливою, перетворить звичне зображення в абсолютно|цілком| невиразне. Методи для стиснення зображень з|із| безперервними тонами погано поводяться з чіткими краями дискретно-тонових зображень. Відзначимо, що дискретно-тонові зображення несуть в собі велику надмірність. Багато її фрагментів повторюються багато раз в різних місцях|місце-милях| зображення.

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

Достатньо|досить| складним і цікавим завданням|задачею| є|з'являється| пошук найкращого|щонайкращого| алгоритму для конкретного класу зображень.