Структурно-логічна модель кодера стиску інформаційних потоків даних

 

Структурно-логічна модель кодера стиску інформаційних потоків даних

Вміст

ВСТУП

РОЗДІЛ 1. АНАЛІЗ ІСНУЮЧИХ КОДЕРІВ СТИСКУ ІНФОРМАЦІЙНИХ ПОТОКІВ

1.1 Розгляд основних положень теорії стиснення

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

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

.2.2 Класи кодеків

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

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

.2.5 Алгоритми стиснення без втрат

1.2.5.1 Алгоритм RLE

.2.5.2 Метод LZW

.2.5.3 Класичний метод Хаффмена

.2.5.4 JBIG

.2.5.5 Lossless JPEG

1.2.6 Алгоритми стиснення з втратами

1.2.6.1 Алгоритм JPEG

.2.6.2 Алгоритм JPEG 2000

1.2.7 Зведені характеристики існуючих методів стиснення зображень

1.3. Висновки по розділу

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ТА ЛІТЕРАТУРИ

Додаток А

ВСТУП

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

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

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

Мета та завдання роботи - підвищення ефективності методів компресії джерела повідомлень з умов створення математичної і структурно-логічної моделі кодера стиску даних з урахуванням методів двоознакового структурного кодування (ДСК). При цьому до задач статті відноситься - визначення основних етапів процедури обробки інформації кодером при формуванні стислого потоку даних.

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

Наукова новизна дослідження полягає в наступному: розроблено математичну і програмну модель кодера стиску даних джерела повідомлень з урахуванням методів двоознакового структурного кодування двійкових даних. Визначено основні етапи процедури обробки інформації кодером. Реалізовано визначені моделі та етапи кодування зображень в прикладному програмному середовищі Mathcad.

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

Результати досліджень, зміст яких було викладено в роботі, були презентовані та обговорювалися на науково-технічній конференції студентів та молодих учених «Наукоємні технології», Київ, 2-3 грудня 2009р., на Всеукраїнському конкурсі студентських наукових робіт 2009-2010 рр. з напрямку «Інформатика, обчислювальна техніка та автоматизація» (Вінницький національний технічний університет), на Всеукраїнському конкурсі студентських наукових робіт 2009-2010 рр. з напрямку «Телекомунікаційні системи та мережі» (Одеська національна академія звязку ім. О.С. Попова).

Було опубліковано ряд наукових статей, присвячених темі, що розглядалася в дипломній роботі:

1.Юдін О.К., Чеботаренко Ю.Б., Курінь К.О. Розробка математичної моделі кодера стиску інформаційного потоку даних з урахуванням двоознакового структурного кодування // Наука и образование, том 20. - 2010. - с. 84-89.

2.Юдін О.К., Чеботаренко Ю.Б., Курінь К.О. Структурно-логічна модель кодера стиску інформаційного потоку даних // Вісник Інженерної академії України. - К., 2010. - 4 вид. - c. 151-157.

3.Юдін О.К., Луцький М.Г., Курінь К.О. Стиснення зображень з використанням двоознакового структурного кодування двійкових послідовностей // Наукоємні технології. - К., 2010. - 3-є вид. - с. 87-92.

РОЗДІЛ 1. АНАЛІЗ ІСНУЮЧИХ КОДЕРІВ СТИСКУ ІНФОРМАЦІЙНИХ ПОТОКІВ

.1 Розгляд основних положень теорії стиснення

Основна проблема, яку необхідно вирішити при побудові системи комунікації, була вперше сформульована Клодом Шенноном в 1948 році:

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

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

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

Головна ідея, обгрунтована Шеноном, полягає в тому, що надійні комунікації мають бути цифровими, тобто задачу зв'язку слід розглядати як передачу двійкових цифр (бітів).

На рис. 1.1 приведена загальна схема передачі цифрової інформації [1].

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

(1.1)

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

Форматування джерела повідомлень - це процес аналого-цифрового перетворення інформаційного сигналу джерела повідомлення в цифровий сигнал за допомогою дискретизації й квантування сигналу та його представлення в двійковій системі числення.

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

Рис. 1.1. Структурна схема цифрової інформаційної мережі передачі даних

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

Крім того, Шенон довів, що завдання надійного зв'язку можна розкласти на дві підзадачі без применшення її ефективності. Ці дві підзадачі називаються кодуванням джерела і кодуванням каналу.

