5.2. Вычисление размерности

Компьютерные алгоритмы вычисления размерности Минковского d обычно опираются на соотношение (5.3). Для удобства приведем его еще раз:

где с — константа.

Как видно, график зависимости от — прямая с угловым коэффициентом —d. Напомним, что через обозначено минимальное число клеток со стороной , необходимых для покрытия фрактала. Для определения неизвестных параметров (хотя значение с обычно не представляет интереса) необходимо оценить для нескольких значений . Следствие 5.1.2 облегчает нашу задачу, позволяя использовать квадратные клетки вместо кругов при оценке

Если использовать клетки только двух размеров, , то неизвестные можно определить из системы уравнений:

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

Приближение по методу наименьших квадратов.

Рассмотрим задачу об интерполяции точек

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

Положим Прямая

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

достигает минимума.

Значения этих параметров найдутся решением системы уравнений:

В матричной записи (см. упр. 3 в конце этого параграфа):

Алгоритм 5.2.1. (МНК-ПРЯМАЯ)

Назначение: вычисляет МНК-прямую .

Вход:

Выход:

Шаги:

Клеточный метод.

Простейший способ определения размерности Минковского фрактала А состоит в следующем. Разобьем область, содержащую А, на квадратные клетки (двумерный случай) нескольких размеров. Затем подсчитаем число клеток, необходимых для покрытия А в каждом случае, и подставим полученные значения в соотношение (5.3). Очевидно, если фрактал А является подмножеством прямой, то вместо квадратов надо использовать отрезки.

Если же А — подмножество трехмерного пространства, то квадраты заменяются кубами.

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

Алгоритм 5.2.2. (РАЗМЕРНОСТЬ МИНКОВСКОГО)

Назначение: вычисляет размерность плоского фрактала.

Вход:

Выход:

d (оценка размерности Минковского)

Инициализация:

Шаги:

найти MHK-прямую по точкам , модуль углового коэффициента MHK-прямой

Рис. 5.2. Фрактал, размерность которого находится численно

Пример. Обозначим через S фрактал, изображенный на рис. 5.2. Это самоподобный фрактал теоретическая размерность которого составляет . Как рисунок, так и данные для моделирования были получены с помощью алгоритма детерминированной СИФ (глава 4).

В результат работы алгоритма 5.2.2 были получены следующие результаты:

Рис. 5.3. Зависимость log N(L) от log L

Зависимость log N(L) от log L приведена на рис. 5.3. Угловой коэффициент МНК-прямой в этом случае равен —1,3460, а значит численное значение размерности Минковского d = 1,3460.

Точечный метод.

Точечный метод представляет собой альтернативный подход к вычислению размерности фрактала [45]. Рассмотрим сетку, покрывающую весь фрактал. Ее узлы будем называть ячейками. Каждую ячейку, имеющую с фракталом непустое пересечение, будем считать за одну точку. Ясно, что именно эта схема реализуется при графическом выводе фрактала на экран как массива пикселов. В этом параграфе «подсчет числа точек в клетке» означает подсчет числа ячеек (или пикселов) в клетке. Это не то же самое, что считать действительное число геометрических точек в клетке — ведь их бесконечно много. Точечный метод принципиально отличается от клеточного; в первом подсчитывается число точек в клетке, а во втором — число клеток, необходимых для покрытия фрактала.

Для упрощения вычислений будем считать клетки квадратными. Размер L клетки означает число ячеек по каждой стороне. Ограничимся нечетными значениями L; в этом случае центральная ячейка клетки будет равноудалена от всех сторон. Сначала вычислим вероятности того, что клетка размера L содержит точек (ячеек) фрактала. Для этого вокруг каждой точки фрактала, считая ее центральной, построим клетку размера L и подсчитаем число точек, попавших в нее. Предположим, что фрактал содержит М точек. Тогда равно числу клеток, содержащих точек, , деленному на М. Заметим, что сумма всех вероятностей равна единице:

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

где К — возможное число точек в клетке. Следовательно,

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

Алгоритм 5.2.3. (РАЗМЕРНОСТЬ МИНКОВСКОГО II)

Назначение: вычисляет d через

Вход

Выход:

d (оценка размерности Минковского)

Инициализация:

Шаги:

Замечание: для удобства вместо вычисляется где а — несущественная константа.

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

Рис. 5.4. Зависимость от

В первом случае обычно а во втором —

Точность вычислений может быть проиллюстрирована следующим примером. Численно оценивалась фрактальная размерность ковра Серпинского, теоретическое значение которой нам известно из построения: Использовалось изображение фрактала размером 300 х 300 пикселов, причем вокруг него был оставлен белый фон — граница в 20 пикселов шириной, так что полное изображение занимало 340 х 340 пикселов. Размер клетки L пробегал все нечетные значения от 3 до 21. На рис. 5.4 приведен график зависимости от logZ.

На первый взгляд, график почти не отклоняется от прямой. Однако если провести МНК-прямую (алгоритм 5.2.1) для всех наборов из четырех последовательных точек, то получим следующие значения d (угловые коэффициенты, взятые с обратным знаком):

Таким образом, оценка фрактальной размерности имеет лишь один верный десятичный разряд (d = 1,6).