Апроксимация рисованной линии, при переводе в вектор.

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 31.05.2017 12:11:45

Всем хорошего настроения!

Дано:
Рисованная линия. Она сканирована и переведена в массив точек. Массив точек получается большой. Хочется этот массив апроксимировать. Например был нарисован прямоугольник и в итоге после апроксимации - хочется получить всего 4-ре вершины. Алгоритм должен работать максимально быстро.

Интересует, математическое решение. Есть ли, в закромах Родины - математические алгоритмы позволяющие решить такую задачу? Или уже готовые решения, которые можно изучить, для образования?

И ещё, в геометрии есть хитрые линии, которые позволяют малыми силами рисовать волнистые линии (кривые Безье), включая окружности. Как для них вычисляют апроксимацию?

спасибо.
.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение Mirage » 31.05.2017 15:32:58

Если известно, что линии прямые, то берем уравнение y = kx + b, или любое другое представление и подставляя пару точек получаем прямую. Отрезок выделить из нее уже легко.
С более сложными линиями сложнее, что логично. Но принцип тот же - берется уравнение аппроксимирующей линии и подставляя в него точки находятся коэффициенты.
Готовое решение можно поискать в каком-нибудь OpenCV.

Хитрые линии называют сплайнами. Представляются полиномами разных степеней.
Например, кривая Безье 3-го порядка - это полином 3-й степени, коэффициенты которого получаются из начальных условий. Начальные условия для кривых Безье это значения функции в двух точках и значения производной в них же. Т.е. кривая Безье проходит через начальную и конечную точку, причем имеет в них заданные направления.
Если убрать направления и заменить их на еще два значения, то получится Cathmull-Rom сплайн, который проходит через все 4 указанные точки.

Аппроксимировать сплайнами можно, разбив кривую на кусочки и вычисляя коэффициенты. Тут вся соль в том, как разбивать.
Mirage
энтузиаст
 
Сообщения: 881
Зарегистрирован: 06.05.2005 20:29:07
Откуда: Russia

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 31.05.2017 19:19:45

Mirage писал(а):Cathmull-Rom

Спасибо!. Поискал, Cathmull-Rom - вроде есть разные формулы и можно понять как оно устроено.
Кривые всегда таким способом делаются или есть ещё варианты?

Mirage писал(а):Аппроксимировать сплайнами можно, разбив кривую на кусочки и вычисляя коэффициенты. Тут вся соль в том, как разбивать.

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

И соответственно буду благодарен за любую информацию.

.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение Pavia » 31.05.2017 20:29:21

1) Векторизация основы.
http://ocrai.narod.ru/vectory.html
2) Алгоритм оптимизации поллинии: Берём два соседних отрезка если срединная точка откланяется от прямой линии между двумя другими точками менее допуска, скажем 0٫5 пикселя то удаляем срединную точку.
3)Аппроксимация сплайнов делается через МНК. Вводим функцию ошибок, а после её минимизируем при помощи МНК.
4)Математика про сплайны описана много где. Да хотя бы здесь:
https://www.ibiblio.org/e-notes/Splines/Intro01.htm
или здесь
http://web.mit.edu/hyperbook/Patrikalak ... node2.html
Аватара пользователя
Pavia
постоялец
 
Сообщения: 290
Зарегистрирован: 07.01.2011 12:46:51

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 01.06.2017 21:20:38

Pavia писал(а):1) Векторизация основы.
http://ocrai.narod.ru/vectory.html

Забавно смотреть на картинки, где начало санирования волной начинается оттуда, откуда надо автору статьи.
Но общая идея понятна и принципы там разжёваны. Спасибо.

Pavia писал(а):4)Математика про сплайны описана много где. Да хотя бы здесь:
https://www.ibiblio.org/e-notes/Splines/Intro01.htm
или здесь
http://web.mit.edu/hyperbook/Patrikalak ... node2.html

Тут голая математика и её много - это очень тяжело, пока во всё вникнешь, математиком можно стать.

В общем решил остаться на формуле y = kx + b, т.к. она довольно понятна и я вижу как её применить в программе. Единственный минус, что её нужно очень часто вызывать. Поэтому мне казалось, что математики или программисты, давно уже изобрели: "чего-то другое". И ещё вот это Cathmull-Rom хочу довести до ума, т.к. оно рассчитано на математиков, а в программе, можно сделать немножечко по другому.

Тема, думаю всегда будет актуальна, так что, если у кого чего есть делитесь.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение Снег Север » 02.06.2017 07:03:46

vitaly_l, векторизация - это очень сложная задача. Чтобы это оценить достаточно запустить векторизацию растрового изображения в inkskape, например, и посмотреть на результаты.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2993
Зарегистрирован: 27.11.2007 16:14:47

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 02.06.2017 09:03:49

Снег Север писал(а):запустить векторизацию растрового изображения в inkskape, например, и посмотреть на результаты.

Там очень-очень долго идёт я знаю(несколько раз пользовал). очевидно там неправильный (в смысле медленный) алгоритм?
Кстати наверное как-то можно их алгоритм выудить и посмотреть: что именно они там делают?

Кроме того сейчас посмотрел, там не контур ищется, там каждая деталь рисунка превращается в векторный рисунок.
Это примерно в 50 раз сложнее задача чем моя. Мне нужно только контур апроксимировать из уже существующего массива точек.


.
Последний раз редактировалось vitaly_l 02.06.2017 09:42:39, всего редактировалось 1 раз.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение Лекс Айрин » 02.06.2017 09:35:50

vitaly_l, как раз в таких вещах лучше не спешить. Лично мне не понравилось то, что изображение сильно портится. Надо будет проверить на своей иконке -- она как раз идеально подходит для векторизации.

