Добавляем итерируемые системы функций в dlib

Сегодня я расскажу о том, как я осуществил перенос наработок из проекта нашей библиотеки для обработки изображений Raster and Image Processor (RIP) в библиотеку «швейцарский нож для D» dlib. В статье я немного расскажу о том, как при минимуме усилий и использованной инфраструктуре проекта rip, мне удалось подарить вторую жизнь старой идее реализации Итерируемой Системы Функций (ИФС) и перенести ее со старой dgui (об этом я уже как-то писал) в новую среду.

Итерируемая система функций (более известна под названием итерированная система функций) или ИФС — это удобный математический аппарат для описания фрактальных или фракталоподобных изображений через задание системы уравнений. Система уравнений задается для некоторой начальной точки (обычно, эта точка с координатами (0;0), т.е начало координат) и применяется к ней итеративно, причем, каждое уравнение из системы имеет свою вероятность «быть примененным» к точке. Исходя из этого, для получения некоторого изображения из единственной точки нам нужна система уравнений и некоторое количество раз применения для уравнений, каждое из которых применяется единственный раз в некоторый момент времени. Следуя традиции, один раз применения системы к точке (т.е применения какого-либо уравнения из системы) называется одним поколением ИФС.

Также, для удобства позиционирования графического образа системы на плоскость, можно ввести еще ряд параметров, а именно, масштабы по осям X и Y, а также коэффициенты смещения относительно стартовой точки по тем же самым осям.

Применяя все эти допущения, математический аппарат не содержит ничего серьезного, кроме простой подстановки текущих значений X и Y, в простые линейные уравнения, содержащие шесть коэффициентов. Эти коэффициенты удобно обозначить латинскими буквами: a, b, c, d, e, f и ввести еще один коэффициент p, обозначающий вероятность использования уравнения на текущем шаге. Детали реализации вычисления по этим коэффициентам были нами рассмотрены в статье «Усовершенствуем лист папоротника», но в контексте библиотеки dgui.

Теперь, когда обозначены многие аспекты относительно предыдущей реализации ИФС, можно перейти к непосредственному переносу разработок из rip в dlib.

В rip были использованы несколько иные соображения, чем в dlib. Дело в том, что при создании rip, мы предполагали, что в пределах этой библиотеки можно будет использовать в функциях любые числовые типы (или приводимые к таковым), что позволило бы снизить нагрузку на программиста и сделало бы использование библиотеки более комфортным. Этого мы добились тем, что ввели автоматическую проверку на то, все ли из используемых в шаблонах параметров типов, являются числовыми, а также автоматическим приведением к некоторому удобному для расчетов арифметическому типу.

И этот факт нужно учесть, взяв из модуля templates библиотеки rip шаблон allArithmetic.

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

Эти шаблоны одного из базовых модулей rip мы разместим в файле concepts.d:

module concepts;

private 
{
	import std.meta : allSatisfy;
	import std.traits : isIntegral, isFloatingPoint, Unqual;
}

// Проверяем все ли типы арифметические (т.е числовые)
template allArithmetic(T...)
	if (T.length >= 1)
{
	template isNumberType(T)
	{
		enum bool isNumberType = isIntegral!(Unqual!T) || isFloatingPoint!(Unqual!T);

	}

	enum bool allArithmetic = allSatisfy!(isNumberType, T);
}

// Генерируем универсальный геттер
template addTypedGetter(string propertyVariableName, string propertyName)
{
	import std.string : format;

	const char[] addTypedGetter = format(
		`
		@property
		{
			T %2$s(T)() const
			{
				import std.conv : to;
				alias typeof(return) returnType;
				return to!(returnType)(%1$s);
			}
		}`,
		propertyVariableName,
		propertyName
		);
}

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

А теперь можно перейти к реализации непосредственно ИФС для чего создадим файл ifs.d и добавим туда очень много импортов из стандартной библиотеки Phobos (и из модуля concepts), причем в приватном режиме:

module ifs;

private
{
	import std.algorithm;
	import std.math;
	import std.range;
	import std.random;
	import std.string;

	import concepts;
	import dlib.image;

	import std.stdio;
}

Создадим структуру данных, которая будет описывать стартовую точку для отрисовки итерируемой системы функций:

// Стартовая точка для IFS
class IFS_StartPoint
{
	private
	{
		float x;
		float y;
	}

