Алгоритм фрактального стиснення

Трикутник Серпінського — зображення, що задається трьома афінними перетвореннями

Фрактальне стиснення зображень — це алгоритм стиснення зображень з втратами, заснований на застосуванні систем ітерованих (повторних) функцій (IFS, які, як правило, є афінними перетвореннями) до зображень. Даний алгоритм відомий тим, що в деяких випадках дозволяє отримати дуже високі коефіцієнти стиснення (найкращі приклади — до 1000 разів при прийнятній візуальній якості) для реальних фотографій природних об'єктів, що неможливо для інших алгоритмів стиснення зображень. Через складну ситуацію з патентуванням широкого розповсюдження алгоритм не отримав.

Опис

Основа методу фрактального кодування — це виявлення самоподібних ділянок у зображенні. Вперше можливість застосування теорії систем ітерованих функцій (англ. Iterated Function System, IFS) до проблеми стиснення зображень була досліджена Майклом Барнслі (англ. Michael Barnsley) та Аланом Слоуном (англ. Alan Sloan). Вони запатентували свою ідею в 1990 та 1991 роках (U.S. Patent 5,065,447). А. Жакен (фр. Arnaud Jacquin) представив метод фрактального кодування, в якому використовуються системи доменних і рангових блоків зображення (англ. domain and range subimage blocks), блоків квадратної форми, що покривають усе зображення. Цей підхід став основою для більшості методів фрактального кодування. Він був удосконалений Ювалом Фішером (англ. Yuval Fisher) і багатьма іншими дослідниками.

У відповідності з даним методом зображення розбивається на безліч рангових підзображень, що не перекриваються (англ. range subimages), і визначається множина доменних підзображень, які перекриваються (англ. domain subimages). Для кожного рангового блоку алгоритм кодування знаходить найбільш підхожий доменний блок і афінне перетворення, яке переводить цей доменний блок в даний ранговий блок. Структура зображення відображається в систему рангових блоків, доменних блоків і перетворень.

Ідея полягає в наступному: припустимо, що вихідне зображення є нерухомою точкою якогось стискаючого відображення. Тоді можна замість самого зображення запам'ятати будь-яким чином це відображення, а для відновлення достатньо багаторазово застосувати це відображення до будь-якого стартового зображення.

За теоремою Банаха, такі ітерації завжди призводять до нерухомої точки, тобто до вихідного зображення. На практиці вся складність полягає у відшуканні по зображенню найбільш підхожого стискаючого відображення і в компактному його зберіганні. Як правило, алгоритми пошуку відображення (тобто алгоритми стиснення) в значній мірі перебірні і вимагають великих обчислювальних витрат. У той же час, алгоритми відновлення досить ефективні і швидкі.

Метод, запропонований Барнслі, можна описати таким чином. Зображення кодується кількома простими перетвореннями (в нашому випадку афінними), тобто визначається коефіцієнтами цих перетворень (в нашому випадку A, B, C, D, E, F).

Наприклад, зображення кривої Коха можна закодувати чотирма афінними перетвореннями, однозначно визначивши його за допомогою 24-х коефіцієнтів.

Далі, поставивши чорну крапку в будь-якій точці картинки ми будемо застосовувати наші перетворення у випадковому порядку деяке (досить велике) число разів (цей метод ще називають фрактальним пінг-понгом).

У результаті точка обов'язково перейде кудись всередину чорної області на вихідному зображенні. Проробивши таку операцію багато разів ми заповнимо весь чорний простір, тим самим відновивши картинку.

Складність методу

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

На даний момент відома досить велика кількість алгоритмів оптимізації перебору, що виникає при фрактальному стисненні, оскільки більшість статей, які досліджували алгоритм, були присвячені цій проблемі, і під час активних досліджень (1992—1996 роки) виходило до 300 статей на рік. Найбільш ефективними виявилися два напрямки досліджень: метод виділення особливостей (feature extraction) і метод класифікації доменів (classification of domains).

Патенти

Майклом Барнслі та іншими було отримано декілька патентів на фрактальне стиснення в США та інших країнах. Наприклад, 4,941,193, 5,065,447, 5,384,867, 5,416,856 і 5,430,812. Ці патенти покривають широкий спектр можливих змін фрактального стиснення і серйозно стримують його розвиток.

Дані патенти не обмежують досліджень у цій області, тобто можна придумувати свої алгоритми на основі запатентованих і публікувати їх. Також можна продавати алгоритми у країни, на які не поширюються отримані патенти. Крім того, термін дії більшості патентів — 17 років з моменту прийняття, і він закінчується для більшості патентів найближчим часом, відповідно, використання методів, що покриваються цими патентами, стане гарантовано вільним.