Під кодуванням в загальному випадку розуміють перетворення алфавіту повідомлення в алфавіт деяким чином вибраних кодових символів . Зазвичай (але не обов'язково) розмір алфавіту кодових символів менше або набагато менше розміру алфавіту джерела .

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

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

Передача і зберігання інформації вимагають достатньо великих витрат. Велика частина даних, які потрібно передавати по каналах зв'язку і зберігати, має не найкомпактніше представлення. Зазвичай дані зберігаються у формі, що забезпечує їх найбільш просте використання, наприклад: звичайні книжкові тексти, ASCII коди текстових редакторів, двійкові коди даних ЕОМ, окремі відліки сигналів в системах збору даних і т.д. Проте таке найбільш просте у використанні представлення даних вимагає удвічі - втричі, а іноді і в сотні разів більше місця для їх збереження і смугу частот для їх передачі, ніж насправді потрібно. Тому стиснення даних - це один з найбільш актуальних напрямків сучасної теорії інформації.

Завданням кодування джерела є створення кодера джерела, яке проводить компактний (укорочене) опис початкового сигналу, який необхідно передати адресатові. Джерелом сигналів може служити текстовий файл, цифрове зображення, оцифрована музика або телепередача. Це стислий опис сигналів джерела може бути неточним, тоді слід говорити про розбіжність між відновленим після прийому і декодування сигналом і його оригіналом. Це зазвичай відбувається при перетворенні (квантуванні) аналогового сигналу в цифрову форму. Таке кодування називають економним, безнадлишковим, ефективним кодуванням або стисненням даних. Нижче приведена умовна структура [1] системи стиснення даних (рис.1.2.) :

Рис.1.2. Блок-схема алгоритму стиснення даних

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

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

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

Якщо алгоритм компресії є неадаптивним, то він не здатен змінювати свої операції та параметри в залежності від даних, що стискаються.

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

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

Деякі методи компресії використовують двопрохідні алгоритми, коли при першому проході файлом збирається певна статистика даних, що стискаються, а на другому - проходить безпосередньо стиснення з використанням параметрів, отриманих на першому етапі. Такі алгоритми є напівадаптивними.

Метод компресії, при якому дані на виході декомпресора завжди тотожно співпадають з вихідними даними називається методом компресії без втрат. Метод компресії, при якому дані на виході декомпресора відрізняються від вихідних даних, стиснених компресором, але результат, тим не менш, влаштовує користувача, називається компресією з втратами.

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

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

Для оцінки продуктивності стиснення використовується ряд величин.

Коефіцієнт стиснення розраховується за формулою [1]:

(1.2)

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

Коефіцієнт стиснення прийнято вимірювати в bpb (bit per bit). При стисненні графічних зображень використовується величина bpp (bit per pixel), текстових - bpc (bit per character). Разом з коефіцієнтом стиснення ефективність системи стиснення може бути охарактеризована швидкістю стиснення , що визначається як відношення

(1.3)

де - кількість біт повідомлення.

Величина, обернена коефіцієнту стиснення, називається фактором стиснення :

(1.4)

Головна причина використання стиснення даних в комунікаціях полягає в бажанні передавати або зберігати інформацію з найбільшою ефективністю. Бітовий бюджет (bit budget) визначає певний додаток до кожного біта стиснених даних. Наприклад, якщо в стиснутому файлі 90% займають коди змінної довжини, а 10% використовуються для зберігання деяких таблиць, які будуть використовуватися декомпресором для відновлення вихідних даних, то бітовий бюджет в даному випадку складає 10%.

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

Звернемося до кодування джерел. Як і в звичайному тексті в різних джерелах цифрових даних є надлишкові дані. Тому виникає питання: що є найбільш компактним представленням даних джерела? На це питання відповідь була дана Шеноном. У своїй роботі по теорії інформації він ввів числову характеристику джерела, яка називається ентропією. Фундаментальне значення цієї величини полягає в тому, що вона задає нижню межу можливого стиснення. Крім того, є теорема, яка стверджує, що до цієї межі можна наблизитися скільки завгодно близько за допомогою відповідного методу кодування джерела. Наприклад, відомо, що ентропія усередненого англійського тексту дорівнює приблизно 3.2 біт/букву. У комп'ютерному уявленні одна буква займає 8 бітів. Значить, при стисненні типового текстового файлу англійською мовою досягається стиснення приблизно в 2.5 раз. Під ентропією символа , ймовірність появи якого в повідомленні , розуміється кількість інформації, що міститься в і чисельно дорівнює [2]:

(1.5)

Якщо символи певного алфавіту мають ймовірності відповідно , то ентропія всього алфавіту дорівнює:

(1.6)

Ентропія строки символів цього алфавіту визначається аналогічно.

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

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

Як вже згадувалося вище всі методи стиснення поділяються на два великі класи [3]:

§методи стиснення без втрат інформації (не руйнуюче стиснення);

§методи стиснення з втратами інформації (руйнуюче стиснення).

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

Блок-схема алгоритму кодування без втрат зображена на рис. 1.3.

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

Рис.1.3. Блок-схема алгоритму кодування без втрат

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

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

Рис. 1.4. Блок-схема алгоритму кодування з втратами

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

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

Руйнуючий кодер додатковим параметром - величиною спотворень , яка визначається як:

(1.7)

Величина є мірою середньоквадратичної відмінності між .

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

Міра, що зараз використовується на практиці, називається мірою відношення сигналу до шуму (peak-to-peak signal-to-noise ratio - PSNR).

(1.8)

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

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

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

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

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

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

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

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

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

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

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

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

Розглянемо ці питання докладніше.

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

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

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

Для того, щоб корректніше оцінювати ступінь стиснення, потрібно ввести поняття класу зображень.

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

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

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

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

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

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

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

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

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

1.2.2 Класи кодеків

Розглянемо наступну просту класифікацію програм, що використовують алгоритми компресії [4]:

Клас 1. Характеризуються високими вимогами до часу стиснення і відновлення. Часто необхідне проглядання зменшеної копії зображення і пошук в базі даних зображень. Приклади: Видавничі системи, причому як ті, що готують якісні публікації (журнали) із високою якістю зображень і використанням алгоритмів стиснення без втрат, так і ті, що видають газети, і інформаційні вузли в WWW, де є можливість оперувати зображеннями меншої якості і використовувати алгоритми стиснення з втратами. У подібних системах доводиться мати справу з повнокольоровими зображеннями самого різного розміру (від 640х480 - формат цифрового фотоапарата, до 3000х2000) і з великими двокольоровими зображеннями. Оскільки ілюстрації займають левову частку від загального об'єму матеріалу в документі, проблема зберігання стоїть дуже гостро. Проблеми також створює велика різнорідність ілюстрацій (доводиться використовувати універсальні алгоритми).

Клас 2. Характеризується високими вимогами до ступеня стиснення і часу відновлення. Час компресії ролі не грає. Іноді від алгоритму компресії також вимагається легкість масштабування зображення під конкретний дозвіл монітора у користувача. Приклад: Довідники і енциклопедії на CD-ROM. З появою великої кількості комп'ютерів, оснащених цим приводом достатньо швидко сформувався ринок програм, що випускаються на лазерних дисках. Не дивлячись на те, що місткість одного диска досить велика, її, як правило, не вистачає. При створенні енциклопедій і ігор велику частину диска займають статичні зображення і відео. Таким чином, для цього класу додатків актуальності набувають істотно асиметричні за часом алгоритми.

Клас 3. Характеризується дуже високими вимогами до ступеня архівації. Програма клієнта отримує від сервера інформацію мережею. Приклад: Нова система Всесвітня інформаційна павутина - WWW. У цій гіпертекстовій системі достатньо активно використовуються ілюстрації. При оформленні інформаційних або рекламних сторінок хочеться зробити їх яскравішими і барвистішими, що природно позначається на розмірі зображень. Найбільше при цьому страждають користувачі, підключені до мережі за допомогою повільних каналів зв'язку. Якщо сторінка WWW перенасичена графікою, то очікування її повної появи на екрані може затягнутися. Оскільки при цьому навантаження на процесор мале, то тут можуть знайти застосування складні алгоритми ефективного стиснення з порівняно великим часом розархівування. Крім того, ми можемо видозмінити алгоритм і формат даних так, щоб проглядати огрублене зображення файлу до його повного отримання.

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

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

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

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

1. Високий ступінь компресії. Відмітимо, що далеко не для всіх програм актуальний високий ступінь компресії. Крім того, деякі алгоритми дають краще співвідношення якості до розміру файлу при високих ступенях компресії, проте програють іншим алгоритмам при низьких ступенях.

. Висока якість зображень. Виконання цієї вимоги безпосередньо суперечить виконанню попередньої.

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

. Висока швидкість декомпресії. Достатньо універсальна вимога, актуальна для багатьох застосувань. Проте можна привести приклади прогрпм, в яких час декомпресії не критичний.

. Масштабування зображень. Дана вимогу передбачає легкість зміни розмірів зображення до розмірів вікна активного застосування. Річ у тому, що одні алгоритми дозволяють легко масштабувати зображення прямо під час декомпресії, тоді як інші не тільки не дозволяють легко масштабувати, але і збільшують вірогідність появи неприємних артефактів після застосування стандартних алгоритмів масштабування до декомпресованого зображення.

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

. Стійкість до помилок. Дана вимога передбачає локальність порушень в зображенні при псуванні або втраті фрагмента передаваного файлу. Дана можливість використовується при широкомовленій передачі (broadcasting - передача по багатьом адресам) зображень по мережі, тобто в тих випадках, коли неможливо використовувати протокол передачі, що повторно запрошує дані у сервера при помилках. Наприклад, якщо передається відеоряд, то було б неправильно використовувати алгоритм, у якого збій приводив би до припинення правильного показу всіх подальших кадрів. Дана вимога

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

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

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

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

Відмітимо, що характеристики алгоритму, сформульовані вище, залежать від конкретних умов, в які буде поставлений алгоритм. Так, ступінь компресії залежить від того, на якому класі зображень алгоритм тестується. Аналогічно, швидкість компресії нерідко залежить від того, на якій платформі реалізований алгоритм. Перевагу одному алгоритму перед іншим може дати, наприклад, можливість використання в обчисленнях алгоритму технологій нижнього рівня, типу MMX, а це можливо далеко не для всіх алгоритмів. Так, JPEG істотно виграє від застосування технології MMX, а LZW - ні. Таким чином, неможливо скласти універсальний порівняльний опис відомих алгоритмів. Це можна зробити тільки для типових класів програм за умови використання типових алгоритмів на типових платформах. Проте такі дані швидко застарівають.

Зі всіма зробленими вище обмовками, виділимо декілька найбільш важливих для нас критеріїв порівняння алгоритмів компресії, які і використовуватимемо надалі [5].

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

. Клас зображень, на який орієнтований алгоритм.

. Симетричність. Відношення характеристики алгоритму кодування до аналогічної характеристики при декодуванні. Характеризує ресурсомісткість процесів кодування і декодування. Для нас найбільш важливою є симетричність за часом: відношення часу кодування до часу декодування. Іноді нам буде потрібно симетричність по пам'яті.

. Чи є втрати якості? І якщо є, то за рахунок чого змінюється коефіцієнт архівації? Річ у тому, що у більшості алгоритмів стиснення з втратою інформації існує можливість зміни коефіцієнта стиснення.

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

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

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

Один і той же алгоритм часто можна реалізувати різними способами. Багато відомих алгоритмів, такі як RLE, LZW або JPEG, мають десятки реалізацій, що розрізняються. Крім того, у алгоритмів буває декілька явних параметрів, варіюючи які, можна змінювати характеристики процесів архівації і розархівування. При конкретній реалізації ці параметри фіксуються, виходячи з найбільш вірогідних характеристик вхідних зображень, вимог на економію пам'яті, вимог на час архівації і так далі. Тому у алгоритмів одного сімейства кращий і гірший коефіцієнти можуть відрізнятися, але якісно картина не зміниться.

1.2.5 Алгоритми стиснення без втрат

.2.5.1 Алгоритм RLE

Даний алгоритм э надзвичайно простим в реалізації. Групове кодування - від англійського Run Length Encoding (RLE) [4]- один з найстаріших і найпростіших алгоритмів стиснення графіки. Зображення в нім витягується в ланцюжок байт по рядках растру. Сам процес стиснення в RLE відбувається за рахунок того, що в початковому зображенні зустрічаються ланцюжки однакових байт. Заміна їх на пари <лічильник повторень, значення> зменшує надмірність даних.

Кодування довжин ділянок (або повторень) може бути достатньо ефективним при стисненні двійкових даних, наприклад, чорно-білих зображень що містять безліч прямих ліній і однорідних ділянок, схем і т.п.

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

Припустимо, що потрібно закодувати двійкове зображення розміром 8 х 8 елементів.

Проскануємо це зображення по рядках (двом обєктам на зображенні відповідатимуть 0 і 1), в результаті отримаємо двійковий вектор даних, наприклад:

довжиною 64 біта (швидкість початкового коду складає 1 біт на елемент зображення).

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

Таблиця 1.1. Кодові слова RLE

Довжина ділянкиКодове слово4011071103111

Тепер цю послідовність, в якій помітна певна повторюваність (одиниць і четвірок значно більше, чим інших символів), можна закодувати яким-небудь статистичним кодом, наприклад, кодом Хаффмена без пам'яті, що має таблицю кодування (табл. 1.1)

Для того, щоб вказати, що кодована послідовність починається з нуля, додамо на початок кодового слова префіксний символ 0. В результаті отримаємо кодове слово довжиною в 34 біта, тобто результуюча швидкість коду складе 34/64, або трохи більше 0,5 біт на елемент зображення. При стисненні зображень більшого розміру і повторюванні елементів, що містять множину, ефективність стиснення може виявитися істотно вищою.

Нижче наведений інший приклад використання кодування довжин повторень, коли в цифрових даних зустрічаються ділянки з великою кількістю нульових значень. Кожного разу, коли в потоці даних зустрічається нуль, він кодується двома числами. Перше - 0, такий, що є прапором початку кодування довжини потоку нулів, і друге - кількість нулів в черговій групі (Рис. 1.5). Якщо середнє число нулів в групі більше двох, матимемо стиснення. З іншого боку, велике число окремих нулів може привести навіть до збільшення розміру кодованого файлу.

Рис. 1.5 . Графічне зображення алгоритму кодування по довжині повторів нулів

1.2.5.2 Метод LZW

Метод LZW (Лємпеля-Зіва-Уелча) був розроблений у 1984 році Тері Уелчем на основі метода LZ (Лємпеля-Зіва) [4].являється словниковим методом компресії, у якому використовується словник послідовностей символів, які зустрічалися раніше в вихідному тексті. На виході компресора ці послідовності представляються у вигляді міток. Мітка LZW складається з вказівника на місце послідовності в словнику. Процес стиснення виглядає досить просто. Считуються послідовно символи вхідного потоку і перевіряється, чи є в створеній таблиці рядків такий рядок. Якщо рядок є, то ми считуємо наступний символ, а якщо рядка немає, то заносимо в потік код для попереднього знайденого рядка, заносимо рядок в таблицю і починаємо пошук знову.

Хай ми стискаємо послідовність 45, 55, 55, 151, 55, 55, 55. Тоді, згідно викладеному вище алгоритму, ми помістимо у вихідний потік спочатку код очищення <256>, потім додамо до спочатку порожнього рядка 45 і перевіримо, чи є рядок 45 в таблиці. Оскільки ми при ініціалізації занесли в таблицю всі рядки з одного символу, то рядок 45 є в таблиці. Далі ми читаємо наступний символ 55 з вхідного потоку і перевіряємо, чи є рядок 45, 55 в таблиці. Такого рядка в таблиці поки немає. Ми заносимо в таблицю рядок 45, 55 (з першим вільним кодом 258) і записуємо в потік код <45>. Можна коротко представити архівацію так:

45 - є в таблиці;

45, 55 - ні. Додаємо в таблицю <258>45, 55. У потік: <45>;

55, 55 - ні. У таблицю: <259>55, 55. У потік: <55>;

55, 151 - ні. У таблицю: <260>55, 151. У потік: <55>;

151, 55 - ні. У таблицю: <261>151, 55. У потік: <151>;

55, 55 - є в таблиці;

55, 55, 55 - ні. У таблицю: 55, 55, 55 <262>. У потік: <259>;

Послідовність код для даного прикладу, що потрапляють у вихідний потік: <256>, <45>, <55>, <55>, <151>, <259>.

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

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

Принцип роботи алгоритму проілюстровано на рис. 1.6 [1].

Рис. 1.16. Процедура кодування відповідно до алгоритму LZW

1.2.5.3 Класичний метод Хаффмена

Метод Хаффмана - це статистичний метод, що будує коди змінної довжини з мінімальною середньою довжиною. Базуючись на ймовірності появи символів алфавіту в тексті. Базується на створенні так званого дерева Хаффмана, що будується за наступним алгоритмом [6]:

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

) Вибираються два листки дерева з найменшою вагою та створюється їх предок з вагою, рівною їх сумарній вазі.

) Предок додається до списку вільних вузлів, а двоє його нащадків видаляються з цього списку.

) Одній дузі (гілці), що виходить з предка, приписується значення 1, а іншій - 0.

) Кроки 2-4 повторюються до тих пір, доки не залишиться єдиний вільний вузол - корінь дерева.

) Побудова коду символа здійснюється спуском по дереву від кореня до відповідного листа.

