Алгоритмы векторизации цветных растровых изображений на основе триангуляции и их реализация

Задача векторизации обычно решается для случая бинарного (двуцветного) растра [1, 2]. При обобщении известных методов на многоцветное изображение (например, путем предварительного расслоения изображения по цветам) значительно возрастает их трудоемкость. В то же время полученные векторные модели впоследствии трудно совместить между собой.

В работе [3] для решения задачи векторизации многоцветного растрового изображения предлагается следующий метод построения комплексной векторной модели:

1. создается дополнительный растр границ между пикселями исходного растра изображения;
2. отслеживаются граничные линии на дополнительном растре, разделяющие пиксели растра на области, окрашенные в одинаковые цвета;
3. граничные линии аппроксимируются отрезками;
4. строится триангуляция с ограничениями по полученным отрезкам;
5. по триангуляции распознаются объекты векторной модели изображения.

В настоящей статье предлагаются усовершенствованные алгоритмы выделения граничных линий, их аппроксимации прямолинейными отрезками и кривыми Безье, а также распознавания объектов векторной модели изображения. Наряду с этим описывается реализация предложенных алгоритмов в виде модуля, подключаемого к программе иллюстративной графики Adobe Illustrator™, которая предназначена для работы с векторными объектами.

Нахождение граничных линий

Будем считать, что исходное растровое изображение (растр) состоит из пикселей, каждому из которых приписан некоторый цвет – целое положительное число (номер цвета). Граница между двумя совокупностями пикселей, окрашенных в два различных цвета, всегда проходит между пикселями, поэтому для построения граничных линий необходим вспомогательный растр – растр границ. Для его построения вначале расширим исходный растр G из M строк и N столбцов, дополнив его строками номер 0 и номер M + 1 и столбцами номер 0 и номер N + 1. Дополненным пикселям присвоим цвет номер 0. Затем сформируем растр границ B = {b,u} размером (M + 1)×(N + 1), элементы которого располагаются в узлах сетки, образованной точками расширенного растра G.

Растр B определим по-другому, чем в [3]. Элемент b растра B задает границы между четырьмя соседними пикселями различных (в общем случае) цветов {g, g, g, g} на растре G, а элемент u – признак неудаляемой узловой точки. В элементе b границы кодируются четырьмя битами следующим образом: если есть линия от центра вправо, то код: 1000; если вверх – то код: 0100; если влево – то код: 0010; если вниз – то код: 0001. При нескольких линиях общий код образуется наложением кодов по операции или. Если цвета у всех четырех пикселей одинаковы, то код равен нулю. Элемент u = 1, если узловая точка в центре между четырьмя соседними пикселями есть, и u = 0, если узловой точки нет. На рис. 1 показаны все возможные ситуации расположения различных цветов на соседних четырех пикселях растра G и соответствующие им значения кода b и признака u. Цифрами от 1 до 4 обозначены различные цвета.

Воспользуемся определением граничной линии, взятым из [3].

Определение 1. Граничной линией назовем ломаную линию, образованную точками растра B, в которой: 1) соседние узлы этой ломаной являются 4- соседями на растре B; 2) при движении вдоль ломаной от начального узла до конечного слева и справа от всех отрезков ломаной находятся пиксели растра G двух различных цветов (слева одного, а справа – другого цвета); 3) ломаная является максимальной по включению.

Алгоритм 1. Выделение граничных линий.

1. Цикл по точкам растра B
   1. Если код b очередной точки равен нулю, то переход к следующей очередной точке.
   2. Иначе выполнение следующих действий:
      1. Если признак u = 0, то u := 2.
      2. Отслеживание граничной линии вплоть до точки с кодом u > 0.
      3. Если конечная (pq)-я точка совпадает с начальной (ij)-й точкой, то выделение граничной линии в виде замкнутой ломаной.
      4. Иначе, если признак начальной точки u = 2, то отслеживание линии от (ij)-й точки в обратном порядке.

Конец алгоритма.

При отслеживании линии алгоритм также запоминает цвет пикселей слева и справа от линии.

Алгоритм 1, сканируя точки растра B, находит ненулевой код b и далее отслеживает очередную линию вплоть до точки с ненулевым признаком u. При отслеживании в каждую точку b растра B выполняется вход, а затем, если признак u = 0, то выход. При входе и выходе обнуляются соответствующие биты в коде b. Например, если при коде b = 1111 вход был по линии слева от точки растра, а выход по линии вниз, то после этого код b = 1100. Если признак u > 0, то обнуляется только бит входа: b = 1101. Если отслеживание граничной линии начинается с (ij)-й точки растра B, то обнуляется только бит выхода.

