Глава 47. Трассировка растровых изображений

Идеи реализации
	Глава 47. Трассировка растровых изображений

Интерфейс PerlMagick

Хотелось бы, чтобы наша программа понимала исходные изображения в самых разных графических форматах. Разумеется, мы не собираемся ради этого изучать все эти форматы, а вместо этого поручим работу одной из многочисленных графических библиотек. Наш выбор пал на проект ImageMagick и входящую в него библиотеку libmagick, запрограммированную на языке C. Имеется объектно-ориентированный интерфейс PerlMagick к этой библиотеке для программ на Perl. С точки зрения Perl-программы изображение — объект класса Image::Magick. Создав конструктором новый объект этого класса, можно затем считать в него изображение из заданного файла. После этого становится возможным получать или изменять различные свойства изображения, всячески преобразовывать его, и сохранять результат в файле в любом формате, понятном ImageMagick.

К примеру, этот фрагмент кода создаёт объект Image::Magick, считывает в него изображение из файла Ronchamp.png, выводит на экран размер картинки, копирует пиксел $(20, 10)$ поверх пиксела $(10, 20)$ , и, наконец, записывает получившееся изображение в файл RonchampModified.png.

Perl
use Image::Magick;
my $image=Image::Magick->new;
$image->Read('Ronchamp.png');
printf "Размер: \%d×\%d\n", $image->Get('columns'), $image->Get('lines');
my @pixel=$image->GetPixel(x=>20, y=>10);
$image->SetPixel(x=>10, y=>20, color=>\@pixel);
$image->Write('RonchampModified.png');

(разговор о встроенной процедуре printf нам ещё предстоит).

Расстояние между изображениями

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

Логично было бы вычислять различие (расстояние) между изображениями на основе расстояния между цветовыми значениями их соответствующих (то есть имеющих одни и те же координаты) пикселов. Цветовое значение пиксела можно интерпретировать как координаты $(R, G, B)$ воображаемой точки в трёхмерном цветовом пространстве $R⁣ G⁣ B$ , а точнее в кубе, поскольку каждая из цветовых компонент заключена в пределах от $0$ до $1$ . Тогда в качестве цветового расстояния между цветами двух пикселов хочется взять обычное евклидово расстояние $dist (X, Y) = {({(R_{X} - R_{Y})}^{2} + {(G_{X} - G_{Y})}^{2} + {(B_{X} - B_{Y})}^{2})}^{\frac{1}{2}} .$ Если пожелать, чтобы расстояние между наиболее различающимися цветами равнялось единице, а между одинаковыми — нулю, нужно разделить это выражение на $\sqrt{3}$ : $dist (X, Y) = {(\frac{{(R_{X} - R_{Y})}^{2} + {(G_{X} - G_{Y})}^{2} + {(B_{X} - B_{Y})}^{2}}{3})}^{\frac{1}{2}} .$

Возможны и другие выражения для расстояния между цветами: $dist (X, Y) = \frac{{(R_{X} - R_{Y})}^{2} + {(G_{X} - G_{Y})}^{2} + {(B_{X} - B_{Y})}^{2}}{3}$ или $dist (X, Y) = \frac{|R_{X} - R_{Y}| + |G_{X} - G_{Y}| + |B_{X} - B_{Y}|}{3}$ или даже $dist (X, Y) = \max (|R_{X} - R_{Y}|, |G_{X} - G_{Y}|, |B_{X} - B_{Y}|) .$ Предпоследнее из расстояний легче всего в вычислительном отношении.

За расстояние между двумя изображениями $P$ и $Q$ можно взять среднее цветовое расстояние между соответствующими пикселами: $dist (P, Q) = \frac{\sum_{x = 0}^{w - 1} \sum_{y = 0}^{h - 1} dist (P_{x, y}, Q_{x, y})}{w h} .$ Здесь $w$ и $h$ — размеры картинки, а $P_{x, y}$ и $Q_{x, y}$ — пикселы обеих картинок с координатами $(x, y)$ .

Метод имитации отжига

Поиск наилучшего приближения к оригиналу можно организовать на основе старого доброго метода имитации отжига, обсуждавшегося в главе 45. «Задача коммивояжёра».

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

