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

[vitaly_l]

кривизна кривой безье не позволяет точно описать букву р. Тут как минимум надо 3 штуки этих кривых. Хотя если точностью пожертвовать то можно и одну оставить.

Без разницы 1 , 2 или 3, важно чтоб не 111 - мне нужно умом понять принцип и систему работы формул

Добавлено спустя 10 минут 38 секунд:
Можно изменить задачу. Например есть три объекта, в виде массивов точек толщиной 1 пиксель.
1) прямая линия под углом примерно 33 градуса из 111 точек. Нужно аппроксимировать до 2 точек. (это легче всего и на 99% понятно как)
2) дуга типа: U - из 111 точек. Нужно аппроксимировать до 2 или 3 точек. (это много сложнее, и понятно только на 50%)
3) синусоида типа: S - из 111 точек. Нужно аппроксимировать до 2 или 5 точек. ( это на 50% п.2 )
Во втором и третьем ТЗ имеются ввиду Cathmull-Rom сплайны, и/или Безье.

[Лекс Айрин]

Если подходить тупо, то для прямой можно просто ввести зону отклонения (допустим, 3-4 пикселя в сторону). Все, что попадает в эту зону удаляется... Но добавляется поиск начальной/конечной точки. Специалисты, конечно, найдут способ поинтереснее.

[Pavia]

vitaly_l
Да там всё просто. Вначале строим скелет изображения. Это когда соседние пиксели удаляются, так что-бы линии стали толщиной в один пиксель. Я бы для этого взял за основу алгоритм поиска Non-Maximum Suppression предложенный Canny в 1976 году см предыдущий слайд. Хотя тут есть варианты.

Далее строится граф. Структура которая указывает какая точка с какой связана в нашем случае соприкасается.
Далее ищем точки у которых всего по 1 соседу. Затем от них переходим по узлам графа. И заменяем точки линиями.
Как ссылку я уже приводил.
Далее работаем с отрезками. Аппроксимируем их кривой Безье. Берём строго по 4 отрезка.*
Система уравнений описывающих Безье известна. Подставляем наши точки в эти уравнения. Получаем систему. Решаем систему уравнений да Хотя-бы методом гаусса.

Далее соседние кривые Безье можно объединить. Применяем инверсию мышления. Формулу как разбить одну кривую Безье на две других есть в ссылках указанных мной выше.
Соответственно ничего не мешает повторить эти математические операции в обратном порядке, конечно тут будет парочка условий из-за которых объединение не возможно. Но они элементарные.

* Если брать не по 4 отрезка, а больше то у нас будет переопределённая система, если меньше то не до определённая.
Соответственно тут решается через МНК. Как описано в книге:
Каханер,_Моулер,_Наш.-Численные_методы_и_программное_обеспечение-Мир(1998)

Вводиться функция ошибок - она на самом деле вытекает из системы уравнений. Далее транспонируем матрицу Вандерморда и перемножаем саму на себя. Получаем квадратную матрицу которую мы умеем решать по Гаусу. Затем результат обратно умножается. Это и будет наименьшая ошибка по квадратом. Почему это так смотри в книге.

Для тех кто не догадался матрица Вандерморда в точности совпадает с системой уравнений полученной из кривой Безье.

PS. Интернет у меня закончился, так что без подробностей.

[vitaly_l]

Я бы для этого взял за основу алгоритм поиска Non-Maximum Suppression предложенный Canny в 1976 году см предыдущий слайд. Хотя тут есть варианты.

Тут много есть вариантов, и всё зависит от желаемого результата в конце, т.к. они все дают разные результаты, т.к. например Оператор Собеля - судя по одинаковой тестовой картинке даёт более яркий визуальный вариант чем Кэнни. Вот можно сравнить:
https://ru.wikipedia.org/wiki/%D0%9E%D0 ... 0%BD%D0%B8
https://ru.wikipedia.org/wiki/%D0%9E%D0 ... 0%BB%D1%8F

