Triangulation-based vectorization: false branch removal and junction processing .pdf Данная статья является продолжением работы [1]. Предлагаются две модификации к алгоритму векторизации на основе триангуляции [2,3]. Первая из них позволяет устранять древовидные паразитные ответвления на этапе обработки триангуляции, до построения векторной модели. При помощи второй модификации получаются более корректные векторные модели пересечений нескольких линий за счёт того, что в скелете могут появляться вершины степени 4 и выше. Представлены соответствующие алгоритмы и проиллюстрированы результаты их применения.1. Алгоритм удаления ложных ответвленийПроблема паразитных ответвлений присуща не только рассматриваемому алгоритму векторизации [4, 5]. Обычно она решается с помощью эвристических процедур постобработки. При векторизации на основе триангуляции паразитные ответвления появляются там, где все три вершины треугольника лежат на одной стороне векторизуемого линейного объекта. Данные явления более характерны для «толстых» линейных объектов. На конфигурациях, подобных изображённой на рис. 1, образуются древовидные паразитные ответвления, снижающие качество векторной модели.Для данного примера, с точки зрения теории графов, каждое ответвление является деревом. На практике это выполняется в подавляющем большинстве случаев.При векторизации на основе триангуляции существует строгое соответствие между звеньями скелета и треугольниками. Описываемый алгоритм выделяет группы треугольников, являющиеся причиной возникновения паразитных ответвлений. Будем называть треугольники, закрашенные цветом объекта, «чёрными», а цветом фона - «белыми».Сформулируем признак паразитного ответвления. Группа смежных чёрных треугольников Ть Т2,...,Тк считается паразитным ответвлением, если она удовлетворяет следующим условиям:1..1..Граф смежности треугольников этой группы является деревом.2..Среди треугольников есть ровно один треугольник Тр, смежный с некоторым чёрным треугольником, не принадлежащим данной группе (обозначим его Т*).3..Отношение квадрата длины ребра m, разделяющего треугольники Тр и Т*, к сумме площадей треугольников Ть Т2,.. .,ТК превышает порог s (рис. 2):Ключевым моментом является то, что в качестве потенциальных паразитных ответвлений рассматриваются только древовидные конфигурации. Для этого случая можно получить эффективные алгоритмы.Для произвольного чёрного треугольника T обозначим сумму площадей треугольников, лежащих по другую сторону его i-го (i = 1,...,3) ребра через F(T, i).Для случая А верны следующие равенства:F(T0, 1) = F(T0, 3) = 0, F(T0, 2) = S(T) + + S(T3) + S(T4),где S(T) - площадь треугольника. Для конфигурации Б F(T0, 3) = 0, а величины F(T0, 1) и F(T0, 2) не могут быть посчитаны, так как имеется цикл. В общем случае для вычисления F(T, i) достаточно следующих двух тривиальных правил.Правило 1. Если по другую сторону i-го ребра треугольника T нет чёрного треугольника (т.е. есть белый либо это граница триангуляции), то F(T, i) = 0.Правило 2. Пусть есть два соседних чёрных треугольника TA и TB. Пусть i-е ребро треугольника TA смежно треугольнику TB. Пусть также j- иу'2-е рёбра треугольника TB не смежны треугольнику TA. Если известны F(TB, j) и F(TB, j2), то F(Ta, i) = F(Tb, j) + F(Tb, 72) + S(Tb).Рис. 3. Вычисление F(T,i)Алгоритм вычисления F(T, i) состоит в итеративном применении правил к треугольникам. Вычисления завершаются, когда правила нельзя применить ни к одному треугольнику. При реализации удобно использовать структуру данных «очередь». Поиск паразитных ответвлений сводится к перебору отношений F(T, i) к квадратам длин соответствующих рёбер.Не все треугольники паразитных ответвлений должны быть перекрашены в белый цвет. Если к внутреннему треугольнику (треугольник называется внутренним, если у него 3 чёрных соседа) примыкает одно паразитное ответвление, то можно провести перестроение, после которого только часть треугольников будет перекрашена. Перестроение (рис. 4) затрагивает сам треугольник, и некоторые треугольники ответвления. За счёт этого форма объекта остаётся максимально близкой к исходной.Трудоёмкость алгоритма удаления паразитных ответвлений линейная относительно числа треугольников. В качестве порогового значения s обычно выбирается число от 4 до 8 (рис. 5).2. Модификация алгоритма построения скелетной линииСкелет изображения, полученный при помощи алгоритма, описанного в [3], обладает серьёзным недостатком. В нём не могут существовать вершины степени выше 3. Пересечение двух линий вместо вершины степени 4 представляется, как две соединённые вершины степени 3 (рис. 6). Если в одной точке пересекаются три линии, то получится уже четыре вершины степени 3.Часто в месте сочленения нескольких линейных объектов находится группа смежных внутренних треугольников. Идея предлагаемого алгоритма состоит в том, чтобы выбрать единственную точку внутри области, образованную этими треугольниками, и соединить её со всеми ответвлениями. Пусть изначально все внутренние треугольники являются непомеченными.Алгоритм построения скелетных линий для внутренних треугольников следующий:Шаг 1. Найти очередной непомеченный внутренний треугольник. Если поиск закончился неудачей, то алгоритм завершает работу.Шаг 2. Найти группу связных внутренних треугольников, которая включает треугольник, найденный на предыдущем шаге. Область, состоящую из этих треугольников, обозначим R. Пометить все треугольники, входящие в R.Шаг 3. Пусть R является N-угольником. Каждая сторона соответствует линии, примыкающей к R. При помощи метода наименьших квадратов [6] получитьоценки направлений этих линий в виде векторов vi, v2vN . Обозначим также середины сторон R через Pb P2,..., PN. Прямую, проходящую через Р,- и параллельную vi, обозначим /; (i = 1,..., N).Шаг 4. Найти положение узловой точки.4.1.Найти два направления (v а, vb), близких (в смысле порогового значенияугла а) к противоположным. Если таких направлений не существует, то в качествеузловой точки берётся центр масс области R. Иначе считается, что эти два ответв-ления являются частями одной линии.4.2.Если в пункте 4.1 поиск успешен, то из оставшихся направлений ищутсядругие два (vc, vd ), близкие к противоположным. Если они найдены, то в качестве узловой точки берётся пересечение прямых PaPb и PcPd .4.3.Если же вторую пару направлений найти не удалось, то в качестве узловойточки берётся медианная из точек пересечений прямой PaРъ с прямыми /(i ФШаг 5. Соединить найденную узловую точку с точками P1, P2,..., PN. Перейти на шаг 1.Конец алгоритма.Трудоёмкость обработки каждого сочленения составляет O(N log N). На практике N редко бывает больше четырёх. Алгоритм корректно обрабатывает случаи, когда в месте сочленения лежит единственная группа смежных внутренних треугольников (рис. 7).Алгоритм триангуляции не гарантирует, что в месте пересечения линий будет единственная группа смежных внутренних треугольников. Если это не выполняется, то в получаемом скелете сложные сочленения будут разнесены на несколько простых. Обычно связность внутренних треугольников нарушается, когда линиипересекаются под малым углом (это, например, неизбежно, если число линий велико). Даже в таких случаях (рис. 8) применение данной версии алгоритма даёт результат не хуже, чем до модификации.Представленные алгоритмы позволяют, во-первых, находить более широкий класс паразитных ответвлений, чем в [1], и, во-вторых, более корректно обрабатывать сочленения нескольких линейных объектов. Алгоритмы достаточно эффективны и практически не влияют на время, затрачиваемое на векторизацию.

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