На головну
МІНІСТЕРСТВО ЗВ'ЯЗКУ ТА ІНФОРМАТИЗАЦІЇ РЕСПУБЛІКИ БІЛОРУСЬ
Установа освіти
"ВИЩИЙ ДЕРЖАВНИЙ КОЛЕДЖ ЗВ'ЯЗКУ"
ФАКУЛЬТЕТ ЕЛЕКТРОЗВ'ЯЗКУ
Реферат на тему:
Методи стиснення статичних зображень, алгоритм SPIHT
з дисципліни:
"Цифрова обробка мови і зображення"
Виконав студент гр. ПО941
Гамановіч С.В.
Мінськ 2011
Методи стиснення статичних зображень, алгоритм SPIHT
Основні методи стиснення статичних зображень:
· Зниження глибини кольору
· Метод головних компонент
· Фрактальное стиск
· Стиснення на основі провісників
· ДІКМ
· Ієрархічна сіткова інтерполяція
· JPEG
· Вейвлетного компресія
· JPEG 2000
Вейвлетного стиск - загальна назва класу методів кодування зображень, що використовують двовимірне вейвлет-розкладання кодованого зображення або його частин. Зазвичай мається на увазі стиснення з втратою якості.
Істотну роль в алгоритмах вейвлетного компресії відіграє концепція представлення результатів вейвлет-розкладання у вигляді нуль-дерева (zero-tree). Впорядковані в нуль-дереві бітові площини коефіцієнтів вейвлет-розкладання огрубляются і кодуються далі з використанням статистичних методів стиснення.
Вейвлетного компресія в сучасних алгоритмах компресії зображень дозволяє значно (до двох разів) підвищити ступінь стиснення чорно-білих і кольорових зображень при порівнянному візуальній якості по відношенню до алгоритмів попереднього покоління, заснованим на дискретній косинусном перетворенні, таких, наприклад, як JPEG.
DjVu (від фр. Deja vu - "вже бачене") - технологія стиснення зображень з втратами, розроблена спеціально для зберігання відсканованих документів - книг, журналів, рукописів та інше, де велика кількість формул, схем, малюнків і рукописних символів робить надзвичайно трудомістким їх повноцінне розпізнавання. Також є ефективним рішенням, якщо необхідно передати всі нюанси оформлення, наприклад, історичних документів, де важливе значення має не тільки зміст, а й колір і фактура паперу; дефекти пергаменту: тріщини, сліди від складання; виправлення, плями, відбитки пальців; сліди, залишені іншими предметами і т.д.
JPEG 2000 (або jp2) - графічний формат, який замість дискретного косинусного перетворення, застосовуваного в форматі JPEG, використовує технологію вейвлет-перетворення, що грунтується на уявленні сигналу у вигляді суперпозиції базових функцій - хвильових пакетів.
В результаті такої компресії зображення виходить більш гладким і чітким, а розмір файлу в порівнянні з JPEG при однаковій якості виявляється меншим. JPEG 2000 повністю вільний від головного недоліку свого попередника: завдяки використанню вейвлетов, зображення, збережені в цьому форматі, при високих ступенях стиснення не містять артефактів у вигляді "решітки" з блоків розміром 8х8 пікселів. Формат JPEG 2000 так само, як і JPEG, підтримує так зване "прогресивне стиснення", що дозволяє у міру завантаження бачити спочатку розмите, але потім все більш чітке зображення.
Алгоритм фрактального стиснення зображення відносять до алгоритмів архівації з частковою втратою інформації. Основа методу фрактального кодування - це виявлення самоподібних ділянок в зображенні. Ідея компресії зображення заснована на застосувань систем ітеріруемих функцій.
Фрактал - це нескінченно самоподібна геометрична фігура, кожен фрагмент якої повторюється при зменшенні масштабу.
вейвлетного компресія зображення алгоритм
Рисунок 1 - приклад фрактала
Фрактальний алгоритм дозволяє стискати зображення в сотні і навіть тисячі разів.
Основна складність фрактального стиснення полягає в тому, що для знаходження відповідних доменних блоків, потрібен повний перебір.
Оскільки при цьому переборі кожен раз повинні порівнюватися два масиви, дана операція виходить досить тривалою, що вимагає значних обчислювальних ресурсів.
На сьогоднішній день фрактальні методи найкращим чином пристосовані для додатків архівування, таких як цифрові енциклопедії, в яких кодування необхідно лише одного разу, а декодування відбувається безліч разів.
Фрактальні методи можна розглядати, як альтернативу технологіям, заснованим на перетворенні Фур'є, наприклад, таким як JPEG. Нові технології, такі як фрактальні повинні розглядатися не тільки як конкуренти, але і як союзники у встановленні нових стандартів.
Алгоритм SPIHT (Просторово Впорядковані Ієрархічні Дерева) являє собою метод стиснення зображень з втратами і володіє високою чутливістю. Його легко реалізовувати, він працює швидко і дає прекрасні результати при стисненні будь-яких типів зображень.
Метод SPIHT був розроблений для оптимальної прогресуючої передачі зображень, а також для їх стиснення. Найважливіша особливістю цього алгоритму полягає в тому, що на будь-якому етапі декодування якість відображуваної в цей момент картинки є найкращим для введеного обсягу інформації про даному образі.
Інша відмінна риса алгоритму SPIHT полягає у використанні їм вкладеного кодування. Це властивість можна визначити наступним чином: якщо кодер, який використовує вкладене кодування, виробляє два файли, великий обсягу М біт і маленький обсягу n біт, то менший файл збігається з першими M битами більшого файлу.
Наступний приклад вдало ілюструє це визначення. Припустимо, що три користувача очікують деякий відправлене їм стислий зображення. При цьому їм потрібно різне якість цього зображення. Першому з них вимагається якість, що забезпечується 10 KB образу, а другий і третій користувачеві необхідно якість, відповідно, в обсязі 20 KB і 50 КВ. Більшості методів стиснення зображення з частковою втратою даних буде потрібно стискати вихідний образ три рази з різною якістю, для того, щоб згенерувати три різних файлу, необхідних обсягів. А метод SPIHT справить для цих цілей всього один файл, і користувачам будуть послані три початкових фрагмента цього файлу, довжини яких відповідно рівні 10 KB, 20 KB і 50 КВ.
На одному з його етапів застосовується вейвлетного перетворення. Крім того, основна структура даних цього алгоритму, просторово орієнтоване дерево, використовує той факт, що різні піддіапазони відображають різні геометричні особливості образу. Перетворення Хаара можна застосовувати до зображення кілька разів поспіль. При цьому утворюються різні області (піддіапазони), що складаються з середніх і деталей даного образу. Перетворення Хаара є дуже простим і наочним, але для кращого стиснення варто використовувати інші вейвлетного фільтри, які краще концентрують енергію зображення.
Різні вейвлетного фільтри будуть давати різні коефіцієнти стиснення для різних типів зображень. Однак дослідникам поки не до кінця ясно, як побудувати найкращий фільтр для кожного типу образів. Незалежно від конкретно використовуваного фільтра, образ розкладається на піддіапазони так, що нижні піддіапазони відповідають високим частотам зображення, а верхні піддіапазони відповідають низьким частотам образу, в яких концентрується основна частина енергії зображення. Тому можна очікувати, що коефіцієнти деталей зображення зменшуються при переміщенні від високого рівня до більш низького. Крім того, є певне просторове подобу між піддіапазонами. Частини образу, такі як піки, займають одну і ту ж просторову позицію в усіх піддіапазонах.
Малюнок 2 - піддіапазони і рівні вейвлетного розкладання.
Почнемо з загального опису методу SPIHT. Позначимо пікселі початкового зображення р через pij. Будь-яке безліч фільтрів Т може бути використано для перетворення пікселів в вейвлетного коефіцієнти (або коефіцієнти перетворення) Cij. Ці коефіцієнти утворюють перетворений образ с. Саме перетворення позначається с = Т (р). При прогресуючому методі передачі декодер починає з того, що привласнює значення нуль реконструйованому образу с. Потім він приймає (кодовані) перетворені коефіцієнти, декодує їх і використовує для отримання поліпшеного способу с, який, у свою чергу, виробляє покращене зображення р = Т-1 (с). Основна мета прогресуючого методу полягає в якнайшвидшій передачі найважливішої частини інформації про зображення. Ця інформація дає найбільше скорочення розбіжності вихідного і реконструйованого образів. Для кількісного виміру цієї розбіжності метод SPIHT використовує среднеквадратическую помилку MSE (mean squared error).
Найбільші (за абсолютною величиною) коефіцієнти Cij несуть в собі інформацію, яка найбільше скорочує розбіжність MSE, тому прогресуюче кодування повинно посилати ці коефіцієнти в першу чергу. У цьому полягає перший важливий принцип SPIHT. Інший принцип заснований на спостереженні, що найбільш значущі біти довічних уявлень цілих чисел прагнуть бути одиницями, коли ці числа наближаються до максимальних значень. (Наприклад, в 16-бітному комп'ютері число +5 має уявлення 0 | 000.0101, а велике число +65382 запишеться у вигляді 0 | 111111101100110. Це наводить на думку, що старші біти містять найбільш значущу частину інформації, і їх також слід посилати (або записувати в стислий масив даних) в першу чергу.
Головним недоліком цього алгоритму є великий обсяг інформації координат переданих значущих коефіцієнтів. Для того щоб оптимізувати даний процес в алгоритмі SPIHT поступають таким чином. Розбивають всі безліч коефіцієнтів на підмножини, наприклад, так як показано на малюнку 3.
Малюнок 3 - приклад розташування множин Tk
Потім, переглядають кожне множествоі перевіряють, чи є в них значущі коефіцієнти, тобто коефіцієнти, що задовольняють умові. Якщо знайдений в множествехотя б один такий коефіцієнт, то така безліч також вважається істотним. Припустимо, що в нашому прикладі значущим безліччю є тільки. Тоді воно розбивається на підмножини, для яких виконується така ж перевірка коефіцієнтів. І так далі поки не дійдемо до множин, що складаються з одного коефіцієнта. В результаті декодера передається битовая інформація, яка вказує, чи є конкретне множествозначімим чи ні. Завдяки ієрархічній структурі множин, загальний обсяг інформації про розташування значущих коефіцієнтів стає менше, ніж проста передача їх координат.
Основні кроки кодера SPIHT
Крок 1: Для заданого стискуваного зображення обчислити його вейвлетного перетворення, використовуючи відповідні вейвлетного фільтри, розкласти його на коефіцієнти перетворення qj і представити їх у вигляді цілих чисел фіксованою розрядності. Припустимо, що коефіцієнти представлені у вигляді цілих чисел зі знаком, розрядність яких дорівнює 16, причому самий лівий біт є знаковим, а в інших довічних 15 розрядах записаний модуль цього числа. (Зазначимо, що таке подання відрізняється від комплементарного представлення чисел зі знаком, яке традиційно застосовується в комп'ютерах.) Значення цих чисел змінюються в діапазоні від - (215- 1) до (215- 1). Привласнимо змінної n значення n = [log2 (215- 1) J = 14.
Крок 2: Сортування. Передати число I коефіцієнтів які задовольняють нерівності 2n <\ c, ij \ <2n + 1. Потім передати I пар координат і I знаків цих коефіцієнтів.
Крок 3: Поправка. Передати (n - 1) - ті самі старші біти всіх коефіцієнтів, що задовольняють нерівності \ c {j \> 2n. Ці коефіцієнти були обрані на кроці сортування попередній ітерації циклу (не цією ітерації!).
Крок 4: Ітерація. Зменшити n на 1. Якщо необхідно зробити ще одну ітерацію, піти на Крок 2. Зазвичай остання ітерація відбувається при n = 0, але кодер може зупинитися раніше. У цьому випадку найменш важлива частина інформації (деякі менш значущі біти всіх вейвлетного коефіцієнтів) не буде передаватися. У цьому полягає природне відкидання частини інформації в методі SPIHT. Це еквівалентно скалярному квантованию, але результат виходить краще, оскільки коефіцієнти передаються в впорядкованої послідовності. В альтернативі кодер передає весь образ (тобто, всі біти всіх вейвлетного коефіцієнтів), а декодер може зупинити процес декодування в будь-який момент, коли відновлюване зображення досягло необхідної якості. Ця якість або зумовлюється користувачем, або встановлюється декодером автоматично по витраченому часу.
Розглянемо докладно, що собою являє кодування в алгоритмі SPIHT
Насамперед відзначимо, що кодер і декодер повинні використовувати єдиний тест при перевірці множин на істотність. Алгоритм кодування використовує три списки, які називаються: список істотних пікселів (LSP, list of significant pixels), список несуттєвих пікселів (LIP, list of insignificant pixels) і список несуттєвих множин (LIS, list of insignificant sets).
У ці списки заносяться координати (i, j) так, що в списках LIP і LSP вони представляють індивідуальні коефіцієнти, а в списку LIS вони представляють або безліч T> (i, j), або безліч C (i, j).
Список LIP містить координати коефіцієнтів, які були несуттєвими на попередній стадії сортування. У поточній стадії вони перевіряються, і якщо безліч є істотним, то вони переміщаються в список LSP. Аналогічно безлічі з LIS тестуються в послідовному порядку, і якщо виявляється, що безліч стало істотним, то воно видаляється з LIS і розділяється.
Нові підмножини, що складаються більш ніж з одного елемента, поміщаються назад в список LIS, де вони пізніше будуть піддані тестуванню, а одноелементні підмножини перевіряються і додаються в список LSP або LIP залежно від результатів тесту. Стадія поправки передає n-ний найстарший біт записів зі списку LSP.
Продуктивність алгоритму SPIHT можна підвищити за допомогою ентропійного кодування виходу, але з дослідів відомо, що це вносить вельми незначне поліпшення, яке не покривають тимчасові витрати на його виконання кодером і декодером. Виявляється, що розподіл знаків та індивідуальних бітів вейвлетного коефіцієнтів, вироблених на кожній ітерації, близький до рівномірного, тому ентропійне кодування не дає ефекту стиснення.