Зауважимо!!! Дані з рівноможливими символами не стискаються методом Хаффмана.

Краще за все проілюструвати даний алгоритм на простому прикладі, наведеному у наступному пункті.

Проілюструємо принцип роботи методу прикладом. Маємо п'ять символів з ймовірностями, заданими на рис. 1.7.

Рис. 1.7. Дерево Хаффмена

Символи об'єднуються в пари згідно алгоритму, наведеному раніше, в наступній послідовності:

) а4 об'єднується з а5 й обидва замінюються комбінованим символом а45 з ймовірністю 0.2;

) залишились символ а1 з ймовірністю 0.4 та три символи а2, а3, а45 з ймовірностями 0.2. Довільно вибираємо а3 та а45, об'єднуємо їх та замінюємо комбінованим символом а345 з ймовірністю 0.4;

) маємо три символи а1, а2, а345 з ймовірностями 0.4 ,0.2 та 0.4, відповідно. Вибираємо та об'єднуємо символи а2 та а345 в комбінований символ а2345 з ймовірністю 0.6;

) нарешті, об'єднуємо символи а1 та а2345 й замінюємо їх на а12345 з ймовірністю 1.

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

Зчитуючи коди від кореня дерева Хаффмана до відповідних вузлів, отримаємо значеня, наведені в табл. 1.2.