Добавлено спустя 2 минуты 30 секунд:
vitaly_l писал(а):Кстати наверное как-то можно их алгоритм выудить и посмотреть: что именно они там делают?


Легко, если знаешь С. Скачиваешь исходники с официального сайта...

Добавлено спустя 25 минут 2 секунды:
Как я и думал... много лишних точек, рваные края фигур, пятна... в общем, легче нарисовать прямо в нем самом.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение Снег Север » 02.06.2017 11:33:27

Лекс Айрин писал(а):Как я и думал... много лишних точек, рваные края фигур, пятна... в общем, легче нарисовать прямо в нем самом.
Конечно, проще, но если стоит другая задача - перевести в вектор не теряя значимых деталей, то по-другому не получится.
Аватара пользователя
Снег Север
долгожитель
 
Сообщения: 2993
Зарегистрирован: 27.11.2007 16:14:47

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 02.06.2017 11:41:51

Снег Север писал(а):Конечно, проще, но если стоит другая задача - перевести в вектор не теряя значимых деталей, то по-другому не получится.

Там(в инкскейпе) вообще непонятно, что именно делает их код, я только что изучал результат. Там как таковой - практически нет аппроксимации (в моём понимании). Даже если их алгоритму скормить прямую линию, она будет превращена в PATH из svg. И этот PATH - это не одна линия, а сложная фигура типа ажурной кляксы. Там совершенно другие задачи решаются. Они превращают растр, в мазки кисти как в живописи. Видимо это-какой-то эффект, который понравился программисту и он делает рисунок векторным, но там нет аппроксимации точек.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение Лекс Айрин » 02.06.2017 12:27:43

vitaly_l писал(а): Даже если их алгоритму скормить прямую линию, она будет превращена в PATH из svg. И этот PATH - это не одна линия, а сложная фигура типа ажурной кляксы.


Попробуй, посмотреть код за пунктом меню "упростить"

Снег Север писал(а): но если стоит другая задача - перевести в вектор не теряя значимых деталей, то по-другому не получится.


К сожалению, в процессе редактирования изображения неизбежно возникнут искажения. Есть вероятность, что избавление от них будет более трудоемким, чем рисование векторного рисунка поверх растра.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 02.06.2017 12:41:29

Лекс Айрин писал(а):Попробуй, посмотреть код за пунктом меню "упростить"

Да, вот этот код: "упростить" - решает ПОХОЖУЮ нужную задачу и делает это быстро. Например если, там, нарисовать замкнутую линию карандашом и потом 100 раз применить к ней функцию "упростить". Примерно на 55 разе - фигура примет оптимальные черты (и превратится в адекватное Безье) и начиная с 55 по 88 клик, по каждому клику: начнёт НЕ-МЕНЯЯСЬ внешне - упрощаться, исключительно за счёт сокращения точек, но при этом сохраняя формы линий. Вот мне нужно получить, то, что делает тот алгоритм с 55 по 88 клик, при использовании их функции "упрощение".

Их код сложно скачать с репозитория, там только примеры для юникс судо-кода (кажется), там чего-то в этом судо-кодо-редакторе нужно набрать и исходники скачаются, а для виндовз нет гиперссылки. Да и даже если бы была, найти там именно этот кусочек ОЧЕНЬ сложно.

Добавлено спустя 46 минут 27 секунд:
Чёртова математика: "Метод наименьших квадратов" - https://www.youtube.com/watch?v=nTbbAe0sBUk там тоже решает примерно эту задачу.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vada » 02.06.2017 14:07:31

"Метод наименьших квадратов"

Ну, таки, да. Именно это. Проще некуда, ващето.
Правда есть проблемы. Например, прямоугольник может получиться вообще не прямоугольником, а просто четырехугольником. Но это уже хорошо, ибо чаще всего это будет многоугольник. А с кривыми еще чудесатее. Приходилось как-то участвовать в оцифровке сканированных чертежей... Беда! Хорошо я вовремя свалил из конторы :)
Аватара пользователя
vada
энтузиаст
 
Сообщения: 691
Зарегистрирован: 14.02.2006 13:43:17

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vitaly_l » 02.06.2017 14:38:36

vada писал(а):прямоугольник может получиться вообще не прямоугольником, а просто четырехугольником. Но это уже хорошо, ибо чаще всего это будет многоугольник. А с кривыми еще чудесатее.

Да мне всего-то нужно, например, если на канвасе сделать: moveTo(1,1); lineTo(33, 44);, толщиной 1 пиксель, то нарисуется прямая. Теперь я например, её отсканировал. Получилось "много точек" распределённых по "пиксельной решётке". Соответственно линия, там не совсем прямая... И вот это "много точек", мне нужно обратно превратить в две координаты. Вот ещё так можно описать "ТЗ".

Но это с прямыми.

А например, если нарисована буква Р, то в итоге должно получиться три точки и из них получаются два отрезка. Один из отрезков будет Cathmull-Rom (чёртов Безье). Это тогда получится идеальное окончание - аппроксимации. Всё это уже по 1000000 раз решалось.

.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: Апроксимация рисованной линии, при переводе в вектор.

Сообщение vada » 02.06.2017 17:40:32

Ну да. Осталось то всего-ничего - понять где кончается прямая, а начинается кривая. Мелочи :) А еще вдруг окажется что буковка P нарисована со сглаживанием и несколькими цветами и толщиной не в один пиксель :)
Нарисуйте карандашом букву, сосканируйте ее, и посмотрите что получилось с пикселами. Увидите много интересного! :)
С прямыми та же фигня. :wink:
Аватара пользователя
vada
энтузиаст
 
Сообщения: 691
Зарегистрирован: 14.02.2006 13:43:17

След.

Вернуться в Общее

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Рейтинг@Mail.ru