	// Универсальный конструктор
	this(T, U)(T x, U y)
	   if (allArithmetic!(T, U))
	{
		this.x = cast(float) x;
		this.y = cast(float) y;
	}

	// Получить X координату 
	mixin(addTypedGetter!("x", "getX"));
	// Получить Y координату
	mixin(addTypedGetter!("y", "getY"));

	// Установить X координату
	void setX(T)(T x)
		if (allArithmetic!T)
	{
		this.x = cast(float) x;
	}
	
	// Установить Y координату
	void setY(T)(T y)
		if (allArithmetic!T)
	{
		this.y = cast(float) y;
	}
}

В данном случае, мы создаем класс, отражающий наше понимание некоторой точки плоскости: в этом классе есть универсальный конструктор, способный принять любой числовой тип данных, набор сеттеров для X и Y координат точки, а также микшины, которые встраивают «универсальный геттер» (который взят из модуля concepts).

Аналогично этому классу создаем класс, который будет представлять собой набор масштабирующих (управляют масштабом ИФС по осям) и смещающих (управляют смещением ИФС относительно стартовой точки):

// Масштабирование ИФС
class IFS_Scales
{
	private
	{
		float scaleX;
		float scaleY;
		float offsetX;
		float offsetY;
	}

	this(T, U, V, W)(T scaleX, U scaleY, V offsetX, W offsetY)
	  if (allArithmetic!(T, U, V, W))
	{
		this.scaleX = scaleX;
		this.scaleY = scaleY;
		this.offsetX = offsetX;
		this.offsetY = offsetY;
	}

	// Масштаб по оси X
	mixin(addTypedGetter!("scaleX", "getScaleX"));
	// Масштаб по оси Y
	mixin(addTypedGetter!("scaleY", "getScaleY"));
	// Смещение по оси  X
	mixin(addTypedGetter!("offsetX", "getOffsetX"));
	// Смещение по оси Y
	mixin(addTypedGetter!("offsetY", "getOffsetY"));

	// Установить масштаб для оси X
	void setScaleX(T)(T scaleX)
		if (allArithmetic!T)
	{
		this.scaleX = cast(float) scaleX;
	}

	// Установить масштаб для оси Y
	void setScaleY(T)(T scaleY)
		if (allArithmetic!T)
	{
		this.scaleY = cast(float) scaleY;
	}

	// Установить смещение по оси X
	void setOffsetX(T)(T offsetX)
		if (allArithmetic!T)
	{
		this.offsetX = cast(float) offsetX;
	}

	//  Установить смещение по оси Y
	void setOffsetY(T)(T offsetY)
		if (allArithmetic!T)
	{
		this.offsetY = cast(float) offsetY;
	}
}

И, теперь мы можем описать одно уравнение системы итерируемых функций со всеми коэффициентами и удобным методом отображения:

// Одно уравнение ИФС
class IFS_Equation
{
	private
	{
		float a;
		float b;
		float c;
		float d;
		float e;
		float f;
		float p;
	}

    // Получение коэффициентов ИФС
	mixin(addTypedGetter!("a", "getA"));
	mixin(addTypedGetter!("b", "getB"));
	mixin(addTypedGetter!("c", "getC"));
	mixin(addTypedGetter!("d", "getD"));
	mixin(addTypedGetter!("e", "getE"));
	mixin(addTypedGetter!("f", "getF"));
	mixin(addTypedGetter!("p", "getP"));

    // Универсальный конструктор строк для задания коэффициентов ИФС
	this(R, S, T, U, V, W, Z)(R a, S b, T c, U d, V e, W f, Z p)
		if (allArithmetic!(R, S, T, U, V, W, Z))
	{
		this.a = a;
		this.b = b;
		this.c = c;
		this.d = d;
		this.e = e;
		this.f = f;
		this.p = p;
	}

	void setA(T)(T a)
		if (allArithmetic!T)
	{
		this.a = cast(float) x;
	}
	
	void setB(T)(T b)
		if (allArithmetic!T)
	{
		this.b = cast(float) b;
	}

	void setC(T)(T c)
		if (allArithmetic!T)
	{
		this.c = cast(float) c;
	}
	
	void setD(T)(T d)
		if (allArithmetic!T)
	{
		this.d = cast(float) d;
	}

