Алгоритмы векторизации цветных растровых изображений на основе триангуляции и их реализация
 Скачать 151.42 Kb.
|
|
Алгоритмы векторизации цветных растровых изображений на основе триангуляции и их реализация Костюк Ю.Л., Кон А.Б., Новиков Ю.Л. Алгоритмы векторизации цветных растровых изображений на основе триангуляции и их реализация Костюк Юрий Леонидович, Кон Алексей Борисович, Новиков Юрий Леонидович. Алгоритмы векторизации цветных растровых изображений на основе триангуляции и их реализация // Вестн. Том. гос. ун-та. 2003. №280. URL: https://cyberleninka.ru/article /n/algoritmy-vektorizatsii-tsvetnyh-rastrovyh-izobrazheniy-na-osnove-triangulyatsii-i-ih- realizatsiya (дата обращения: 18.05.2020). [ Ссылка ] Для решения задачи векторизации многоцветного растрового изображения используются методы построения комплексной векторной модели на основе выделения граничных линий между областями различных цветов, построения по линиям триангуляции с ограничениями, распознавания векторных объектов по триангуляции. В статье предлагаются усовершенствованные алгоритмы выделения граничных линий, их аппроксимации прямолинейными отрезками и кривыми Безье, а также распознавания объектов. Описывается реализация предложенных алгоритмов в виде модуля, подключаемого к программе иллюстративной графики Adobe Illustrator™. Задача векторизации обычно решается для случая бинарного (двуцветного) растра [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 обозначены различные цвета. Ситуации и коды расположения различных цветов на соседних четырех пикселях растра G Воспользуемся определением граничной линии, взятым из [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. Структура растра G Аппроксимация граничных линий прямолинейными отрезками Полученные на предыдущем этапе граничные линии содержат чрезмерно большое число точек и выглядят ступенчатыми, поэтому их необходимо аппроксимировать. Рассмотрим аппроксимацию ломаными линиями, такими, что их отклонения от исходной граничной линии должны быть невелики, как правило, не более чем 1 пиксель. При этом также требуется, чтобы наиболее удаленные точки граничной линии отклонялись от аппроксимирующей ломаной по возможности на одинаковое расстояние по обеим сторонам. Приведенный в [3] способ аппроксимации может получить такой отрезок ломаной, что соответствующий участок исходной граничной линии располагается весь по одну его сторону. Поэтому рассмотрим еще один способ, лишенный указанного недостатка. Алгоритм 2. Аппроксимация граничных линий. 1. Выделение и вставка характерных узловых точек (рис. 3). |