Просмотр точек в цикле на шаге 1 производится слева направо и сверху вниз, поэтому коды b точек, с которых может начаться отслеживание граничной линии, могут быть только 1001, 1000 или 0001. Для кода 1001 направление отслеживания может быть любым, например вправо. При продолжении отслеживания в большинстве случаев проблемы неоднозначности не возникает, кроме некоторых вариантов с кодом 1111 (см. рис. 1). Чтобы здесь решить, в каком направлении проходит диагональный участок линии в один пиксель, необходимо просмотреть предыдущее и последующее звено граничной линии. Выбрать следует тот вариант, который дает меньше поворотов в одном и том же направлении.

Нетрудно видеть, что алгоритм 1 каждую точку растра B просматривает от одного (для точки с кодом b = 0000) до пяти раз (для точки с кодом b = 1111), т.е. его трудоемкость линейная от числа точек растра.

Отслеженная граничная линия может быть либо замкнутой, либо ограниченной в начале и конце узлами (точками растра B) с признаком u = 1. На рис. 2 цифрами отмечены цвета пикселей растра G, буквами A, B, C и D – точки растра B, помеченные как узловые. Здесь шесть граничных линий построены соответственно между узлами: 1) A-B; 2) B-C; 3) B-D; 4) A-C; 5) A-D; 6) C-D, седьмая граничная линия замкнутая, она охватывает область пикселей с цветом 1.

Аппроксимация граничных линий прямолинейными отрезками

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

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

Алгоритм 2. Аппроксимация граничных линий.

1. Выделение и вставка характерных узловых точек (рис. 3).
   1. Если граничная линия незамкнута, то выделяются две концевые точки.
   2. Выделяются точки в углах – местах стыковки двух отрезков, если по длине оба строго больше чем 2 пикселя либо оба равны 2 пикселям.
   3. Вставляются точки на отрезках длиной больше чем 2 пикселя, за 0.5 пикселя от места стыковки с другим отрезком длиной в 2 пикселя.
   4. Вставляются точки в середине отрезков, являющихся локальными экстремумами, если на этих отрезках еще нет выделенных точек.
2. Вставляются точки в середине всех тех отрезков, на которых еще нет выделенных точек.
3. Удаляются те точки исходной граничной линии, которые остались не выделенными.
4. Просматриваются все получившиеся отрезки (по два соседних), и если наклон следующего строго совпадает с наклоном предыдущего, то удаляется промежуточная точка.

Конец алгоритма.

Теорема. Алгоритм 2 строит аппроксимирующую ломаную с максимальным отклонением от исходной граничной линии менее 0.5 пикселя.

Доказательство. Введем следующие обозначения (рис. 4): X – точка исходной ломаной; a, b – инцидентные точке X отрезки исходной граничной линии; N, M – середины отрезков a и b соответственно; d – сегмент аппроксимирующей линии; K, T – точки пересечения d с отрезками a и b соответственно.

Длины отрезков a и b будем обозначать теми же буквами.

Рассмотрим следующие случаи взаимного расположения отрезков исходной граничной линии и аппроксимирующей ломаной:

1. a > 2 и b > 2 либо a = 2 и b = 2. Точка X войдет в состав аппроксимирующей ломаной, поэтому отклонение равно нулю.
2. Длина одного из отрезков строго равна 2, длина другого больше чем 2 пикселя. Пусть для определенности a = 2 и b > 2. Тогда на отрезке b на расстоянии 0.5 пикселя от точки X будет добавлена узловая точка, через которую пройдет аппроксимирующая ломаная. Очевидно, что расстояние от точки X до этой ломаной не больше 0.5 пикселя.
3. Длина одного из отрезков, например a, равна единице. Тогда K находится на расстоянии 0.5 от точки X, а евклидово расстояние от точки X до отрезка d – менее 0.5 пикселя.

Теорема доказана.

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

Алгоритм 2 строит весьма точную аппроксимацию, однако в некоторых случаях она может оказаться излишне детальной. Если допустить максимальное отклонение аппроксимирующей ломаной больше чем 0.5 пикселя, то в алгоритме 2 можно выполнить еще один – дополнительный шаг аппроксимации. На этом шаге просматриваются соседние отрезки и проверяется возможность их склеивания – отбрасывания соединяющей их узловой точки. Узловая точка отбрасывается, если: 1) она вставлена на шаге 2 в середину какого-либо отрезка; 2) максимальное отклонение склеенного отрезка от исходной граничной линии не превышает заданной величины ∆ (0.5 < ∆ ≤ 1). Очевидно, что при этом максимальное отклонение не будет превышать ∆. При отбрасывании промежуточных узловых точек необходимо контролировать длины получающихся отрезков так, чтобы отношение длин соседних отрезков на границе не превышало величину 5–10. Это необходимо для того, чтобы облегчить последующую обработку, в частности триангуляцию.

Распознавание объектов на триангуляции

