Algorithms for vectorization of a multicolor raster image based on triangulation and their realization.pdf Задача векторизации обычно решается для случая би-нарного (двуцветного) растра [1, 2]. При обобщении извест-ных методов на многоцветное изображение (например, пу-тем предварительного расслоения изображения по цветам)значительно возрастает их трудоемкость. В то же время по-лученные векторные модели впоследствии трудно совмес-тить между собой.В работе [3] для решения задачи векторизации много-цветного растрового изображения предлагается следующийметод построения комплексной векторной модели:1) создается дополнительный растр границ между пик-селями исходного растра изображения;2) отслеживаются граничные линии на дополнительномрастре, разделяющие пиксели растра на области, окрашен-ные в одинаковые цвета;3) граничные линии аппроксимируются отрезками;4) строится триангуляция с ограничениями по получен-ным отрезкам;5) по триангуляции распознаются объекты векторноймодели изображения.В настоящей статье предлагаются усовершенствован-ные алгоритмы выделения граничных линий, их аппрокси-мации прямолинейными отрезками и кривыми Безье, а так-же распознаванияПри отслеживании линии алгоритм также запоми-нает цвет пикселей слева и справа от линии.Алгоритм 1, сканируя точки растра B, находитненулевой код bij и далее отслеживает очереднуюлинию вплоть до точки с ненулевым признаком uij.При отслеживании в каждую точку brs растра B вы-полняется вход, а затем, если признак urs = 0, то вы-ход. При входе и выходе обнуляются соответствую-щие биты в коде brs. Например, если при кодеbrs = «1111» вход был по линии слева от точки растра,а выход по линии вниз, то после этого кодbrs = «1100». Если признак urs > 0, то обнуляетсятолько бит входа: brs = «1101». Если отслеживаниеграничной линии начинается с (ij)-й точки растра B,то обнуляется только бит выхода.Просмотр точек в цикле на шаге 1 производитсяслева направо и сверху вниз, поэтому коды bij точек,с которых может начаться отслеживание граничнойлинии, могут быть только «1001», «1000» или «0001».Для кода «1001» направление отслеживания можетбыть любым, например вправо. При продолжении от-слеживания в большинстве случаев проблемы неод-нозначности не возникает, кроме некоторых вариан-тов с кодом «1111» (см. рис. 1). Чтобы здесь решить, вкаком направлении проходит диагональный участоклинии в один пиксель, необходимо просмотреть пре-дыдущее и последующее звено граничной линии. Вы-брать следует тот вариант, который дает меньше по-воротов в одном и том же направлении.Нетрудно видеть, что алгоритм 1 каждую точкурастра B просматривает от одного (для точки с ко-дом bij = «0000») до пяти раз (для точки с кодомbij = «1111»), т.е. его трудоемкость линейная от числаточек растра.Отслеженная граничная линия может быть либозамкнутой, либо ограниченной в начале и конце узла-ми (точками растра B) с признаком uij = 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.Рис. 2АППРОКСИМАЦИЯ ГРАНИЧНЫХ ЛИНИЙПРЯМОЛИНЕЙНЫМИ ОТРЕЗКАМИПолученные на предыдущем этапе граничные ли-нии содержат чрезмерно большое число точек и вы-глядят ступенчатыми, поэтому их необходимо ап-проксимировать. Рассмотрим аппроксимацию лома-ными линиями, такими, что их отклонения от исход-ной граничной линии должны быть невелики, какправило, не более чем 1 пиксель. При этом также тре-буется, чтобы наиболее удаленные точки граничнойлинии отклонялись от аппроксимирующей ломанойпо возможности на одинаковое расстояние по обеимсторонам.Приведенный в [3] способ аппроксимации можетполучить такой отрезок ломаной, что соответствую-щий участок исходной граничной линии располагает-ся весь по одну его сторону. Поэтому рассмотрим ещеодин способ, лишенный указанного недостатка.Алгоритм 2. Аппроксимация граничных линий.1. Выделение и вставка характерных узловых то-чек (рис.3).1.1. Если граничная линия незамкнута, то вы-деляются две концевые точки.1.2. Выделяются точки в углах - местах сты-ковки двух отрезков, если по длине обастрого больше чем 2 пикселя либо обаравны 2 пикселям.1.3. Вставляются точки на отрезках длинойбольше чем 2 пикселя, за 0.5 пикселя отместа стыковки с другим отрезком длинойв 2 пикселя.1.4. Вставляются точки в середине отрезков,являющихся локальными экстремумами,если на этих отрезках еще нет выделенныхточек.2. Вставляются точки в середине всех тех отрез-ков, на которых еще нет выделенных точек.3. Удаляются те точки исходной граничной ли-нии, которые остались не выделенными.4. Просматриваются все получившиеся отрезки(по два соседних), и если наклон следующегострого совпадает с наклоном предыдущего, тоудаляется промежуточная точка.Конец алгоритма.Точки локальных экстремумовТочка на длинной прямой при стыковкес отрезком длиной 2 пикселяУгловая точкаРис. 3Теорема. Алгоритм 2 строит аппроксимирующуюломаную с максимальным отклонением от исходнойграничной линии менее 0.5 пикселя.Доказательство. Введем следующие обозначения(рис. 4): X - точка исходной ломаной; a, b - инци-дентные точке X отрезки исходной граничной линии;N, M - середины отрезков a и b соответственно;d - сегмент аппроксимирующей линии; K, T - точкипересечения d с отрезками a и b соответственно.Длины отрезков a и b будем обозначать теми жебуквами.21234ABCDРассмотрим следующие случаи взаимного распо-ложения отрезков исходной граничной линии и ап-проксимирующей ломаной: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 - ширине линии. Площадьтреугольника Sabc и участка линии Sлинии связанысоотношениемлинии1 1Sabc =2⋅h⋅L=2S .ca L bh = dРис. 5Аналогичные соотношения выполняются с неко-торыми погрешностями и для случаев типа изобра-женных на рис. 6, когда вычисляется средняя шириналинии для группы треугольников (при этом площадьвнутреннего треугольника А также должна быть уч-тена).Таким образом, можно сформулировать следую-щий критерий: если площадь группы треугольниковменьше половины произведения суммарной длиныребер ограничений на максимально возможную ши-рину линии, то треугольники считаются линейными.Как показывают вычислительные эксперименты,применение этого критерия к группе треугольниковдает более качественные результаты, чем к отдельнымтреугольникам.При этом предлагается формировать группы изтреугольников внутри одноцветной области, смежныхс общей для них опорной вершиной. Из несколькихподряд расположенных вдоль границы вершин в ка-честве опорной следует выбирать ту, которая являетсясмежной не менее чем с тремя треугольниками. Кро-ме того, при этом следует учесть особые случаи, ко-гда вся одноцветная область состоит из одного илидвух треугольников. В процессе анализа одноцветнойобласти отдельные треугольники могут поочереднопопасть в две-три группы, что увеличивает вероят-ность того, что они будут классифицированы пра-вильно. Некоторый треугольник классифицируетсякак площадной, если он поочередно помещался в не-сколько групп, и хотя бы одна из них была классифи-цирована как площадная. В противном случае тре-угольник классифицируется как линейный.На рис. 7 одноцветная область изображена чернымцветом. На рис. 8 показан результат работы алгоритмаклассификации объектов. Черным цветом изображенытреугольники, классифицированные как линейные,серым - как площадные.Рис. 7Рис. 8Недостатком данного алгоритма является то, чтоиногда треугольники на границе площадных объектовпринимаются алгоритмом за линейные объекты. Дляисправления ошибок данного типа производится до-полнительная проверка - с помощью дополнительно-го просмотра триангуляции все линейные треуголь-ники, у которых длина невидимого ребра больше мак-симальной ширины линии, и которые соседствуют поневидимому ребру с площадным треугольником, счи-таются ошибочно классифицированными как линей-ные, и помечаются как площадные.Трудоемкость данного этапа - линейная относи-тельно числа точек в триангуляции, так как числотреугольников линейно зависит от числа точек.СОЗДАНИЕ ВЕКТОРНОЙ МОДЕЛИ РАСТРАРезультатом работы алгоритмов предыдущих эта-пов является полностью размеченная триангуляция,которая содержит достаточную информацию для по-строения векторной модели растра. Дальнейшие дей-ствия, описанные в работе [3], проиллюстрированы, вчастности, на рис. 9.При создании векторного представления линейныхобъектов отслеживаются смежные линейные тре-угольники одного цвета с одновременным построени-ем скелетной линии. Линейные треугольники можноусловно разделить на три типа: «внутренние» (всеребра невидимые), «боковые» (одно ребро границы идва невидимых ребра), «оконечные» (одно невидимоеребро и два ребра границы).Алгоритм в процессе работы строит участки ске-летных линий, проходящих через середины невиди-мых ребер «боковых» треугольников и заканчиваю-щихся в точке пересечения медиан, если последнийтреугольник линии - «внутренний», либо в точке пе-ресечения ребер ограничений, если последний тре-угольник линии - «оконечный», либо на середине от-крытого ребра, если последний треугольник данногоучастка скелетной линии - «боковой». На рис. 9 этислучаи соответственно обозначены цифрами 1, 2, и 3.123Рис. 9После этого фильтруются некоторые погрешностискелетных линий, а оставшиеся их смежные участкисклеиваются. При этом распознается ситуация, когдастыкуются две распознанные линии разной толщины.Для создания векторных представлений площад-ных объектов строятся максимальные по включениюсвязные области, состоящие только из треугольников,не являющихся линейными. При этом строится внеш-няя граница площадного объекта.Нетрудно видеть, что трудоемкость каждого израссмотренных этапов - линейная относительно чис-ла треугольников.АППРОКСИМАЦИЯ ПЛОЩАДНЫХ ВЕКТОР-НЫХ ОБЪЕКТОВ КРИВЫМИ БЕЗЬЕВекторная модель растра, построенная рассмот-ренным выше алгоритмом, представляет собой набо-ры ломаных и многоугольников. Однако во многихзадачах иллюстративной графики и дизайна требуетсяпредставлять векторные объекты плавными кривыми,в качестве которых используются, как правило, кри-вые Безье [4]. При этом обычно ставится задача по-строения только площадных объектов (без распозна-вания линий на растре).Пусть на растре B алгоритмом 1 выделен наборграничных линий, каждая из которых является либозамкнутой, либо нет, и тогда она имеет начальную иконечную точки. Кроме того, для каждой линии зада-на ориентация и запомнены цвет области слева и цветобласти справа.Построение площадных объектов по граничнымлиниям можно выполнить без построения триангуля-ции. Для этого необходимо построить планарныйориентированный граф, в котором каждая граничнаялиния - ребро, а точки сочленения граничных линий -вершины графа. Кроме того, в каждой вершине ука-зывается порядок смежных с вершиной ребер по на-правлению часовой стрелки.По такому графу легко совершить обход по всемконтурам, ограничивающим одноцветные области,выделив таким образом площадные объекты.Теперь рассмотрим задачу аппроксимации гра-ничных линий кривыми. Каждую такую линию будемаппроксимировать следующим образом.Алгоритм 3. Аппроксимация граничных линийкривыми Безье.1. Формирование списка характерных узловыхточек.1.1. Если граничная линия незамкнута, то в спи-сок заносятся две концевые точки линии.1.2. В список заносятся точки в углах линии -местах стыковки двух отрезков, если онипо длине оба больше, чем некоторая за-данная величина ƒ (в пикселях).1.3. В список заносятся точки в середине техотрезков линии, которые являются локаль-ными экстремумами, если на этих отрезкахеще нет точек, занесенных в список.2. Цикл по списку характерных узловых точек(кроме концевых).2.1. Для k точек исходной граничной линиислева от узловой точки вычисляется на-клон аппроксимирующей прямой, прохо-дящей точно через узловую точку и всреднем вблизи k точек.2.2. Вычисляется наклон аналогичной аппрок-симирующей прямой для k точек справа.2.3. Если наклоны аппроксимирующих пря-мых слева и справа различаются более,чем на заданный угол ƒ, то запоминаютсяоба наклона для этой узловой точки.2.4. В противном случае вычисляется наклонаппроксимирующей прямой для k точекслева и для k точек справа и запоминает-ся общий наклон для этой узловой точки.3. Для концевых узловых точек (если они есть)вычисляется наклон аппроксимирующей пря-мой, проходящей точно через узловую точку ив среднем вблизи k соседних точек.4. Цикл по списку характерных узловых точек(рассматриваются по две соседних точки).4.1. Строится отрезок аппроксимирующей кри-вой Безье 3-й степени по двум узловымточкам и по наклонам слева и справа.4.2. Если максимальное отклонение кривой Бе-зье от соответствующего участка гранич-ной линии превышает заданную величинуƒ, то в середину этого участка вставляетсяновая узловая точка и вычисляется для неенаклон аппроксимирующей прямой для kточек слева и для k точек справа.Конец алгоритма.Так как некоторые характерные узловые точкиимеют координаты, кратные 0.5 пикселя, то все рас-четы следует вести на целочисленной сетке с шагом0.5 пикселя. Вычисление наклона аппроксимирующейпрямой, проходящей через узловую точку, можновести методом наименьших квадратов. Пусть пара-метрическое уравнение аппроксимирующей прямой всистеме координат с нулем в узловой точкеX (t) =at, Y(t) =bt. (1)Пусть также параметр t на соседних точках гра-ничной линии (на целочисленной сетке) имеет значе-ния 1, 2, …, k справа от узловой точки и, соответст-венно, -1, -2, …, - k слева от узловой точки. Еслиминимизировать сумму квадратов расстояний междуэтими точками (xi, yi) и соответствующими точкамипрямой (1) - (X(ti), Y(ti)), то получим следующиеоценки коэффициентов наклона a и b:i / 2i ia= ƒix ƒi , i / 2i ib=ƒiy ƒi. (2)Для построения отрезка кривой Безье 3-й степенипо двум узловым точкам и по наклонам слева и спра-ва необходимо от наклонов перейти к управляющимточкам. Следует учесть, что отрезок кривой Безье естьлокальный параметрический сплайн, заданный поли-номами X(t) и Y(t) третьей степени, где параметр tизменяется от 0 до 1. В работе [5] приведен способнормализации такого сплайна вдоль длины кривой,позволяющий рассчитать длины касательных в точкахпри t = 0 и t = 1 таким образом, чтобы кривая быланаиболее выпуклой.Проверку максимального отклонения отрезка кри-вой Безье от соответствующего участка граничнойлинии можно выполнить с помощью быстрого алго-ритма цифровой интерполяции параметрических по-линомов [6].Следует заметить, что некоторый отрезок кривойБезье может на самом деле оказаться прямолинейным,если линии наклона для двух соседних узловых точекнаправлены строго вдоль отрезка, их соединяющего.На рис. 10 показан процесс аппроксимации гранич-ных линий отрезками кривой Безье, а на рис. 11 -пример построения площадных объектов и аппрокси-мация граничных линий этих объектов.Рис. 10Рис. 11ВЕКТОРИЗАТОРПриложение, реализующее рассмотренные алго-ритмы, было создано как подключаемый модуль к по-пулярному оформительскому пакету Adobe Illustrator™. В данной технологии основной пакет программпринято называть приложением-хостом.Модуль векторизации использует функции для за-грузки растра, обращения к пикселям растра, опреде-ления расположения растра в рабочей обрасти, а так-же функции создания векторных объектов, предос-тавляемые приложением-хостом.Интерфейс задания параметров векторизации изо-бражен на рис. 12, на котором показана настройка па-раметров построения триангулированной модели рас-тра. Кроме того, в приложении имеется возможностьзадания количества цветов на растре (после обработкирастра для уменьшения на нем цветов), параметровпостроения кривых Безье.Рис. 12На рис. 13 показан пример обработки рассмотрен-ными алгоритмами одноцветного растрового рисунка.Слева направо - исходный растр, векторизованноеизображение с использованием только площадныхобъектов, изображение с использованием как линей-ных, так и площадных объектов, изображение для де-монстрации созданных векторных объектов.Рис. 13ЗАКЛЮЧЕНИЕРассмотренные в работе алгоритмы являютсядальнейшим усовершенствованием методов, предло-женных в работе [3]. Эти алгоритмы позволяют про-изводить векторизацию многоцветных растров с клас-сификацией выделенных из изображения объектов налинейные и площадные, достигая при этом высокойточности аппроксимации объектов. Алгоритмы могутфункционировать в полностью автоматическом ре-жиме, требуя задания лишь небольшого числа понят-ных пользователю параметров. Их трудоемкость вбольшинстве случаев линейная.

Скачать электронную версию публикации