ЛЕКЦІЯ 11. СТИСНЕННЯ ТА КОДУВАННЯ ЗОБРАЖЕНЬ
|
Растрові файли мають дуже великі розміри. Якщо знехтувати заголовками файла й іншими неграфічними даними, те його розмір пропорційний кількості пікселів у зображенні і кількості бітів, необхідних для представлення кожного пiксела. Повнокольорове зображення розміром 1024х768 пікселів займає більш двох мегабайт пам'яті, а одна секунда вiдеофільма телевізійної якості в растровому виді вимагає біля тридцятьох мегабайт. Тому жорсткий диск можна заповнити миттєво. Навіть компакт-диск, що вміщає біля 700 мегабайт даних, не настільки великий, щоб помістити такий об'єм інформації. Використовуючи метод, який називається стисненням зображень, можна різко зменшити в розмірі графічні файли. При стисненні графічної інформації використовуються спеціальні прийоми, що зменшують кількість байтів, необхідних для представлення зображення. Ступінь стиснення залежить від методу стиснення і вмісту графічного файла. Як правило графічний файл стискується в п'ять і більш разів. Існують методи, що стискують ще сильніше, але з втратами якості . При відновленні зображення втрачається деяка частина колірної інформації. У підсумку, розпаковане зображення може стати злегка розмитим або знебарвленим. Методи стиснення растрової інформації діляться на дві великі групи: стиснення з втратами і стиснення без втрат. Методи стиснення без втрат дають більш низький коефіцієнт стиснення, але зате зберігають точне значення пікселів вихідного зображення. Методи з втратами дають більш високі коефіцієнти стиснення, але не дозволяють відтворити початкове зображення з точністю до піксела. Для файлів, які формуються програмами автоматизованого проектування, дуже важливо зберегти всю інформацію, тому що втрата хоча б одного біта може змінити зміст усього файла. Зовсім інша справа з растровими даними. Людське око не сприймає всі відтінки кольору в звичайному растровому зображенні. Таким чином, деякі деталі можуть бути опущені без видимого порушення інформаційного змісту зображення. Розглянемо два найбільш розповсюджені методи стиснення зображень. Спочатку познайомимося з одним із варіантів групового кодування (run-lenght encoding - RLE). Ідея методу полягає в тому, що послідовність значень, що повторюються, заміняється парою чисел: одне з них вказує на довжину групи (число повторень даного значення), а інше - на власне це значення. Це дуже загальний і дуже простий метод без втрат. Він використовується в багатьох популярних сьогодні форматах графічних файлів і, зокрема, у PCX і BMP. У його основі лежить той факт, що багато зображень надлишкові, оскільки містять велику кількість суміжних пікселів одного кольору. Розглянемо, наприклад, як за допомогою групового кодування стискається зображення, у якому зустрічається підряд 100 пікселів із нульовим значенням. Ця послідовність із 100 нулів кодується парою чисел (100,0). Отже такий фрагмент картинки скоротиться в п'ятдесят разів. Іншій методом, яким користуються досить часто, - JPEG ( метод, що стискує з утратами) одержав свою назву від абревіатури об'єднаної групи експертів в області фотографії (Joint Photographic Expert Group - JPEG), що його і розробила. JPEG широко використовується при стиснення статичних зображень . Цей метод істотно складніший, чим RLE. Основна ідея методу перебуває в поділі інформації в зображенні за рівнем важливості, і потім відкиданні менше важливої її частини, зменшуючи тим самим загальний об'єм збережених даних. Це досягається перетворенням матриці колірних значень у матрицю амплітуд, що відповідають визначеним частотам розкладання зображення. (Звукові коливання, наприклад, можна розкласти математичними методами на прості синусоїдальні гармоніки різних амплітуд і частот, що при додаванні відтворюють вихідний сигнал). Рядок або стовпець пікселів зображення теж можна представити амплітудами і частотами. Мова в даному випадку йде не про спектральний склад світла, а про форму представлення кривих, що утворять графіки, якщо значення пікселів служать ординатами. Відзначимо, що формула перетворення матриці пікселів у матрицю амплітуд не проста. JPEG-стиснення відкидає частину високочастотних компонент зображення, залишаючи компоненти з низькими частотами. Людське око менше критичне до високочастотних варіацій кольору, оскільки загальний вид зображення визначається низькими частотами. Значення піксела, отримане при відновленні зображення, дещо відрізняється від вихідного значення, тому що частина інформації була загублена, хоча звичайно вони дуже близькі. У методу JPEG є дуже цікава особливість: користувач може задавати коефіцієнт якості. Високий коефіцієнт якості дозволяє зберегти більше деталей, але при цьому зменшується ступінь стиснення. При низькому коефіцієнті якості степінь стиснення збільшується, але зображення стає менше чітким. Чим нижче коефіцієнт якості, тим більша кількість інформації відкидається. Коли любий із методів (RLE або JPEG) застосовується до повнокольорового зображення, то червона, зелена і синя компоненти стискуються незалежно. Якщо в растровому зображені використовується палітра або просто відтінки сірого, то значення пікселів можливо закодувати в один прохід. Розглянемо більш детально методи RLE і JPEG. Починаючи з першого рядка, програма групового кодування переглядає значення пікселів зліва праворуч і шукає відрізки пікселів, що повторюються. Всякий раз, коли зустрічаються три або більше пікселів, що йдуть підряд, з однаковим значенням, програма заміняє їх парою чисел: перше число вказує на довжину відрізка, друге - на значення пікселів. Число, що визначає довжину відрізка, називають міткою відрізка. Щоб ідентифікувати серії значень пікселів, що не повторюються, програма також уставляє мітки , що вказують на кількість таких значень у серії. Зарезервований біт необхідний для того, щоб можна було відрізнити мітку відрізка від мітки серії значень, що не повторюються. Наприклад, у 8-ми бітах можна задати послідовності довжиною до 127 пікселів; восьмий біт у кожній мітці може відрізняти відрізок від серії пікселів, що не повторюються . Точно так само обробляється кожний рядок пікселів і відрізки однакових значень пікселів стискуються у всьому зображенні. Графічна програма декодує зображення, зчитуюючи стиснутий файл і відновлює відрізки повторюваних значень пікселів. Зауважимо, що відновлене зображення цілком збігається з оригіналом. Насамперед програма поділяє зображення на блоки - матриці розміром 8х8 пікселів. При використанні методу JPEG час, що затрачається на стиснення зображення, пропорційний квадрату числа пікселів у блоці. Обробка декількох блоків меншого розміру робиться значно швидше, чим обробка всього зображення цілком. До значень пікселів застосовується формула, названа дискретним косинусоїдальним перетворенням (Discrete Cosine Transform - DCT). DCT переводить матрицю значень пікселів 8х8 у матрицю значень амплітуд тієї ж розмірності, що відповідає визначеним частотам синусоїдальних коливань. Лівий верхній кут матриці відповідає низьким частотам, а правий нижній - високим. Коефіцієнт якості, введений користувачем, використовується в простій формулі, що генерує значення елементів іншої матриці 8х8, яка називається матрицею квантування. Чим нижче коефіцієнт якості, тим більші значення будуть мати елементи матриці. Кожне значення в матриці, яка була сформована після DCT-перетворення, ділиться на відповідне значення з матриці квантування, потім округляється до найближчого цілого числа. Оскільки великі числа знаходяться в правій нижній половині матриці квантування, то основна частина високочастотної інформації зображення буде відкинута. Тому нижня права частина матриці пікселів буде перебувати в основному з нулів. Далі програма зчитує елементи матриці і кодує їх послідовно методами без втрат. Зауважимо, що стиснення істотно залежить від нулів у правій нижній половині матриці. Чим нижче коефіцієнт якості, тим більше нулів у матриці і, відповідно, тим вище ступінь стиснення. Декодування JPEG-зображення починається з кроку зворотного кодуванню без втрат, у результаті чого відновлюється матриця квантування пікселів. Значення з матриці пікселів перемножується на значення з матриці квантування, щоб відновити, наскільки це можливо, матрицю, що була обчислена на кроку застосування DCT. На етапі квантування була загублена деяка частина інформації, тому числа в матриці будуть близькі до початкових, але не буде абсолютного збігу. Зворотна до DCT формула (IDCT) застосовується до матриці для відновлення значень пікселів вихідного зображення. Ще разом відзначимо, що отримані кольори не будуть цілком відповідати початковим через втрату інформації на кроку квантування. Відновлене зображення, при порівнянні з оригіналом, буде виглядати декілька розмитим і знебарвленим. Один з класичних алгоритмів. Використовує тільки частоту появи однакових байт в зображенні. Порівнює символів вхідного потоку, які зустрічаються більше число разів, ланцюжок біт меншої довжини. І навпаки - зустрічаються рідко - ланцюжок більшої довжини. Для збору статистики вимагає двох проходів по зображенню. Коефіцієнти стиснення: 1 / 8, 2 / 3, 1. Вимагає запису у файл таблиці відповідності кодуються символів і кодують ланцюжків. На практиці використовуються його різновиди. Так, в деяких випадках резонно або використовувати постійну таблицю, або будувати її "адаптивно", тобто в процесі архівації / розархівації. Ці прийоми позбавляють від двох проходів по зображенню і необхідності зберігання таблиці разом з файлом. Кодування з фіксованою таблицею застосовується як до останнього етапу архівації в JPEG. Близька модифікація алгоритму використовується при стисненні чорно-білих зображень. Послідовності поспіль йдуть чорних і білих крапок замінюються числом, рівним їх кількості з ознакою кольору. А цей ряд вже, у свою чергу, стискується по Хаффману з фіксованою таблицею. Алгоритм реалізований у форматі TIFF . Цей метод дає високий коефіцієнт стиснення, підтримувана колірна модель - індексовані кольорові зображення. Застосовується у форматі AVI – Microsoft Animation VIdeo GIF для зберігання й передавання. Алгоритм розроблений групою експертів ISO (-Joint Bi level Experts Group) спеціально для стиснення однобітних чорно-білих зображень. Наприклад, факсів або відсканованих документів. У принципі може застосовуватися і до 2-х, і до 4-х двійкового картинок. При цьому алгоритм розбиває їх на окремі бітові площині. JBIG дозволяє управляти такими параметрами, як порядок розбиття зображення на бітові площині, ширина смуг в зображенні, рівні масштабування. Остання можливість дозволяє легко орієнтуватися в базі великих за розмірами зображень, переглядаючи спочатку їх зменшені копії. Настроюючи ці параметри, можна використовувати цікавий ефект при отриманні зображення по мережі або з будь-якого іншому каналу, пропускна здатність якого мала в порівнянні з можливостями процесора. Розпаковуватися зображення на екрані буде поступово, як би повільно "проявляючись". При цьому людина починає аналізувати зображення задовго до кінця процесу розархівації. Алгоритм побудований на базі Q-кодувальника, патент на який володіє IBM. Q-кодер також, як і алгоритм Хаффмана, використовує для частіше з'являються символів короткі ланцюжки, а для рідше з'являються довгі. Однак, на відміну від нього, в алгоритмі використовуються і послідовності символів. Характерною особливістю JBIG є різке зниження ступеня стиснення при підвищенні рівня шумів вхідний картинки. |
Ця група алгоритмів, мабуть, є найбільш перспективною і розвивається зараз найбільш бурхливо. Перші практичні результати були отримані зовсім недавно - у 1992 році - і виробили приголомшливе враження. Коефіцієнт стискування у фрактальних алгоритмів варіюється в межах 2-2000. Причому великі коефіцієнти досягаються на реальних зображеннях, що, взагалі кажучи, нетипово для попередніх алгоритмів. Крім того, при розархівації зображення можна масштабувати. Унікальна особливість цього алгоритму полягає в тому, що збільшене зображення не дробиться на квадрати. Під фрактального стиснення використовується принципово нова ідея - не близькість квітів у локальній області, а подібність різних за розміром областей зображення. Це, безумовно, найбільш прогресивний підхід на сьогоднішній день. Алгоритм орієнтований на повнокольорові зображення і зображення в градаціях сірого кольору.
Його особливістю є потреба в колосальних обчислювальних потужностях за архівації. При цьому розпаковування вимагає менше обчислень, ніж у JPEG. Стиск зображень (image compression). За допомогою фракталів можна стискувати зображення з деякою втратою якості, аналогічно іншим методам стику з втратами. Але фрактальний стиск дає кращі результати. Методи компресії, основані на RLE, класичний алгоритм Хаффмана, LZW, не враховують природи стискуваних даних і тому дають незадовільні результати при обробці зображень. Фрактальний стиск зображень – це алгоритм стиску зображень з втратами, заснований на застосуванні систем ІFS до зображень. Даний алгоритм відомий тим, що в деяких випадках дозволяє одержати дуже високі коефіцієнти стиску (кращі приклади – до 1000 разів при прийнятній візуальній якості) для реальних фотографій природних об'єктів, що недоступно для інших алгоритмів стиску зображень у принципі.
Основна проблема фрактального стиску – це те, що компресія-декомпресія виконується швидко і однозначно, в той час, як пряма процедура потребує від машини великих інтелектуальний можливостей. При компресії можна не зберігати оригінальні розміри зображення, достатньо просто запам’ятати їх відношення. А при декомпресії – задавати ті розміри, які нам найбільше підходять. Така можливість дозволяє вирішити задачу екстраполяції початкового зображення. При встановленні нових розмірів, що перевищують старі, в нове зображення добавляються елементи, подібні іншим елементам зображення. І якщо, оброблюється природній об’єкт (наприклад, гранітний камінь), то заміна не буде помітною.
Основа методу фрактального кодування – це виявлення самоподібних ділянок у зображенні. Патенти на ідеї були отримані в 1990-1991 роках.
Суть фрактального стиску. В основі більшості методів фрактального кодування, що застосовуються сьогодні, використовуються системи доменних і рангових блоків зображення, блоків квадратної форми, що покривають все зображення. Фрактальне кодування напівтонових зображень основане не гіпотезі, згідно з якою, в будь-якому зображенні можна знайти локальну самоподібність різних його частин. Існуючі алгоритми фрактального стиску, як правило, притримуються наступної схеми кодування. Зображення, яке кодується розбивається на множину блоків, що не перекриваються (рангові області), для кожного з яких, в межах цього ж зображення, відшукується блок більшого розміру (домен), пікселі якого, шляхом деякого перетворення, переводились би в пікселі рангової області. При цьому для пошуку оптимальної відповідності рангових областей і доменів необхідний повний перебір варіантів, що веде за собою значні обчислювальні затрати. З перетворень, що переводять домени в рангові області, формується відображення, що переводить зображення в зображення. При цьому, кодом зображення буде місце розташування і розміри рангових областей, а також коефіцієнти перетворень, описуючих самоподібність всередині зображення. Кількість біт, необхідних для опису коду, буде значно менше кількості біт, необхідних для опису початкового зображення.
Коефіцієнтом стиску називається відношення бітового представлення зображення до бітового представлення коду. В відомих фрактальних методах стиску зображень значення цього коефіцієнту може досягати 100 при достатньо непоганій якості відновлення. Для відновлення закодованого таким чином зображення використовується принцип стиснених відображень, який говорить, що стискуюче відображення, діюче в повному метричному просторі, має єдину нерухому точку. Відображення, що діє на повному метричному просторі зображень, формується з перетворень, які переводять домени в рангові області.
Відповідно до даного методу зображення розбивається на безліч неперекриваючих рангових підзображень і визначається безліч перекриваючих доменних підзображень. Для кожного рангового блоку алгоритм кодування знаходить найбільш підходящий доменний блок і афінне перетворення, що переводить цей доменний блок у даний ранговий блок. Структура зображення відображається в систему рангових блоків, доменних блоків і перетворень.
Основна складність фрактального стиску полягає в тому, що для знаходження відповідних доменних блоків, загалом кажучи, потрібен повний перебір. Оскільки при цьому переборі щораз повинні рівнятися два масиви, дана операція виходить досить тривалою. Порівняно простим перетворенням її можна звести до операції скалярного добутку двох масивів, однак навіть скалярний добуток рахується порівняно тривалий час.
Крім стиску, іншою областю фрактальної обробки зображень є їх генерація. В наш час існує множина найрізноманітніших пакетів прикладних програм від простих, які створюють зображення на основі множини Мандельброта (Fractal SSE), до складних, які генерують зображення 3d, анімаційні зображення та IFS-зображення. Всі вони побудовані на основі відкриття Мандельброта: якщо нанести визначені точки на площину комплексних чисел, то можна створювати зображення надзвичайного абстрактного вигляду – множина Мандельброта. В рівняння Мандельброта підставляються координати деякої точки комплексної площини, і результатом є координати іншої точки. Результат, отриманий при вводі координат першої точки, слугує початком для наступної ітерації, її результат підставляється в наступне рівняння і так далі.
Обидві ці найголовніші області застосування фрактальних методів в наш час знаходяться на порівняно високому рівні розвитку, незважаючи на те, що фрактальна наука досить молода. Існує надзвичайно велика кількість програм, за допомогою яких можна створити або стиснути зображення і ефективність обробки зображень деяких з цих програм достатньо висока.
Потенційним, хоч і менш відомим видом фракталів, є фрактали на основі системи ітераційних функцій (Iterated Function System – IFS). Метод IFS, який застосовується до побудови фрактальних зображень, винайшов Майкл Барнслі. Він базується на самоподібності елементів зображення і полягає в моделюванні малюнка декількома меншими частинами його самого. Найвідомішим IFS-зображенням є чорний папоротник, в якому кожен лист в дійсності являє собою мініатюрний варіант самого папоротника.
Система IFS – це також сукупність стискаючих афінних перетворень. Як відомо, афінні перетворення містять у собі масштабування, поворот і паралельний перенос. Афінне перетворення вважається стискаючим, якщо коефіцієнт масштабування менше одиниці.
Розглянемо докладніше побудову кривій Кох з використанням афінних перетворень. Кожний новий елемент кривої містить чотири ланки, отриманих з утворюючого елемента використанням масштабування, повороту й переносу.
- 1. Для одержання першої ланки досить стиснути вихідний відрізок у три рази. Слід зазначити, що те ж масштабування застосовується для всіх ланок.
- 2. Наступна ланка будується з використанням всіх можливих перетворень, а саме: стиск у три рази, поворот на – 60 градусів і паралельний перенос на 1/3 по осі X.
- 3. Третя ланка будується аналогічно другому: стиск у три рази, поворот на 60 градусів, паралельний перенос на 2/3 по осі X.
- 4. Остання ланка: стиск у три рази, паралельний перенос на 2/3 по осі X.
Для синтезу фрактала вибирається початкова точка, до якої застосовується випадковим образом обране з ІFS перетворення, у результаті чого точка переміщується в інший кінець екрана. Ця операція повторюється багато разів (досить 100 ітерацій), і через деякий час точка починає блукати по атрактору (безліч всіх можливих траєкторій), що і буде являти собою зображення фрактала. Кожне нове положення точки зафарбовується кольором, відмінним від фону. Існує теорема, яка доводить, що отриманий атрактор буде замкнутим.
Для того, щоб блукаюча точка зафарбовувала нові пікселі, а не блукала по старим, використовують сьомий параметр, що являє собою ймовірність появи конкретного афінного перетворення з набору перетворень ІFS. Якщо вибрати початкову точку так, щоб вона відразу виявилася на атракторі, то вона починає блукати в області цього атрактора, не переміщуючись в інші області екрана. Розглядаючи кожне перетворення окремо, можемо помітити, що де б ми не починали, після декількох ітерацій, точка перестане рухатися по екрану.
Точка зупинки називається нерухомою точкою – це розв’язок системи лінійних рівнянь двох змінних, яке знаходиться методом простої ітерації. Нерухома точка кожного перетворення входить до складу атрактора. Тому за початкову точку при побудові фрактала можна взяти нерухому точку першого перетворення з набору ІFS.