Следующим этапом работы является построение триангуляции Делоне с ограничениями. В качестве ребер ограничений выступают отрезки аппроксимирующих ломаных, полученные на предыдущем шаге. Эта задача на практике решается с помощью известных алгоритмов за время O(n log n) в наихудшем или за O(n) в среднем [4, 5]. При построении триангуляции каждое из ребер треугольников помечается либо как отрезок аппроксимирующей ломаной (и тогда для него запоминается цвет пикселей слева и цвет справа), либо как невидимое ребро.

Далее в построенной триангуляции выделяются области, состоящие из треугольников одинакового цвета (методом заливки с затравкой, см. [5]).

Выделенные одноцветные области необходимо классифицировать на линейные и площадные. В работе [3] эта задача решается построением скелета (серединной линии) внутри области. Для этого первоначально скелет строится внутри каждого из треугольников, который затем сшивается в связный граф. При этом для каждого треугольника оценивается толщина объекта, которая и позволяет классифицировать этот объект как линейный (с толщиной меньше заданной величины) либо как площадной.

В работе [3] для оценивания толщины рассматриваются пары треугольников, имеющих общее невидимое ребро. Однако возможны ситуации (если оба треугольника сильно вытянуты и к тому же тупоугольные), когда оценка толщины оказывается некорректной. Используем более простой и надежный способ – вычисление отношения площади области к суммарной длине ребер ограничений, входящих в область. Последующее более точное измерение толщины объекта будем производить лишь для тех треугольников, которые на первом этапе помечены как линейные.

Рассмотрим идеальный случай: отрезок прямой, образованный двумя параллельными граничными отрезками длиной по L (рис. 5). Треугольник abc содержит одно ребро ограничения ab длины L. Высота треугольника равна d – ширине линии. Площадь треугольника S и участка линии S связаны соотношением:

$$ S_{abc}=\frac{1}{2}\cdotp h\cdotp L=\frac{1}{2}S_{линии} .$$

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

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

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

На рис. 7 одноцветная область изображена черным цветом. На рис. 8 показан результат работы алгоритма классификации объектов. Черным цветом изображены треугольники, классифицированные как линейные, серым – как площадные.

Недостатком данного алгоритма является то, что иногда треугольники на границе площадных объектов принимаются алгоритмом за линейные объекты. Для исправления ошибок данного типа производится дополнительная проверка – с помощью дополнительного просмотра триангуляции все линейные треугольники, у которых длина невидимого ребра больше максимальной ширины линии, и которые соседствуют по невидимому ребру с площадным треугольником, считаются ошибочно классифицированными как линейные, и помечаются как площадные.

Трудоемкость данного этапа – линейная относительно числа точек в триангуляции, так как число треугольников линейно зависит от числа точек.

Создание векторной модели растра

Результатом работы алгоритмов предыдущих этапов является полностью размеченная триангуляция, которая содержит достаточную информацию для построения векторной модели растра. Дальнейшие действия, описанные в работе [3], проиллюстрированы, в частности, на рис. 9.

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

Алгоритм в процессе работы строит участки скелетных линий, проходящих через середины невидимых ребер «боковых» треугольников и заканчивающихся в точке пересечения медиан, если последний треугольник линии – внутренний, либо в точке пересечения ребер ограничений, если последний треугольник линии – оконечный, либо на середине открытого ребра, если последний треугольник данного участка скелетной линии – боковой. На рис. 9 эти случаи соответственно обозначены цифрами 1, 2, и 3.

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

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

Нетрудно видеть, что трудоемкость каждого из рассмотренных этапов – линейная относительно числа треугольников.

Аппроксимация площадных векторных объектов кривыми Безье

Векторная модель растра, построенная рассмотренным выше алгоритмом, представляет собой наборы ломаных и многоугольников. Однако во многих задачах иллюстративной графики и дизайна требуется представлять векторные объекты плавными кривыми, в качестве которых используются, как правило, кривые Безье [4]. При этом обычно ставится задача построения только площадных объектов (без распознавания линий на растре).

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

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

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

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

Алгоритм 3. Аппроксимация граничных линий кривыми Безье.

1. Формирование списка характерных узловых точек.
   1. Если граничная линия незамкнута, то в список заносятся две концевые точки линии.
   2. В список заносятся точки в углах линии – местах стыковки двух отрезков, если они по длине оба больше, чем некоторая заданная величина δ (в пикселях).
   3. В список заносятся точки в середине тех отрезков линии, которые являются локальными экстремумами, если на этих отрезках еще нет точек, занесенных в список.