Таблиця 1.2. Коди хаффмена

аіКода10а210а3111а41101а51100

Зауважимо, що кожен з кодів не являється префіксом іншого (правило префікса), й символи з вищою ймовірністю представлені коротшими кодами.

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

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

Далі зчитується другий біт й відбувається просування по наступній гілці у напрямку до листя.

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

1.2.5.4 JBIG

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

Алгоритм побудований на базі Q-кодера, патентом на який володіє IBM. Q-кодер, так само як і алгоритм Хаффмана, використовує для частіше за символи, що з'являються, короткі ланцюжки, а для що рідше з'являються - довгі. Проте, на відміну від нього, в алгоритмі використовуються і послідовності символів.

1.2.5.5 Lossless JPEG

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

1.2.6 Алгоритми стиснення з втратами

.2.6.1 Алгоритм JPEG

Однимими з найпоширеніших на сьогоднішній день кодерів стиснення відеозображень є JPEG, що розроблявся об'єднаною міжнародною групою експертів по обробці даних відеозображень (Joint Photographic Experts Group) спільно з комітетом СCITT і міжнародною організацією стандартизації ISO в 1991 році. Перший кодер JPEG розроблявся, як алгоритм стиснення для неперервно-тонових 24-бітових зображень [9].

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

У цілому алгоритм заснований на дискретному косинусоїдальному перетворенні (надалі ДКП), застосовуваному до матриці зображення для одержання деякої нової матриці коефіцієнтів. Для одержання вихідного зображення застосовується зворотне перетворення.

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