	void setE(T)(T e)
		if (allArithmetic!T)
	{
		this.e = cast(float) e;
	}
	
	void setF(T)(T f)
		if (allArithmetic!T)
	{
		this.f = cast(float) f;
	}

	// Установить вероятность применения уравнения
	void setP(T)(T p)
		if (allArithmetic!T)
	{
		this.p = cast(float) p;
	}

	override string toString()
	{
		return format("IFS_Equation(%f, %f, %f, %f, %f, %f, probability = %f)", a, b, c, d, e, f, p);
	}
}

Здесь мы используем все те же приемы, что и рассмотренные ранее, в том числе и ограничение сигнатуры методов-сеттеров с помощью соответствующего шаблона (template constrain, так кажется называется эта идея). Также, сам класс берет на себя обязанность по приведению любых параметров к удобному для расчетов float.

Имея одно уравнение ИФС, которое просто служит хранилищем параметров, можно удобным образом построить контейнер, который будет хранить все уравнения некоторой системы и для этого введем псевдоним для массива уравнений системы и создадим новый класс, который будет управлять расчетами над текущей системой уравнений:

// Система уравнений ИФС
alias IFS_EquationSystem = IFS_Equation[];

// Сама ИФС
class IFS
{
	private
	{
		SuperImage surface;
		Color4f color;
		IFS_EquationSystem equationSystem;
		IFS_StartPoint point;
		IFS_Scales scales;
		ulong numberOfGeneration;
		
		float[] probabilities;
	}

	this(W)(SuperImage surface, Color4f color, IFS_EquationSystem equationSystem, IFS_StartPoint point, IFS_Scales scales, W numberOfGeneration)
		if (allArithmetic!(W))
	{
		this.surface = surface;
		this.color = color;
		this.equationSystem = equationSystem;
		this.numberOfGeneration = cast(ulong) numberOfGeneration;

		this.point = point;
		this.scales = scales;
		this.probabilities = equationSystem.map!(a => a.getP!float).array;
	}

	IFS_EquationSystem execute()
	{
		float x = point.getX!float;
		float y = point.getY!float;

		for (ulong i = 0; i < numberOfGeneration; i++)
		{
			auto d = dice(probabilities);
			
			IFS_Equation eq = equationSystem[d];

			auto mul0 = eq.getA!float * x + eq.getB!float * y;
			auto mul1 = eq.getC!float * x + eq.getD!float * y;

			x = mul0 + eq.getE!float;
			y = mul1 + eq.getF!float;

			// surface.drawPoint(
			// 	color, 
			// 	scales.getOffsetX!float + scales.getScaleX!float * x, 
			// 	scales.getOffsetY!float + scales.getScaleY!float * y
			// );

            surface[
                cast(int) (scales.getOffsetX!float + scales.getScaleX!float * x),
                cast(int) (scales.getOffsetY!float + scales.getScaleY!float * y)
            ] = color;

            
		}
		
		return equationSystem;
	}
}

Конструктор класса IFS примет в себя некоторую двумерную поверхность (ее роль будет играть обобщенный класс изображения SuperImage из dlib), цвет (которым и будет отрисована сама система), набор уравнений ИФС, стартовую точку и количество поколений (оно должно быть достаточно большим, чтобы пронаблюдать все интересное). Далее, метод execute описывает собственно говоря саму процедуру итерации через поколения ИФС и на основе расчетов окрашивает нужным цветом рассчитанные с помощью уравнений точки.

