Поява недорогих цифрових фотоапаратів призвело до того, що значна частина жителів нашої планети, незалежно від віку і статі, придбала звичку запам'ятовувати кожен свій крок і виставляти отримані зображення на загальний огляд в соціальних мережах. Крім того, якщо раніше сімейний фотоархів містився в одному альбомі, то сьогодні він складається із сотень знімків. Для того щоб полегшити їх зберігання і передачу мережами, потрібно зменшення ваги цифрового зображення. З цією метою застосовуються методи, засновані на різних алгоритмах, включаючи вейвлет-перетворення. Що це таке, розповість наша стаття.

Що таке цифрове зображення

Візуальна інформація в комп'ютері представляється у вигляді чисел. Говорячи простою мовою, фото, зроблене цифровим апаратом, являє собою таблицю, в осередки якої вписані значення кольору кожного з його пікселів. Якщо мова йде про монохромному зображенні, то їх замінюють значеннями яскравості з відрізка[0, 1], де 0 використовують для позначення чорного кольору, а 1 — білого. Інші відтінки задаються дробовими числами, але з ними незручно працювати, тому діапазон розширюють і значення вибирають з відрізка між 0 та 255. Чому саме з цього? Все просто! При такому виборі в двійковому представленні для кодування яскравості кожного пікселя потрібно рівно 1 байт. Очевидно, що для зберігання навіть невеликого зображення потрібно досить багато пам'яті. Наприклад, фотографія розміром 256 х 256 пікселів займе 8 кБайт.

Кілька слів про методи стиснення зображень

Напевно, кожен бачив знімки поганої якості, де присутні спотворення у вигляді прямокутників одного кольору, які прийнято називати артефактами. Вони виникають в результаті так званого стиснення з втратами. Воно дозволяє значно зменшити вагу зображення, проте неминуче позначається на його якості.


До алгоритмів стиснення з втратами відносяться:

JPEG. На даний момент це один з найбільш популярних алгоритмів. Він заснований на застосуванні дискретного косинусного перетворення. Справедливості заради потрібно відзначити, що існують варіанти JPEG, здійснюють стиснення без втрат. До них відносяться Lossless JPEG і JPEG-LS.

JPEG 2000. Алгоритм використовується на мобільних платформах і заснований на застосуванні дискретного вейвлет-перетворення.

Алгоритм фрактального стиснення. У деяких випадках він дозволяє отримувати зображення відмінної якості навіть при сильному стисненні. Однак з-за проблем з патентуванням цей метод продовжує залишатися екзотикою.

Стиснення Без втрат здійснюють за допомогою алгоритмів:

RLE (використовується в якості основного методу в форматах TIFF, BMP, TGA).

LZW (застосовується у форматі GIF).

LZ-Huffman (використовується для формату PNG).

Перетворення Фур'є

Перш ніж перейти до розгляду вейвлетів, має сенс вивчити пов'язану з ними функцію, що описує коефіцієнти при розкладанні вихідної інформації на елементарні складові, тобто гармонійні коливання з різними частотами. Іншими словами, перетворення Фур'є — унікальний інструмент, що зв'язує дискретні і безперервні світи.
Воно виглядає так: Формула звернення записується наступним чином:

Що таке вейвлет

За цим назвою ховається математична функція, яка дозволяє проаналізувати різні частотні компоненти досліджуваних даних. Її графік являє собою хвилеподібні коливання, амплітуда яких зменшується до 0 вдалині від початку координат. У загальному випадку інтерес представляють вейвлет-коефіцієнти, що визначаються інтегральним перетворенням сигналу. Вейвлет-спектрограми відрізняються від звичайних спектрів Фур'є, оскільки пов'язують спектр різних особливостей сигналів з їх тимчасової компонентою.

Вейвлет-перетворення

Такий спосіб перетворення сигналу (функції) дозволяє переводити його з тимчасового в частотно-часове подання. Для того щоб вейвлет-перетворення було можливо, для відповідної вейвлет-функції повинні виконуватися наступні умови:

Якщо для деякої функції ? (t) Фур'є-перетворення має вигляд

повинно виконуватися умова: Крім того:

вейвлет повинен володіти кінцевою енергією;

він повинен бути интегрируемим, безперервним і мати компактний носій;

вейвлет повинен бути локалізованим як по частоті, так і в часі (в просторі).

Види

Безперервне вейвлет-перетворення для відповідних сигналів. Набагато більший інтерес представляє його дискретний аналог. Адже він може використовуватися для обробки інформації в комп'ютерах. Однак при цьому виникає проблема, пов'язана з тим, що формули для дискретного ДВП не можна отримати шляхом простої дискретизацією відповідних формул ДНП. Рішення даної задачі було знайдено В. Добеші, який зміг підібрати метод, що дозволяє побудувати серію таких ортогональних вейвлетів, кожен з яких визначається кінцевим числом коефіцієнтів. Пізніше були створені швидкі алгоритми, наприклад алгоритм Малла. При його застосуванні для розкладання або для відновлення потрібно здійснити порядку cN операцій, де N – довжина вибірки, а з – число коефіцієнтів.

Вайвлет Хаара

