Михаил Бессмельцев с коллегой разработал новые алгоритмы для векторизации графики

Слева направо: оригинал, оснащённое поле (frame field) и окончательный результат. На базе зашумлённого растрового изображение в оттенках серого вычисляется оснащённое поле, выровненное по линиям картинки. На острые углы типа X- и T-пересечений накладываются векторы по обоим направлениям. Затем из этого поля извлекается топология чертежа — и производится окончательная генерация векторных кривых

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

Первые алгоритмы векторизации изображений появились в начале 1990-х годов и
использовались в инструментах для редактирования векторной графики, таких как Adobe Illustrator (Live Trace), CorelDRAW (PowerTRACE) и Inkscape. Несмотря на их широкое внедрение в промышленности, эти алгоритмы до сих пор страдают от серьёзных недостатков и находятся в активной разработке. В нескольких индустриях, где векторизация крайне необходима, включая традиционную анимацию и инженерное проектирование, она часто выполняется вручную. Дизайнеры кропотливо обводят отсканированное изображение с помощью инструментов рисования.

К сожалению, современные алгоритмы даже для чистых чертежей не позволяют точно векторизовать X- и T-пересечения, поэтому получаются векторные чертежи с неправильной связностью. Из-за этих проблем у дизайнеров зачастую возникают колебания, использовать ли инструменты автоматической векторизации. Их надёжность вызывает сомнения. Точнее, так было до сих пор, пока двое исследователей — Михаил Бессмельцев и Джастин Соломон — из лаборатории компьютерных наук и искусственного интеллекта (CSAIL) Массачусетского технологического института не адаптировали известные математические алгоритмы для векторизации растровых рисунков.

Некорректная обработка стыков и пересечений линий — главный недостаток всех алгоритмов векторизации. Эти ошибки приводят к генерации неправильной топологии и нарушению связности. Новый метод векторизации основан на современных математических алгоритмах обработки оснащённых полей. Алгоритм специально адаптирован для устранения неоднозначности на стыках линий без потери качества.

а) Локальный подход к векторизации переходов, предложенный Норисом с коллегами в 2013 году, может привести к неправильным или неточным соединениям. b) Метод Фавро с коллегами (2016) может выдавать результат, существенно отклоняющийся от растрового оригинала. (с) Новый метод, предложенный Бессмельцевым и Соломоном, превосходит прежние разработки по векторизации

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

С учётом этих проблем существующих методов авторы научной работы предложили новый метод трассировки для изображений, в том числе со специальной обработкой T-образных и X-образных пересечений, где исходная информация может быть неоднозначно интерпретирована. Главное техническое нововведение заключается в использовании оснащённого поля с двумя парами векторов для каждой точки на плоскости.

В оснащённом поле хотя бы одно направление поле выровнено по исходной кривой, а около X- и T-пересечений оно выровнено по обоим направлениям

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

Примеры

(по клику открывается изображение высокого разрешения)

^[1]
Чувствительность инструмента к небольшим изменениям исходного изображения

^[2]

^[3]

^[4]
Метод не чувствителен к разрешению исходной картинки

^[5]
Векторизация качественно работает даже на сильно зашумлённом оригинале

Новый инструмент значительно облегчит жизнь дизайнеров и иллюстраторов: «По приблизительной оценке, он сэкономит от 20 до 30 минут при работе с автоматизированными инструментами [на каждом изображении]. Это существенный результат для аниматоров, которые обрабатывают много эскизов, — говорит ^[6] ведущий автор научной работы Михаил Бессмельцев, бывший сотрудник CSAIL, а ныне доцент (assistant professor) Монреальского университета. — Мы надеемся сделать автоматизированные инструменты векторизации более удобными для художников, которые заботятся о качестве своей работы».

Научная статья опубликована ^[7] 5 января 2018 года на сайте препринтов arXiv.org (вторая версия статьи ^[8] — 5 сентября 2018 года, arXiv:1801.01922v2). Она принята для публикации в научном журнале ACM Transactions on Graphics.

Автор: Анатолий Ализар

Источник ^[9]