почти аппроксимация наборов точек

@mikmik2 · Регистрация: 15.08.2015

Студворк — интернет-сервис помощи студентам

Добрый день
Есть набор точек, x y
Нужно их аппроксимировать, но с тем учетом, что если нарисовать эти точки на графики, то получится не функция, а просто кривая, и одному значению х может соответствовать несколько Y.
Для примера - символ "омега".
Т.е. взяли символ, разбили его на несколько тысяч точек с небольшим "шумом" и нужно этот набор точек аппроксимировать и получить чуть меньший набор глаженных точек.

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

Какие есть алгоритмы для этого? Или нужно разбивать участок и аппроксимировать кусочками?

@Sindbad_M · 10.11.2019, 17:29

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

@mikmik2 · 10.11.2019, 17:39 **[ТС]**

Сообщение от Sindbad_M

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

В моем случае задача работать с почти случайным по форме профилем

@Excalibur921 · 10.11.2019, 19:56

Покажите фотку примерно что вход и что выход.
В общем тут “скелетизация алгоритм” “векторизация изображения” “аппроксимация”.
Также и из искусственного интеллекта, распознание и классификация элементов на изображении.

Сообщение от mikmik2

если это точки, образующие, например круг?

“Поиск окружностей на изображении”

Сообщение от mikmik2

Для примера - символ "омега".

Для примера хотим омегу из чернобелой фотки текстового символа.
1)скелетизация убирает все толстые линии оставляя сложную ломанную из кучи мелких отрезков.
2)Аппроксимация, заменяет кучу мелких отрезков ломанной на один отрезок.

@VTsaregorodtsev · 10.11.2019, 22:17

Сообщение от mikmik2

Есть набор точек, x y
Нужно их аппроксимировать

Любой алгоритм кластерного анализа. Например, k-means.
Можно взять и нейросетки типа SOINN/ESOINN.

Если надо "чуть меньший набор сглаженных точек" соединять между собой - то
- либо постобработка результатов кластерного анализа (строим по полученным точкам=ядрам кластеров минимальное остовное дерево),
- либо берём растущий нейронный газ (но там в итоге останутся избыточные рёбра между узлами графа),
- либо глазами смотрим на картинку и по итогам увиденного затем напускаем на данные самоорганизующуюся карту (нейросеть) Кохонена вручную выбранной топологии (замкнутая цепочка узлов=нейронов, разомкнутая цепочка, либо шкилет какой-то более сложной формы).

Это я написал для случая, если у Вас контур не в виде кривой однопиксельной толщины - а в виде длинной (возможно, замкнутой) изгибающейся полосы (возможно, неравномерной ширины) точек. При однопиксельном же контуре - что-то типа https://en.wikipedia.org/wiki/Active_contour_model

@u235 · 11.11.2019, 12:53

Я бы для начала преобразовал набор точек в ориентированный граф, т.е. упорядочил точки.
Дальше нашел бы производные в точках и нахождение кривых Безье для сегментов.

@mikmik2 · 12.11.2019, 00:06 **[ТС]**

вот пример

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

@u235 · 12.11.2019, 05:28

mikmik2, так не понятно, набор точек как-то упорядочен у вас или нет? Самопересечения возможны?

@mikmik2 · 12.11.2019, 06:00 **[ТС]**

Сообщение от u235

набор точек как-то упорядочен у вас или нет? Самопересечения возможны?

Набор я могу упорядочить в порядке "следования" точек - верхняя точка "первая", а правая - "последняя".
Самопересечения вроде как невозможны

@u235 · 12.11.2019, 07:51

mikmik2, тогда упрядочивайте, делайте натуральную параметризацию кривой. Т.е. находите зависимости X(s), Y(s), где s-параметр, длина дуги от стартовой точки. X(s), Y(s) - будут "хорошими" функциями, которые можно аппроксимировать, например, полиномами.

@mikmik2 · 21.11.2019, 21:14 **[ТС]**

Сообщение от u235

тогда упрядочивайте, делайте натуральную параметризацию кривой. Т.е. находите зависимости X(s), Y(s), где s-параметр, длина дуги от стартовой точки. X(s), Y(s) - будут "хорошими" функциями, которые можно аппроксимировать, например, полиномами.

Спасибо за ответ! Долго пытался въехать в параметризацию кривой)
На сколько я понял, в каждой от начала кривой нужно получить вектор, направленный в сторону конечной точки. Но как потом аппроксимировать полиномами этот набор векторов? Набор точек я еще понимаю как, а набор функций - уже нет

