3.4. Аппроксимация функций

В п. 3.3 рассматривалось отображение

Рис. 1. Множество эпицентров землетрясений, Калифорния, 1932—1994.

пространства компактных подмножеств из X, задаваемое набором сжимающих отображений Это одно из, несомнённо, богатого многообразия сжимающих отображений Более общее отображение в сравнении с названным задается той же формулой (3.14) с набором отображений

где некоторый набор областей (домен) из Такой набор именуется как LIFS или PIFS - Local (Partitioned) Iterated Funtions System. IFS есть частный случай при Отображения, задаваемые посредством целесообразно применять для обработки множеств, близких по структуре к самоподобным множествам (имеющим большое количество малых частей, подобных всему множеству). Набор может быть полезен при обработке такого множества в котором явно выделяется набор составных частей каждая из которых имеет много себе подобных подмножеств из (не обязательно содержащихся в малых размеров. Сказанное в равной степени относится и к задаче компактного хранения функций. Продемонстрируем суть метода,

опирающегося на в простейшем случае (см. [98]).

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

Предположим, что разбит на регионы (например, прямоугольники)

и выделен набор областей так, что для любого указаны номер и взаимно-однозначное аффинное отображение

Пусть оно задается формулой

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

где заданные коэффициенты, а через обозначается сужение на множество Итак, отображение строится на основе двух преобразований:

— преобразование по горизонтали (обозначим его через для определения при вычисляется значение функции в точке

— преобразование по вертикали, действующее на функцию

Это кусочно-аффинные преобразования, они задаются набором коэффициентов

Коэффициенты в (3.16) могут выбираться как ешение следующей задачи о наилучшем приближении (см. гл. I, § 3,4)

Для выяснения условия сжимаемости оператора выпишем оценку при

где якобиан преобразований Следовательно, коэффициент сжатия отображения удовлетворяет неравенству

и условие сжимаемости отображения имеет вид

В рассматриваемом случае задается посредством коэффициентов (3.16) и величина (см. (2.8)) оценивается следующим образом:

Если пространство ограниченных на функций с нормой

S - определенное в (3.16) отображение, то для любых будет

Следовательно, коэффициент сжатия удовлетворяет неравенству

и, значит,

Заметим, что в случае функции одной переменной отображение (3.16) можно выразить следующим образом:

Возможны обобщения метода по следующим направлениям:

— область определения функции содержится в или в произвольном метрическом пространстве;

— разбиение области на регионы и набор домен выбирается с учетом особенностей функции поэтому не обязательно являются прямоугольниками;

— отображения являются полиномиальными;

— задан набор функций по которому отображение определяется так:

— для каждого задан набор номеров из и коэффициентов и отображение определяется в виде

Отметим, что если функции из (3.24) удовлетворяют условию Липшица

то, как легко видеть, выполняются неравенства, получающиеся из (3.19)-(3.23) заменой величины на

Подведем итог. Для реализации предлагаемого метода надо выполнить следующее:

1) разбить область на конечное число регионов

2) выбрать набор домен

3) для каждого региона подобрать домен в случае отображения вида (3.25) подобрать набор домен

4) определить отображения

5) построить отображение вида (3.24) или (3.25). Этапы 1) - 4) осуществляются так, чтобы

а) отображение было сжимающим в метрике пространства

б) неподвижная точка оператора была по возможности ближе к обрабатываемой функции

Условие сжимаемости проверяется посредством неравенств (3.20), (3.22), а в случае операторов (3.25) для функций, удовлетворяющих условию Липшица, — посредством неравенства

Требование б) напрямую трудно выполнимо. Более доступна задача минимизации по коэффициентам (3.17) отношения (3.21), а в случае отображения (3.24) — минимизация величины

с последующим использованием теоремы 2 из п. 2.3. На практике же, как отмечалось выше (см. (3.18)), с целью удовлетворения требования б) минимизируют величину Так, в случае отображения

вида (3.16) для каждой пары находят

затем отыскивают

и полагают в качестве тот номер на котором дости гается минимум (3.27). Как видим, минимизация величины связана с большими вычислительными затратами, для каждого требуется I раз решить задачу (3.26). Известно (см. [47]) несколько способов уменьшения времени поиска.

Далее излагаются способы, предложенные Я.В. Малыгиным [47].

