Идеи реализации

Хотелось бы, чтобы наша программа понимала исходные изображения в самых разных графических форматах. Разумеется, мы не собираемся ради этого изучать все эти форматы, а вместо этого поручим работу одной из многочисленных графических библиотек. Наш выбор пал на проект 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 1 2 . Если пожелать, чтобы расстояние между наиболее различающимися цветами равнялось единице, а между одинаковыми — нулю, нужно разделить это выражение на 3: dist X Y = R X R Y 2 + G X G Y 2 + B X B Y 2 3 1 2 .

Возможны и другие выражения для расстояния между цветами: dist X Y = R X R Y 2 + G X G Y 2 + B X B Y 2 3 или dist X Y = 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 = x = 0 w 1 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. На процесс трассировки будут влиять несколько параметров. Среди них имя исходного графического файла imageFileName, количество треугольников triangles, максимальная величина мутации step, начальная температура theta, параметр, отвечающий за скорость остывания decay, количество мутаций mutations, после которого процесс трассировки должен завершиться.

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

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.

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

Выяснив, что объекты Image::Magick могут сообщать размеры изображения и цветовые значения пиксела с заданными координатами, мы вначале так обрадовались, что не стали узнавать о других возможностях класса, считая, что этого нам будет вполне достаточно.

Замысел был таков: при вычислении расстояния между изображениями в методе deviation потребуется многократно вычислять цветовое расстояние между соответствующими пикселами на оригинале. Как определить цвет пиксела на исходной картинке, мы уже знаем: нужно использовать метод GetPixel класса Image::Magick. А вот цвет пиксела на треугольной трассировке мы будем вычислять сами.

Первоначальная версия программы triangletrace-opaque.pl (opaque — непрозрачный) использовала непрозрачные треугольники. Треугольники, помещаемые на рисунок позже, могли заслонить (частично или полностью) ранее нарисованные. Поэтому нужно перебирать треугольники от конца списка к началу до тех пор, пока не будет найден треугольник, содержащий пиксел с данными координатами. Тогда цвет найденного треугольника и станет искомым цветом пиксела.

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

А как же проверить, принадлежит ли пиксел треугольнику, зная его координаты и координаты вершин треугольника? На рисунке 47.2. «Определение принадлежности точки треугольнику» показаны два случая расположения точки Z по отношению к треугольнику A B C  — внутренний и внешний.


Будем говорить, что пара векторов на плоскости u v  — правая, если кратчайший поворот от u к v осуществляется против часовой стрелки, если же по часовой стрелке, то левая. Из рисунка видно, что во внутреннем случае каждая из пар A B A Z , B C B Z , C A 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 · 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 = u x u y v x v y .

Прозрачность можно понимать как дополнительное цветовое свойство. Помимо цветовых компонент у пиксела появляется ещё одно число, заключённое между нулём и единицей — так называемая альфа. Нулевое значение альфы отвечает полной непрозрачности, единица означает полную прозрачность. Получается так называемая цветовая схема 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.

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

Теперь алгоритм определения цвета пиксела изменится. Вначале этот цвет сделаем равным цвету фона (например, белым). Затем перебираем треугольники в порядке их перечисления, и для тех из них, которые содержат данный пиксел, будем корректировать искомый цвет, комбинируя его с цветом треугольника и с учётом прозрачности треугольника. По окончании перебора получим нужный цвет.

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

Как нас раньше не посетила эта благодатная идея — растеризовать векторный результат трассировки для сравнения с оригиналом! Естественно, растеризовать силами пакета Image::Magick. Скажем, записать на диск SVG-картинку, создать новый объект Image::Magick, прочитать в него изображение из только что записанного файла, а затем в двойном цикле по координатам пикселов заняться вычислением расстояния между оригиналом и приближением, вызывая для каждого пиксела методы GetPixel.

Изучая возможностей пакета Image::Magick, мы сделали ещё одно открытие: имеются методы для определения расстояний между изображениями, причём основанные на разных формулах цветового расстояния между пикселами — на выбор! Будучи запрограммированными на языке C, эти методы работают на порядок быстрее, чем наш двойной цикл по координатам.

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

К тому же счёт создаваемых файлов шёл на десятки тысяч, что грозило исчерпанием свободного места на диске. Для экономии места мы при записи SVG-файлов использовали сжатие информации популярным компрессором gzip. Этот компрессор не является рекордсменом по части сжатия, однако он очень быстрый. Имена полученных файлов оканчивались на .svgz, а не на .svg, а утилиты из пакета imagemagick понимают, что при считывании такие файлы нужно разжимать. Хотя размер файлов из-за сжатия и получался заметно меньше (порядка килобайта), экономия вышла небольшая: во многих файловых системах каждый файл, даже маленький, занимает не меньше четырёх килобайт.

Лучшего результата удалось добиться, используя графический формат GIF с возможностью анимации. Прямо в нашей программе последовательные этапы поиска оптимального приближения добавлялись как кадры в объект Image::Magick, а в конце работы программы содержащееся в этом объекте изображение записывалось в GIF-файл. Чтобы размер этого файла не оказался слишком большим, и, чтобы добавление кадров в объект не привело к ошибке, связанной с нехваткой оперативной памяти, мы добавляли не каждый кадр, а лишь каждый двухсотый.

Операции записи файла на диск и последующее их считывание очень сложны и занимают много времени. Оказалось, что Image::Magick умеет считывать изображения не только из файлов, но и из скалярных переменных. Можно создать строковую переменную, записать в неё SVG-текст и затем прочитать в объект Image::Magick и использовать для вычисления расстояния до оригинала. Таким образом отпала необходимость в записи SVG-картинок на диск, а весь результат работы программы стал заключаться в создании файла GIF.

Продолжение скоро будет…

Информатика-54© А. Н. Швец