Для того щоб стиснути зображення, слід знайти певну закономірність серед його даних, а ще краще, якщо це будуть довгі ланцюжки нулів. Ось тут-то може знадобитися алгоритм вейвлет-перетворення. Однак продовжимо розгляд методу по порядку.
Спочатку потрібно згадати, що у яскравість фотографій сусідніх пікселів, як правило, відрізняється на незначну величину. Якщо навіть на реальних зображеннях присутні ділянки з різкими, контрастними перепадами яскравості, то вони займають лише малу частину зображення. В якості прикладу візьмемо всім відомий тестове зображення Lenna у градаціях сірого. Якщо взяти матрицю яскравості пікселів його, то частина першого рядка буде виглядати як послідовність чисел 154155156 157157157 158156. Для отримання нулів до неї можна застосувати так званий дельта-метод. Для цього зберігають тільки перше число, а для решти беруть лише відмінності кожного числа від попереднього зі знаком «+» або «-». В результаті вийде послідовність: 154111001-2. Недоліком дельта-кодування є його нелокальність. Іншими словами, неможливо брати тільки шматочок послідовності і з'ясувати, які яскравості в ньому закодовані, якщо не декодованими всі значення перед ним. Для подолання цього недоліку числа ділять на пари і для кожної знаходять полусумму (про. a) та полуразность (про. d), тобто для (154155),(156157),(157157),(158156) маємо (154505),(156505),(1570.0),(157-1.0). В такому випадку в будь-який момент можна знайти значення обох чисел в парі. В загальному випадку для дискретного вейвлет-перетворення сигналу S маємо: Такий дискретний метод випливає із випадку безперервного вейвлет-перетворення-Хаара і широко використовується в різних областях обробки і стиснення інформації.

Стиснення

Як вже було сказано, однією зі сфер застосування вейвлет-перетворення є алгоритм JPEG 2000. Стиснення з використанням методу Хаара засноване на перекладі вектора з двох пікселів X і Y у вектор (X + Y)/2 і (X - Y)/2. Для цього досить помножити вихідний вектор на матрицю, представлену нижче. Якщо точок більше, то беруть матрицю побільше, по діагоналі якої розташовані матриці H. Таким чином, вихідний вектор незалежно від своєї довжини обробляється парами.

Фільтри

Отримані «полусумми» — це середні значення яскравості в парах пікселів. Тобто значення при конвертації в зображення повинно дати його копію, зменшеною у 2 рази. При цьому полусумми усереднюють яскравості, тобто «відфільтровують» випадкові сплески їх значень і відіграють роль частотних фільтрів. Тепер розберемося з тим, що показують різниці. Вони виділяють межпиксельние «сплески», усуваючи константну складову, тобто «відфільтровують» значення з низькими частотами. Навіть з наведеного вище хаарівського вейвлет-перетворення для «чайників» стає очевидно, що воно являє собою пару фільтрів, які поділяють сигнал на дві складові: високочастотну та низькочастотну. Для отримання вихідного сигналу досить просто знову об'єднати ці складові.

Приклад

Нехай ми хочемо стиснути фотопортрет (тестове зображення Lenna). Розглянемо приклад вейвлет-перетворення його матриці яскравості пікселів. Високочастотна складова зображення відповідає за відображення дрібних деталей і описує шум. Що стосується низькочастотної, то вона несе в собі інформацію про форму обличчя і плавних перепадах яскравості. Особливості людського сприйняття фотографій такі, що важливіше остання компонента. Це означає, що при стисненні певна частина високочастотних даних може бути відкинута. Тим більше, що вона має менші значення і кодується більш компактно. Для збільшення ступеня стиснення можна застосувати перетворення Хаара кілька разів до низькочастотних даними.

Застосування до двовимірним масивів

Як вже було сказано, цифрове зображення в комп'ютері представляють у вигляді матриці значень інтенсивностей його пікселів. Таким чином, нас має цікавити хааровское двовимірне вейвлет-перетворення. Для його здійснення необхідно просто виконати одномірне його перетворення для кожного рядка і кожного стовпця матриці інтенсивностей пікселів зображення. Значення, близькі до нуля, можна відкинути без істотного збитку для декодованого зображення. Такий процес відомий як квантування. І саме на цьому етапі втрачається частина інформації. До речі, число обнуляемих коефіцієнтів можливо змінювати, тим самим регулюючи ступінь стиснення. Всі описані дії призводять до того, що виходить матриця, яка містить велику кількість 0. Її слід записати порядково в текстовий файл і стиснути будь-яким архіватором.

Декодування

Зворотне перетворення зображення проводиться за наступним алгоритмом:

архів розпаковується;

застосовується зворотне перетворення Хаара;

розкодована матриця перетворюється в зображення.

Переваги в порівнянні з JPEG

При розгляді алгоритму Joint Photographic Experts Group було сказано, що він заснований на ДКП. Таке перетворення здійснюється по блоках (8 х 8 пікселів). В результаті, якщо стиск сильне, то на відновленому зображенні стає помітною блокова структура. При стисненні з використанням вейвлетів така проблема відсутня. Однак можуть з'явитися спотворення іншого типу, які мають вигляд брижів близько різких кордонів. Вважається, що подібні артефакти в середньому менш помітні, ніж «квадратики», які створюються при застосуванні алгоритму JPEG. Тепер ви знаєте, що таке вейвлети, якими вони бувають і яке практичне застосування для них знайшлося в сфері обробки і стиснення цифрових зображень.