Для цього використовується квантування коефіцієнтів (quantization). У найпростішому випадку - це арифметичне побітове зрушення вправо. При цьому перетворенні губиться частина інформації, але може досягатися більший ступінь стиснення.

Отже, розглянемо алгоритм докладніше. Нехай ми стискаємо 24-бітне зображення.

Етап 1. Переводимо зображення з колірного простору RGB, з компонентами, відповідальними за червону (Red), зелену (Green) і синю (Blue) складові кольору крапки, у колірний простір YCrCb (іноді називають YUV).

У ньому Y - яскравісна складова, а Сг, Сb - компоненти, відповідальні за кольори (хроматичний червоний і хроматичний синій). За рахунок того, що людське око менш чутливе до кольорів, ніж до яскравості, з'являється можливість архівувати масиви для Сг і Сb компонент із більшими втратами й, відповідно, більшими ступенями стиснення. Подібне перетворення вже давно використовується в телебаченні. На сигнали, відповідальні за кольори, там виділяється більш вузька смуга частот.

Спрощено переклад з колірного простору RGB у колірний простір YCrCb можна представити у вигляді матриці переходу:

Зворотнє перетворення здійснюється множенням вектору YUV на обернену матрицю:

Етап 2. Розбиваємо вихідне зображення на матриці 8x8. Формуємо з кожної третьої робочої матриці ДКП - по 8 біт окремо для кожного компонента.