Но мне ненужно строить скелет изображения.

Берём строго по 4 отрезка

У Безье есть: Кубические кривые (Кривые высших степеней), - это те кривые, которые мне нужны. Но вот, есть же ещё: Cathmull-Rom они какие-то немножечко другие. Но они насколько я понимаю, в итоге делают тоже самое? А именно, рисуют кривую между: Р1 и Р2 из: Р0, Р1, Р2, Р3, а Р0, Р3 - в обоих случаях управляющие? Или у Cathmull-Rom они играют роль продолжения линии(ребра), точки которой влияют на кривизну соседнего "ребра"?

И там разница только в методе вычислений? Или ещё есть какие-то различия или нюансы?

[Pavia]

Все сплайны деляться на 2 вида.
1) Классические функции.
2) Сглаживающие функции.

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

Вторый отличаются от 1 тем что они имет вид полинома в своём простанствен, а при переводи в параметрический вид

x(t)=f1(t), y(t)=f2(t) они уже не будут иметь вид полиномов, а примут сложный вид.

Теперь. О том на каких сплайнах остановиться. Точность у чисел с плавающей точкой очень маленькие.
У Real хватает только на полином 7 степени. Поэтому чем ниже у слпайна степень тем лучше.

Поэтому оставливаемся на BSpline 3-порядка.

Чем кривые отличаются от сплайнов?

Б-Слайн отличается от кривой Безье тем что проходит через 4 опорных точки. Когда как сам Безье разлечал 2 точки как базовые и 2 как управляющие.

На самом деле эти управляющее точки не что иноее как производные от опорных.

Поэтому отличия там чисто художественные. C CorelDraw работали? Управляющими точками проще менять кривизну. А бозовыми проще подгонять линии по месту. Но всегла одни можно преобразовать в другие.

У Cathmull-Rom P0,P1,P2,P4 это все 4 опорные точки. На кривизну рёбер влияет полином которым их сглаживаю.
По большей части полином всюду стандартный. Конечно бывают что там делают не стандартный, но они не нашли практического применения.
Ф.Хилл OpenGL. Программирование компьютерной графики Глава 11.6.3-11.6.4

Вернёмся к Безье.
Bezier(t)=(1-t)^3*P0+3*(1-t)^2*t*P1+3*(1-t)*t^2*P2+t^3*P3
Расскроем скобки и перегруппируем t к вид s0+s1*t+s2*t^2+s3*t^3
(1-t)^2=1-2*t+t^2
(1-t)^3=1-2*t+t^2-t+2*t^2-t^3=1-3*t+3*t^2-t^3
3*(1-t)^2*t=3*t-6*t^2+3*t^3
3*(1-t)*t^2=3*t^2-3*t^3
Bezier(t)=
P0*(1-3*t+3*t^2-t^3)+
P1*(3*t-6*t^2+3*t^3)+
P2*(3*t^2-3*t^3)+
P3*(t^3)=
P0+(-3*P0+3*P1)*t+(3*P0-6*P1+3*P2)*t^2+(-P0+3*P1-3*P2+P3)*t^3

Теперь сплал проходит через 4 опорных точки S0, S1, S2, S3.

[vitaly_l]

Ф.Хилл OpenGL. Программирование компьютерной графики Глава 11.6.3-11.6.4

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

Теперь сплал проходит через 4 опорных точки S0, S1, S2, S3.

Corel я пользовал очень давно и уже не помню, что там к чему. Я давно уже перешёл на опенсорс, т.к. это позволяет сохранять законность. Но очень хорошо понял о чём спич, т.к. владею на 55-88% всеми 3D-пакетами, эти: базовые и управляющие точки, в них тоже есть.

Я тут уже начал экспериментировать с кодом, в общем всё хорошо.
Как работает Безье - разобрался и теперь даже могу свою собственную формулу придумать.
Спасибо большое за разъяснения! Хорошего дня и всегда хорошего настроения - всем!!!

.