Этот пост выстроен по мере увеличения тягомотности. Сначала в нём будет много абстрактных картинок, а потом гораздо больше текста, объясняющего, что и как на этих картинках нарисовано, причём чем дальше, тем тоскливее и зануднее он будет.
Картинки
Картинки
Картинка № 1
Картинка № 2
Картинка № 3
Картинка № 4
Картинка № 5
Картинка № 6
Картинка № 7
Картинка № 8
Кто все эти пикселы?
Кто все эти пикселы?
Как это появилось и что это?
Однажды я сидел на работе, отсчитывал нужные байты в шестнадцатеричном редакторе, и мне стало интересно, как меняются бассейны фракталов Ньютона при малых модификациях функции, по которой он построен (о том, что это значит, будет сказано ниже, так как это скучно). Мне часто приходят всякие левые мысли в голову, но именно эта почему-то всплывала в моей голове не протяжении нескольких недель при каждом открытии шестнадцатеричного редактора, и в итоге я решил сесть, закодить и посмотреть, что получится. В процессе реализации случайно выяснилось, что при раскраске фракталов
Почему оно мне интересно
Мне всегда нравилось генерировать программно всякие картинки --- графики, поверхности, диаграммы. Я очень хорошо помню один день на втором курсе, когда я, раздосадованный задачкой из Демидовича про особо хитрую поверхность, решил нарисовать её на компьютере. В тот день для себя я выяснил, что есть такая программа, как «Мапл», и дико обрадовался, увидев, как быстро и клёво она умеет визуализировать всякие разные штуки. Красиво нарисованная в нём поверхность, правда, решить задачу тогда так и не помогла, но любовь к превращению формул в изображения, по всей видимости, появилась у меня именно в тот день.
На третьем-четвёртом курсах мне пришлось писать трассировщик лучей (это такая программа, которая рисует трехмерную сцену по её аналитическому описанию). Тогда же я начал рисовать в нём фракталы. Это мне очень понравилось: ты пишешь пару-тройку функций и циклов, ставишь на счёт --- и вуаля, вот тебе сложная и изящная картинка. Надо сказать, что руки у меня сами по себе кривые до невозможности, я прямую линию без линейки нарисовать не могу, а если я пытаюсь нарисовать что-то посложнее, то на это обычно нельзя смотреть без слёз. Поэтому факт превращения странички с кодом в картинку у меня всегда вызывал очень тёплые чувства.
Так что же такое эти фракталы?
В этом абзаце я попытаюсь вкратце описать, что же все-таки такое было нарисовано в начале поста. У Стивена Хокинга написано, что каждая формула сокращает число потенциальных читателей в два раза. Если это правда, то на данный момент (24.11.2013) мне достаточно четырёх формул, что этот пост вообще никто из ПЧ не прочитал. Поэтому формул тут не будет, за ними можно пойти в википедию. Я привру, я заранее извиняюсь, но это только для обозримости.
Итак, речь пошла о Ньютоновских фракталах. Это очень простая штука, на самом деле.
В суровой и беспощадной реальности, как бы удивительно это не звучало, очень часто приходится решать уравнения. Увы, для большинства из них не удаётся найти явную формулу для решения; хуже того, есть теоремы, доказывающие, что для некоторых уравнений нет и быть не может общей формулы для решения. Вот как нет самого большого целого числа --- так и таких формул тоже нет. С другой стороны, решать уравнения всё-таки приходятся, ибо поезда должны ездить, а мосты --- не проваливаться под ними. В таких случаях используют так называемые итерационные процедуры. Это такие многошаговые алгоритмы, которые с каждым шагом подкрадываются к искомому значению всё ближе и ближе. (Знаете, есть такой вид спорта --- кто больше знаков числа «пи» посчитает? Так вот там как раз такого рода алгоритмы работают.) Обычно для них доказывается, что при бесконечном числе шагов они дадут точный результат. На практике ни у кого почему-то нет в запасе бесконечного времени, и поэтому ограничиваются большим-пребольшим, но всё же конечным числом шагов. Как правило, это позволяет узнать корень с весьма высокой точностью.
Так вот. Есть такая штука, как метод Ньютона для решения нелинейных уравнений. Нам совершенно не важно, как именно он устроен. Нам важно то, что он берёт некоторую произвольную точку и неким образом перемещает её, постепенно приближая к одному из корней уравнения.
Вот на этой гифке показано, как коварный метод Ньютона шаг за шагом подкрадывается к корню уравнения
Результат работы метода, как оказывается, зависит от того, из какой точки стартовать. В учебниках доказываются теоремы типа «если начальная точка лежит не дальше такой-то величины от корня, то метод сойдётся к этому корню». Встаёт вопрос --- а что происходит, если точка не лежит рядом (в смысле таких теорем) ни с одним из корней? Как устроено множество точек, стартуя из которых, метод Ньютона сойдётся к заданному корню (эта множество и называется бассейном аттрактора)?
Вопрос оказался решённым только в 70х годах прошлого века методом брутфорсного компьютерного моделирования. Идея --- простая до невозможности. Давайте сопоставим каждому корню цвет --- синий, красный, зелёный и так далее. Если из точки мы сошлись к какому-то корню, то покрасим её в его цвет. Заставим компьютер это посчитать для большого набора точек, а потом напечатать картинку. Поскольку плоскость раскрашивать веселее, чем прямую, то давайте рассматривать точки не на прямой (вещественные), а на плоскости (комплексные). Что мы получим?
Вообще, что бы осознать реакцию на полученные результат, надо на минутку отвлечься и подумать. Чего, казалось бы, можно было ожидать увидеть на такой картинке? Интуиция, тяга к простому и изящному подсказывает --- наверно, к какому корню начальная точка ближе, к такому метод и сойдётся. Поэтому, взяв, скажем, уравнение с тремя корнями, неподготовленный человек ожидает увидеть что-то не сильно отличающееся от
такого,
(Чёрными кругами помечена область, внутри которой сходимость гарантируется Высокой Теорией.) Ну, может, линии не прямые там, а изогнутые. Или в центре какой пузырь появится. В реальности же нас встречает
такое,
что, конечно, «похоже» на то, что ожидалось, но... В общем, наивное ожидание простоты здесь полностью разрушается. Метод оказывается хитро зависящим от выбора начальной точки. Если корней не три, а больше, то картинка может стать ещё более замысловатой. Полученные подобным образом картинки отличаются тем свойством, что при приближении они не теряют в деталях, а наоборот, демонстрируют новые замысловатые узоры, напоминающие чем-то исходное изображение. Обычное такие штуки и называют «фракталами». Примеров приближения к границе фрактала на ютубе завались. Вбиваем в поиск «fractal zoom» и
Итак, «фрактал Ньютона» --- это такая замысловатая самоподобная геометрическая фигура (фрактал), построенная с помощью метода Ньютона. Вот и всё. Все приведённые картинки были сделаны по очень простому алгоритму:
1. Задать функцию (я ограничился из всех функций только многочленами).
2. Задать каждому корню функции свой цвет.
3. Для каждого пиксела картинки прогнать метод Ньютона, посмотреть, куда он сойдётся, и покрасить пиксел в соответствующий цвет. Если из точки мы никуда не сошлись, то покрасить её в чёрный цвет.
Вот и всё. Анонсированный во второй части вопрос («Как меняются бассейны фракталов Ньютона при малых модификациях функции, по которой он построен?») решался путём рисования большого числа картинок, которые потом склеивались в мультики. Один такой мультик выложен тут.
Технические подробности
Технические подробности
Раскраска корней
Внимательный читатель наверняка заподозрил неладное на фразе из предыдущего раздела про раскраску каждого пиксела в цвет, отвечающий корню, к которому сойдётся стартовавший из него метод. Получается, что тогда на картинке должно быть конечное число цветов, равное числу корней функции. Однако на последней картинке (для многочлена с тремя корнями) цветов явно больше трёх: там налицо есть разные оттенки красного, синего и зелёного. Как так?
Если для той же функции честно ограничиться тремя цветами, то получится такая картинка:
Честные три цвета
Вообще вполне ничего результат, но выглядит аляповато. Надо бы это как-то улучшить. Поскольку человеческий глаз создан видеть то, что он обычно видит, а обычно он не видит только три совершенно однородных цвета, то, наверно, надо придумать способ как-то добавить ещё цветов. Основная идея --- воспользоваться дополнительной информацией для каждого пиксела, а именно --- числом шагов, за которое стартовавший из него процесс сходится. Чем больше шагов надо сделать --- тем темнее мы будем брать цвет для окрашивания пиксела.
Если «затемнение» брать линейно зависящим от числа шагов, то получится так:
Линейное затемнение
Немногим лучше. Если очень постараться, то можно увидеть границы цветов. (Вообще, ситуацию можно улучшить, если искусственно обрезать часть итераций и тем самым искусственно затемнить часть картинки, но какую именно часть резать, в общем случае непонятно.)
Уткнувшись в вопрос «как же раскрасить получившуюся картинку?», я принялся составлять статистики распределения числа шагов по пикселам. Неожиданно (для меня) оказалось, что для многочленов порядка до десяти-двенадцати имеет очень простой вид, вроде
такого,
Иными словами, у распределения есть ровно один максимум, и в его районе сидит очень много пикселов. Положение максимума обычно приходится примерно на треть от общего числа шагов. Тут грех было не прибегнуть к лучшему другу любого статистика --- гауссиане и её правилу трёх сигм. Если брать коэффициент затемнения равным значению гауссианы с центром в минимальном числе шагов и среднеквадратичным отклонением (сигмой), равным примерно пику, то это даёт весьма неплохие результаты:
Раскраска по гауссиане
Поскольку у границы бассейнов процесс обычно сходится медленнее, то создаётся такое ощущение, будто границы обведены чёрным контуром. Это особенно хорошо видно, если всем корням назначить один цвет,
например.
Это вариант мне показался удовлетворительным, и большая часть картинок раскрашивалась именно таким способом.
Недостатки такой раскраски
1. Для многочленов степеней выше десяти красивая картинка распределения с единственным пиком уже обычно оказывается неверна, и, поскольку гауссиана --- очень быстро убывающая функция, то куча пикселов оказывается чёрной. Это можно увидеть, например, на Картинке № 7. В области чёрного пятна сходимость есть, но она очень медленная (надо много-много шагов). Это можно поправить, если задать другую сигму, но подбирать её, увы, придётся руками.
2. Получаемые таким образом картинки имеют тенденцию быть тёмными. На отдельной картинке это выглядит неплохо, но при попытке склеить из них мультик получается форменное месиво. Поэтому для мультика из ссылки выше использовалась линейная покраска с специально заданным интервалом.
3. У раскраски возникают проблемы в районе стыка более чем одного бассейна (как на приведённой картинке --- в центре). Такие области обычно оказываются особо тёмными. Это связано с тем, что обычно в таких точках обнуляется производная функции, а на такие точки у метода Ньютона аллергия и сходимость там особо медленная.
4. Чтобы покрасить фрактал, надо сначала просчитать итерации по всем пикселам, и уже по ним искать максимум распределения. Иными словами, пока мы все пикселы не прогоним, картинки мы не увидим. Вообще, хотелось бы, что бы покраска не выделялась в отдельный этап, а производилась «на лету».
Как оно рисовалось
После придумывания способа раскраски я пришёл к следующей схеме рисования картинок: задаются корни многочлена (по ним сам многочлен однозначно восстанавливается раскрытием скобок), цвета для них, они рисуется, критически рассматривается, и так далее. Для мультика корни перемещались от кадра к кадру по какой-нибудь легко параметризуемой кривой --- кругу там или ещё чему. Большинство картинок было получено случайно в процессе рисования мультиков.
Например, Картинка № 2 получилась из следующего
кадра,
возникшего при прогоне семи корней вдоль одной кривой постоянной ширины. Я подумал, что красный бассейн чем-то похож на птицу (или самолёт), и решил повозиться с ним. Для Картинки № 2 корни были повёрнуты и перекрашены: от семи цветов осталось только четыре. Если их повернуть и покрасить по-другому, то получится Картинка № 8 (да, я --- ленивый халтурщик). Вообще, другой выбор цветов и покраски --- затягивающий процесс. Так, скажем, Картинку № 1 можно сделать потемнее,
такой.
Ещё пример, Картинка № 4. Исходно она была кадром в движении корней ко квадрату,
такой.
После вытаскивания, перворачивания и назначения четырёх цветов в чёрный, получилось
так.
Наконец, заменяя оставшиеся цвета (кроме красного) на оттенки зелёного, получилась Картинка № 4.
Вообще, у меня исходно была следующая простая мысль: брать некоторый контурный рисунок и ставить вдоль его линий корни. Должно было получиться нечто, с одной стороны, похожее на исходный рисунок, и, с другой, такое замысловато-органичное. Эта затея потерпела былинный провал: для её реализации надо брать довольно большее число корней, не менее пяти десятков, а на такое не то раскраски --- машинной точности не хватает. Опять-таки, если у многочлена N корней, то у его производной будет (N-1) корней, и каждый корень производной будет портить жизнь алгоритму в своей окрестности. В общем, тут проблема упёрлась в технику. Её можно попробовать преодолеть (скажем, используя арифметику с произвольным числом байт на числа), но руки у меня в этом направлении не дошли.
Если же пытаться нарисовать что-то осмысленное малым числом корней, то всё упрётся в сложную зависимость картинки от новых корней. Грубо говоря, если мы добавим в уже имеющуюся картинку один новый корень, то мы изменим не только область около него --- мы перестроим практически всё изображение.
Иными словами, рисовать что-то осмысленное на данном моей программой нельзя. Поэтому все приведённые картинки содержат
Один из способов расширения «средств художественной выразительности» лежит в модификации используемого алгоритма поиска корня. Скажем, можно модифицировать метод Ньютона, добавив в него один комплексный параметр. Покажем, как он изменит уже приведённый здесь многострадальный фрактал с тремя корнями. Мнимая часть парамера будет «закручивать» бассейны
в нечто вроде спирали,
а действительная --- делать бассейны «шипастыми»,
похожими на листья папоротника.
Такой трюк использовался для создания Картинки № 6. Злоупотребление закручиванием, кстати, позволяет получить
неплохую эмблему для мясо-молочного комбината.
Программисткие детальки
Рисовальщик одного кадра по заданным корням, цветам и прочим опциям написан на С++, языке, который я знаю лучше всех других (возможно, лучше русского). Построитель корней, цветов и прочих опций для передачи рисовальщику написан на Питоне. Причина простая: корни хочется описывать в терминах языка высокого уровня, а не задавать их руками. Писать парсер для плюсов мне просто лень, а задавать сложные данные в коде --- моветон. Поэтому питон генерирует по описаниям все необходимые данные и передаёт их рисовальщику через командную строку.
Итак, всё просто: скрипт на питоне содержит описание картинки, он вызывает для каждого кадра рисовальщик, рисовальщик обсчитывает каждый кадр и пишет их на диск в формате png. Потом все кадры свинчиваются в видеоролик через ffmpeg.
(В скобках заметим, что я, как тру-нуб, проглядел существование в питоне встроенного класса комплексных чисел и реализовывал их через списки.)
В завершении программистских вопросов я честности ради положу сюда ссылку на исходники. Код простой, как три копейки, но в нём не обошлось без корявых мест. Комментарии там внутри есть, а писать документацию мне лень. Если вдруг возникнет желание их собрать --- пишите.
Вопросы быстродействия
Рисовальщик настолько прост, насколько это возможно, и работает на процессоре и только на нём. Единственная оптимизация --- использование OpenMP для многопоточности.
Конечно, грамотно было бы писать всё на чистом С или вообще считать всю картинку или часть её на видеокарточке. (Тогда можно было бы считать всё в более-менее реальном времени.) Но я этого не умею, и производительность пока измеряется в секундах на кадр, а не в кадрах на секунду. Так что я не спешу. Солдат спит ---
Несколько дополнительных технических подробностей
Нескольких дополнительных технических подробностей под этим тэгом не будет. Полагаю, что если вы добрались до этого места, продравшись сквозь мои тяжеловесные и перегруженные тоскливыми деталями слова, то это очень здорово! Здесь вас ждёт небольшой бонус --- рассказ о том, почему Пост Номер Два не появился в июне, как изначально задумывалось. Разумеется, рассказ этот будет перегружен техническими подробностями и прочей нудятиной.
Итак, однажды утром (ранней весной) на работе за чаем я услышал от коллеги о конкурсе на радио, который она слушает по дороге на работу. Ведущий предлагал товарищам радиослушателям две строчки от четверостишия, а товарищи радиослушатели должны были по смс предложить окончание. Варианты зачитывались по мере поступления в прямом эфире, а в конце объявлялся победитель. Коллега заметила, что каждый раз выигрывают не очень связные и имеющие слабую связь с началом четверостишия варианты. У этого обстоятельства есть два возможных объяснения, первое нам не интересное, а второе --- ведущие конкурса любят
Идея для реализации такой шутки была придумана за один вечер. Есть такая штука, как марковские алгоритмы для генерации случайных текстов. Они берут какой-то (скажем, художественный) текст, считают, с какими вероятностями одни последовательности слов идут за другими, и потом по таким вероятностям строят случайный текст. Впервые я увидел описание такого алгоритма во втором издании книги Programming In Lua, где алгоритму подали на вход исходный текст самой книги. Алгоритм выдал
следующее.
Constructors can also traverse a table constructor, then the parentheses in the following line does the whole file in a field n to store the contents of each function, but to show its only argument. If you want to find the maximum element in an array can return both the maximum value and continues showing the prompt and running the code. The following words are reserved and cannot be used to convert between degrees and radians.
Иными словами, это уже не случайный набор слов, а нечто, несущее на себе отпечаток связности. Похоже на речь больного шизофазией.
Такой алгоритм очень легко реализовать (на питоне у меня на это ушло 90 строк кода с проверкой входных данных и комментариями). Я не удержался и скормил алгоритму пару-тройку имеющихся у меня книг. Результаты --- ниже.
Б. Страуструп. Язык программирования С++
Язык программирования задумывался как язык, включая подмножество собственно С. В конце деструктор нарушает инвариант, и имя конструктора. Задача системы программирования обеспечить создание вариантов функции по шаблону, сложение с двойной вынуждает операции с именем можно создать служащих, часть из управляющего класса может различить эти две особые ситуации являются производными класса, представляет символы не о состоянии сказать нельзя. Значения, обозначающие эти состояния, для может быть свой взгляд на программу или процесс разработки программного обеспечения. Строка это структура данных, как выглядят наиболее употребляемые типы.
«Мастер и Маргарита»
Не прошло и несколько секунд, а также и артистами, а там мы вас и проводим, и притом сравнительно правильно. Перестань, перестань. Я люблю сидеть низко, так показывают свидетели, добрые души. Ну чего вам-то ввязываться в это время его женой художницей. Многое стало известно за последнее время, когда Маргарита Николаевна от Каменного моста немедленно бросилась в лицо и воспаленные глаза. Зеленым огнем загорелся его мозг буквально запылал. Патефона, никакого крика у него под ногами, сказал Стравинский, и вооружился паспортом Латунского. Он радуется, сказал Степа, вчера вечером, ответил, как некогда привык командовать в бою, и первым долгом заперся, а Берлиозу, пробравшийся в Москву, как девическая, вы не хотели подшутить.
«Война и Мир»
Спасибо, отскочил, а умирать со своими. У крыльца дома, завернула направо в кабинет отца, узнав, сказал он, надо наблюдать всех заметных нам животных, сказала она и прежде не могла себе позволить, говоря, что княжна чувствовала себя столь способной любить и быть понято ею. Благообразный, тихий старичок служил с года. Диспозиция, желчно вскрикнул Кутузов, казалось, предстояло ему. Козловский с решительным видом оглянулся на Пьера, опять сблизился с холостыми компаниями и начал решительно работать. Но баба, кланяйся, и окружающими его темными горами. Они старались плыть вперед на ту ногу, стоял у двери балагана. В длинной комнате, требуя, чтобы усилить этот, которого употреблял для игры на клавикордах играть тот экосез его, что ты не говоришь. Кутузов опять с досадой проговорил офицер, сверху вниз блестящими, неопределённого сероватого цвета глазами. Денисов молча следил за этой силой и, потягиваясь после долгого лишения, опьянившее его удовольствием положение всеобщего любимца. Не слушайте меня, старика.
В общем, я почему-то подумал, что что-то подобное будет легко провернуть и со стихами. Идея очень простая. Пусть нам надо сгенерировать две рифмующиеся строчки, удовлетворяющие заданному ритму. Пусть нам задан ритм в виде набора ударных и безударных слогов, скажем, /-/-/-/- (четверостопный хорей), /--/-- (двухстопный дактиль) или даже ---/---/-/-/-/ (абстрактное нечто) --- короче, произвольный набор символов «/» и «-». Пусть у нас есть набор групп рифм: мы знаем, что внутри каждой группы слова рифмуются между собой, и большой запас слов, для каждого из которых мы знаем его представление в слогах (например, «мыло» --- «/-», «птеродактиль» --- «--/-» и так далее). Найдя два слова из одной рифмующейся группы, чьё представление в слогах удовлетворяет хвосту ритма, мы потом слово за словом строим остатки строчек.
Пример: пусть нам задан ритм «/-/-/-/-». Находится группа женских (ударение на предпоследний слог) рифм на «аю», оттуда извлекается два слова: «краю» и «лаю». Оба имеют структуру «/-», и остаётся ритм «/-/-/-». Для каждой строки он случайным образом разбивается на части (с тем условием, что в каждой части должен быть один и только один ударный слог). Пусть первая строка получила набор «/», «-/», «-/-», вторая --- «/-», «/-», «/-». Из списка слов с известным представлениями в виде слогов извлекаются случайные слова, удовлетворяющие этим схемам, и составляются сами строчки. Например, для приведённых разбиений это может быть такое:
Ёж стекло десница краю
Рыба воля вилы лаю
Строчки, разумеется, совершенно бессмысленные, но формально под ритм попадающие. Такой алгоритм, оказывается, вполне можно реализовать. Группы рифм были выдраны из википедии, а разбиения на слога были получены разбором словаря ударений, взятого на либрусеке. Основное время ушло на то, чтобы привести всё это в единообразное состояние. Алгоритм при этом немного усложнился, он стал допускать штуки типа пропуска ударений в двухсложных размерах (кажется, это называется пиррихием). Итого набралось примерно 264 тысячи слов с ударениями и три типа групп рифм (с ударениями на третий, второй и первый слог с конца) числом 4, 90, 87 тысяч слов соответственно.
После этого настал ответственный момент совмещения марковской части и части, строящей строчки. (Это было начало лета, июнь.) Идея была такая: марковский алгоритм читает кучу художественных текстов, и при генерации строк разбиения и удовлетворяющие им слова берутся не абсолютно случайно, а пропорционально их вероятностям в смысле марковского алгоритма.
И вот тут нашла коса на камень.
Оказалось, что подавляющего большинства слов из художественных текстов в словаре рифм нет по очень простой причине: почти все слова в словаре были одном-двух основных падежах. Надо понимать, что с точки зрения бездушного алгоритма слова «полено», «полену», «полена», «поленом» --- это разные слова. Задача же определения ударения в слове «на лету» в русском языке, увы, неразрешима ввиду отсутствия в нём чёткого набора правил для проставления ударений. Существующие же правила часто оперируют частью речи слова (т. е., существительное ли это, глагол или ещё что). Я слабо себе представляю, как формально распознать часть речи. Разве что тоже с помощью словаря.
Таким образом, с точки зрения марковского алгоритма почти все строчки, предлагаемые генератором, имели нулевую вероятность, и де-факто, после долгих вычислений, выдавалась всё такая же бессмыслица. В общем, потерпела эта затея былинный провал, и выход второго поста переполз с лета на вот теперь. Зато я стал лучше разбираться в питоне (наверно).
Потом, в июле, мне пришлось сочинять один стих уже самостоятельно. В отличие от моей программы, я, как показала практика, не умею считать до одиннадцати.
А ещё тут будет песенка!
Прослушать или скачать Uriah Heep Lady In Black бесплатно на Простоплеер
Вот теперь всё =)