Структурно-логічна модель кодера стиску інформаційних потоків даних
Розкриття вмісту теорії стискування і опис класифікаційних характеристик методів компресії з втратами і без втрат. Оцінка втрат якості зображень при їх стискуванні за допомогою програм-кодеків. Розрахунок математичної моделі кодера стискання зображень.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | украинский |
| Дата добавления | 25.11.2012 |
| Размер файла | 1,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1
Структурно-логічна модель кодера стиску інформаційних потоків даних
Вміст
ВСТУП
РОЗДІЛ 1. АНАЛІЗ ІСНУЮЧИХ КОДЕРІВ СТИСКУ ІНФОРМАЦІЙНИХ ПОТОКІВ
1.1 Розгляд основних положень теорії стиснення
1.2 Аналіз існуючих методів стиснення зображень
1.2.1 Класи зображень
1.2.2 Класи кодеків
1.2.3 Вимоги програм до алгоритмів компресії
1.2.4 Критерії порівняння алгоритмів
1.2.5 Алгоритми стиснення без втрат
1.2.5.1 Алгоритм RLE
1.2.5.2 Метод LZW
1.2.5.3 Класичний метод Хаффмена
1.2.5.4 JBIG
1.2.5.5 Lossless JPEG
1.2.6 Алгоритми стиснення з втратами
1.2.6.1 Алгоритм JPEG
1.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.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]:
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. Півтонове зображення. Кожен піксел такого зображення може мати 2n значень від 0 до 2n - 1, що позначають одну з 2n градацій сірого (або іншого) кольору. Число n зазвичай зрівняне з розміром байта, тобто, воно дорівнює 4, 8, 12, 16, 24 або інше кратне 4 або 8 число. Безліч найбільш значущих бітів всіх пікселів утворює значущу бітову площину або шар зображення. Отже, півтонове зображення з шкалою з 2n рівнів складене з n бітових шарів.
3. Кольорове зображення. Існує декілька методів задання кольору, але в кожному з них беруть участь три параметри. Отже, кольоровий піксел складається з трьох частин, зазвичай - з трьох байтів. Типовими колірними моделями є RGB, CMYK, HLS.
4. Зображення з безперервним тоном. Цей тип зображення може мати багато схожих кольорів (або півтонів). Коли сусідні піксели відрізняються всього на одну одиницю, око практично не здатне розрізнити їх кольори. В результаті такі зображення можуть містити області, в яких колір здається оку неперервним. В цьому випадку піксел представляється або великим числом ( у півтоновому випадку) або трьома компонентами (у разі кольорового зображення). Зображення з безперервним тоном є природними, зазвичай вони отримуються при зйомці на цифрову камеру або при скануванні фотографій і малюнків.
5. Дискретно-тонове зображення (синтетичне). Звичайно це зображення виходить штучним шляхом. Воно може містити всього декілька або багато кольорів, але в ньому немає шумів і плям природного зображення. Прикладами таких зображень можуть бути креслення штучних об'єктів, механізмів або машин, сторінки тексту, карти або зображення на екрані комп'ютера. Штучні об'єкти, тексти, намальовані лінії мають форму, добре визначувані межі. Вони сильно контрастують на фоні інших чатин зображення. Такі зображення погано стискаються методами з втратами даних, оскільки спотворення всього декількох пікселів букви робить її нерозбірливою, перетворить звичне зображення в абсолютно невиразне. Методи для стиснення зображень з безперервними тонами погано поводяться з чіткими краями дискретно-тонових зображень. Відзначимо, що дискретно-тонові зображення несуть в собі велику надмірність. Багато її фрагментів повторюються багато раз в різних місцях зображення.
6. Зображення, подібні до мультфільмів. Це кольорові зображення, в яких присутні великі області одного кольору. При цьому дотичні області можуть дуже сильно розрізнятися по своєму кольору. Цю властивість можна використовувати для досягнення кращої компресії.
Достатньо складним і цікавим завданням є пошук найкращого алгоритму для конкретного класу зображень.
1.2.2 Класи кодеків
Розглянемо наступну просту класифікацію програм, що використовують алгоритми компресії [4]:
Клас 1. Характеризуються високими вимогами до часу стиснення і відновлення. Часто необхідне проглядання зменшеної копії зображення і пошук в базі даних зображень. Приклади: Видавничі системи, причому як ті, що готують якісні публікації (журнали) із високою якістю зображень і використанням алгоритмів стиснення без втрат, так і ті, що видають газети, і інформаційні вузли в WWW, де є можливість оперувати зображеннями меншої якості і використовувати алгоритми стиснення з втратами. У подібних системах доводиться мати справу з повнокольоровими зображеннями самого різного розміру (від 640х480 -- формат цифрового фотоапарата, до 3000х2000) і з великими двокольоровими зображеннями. Оскільки ілюстрації займають левову частку від загального об'єму матеріалу в документі, проблема зберігання стоїть дуже гостро. Проблеми також створює велика різнорідність ілюстрацій (доводиться використовувати універсальні алгоритми).
Клас 2. Характеризується високими вимогами до ступеня стиснення і часу відновлення. Час компресії ролі не грає. Іноді від алгоритму компресії також вимагається легкість масштабування зображення під конкретний дозвіл монітора у користувача. Приклад: Довідники і енциклопедії на CD-ROM. З появою великої кількості комп'ютерів, оснащених цим приводом достатньо швидко сформувався ринок програм, що випускаються на лазерних дисках. Не дивлячись на те, що місткість одного диска досить велика, її, як правило, не вистачає. При створенні енциклопедій і ігор велику частину диска займають статичні зображення і відео. Таким чином, для цього класу додатків актуальності набувають істотно асиметричні за часом алгоритми.
Клас 3. Характеризується дуже високими вимогами до ступеня архівації. Програма клієнта отримує від сервера інформацію мережею. Приклад: Нова система “Всесвітня інформаційна павутина” -- WWW. У цій гіпертекстовій системі достатньо активно використовуються ілюстрації. При оформленні інформаційних або рекламних сторінок хочеться зробити їх яскравішими і барвистішими, що природно позначається на розмірі зображень. Найбільше при цьому страждають користувачі, підключені до мережі за допомогою повільних каналів зв'язку. Якщо сторінка WWW перенасичена графікою, то очікування її повної появи на екрані може затягнутися. Оскільки при цьому навантаження на процесор мале, то тут можуть знайти застосування складні алгоритми ефективного стиснення з порівняно великим часом розархівування. Крім того, ми можемо видозмінити алгоритм і формат даних так, щоб проглядати огрублене зображення файлу до його повного отримання.
Можна привести безліч вужчих класів програм. Так, своє застосування машинна графіка знаходить і в різних інформаційних системах. Наприклад, вже стає звичним досліджувати ультразвукові і рентгенівські знімки не на папері, а на екрані монітора. Поступово в електронний вигляд переводять і історії хвороб. Зрозуміло, що зберігати ці матеріали логічніше в єдиній картотеці. При цьому без використання спеціальних алгоритмів велику частину архівів займуть фотографії. Тому при створенні ефективних алгоритмів рішення цієї задачі потрібно врахувати специфіку рентгенівських знімків -- переважання розмитих ділянок.
У геоінформаційних системах -- при зберіганні аерофотознімків місцевості -- специфічними проблемами є великий розмір зображення і необхідність вибірки лише частини зображення на вимогу. Крім того, може знадобитися масштабування. Це неминуче накладає свої обмеження на алгоритм компресії.
1.2.3 Вимоги програм до алгоритмів компресії
У попередньому розділі ми визначили, які програми потребують алгоритмів стиснення зображень. Проте відмітимо, що додаток визначає характер використання зображень (або велика кількість зображень зберігається і використовується, або зображення викачуються по мережі, або зображення великі по розмірах, і нам необхідна можливість отримання лише частини...). Характер використання зображень задає ступінь важливості наступних нижче суперечливих вимог до алгоритму [4]:
1. Високий ступінь компресії. Відмітимо, що далеко не для всіх програм актуальний високий ступінь компресії. Крім того, деякі алгоритми дають краще співвідношення якості до розміру файлу при високих ступенях компресії, проте програють іншим алгоритмам при низьких ступенях.
2. Висока якість зображень. Виконання цієї вимоги безпосередньо суперечить виконанню попередньої.
3. Висока швидкість компресії. Ця вимога для деяких алгоритмів з втратою інформації є взаємовиключною з першими двома. Інтуїтивно зрозуміло, що чим більше часу ми аналізуватимемо зображення, намагаючись отримати найвищий ступінь компресії, тим краще буде результат. І, відповідно, чим менше ми часу витратимо на компресію (аналіз), тим нижче буде якість зображення і більше його розмір.
4. Висока швидкість декомпресії. Достатньо універсальна вимога, актуальна для багатьох застосувань. Проте можна привести приклади прогрпм, в яких час декомпресії не критичний.
5. Масштабування зображень. Дана вимогу передбачає легкість зміни розмірів зображення до розмірів вікна активного застосування. Річ у тому, що одні алгоритми дозволяють легко масштабувати зображення прямо під час декомпресії, тоді як інші не тільки не дозволяють легко масштабувати, але і збільшують вірогідність появи неприємних артефактів після застосування стандартних алгоритмів масштабування до декомпресованого зображення.
6. Можливість показати огрублене зображення (низького дозволу), використавши тільки початок файлу. Дана можливість актуальна для різного роду мережних програм, де перекачування зображень може зайняти достатньо великий час, і бажано, отримавши початок файлу, коректно показати preview. Відмітимо, що примітивна реалізація вказаної вимоги шляхом записування в початок зображення його зменшеної копії помітно погіршить ступінь компресії.
7. Стійкість до помилок. Дана вимога передбачає локальність порушень в зображенні при псуванні або втраті фрагмента передаваного файлу. Дана можливість використовується при широкомовленій передачі (broadcasting -- передача по багатьом адресам) зображень по мережі, тобто в тих випадках, коли неможливо використовувати протокол передачі, що повторно запрошує дані у сервера при помилках. Наприклад, якщо передається відеоряд, то було б неправильно використовувати алгоритм, у якого збій приводив би до припинення правильного показу всіх подальших кадрів. Дана вимога
8. Урахування специфіки зображення. Вищий ступінь архівації для класу зображень, які статистично частіше застосовуватимуться в в даній програмі.
9. Схильність до редагування. Під схильністю до редагування розуміється мінімальний ступінь погіршення якості зображення при його повторному збереженні після редагування. Багато алгоритмів з втратою інформації можуть істотно зіпсувати зображення за декілька ітерацій редагування.
10. Невелика вартість апаратної реалізації. Ефективність програмної реалізації. Дані вимоги до алгоритму реально пред'являють не тільки виробники ігрових приставок, але і виробники багатьох інформаційних систем. Очевидно, що для конкретної задачі нам будуть дуже важливі одні вимоги і менш важливі (і навіть абсолютно байдужі) інші.
1.2.4. Критерії порівняння алгоритмів
Відмітимо, що характеристики алгоритму, сформульовані вище, залежать від конкретних умов, в які буде поставлений алгоритм. Так, ступінь компресії залежить від того, на якому класі зображень алгоритм тестується. Аналогічно, швидкість компресії нерідко залежить від того, на якій платформі реалізований алгоритм. Перевагу одному алгоритму перед іншим може дати, наприклад, можливість використання в обчисленнях алгоритму технологій нижнього рівня, типу MMX, а це можливо далеко не для всіх алгоритмів. Так, JPEG істотно виграє від застосування технології MMX, а LZW - ні. Таким чином, неможливо скласти універсальний порівняльний опис відомих алгоритмів. Це можна зробити тільки для типових класів програм за умови використання типових алгоритмів на типових платформах. Проте такі дані швидко застарівають.
Зі всіма зробленими вище обмовками, виділимо декілька найбільш важливих для нас критеріїв порівняння алгоритмів компресії, які і використовуватимемо надалі [5].
1. Гірший, середній і кращий коефіцієнти стискування. Тобто частка, на яку зросте зображення, якщо початкові дані будуть якнайгіршими; якийсь середньостатистичний коефіцієнт для того класу зображень, на який орієнтований алгоритм; і, нарешті, кращий коефіцієнт. Останній необхідний лише теоретично, оскільки показує ступінь стиснення якнайкращого (як правило, абсолютно чорного) зображення, іноді фіксованого розміру.
2. Клас зображень, на який орієнтований алгоритм.
3. Симетричність. Відношення характеристики алгоритму кодування до аналогічної характеристики при декодуванні. Характеризує ресурсомісткість процесів кодування і декодування. Для нас найбільш важливою є симетричність за часом: відношення часу кодування до часу декодування. Іноді нам буде потрібно симетричність по пам'яті.
4. Чи є втрати якості? І якщо є, то за рахунок чого змінюється коефіцієнт архівації? Річ у тому, що у більшості алгоритмів стиснення з втратою інформації існує можливість зміни коефіцієнта стиснення.
5. Характерні особливості алгоритму і зображень, до яких його застосовують. Тут можуть указуватися найбільш важливі для алгоритму властивості, які можуть визначними стати при його виборі.
Використовуючи дані критерії, приступимо до розгляду алгоритмів архівації зображень.
Перш, ніж безпосередньо почати розмову про алгоритми, хотілося б зробити обмовку.
Один і той же алгоритм часто можна реалізувати різними способами. Багато відомих алгоритмів, такі як RLE, LZW або JPEG, мають десятки реалізацій, що розрізняються. Крім того, у алгоритмів буває декілька явних параметрів, варіюючи які, можна змінювати характеристики процесів архівації і розархівування. При конкретній реалізації ці параметри фіксуються, виходячи з найбільш вірогідних характеристик вхідних зображень, вимог на економію пам'яті, вимог на час архівації і так далі. Тому у алгоритмів одного сімейства кращий і гірший коефіцієнти можуть відрізнятися, але якісно картина не зміниться.
1.2.5 Алгоритми стиснення без втрат
1.2.5.1 Алгоритм RLE
Даний алгоритм э надзвичайно простим в реалізації. Групове кодування -- від англійського Run Length Encoding (RLE) [4]-- один з найстаріших і найпростіших алгоритмів стиснення графіки. Зображення в нім витягується в ланцюжок байт по рядках растру. Сам процес стиснення в RLE відбувається за рахунок того, що в початковому зображенні зустрічаються ланцюжки однакових байт. Заміна їх на пари <лічильник повторень, значення> зменшує надмірність даних.
Кодування довжин ділянок (або повторень) може бути достатньо ефективним при стисненні двійкових даних, наприклад, чорно-білих зображень що містять безліч прямих ліній і однорідних ділянок, схем і т.п.
Ідея стиснення даних на основі кодування довжин повторень полягає в тому, що замість кодування власне дані піддають кодуванню числа, що відповідають довжинам ділянок, на яких дані зберігають незмінне значення.
Припустимо, що потрібно закодувати двійкове зображення розміром 8 х 8 елементів.
Проскануємо це зображення по рядках (двом об'єктам на зображенні відповідатимуть 0 і 1), в результаті отримаємо двійковий вектор даних, наприклад:
довжиною 64 біта (швидкість початкового коду складає 1 біт на елемент зображення).
Виділимо у векторі X ділянки, на яких дані зберігають незмінне значення, і визначимо їх довжини. Результуюча послідовність довжин ділянок - позитивних цілих чисел, що відповідають початковому вектору даних , - матиме вид .
Таблиця 1.1. Кодові слова RLE
|
Довжина ділянки |
Кодове слово |
|
|
4 |
0 |
|
|
1 |
10 |
|
|
7 |
110 |
|
|
3 |
111 |
Тепер цю послідовність, в якій помітна певна повторюваність (одиниць і четвірок значно більше, чим інших символів), можна закодувати яким-небудь статистичним кодом, наприклад, кодом Хаффмена без пам'яті, що має таблицю кодування (табл. 1.1)
Для того, щоб вказати, що кодована послідовність починається з нуля, додамо на початок кодового слова префіксний символ 0. В результаті отримаємо кодове слово довжиною в 34 біта, тобто результуюча швидкість коду складе 34/64, або трохи більше 0,5 біт на елемент зображення. При стисненні зображень більшого розміру і повторюванні елементів, що містять множину, ефективність стиснення може виявитися істотно вищою.
Нижче наведений інший приклад використання кодування довжин повторень, коли в цифрових даних зустрічаються ділянки з великою кількістю нульових значень. Кожного разу, коли в потоці даних зустрічається “нуль”, він кодується двома числами. Перше - 0, такий, що є прапором початку кодування довжини потоку нулів, і друге - кількість нулів в черговій групі (Рис. 1.5). Якщо середнє число нулів в групі більше двох, матимемо стиснення. З іншого боку, велике число окремих нулів може привести навіть до збільшення розміру кодованого файлу.
Рис. 1.5 . Графічне зображення алгоритму кодування по довжині повторів нулів
1.2.5.2 Метод LZW
Метод LZW (Лємпеля-Зіва-Уелча) був розроблений у 1984 році Тері Уелчем на основі метода LZ (Лємпеля-Зіва) [4].
LZW являється словниковим методом компресії, у якому використовується словник послідовностей символів, які зустрічалися раніше в вихідному тексті. На виході компресора ці послідовності представляються у вигляді міток. Мітка 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) Будується список вільних вузлів (листів), утворених символами алфавіту в порядку зменшення їх ймовірностей появи в тексті. Кожен лист має вагу, що дорівнює його ймовірності.
2) Вибираються два “листки” дерева з найменшою вагою та створюється їх предок з вагою, рівною їх сумарній вазі.
3) Предок додається до списку вільних вузлів, а двоє його нащадків видаляються з цього списку.
4) Одній дузі (гілці), що виходить з предка, приписується значення 1, а іншій - 0.
5) Кроки 2-4 повторюються до тих пір, доки не залишиться єдиний вільний вузол - корінь дерева.
6) Побудова коду символа здійснюється спуском по дереву від кореня до відповідного листа.
Зауважимо!!! Дані з рівноможливими символами не стискаються методом Хаффмана.
Краще за все проілюструвати даний алгоритм на простому прикладі, наведеному у наступному пункті.
Проілюструємо принцип роботи методу прикладом. Маємо п'ять символів з ймовірностями, заданими на рис. 1.7.
Рис. 1.7. Дерево Хаффмена
Символи об'єднуються в пари згідно алгоритму, наведеному раніше, в наступній послідовності:
1) а4 об'єднується з а5 й обидва замінюються комбінованим символом а45 з ймовірністю 0.2;
2) залишились символ а1 з ймовірністю 0.4 та три символи а2, а3, а45 з ймовірностями 0.2. Довільно вибираємо а3 та а45, об'єднуємо їх та замінюємо комбінованим символом а345 з ймовірністю 0.4;
3) маємо три символи а1, а2, а345 з ймовірностями 0.4 ,0.2 та 0.4, відповідно. Вибираємо та об'єднуємо символи а2 та а345 в комбінований символ а2345 з ймовірністю 0.6;
4) нарешті, об'єднуємо символи а1 та а2345 й замінюємо їх на а12345 з ймовірністю 1.
Дерево Хаффмана побудовано. Для призначення кодів приписуємо біт 1 гілці, яка виходить з вузла з більшою ймовірністю, іншій приписуємо біт 0.
Зчитуючи коди від кореня дерева Хаффмана до відповідних вузлів, отримаємо значеня, наведені в табл. 1.2.
Таблиця 1.2. Коди хаффмена
|
аі |
Код |
|
|
а1 |
0 |
|
|
а2 |
10 |
|
|
а3 |
111 |
|
|
а4 |
1101 |
|
|
а5 |
1100 |
Зауважимо, що кожен з кодів не являється префіксом іншого (правило префікса), й символи з вищою ймовірністю представлені коротшими кодами.
При декомпресії в стиснутий файл записуються ймовірності символів. Коли декомпресор відновлює вихідні дані, він будує дерево Хаффмана, спираючись на отриману інформацію про ймовірності.
Декомпресор починає з кореня й зчитує перший біт, в залежності від того, 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 Алгоритми стиснення з втратами
1.2.6.1 Алгоритм JPEG
Однимими з найпоширеніших на сьогоднішній день кодерів стиснення відеозображень є JPEG, що розроблявся об'єднаною міжнародною групою експертів по обробці даних відеозображень (Joint Photographic Experts Group) спільно з комітетом СCITT і міжнародною організацією стандартизації ISO в 1991 році. Перший кодер JPEG розроблявся, як алгоритм стиснення для неперервно-тонових 24-бітових зображень [9].
Оперує алгоритм областями 8x8, на яких яскравість і кольори міняються порівняно плавно. Внаслідок цього, при розкладанні матриці такої області в подвійний ряд по косинусах (див. формули нижче) значимими виявляються тільки перші коефіцієнти. Таким чином, стиснення в JPEG здійснюється за рахунок плавності зміни кольорів у зображенні.
У цілому алгоритм заснований на дискретному косинусоїдальному перетворенні (надалі ДКП), застосовуваному до матриці зображення для одержання деякої нової матриці коефіцієнтів. Для одержання вихідного зображення застосовується зворотне перетворення.
ДКП розкладає зображення по амплітудах деяких частот. Таким чином, при перетворенні ми одержуємо матрицю, у якій багато коефіцієнтів або близькі, або дорівнюють нулю. Крім того, завдяки недосконалості людського зору, можна апроксимувати коефіцієнти більш грубо без помітної втрати якості зображення.
Подобные документы
Призначення та область застосування програм, які орієнтовані на перетворення зображень з плоского в об’ємне. Основні стадії формування тривимірного зображення. Класифікація моделей і методів візуалізації. Особливості створення карти глибин по пікселям.
курсовая работа [325,8 K], добавлен 04.06.2010Растрові формати зображень tiff, bmp, pcx, gif, jpeg, png, опис растрової графічної інформації. Зручність та недоліки векторних форматів. Зберігання і обробка зображень, що складаються з ліній, або можуть бути розкладені на прості геометричні об'єкти.
контрольная работа [2,5 M], добавлен 19.09.2009Загальна характеристика теорії редагування зображень, місце у ній растрових зображень. Аналіз переваг та недоліків програм малювання і векторної графіки. Структура, розмір і розширення зображення. Сутність і призначення основних форматів графічних файлів.
реферат [1,1 M], добавлен 13.10.2010Модель обробки файлів растрових зображень. Середній квадрат яскравості. Фільтри для виділення перепадів і границь. Опис та обґрунтування вибору складу технічних та програмних засобів. Опис інтерфейсу програми. Зображення діалогового вікна програми.
курсовая работа [664,3 K], добавлен 30.06.2009Основні теоретичні відомості алгоритмів стиснення зображень: класи зображень та їх представлення в пам'яті, алгоритми та принципи групового кодування. Огляд та аналіз сучасних програмних засобів конвертування. Тестування, опис роботи програмного засобу.
курсовая работа [2,9 M], добавлен 15.03.2014Опис предметної області. Визначення проблеми та постановка задачі. Проектування бази даних. Концептуальна модель. Логічна модель. Фізична модель. Розробка програмних модулів.
курсовая работа [136,3 K], добавлен 14.07.2007Побудова логічно-фізичної моделі даних за допомогою CASE-засобу ERWin. Інструкція користувача програми. Форма "Складський ордер", "Автотранспорт", "Оператори". Логічна та фізична модель бази даних. Форма "Меню", "Акт прийому", форми для введення даних.
курсовая работа [6,6 M], добавлен 14.09.2012Використання CMY та CMYK для опису кольору при отриманні зображень методом поглинання кольорів. Субтрактивні кольори: блакитний (Cyan), пурпурний (Magenta) та жовтий (Yellow). Моделювання розповсюдження світла в об'ємі напівпрозорого середовища.
контрольная работа [3,5 M], добавлен 22.10.2009Області застосування методів цифрової обробки зображень. Динамічний діапазон фотоматеріалу. Графік характеристичної кривої фотоплівки. Загальне поняття про High Dynamic Range Imaging. Тональна компресія та відображення. Головні стегано-графічні методи.
контрольная работа [1,6 M], добавлен 10.04.2014Синтез, обґрунтування і дослідження моделей мультиграничної сегментації на основі зв’язків покриттів. Введення і дослідження операцій на класах еквівалентностей або толерантностей для перетворень результатів сегментації для отримання областей зображень.
автореферат [199,1 K], добавлен 11.04.2009
