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

Общие сведения
Цифровые модели изображения
Трассировка и растеризация
Постановка задачи
Идеи реализации
Интерфейс PerlMagick
Расстояние между изображениями
Метод имитации отжига
Объектная модель трассировщика — класс Tracer
Трассировка с использованием непрозрачных треугольников
Трассировка с использованием прозрачных треугольников
Готовая программа

Изображение как объект данных принято представлять с помощью одной из двух моделей: растровой или векторной.

Растровая модель рассматривает изображение как прямоугольный массив цветных точек (пикселов). Таким образом растровое изображение должно содержать информацию о размерах картинки и перечисление цветовых значений всех составляющих её пикселов. В качестве цветового значения часто применяют тройку чисел R, G, B, заключённых в диапазоне от 0 до 255. Если же количество различных цветов, встречающихся у пикселов изображения, невелико, можно включить в модель изображения палитру — таблицу всех встречающихся цветов, а в качестве цветового значения пиксела взять индекс его цвета в таблице.

Наиболее известные растровые графические форматы — PNG, JPEG, GIF, PCX, BMP и др. — различаются лишь способами сжатия информации, а также наличием ограничений или дополнительных возможностей, вроде анимации (GIF) или дополнительной цветовой компоненты, отвечающей за степень прозрачности пиксела (PNG). Некоторые алгоритмы сжатия информации основаны на отбрасывании тех деталей изображения, которые несущественны для зрительного восприятия (JPEG), другие не допускают никаких потерь информации. Формат GIF позволяет хранить последовательность из многих изображений одного размера, которые при показе будут сменять друг друга (это явление называется анимацией). Некоторые из названных форматов обременены патентными ограничениями.

Графические файлы в растровых форматах обычно создаются программным обеспечением сканеров, цифровых фотоаппаратов, или популярными графическими редакторами (Adobe PhotoShop, The Gimp!).

Растровое представление хорошо подходит для фотографических изображений, для которых характерно плавное перетекание цветов. Растровые изображения плохо переносят даже простые геометрические преобразования, такие как сдвиги, масштабирование и поворот.

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

Среди популярных векторных форматов следует назвать уже знакомые нам форматы SVG, PostScript и PDF.

Файлы в векторных форматах обычно создаются векторными графическими редакторами (Corel Draw, Inkscape).

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

Иногда бывает нужно перейти от растрового представления изображения к векторному или наоборот. Переход к растровому представлению называют растеризацией (рендерингом). Обратный процесс называется трассировкой (векторизацией).

Алгоритмы растеризации реализованы в огромном количестве программ и библиотек. Задачу трассировки решают, например, программы autotrace и potrace.

На рисунке 47.1. «Растровое изображение и результат его трассировки программой autotrace» слева мы видим цифровую фотографию прекрасной железобетонной католической капеллы Notre Dame du Haut в Роншане (Франция) архитектора Ле Корбюзье. Справа показаны векторные изображения, поочерёдно сменяющие друг друга. Они получены программой autotrace. Изображения состоят соответственно из фигур двух, четырёх и шестнадцати различных цветов (количество цветов можно задать как параметр командной строки).


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

Мы видим, что качество изображения несколько пострадало, да иначе и не могло быть, поскольку алгоритм трассировки накладывал ограничение на используемые ресурсы — количество цветов. Кроме того появились артефакты вроде зазоров между областями. Но даже такая шестнадцатицветная картинка хорошо узнаваема и по-своему интересна.

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