При більших ступенях стиснення цей крок може виконуватися трохи складніше. Зображення ділиться по компоненті Y - як і в першому випадку, а для компонентів Сг і Сb матриці набираються через рядок і через стовпець.

Тобто з вихідної матриці розміром 16x16 виходить тільки одна робоча матриця ДКП.

При цьому, як неважко помітити, ми втрачаємо 3/4 корисної інформації про колірні складові зображення й одержуємо відразу стиснення у два рази. Ми можемо робити так завдяки роботі в просторі YCrCb. На результуючому RGB зображенні, як показала практика, це позначається несильно.

Етап 3. У спрощеному вигляді ДКП при п=8 можна представити так:

, (1.8)

де ,

а .

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

Етап 4. Проводимо квантування. У принципі, це просто розподіл робочої матриці на матрицю квантування поелементно. Для кожного компонента (Y, U і V), у загальному випадку, задається своя матриця квантування q[u,v] (далі МК).

(1.9)

На цьому кроці здійснюється керування ступенем стиснення, і відбуваються самі більші втрати. Зрозуміло, що, задаючи МК із більшими коефіцієнтами, ми одержимо більше нулів і, отже, більший ступінь стиснення. У стандарт JPEG включені рекомендовані МК, побудовані дослідним шляхом. Матриці для більшого або меншого ступеня стиснення одержують шляхом множення вихідної матриці на деяке число gamma.

Із квантуванням зв'язані й специфічні ефекти алгоритму. При більших значеннях коефіцієнта gamma втрати в низьких частотах можуть бути настільки великі, що зображення розпадеться на квадрати 8x8. Втрати у високих частотах можуть виявитися в так званому «ефекті Гіббса», коли навколо контурів з різким переходом кольорів утвориться своєрідний «німб».

Етап 5. Переводимо матрицю 8x8 в 64-елементний вектор за допомогою «зиґзаґ»-сканування, тобто беремо елементи з індексами (0,0), (0,1), (1,0), (2,0)... (рис.1.8).

Рис. 1.8. Зиґзаґ-сканування

Таким чином, на початку вектора ми одержуємо коефіцієнти матриці, що відповідають низьким частотам, а наприкінці - високим.

Етап 6. Згортаємо вектор за допомогою алгоритму групового кодування.

При цьому одержуємо пари типу (пропустити, число), де «пропустити» є лічильником нулів, що пропускають, а «число»- значення, які необхідно поставити в наступну ячійку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1... буде згорнутий у пари (0,42) (0,3) (3,-2) (4,1)....

Етап 7. Згортаємо отримані пари кодуванням по Хаффману з фіксованою таблицею.

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

Основні кроки стиснення за методом JPEG, представлені у вигляді структурно-логічної схеми на рис. 1.9.

Рис. 1.9. Блок-структурна схема реалізації методу JPEG

Істотними позитивними сторонами алгоритму є те, що:

1. Задається ступінь стиснення.
2. Вихідне кольорове зображення може мати 24 біта на
   крапку.
   

Негативними сторонами алгоритму є те, що:

3. При підвищенні ступеня стиснення зображення розпадається
   на окремі квадрати (8x8). Це пов'язане з тим, що зявляються більші втрати в низьких частотах при квантуванні, і відновити вихідні дані стає неможливо.
   
4. Проявляється ефект Гіббса - ореоли по межах різких
   переходів кольорів.
   
Як уже говорилося, стандартизований JPEG був в 1991 році. Але вже тоді існували алгоритми, що стискають сильніше при менших втратах якості. Справа в тому, що дії розроблювачів стандарту були обмежені потужністю існуючої на той момент техніки. Тобто навіть на персональному комп'ютері алгоритм повинен був працювати менше хвилини на середньому зображенні, а його апаратна реалізація повинна бути відносно простою і дешевою. Алгоритм повинен був бути симетричним (час розархівації приблизно дорівнює часу архівації). Виконання останньої вимоги уможливило появу таких пристроїв, як цифрові фотоапарати, що знімають 24-бітові фотографії на 8 - 256 Мб флеш карту. Потім ця карта вставляється в розєм на вашому ноутбуці й відповідна програмі дозволяє зчитати зображення. Чи не правда, що якби алгоритм був несиметричний, було б неприємно довго чекати, поки апарат «перезарядиться»- стисне зображення.

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

Широке застосування JPEG довгий час зумовлювалося, мабуть, лише тим, що він оперує 24-бітними зображеннями. Тому для того, щоб із прийнятною якістю подивитися картинку на звичайному моніторі в 256-кольоровій палітрі, було необхідне застосування відповідних алгоритмів і, отже, певний час. У програмах, орієнтованих на прискіпливого користувача, таких, наприклад, як ігри, подібні затримки неприйнятні. Крім того, якщо наявні у вас зображення, припустимо, в 8-бітному форматі GIF перевести в 24-бітний JPEG, а потім назад в GIF для перегляду, то втрата якості відбудеться двічі при обох перетвореннях. Проте, виграш у розмірах архівів найчастіше настільки великий (в 3-20 разів), а втрати якості настільки малі, що зберігання зображень в JPEG виявляється дуже ефективним.