@u235 · 21.11.2019, 21:34

mikmik2, нет.
Есть упорядоченный набор точек, для каждой точки (кроме последней)считается dx, dy как разница координат текущей и следующей точки.
Зная dx, dy считается по Пифагору ds для точки (гипотенуза элементарного треугольничка). Далее из вектора ds считается кумулятивная сумма - s - длина кривой. Зависимости x(s), y(s) это и будет натуральная параметризация кривой.

@mikmik2 · 22.11.2019, 07:50 **[ТС]**

Как раз до этого момента примерно понятно что делать)
А дальше что? Есть у меня длина этой кривой, причем если набор точек был с шумом, то эта длина может быть заметно больше длины сглаженной кривой.
Что потом? Как этот набор поможет мне сгладить/аппроксимировать заданный набор точек?

@u235 · 22.11.2019, 08:08

а дальше полиномами/сплайнами аппроксимируйте зависимость x от s и y от s. s меняется от 0 в стартовой точке, до, допустим, s_end в конечной.
Затем для выбраных значений s (в скольких точках вам надо - не знаю) у вас будет аппроксимированная (расчет двух полиномов от s) точка x, y это и будут координаты сглаженой кривой. Насчет шума и несоответствия длин не волнуйтесь.

@mikmik2 · 22.11.2019, 10:07 **[ТС]**

Для каждой точки, начиная со первой до предпоследней я получил dx, dy и длину вектора ds. Dx, dy – это проекции на оси между соседними точками, а ds – длина участка до следующей точки. Все верно пока что?
Т.е. имеем набор
1. x1,y1, dx1, dy1, ds1
2. x2,y2, dx2, dy2, ds2
И т.д.
Сумма всех ds-ов равна длине моей ломаной и равна s_end. Для какой-то конкретной точки, заданной на интервале [0 … s_end] мы можем найти X и Y.
Т.е. теперь я могу можно изменить шаг точек и построить эту же ломанную, но с другим шагом. Но эта новая кривая не будет сглаженной, особенно если уменьшить шаг точек. Будет просто больше точек, но ломанная останется ломаной.
Вот как её сгладить я так и не понял. Как можно «сплайнами аппроксимировать зависимость x от s и y от s»? Нужно как-то усреднить набор dx, dy ?

@Excalibur921 · 22.11.2019, 10:55

Берем 3 точки подряд, это два отрезка.
Если угол между отрезками меньше Порог1 или сумма длин этих отрезков меньше Порог2 то удаляем среднюю точку. Так будет разрежение точек близко лежащих на одной прямой и удаление сильно близко расположенных. Пару итераций всем точкам вот и аппроксимация.

@mikmik2 · 22.11.2019, 11:50 **[ТС]**

u235, я кажется наконец понял
Если построить график х(s), то это будет уже функция, где одному х соответствует один s. Эту зависимость и нужно аппроксимировать и по ней получить обратно кривую с любым шагом. Так?

@u235 · 22.11.2019, 13:35

нет, наоборот, каждому s соответствует только одно значение x (то же самое для y). Т.е. x(s) - функция. Ее и надо аппроксимировать. В остальном все так.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

почти аппроксимация наборов точек

Решение

Решение

@mikmik2 0 / 0 / 0 Регистрация: 15.08.2015 Сообщений: 23

	почти аппроксимация наборов точек 10.11.2019, 14:47. Показов 3381. Ответов 17 Метки нет (Все метки) Добрый день Есть набор точек, x y Нужно их аппроксимировать, но с тем учетом, что если нарисовать эти точки на графики, то получится не функция, а просто кривая, и одному значению х может соответствовать несколько Y. Для примера - символ "омега". Т.е. взяли символ, разбили его на несколько тысяч точек с небольшим "шумом" и нужно этот набор точек аппроксимировать и получить чуть меньший набор глаженных точек. Если бы это были точки, которые лежат на графике - проблем бы не было, алгоритмов аппроксимаций на этот случай море. А как быть, если это точки, образующие, например круг? Какие есть алгоритмы для этого? Или нужно разбивать участок и аппроксимировать кусочками? 0

@Sindbad_M 485 / 411 / 126 Регистрация: 23.05.2016 Сообщений: 1,653
	10.11.2019, 17:29
	окружность и многие другие загогулины хорошо описываются функцией в полярных координатах. 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	11.11.2019, 12:53
	Я бы для начала преобразовал набор точек в ориентированный граф, т.е. упорядочил точки. Дальше нашел бы производные в точках и нахождение кривых Безье для сегментов. 0

