5.7 Методи стиснення зображень
В залежності від оброблюваного зображення всі методи стиснення зображень можна умовно поділити на методи стиснення бінарних зображень, півтонових зображень та кольорових зображень. Також стиснення може відбуватись із втратами інформації та без втрат. Розглянемо більш детально ці методи.
Методи стиснення без втрат
Факсовий метод
Факсовий (використовуваний у факсах) метод кодування полягає в тому, що кодуються одиницями перепад кольорів сусідніх пікселів в рядку, а нулем – відсутність перепаду (рис. 5.22). Для зображень, що містять однорідні ділянки великої площі, цей метод є надлишковим, легко кодується методами оптимізації.
До недоліків методу слід віднести: при збої виходять перешкоди у вигляді чорних або білих смуг; не використовується двовимірна природа зображення.
RLE метод
RLE код відрізняється тим, що порядково кодується колір пікселя і кількість пікселів цього кольору, що йдуть підряд у цьому рядку поки не зустрінеться зміна кольору (рис. 5.23).
Рисунок 5.23 – Приклад кодування RLE методом
Метод досить простий у реалізації і застосовується при стисненні bmp-зображень.
Недолік RLE методу полягає в тому, що він при стисненні зображення, у якому плавно змінюються кольори, приводить не до стиснення, а навпаки до збільшення розміру місця, займаного зображенням.
Кодування кутами Шлезенгера
Для простоти розглянемо стиснення чорно-білого зображення. Наприклад, маємо чорно-біле зображення, записане растром.
Для реалізації методу необхідно:
а) дописати рядок і стовпець нулів;
б) як запропонував Шлезенгер, надалі необхідно кодувати не кожен піксел, а четвірки пікселів. Таких четвірок може бути всього шістнадцять видів (рис. 5.24).
Рисунок 5.24 – Типи кутів Шлезенгера
З вихідної растрової (N +1) на (M +1) картинки ми отримаємо масив розміром N на M біт (рис. 5.25, а).
а) б)
Рисунок 5.25 – Результати кодування методом кутів Шлезенгера
Далі проводимо виділення кутів та записуємо їх у вигляді послідовності (рис. 5.25, б).
Наступним кроком є аналіз цієї послідовності. Якщо сканувати зліва направо, зверху вниз, і якщо є кут № 1, то його обов'язково замикає кут № 2. Тому для кодування використовуємо основні кути. Із зображення розміром N на M, кожен піксел якого є 1 біт, замінюємо зображенням основних кутів розміром 1 біт, вказуючи 1 – якщо кут дуальний (основний), і вказуючи 0 – якщо кут недуальний (неосновний).
Можна зробити такі висновки.
1. Отриманий растр менш надлишковий.
2. Перетворення є стискальним для зображень з великими площами рівної зафарбованості (креслення).
3. Дане кодування зворотне, тобто зображення відновлюється без втрат.
4. Перетворення Шлезенгера знижує ентропію, отже підвищує ступінь стиснення.
Wavelet – хвильове перетворення
Таке перетворення полягає в тому, що вихідний сигнал пропускається через систему лінійних фільтрів (як правило ФНЧ і ФВЧ), в результаті сигнали, отримані на виході цих фільтрів, пропускаються через аналогічні фільтри (рис. 5.26).
Рисунок 5.26 – Схема Wawelet-перетворення
У результаті отримуємо розкладання вихідного сигналу на складові, пропорційні ортогональним функціям імпульсних характеристик фільтрів, які називаються вейвлетами (Wavelet).
Фільтри, що зазвичай використовуються в Wavelet-парі повинні бути ортогональними, тобто, згортка імпульсних характеристик повинна дорівнювати нулю.
S-перетворення
Розглянемо принцип методу S-перетворення на основі певного прикладу.
Виберемо як сигнал певну послідовність відліків фіксованої величини S(i): SMIN Ј S(i) Ј SMAX .
Далі необхідно здійснити перетворення за схемою, що зображена на рис. 5.27.
Рисунок 5.27 – Схема S-перетворень
Таких перетворень необхідно здійснити (Log2N) раз, це буде кількість кроків.
У результаті S-перетворення отримаємо зображення з ентропією меншою, ніж у вихідного зображення за умови, що вихідне зображення було природного походження, тобто, поряд розташовані пікселі мали схожі характеристики (рис. 5.28).
Рисунок 5.28 – Результати S-перетворення
Це дає можливість стискати перетворені за допомогою цього методу зображення без втрат більш ефективно, ніж без використання
S-перетворення. Операція зворотна стисненню і абсолютно симетрична.
Методи стиснення із втратами
При стисненні зображень необов'язковим є стиснення без втрат. Це пояснюється особливостями зорового сприйняття людини. Тому незначні зміни кольорів зображення або його відтінків зазвичай залишаються непоміченими. Для характеристики втрат при стисненні використовують такі параметри.
1. Середня похибка:
.
де Dij – різниця в числових характеристиках піксела, що стоїть в i рядку і в j стовпці вихідного зображення і стисненого;
Xij – значення піксела вихідного зображення в точці (i, j).
Оцінити середню помилку на зображенні можна за формулою:
.
2. Максимальна помилка на зображенні:
.
Перевага методів стиснення із втратами у тому, що коефіцієнт стиснення на порядок вищий. Тому ці методи використовуються в мережі Інтернет, телекомунікаціях, супутниковому зондуванні тощо.
Метод JPEG
У цьому методі зображення розкладається за двовимірним косинус-перетворенням. Розглянемо приклад.
Нехай є функція ні парна, ні непарна, тоді перетворення Фур'є має складові і косинуси, і синуси (парна має тільки косинуси, непарна синуси). Доповнимо її симетрично і вона стане парною.
Косинусний спектр вихідної функції буде мати вигляд як на рис. 5.29.
Рисунок 5.29 – Вихідна функція стиснення
Стиснення відбувається за рахунок відкидання ВЧ частини складової спектра, що має малі амплітуди.
У результаті з'являється розмитість (рис. 5.30).
Рисунок 5.30 - Результат обробки
Даний метод стиснення є найбільш розповсюдженим внаслідок простоти реалізації. При цьому коефіцієнт стиснення методом JPEG – від десяти до декількох сотень. Метод зазвичай застосовується для зображень природного походження.
Фрактальний метод стиснення
Згідно з фрактальним методом зображення поділяється на певні подібні ділянки (фрактали), частина яких в подальшому відкидається (рис. 5.31).
Рисунок 5.31 – Поділ зображення на фрактали
У результаті отримано множину, що має нульову довжину – це множина кінців відрізків – канторова множина ( 2n / 3n ).
Фрактал – множина точок, результат канторової множини. Але не всякий фрактал є канторовою множиною. Фрактал має властивість самоподібності.
На початковому зображенні відшукуються самоподібні ділянки і вони беруться як базові елементи фрактального зображення. Останнє апроксимується за допомогою фрактальних перетворень, потім отримуємо зображення у вигляді формули, що відображає фрактальні перетворення.
Цей метод не отримав широкого поширення через ряд недоліків:
а) відсутність автоматичного перетворення для множини випадків.
б) похибка методу залежить від часу обчислення, щоб отримати гарне стиснення інформації необхідно витратити на стиснення декілька годин.
в) вузьке застосування – там, де необхідно створити за великий час компактний приклад сигналу.
SPITH-перетворення
Це перетворення базується на Wavelet-перетворенні. Відбувається нормування зображення за певною схемою і вводиться норма на пікселі, які множаться на вибрані коефіцієнти (рис. 5.32).
Рисунок 5.32 – Принцип SPITH-перетворення
Далі відкидаються ті коефіцієнти, які менші наперед заданого порогового значення. Процес повторюється доки зображення не стиснеться до необхідних меж або явно погіршиться якість.
До переваг даного методу можна віднести те, що при одних і тих самих коефіцієнтах стиснення втрат виходить менше, ніж при JPEG стисненні.
1. Які складові входять до типової системи передачі?
2. Які типи каналів зв’язку бувають?
3. Сформулюйте основні принципи завадостійкого кодування.
4. Які недоліки завадостійкого кодування?
5. Які ви знаєте коди з виявленням помилок? Дайте їx загальну характеристику.
6. Що являють собою систематичні коди?
7. Як працює кодер коду з перевіркою на парність?
8. Як працює декодер коду з перевіркою на парність?
9. Які коди відносяться до кодів з повторенням числа елементів?
10. Як працює кодер i декодер коду з прямим повторенням?
11. Кодер коду з інверсним повторенням. Алгоритм побудови.
12. Як працює декодер коду з інверсним повторенням?
13. Як працює кодер i декодер кореляційного коду?
14. Як кодується код Хемінга?
15. Алгоритм декодування коду Хемінга.
16. Побудуйте кодер коду Хемінга на 5 інформаційних розрядів.
17. Побудуйте декодер коду Хемінга (9, 5).
18. Яка залежність між кількістю інформаційних i контрольних символів коду Хемінга?
19. У чому сутність циклічного кодування?
20. Наведіть переваги та недоліки рекурентних кодів.
21. Розкрийте сутність алгоритму коду Шеннона-Фано.
22. Розкрийте сутність алгоритму коду Хаффмена.
23. Що розуміють під арифметичним кодуванням?
24. У чому відмінність динамічного кодування Хаффмена від звичайного?
25. Які модифікації має алгоритм динамічного кодування Хаффмена? Розкрийте їх суть.
26. Наведіть приклади методів стиснення зображень без втрат.
27. Які переваги та недоліки методів стиснення зображень із втратами?