.2.6.2 Алгоритм JPEG 2000

Алгоритм JPEG-2000 розроблений тією же групою експертів в області фотографії, що й JPEG. Формування JPEG як міжнародного стандарту було закінчено в 1992 році [4,10]. В 1997 стало ясно, що необхідно новий, більше гнучкий і потужний стандарт, що і був дороблений до зими 2000 року. Основні відмінності алгоритму в JPEG 2000 від алгоритму в JPEG полягають у наступному:

1.Краща якість зображення при сильному ступені стиснення.

1. Підтримка кодування окремих областей із кращою якістю. Відомо, що окремі області зображення критичні для сприйняття людиною, у той час як якістю інших можна знехтувати. При «ручній» оптимізації збільшення ступеня стиснення проводиться доти, поки не буде втрачена якість у якійсь важливій частині зображення. В даному методі з'являється можливість задати якість у критичних областях, стиснувши інші області сильніше, тобто одержується ще більший остаточний ступінь стиснення при суб'єктивно рівній якості зображення.

3.Основний алгоритм стиснення замінений на wavelet. Крім зазначеного підвищення ступеня стиснення це дозволило позбутися від 8-піксельної блочності, що виникає при підвищенні ступеня стиснення.

4.Для підвищення ступеня стиснення в алгоритмі використовується арифметичне кодування.

5.Підтримка стиснення однобітних (2-кольорових) зображень. Для збереження однобітних зображень (малюнки тушшю, відсканований текст і т.п.) раніше повсюди рекомендувався формат GIF, оскільки стиснення із використанням ДКП досить неефективно стискає зображеня із різкими переходами кольорів. В JPEG при стисненні 1-бітна картинка приводилася до 8-бітної, тобто збільшувалася в 8 разів, післе чого робилася спроба стиснення. Зараз можна рекомендувати JPEG 2000 як універсальний алгоритм.

6.На рівні формату підтримується прозорість. Крім того, підтримується не тільки 1 біт прозорості (піксель прозорий/непрозорий), а окремий канал, що дозволить задавати плавний перехід від непрозорого зображення до прозорого фону.

7.Крім того, на рівні формату підтримуються включення в зображення інформації про копірайт, підтримка стійкості до бітових помилок при передачі й широкомовленні, можна запитувати для декомпресії або обробки зовнішні засоби (plug-ins), можна включати в зображення його опис, інформацію для пошуку й т.д.

Базова схема JPEG-2000 дуже схожа на базову схему JPEG. Відмінності полягають у наступному:

1. Замість дискретного косинусного перетворення (DCT) використається дискретне вейвлет-перетворення (DWT).
2. Замість кодування по Хаффмену використовується арифметичне стиснення.
3. В алгоритм закладене керування якістю областей зображення.

4) Не використовується явно дискретизація компонентів U і V після перетворення колірних просторів, оскільки при DWT можна досягти того ж результату, але більш акуратно.

Блок-структурна схема даного алгоритму приведена на рис. 1.10.

Рис. 1.10. Блок-структурна схема реалізації методу JPEG-2000

Розглянемо алгоритм по кроках.

Етап 1. В JPEG-2000 передбачене зрушення яскравості (DC level shift) кожного компонента (RGB) зображення перед перетворенням в YUV. Це робиться для вирівнювання динамічного діапазону (наближення до 0 гістограми частот), що приводить до збільшення ступеня стиснення. Формулу перетворення можна записати як:

(1.10)

При відновленні зображення виконується зворотне перетворення:

. (1.11)

Етап 2. Переводимо зображення з колірного простору RGB, з компонентами, відповідальними за червону (Red), зелену (Green) і синю (Blue) складові кольору точки, у колірний простір YUV. Цей крок аналогічний JPEG , за тим виключенням, що крім перетворення із втратами передбачено також і перетворення без втрат.

Етап 3. Дискретне wavelet перетворення (DWT) також може бути двох видів - для випадку стиснення із втратами й для стиснення без втрат.

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

, (1.12)

. (1.13)

Оскільки більшість , крім i=0, рівні 0, то можна переписати наведені формули з меншою кількістю операцій. Для простоти розглянемо випадок стиснення без втрат.

, (1.14)

, (1.15)

Легко показати, що даний запис можна еквівалентно переписати, зменшивши ще втроє кількість операцій множення й розподіли (однак тепер необхідно буде підрахувати спочатку всі непарні у). Додамо також операції округлення до найближчого цілого, що не перевищує задане число а, позначені як [a]:

, (1.16)

, (1.17)

Етап 4. Так само, як і в алгоритмі JPEG, після DWT застосовується квантування.

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

Етап 5. Для стиснення отриманих масивів даних в JPEG 2000 використовується варіант арифметичного стиснення, названий MQ-кодер, прообраз якого (QM-кодер) розглядався ще в стандарті JPEG, але реально не використовувався через патентні обмеження.

