3.3 Программа Fract2.

Програма Fract3 является иллюстрацией к теореме о сжимающих отображениях в пространстве Хаусдорфа.

Изначально заданы два изображения и IFS папоротника Барнсли. Нажатие на кнопку "Вычислить" в разделе "Расстояние" запускает процедуру вычисления расстояния Хаусдорфа между данными изображениями. Результат отображается в поле справа от надписи "Расстояние"; в полях расположенных ниже выводятся координаты точек, расстояние между которыми и дает расстояние Хаусдорфа. При этом, если в среднем поле стоит стока "-->", значит результат получен при вычислении расстояния от левого до правого изображения, если - строка "<--", то - от правого до левого.

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

Нажатие на кнопку "Преобразовать" запускает вероятностный алгоритм с параметром, указанным в поле "Кол-во итераций" для обоих изображений сразу. Результаты отображаются на экране.

В программе предусмотрена возможность загрузки IFS пользователя(см. руководство к программе Fract0) и восстановления исходной, а также - возможность загрузки изображений. При этом загрузка производится не из файлов – картинок (bmp, jpg и др.), а из текстового файла в каждой строке которого через запятую содержатся координаты точек изображения(т. е. - точек цвета, отличного от черного).

Например:

100 100

20 70

135 40

При зарузке данного файла получим черное изображение с тремя белыми точками - (100, 100), (20,70) и (135, 40).

Следует также помнить, что размер изображений - 300x300 пикселей.

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

т. д.

После завершения этого процесса появляется новое окно. Для построения графика следует выбрать пункт меню "График" - "Построить". Полученный график можно экспортировать в файлы типа bmp, wmf или emf.

3.3.1 Вычисление расстояния Хаусдорфа

Расстояние Хаусдорфа является одним из ключевых понятий фрактального сжатия изображений. Однако, его вычисление – задача нетривиальная, т. к. вычисление его по определению требует значительных временных затрат даже на современных компьютерах. Так, например, чтобы вычислить расстояние Хаусдорфа по определению между двумя изображениями размера 300х300 пикселей, компьютеру на базе процессора Pentium4 потребовалось более одного часа времени.

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

В программе вычисление метрики Хаусдорфа реализовано на базе классического алгоритма поиска в ширину, известного также как «волна». Его идея заключается в следующем: процесс начинается с некоторой исходной точки; все точки, соседние с исходной помечаются как пройденные; на следующих шагах для текущей точки рассматриваем все соседние и помечаем их, если они еще не пройдены.

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

Схема работы алгоритма поиска в ширину.