Объектная модель трассировщика — класс `Tracer`

Трассировкой изображения у нас будет заниматься трассировщик — объект класса Tracer. На процесс трассировки будут влиять несколько параметров. Среди них имя исходного графического файла imageFileName, количество треугольников triangles, максимальная величина мутации step, начальная температура theta, параметр, отвечающий за скорость остывания decay, количество мутаций mutations, после которого процесс трассировки должен завершиться.

Тогда основная часть программы будет состоять из создания трассировщика и немедленного его запуска. При создании конструктору будет передан ассоциативный массив с параметрами:

Perl
use Tracer;

Tracer->new(
		imageFileName=>'Ronchamp.png',
		triangles=>25,
		step=>1E-2,
		theta=>1E-4,
		decay=>10,
		mutations=>2E5,
	)->run;

Часть из переданных параметров станет одноимёнными свойствами создаваемого конструктором объекта, а часть будет использована иначе. Например, числовой параметр triangles (количество треугольников) не станет свойством объекта, а вместо этого в качестве свойства triangles будет указана ссылка на массив с данными о треугольниках. Каждый элемент массива будет содержать информацию о координатах вершин и цвете треугольника. Безусловно, при необходимости мы восстановим количество треугольников как размер этого массива, так что сохранять эту величину отдельно нет необходимости.

Моделью треугольника станет ссылка на ассоциативный массив с ключами points и color. Соответствующими значениями будет ссылка на массив из шести чисел — координат вершин и ссылка на массив с цветовыми компонентами RGB.

Теперь пора назвать методы класса Tracer.

new(%opts): Конструктор. Создаёт новый объект класса на основе переданных в ассоциативном массиве %opts параметров.
run: Запускает процесс трассировки.
width height: Возвращают ширину и высоту картинки (в пикселах).
mutate: Совершает один шаг мутации (смещает вершины случайно выбранного треугольника и его цвет).
deviation: Возвращает расстояние между текущей трассировкой и оригиналом.
status: Выводит на экран сообщение о ходе процесса трассировки.

При необходимости этот список может быть пополнен вспомогательными методами.

Будем говорить, что пара векторов на плоскости $(u, v)$ — правая, если кратчайший поворот от $u$ к $v$ осуществляется против часовой стрелки, если же по часовой стрелке, то левая. Из рисунка видно, что во внутреннем случае каждая из пар $(\vec{A⁣ B}, \vec{A⁣ Z})$ , $(\vec{B⁣ C}, \vec{B⁣ Z})$ , $(\vec{C⁣ A}, \vec{C⁣ Z})$ является правой. Возможна также ситуация, когда все эти пары оказались бы левыми. Такое случилось бы, если обход вершин треугольника в алфавитном порядке проходил бы по часовой стрелке. Во внешнем же случае среди перечисленных пар векторов непременно нашлись бы и правые, и левые.

Все эти рассуждения относятся к случаю, когда точка не лежит на прямой, содержащей какую-нибудь сторону треугольника. Тогда одна из пар не будет ни правой, ни левой — векторы в паре окажутся коллинеарными. Тогда либо поворот не потребуется, либо оба поворота — и против, и по часовой стрелке — будут кратчайшими. Такие случаи редки, но если точка попала на стороны или их продолжения, не будем считать её принадлежащей треугольнику. Итак, для такого строгого попадания необходимо и достаточно, чтобы все пары векторов были бы только правыми или только левыми.

Мы утверждаем, что для правой пары векторов $(u, v)$ выражение $u_{x} v_{y} - u_{y} v_{x}$ положительно, для левой — отрицательно. В случае пары коллинеарных векторов, как нетрудно догадаться, выражение равно нулю.

Действительно, повернём вектор $u$ с координатами $(u_{x}, u_{y})$ против часовой стрелки на $90 °$ . Результат поворота обозначим $u^{'}$ . Нетрудно видеть, что у вектора $u^{'}$ будут координаты $(- u_{y}, u_{x})$ . Повёрнутый вектор будет отложен в левую полуплоскость относительно исходного вектора $u$ . Векторы $v$ , попавшие в эту полуплоскость, будут дополнять $u$ до правой пары, а для этого необходимо и достаточно, чтобы между векторами $v$ и $u^{'}$ был острый угол. Это случится в точности при выполнении условия $v \cdot u^{'} > 0$ , или, в координатах, $u_{x} v_{y} - u_{y} v_{x} > 0$ .

	Примечание