1.2.7 Зведені характеристики існуючих методів стиснення зображень

В табл. 1.3 наведені основні параметри, що характеризу.ть методи стиснення зображень, описані вище [4].

Таблиця 1.3. Порівняльна хаарктеристика методів стиснення зображень

АлгоритмК-ти стисненняСиметричність за часомНа які зображення орієнтованийВтратиRLE32, 2, 0.513,4-х бітніНіLZW1000, 4, 5/71.2-31-8 бітніНіХаффмана8, 1.5, 11-1.58-бітніНіJBIG2-30 разів11-бітніНіLossless JPEG2 рази124-бітні,сіріНіJPEG2-200 разів124-бітні, сіріТакJPEG-20002-200 разів1-1.524-бітні, сірі,1-бітніТак

1.3 Висновки по розділу

В даному розділі дипломної роботи були викладені основні поняття теорії стиснення. Задачу компресії даних ідентифіковано з одним з найважливіших завдань теорії інформації - кодуванням джерела.

Описані поняття енторопії, основні класифікаційні характеристики методів стиснення, розглянуті відмінності між двома основними класами методів компресії - з втратами та без втрат.

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

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

Аналіз отриманих даних дозволяє стверджувати, що проаналізовані методи мають ряд недоліків:

1.методи, які забезпечують досить високий ступінь стиснення призводять до значних втрат якості зображення із збільшенням коефіцієнта стисненя (JPEG, JPEG-2000);

2.на потивагу їм, методи стиснення без втрат не забезпечують достатнього ступеня стиснення (RLE, LZW, Хаффмана, Lossless JPEG );

.методи які забезпечують як прийнятний рівень якості зображень, так і достатній ступінь стиснення, орієнтовані на вузький клас зображень (JBIG).

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

стискування компресія втрата якість зображення

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ТА ЛІТЕРАТУРИ

1. Юдін О.К. Кодування в інформаційно-комунікаційних мережах: - Монографія. - К.: НАУ, 2007. - 308с

. Фомин А.А. Основы сжатия информации. - С.-П.: СПГТУ, 1998. - с.27-30.

. Свириденко В.А. Анализ систем со сжатием данных ? М.: Связь, 1977. ? 184 с.

. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. - 384 с.

. Методы передачи изображений. Сокращение избыточности. / Под. ред. У.К. Прэтта. ? М.: Радио и связь, 1983. ? 263 с.

. Королев А.В., Лебедев С.М., Паржин Ю.В. Методы сжатия графической информации. Тез. докл. ХIII Всесоюз. симпозиума по пробл. избыточности в информ. системах. - Л.: ЛИАП. - 1983. - Ч.6. - С. 82- 84.

. Хэмминг Р.В. Теория кодирования и теория информации / Под. ред. Б.С. Цыбакова. ? Пер. с англ. С.И. Гельфанда. ? М.: Радио и связь, 1983. ? 176 с.

. Скляр Б. Цифровая связь. Теоретические основы и практическое применение / Пер. с англ. - М.: Изд. дом Вильямс, 2004. - 1104 с.

. Д. Селомон. Стиснення даних, зображень і звуку. - М.: Техносфера, 2006. - 386с.

. Юдин А.К., Пуха Д.А. Методы и алгоритмы эффективного сжатия видеоданных на базе стандарта JPEG 2000. // Защита информации: сборник научных трудов, выпуск №13. - К.: НАУ, 2006. - С. 209-214.

. Ефимов В.М., Золотухин Ю.Н., Колесников А.Н. Оценка эффективности некоторых алгоритмов сокращения избыточности информации при абсолютной точности воспроизведения. // Автометрия. - 1991. - № 6. - с. 50

. Юдін О.К. Обґрунтування взаємооднозначності двоознакового структурного представлення двійкових даних у поліадичному просторі. // Науковий журнал Вісник НАУ, №1. К.: НАУ - 2007. - С. 38-42.

. Баранник В.В., Юдин А.К. Двухпризнаковое структурное кодирование массивов двоичных данных. // Всеукраинский межведомственный научно-технический сборник Автоматизированные системы управления и приборы автоматики, №133. - Х.: ХНУРЭ, 2005 - C. 64-72.

. Баранник В.В., Юдин А.К. Оценка эффективности структурного кодирования двоичных данных в полиадическом пространстве. // Науковий журнал Інформаційно-керуючі системи на залізничному транспорті , №3 - Х.: 2006. - С. 3-11.

. Юдін. О.К. Методи структурного кодування даних в автоматизованих системах управління. - К.: НАУ, 2007.

. Юдін О.К. Обгрунтування ефективності двоознакового структурного кодування у двійковому поліадичному просторі. Проблеми інформатизації та управління: Збірник наукових праць: Випуск 2(17). - К.:НАУ, 2006. - С.137-141

. Макаров Е. Mathcad. Учбовий курс. - С.-П.: Питер, 2008. - 384с.

Додаток А

Програмна реалізація кодера стиску зображень з урахуванням ДСК (codec.xcmd )

Структурно-логічна модель кодера стиску інформаційних потоків даних Вміст ВСТУП РОЗДІЛ 1. А

Больше работ по теме: