Geum.ru

Поддубный А. П., Юрков Н. К., Якимов А. Н. Фрактальный подход к сжатию информации. // Проблемы информатики в образовании, управлении, экономике и технике: Сб

Вид материалаДокументы

Содержание


A.P. Poddubny, N.K. Yurkov, A.N. Yakimov Fractal approach to data reduction.
Подобный материал:
Поддубный А.П., Юрков Н.К., Якимов А.Н. Фрактальный подход к сжатию информации. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей XI Междунар. научно-техн. конф. – Пенза: ПДЗ, 2011. – С. 103 106.

ФРАКТАЛЬНЫЙ ПОДХОД К СЖАТИЮ ИНФОРМАЦИИ

А.П. Поддубный, Н.К. Юрков, А.Н. Якимов

Пензенский государственный университет,

г. Пенза, Россия, kipra@pnzgu.ru

Предлагается метод фрактального кодирования информации, позволяющий осуществить эффективное сжатие информации больших объемов.


A.P. Poddubny, N.K. Yurkov, A.N. Yakimov Fractal approach to data reduction. A method of fractal coding information, allowing to implement effective data compression of large volumes is suggested.


Понятия «фрактал» и «фрактальная геометрия», появившиеся в конце 70-х гг., с середины 80-х гг. прошлого века прочно вошли в обиход математиков и программистов.

Раньше математики концентрировали внимание на множествах и функциях, для которых могут быть применены методы классических вычислений. Функции, которые не являются достаточно гладкими или регулярными, часто игнорировались. Однако в последние годы отношение к негладким функциям (или нерегулярным множествам) изменилось, так как они обеспечивают значительно лучшее представление многих природных явлений по сравнению с тем, которые дают объекты классической геометрии. Изучением таких функций занимается фрактальная геометрия.

Фрактальное кодирование изображений основано на гипотезе, согласно которой в любом изображении можно обнаружить локальное самоподобие различных его частей. Впервые возможность применения теории систем итерируемых функций (СИФ) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном.

Существующие алгоритмы фрактального кодирования, как правило, придерживаются следующей схемы. Кодируемое изображение разбивается на множество неперекрывающихся блоков (ранговых областей), для каждого из которых (в пределах этого же изображения) ищется блок большего размера (домен), пикселы которого путём некоторого преобразования переводились бы в пикселы ранговой области. При этом для поиска оптимального соответствия ранговых областей и доменов необходим полный перебор вариантов, что влечёт за собой значительные вычислительные затраты. При этом кодом изображения будут являться местоположение и размеры ранговых областей, а также коэффициенты преобразований, описывающих самоподобие внутри изображения. Количество бит, необходимых для описания кода, будет существенно меньше количества бит, необходимых для описания исходного изображения. Коэффициентом сжатия называется отношение битового представления изображения к битовому представлению кода. В известных фрактальных методах сжатия изображений значение этого коэффициента может достигать 100 при приемлемом качестве восстановления.

Для восстановления закодированного таким образом изображения используется принцип сжатых отображений, который гласит, что сжимающее отображение, действующее в полном метрическом пространстве, имеет единственную неподвижную точку. В нашем случае мы используем полное метрическое пространство полутоновых изображений с определённой на нём метрикой. Отображение, действующее на полном метрическом пространстве изображений, формируется из преобразований, переводящих домены в ранговые области. Неподвижной точкой такого отображения (при условии, что оно является сжимающим) будет восстановленное полутоновое изображение.

СИФ-фракталы имеют одно вполне реальное и полезное применение – с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров.

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

На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии [1,2]. Метод «Систем интерируемых функций» появился в середине 80-х гг. XX века как наиболее простое средство получения фрактальных структур. СИФ представляет собой систему функций из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое. Наиболее простая СИФ состоит из аффинных преобразований плоскости.

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

В предлагаемом архиваторе метод СИФ применяется не для подбора последовательностей подобных исходному значению, а для создания последовательности псевдослучайных значений. Существует несколько преимуществ использования СИФ и фрактальной алгебры в качестве метода создания псевдослучайной последовательности:

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

СИФ позволяет создать разные последовательности, меняя несколько коэффициентов; в самой итерируемой функции вычисление очередного значения основано на результате функции, на предыдущем шаге вычисления. Это позволяет в течение многих итераций получать разные значения функции. Использование системы итерируемых функций, в которой значение (результат) вычисления зависит от результата решения всей системы, позволяет получить необходимый набор псевдослучайных чисел. Если же поменять значения нескольких коэффициентов при системе, то получатся разные наборы (последовательности) псевдослучайных чисел.

СИФ позволяет восстановить последовательность при известных коэффициентах и формуле расчёта; так как последовательность создана с использованием итераций начиная с первого шага, то её (последовательность) можно восстановить, зная начальные координаты функции, значения коэффициентов и число итераций. Восстановленная последовательность (ряд) по заданным параметрам используется в восстановлении сжатых данных.

Данный способ отвечает всем необходимым условиям создания псевдослучайной последовательности для компрессии и декомпрессии данных, предлагаемым в данном подходе. Он позволяет генерировать псевдослучайный ряд, имея минимальный набор входных параметров, а также восстановить его при сохранении набора параметров.

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

1. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. – М.: Триумф, 2003. – 320 с.

2. Шелухин О.И., Осин А.В., Смольский С.М. Самоподобие и фракталы. Телекоммуникационные приложения. – М.: Физматлит, 2008. – 368 с.