Основоположником науки про стиснення інформації прийнято рахувати Клода Шеннона. Його теорема про оптимальне кодування показує, до чого потрібно прагнути при кодуванні інформації і на скільки та або інша інформація при цьому стиснеться. Крім того, ним були проведені досліди за емпіричною оцінкою надмірності англійського тексту. Він пропонував людям вгадувати наступну букву і оцінював вірогідність правильного вгадування. На основі ряду дослідів він прийшов до висновку, що кількість інформації в англійському тексті коливається в межах 0.6 — 1.3 біта на символ. Не дивлячись на те, що результати досліджень Шеннона були по-справжньому затребувані лише десятиліття опісля, важко переоцінити їх значення. Перші алгоритми стиснення були примітивними у зв'язку з тим, що була примітивною обчислювальна техніка. З розвитком потужностей комп'ютерів стали можливими все більш могутні алгоритми. Справжнім проривом був винахід Лемпелем і Зівом в 1977 р. словарних алгоритмів. До цього моменту стиснення зводилося до примітивного кодування символів. Словарні алгоритми дозволяли кодувати рядки символів, що повторювалися, що дозволило різко підвищити ступінь стиснення. Важливу роль зіграв винахід зразково в цей же час арифметичного кодування, що дозволило утілити в життя ідею Шеннона про оптимальне кодування. Наступним проривом був винахід в 1984 р. алгоритму РРМ. Слід зазначити, що цей винахід довго залишався непоміченим. Річ у тому, що алгоритм складний і вимагає великих ресурсів, в першу чергу великих об'ємів пам'яті, що було серйозною проблемою у той час. Винайдений в тому ж 1984 р. алгоритм LZW був надзвичайно популярний завдяки своїй простоті, хорошій рекламі і невимогливості до ресурсів, не дивлячись на відносно низький ступінь стиснення. На сьогоднішній день алгоритм РРМ є найкращим алгоритмом для стиснення текстової інформації, а LZW давно вже не вбудовується в нові додатки (проте широко використовується в старих). Майбутнє алгоритмів стиснення тісно пов'язане з майбутнім комп'ютерних технологій. Сучасні алгоритми вже впритул наблизилися до Шеннонівської оцінки 1.3 біта на символ, але учені не бачать причин, по яким комп'ютер не може передбачати краще, ніж людина. Для досягнення високих ступенів стиснення доводиться використовувати складніші алгоритми. Так, існують украй швидкі реалізації алгоритмів РРМ для текстової інформації і SPIHТ для графіки, що мають дуже високий ступінь стиснення. Таким чином, майбутнє за новими алгоритмами з високими вимогами до ресурсів і все більш і більш високим ступенем стиснення.
1 АНАЛІЗ ПРОБЛЕМИ ТА ТИПИ ГРАФІЧНИХ ФОРМАТІВ
1.1 Аналіз проблеми стиснення інформації
Кількість потрібної людині інформації неухильно росте. Об'єми пристроїв для зберігання даних і пропускна спроможність ліній зв'язку також ростуть. Проте кількість інформації росте швидше. У цієї проблеми є три рішення. Перше - обмеження кількості інформації. На жаль, воно не завжди прийнятне. Наприклад, для зображень це означає зменшення розширення, що приведе до втрати дрібних деталей і може зробити зображення взагалі даремними (наприклад, для медичних або космічних зображень). Друге — збільшення об'єму носіїв інформації і пропускної спроможності каналів зв'язку. Це рішення пов'язане з матеріальними витратами, причому іноді вельми значними. Третє рішення - використання стиснення інформації. Це рішення дозволяє у декілька разів скоротити вимоги до об'єму пристроїв зберігання даних і пропускної спроможності каналів зв'язку без додаткових витрат (за винятком витрат на реалізацію алгоритмів стиснення). Умовами його застосовності є надмірність інформації і можливість установки спеціального програмного забезпечення або апаратури як поблизу джерела, так і поблизу приймача інформації. Як правило, обидва ці умови задовольняються. Саме завдяки необхідності використання стиснення інформації методи стиснення досить широко поширені. Проте існують дві серйозні проблеми. По-перше, широко використовувані методи стиснення, як правило, застаріли і не забезпечують достатнього ступеня стиснення. В той же час вони вбудовані у велику кількість програмних продуктів і бібліотек і тому використовуватимуться ще достатньо довгий час. Другою проблемою є часте застосування методів стиснення, не відповідних характеру даних. Наприклад, для стиснення графіки широко використовується алгоритм LZW, орієнтований на стиснення одновимірної інформації, наприклад тексту. Вирішення цих проблем дозволяє різко підвищити ефективність застосування алгоритмів стиснення. Таким чином, розробка і впровадження нових алгоритмів стиснення, а також правильне використання тих, що існують дозволить значно скоротити витрати на апаратне забезпечення обчислювальних систем. Отже, побудова алгоритму стиснення інформації – це завжди пошук компромісу між вимогами до ступеня стиснення, швидкодією, складністю алгоритму і кількістю потрібної для роботи алгоритму пам'яті. Перед побудовою алгоритму слід відповісти на наступні питання: – Скільки пам'яті буде доступна алгоритму? – Чи повинен алгоритм бути максимально швидким? – Чи повинен алгоритм бути простим? – Чи повинен алгоритм мати максимально можливий ступінь стиснення? – Чи повинен алгоритм бути однопрохідним (потоковим)? Якщо головним критерієм є швидкодія, має сенс використовувати префіксне кодування. Якщо немає, то краще використовувати Range кодування. Якщо розмір вільної пам'яті менше 100 кбайт (наприклад, алгоритм використовуватиметься у вбудовуваних системах) і дані мають складну модель (наприклад, потрібно стискати текстову інформацію), то статистичні моделі не підходять і слід використовувати словарні. Якщо пам'ять досить (6-8 мбайт і більш), то слід використовувати статистичні моделі. Алгоритми на основі BWT-перетворення не можуть бути ефективно реалізовані як потокові (наприклад, для використання в модемах).
1.2 Типи графічних файлів
Займаючись обробкою зображень, ми завжди стикаємось із тим, що плоди нашої праці потрібно зберігати. І тут є широкий вибір форматів графічних файлів. Їх можна класифікувати за декількома критеріями. Ми розглянемо дві найбільш вживані: перша – за, власне, змістом файлу, а друга за форматами прикладних програм. Згідно першої класифікації графічні файли поділяються на растрові, векторні, метафайлові та спеціалізовані. У перших зберігають, згідно назві, растрову графіку, застосовуючи різні алгоритми кодування та стиснення інформації. Якщо інформацію про зображення просто кодувати та розміщувати у фалі без стиснення, то об’єми їх будуть вражаючими. Тому слід розглянути деякі алгоритми стиснення графічних файлів. Стиснення може бути з втратами та без втрат кодованої інформації. Стиснення може здійснюватись за допомогою словників найбільш вживаних слів, і тут словники можуть бути адитивні та неадитивні (постійні словники та динамічні відповідно). GIF (Graphic Interchange Format) – растровий з обмеженою колірністю: 2 – 256 кольорів. Використовує LZW стиснення, має обмеження на розмір зображення: 64К х 64К пікселів. Підтримує анімацію, найбільш підходить для плашкових зображень. EPS (Encapsulated PostScript) – метафайловий формат, базується на використанні мови опису сторінок PostScript. Цей файл є монохромним, при збереженні кольорового CMYK зображення у файлі буде по одному зображенню на кожний колірний канал. Ще надається можливість зберігання екранної копії зображення та піктограми для відтворення у файлі. Може бути двох форматів – ASCII або двійковому. Не використовує стискання, не має обмежень на розмір. Використовується для поліграфічного відтворення, в програмах макетування. JPEG – растровий, колірність 24 біта, має обмеження на розмір, що і *.gif. Власне стискання – ефект стиснення 10-15 разів без помітної оком різниці. Не підтримує анімації. Використовується для збереження на півтонових сірих і кольорових фотографічних зображень. TIFF (Tag Image File Format) – найбільш вживаний формат обміну, передає всю інформацію, що створила програма. Не підтримує багатошаровості, максимальний розмір файлу 232. Колірність до 24 бітів, використовує всі можливі алгоритми стиснення (RLE, CCITT, LZW). Проаналізувавши різні типи графічних форматів, я зупинився на BMP-форматі. Тому в даній дипломній роботі буде кодуватись саме такі зображення. Розглянемо його докладніше. Структура BMP файлу така. Перших 54 байти складає заголовок. У перших 2 байтах заголовку записані символи B та M, за цим можна відрізнити, що ми працюємо саме з BMP-файлом. У байтах 10–13 записане 4–байтне ціле, яке вказує зміщення від початку файлу до початку піксельних даних. Якщо це число більше за 54, значить, після заголовку йде таблиця кольорів, і тому BMP-файл не є 24–бітним. У байтах 18–21 записана ширина зображення, у байтах 22–25 — висота, у байтах 28–29 буде бітність, у байтах 30–33 — тип компресії. Для незтиснутого зображення рівна нулю. Незжаті піксельні дані записані в форматі BGR по рядках знизу вверх. На відміну від PCX-формату, дані рядка пікселів тут записуються послідовно, а не покомпонентно. Рядок пікселів повинен бути кратним 4 байтам. Тому, якщо, наприклад, зображення є шириною 9 пікселів, то довжина рядку при 24–бітному кольорі повинна була б бути 9*3=27 байт. 27 не є кратним четвірці, тому після даних рядка 1 байт заповнюється нулем.
1.3 Методи кодування
Кодування (encoding) має справу з потоком символів у деякому алфавіті, до того ж частоти символів – різні. Ціллю кодування є перетворення цього потока на потік бітів мінімальної довжини. Це досягається за рахунок зменшення надлишковості вихідного потоку шляхом врахування частоти символів на вході: довжина коду має бути пропорційна інформації, що міститься у вхідному потоці. Якщо розподіл частот символів відомий, тоді можна побудувати оптимальне кодування. Задача ускладнюється, якщо цей розподіл заздалегідь невідомий. В такому разі існують два різних підходи. Перший підхід: продивитися вхідний потік і побудувати кодування на основі зібраної статистики (це потребу двох проходів по файлу, що звужує сферу застосування таких алгоритмів). У вихідний потік в такому випадку має бути записано схему кодування, що застосовувалося. Цією схемою потім скористається декодер. Приклад – статистичне кодування Хаффмена. Другий підхід – використовувати так званий адаптивний кодер (adaptive coder). Ідея полягає в тому, щоб змінювати схему кодування в залежності від вихідних даних. Такий алгоритм є однопрохідним і не потребує передавання інформації про використане кодування в явному вигляді. Замість цього декодер, зчитуючи кодований потік, синхронно з кодером змінює схему кодування, починаючи деякої початкової. Адаптивне кодування забезпечує більшу ступінь стискання, оскільки враховуються локальні зміни частот. Прикладом є динамічне кодування Хаффмена. Кодування Хаффмена Розглянемо статистичне кодування Хаффмена. Це кодування співставляє вхідним символам, що подаються ланцюжками бітів однакової довжини (наприклад, 8-бітовими байтами), ланцюжки бітів змінної довжини. Довжина коду пропорційна (з округленням до цілого) двійковому логарифму його частоти, взятому з оберненим знаком. Це кодування є префіксним, що дозволяє його легко декодувати однопрохідним алгоритмом. В префіксному кодуванні код будь-якого символа не є префіксом коду жодного іншого символа. Префіксний код зручно представляти у вигляді двійкового дерева, в якому символи знаходяться на листках, а ребра помічені 0 або 1. Тоді код символа можна задати як шлях від кореня дерева до листа, що містить цей символ. При використанні адаптивного кодування Хаффмена необхідно постійно коректувати дерево у відповідності до статистики вхідного потоку, яка весь час змінюється. Під час реалізації, як правило, вимагаються значні витрати на балансування кодового дерева відповідно до нових частот символів на кожному кроці. Перевагами методу Хаффмена є його досить висока швидкість і так само висока якість стискання. Цей алгоритм порівняно давно відомий і є на сьогодні дуже розповсюдженим: прикладами є програма compact OC UNIX (програмна реалізація), а також стандарт кодування факсів (апаратна реалізація).
Кодування Хаффмена має мінімальну надлишковість за умови, що кожний символ кодується окремим ланцюжком в алфавіті {0,1}. Недоліком кодування Хаффмена є залежність коефіцієнту стискання від близькості імовірностей символів до від’ємних ступенів 2; це пов’язано з тим, що кожен символ кодується цілою кількістю біт. Найбільш помітно це під час кодування двосимвольного алфавіту: в цьому випадку стискання неможливе, незважаючи на відмінності імовірностей символів; алгоритм фактично “округляє” їх до 1/2! Арифметичне кодування Арифметичне кодування – це метод, що дозволяє стискати символи вхідного алфавіту без втрат за умови, що відомий розподіл частот цих символів. Концепцію методу наведено у роботах Еліаса в 60-х роках. Пізніше метод було розвинено та значно модифіковано. Арифметичне кодування є оптимальним, досягаючи теоретичної границі стискання – ентропії вхідного потоку. Текст, який стиснено арифметичним кодером, розглядається як деякий двійковий дріб з інтервалу [0,1). Результат стискання можна подати як послідовність двійкових цифр із цього дробу. Ідея методу полягає в наступному: початковий текст розглядається як запис цього дробу, де кожен вхідний символ є “цифрою” з вагою, що пропорційна ймовірності його появи. Під час реалізації цього методу виникають дві проблеми: по-перше, необхідно використовувати дійсну арифметику необмеженої точності, і по-друге, результат кодування стає відомим лише після закінчення вхідного потоку. Однак, досліди показали, що можна практично без втрат обмежитися цілочисельною арифметикою невеликої точності (16-32 розряди), а також домогтися покрокової (інкрементальної) роботи алгоритми: цифри коду можуть видаватися послідовно під час читання вхідного потоку.
2 РОЗРОБКА ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ
2.1 Вибір програмного середовища розробки
В якості середовища розробки програми була вибрана мова програмування Delphi 7.0. Delphi – могутня система візуального об'єктно-орієнтованого проектування, що дозволяє вирішувати безліч задач, зокрема: - створювати завершені додатки для Windows різноманітної спрямо-ваності, від чисто обчислювальних і логічних, до графічних і мультимедіа; - швидко створювати (навіть програмістам-початківцям) професіо-нально виглядаючий віконний інтерфейс для будь-яких додатків; - створювати могутні системи роботи з локальними і розподіленими базами даних; - створювати довідкові системи (файли. hlp) для своїх додатків; - та багато іншого. Крім того, Delphi 7.0 працює в середовищах Windows 9.х, ХР і використовує всі можливості сучасної комп’ютерної техніки . Нове покоління засобів візуального програмування дозволило значно скоротити час розробки функціонально-складних і зручних в користуванні прикладних програм. Система Delphi – останнє досягнення на ниві візуального програмування. Головним суперником Delphi є система Builder C++, проте для початкового освоєння Delphi є більш доступною системою оскільки вона базується на мові Pascal – мові спеціально створеній для освоєння програмування швейцарським математиком Ніклаусом Віртом в 60-х роках.
Компілятор Delphi забезпечує швидке перетворення написаного програмного коду безпосередньо в робочий код процесора ЕОМ, чим зумовлює швидкість написання, відладки і виконання прикладної програми, уникаючи етапів проміжної компіляції (перетворення в Р-код, тощо) – які ми бачимо в компіляторах з інших мов. В цьому відношенні мова Сі є більш складною для вивчення і є придатною для масового виробництва програмних продуктів, за умови наявності спеціальних бібліотек і необхідності максимального використання апаратних засобів ЕОМ. Для одиничних застосувань, за умови відсутності надпродуктивних обчислювальних засобів (Pentium2-350400МГц), а тим більше на етапі початкового освоєння, більш доцільним є застосування системи Delphi, яка забезпечує мінімальний час компіляції і ефективну оптимізацію результуючого процесорного коду. На відміну від таких мов програмування як Visual Basic Delphi справжня об’єктно-орієнтована мова, яка дозволяє об’єднувати дані і код в один клас (інкапсуляція), створювати дочірні класи (наслідування) і звертатися до класів-нащадків як до класів-предків (поліморфізм) . Проект Delphi складається з форм, модулів, установок параметрів проекту, ресурсів і т.д. Вся ця інформація розміщується в файлах. Багато з цих файлів автоматично створюються Delphi, коли програміст будує свій додаток. Ресурси, такі як бітові матриці, піктограми і т.д., знаходяться в файлах, які програміст отримує з інших джерел або створює за допомогою численних інструментів і редакторів ресурсів, що є у його розпорядженні. При проектуванні додатку Delphi створює наступні файли: - файл проекту (.dpr) – цей текстовий файл використовується для зберігання інформації про форми і модулі. У ньому містяться оператори ініціалізації і запуску програм на виконання; - файл модуля (.pas) – кожній формі, що створюється, відповідає текстовий файл модуля, що використовується для зберігання коду.
Можна створювати модулі, не пов'язані з формами. Багато з функцій і процедур Delphi зберігаються в модулях; - файл форми (.dfm) – це двійковий або текстовий файл, який створюється Delphi для зберігання інформації про ваші форми. Кожному файлу форми відповідає файл модуля (.pas); - файл параметрів проекту (.dfo) – у цьому файлі зберігаються установки параметрів проекту; - файл ресурсів (.res) – цей бінарний файл містить піктограму, що використовується проектом і інші ресурси; - файли резервних описів (.~dp,. ~df,. ~pa) – це відповідно файли резервних описів для файлів проекту, форми і модуля. Якщо щось безнадійно зіпсоване в проекті, можна відповідно змінити розширення цих файлів і таким чином повернутися до попереднього не зіпсованого варіанту; - файл конфігурації вікон (.dsk) – Файл зберігає конфігурацію всіх вікон середовища розробки; - файл, що виконується (.exe) – це файл вашого додатку, що виконується. Він є автономним файлом, що виконується, для якого більше нічого не потрібно, якщо тільки ви не використовуєте бібліотеки, що містяться в DLL, OCX і т.д., а також якщо ви не використовуєте підтримку пакетів часу виконання; - об'єктний файл модуля (.dcu) – це відкомпільований файл модуля (.pas), який компонується в остаточний файл, що виконується. І, нарешті, інші файли Windows, які можуть використовуватися Delphi: - файли довідки (.hlp) – це стандартні файли довідки Windows, які можуть бути використані вашим додатком Delphi; - файли зображень або графічні файли (.wmf,. bmp,. ico) – ці файли звичайно використовуються в додатках Windows для створення привабливого і дружнього призначеного для користувача інтерфейсу.
Головною частиною додатку є файл проекту (.dpr), з якого починається виконання програми і який забезпечує ініціалізацію інших модулів. Він створюється і модифікується Delphi автоматично в процесі розробки прикладної програми. Ім'я, яке дається файлу проекту при зберіганні, стає ім'ям файла, що виконується. Після створення додатку з пустою формою, потрібно відразу зберегти його в потрібному каталозі. У багатовіконних додатках це дозволяє відразу давати модулям імена, які будуть використовуватися в програмі для взаємних посилань модулів один на одного.
2.2 Вибір алгоритму кодування
Стискання здійснюється з метою зменшення фізичного розміру блоку інформації. Стискання інформації здійснює програма-компресор, а відновлення – програма-декомпресор. Стискання растрових і векторних даних здійснюється по-різному. В растрових файлах стискаються тільки дані зображення, а заголовок і решта даних (таблиця кольорів, кінцівка і т.п.) завжди залишаються нестисненими (вони, як правило, займають незначну частину растрового файла). Векторні файли, в яких зберігається математичний опис зображення, а не самі дані, як правило, не мають “рідної” форми стискання. Це викликано тим, що в векторному форматі дані вже представлені в компактній формі і стискання дає дуже незначний ефект. Окрім цього звичайно векторні дані читаються з незначною швидкістю і при додаванні розпаковування цей процес може стати ще більш повільним. Якщо векторний файл все ж стискається, то, як правило, стискаються всі дані, включаючи заголовок. Більшість алгоритмів стискання забезпечують кодування без втрат, коли дані при розпаковуванні повністю відновлюються. Методи кодування з втратами передбачають відкидання деяких даних зображення для досягнення кращої міри стискання, ніж за методами без втрат. При цьому важливо, щоб втрата деякої частини даних була прийнятною або навіть доцільною. Найбільш поширеними алгоритмами стискання даних є групове кодування (RLE), алгоритм Лемпела-Зіва-Велча (LZW), кодування CCITT (Хафмена), технологія JPEG, алгоритм ART, алгоритми фрактального стискання зображень Алгоритм LZW базується на словниках. Із даних вхідного потоку він будує словник даних. Зразки даних ідентифікуються в потоці даних і співставляються з записами в словнику. Якщо зразка даних нема в словнику, то на основі цих даних в словник записується кодова фраза, яка має менший розмір, ніж самі дані. Ця ж фраза записується і в вихідний потік стиснених даних. Якщо ж зразок даних зустрічається у вхідному потоці повторно, фраза, що відповідає йому, читається із словника і записується в вихідний потік. Так як кодові фрази мають менший розмір, ніж зразки даних, відбувається стискання. Декодування здійснюється в зворотному порядку. Декомпресор читає код з потоку стиснених даних і, якщо його ще нема в словнику, додає його туди. Потім цей код перево¬диться в рядок, який він представляє, і записується в вихідний потік нестиснених даних. Перевагою алгоритму LZW перед іншими, які базуються на словниках, є те, що не обов’язково зберігати словник для наступ¬ного декодування. Алгоритм LZW є запатентованим і його викорис¬тання при створенні нових програмних продуктів обмежується ліцензійними угодами. Міжнародний Консультативний комітет з телеграфії і телефонії (CCITT) розробив серію комунікаційних протоколів для факсимільної передачі чорно-білих зображень по телефонних каналах і мережах передачі даних. Ці протоколи офіційно відомі як стандарти Т.4 і Т.6 CCITT, але більш розповсюджена їхня назва – стиск CCITT Group 3 і Group 4 відповідно. Іноді кодування CCITT називають кодуванням за алгоритмом Хафмена. Це простий алгоритм стиску, запропонований Девідом Хафменом у 1952 році. Стандарти Group 3 і Group 4 – це алгоритми стиску, спеціально розроблені для кодування однобітових даних зображення. Алгоритми CCITT не є адаптивними, тобто не настоюються для кодування кожного растра з оптимальною ефектив¬ністю. У них використовується фіксована таблиця кодових значень, що були обрані спеціально для представлення документів, які підлягають факсимільній передачі. Перед початком кодування здійснюється частотний аналіз коду документу і виявляється частота повтору кожного з символів. Символи, які частіше зустрічаються, кодуються меншою кількістю розрядів. При використанні кодування за схемою Хафмена треба разом із закодованим текстом передати відповідний алфавіт, але для великих фрагментів надлишковість не може бути значною. JPEG (Joint Photographic Experts Group – об’єднана група експертів по фотографії) є методом стиску, що дозволяє стискати дані багатоградаційних зображень (фотографій, телевізійних заставок, іншої складної графіки) з піксельною глибиною від 6 до 24 біт з задовільною швидкістю й ефективністю. На відміну від інших методів стиску JPEG не є одним алгоритмом. JPEG може налаштовуватися на відтворення дуже маленьких стиснутих зображень поганої якості, але проте придатних для більшості програм, і в той же час дозволяє робити стиснені зображення дуже високої якості, обсяг даних яких набагато менше, ніж в оригінальних нестиснених даних. JPEG, як правило, супроводжується втратами. Схема JPEG заснована на відкиданні інформації, яку важко помітити візуально. Невеликі зміни кольору погано розпізнаються оком людини, а от незначні зміни інтенсивності (світліше чи темніше) – краще. Виходячи з цього, кодування з втратами JPEG прагне до дбайливого поводження з напівтоновою частиною зображення, але більш вільно поводиться з кольором. При цьому анімація, чорно-білі ілюстрації і документи, а також типова векторна графіка, як правило, стискуються погано. В даний час JPEG стали використовувати для стиску “живого” відео, однак стандарт не містить ніяких положень щодо такого застосування. Обсяг стиснутих даних залежить від змісту зображення. Міра стиску зображення з фотографічною якістю може становити від 20:1 до 25:1 без помітної втрати якості. Звичайно ж, настільки високий показник стиску супроводжується відмінністю від оригіналу, але вона настільки незначна, що якість зображення все-таки залишається досить високою. Зображення, що містять великі області одного кольору, стискуються дуже погано. JPEG вводить у такі зображення артефакти (недоліки, вади), особливо помітні на суцільному фоні. Це значно погіршує якість зображень у порівнянні з традиційним методом стиску без втрат. Процес стиску за схемою JPEG поділяється на кілька етапів: - перетворення зображення в оптимальний колірний простір; - субдискретизація компонентів колірності усередненням груп пікселів; - застосування дискретних косинусних перетворень для зменшення надлишковості даних зображення; - квантування кожного блоку коефіцієнтів дискретних косинусних перетворень із застосуванням вагових функцій, що оптимізовані з урахуванням візуального сприйняття людиною; - кодування результуючих коефіцієнтів (даного зображення) із застосуванням алгоритму Хафмена для видалення надлишковості інформації.
ART – це оригінальний алгоритм стиснення, що був створений і про¬да¬ється фірмою Johnson-Grace. Як і при роботі з алгоритмом JPEG, міра стиску в ART регулюється, а установка високого її значення може викликати втрати даних. Існує і режим кодування без втрат. Фірма Johnson-Grace продає ART як універсальний компресор для online-сервісів, а в перспективі планує адаптувати його для підтримки звуку, анімації і повномасштабного відеозображення. Хоча детальний опис цього алгоритму тримається в таємниці, Johnson-Grace випустила ряд документів описового характеру. Мета алгоритму – аналіз зображення і виявлення ряду його ключових ознак (колір, завади, межі, особливості, що повторюються), яким потім привласнюються пріоритети відповідно до відносної ваги кожної ознаки у вмісті зображення. Для класифікації і призначення пріоритетів ознакам стисненого зображення в програмі викорис¬то¬вується нечітка логіка. Повторювані особливості виявляються і зв'язуються в зображенні оригінальним методом, розробленим самою фірмою. Компоненти зображення квантуются, при цьому низкопріоритетні ознаки ігноруються. Як і при використанні алгоритму JPEG, міра втрати інформації підвищується пропорційно росту міри стиску і компенсується певною надлишковістю. ART-зображення можуть бути багаторівневими. Це значить, що їх можна передавати поетапно по модемних лініях з низькою пропускною здатністю. Крім того, алгоритм забезпечує майже миттєве, хоча і низькоякісне, відображення на пристрої виведення клієнта. Потім, по мірі прийому даних і поступової візуалізації, якість зображення підвищується. Фрактальне кодування засноване на тім факті, що всі природні і більшість штучних об'єктів містять надлишкову інформацію у виді однакових, повторюваних малюнків, які називаються фракталами. Процес кодування, що перетворює зображення в сукупність математичних даних, вимагає винятково великого обсягу обчислень. В залежності від розділь¬ної здатності і вмісту вхідних растрових даних, якості зображення, часу стиснення і розміру файлу процес стиснення одного зображення може зайняти від декількох секунд до декількох годин навіть на дуже швидко¬діючому комп'ютері. Декодування фрактального зображення – процес набагато більш простий, тому що вся трудомістка робота була виконана при пошуку всіх фракталів під час кодування. В процесі декодування потрібно лише інтерпретувати фрактальні коди, перетворивши їх у растрове зображення. Тому фрактальний метод доцільно використовувати тоді, коли дані зображень безупинно розпаковуються, але ніколи не стискуються. Фрактальний метод забезпечує легкість масштабування зображення без введення артефактів і втрати деталей та невеликий розмір стиснених даних але супроводжується втратами. Алгоритм RLE зменшує фізичний розмір рядків символів, що повторюються. Такі рядки називають групами і кодують двома байтами, перший з яких визначає кількість символів в групі, а другий містить значення символу. Ефективність стискання залежить від типу даних зображення. Краще стискаються чорно-білі зображення, які містять багато білого кольору, а гірше – фотореалістичні зображення з великою кількістю кольорів. Алгоритм RLE характеризується простотою і високою швидкодією. Варіанти групового кодування розрізняються напрямом утворення рядка (вздовж осі X, осі Y та діагоналі). Найчастіше вони стискають без втрат, однак відкидання молодших розрядів в значеннях символу може суттєво збільшити міру стискання складних зображень. Зміст методу – заміна ланцюжків символів, що повторюються, на один цей символ та лічильник повторювання. Проблема полягає в тому, щоб декодер міг відрізнити у вихідному потоці таку кодовану серію від інших символів. Розв’язок цієї проблеми очевидний – додавати до таких ланцюжків деякі заголовки (наприклад, використовувати перший біт як ознаку кодованої серії). Метод є досить ефективним для графічних зображень у форматі “байт на піксел” Алгоритм RLE (run length encoding) – групове кодування без втрат. В ньому послідовність символів подається самим символом та його кількістю в групі. Тут, наприклад, FFFFFF буде закодоване в 6F. В bitmap файлах використовується групове кодування BMP. Бітові,8U, 24U, 32U бітові групи нуликів та одиниць стискуються та мають 12 бітовий службовий ключ. Тут можливе використання палітр – таблиць кольорів, де кожний відтінок, що є у файлі має свій власний номер. Тобто, можлива заміна трьох байтів одним номером у палітрі. В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. Наприклад, нехай задана така послідовність даних, що підлягає стисненню: 1 1 1 1 2 2 3 4 4 4 В алгоритмі RLE пропонується замінити її наступною структурою: 1 4 2 2 3 1 4 3, де перше число кожної пари чисел -це код даних, а друге - коефіцієнт повторення. Якщо для зберігання кожного елементу даних вхідної послідовності відводиться 1 байт, то вся послідовність займатиме 10 байт пам'яті, тоді як вихідна послідовність (стиснений варіант) займатиме 8 байт пам'яті. Чим менше значення коефіцієнта стиснення, тим ефективніший метод стиснення. Зрозуміло, що алгоритм RLE буде давати кращий ефект стиснення при більшій довжині послідовності даних, що повторюється. У випадкові розглянутого вище прикладу, якщо вхідна послідовність матиме такий вигляд: 1 1 1 1 1 1 3 4 4 4, то коефіцієнт стиснення буде рівний 60%. У зв'язку з цим найбільша ефективність алгоритму RLE досягається при стисненні графічних даних (особливо для однотонових фонових зображень). Недоліки методу RLE є очевидними: це, передусім, низька пристосованість до багатьох розповсюджених типів файлів, наприклад, текстових: у загальному випадку реально стиснути можна лише ланцюжки проміжків на початку абзаців. Саме тому цей метод можна ефективно використовувати лише у комбінації з вторинним кодуванням.
