IFS

[fregimus]

Не спалось, построил — чтобы уснуть. Не помогло, зато красиво. Тыцайте до полного размера 600×1000 (40 КБ). Хорошо известная формула, 600 тысяч итераций.



Исходный код, Mathematica 6.0, сырой и неоптимальный. Скорость примерно 10000 итер/сек на P4 2.8 MHz. Уменьшите размер пиксела до 0.001 и увеличьте изображение до 600,1000, чтобы повторить картинку в точности.

TFun[a_?MatrixQ, b_?VectorQ] := Compile[{{x, _Real, 1}}, {a.x + b}];

(* Prepare a set of function for quick retrieval.
   The resulting list has an accrued weight as the first element of each
   nested list, so that the first one that's >= random_num can be chosen *)
TFunSet[t_, w_] := Block[{a, p, s, q},
   {p, a} = Transpose[w];              (* {weight, {fun arg..}}..  *)
   p = Accumulate[p]/Plus @@ p;        (* Normalize weights to 1   *)
   MapThread[{#1,t @@ #2}&,{p, a}]];   (* To {weight bound, fun}.. *) 

(* Select а random function from the given TFunSet *)
TSetSelect[set_] := Block[{r = RandomReal[]},
   Select[set, First[#] >= r &, 1][[1, 2]]];

(* Use the above and apply the resulting function to the vector x *)
TSetApply[set_, x_] := First[TSetSelect[set][x]]

Block[{
  ITER = 10000,
  tset = TFunSet[TFun, {
     {0.01, {{{0, 0}, {0, 0.16}}, {0, 0}}},
     {0.85, {{{0.85, 0.04}, {-0.04, 0.85}}, {0, 1.6}}},
     {0.07, {{{0.22, -0.26}, {0.23, 0.22}}, {0, 1.6}}},
     {0.07, {{{-0.15, 0.28}, {0.26, 0.24}}, {0, 0.44}}}
     }]},

 Rasterize @ ListPlot[NestList[TSetApply[tset, #] &, {0, 0}, ITER],
   PlotStyle -> {PointSize[0.005], RGBColor[0, 7/8, 0]},
   ImageSize -> {300, 500},
   AspectRatio -> Full
   ]]

Хозяйке на заметку. Без Rasterize[...] результат будет очень громоздким, и Front End будет его долго форматировать, а так он превращается в растровое изображение еще в ядре, и отрисовывается моментально.

Comments

[fregimus.livejournal.com]

Четыре. Я формулы из этой статьи взял: http://www.cs.wlu.edu/~levy/pubs/bics2004.pdf

[rwalk.livejournal.com]

Вы имеете в виду, что точек 600000, а итераций же наверное около 10? Кстати, интереснее было бы визуализировать саму меру, а не ее носитель. Таких картинок не припомню.

[fregimus.livejournal.com]

Нет-нет, начал с {0,0}; с взвешенной вероятностью выбирается одна из 4 функций, отображает точку. Повторяем 600000 раз: процессор — камень, ему-то что :-)

[rwalk.livejournal.com]

А - ну да - я о другом алгоритме подумал. То есть действительно симулируется мера, а не носитель. Интересно, до какой степени картинка зависит от весов? Чем больше число итераций, тем ближе она к предельному множеству.

[fregimus.livejournal.com]

Сильно зависит. Как-то не торопится она к предельному множеству. :-) Если первый вес поднимать, получаются толстые стебли и редкие листья. Если увеличивать вес 0,07 — левого и правого поворотов — получаются сплошные толстые колючие листья.

Смотрите, что я нашел: http://en.wikipedia.org/wiki/Iterated_function_system#Example:_a_fractal_.22fern.22

У Вас Mathematica есть? Могу кодом поделиться, если интересно.

[rwalk.livejournal.com]

Математика-то есть - правда пользовался ею 2 раза в жизни. Оба раза вычисления настойчиво подталкивали к заключениям, которые по некоторому размышлению оказывались совершенно ложными:))) Тут же код совсем нехитрый должен быть? Кстати, вот такая визуализационная задача - как "нарисовать" меру с промежуточной размерностью, но с полным носителем? Из того, что Вы говорите о зависимости от весов следует, что в обсуждаемом примере "рисуется" не только носитель, но и до некоторой степени мера, но с другой стороны, подозреваю, что если бы носителем был весь квадрат, то вряд ли бы что-нибудь красивое получилось (есть такие примеры?).

[fregimus.livejournal.com]

Мне кажется, что я не въезжаю — то, что генерирует IFS, ведь и есть мера, разве нет? Боюсь, что тут я плавать буду. Я ведь прикладными вещами занимаюсь, и IFS меня заинтересовали как способ кодирования бинарных деревьев, выстраивающих их по «похожести», почему я Леви и читаю. А от measurement theory, боюсь, у меня одно только название осталось.

«Лопух» этот в целом форму сохраняет, детали только по-разному проявляются при разных весах функций; support — это ведь носитель, правильно? — здесь явно лопухообразный. :-)

если бы носителем был весь квадрат, то вряд ли бы что-нибудь красивое получилось (есть такие примеры?).
Кривые Гильберта подойдут?

[rwalk.livejournal.com]

Да нет - тут тоже вопрос вполне прикладной. Слово "мера" (measure) я тут употребил в значении "вероятностное распределение" (а теория меры - measure theory). Его носитель (он же support) - это наименьшее замкнутое множество полной меры. Данные, которые используются для описания IFS, состоят из двух частей: собственно линейные преобразования и их веса. Преобразования определяют предельное множество (не помню, как его фрактальщики точно называют), а веса задают некоторое вероятностное распределение (меру) на этом множестве. Эту меру правильно называть гармонической (хотя не уверен, что IFS people так говорят). Мы симулируем это распределение, используя эргодическую теорему: для типичной траектории частота попаданий в любое подмножество квадрата сходится к мере этого подмножества. В Вашей симуляции количество итераций "не очень маленькое" и "не очень большое" - а "в самый раз" - если меньше, то форма не проявится, а если больше, то мы потеряем информацию о мере, а увидим только носитель. Изменение весов приводит к изменению предельной меры (но с сохранением носителя!), что, как Вы заметили, видно и из Вашей симуляции.

Меня наш разговор подвигнул на поиски. На первый взгляд, вроде бы вот тут http://flam3.com/flame.pdf
что-то похожее на то, что я хочу, делается. Пожалуй, дам студенту для разбирательства - как раз тему у меня попросил.

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

Насчет кривых Гильберта - возникающее предельное множество тут конечно квадрат, но по-видимому можно использовать что-то вроде различных весов на ребрах для того, чтобы получить меру, носитель у которой весь квадрат, но распределена она будет очень неравномерно (с размерностью меньше 2). По-моему хороший test case. Спасибо!

[rwalk.livejournal.com]

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

[fregimus.livejournal.com]

уже много лет гложет желание красивые картинки показывать, а не только мелом по доске стучать :)
Так Mathematica же! Посмотрите вот здесь, какие роскошные демонстрации народ делает!

Я статью эту загружаю, посмотрю. Я, кажется, понял, что Вы ищете, и, если мне что-нибудь в голову придет, обязательно Вам скажу.

[rwalk.livejournal.com]

Да видел я картинки (и даже кино) с Математикой - поэтому и гложет :)))

[mops.livejournal.com]

если не трудно поделитесь с начинающим. viaceslav@gmail.com

[fregimus.livejournal.com]

Да он немного не для начинающих. Вы бы с чего попроще начинали. :-)

Я «Математику» довольно хорошо знаю, так что если будут вопросы (не по этому коду, а вообще) — спрашивайте.

PS. Я неправильную версию выложил, вернее, не ту «лишнюю» строчку из нее удалил. прошу прощения. Здесь код теперь правильный. Не хватало функции TSetApply[...].

ЗЗЫ. Правильный код в самой записи. Здесь была версия с неправильными весами.

[fregimus.livejournal.com]

Только веса переврал. Правильный код я в саму запись вставил.

[arno1251.livejournal.com]

И кто-то камень положил в его протянутую мамку.

[fregimus.livejournal.com]

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

Cuneintel

[arno1251.livejournal.com]

Если внимательно вглядеться, данные производителя выбиты на нём клинописью.