Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Стискання інформації методом FELICS
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2007
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська Політехніка”
Кафедра САПР
Курсова робота
з дисципліни “Методи та засоби комп’ютерних інформаційних технологій”
Стискання інформації методом
FELICS
Львів -2007
Завдання до курсового проекту
Національний університет «Львівська Політехніка»
/назва вищого учбового закладу/
Кафедра системи автоматизованого проектування
Дисципліна основи лінгвістичного забезпечення САПР
Спеціальність Комп’ютерні науки
Курс третій Група КН-320 Семестр шостий .
Завдання
на курсовий проект студента
Сидор Анатолій Юрійович
/прізвище, ім’я, по - батькові/
1. Тема проекту Стискання інформації методом FELICS
2. Термін здачі студентом закінченого проекту 26 червня 2007 р.
3. Вихідні дані для проекту
4. Зміст розрахунково-пояснювальної записки Вступ, теоретичні відомості, опис програми, текст програми, висновки
5. Перелік графічного матеріалу / з точним зазначенням обов’язкових креслень/
зображення роботи програми, приклади графічних файлів
6. Дата видачі завдання 03 березня 2006 р.
Постановка задачі
Ознайомитися з предметною областю теми курсової роботи і її проблематикою.
Здійснити програмну реалізацію методу стискання інформації FELICS; на основі цього зробити висновки.
Календарний план
№ п/п
Назва етапів курсового проекту
Термін виконання етапів проекту
Примітки
1
Формування технічного завдання
03.03 – 10.03
2
Створення алгоритму програми
12.03 – 25.03
3
Розробка програми
23.03 – 05.05
4
Відлагодження програми
05.04 – 19.05
5
Формування розділів записки
09.04 – 10.05
Студент
Сидор Анатолій Юрійович
( підпис )
( прізвище, ім’я, по-батькові )
Керівник
Грицишин Ярема
( підпис )
( прізвище, ім’я, по-батькові )
2007 р
Реферат
Сидор А.Ю. “Стискання інформації методом FELICS ”. Курсова робота. - НУ “Львівська політехніка”, каф.: САПР, дисципліна : “Основи лінгвістичного забезпечення САПР ”, 2007.
Курсова робота складається з 36 сторінки, 5 таблиць, 1 додатку.
В даній курсовій роботі розроблено програмне забезпечення для Стискання інформації методом FELICS, яке передбачає завантаження зображення з файлу та вивід результатів роботи програми у файл.
Зміст
Вступ……………………………………………………………………………..…..7
1. Аналіз предметної області…………………………..…………………………..9
1.1 Графіка. Види графіки…………………………………...……………...…..9
1.2 Формати графічних файлів …………………………………………..……11
1.3 Методи стискання зображень ……………………………………….…….12
1.4 Порівняння методів стискання зображень………………………………16
1.4.1 Класи зображень………………………………………………………..17
1.4.2 Класи об’єктів, які потребують стискання………………………….18
1.4.3 Вимоги об’єктів до алгоритмів компресії…………………………...20
1.4.4 Критерії порівняння алгоритмів……………………………………..23
1.4.5 Визначення характеристик методу FELICS………………………...25
2. Опис алгоритму…………………………………………..………………….....26
2.1 Опис методу…………………………………...……………...……………...26
2.1 Опис реалізації алгоритму……………………………...……………...…..29
3. Аналіз результатів та висновки…………………………………..…………..33
Вступ
Алгоритми стиску зображень - область машинної графіки, що бурхливо розвивається. Основний об'єкт зусиль у ній - зображення - своєрідний тип даних, який характеризується трьома особливостями:
1) Зображення (як і відео) звичайно вимагають для зберігання набагато більше пам'яті, ніж текст. Так, скромна, не дуже якісна ілюстрація на обкладинці книги розміром 500х800 точок, займає 1.2 Мб - стільки ж, скільки художня книга з 400 сторінок (60 знаків у рядку, 42 рядків на сторінці). Як приклад можна розглянути також, скільки тисяч сторінок тексту ми зможемо розмістити на CD-ROM, і як мало там поміститься нестиснутих фотографій високої якості. Ця особливість зображень визначає актуальність алгоритмів архівації графіки.
2) Другою особливістю зображень є те, що людський зір при аналізі зображення оперує контурами, загальним переходом кольорів і порівняно нечутливий до малих змін у зображенні. Таким чином, ми можемо створити ефективні алгоритми архівації зображень, у яких декомпресоване зображення не буде збігатися з оригіналом, однак людина цього не помітить. Дана особливість людського зору дозволила створити спеціальні алгоритми стиску, орієнтовані тільки на зображення. Ці алгоритми дозволяють стискати зображення з високим ступенем стиску й незначними з погляду людини втратами.
3) Ми можемо легко помітити, що зображення, на відміну, наприклад, від тексту, має надлишковість в 2-х вимірах. Тобто, як правило, сусідні точки, як по горизонталі, так по вертикалі, у зображенні близькі за кольором. Крім того, ми можемо використати подобу між колірними площинами R, G й B у наших алгоритмах, що дасть можливість створити ще більш ефективні алгоритми. Таким чином, при створенні алгоритму компресії графіки ми використовуємо особливості структури зображення.
З огляду на все вищевказане, побудова і вдосконалення алгоритмів стискання зображень є надзвичайно цікавою та актуальною проблемою, якщо звернути увагу на поширення цифрової графічної інформації серед різноманітних приладів з обмеженою пам’яттю, таких як фотоапарати, відеокамери, мобільні телефони тощо. Велику роль у стимулюванні розвитку програм архівації зображень відіграє і Internet, оскільки одною з найбільших проблем користувачів всесвітньої павутини завжди була недостатня швидкість перекачування інформації, яка напряму залежить від розмірів цієї інформації. І, на мою думку, ця проблема залишатиметься ще дуже надовго, бо разом з вдосконаленням апаратних засобів з’єднання з Internet паралельно зростає і потужність програмного забезпечення (і, відповідно, їх розмір).
1. Аналіз предметної області
Графіка. Види графіки.
Під терміном “графіка” звичайно розуміють результат візуального подання реального або уявного об’єкта, отриманий традиційними методами – малюванням або друкуванням. Комп’ютерна графіка включає методи і засоби створення і обробки зображень за допомогою програмно-апаратних комплексів і охоплює всі види і форми подання зображень, доступних для сприйняття людиною на екрані монітору або в вигляді копії на певному носії.
В залежності від способу опису та формування зображення розрізня ють растрову, векторну та фрактальну графіку.
Історично термін “растр” вказував на те, що пристрій при відтворенні зображення використовує набори пікселів (точок), організовані в вигляді послідовностей рядків розгортки. Растрові дані являють собою набори числових значень, які визначають кольори окремих пікселів, впорядко ваних таким чином, щоб їх легко було відобразити на растрових пристроях.
Базовим елементом растрової графіки є піксель. Логічні пікселі подібні до математичних точок: вони мають місцеположення, але не займають фізичного простору. Фізичні пікселі – це реальні точки, що відображаються пристроєм виводу. Вони є найменшими фізичними елементами поверхні відображення і займають її певну площу. В зв’язку з цим на відстань між двома сусідніми пікселями вводяться обмеження. Якщо задати пристрою відображення надто високу роздільну здатність (кількість пікселів на одиницю довжини зображення), то якість зображення знизиться із-за накладення або злиття сусідніх пікселів. При надто низькій роздільній здатності пікселі можуть бути розкидані по всій площі пристрою відображення. Таким чином, при відображенні значень логічних пікселів із растрових даних в фізичні пікселі повинні враховуватись реальні розміри і розміщення фізичних пікселів.
Розрізняють роздільну здатність оригіналу, екранного та друко ваного зображення. Роздільна здатність оригіналу вимірюється в точках на дюйм (dpi) і залежить від вимог до якості зображення, розміру файла, способу оцифровування або методу створення початкової ілюстрації, вибраного формату файла. Підвищення вимог до якості зображення вимагає вищої роздільної здатності оригіналу. Для екранної копії достатньо роздільної здатності 72 dpi, для роздруковування на кольоро вому принтері – 150-200 dpi, для виведення на фотоекспонуючий пристрій – 200-300 dpi.
Розмір точки растрового зображення залежить від методу і параметрів растрування оригіналу, коли на оригінал як би накладається сітка ліній, комірки якої утворюють елемент растра. Частота сітки растра вимірюється кількістю ліній на дюйм і називається лініатурою (lpi). Розмір точки растра розраховується для кожного елементу і залежить від інтенсивності тону в комірці. Для вищої інтенсивності щільніше заповнюється елемент растра. При раструванні з амплітудною модуляцією ілюзія більш темного тону створюється за рахунок збільшення розмірів точок при однаковій відстані між центрами елементів растра. При раструванні з частотною модуляцією інтенсивність тону регулюється зміною відстані між сусідніми точками однакового (найменшого) розміру. Інтенсивність тону прийнято розділяти на 256 рівнів. Для її відтворення достатньо мати розмір комірки растра 16(16 точок.
Растрова графіка використовується в випадках, коли потрібна висока точність в передачі кольорів і напівтонів. Однак при цьому розміри файлів суттєво збільшуються з ростом роздільної здатності (одиниці, десятки і сотні Мбайт). До недоліків растрової графіки, окрім великих розмірів файлів, слід віднести пікселізацію зображень при їх збільшенні та деформацію при зменшенні.
В векторній графіці базовим елементом зображення є лінія, яка описується математично як єдиний об’єкт, тому обсяг даних для відображення об’єкта засобами векторної графіки суттєво менший, ніж в растровій графіці. Лінія характеризується формою, товщиною, кольором, типом (суцільна, пунктирна і т.п.). Замкнуті лінії мають властивість заповнення простору, що ними охоплюються, іншими об’єктами або кольором. Найпростіша незамкнута лінія обмежена двома точками, які називаються вузлами, котрі мають властивості, що впливають на форму кінця лінії і характер сполучення з іншими об’єктами. Всі інші об’єкти векторної графіки складаються з ліній. Найпростішими лініями є пряма (нескінченна), відрізок прямої, криві другого порядку (не мають точок згину – параболи, гіперболи, еліпси, кола), криві третього порядку (можуть мати точки згину), криві Безьє (основані на використанні пари дотичних, проведених до відрізка лінії в її кінцях, кути нахилу і довжина яких впливають на форму лінії).
Векторна графіка зручна для зберіганні і обробки зображень, що складаються з ліній, або можуть бути розкладені на прості геометричні об’єкти. Векторні дані легко масштабувати та виконувати над ними інші перетворення (наприклад, повертання зображення, додавання, видалення або зміну окремих елементів зображення). Поряд з цим векторні файли важко застосувати для зберігання складних фотореалістичних зображень. Векторні дані краще відображаються на векторних пристроях виводу (плотерах, дисплеях з довільним скануванням). Ефективно векторну графіку можна відобразити тільки на растрових дисплеях з високою роздільною здатністю.
Фрактальна графіка, як і векторна, основана на математичних обчисленнях. ЇЇ базовим елементом є математична формула, виключно на основі якої будується зображення. Таким способом будують як найпростіші регулярні структури, так і складні ілюстрації, що імітують природні ландшафти і тривимірні об’єкти.
1. 2 Формати графічних файлів
Для зберігання зображень в комп’ютерній графіці використовують декілька десятків форматів файлів. Деяка частина з них стала стандартами і використовується в більшості графічних програм. За типами графічні формати можна розділити на:
растрові формати – призначені для зберігання растрових даних;
векторні формати – призначені для зберігання векторних даних;
метафайлові формати – можуть зберігати як растрові, так і векторні дані;
формати сцени – містять додатково інструкції, що дозволяють програмі візуалізації відновити зображення цілком;
формати анімації – прості дозволяють відображати зображення в циклі одне за іншим, а більш складні зберігають початкове зображення та різниці між двома зображеннями, які послідовно відображаються;
мультимедійні формати – призначені для зберігання даних різних типів (графіки, звуку, відео) в одному файлі;
тривимірні формати – містять опис форми і кольору об’ємних моделей.
3 Методи стискання зображень
Стискання здійснюється з метою зменшення фізичного розміру блоку інформації. Стискання інформації здійснює програма-компресор, а відновлення – програма-декомпресор.
Стискання растрових і векторних даних здійснюється по-різному. В растрових файлах стискаються тільки дані зображення, а заголовок і решта даних (таблиця кольорів, кінцівка і т.п.) завжди залишаються нестисненими (вони, як правило, займають незначну частину растрового файла). Векторні файли, в яких зберігається математичний опис зображення, а не самі дані, як правило, не мають “рідної” форми стискання. Це викликано тим, що в векторному форматі дані вже представлені в компактній формі і стискання дає дуже незначний ефект. Окрім цього звичайно векторні дані читаються з незначною швидкістю і при додаванні розпаковування цей процес може стати ще більш повільним. Якщо векторний файл все ж стискається, то, як правило, стискаються всі дані, включаючи заголовок.
Більшість алгоритмів стискання забезпечують кодування без втрат, коли дані при розпаковуванні повністю відновлюються. Методи кодування з втратами передбачають відкидання деяких даних зображення для досягнення кращої міри стискання, ніж за методами без втрат. При цьому важливо, щоб втрата деякої частини даних була прийнятною або навіть доцільною. Найбільш поширеними алгоритмами стискання даних є групове кодування (RLE), алгоритм Лемпела-Зіва-Велча (LZW), кодування CCITT (Хафмена), технологія JPEG, алгоритм ART, алгоритми фрактального стискання зображень.
Алгоритм RLE зменшує фізичний розмір рядків символів, що повторюються. Такі рядки називають групами і кодують двома байтами, перший з яких визначає кількість символів в групі, а другий містить значення символу. Ефективність стискання залежить від типу даних зображення. Краще стискаються чорно-білі зображення, які містять багато білого кольору, а гірше – фотореалістичні зображення з великою кількістю кольорів. Алгоритм RLE характеризується простотою і високою швидкодією. Варіанти групового кодування розрізняються напрямом утворення рядка (вздовж осі X, осі Y та діагоналі). Найчастіше вони стискають без втрат, однак відкидання молодших розрядів в значеннях символу може суттєво збільшити міру стискання складних зображень.
Алгоритм 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-зображення можуть бути багаторівневими. Це значить, що їх можна передавати поетапно по модемних лініях з низькою пропускною здатністю. Крім того, алгоритм забезпечує майже миттєве, хоча і низькоякісне, відображення на пристрої виведення клієнта. Потім, по мірі прийому даних і поступової візуалізації, якість зображення підвищується.
Фрактальне кодування засноване на тім факті, що всі природні і більшість штучних об'єктів містять надлишкову інформацію у виді однакових, повторюваних малюнків, які називаються фракталами. Процес кодування, що перетворює зображення в сукупність математичних даних, вимагає винятково великого обсягу обчислень. В залежності від розділь ної здатності і вмісту вхідних растрових даних, якості зображення, часу стиснення і розміру файлу процес стиснення одного зображення може зайняти від декількох секунд до декількох годин навіть на дуже швидко діючому комп'ютері. Декодування фрактального зображення – процес набагато більш простий, тому що вся трудомістка робота була виконана при пошуку всіх фракталів під час кодування. В процесі декодування потрібно лише інтерпретувати фрактальні коди, перетворивши їх у растрове зображення. Тому фрактальний метод доцільно використовувати тоді, коли дані зображень безупинно розпаковуються, але ніколи не стискуються. Фрактальний метод забезпечує легкість масштабування зображення без введення артефактів і втрати деталей та невеликий розмір стиснених даних, але супроводжується втратами.
1.4 Порівняння методів стискання зображень
Усього на даний момент відомо мінімум три сімейства алгоритмів, які розроблені винятково для стиску зображень, і застосовувані в них методи практично неможливо застосувати до архівації ще яких-небудь видів даних.
Для того, щоб говорити про алгоритми стиску зображень, ми повинні визначитися з декількома важливими питаннями:
1) Які критерії ми можемо запропонувати для порівняння різних алгоритмів?
2) Які класи зображень існують?
3) Які класи об’єктів, що використовують алгоритми компресії графіки, існують, і які вимоги вони пред'являють до алгоритмів? Розглянемо ці питання докладніше.
1.4.1 Класифікація зображень
Статичні растрові зображення являють собою двомірний масив чисел. Елементи цього масиву називаються “пікселами” (від англійського «pixel» - picture element). Всі зображення можна підрозділити на дві групи: з палітрою й без неї. У зображень із палітрою в пікселі зберігається число - індекс у деякому одномірному векторі кольорів, названому палітрою. Найчастіше зустрічаються палітри з 16 й 256 кольорів.
Зображення без палітри бувають у певній системі представлення кольорів у градаціях сірого (gray scale). Для останніх значення кожного піксела інтерпретується як яскравість відповідної точки. Найчастіше зустрічаються зображення з 2, 16 й 256 рівнями сірого. Одне із цікавих практичних завдань полягає в приведенні кольорового або чорно-білого зображення до двох градацій яскравості, наприклад, для друку на лазерному принтері.
При використанні якоїсь системи представлення кольорів кожен піксел являє собою запис (структуру), полями якої є компоненти кольорів. Найпоширенішою є система RGB, у якій кольори передається значеннями інтенсивності червоної (R), зеленої (G) і синьої (В) компонент. Існують й інші системи представлення кольорів, такі, як CMYK, СIЕ XYZccir60-1, YVU, YCrCb і т.п.
Для того, щоб коректніше оцінювати ступінь стиску, потрібно ввести поняття класу зображень. Під класом буде розумітися сукупність зображень, застосування до яких алгоритму архівації дає якісно однакові результати. Наприклад, для одного класу алгоритм дає дуже високий ступінь стиску, для іншого майже не стискає, для третього збільшує файл у розмірі. (Наприклад, всі алгоритми стиску без втрат у найгіршому разі збільшують файл).
Дамо неформальне визначення найпоширеніших класів зображень:
1) Клас 1. Зображення з невеликою кількістю кольорів (4-16) і великими областями, заповненими одним кольорами. Плавні переходи кольорів відсутні. Приклади: ділова графіка — гістограми, діаграми, графіки й т.д.
2) Клас 2. Зображення із плавними переходами кольорів, побудовані на комп'ютері. Приклади: графіка презентацій, ескізні моделі в САПР, зображення, побудовані по методу Гуро.
3) Клас 3. Фотореалістичні зображення. Приклад: відскановані фотографії.
4) Клас 4. Фотореалістичні зображення з накладенням ділової графіки. Приклад: реклама.
Розвиваючи дану класифікацію, як окремі класи можуть бути запропоновані неякісно відскановані в 256 градацій сірих кольорів сторінки книг або растрові зображення топографічних карт. (Відмітимо, що цей клас не тотожний класу 4). Формально будучи 8- або 24-бітними, вони несуть не растрову, а чисто векторну інформацію. Окремі класи можуть утворювати й зовсім специфічні зображення: рентгенівські знімки або фотографії в профіль і фас із електронного досьє.
Досить складним і цікавим завданням є пошук найкращого алгоритму для конкретного класу зображень.
Підсумок: Нема рації говорити про те, що якийсь алгоритм стиску краще іншого, якщо ми не позначили класи зображень, на яких рівняються наші алгоритми.
1.4.2 Класи об’єктів, які використовують алгоритми компресії
Приклади об’єктів, що використають алгоритми компресії графіки:
Розглянемо наступну просту класифікацію додатків, що використають алгоритми компресії:
1) Клас 1. Характеризуються високими вимогами вчасної архівації й розархівації. Нерідко потрібен перегляд зменшеної копії зображення й пошук у базі даних зображень. Приклади: Видавничі системи в широкому сенсі цього слова, причому як і якісні публікації, які готують журнали зі свідомо високою якістю зображень і використанням алгоритмів архівації без втрат, так і газети, і WWW-сервери, де є можливість оперувати зображеннями меншої якості й використати алгоритми стиску із втратами. У подібних системах доводиться мати справу з повноколірними зображеннями найрізноманітнішого розміру (від 640х480- формат цифрового фотоапарата, до 3000х2000) і з більшими двоколірними зображеннями. Оскільки ілюстрації займають левину частку від загального обсягу матеріалу в документі, проблема зберігання стоїть дуже гостро. Проблеми також створює більша різнорідність ілюстрацій (доводиться використовувати універсальні алгоритми). Єдине, що можна сказати заздалегідь, це те, що будуть переважати фотореалістичні зображення й ділова графіка.
2) Клас 2. Характеризується високими вимогами до ступеня архівації й часу розархівації. Час архівації ролі не грає. Іноді подібні об’єкти також вимагають від алгоритму компресії легкості масштабування зображення під конкретне розширення монітора в користувача. Приклад: довідники й енциклопедії на CD-ROM. З появленим великої кількості комп'ютерів, оснащених цим приводом (у США рівень в 50% машин досягнуто ще в 1995), досить швидко сформувався ринок програм, які видають на лазерних дисках. Незважаючи на те, що ємність одного диска досить велика (650 Мб), її, як правило, не вистачає. При створенні енциклопедій й ігор більшу частину диска займають статичні зображення й відео. Таким чином, для цього класу додатків актуальність здобувають істотно асиметричні за часом алгоритми (симетричність у часі - відношення часу компресії до часу декомпресії).
3) Клас 3. Характеризується дуже високими вимогами до ступеня архівації. Об’єкт клієнт одержує від сервера з мережі. Приклад: Нова, яка швидко розвивається, система <Всесвітня інформаційна павутина» — WWW. У цій гіпертекстовій системі досить активно використовуються ілюстрації. При оформленні інформаційних або рекламних сторінок хочеться зробити їх ще більше яскравими й барвистими, що, природно, позначається на розмірі зображень. Найбільше при цьому страждають користувачі, підключені до мережі за допомогою повільних каналів зв'язку. Якщо сторінка WWW перенасичена графікою, то очікування її повної появи на екрані може затягтися. Оскільки при цьому навантаження на процесор мале, то тут можуть знайти застосування ефективно стискаючі складні алгоритми з порівняно більшим часом розархівації. Крім того, ми можемо видозмінити алгоритм і формат даних так, щоб переглядати огрублене зображення файлу до його повного одержання.
Можна привести безліч більш вузьких класів об’єктів. Так, своє застосування машинна графіка знаходить й у різних інформаційних системах. Наприклад, уже стає звичним досліджувати ультразвукові й рентгенівські знімки не на папері, а на екрані монітора. Поступово в електронний вид переводять й історії хвороб. Зрозуміло, що зберігати ці матеріали логічніше в єдиній картотеці. При цьому без використання спеціальних алгоритмів більшу частину архівів займуть фотографії. Тому при створенні ефективних алгоритмів рішення цього завдання потрібно врахувати специфіку рентгенівських знімків - перевага розмитих ділянок.
У геоінформаційних системах - при зберіганні аерофотознімків місцевості - специфічними проблемами є великий розмір зображення й необхідність вибірки лише частини зображення на вимогу. Крім того, може знадобитися масштабування. Це неминуче накладає свої обмеження на алгоритм компресії.
В електронних картотеках і досьє різних служб для зображень характерна схожість між фотографіями в профіль і фотографіями в фас, що також необхідно враховувати при створенні алгоритму архівації. Подоба між фотографіями спостерігається й у будь-яких інших спеціалізованих довідниках. Як приклад можна привести енциклопедії птахів або квітів.
Підсумок: Нема рації говорити про те, що якийсь конкретний алгоритм компресії краще за інший, якщо ми не позначили клас додатку, відносно якого ми ці алгоритми збираємося порівнювати.
1.4.3 Вимоги об’єктів до алгоритмів компресії
У попередньому розділі ми визначили, які об’єкти є споживачами алгоритмів архівації зображень. Однак відзначимо, що об’єкт визначає характер використання зображень (або велика кількість зображень зберігається й використовується, або зображення скачуються по мережі, або зображення великі за розміром, і нам необхідна можливість одержання лише частини...). Характер використання зображень задає ступінь важливості наступних нижче суперечливих вимог до алгоритму:
1. Високий ступінь компресії. Помітимо, що далеко не для всіх об’єктів актуальний високий ступінь компресії. Крім того, деякі алгоритми дають краще співвідношення якості до розміру файлу при високих ступенях компресії, однак програють іншим алгоритмам при низьких ступенях.
2. Висока якість зображень. Виконання цієї вимоги прямо суперечить попередній вимозі.
3. Висока швидкість компресії. Це вимога для деяких алгоритмів із втратою інформації є взаємовиключним з першими двома. Інтуїтивно зрозуміло, що чим більше часу ми будемо аналізувати зображення, намагаючись одержати найвищий ступінь компресії, тим краще буде результат, і, відповідно, чим менше ми часу витратимо на компресію (аналіз), тим нижче буде якість зображення й більше його розмір.
4. Висока швидкість декомпресії. Досить універсальна вимога, актуальне для багатьох додатків. Однак можна привести приклади додатків, де час декомпресії далеко не критично.
5. Масштабування зображень. Дана вимога має на увазі легкість зміни розмірів зображення до розмірів вікна активного об’єкта. Справа в тому, що одні алгоритми дозволяють легко масштабувати зображення прямо під час декомпресії, у той час як інші не тільки не дозволяють легко масштабувати, але й збільшують імовірність появи неприємних артефактів після застосування стандартних алгоритмів масштабування до декомпресованого зображення. Наприклад, можна привести приклад «поганого» зображення для алгоритму JPEG - це зображення з досить дрібним регулярним малюнком (піджак у дрібну клітку). Характер внесених алгоритмом JPEG перекручувань такий, що зменшення або збільшення зображення може дати неприємні ефекти.
6. Можливість показати огрублене зображення (низької роздільної здатності), використавши тільки початок файлу. Дана можливість актуальна для різного роду мережевих об’єктів, де перекачування зображень може зайняти досить великий час, і бажано, одержавши початок файлу, коректно показати preview. Помітимо, що примітивна реалізація зазначеної вимоги шляхом записування в початок зображення його зменшеної копії помітно погіршить ступінь компресії.
7. Стійкість до помилок. Дана вимога означає локальність порушень у зображенні при псуванні або втраті фрагмента переданого файлу. Дана можливість використається при широкомовленні (broadcasting — передача багатьом адресам) зображень по мережі, тобто в тих випадках, коли неможливо використати протокол передачі, повторно запитуючи дані в сервера при помилках. Наприклад, якщо передається відеоряд, то було б неправильно використати алгоритм, у якого збій приводив би до припинення правильного показу всіх наступних кадрів. Дана вимога суперечить високому ступеню архівації, оскільки інтуїтивно зрозуміло, що ми повинні вводити в потік надлишкову інформацію. Однак для різних алгоритмів обсяг цієї надлишкової інформації може істотно відрізнятися.
8. Облік специфіки зображення. Більше високий ступінь архівації для класу зображень, які статистично частіше будуть застосовуватися в нашому об’єкті. У попередніх розділах ця вимога вже обговорювалася.
9. Редагованість. Під редагованістю розуміється мінімальний ступінь погіршення якості зображення при його повторному збереженні після редагування. Багато алгоритмів із втратою інформації можуть істотно зіпсувати зображення за кілька ітерацій редагування.
10. Невелика вартість апаратної реалізації. Ефективність програмної реалізації. Дані вимоги до алгоритму реально пред'являють не тільки виробники ігрових приставок, але й виробники багатьох інформаційних систем. Так, декомпресор фрактального алгоритму дуже ефективно й коротко реалізується з використанням технології ММХ і розпаралелюванням обчислень, а стиск за стандартом CCITT group 3 легко реалізується апаратно. Очевидно, що для конкретного завдання нам будуть дуже важливі одні вимоги й менш важливі (і навіть абсолютно байдужі) інші.
Підсумок: На практиці для кожного завдання ми можемо сформулювати набір пріоритетів з вимог, викладених вище, що і визначить найбільш підходящий у наших умовах алгоритм (або набір алгоритмів) для її рішення.
1.4.4 Критерії порівняння алгоритмів
Відзначимо, що характеристики алгоритму щодо деяких вимог додатків, сформульовані вище, залежать від конкретних умов, у які буде поставлений алгоритм. Так, ступінь компресії залежить від того, на якому класі зображень алгоритм тестується. Аналогічно, швидкість компресії нерідко залежить від того, на якій платформі реалізований алгоритм. Перевага одному алгоритму перед іншим може дати, наприклад, можливість використання в обчисленнях алгоритму технологій нижнього рівня, типу ММХ, а це можливо далеко не для всіх алгоритмів. Так, JPEG істотно виграє від застосування технології ММХ, а LZW - немає. Крім того, нам доведеться враховувати, що деякі алгоритми розпаралелюються легко, а деякі ні.
Таким чином, неможливо скласти універсальний порівняльний опис відомих алгоритмів. Це можна зробити тільки для типових класів об’єктів за умови використання типових алгоритмів на типових платформах. Однак такі дані надзвичайно швидко робляться застарілими.
Так, наприклад, ще в 1994р. інтерес до показу огрубленого зображення, використовуючи тільки початок файлу (вимога 6), був чисто абстрактним. Реально ця можливість практично ніде не була потрібна й клас об’єктів, що використають дану технологію, був украй невеликий. З вибуховим поширенням Internet, що характеризується передачею зображень по порівняно повільних каналах зв'язку, використання Interlaced GIF (алгоритм LZW) і Progressive JPEG (варіант алгоритму JPEG), що реалізують цю можливість, різко зросло. Те, що новий алгоритм (наприклад, wavelet) підтримує таку можливість, найсуттєвіший плюс для нього сьогодні.
У той же час ми можемо розглянути таку рідкісну на сьогодні вимогу, як стійкість до помилок. Можна припустити, що незабаром (через 5-10 років) з поширенням широкомовлення в мережі Internet для його забезпечення будуть використовуватися саме алгоритми, стійкі до помилок, навіть не розглянуті в сьогоднішніх статтях й оглядах.
З усіма зробленими вище застереженнями, виділимо трохи найбільш важливих для нас критеріїв порівняння алгоритмів компресії, які й будемо використати надалі. Як легко помітити, ми будемо обговорювати менше критеріїв, ніж було сформульовано вище. Це дозволить уникнути зайвих деталей при викладі.
1. Гірший, середній і кращий ступінь стиску. Тобто частка. на яку зросте зображення, якщо вихідні дані будуть найгіршими; якийсь середньостатистичний ступінь для того класу зображень, на який орієнтований алгоритм; і, нарешті, кращий ступінь. Останнє необхідне лише теоретично, оскільки показує ступінь стиску найкращого (як правило, абсолютно чорного) зображення, іноді фіксованого розміру.
2. Клас зображень, на який орієнтований алгоритм. Іноді зазначено також, чому на інших класах зображень виходять гірші результати.
З. Симетричність. Відношення характеристики алгоритму кодування до аналогічної характеристики при декодуванні. Характеризує ресурсоємність процесів кодування й декодування. Для нас найбільш важливою є симетричність за часом: відношення часу кодування до часу декодування. Іноді нам буде потрібно симетричність за пам'яттю.
4. Є чи втрата якості? І якщо є, то за рахунок чого змінюється ступінь стиску? Справа в тому, що в більшості алгоритмів стиску із втратою інформації існує можливість зміни ступеня стиску.
5. Характерні риси алгоритму й зображень, до яких його застосовують. Тут можуть вказуватися найбільш важливі для алгоритму властивості, які можуть стати визначальними при його виборі.
Використовуючи дані критерії, приступимо до розгляду алгоритмів архівації зображень та порівняння їх з алгоритмом FELICS.
Перш, ніж безпосередньо почати розмову про алгоритми, потрібно зробити застереження. Той самий алгоритм часто можна реалізувати різними способами. Багато відомих алгоритмів, таких як RLE, LZW або JPEG, мають десятки різних реалізацій. Крім того, в алгоритмів буває кілька явних параметрів, змінюючи які, можна змінювати характеристики процесів архівації й розархівації.. При конкретній реалізації ці параметри фіксуються, виходячи з найбільш імовірних характеристик вхідних зображень, вимог на економію пам'яті, вимог на час архівації й т.д. Тому в алгоритмів одного сімейства кращий і гірший ступені стиску можуть відрізнятися, але якісно картина не зміниться.
Визначення характеристик методу FELICS
Очевидно, що порівнювати FELICS можна лише з йому подібними, тобто з методами стискання зображень загального призначення без втрат (це LZW, lossless JPEG, RLE тощо). Порівняння може бути здійснене за критеріями порівняння алгоритмів, описаними вище у розділі 1.4.4. Отже:
Ступінь стиску. В оригінальному авторському описанні методу зазначено, що ступінь стиску аналогічний lossless JPEG. З цього можна визначити, що ступінь стискання не є дуже високий, але з огляду на відсутність втрат, достатній. В найгіршому випадку зображення збільшується.
Клас зображень. Алгоритм за своєю суттю є універсальним, але найкращі результати отримуються при ...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора