Слева направо: оригинал, оснащённое поле (frame field) и окончательный результат. На базе зашумлённого растрового изображение в оттенках серого вычисляется оснащённое поле, выровненное по линиям картинки. На острые углы типа X- и T-пересечений накладываются векторы по обоим направлениям. Затем из этого поля извлекается топология чертежа — и производится окончательная генерация векторных кривых
Векторизация изображений — основополагающий компонент рабочего процесса в графическом дизайне, технике и компьютерной анимации. Она преобразует черновые рисунки художников и дизайнеров в гладкие кривые, необходимые для редактирования.
Первые алгоритмы векторизации изображений появились в начале 1990-х годов и
использовались в инструментах для редактирования векторной графики, таких как Adobe Illustrator (Live Trace), CorelDRAW (PowerTRACE) и Inkscape. Несмотря на их широкое внедрение в промышленности, эти алгоритмы до сих пор страдают от серьёзных недостатков и находятся в активной разработке. В нескольких индустриях, где векторизация крайне необходима, включая традиционную анимацию и инженерное проектирование, она часто выполняется вручную. Дизайнеры кропотливо обводят отсканированное изображение с помощью инструментов рисования.
К сожалению, современные алгоритмы даже для чистых чертежей не позволяют точно векторизовать X- и T-пересечения, поэтому получаются векторные чертежи с неправильной связностью. Из-за этих проблем у дизайнеров зачастую возникают колебания, использовать ли инструменты автоматической векторизации. Их надёжность вызывает сомнения. Точнее, так было до сих пор, пока двое исследователей — Михаил Бессмельцев и Джастин Соломон — из лаборатории компьютерных наук и искусственного интеллекта (CSAIL) Массачусетского технологического института не адаптировали известные математические алгоритмы для векторизации растровых рисунков.
Некорректная обработка стыков и пересечений линий — главный недостаток всех алгоритмов векторизации. Эти ошибки приводят к генерации неправильной топологии и нарушению связности. Новый метод векторизации основан на современных математических алгоритмах обработки оснащённых полей. Алгоритм специально адаптирован для устранения неоднозначности на стыках линий без потери качества.
а) Локальный подход к векторизации переходов, предложенный Норисом с коллегами в 2013 году, может привести к неправильным или неточным соединениям. b) Метод Фавро с коллегами (2016) может выдавать результат, существенно отклоняющийся от растрового оригинала. (с) Новый метод, предложенный Бессмельцевым и Соломоном, превосходит прежние разработки по векторизации
Проблема усугубляется зашумлённостью оригинальной растровой графики, которая остаётся после сканирования бумажного оригинала. Нарушение связности не позволяет применить инструменты автоматической заливки/расцветки, то есть такое векторные рисунки всё равно приходится доводить до ума вручную.
С учётом этих проблем существующих методов авторы научной работы предложили новый метод трассировки для изображений, в том числе со специальной обработкой T-образных и X-образных пересечений, где исходная информация может быть неоднозначно интерпретирована. Главное техническое нововведение заключается в использовании оснащённого поля с двумя парами векторов для каждой точки на плоскости.
В оснащённом поле хотя бы одно направление поле выровнено по исходной кривой, а около X- и T-пересечений оно выровнено по обоим направлениям
Авторы научной работы говорят, что оснащённые поля логично и естественно подходят для отслеживания ориентации кривых в таких резких переходах, но по какой-то причине они никогда не применялись для векторизации изображений. Показанные результаты демонстрируют, что качество векторизации значительно выше, чем у предыдущих методов. Даже на сильно зашумлённых оригиналах геометрия кривых не теряется и совпадает с оригинальными начертаниями.
Примеры
(по клику открывается изображение высокого разрешения)
Чувствительность инструмента к небольшим изменениям исходного изображения
Метод не чувствителен к разрешению исходной картинки
Векторизация качественно работает даже на сильно зашумлённом оригинале
Новый инструмент значительно облегчит жизнь дизайнеров и иллюстраторов: «По приблизительной оценке, он сэкономит от 20 до 30 минут при работе с автоматизированными инструментами [на каждом изображении]. Это существенный результат для аниматоров, которые обрабатывают много эскизов, — говорит ведущий автор научной работы Михаил Бессмельцев, бывший сотрудник CSAIL, а ныне доцент (assistant professor) Монреальского университета. — Мы надеемся сделать автоматизированные инструменты векторизации более удобными для художников, которые заботятся о качестве своей работы».
Научная статья опубликована 5 января 2018 года на сайте препринтов arXiv.org (вторая версия статьи — 5 сентября 2018 года, arXiv:1801.01922v2). Она принята для публикации в научном журнале ACM Transactions on Graphics.
Комментарии (26)
vagran
11.09.2018 20:36Защищено ли оно патентами? Можно ли расчитывать на интеграцию этого алгоритма в open source продукты?
SidMeier
12.09.2018 09:09Если описание алгоритма есть в свободном доступе, то разве нельзя представить собственную открытую реализацию, естественно со ссылками? Я просто не представляю как патентовать идею. Патентуют вроде конкретные реализации.
middle
13.09.2018 09:16В США можно запатентовать алгоритм; в России — нет (хотя иногда алгоритмы патентуют как «способ»).
vassabi
11.09.2018 20:51глянул начало рекламного ролика.
Чем-то похоже на
Известное киноvassabi
11.09.2018 22:39+2о боже, я написал не в тот топик!
извините меня пожалуйста…
на самом деле это было сюда
по теме этого топика — я однажды принимал участие в команде, которая занималась небольшой векторизацией, это действительно огромная задача — респект тем, кто придумал что-то новое на этом поприще.
Moskus
11.09.2018 21:34+1В векторизации технических изображений есть еще одна проблема — идентификация прерывистых линий (разнообразных пунктиров) и выделение их топологии, как сплошных линий, а не отдельных сегментов.
dabar347
12.09.2018 07:40Для логического соединения прерывистых линий вполне можно использовать что-то роде Hough transform, я думаю.
amarao
12.09.2018 15:41И я бы сказал, что это главная проблема. Основное в рисунке — это движение (направление изгиба оси целого или части). Сама ось очень редко рисуется, но всегда подразумевается. Если отдельные линии начинают противоречить движению, это сильно портит рисунок. У хорошего художника движение может передаваться очень многими средствами (в т.ч. перпендикулярными линиями). Потеря его при растеризации сильно огрубляет и примитивизирует рисунок. И чем лучше рисунок, тем больше будет огрубление.
Но как найти ось, если она может быть построена из мнимых линий (например, даже негативным пространством)?springimport
12.09.2018 17:15Возникла идея нового формата с растровым фоном и векторным наложением. Вот это бы решило ту проблему.
Moskus
12.09.2018 20:57Вы говорите о противоположной задаче — не выделении «скрытой» топологии, а о буквальной передаче штрихов и линий, со всеми их свойствами.
amarao
12.09.2018 23:41Не буквальной, а символичной. Но да, я говорю про восстановление штрихов.
Смотрите. Штрих — набор запачканных областей бумаги, причём чаще всего с разрывами (из-за текстуры бумаги). Нас не интересуют границы запачканных областей. Нас даже не всегда волнует точная форма штриха. Вот что нас волнует — это:
1) Отделение одного штриха от другого (например, в случае с гривой — у нас большая линия шеи, поверх которой лежат штрихи гривы).
2) Определение истинного направления штриха (за вычетом погрешностей рук, грифеля и бумаги).
3) Определение направления проведения штриха (т.к. это важно для штриховки — может быть две группы штрихов, одни в одном направлении, другие в другом, и их лучше не путать).
Собственно, оцифровка (векторизация) линейного рисунка (или штриховки) подразумевает, как мне кажется, как человеку, занимающемуся рисованием, восстановления движений карандаша. Точка начала, точка конца, скорость движения (условно — относительная жирность линии), сила нажима (базовая жирность линии).
Имея на руках эти данные можно восстанавливать рисунок, более того, восстановленный рисунок будет богаче, чем просто вектор. Применение разных кистей позволит подобрать (художнику) наиболее приближенное по стилю/духу к бумажному рисунку.batman12345
14.09.2018 08:56В таком случае задача существенно шире и сложней. Ведь нужно учитывать и фактуру штриха. Малевать можно и карандашом и кистью и аэрографом и трафаретом…
Наверняка есть и другие нюансы.
amarao
12.09.2018 13:28Лошадь просто отличный пример малых, но существенных ошибок этого алгоритма.
1. Посмотрите на «подмордие». На рисунке — это тень. Там сильнее шртрихи. На векторе — странная штука снизу морды.
2. Шея на рисунке — ровная, с линиями гривы. На векторе — то ли булочка, то ли морщины.
3. Заднее копыто — потеряли овальность и форму. Выглядит как детская ошибка в рисунке.
4. Переднее копыто — потеряли несколько важных штрихов, считай, потеряли форму.
5. Самое левое копыто — криво взята форма, потеряли точную линию, которая показывала примыкание копыта к ноге.
На первой картинке (верхушка шляпы) видно, что вектор потерял правильное движение — вместо S-образной кривой там образовалась C-образная и не туда.
Т.е. в качестве подпорки — да, в качестве нормального инструмента — нет.
max1muz
12.09.2018 19:07Постоянно требуется перегонять растровые картинки в вектор. Юзаю Vector Magic, очень нравится. Встроенный трассировщик корела и рядом не стоял.
sumanai
12.09.2018 20:31Ещё бы они градиенты научились распознавать, цены бы им не было.
Gryphon88
12.09.2018 20:53Поясните, пожалуйста, что Вы имеете под «распознаванием градиентов».
sumanai
12.09.2018 21:17Пробовали скармливать градиентное изображение векторизатору? Сейчас скачаю Inkscape и покажу, а то он со скоростью 64кб/с качается.
Gryphon88
13.09.2018 12:27Никогда не сталкивался с задачей векторизации, просто не нужно было, поэтому прошу объяснить, что такое «распознавание градиента». С моего дивана, градиент или есть, или его нет. Если есть, то используем какой-то из способов его обнаружения (gradient vector flow, анизотропную диффузию, змейки...) или вообще адаптивную бинаризацию, если нет, то используем скелетонизацию. Линия разбита — опять же змейки, главное, коэффициент подобрать. Не нравится скелет — спрямляем-сглаживаем его, методы тоже есть.
sumanai
13.09.2018 18:44Никогда не сталкивался с задачей векторизации
А, ну тогда ясно. Просто все испробованные мною программы выдавали результат типа
Telomer
14.09.2018 12:57Алгоритмы векторизации вплотную подходят к границам возможностей математического/геометрического подхода. Читая комментарии выше, замечаю, что с точки зрения компьютера рисунок векторизуется вполне точно, но с точки зрения художника всё не совсем хорошо. Был в моей практике другой случай, когда нужно было оцифровать простой растительный рисунок, но, вот беда, низкого разрешения, для программы банально слишком мало информации, приходилось угадывать и от себя дорисовывать, что там было на самом деле. Очевидно, чтобы достичь лучшего результата не обойтись без интеллекта — натурального или искусственного.
Harrix
Как понимаю, попробовать вживую это пока нельзя?
SilentPrayerCG
Я бы, честно говоря, увидивился если бы можно было.
Моя текущая занятость, кстати, требует довольно часто векторизировать всякую фигню. Интересно было бы посмотреть на алгоритм, отличный от стандартного.
Gryphon88
Пошукал, ни supporting materials на гитхабе, ни на сайте MIT. Надеюсь, на момент публикации код будет (см. страницу Justin Solomon на сайте MITа).