Ряд способов основан на предварительной классификации "фрагментов" исходной функции, что позволяет для каждого региона проводить поиск, т.е. решать задачи (3.26), (3.27) только среди домен, близких в смысле этой классификации к Удачно подобранный признак классификации позволяет значительно сократить объем требуемых вычислений, лишь незначительно увеличивая погрешность (3.27). Интуитивно понятно стремление проводить поиск для некоторого скажем, с "гористым" (сильно изломанным) графиком среди таких домен, у которых также является "гористым". При этом в качестве "гористости" графика функции можно принять хаусдорфову размерность (см. § 1): чем больше это число, тем "изломанность" выше.

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

где среднее значение функции на что обеспечивает выполнение равенства

В качестве признака классификации фрагментов выберем такую "нормализованную" размерность которая также не будет зависеть от параметров функции

Таким образом, поиск пар регион-домен будет состоять из двух этапов:

1) нахождение и запоминание "нормализованных" размерностей для всех рассматриваемых регионов и домен

2) для каждого региона поиск производится лишь среди тех домен, размерности которых близки к размерности этого региона.

Замечание. При реализации данного алгоритма на ЭВМ необходимо имеь в виду, что при представлении функции в виде двумерного массива (матрицы) отсчетов мы не можем вычислить хаусдорфову размерность. В этом случае имеет смысл воспользоваться одним из следующих способов (см., напр., [116]):

а) вместо предела при выбрать просто достаточно малое (скажем, наименьшее возможное при данном представлении функции в цифровом устройстве) и вычислить

б) задать два значения и положить

В обоих вариантах значение будет отличаться от истинного но вполне подходит в качестве меры "гористости" графиков функций.

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

Пусть квадратные области из со сторонами, параллельными координатным осям; линейный размер регионов в заранее фиксированное число раз (например в два) меньше линейного размера домен Множество домен порождается одним доменом параллельно сдвигаемым на некоторый вектор

Определим преобразование так, Погрешность между фрагментами функции определяется в виде:

при будем иметь

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

где количества рассматриваемых домен и регионов. Известно, что выражения вида

где отрезок из можно вычислять, используя преобразование Фурье, которое в одномерном случае выглядит следующим образом:

Свертку можно вычислять, используя соотношение:

При этом требуется, чтобы функции имели период, равный длине отрезка

Вычисление выражений (3.31) и (3.32) с помощью дискретного преобразования Фурье

на ЭВМ вполне возможно, но оказывается неэффективным по следующим причинам:

— вычисления приходится проводить в области комплексных значений, тогда как исходное оцифрованное изображение задано, скажем, массивом целых чисел;

— использование величин типа и приводит к ошибкам округления и конечный результат получается неточным.

Имеет смысл заменить преобразование Фурье неким другим преобразованием, которое обладает всеми необходимыми свойствами для подобного вычисления сверток и корреляций и оперирует с целыми числами. Таким является, например, преобразование Мерсенна [51], особенностью которого является работа в модулярной арифметике. Одномерное р-точечное преобразование Мерсенна записывается в виде:

Где простое число. Числа вида простое) называются числами Мерсенна. Сравнивая дискретное преобразование Фурье и преобразование Мерсенна, заметим, что т.е. в обоих преобразованиях разложение происходит по базису, составленному из корней степени из 1 соответственно.

Обратное преобразование Мерсенна записывается в виде:

где обратный элемент к т.е.

Нетрудно показать, что совпадают с точностью до перестановки элементов в наборах, а величина где целая часть выражения. Циклическая свертка [51] представляется следующим образом

а корреляция

при условии, что значения получаемых отсчетов не превосходят величины

Пример 3 (Я.В. Малыгин). Поиск параметров фрактального сжатия проводился на стандартном монохромном изображении размером 256 256 графических элементов (пикселей) с глубиной цвета 6 бит на точку (64 оттенка серого). Вычисления осуществлялись на Pentium 150 без программной оптимизации. Результаты расчетов приведены в таблице 1 и на рис. 2. Качество аппроксимации определяется двумя способами: а) расстоянием в 12 между двумя функциями, определяющими изображения, и б) величиной пикового отношения сигнал-шум (PSNR, - peak signal-to-noise ratio) в децибелах. Для двух изображений с целочисленными значениями отсчетов расстояние в 12 определяется в виде:

Если предположить, что является аппроксимацией исходного изображения

Размер регионов выбран равным 88 отсчетов, а размер домен 16 16. Для хранения параметров фрактального представления изображения необходимо 27 бит для каждого региона, т.е. для представления всего изображения используется 0.422 бит на точку (сжатие в 14 раз). Общее количество рассматриваемых пар регион-домен примерно равно Величины обозначают количества сравниваемых пар регион-домен в методе предварительной классификации.

Таблица 1 (см. скан)

(кликните для просмотра скана)