2. Цикл по списку характерных узловых точек (кроме концевых).
   1. Для k точек исходной граничной линии слева от узловой точки вычисляется наклон аппроксимирующей прямой, проходящей точно через узловую точку и в среднем вблизи k точек.
   2. Вычисляется наклон аналогичной аппроксимирующей прямой для k точек справа.
   3. Если наклоны аппроксимирующих прямых слева и справа различаются более, чем на заданный угол ε, то запоминаются оба наклона для этой узловой точки.
   4. В противном случае вычисляется наклон аппроксимирующей прямой для k точек слева и для k точек справа и запоминается общий наклон для этой узловой точки.
3. Для концевых узловых точек (если они есть) вычисляется наклон аппроксимирующей прямой, проходящей точно через узловую точку и в среднем вблизи k соседних точек.
4. Цикл по списку характерных узловых точек (рассматриваются по две соседних точки).
   1. Строится отрезок аппроксимирующей кривой Безье 3-й степени по двум узловым точкам и по наклонам слева и справа.
   2. Если максимальное отклонение кривой Безье от соответствующего участка граничной линии превышает заданную величину ∆, то в середину этого участка вставляется новая узловая точка и вычисляется для нее наклон аппроксимирующей прямой для k точек слева и для k точек справа.

Конец алгоритма.

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

$$ X(t)=at, Y(t)=bt . $$

Пусть также параметр t на соседних точках граничной линии (на целочисленной сетке) имеет значения 1, 2, ..., k справа от узловой точки и, соответственно, –1, –2, ..., –k слева от узловой точки. Если минимизировать сумму квадратов расстояний между этими точками (x, y) и соответствующими точками прямой (1) – (X(t), Y(t)), то получим следующие оценки коэффициентов наклона a и b:

$$ a = \sum_{i} ix_{i} / \sum_{i} i^{2}, b = \sum_{i} iy_{i} / \sum_{i} i^{2} .$$

Для построения отрезка кривой Безье 3-й степени по двум узловым точкам и по наклонам слева и справа необходимо от наклонов перейти к управляющим точкам. Следует учесть, что отрезок кривой Безье есть локальный параметрический сплайн, заданный полиномами X(t) и Y(t) третьей степени, где параметр t изменяется от 0 до 1. В работе [5] приведен способ нормализации такого сплайна вдоль длины кривой, позволяющий рассчитать длины касательных в точках при t = 0 и t = 1 таким образом, чтобы кривая была наиболее выпуклой.

Проверку максимального отклонения отрезка кривой Безье от соответствующего участка граничной линии можно выполнить с помощью быстрого алгоритма цифровой интерполяции параметрических полиномов [6].

Следует заметить, что некоторый отрезок кривой Безье может на самом деле оказаться прямолинейным, если линии наклона для двух соседних узловых точек направлены строго вдоль отрезка, их соединяющего.

Векторизатор

Приложение, реализующее рассмотренные алгоритмы, было создано как подключаемый модуль к популярному оформительскому пакету Adobe Illustrator™. В данной технологии основной пакет программ принято называть приложением-хостом.

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

Интерфейс задания параметров векторизации изображен на рис. 12, на котором показана настройка параметров построения триангулированной модели растра. Кроме того, в приложении имеется возможность задания количества цветов на растре (после обработки растра для уменьшения на нем цветов), параметров построения кривых Безье.

На рис. 13 показан пример обработки рассмотренными алгоритмами одноцветного растрового рисунка. Слева направо – исходный растр, векторизованное изображение с использованием только площадных объектов, изображение с использованием как линейных, так и площадных объектов, изображение для демонстрации созданных векторных объектов.

Заключение

Рассмотренные в работе алгоритмы являются дальнейшим усовершенствованием методов, предложенных в работе [3]. Эти алгоритмы позволяют производить векторизацию многоцветных растров с классификацией выделенных из изображения объектов на линейные и площадные, достигая при этом высокой точности аппроксимации объектов. Алгоритмы могут функционировать в полностью автоматическом режиме, требуя задания лишь небольшого числа понятных пользователю параметров. Их трудоемкость в большинстве случаев линейная

Литература

1. Розенфельд А. Распознавание и обработка изображений с помощью вычислительных машин: Пер. с англ. М.:Мир, 1972. 230 с.
2. Обработка и отображение информации в растровых графических системах. Минск: ИТК АН БССР, 1989. 180 с
3. Костюк Ю.Л., Новиков Ю.Л. Графовые модели цветных растровых изображений высокого разрешения // Вестник ТГУ. 2002. № 275, апрель. С.153–160.
4. Роджерс Д., Адамс Дж. Математические основы машинной графики. М.: Машиностроение, 1980. 240 с
5. Костюк Ю.Л. Применение сплайнов для изображения линий в машинной графике // Автоматизация эксперимента и машинная графика. Томск: Изд-во Том. ун-та, 1977. С. 116-130.
6. Золотенков В.В., Костюк Ю.Л. Цифровая интерполяция полиномов, не требующая умножения // Управляющие системы и машины. 1984. № 3. С. 31–34.