2
vlad_lightЦитата:
Неужели в мире так много вещей, которые состоят из деталей себе подобных?
Настоящих фрактальных объектов очень мало. Поэтому подобрать (построить) нетривиальный сжимающий оператор, оставляющий приближаемый объект неподвижным или очень похожим на оригинальную версию, вообще говоря, невозможно. По этой причине объект дробят на блоки двумя способами -- на мелкие непересекающиеся и на крупные частично перекрывающиеся, а потом пытаются найти похожие блоки. Ищутся соответствия "большой блок / маленький блок". Здесь существенно, что один из сопоставляемых блоков больше, ведь отображение, делающие большой блок похожим на маленький блок в таком случае будет сжимающим, а это нужно для существования неподвижной точки.
Раз уж вы упомянули сжатие изображений, то попробую объяснит на примере фрактальной обработки картинки. Допустим у вас есть игра-мозаика. В ней есть коробка с фрагментами (словарь) и эталонная картинка, которую вы пытаетесь собрать из доступных вам кусочков. При фрактальном кодировании фрагменты не даются вам заранее, а извлекаются из самого эталонного изображения, деформируются и кладутся на новое место. Лишь-бы в результате получилась та-же картинка.
И вот здесь-то и заключена магия -- раз словарь формируется динамически из эталонного объекта, то во фрактальном описании должны быть лишь команды вроде "взять большой кусочек с такими координатами, отразить слева-направо, скукожить, сделать более зеленым и положить на новые координаты" (набор возможных операций обычно ограничен всего несколькими самыми ходовыми функциями). То есть сами данные хранить не надо, только команды (они занимают меньше места чем пиксели изображения и на этом основано сжатие). Если все эти инструкции выполнять над эталонной картинкой, то получится она же самая (она является неподвижной точкой).
Такой набор инструкции сам по себе не единственен, но его можно немного преобразовать и получить что-то типа сигнатуры картинки. Это может применяться при распознавании образов. То есть при поиске картинки в базе данных просто путем сравнения сигнатур фрактальных кодов.
Однако, вернемся к основной теме. Нам известно, что конструктивные теоремы о неподвижной точке для сжимающих отображений утверждают не только существование неподвижной точки, но и говорят о её уникальности и даже предлагают рецепт её нахождения путем многократного применения инструкций (итерирования фрактального оператора) начиная с произвольной картинки. Т.е. если мы построили фрактальное описание пингвина, то мы получим картинку пингвина, даже если начнем итерации с картинки хомяка. Причем, если мы начнем с картинки похожей на пингвина, то уже после первой итерации получим изображение очень близкое к оригиналу, а вот одна итерация на хомяке даст мусор; это опять же можно использовать для распознавания образов.
Опять отвлекся. Итак, фрактальный декомпрессор восстанавливает оригинальный объект, но он не знает размеров исходного изображения и поэтому его можно обмануть, сообщив завышенные размеры. Теорема о неподвижной точке все-равно сработает и фрактальный декомпрессор все-равно выдаст исходную картинку (затратив больше итераций, то есть проработав больше времени). При этом ему придется дорисовать недостающие детали, это используется при фрактальном фотоулучшении. Именно на этом основана фрактальная интерполяция/аппроксимация.
Вы видимо легко сможете подобрать примеры изображений, в которых найдется маленький кусоче, который не похож ни на один большой кусок той-же картинки. Возьмем классический пример со знаком бесконечности (
): в центральной части линии пересекаются и этот крестик не похож ни на один другой блок изображения знака бесконечность. Это не создает проблем в задачах распознавания, но неприемлемо в задачах интерполяции и сжатия. Для решения такой проблемы применяют иерархическое подразбиение нехороших блоков. В примере со знаком бесконечность мы можем поделить крестик на четыре части, каждая из которых легко сопоставляется с другими участками всей картинки.
Цитата:
зачем, с точки зрения программирования, жертвовать скоростью ради объёма
Подумайте о сжатии видео. :)
Цитата:
Также я слышал, что фракталы используются для прогнозирования результатов
Подходы к фрактальной экстраполяции могут быть различными. Но с высоты птичьего полета вы можете представить себе абстрактную схему предсказания пользуясь теоремкой об эквивалентности задач сжатия, предсказания и классификации. То есть вы можете написать архиватор на основе алгоритма фрактального сжатия, а дальше читайте
эту тему про ленивых генетиков. :)
Цитата:
Приведите, пожалуйста, пример аппроксимации квадрата фракталами.
Извините, лень. Принцип я объяснил. К настоящим фракталам эта задача отношения почти не имеет.
Цитата:
Квадратичный перебор, т.е. такую задачу имеет смысл решать только с помощью компьютера?
Даже для компьютера это сложно.
Цитата:
Я не понимаю, как выбирать функцию, руководствуясь стремлением к похожести наших данных?
Пробуете все функции (их набор задается, как я уже говорил, заранее) по-очереди и смотрите какая из них будет давать лучший результат. В частных случаях эффективней "вычислить" функцию, решив систему уравнений, это похоже на вашу "первую часть".
P.S.: Есть ещё один, альтернативный способ фрактальной аппроксимации. Берется какой-нибудь известный фрактал (e.g., множество Мандельброта), режется на куски, и уже из этих кусков собирается эталонный объект.
-- Сб мар 12, 2011 01:50:02 --Ссылки могу такие дать (на тему фрактальной интерполяции в 1D):
W.O.Cochran, J.C.Hart, P.J.Flynn, On Approximating Rough Curves with Fractal Functions;
E.Guerin, E.Tosan, A.Baskurt, A Fractal Approximation of Curves.