В самой процедуре расчета только один момент реально заслуживает отдельного упоминания — это процедура выбора уравнения на основе вероятности, которая осуществляется в одну строку с помощью интересной функции из std.random под названием dice. Эта функция принимая набор вероятностей генерирует число от 0 до n, где n — это количество вероятностей в наборе. Сгенерированное с помощью dice значение используется как индекс для выбора уравнения, а сами вероятности берутся из переменной probabilities класса IFS, которое в свою очередь получается с помощью пробега по массиву уравнений с помощью map и последующей трансформацией диапазона в обычный массив из float`ов.

Прежде чем перейти к испытаниям, я предлагаю вам ненадолго вернуться к статье «Усовершенствуем лист папоротника» и освежить в памяти одну деталь: дело в том, что я уже описывал откуда я брал коэффициенты для уравнений… Вся суть в том, что существует много ресурсов, посвященных фрактальным изображениям и на некоторых из них описания фракталов даются в форме понятного и легкочитаемого формата, использованного когда-то в старой программе FRACTINT.

Именно, использование формата этой программки, а также некоторое его описание в упомянутой статье, поможет нам облегчить испытание универсального модуля для построения ИФС, а парсер этого формата легко написать в несколько строк, используя функциональный подход:

// from FRACTINT format to standart IFS equations
IFS_EquationSystem fromFRACTINT(string description)
	{
		import std.algorithm;
		import std.conv : to;
		import std.range;
		import std.string;

		IFS_EquationSystem ifs_system;

		auto startDescription = description.indexOf("{");
		auto endDescription = description.indexOf("}");

		IFS_Equation toEquation(float[] equation)
		{
			return new IFS_Equation(
				equation[0],
				equation[1],
				equation[2],
				equation[3],
				equation[4],
				equation[5],
				equation[6],
				);
		}

		description[startDescription+1..endDescription]
								.split
								.map!(a => to!float(strip(a)))
								.chunks(7)
								.map!(a => toEquation(a.array))
								.each!(a => ifs_system ~= a);

		return ifs_system;
	}

В этом коде, мы используем тот факт, что описание во FRACTINT-формате начинается с имени ИФС, после которого следуют фигурные скобки, внутри которых и заключены интересующие нас коэффициенты. Эти коэффициенты расположены внутри описания построчно, т.е одной строке соответствует одно уравнение с шестью коэффициентами и одним параметром вероятности применения уравнения. Таким образом с помощью indexOf мы определяем позиции скобок и с помощью них отделяем от строки описание, оставляя только голую строку с числами. После этого, разбиваем строку по пробелам, формируя таким образом, список из чистых значений, но в строковой форме. Данную форму мы преобразуем с помощью шаблона to и алгоритма map в диапазон элементов типа float (на всякий случай убираем все лишнее с помощью strip). Теперь, помня про то, что каждое уравнение — это ровно семь значений, разбиваем диапазон на блоки по семь элементов в каждом и проходим по блокам, преобразуя каждый из них с помощью уже подготовленной ранее функции toEquation в уравнение. Заключительным этапом работы парсера является накапливание всех уравнений с помощью алгоритма each в единый массив, описывающий систему уравнений ИФС.

Испытаем созданный код в проекте dub с добавленной в качестве зависимости библиотеки dlib, используя следующий код:

import std.stdio;
import dlib.image;
import ifs;

void main()
{
	// Поверхность
	auto surface = image(8000, 8000);
	// Система уравнений в удобном формате
	string description = "
Fern {
 0.00  0.00  0.00 0.16 0.00 0.00 0.01
 0.85  0.04 -0.04 0.85 0.00 1.60 0.85
 0.20 -0.26  0.23 0.22 0.00 1.60 0.07
-0.15  0.28  0.26 0.24 0.00 0.44 0.07
}
";
	// Готовая система уравнений
	IFS_EquationSystem equations = fromFRACTINT(description);
	// Задание цвета
	Color4f color = Color4f(0.0f, 120 / 255.0f, 200 / 255.0f);
        // Начальная точка
	IFS_StartPoint startPoint = new IFS_StartPoint(0 , 0);
	// Масштабирующие и смещающие коэффициенты
	IFS_Scales scales = new IFS_Scales(2500, 700, 0.00001, 0.00001);
        // Итерируемая система функций
        IFS ifs = new IFS(surface, color, equations, startPoint, scales, 100_000_000);
	// Запускаем генерацию IFS
	ifs.execute;
	// Сохраняем изображение
	surface.savePNG("ifs_draw.png");
}

Результатом испытания будет нечто с потрясающей степенью детализации:

Красиво, а? И теперь, вы тоже так можете.

P.S: Имейте в виду, что вы не найдете этих блоков в текущей версии rip из репозитория dub, поскольку эти наработки не были включены в текущую ветвь. Кроме того, функция fromFRACTINT планировалась как скрытая функция внутри модуля, доступная тем, кто не поленился покопаться в исходном коде библиотеки (оставлена как «пасхальное яйцо» для демонстрации возможностей).

Описание ИФС в виде формата FRACTINT вы можете найти здесь

Добавить комментарий