@mikmik2 0 / 0 / 0 Регистрация: 15.08.2015 Сообщений: 23
	12.11.2019, 00:06 [ТС]
	вот пример Но форма может быть в общем-то любой. Требуется сгладить этот профиль, так как это набор точек, полученных как результат измерения некой шайтан-машины. Нужно получить из этого набор точек, напоминающих гладкую "кривую" от текущего набора чтобы повысить точность в наборе точек Невозможно развернуть её так, чтобы можно было получить из этого вид графика функции (в классическом её варианте) 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	12.11.2019, 05:28
	mikmik2, так не понятно, набор точек как-то упорядочен у вас или нет? Самопересечения возможны? 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	12.11.2019, 07:51
	Сообщение было отмечено mikmik2 как решение Решение mikmik2, тогда упрядочивайте, делайте натуральную параметризацию кривой. Т.е. находите зависимости X(s), Y(s), где s-параметр, длина дуги от стартовой точки. X(s), Y(s) - будут "хорошими" функциями, которые можно аппроксимировать, например, полиномами. 1

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	21.11.2019, 21:34
	mikmik2, нет. Есть упорядоченный набор точек, для каждой точки (кроме последней)считается dx, dy как разница координат текущей и следующей точки. Зная dx, dy считается по Пифагору ds для точки (гипотенуза элементарного треугольничка). Далее из вектора ds считается кумулятивная сумма - s - длина кривой. Зависимости x(s), y(s) это и будет натуральная параметризация кривой. 1

@mikmik2 0 / 0 / 0 Регистрация: 15.08.2015 Сообщений: 23
	22.11.2019, 07:50 [ТС]
	Как раз до этого момента примерно понятно что делать) А дальше что? Есть у меня длина этой кривой, причем если набор точек был с шумом, то эта длина может быть заметно больше длины сглаженной кривой. Что потом? Как этот набор поможет мне сгладить/аппроксимировать заданный набор точек? 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	22.11.2019, 08:08
	а дальше полиномами/сплайнами аппроксимируйте зависимость x от s и y от s. s меняется от 0 в стартовой точке, до, допустим, s_end в конечной. Затем для выбраных значений s (в скольких точках вам надо - не знаю) у вас будет аппроксимированная (расчет двух полиномов от s) точка x, y это и будут координаты сглаженой кривой. Насчет шума и несоответствия длин не волнуйтесь. 0

@mikmik2 0 / 0 / 0 Регистрация: 15.08.2015 Сообщений: 23
	22.11.2019, 10:07 [ТС]
	Для каждой точки, начиная со первой до предпоследней я получил dx, dy и длину вектора ds. Dx, dy – это проекции на оси между соседними точками, а ds – длина участка до следующей точки. Все верно пока что? Т.е. имеем набор 1. x1,y1, dx1, dy1, ds1 2. x2,y2, dx2, dy2, ds2 И т.д. Сумма всех ds-ов равна длине моей ломаной и равна s_end. Для какой-то конкретной точки, заданной на интервале [0 … s_end] мы можем найти X и Y. Т.е. теперь я могу можно изменить шаг точек и построить эту же ломанную, но с другим шагом. Но эта новая кривая не будет сглаженной, особенно если уменьшить шаг точек. Будет просто больше точек, но ломанная останется ломаной. Вот как её сгладить я так и не понял. Как можно «сплайнами аппроксимировать зависимость x от s и y от s»? Нужно как-то усреднить набор dx, dy ? 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	22.11.2019, 10:55
	Берем 3 точки подряд, это два отрезка. Если угол между отрезками меньше Порог1 или сумма длин этих отрезков меньше Порог2 то удаляем среднюю точку. Так будет разрежение точек близко лежащих на одной прямой и удаление сильно близко расположенных. Пару итераций всем точкам вот и аппроксимация. 0

@mikmik2 0 / 0 / 0 Регистрация: 15.08.2015 Сообщений: 23
	22.11.2019, 11:50 [ТС]
	u235, я кажется наконец понял Если построить график х(s), то это будет уже функция, где одному х соответствует один s. Эту зависимость и нужно аппроксимировать и по ней получить обратно кривую с любым шагом. Так? 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	22.11.2019, 13:35
	Сообщение было отмечено mikmik2 как решение Решение нет, наоборот, каждому s соответствует только одно значение x (то же самое для y). Т.е. x(s) - функция. Ее и надо аппроксимировать. В остальном все так. 1