Между прочим, это выражение равно по модулю удвоенной площади параллелограмма, натянутого, как говорят, на векторы $u$ и $v$ . Перед натягиванием параллелограмма следует отложить оба вектора от одной точки, как при сложении по правилу параллелограмма. С учётом знака получится ориентированная площадь параллелограмма. Площадь параллелограмма, натянутого на векторы $u$ и $v$ , равна произведению их длин на синус угла между ними (который равен с точностью до знака косинусу угла между $v$ и $u^{'}$ ). Кроме того, $\|u^{'}\| = \|u\|$ , поэтому выражение $\|u_{x} v_{y} - u_{y} v_{x}\|$ действительно даёт площадь параллелограмма. Читатели, знакомые с высшей математикой, узнали, конечно, определитель $u_{x} v_{y} - u_{y} v_{x} = \|\begin{matrix} u_{x} & u_{y} \\ v_{x} & v_{y} \end{matrix}\|$ .

Примечание

Между прочим, это выражение равно по модулю удвоенной площади параллелограмма, натянутого, как говорят, на векторы $u$ и $v$ . Перед натягиванием параллелограмма следует отложить оба вектора от одной точки, как при сложении по правилу параллелограмма. С учётом знака получится ориентированная площадь параллелограмма.

Площадь параллелограмма, натянутого на векторы $u$ и $v$ , равна произведению их длин на синус угла между ними (который равен с точностью до знака косинусу угла между $v$ и $u^{'}$ ). Кроме того, $|u^{'}| = |u|$ , поэтому выражение $|u_{x} v_{y} - u_{y} v_{x}|$ действительно даёт площадь параллелограмма.

Читатели, знакомые с высшей математикой, узнали, конечно, определитель $u_{x} v_{y} - u_{y} v_{x} = |\begin{matrix} u_{x} & u_{y} \\ v_{x} & v_{y} \end{matrix}|$ .

Проблемы, связанные с непрозрачностью треугольников

Экспериментируя с непрозрачными треугольниками, мы обнаружили, что если их взять побольше, качество трассировки существенно не улучшится. Только лишь небольшое их число — те, что нарисованы позже — вносят свой вклад в полученное изображение. Остальные же полностью или почти полностью закрыты, хотя и они подвержены мутациям, как правило, бесцельным. Нужно дать шанс проявить себя и тем треугольникам, которые нарисованы раньше.

Поэтому в новой версии программы мы к свойствам треугольника добавим величину прозрачности.

Трассировка с использованием прозрачных треугольников

Модель прозрачности

Прозрачность можно понимать как дополнительное цветовое свойство. Помимо цветовых компонент у пиксела появляется ещё одно число, заключённое между нулём и единицей — так называемая альфа. Нулевое значение альфы отвечает полной непрозрачности, единица означает полную прозрачность. Получается так называемая цветовая схема RGBA .

При наложении на пиксел фона (background — фон) с цветовым значением $(R_{B}, G_{B}, B_{B})$ пиксела переднего плана (foreground — передний план) с цветовым значением $(R_{F}, G_{F}, B_{F})$ и со значением прозрачности $A_{F}$ получается пиксел со значением $((1 - A_{F}) R_{B} + A_{F} R_{F}, (1 - A_{F}) G_{B} + A_{F} G_{F}, (1 - A_{F}) B_{B} + A_{F} B_{F})$ . Видно, что при нулевом $A_{F}$ у результирующего пиксела получится цвет пиксела переднего плана, при единичном — цвет фонового пиксела. При промежуточных значениях прозрачности получится промежуточный цвет. На рисунке показано наложение на красный фоновый пиксел зелёного пиксела с прозрачностью, плавно меняющейся от $0$ до $1$ .


Постановка задачи		Готовая программа