Фрактальное сжатие изображений - Студенческий научный форум

XII Международная студенческая научная конференция Студенческий научный форум - 2020

Фрактальное сжатие изображений

Метелкин В.О. 1
1ФГБОУ ВО "Брянский государственный университет имени академика И.Г. Петровского"
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Фрактальная геометрия возникла в XIX веке. Кантор с помощью простой повторяющейся процедуры превратил линию в набор несвязанных точек, при этом была получена так называемая Пыль Кантора.

Рисунок 1. Пыль Кантора

Он брал линию и удалял из нее центральную треть, после этого повторял то же самое с оставшимися отрезками. Накопление данных о таких странных объектах шло вплоть до XX века.

Так было, пока за них не взялся Бенуа Р. Мандельброт (Benoit Mandelbrot), математик из Исследовательского центра им. Томаса Уотстона при IBM. Он является отцом современной фрактальной геометрии и именно он предложил термин «фрактал» для описания объектов, структура которых повторяется при переходе к более мелким масштабам. Работая в IBM, Бенуа Р. Мандельброт изучал шумы в электронных схемах, которые невозможно было описать с помощью статистики. Со временем, сопоставив некоторые факты, он пришел к открытию фрактальной геометрии - нового направления в математике.

После открытия Бенуа Мандельбротом теории фракталов стало понятно, что данная теория способна удивительно точно описывать многие объекты и явления окружающего нас мира. Не удивительно, что теория фракталов и фрактальные алгоритмы в частности, нашли практическое применение в очень многих областях науки и технике.

Первым и очевидным применением фрактальных алгоритмов стало так называемое фрактальное сжатие изображений. Фрактальное сжатие изображений — алгоритм сжатия изображений с потерями, основанный на применении систем итерируемых функций к изображениям. (Системы итерируемых функций или просто СИФ - представляет собой систему функций из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое.) Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры — до 1000 раз (при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе.

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли (англ. Michael Barnsley и Аланом Слоуном (англ. Alan Sloan). Они запатентовали свою идею в 1990 и 1991 годах.

Сжимающие отображения обладают важным свойством. Если взять любую точку и начать итеративно применять к ней одно и то же сжимающее отображение: f(f(f...f(x))), то результатом будет всегда одна и та же точка. Чем больше раз применим, тем точнее найдем эту точку. Называется она неподвижной точкой и для каждого сжимающего отображения она существует, причем только одна.

Например, вот так при помощи СИФ из трех функций строится треугольник Серпинского:

Рис. 2 Построение треугольника Серпинского

Исходный треугольник три раза множится, уменьшается и переносится. И так далее. Если так продолжать до бесконечности, получим известный фрактал площадью 0 и размерностью 1,585.

Вот здесь, собственно, начинаются проблемы. Произвольные изображения, в отличие от фракталов, не самоподобны, так что так просто эта задача не решается. Как это сделать придумал в 1992 году Арнольд Жакин, в то время — аспирант Майкла Барнсли, который считается отцом фрактального сжатия.

Если брать сравнение форматов сжатия JPEG и фрактальный метод, то при низких степенях сжатия качество рисунков последнего уступало качеству формата JPEG, но при высоких картинки получались более качественными. В любом случае этот формат не прижился, но работы по его усовершенствованию ведутся до сих пор. Ведь этот формат не зависит от разрешения изображения. Так как изображение закодировано с помощью формул, то его можно увеличить до любых размеров и при этом будут появляться новые детали, а не просто увеличится размер пикселей.

Библиографический список

Саква Д.Ю. Фракталы вокруг нас [Электронный ресурс] — Режим доступа. — URL: http://www.codenet.ru/progr/fract/Fractals-Around/ (дата обращения 10.01.2020).

Fisher Y. Fractal Image Compression — Theory and Applica-tion. — N. Y.: Springer-Verlag, 1994. 341 p.

Шаpабайко М. П., Осокин А. Н. Быстpоäействуþщий аë-ãоpитì фpактаëüноãо сжатия изобpажений // Известия Тоìско-ãо поëитехни÷ескоãо унивеpситета. 2011. Т. 318, No 5. С. 52—57.

Просмотров работы: 9