НГУ

Форумы НГУ
Текущее время: Пн окт 22, 2018 10:50 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: по фрагменту мандельброта
СообщениеДобавлено: Ср мар 30, 2005 1:48 am 
Можно ли по фрагменту изображения множества мандельброта определить его координаты? А так же степень множества?


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср мар 30, 2005 8:18 am 
Не в сети
Опытный автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 471
Вопрос о нахождении координат фрагмента по картинке, как мне кажется, разбивается на два:

Вопрос 1. Насколько уникальны или похожи различные фрагменты мн-ва мандельброта с размером (фрагментов) больше некоторого фиксированного числа r>0? Похожесть фрагментов можно измерять, например, суммой модулей попиксельной разности фрагментов, либо расстоянием Хаусдорфа между двумя множествами.

Вопрос 2. Есть ли способ быстро отыскать координаты максимально похожего фрагмента (размера больше фиксированного r>0), иначе как используя полный перебор? Может быть имеет смысл использовать некоторое самоподобие мн-ва Мандельброта. Для множеств Жулиа, если известен параметр C, можно попробовать поприменять несколько раз к имеющемуся фрагменту преобразование f(z)=z^2+C или обратное к нему f^(-1)(z)=sqrt(z-C).

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


Что касается степени множества. Наверно имеется в виду "по фрагменту изображения определить степень n полинома f(c)=z^n+c, порождающего множество Мандельброта". Если виден участок подобный всему множеству Мандельброта, то степень равна количеству "щупальцеобразных отростков" и количеству осей симметрии этого участка. Лучше самостоятельно поуглубляться в множества Мандельброта при разных n, поизучать как они в глубине выглядят.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт апр 01, 2005 12:35 am 
Aleksey писал(а):
, иначе как используя полный перебор? ...


а даже если и перебор, то как его организовать-то?!! В смысле, как находить хотя бы кандидатов?


Aleksey писал(а):
.... Наверно имеется в виду "по фрагменту изображения определить степень n полинома f(c)=z^n+c, порождающего множество Мандельброта"....


Именно так, выражаясь нежитейским языком.
Уже.
К сожалению, количество отростков в глубине может не совпадать с N.


Вернуться к началу
  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 06, 2005 6:35 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 471
Цитата:
а даже если и перебор, то как его организовать-то?!! В смысле, как находить хотя бы кандидатов?

Например так: строим множество Мандельброта в большом разрешении, скажем, 2^20 по горизонтали. Затем ищем в нём заданный фрагмент с различными масштабами. Памяти конечно съест... ;)

Допустим со всеми возможными оптимизациями фрагмент множества Мандельброта в разрешении 1024x768 строится в среднем 1 сек. Тогда в разрешении 2^20 по горизонтали он будет строится (2^(20-10))^2=2^20 сек. = 12 суток.

Вот черновой набросок идеи алгоритма позволяющего, сэкономить память:

1. За начальную картинку возьмём изображение множества Мандельброта в прямоугольнике [-2,2]x[-1.5,1.5], построенное, например, в разрешении 1024x768. Ищем в нём заданный фрагмент уменьшенный в 0.5<k<=1 раз (т.е. вплоть до уменьшенного в 2 раза размера). Если найден кандидат, печатаем его координаты.
2. Затем строим из этого прямоугольника полоску размером 2048 x h точек с пикселами в 2 раза меньшего диаметра, здесь h - высота искомого фрагмента. При её построении, цвет каждого 4-того пиксела берём из прямоугольника. Затем ищем в этой полоске фрагмент с масштабом в диапазоне [0.5, 1]. Если найден кандидат, печатаем его координаты.
3. Если у нас есть полоска в разрешении 2^n x h, и n<=20, то строим подполоску в разрешении 2^(n+1) x h. Цвет каждого 4-го писксела берём из предыдущей полосы. И снова ищем в ней фрамент.
4. После того, как мы простроили все полоски вплоть до разрешения 2^20 x h, начинаем сдвигать вниз полоски так, чтобы каждая лежала в предыдущей. Т.е сначала двигаем самую последнюю полосу, и когда её двигать некуда сдвигаем предыдующуюю и т.п.

Вобще-то, как видно, цвет пикселов в полосках можно всегда вычислять заново, не учитывая цвета из предыдущей полосы. Производительность упадёт всего лишь в 4/3 раза, а алгоритм упростится. Ещё фрагмент можно не искать в областях далёких от границы множества Мандельброта (т.к. изображения получаются интересными только в окрестности границы).

И всё же, придумать алгоритм работающий без полного перебора, намного интереснее. :) Может у кого-нибудь есть идеи?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB