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

[vitaly_l]

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

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

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

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

спасибо.
.

[Mirage]

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

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

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

[vitaly_l]

Cathmull-Rom

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

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

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

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

.

[Pavia]

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

[vitaly_l]

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

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

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, векторизация - это очень сложная задача. Чтобы это оценить достаточно запустить векторизацию растрового изображения в inkskape, например, и посмотреть на результаты.

[vitaly_l]

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

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

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


.

[Лекс Айрин]

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

Добавлено спустя 2 минуты 30 секунд:

Кстати наверное как-то можно их алгоритм выудить и посмотреть: что именно они там делают?

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

Добавлено спустя 25 минут 2 секунды:
Как я и думал... много лишних точек, рваные края фигур, пятна... в общем, легче нарисовать прямо в нем самом.

[Снег Север]

Как я и думал... много лишних точек, рваные края фигур, пятна... в общем, легче нарисовать прямо в нем самом.

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

[vitaly_l]

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

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

[Лекс Айрин]

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

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

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

К сожалению, в процессе редактирования изображения неизбежно возникнут искажения. Есть вероятность, что избавление от них будет более трудоемким, чем рисование векторного рисунка поверх растра.

[vitaly_l]

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

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

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

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

[vada]

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

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

[vitaly_l]

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

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

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

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

.

[vada]

Ну да. Осталось то всего-ничего - понять где кончается прямая, а начинается кривая. Мелочи А еще вдруг окажется что буковка P нарисована со сглаживанием и несколькими цветами и толщиной не в один пиксель
Нарисуйте карандашом букву, сосканируйте ее, и посмотрите что получилось с пикселами. Увидите много интересного!
С прямыми та же фигня.