Сглаживание кривой

@spirart · Регистрация: 05.12.2011

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

Привет!

Совсем замучился с проблемой )) Помогите, пожалуйста!

Есть двумерный очень большой массив точек - координаты (x,y) мест. В целом они идут по "красивой" кривой, но иногда возникают "клубки" (как на картинке - черным цветом).

Я не понимаю, какой алгоритм применять для того, чтобы "клубки" убрать и просто продолжить мою кривую (на картинке - красная линия).

Очень надеюсь на подсказку.

@Shamil1 · 25.11.2015, 22:05

А как Вы отличаете "клубки" от неклубоков? Например, почему Вы провели красную линию сквозь "клубки" по кратчайшему расстоянию, а не "горбиком"?

@gerMankle · 25.11.2015, 22:31

Хотел предложить метод главных компонент (гусеницу), но понял, что вроде не по теме ))

@spirart · 25.11.2015, 22:33 **[ТС]**

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

@Shamil1 · 25.11.2015, 23:27

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

Важно, чтобы не было запутанностей линий.

То есть, Вы хотите, чтобы каждому x соответсвовал один y? или кривая может идти, например, вверх или даже по спирали (но без завихрений)?

@spirart · 26.11.2015, 07:32 **[ТС]**

Shamil1, идеальный вариант:

каждому x соответсвовал один y

Или хотя бы что-то очень похожее на гладкую кривую.

@ProgJ · 26.11.2015, 08:52

мне кажется, что в вашем случае можно просто исключить точки в которых производная (угол наклона) значительно отличается от значения производной в предыдущей неисключенной точке

@Igor3D · 26.11.2015, 11:51

Ну вообще-то производная - тангенс угла наклона. Если нарисовать график угла вычисляя его как
atan2(delta_y, delta_x), то получится какая-то гладкая кривая на которой будут "всплески". На ней уже найти ровные участки достаточной длины (параметр) и соединить их. Впрочем это велосипед, так, по-быстрому. Задача фильтра ВЧ прекрасно известна, надо читать.

@spirart · 26.11.2015, 13:16 **[ТС]**

Igor3D, я не совсем понял, если честно, первую часть.
Рисую график, строя линии между точками, ок. Посчитал atan2 между смежными линиями, ок. Что потом с этим значением делать? Как его использовать?

@Igor3D · 26.11.2015, 14:19

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

Igor3D, я не совсем понял, если честно, первую часть.
Рисую график, строя линии между точками, ок. Посчитал atan2 между смежными линиями, ок. Что потом с этим значением делать? Как его использовать?

Между смежными - не стоит, просто atan2 каждого отрезка. Вы этот график углов нарисуйте - и сразу мысли появятся

Ну хотя бы: есть текущий вектор скорости, добавляем к нему следующий отрезок с каким-то весом. Этот вес пропорционален длине отрезка и обратно пропорционален разнице углов. Для начала можно просто множить на косинус угла между отрезками. Т.е. имитируете "инерцию". Новые точку получаете как предыдущую + скорость * время. Если вес подобран правильно, то ВЧ компонента сама себя уничтожит.

Ну а можно и книжки открыть на предмет "фильтр ВЧ"

@spirart · 26.11.2015, 17:14 **[ТС]**

Igor3D, спасибо ))
Нарисовал график углов (на картинке).
Как я понял: беру предыдущий построенный отрезок (из точки (х1, у1) в (х2, у2)) и строю следующий так: беру точку (х3, у3) += atan2(отрезок1)*cos(угол между отрезками).

Что в данном контексте скорость? И время?

@hedgehogues · 27.11.2015, 07:21

Ваша задача очень похожа на задачу аппроксимации с выбросами. Задача аппроксимации состоит в том, чтобы провести линию через k точек, которая минимально отличалась бы от каждой из них. Если бы это было чисто сглаживание, то можно было бы применить обычный МНК. Но у Вас, помимо сглаживания, есть выбросы. В таком случае, я бы советовал смотреть в сторону робасных агоритмов. Например, робасные сглаживающие сплайны.

Вики
Диссертация

@Igor3D · 27.11.2015, 11:46

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

Нарисовал график углов (на картинке).
Как я понял: беру предыдущий построенный отрезок (из точки (х1, у1) в (х2, у2)) и строю следующий так: беру точку (х3, у3) += atan2(отрезок1)*cos(угол между отрезками).
Что в данном контексте скорость? И время?

График углов - это просто atan2(y2 - y1, x2 - x1) - и все. Он должен выглядеть совсем иначе.

Сглаживание: каждый отрезок - вектор скорости v = (x2 - x1, y2 - y1). Берете первый отрезок как есть. Затем на каждом шаге у Вас есть предыдущая скорость v0 и новая v1. Смешиваете скорости

float w0 = 2;
float w1 = cos(v0, v1);
v0 = (v0 * w0 + v1 * w1) / (w0 + w1);

Новую точку получаете как предыдущая + v0. Выводите, смотрите что получилось. Подбираете более удачные правила для w0 и w1. Конечно это просто велик чтобы не углубляться в диссеры

Но его за полчаса можно попробовать

@spirart · 27.11.2015, 15:25 **[ТС]**

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

@spirart · 01.12.2015, 12:32 **[ТС]**

Igor3D, пытаюсь сделать вручную - не выходит: график вообще не меняется после преобразования.
Что я делаю:

в цикле по длине данных:
1. Считаю очередную скорость v[i] ( v[0] = (x[1]-x[0], y[1]-y[0]) )
2. Считаю w (w[0] задаю = 2) как w[i] = cos(v[i-1], v[i]);
3. Пересчитываю скорость: v[i-1] = (v[i-1] * w[i-1] + v[i] * w[i]) / (w[i-1] + w[i]);
4. Добавляю следующую точку: point[i] = point[i-1] + v[i-1] (point = (x,y))

Что я делаю не так?

@spirart · 01.12.2015, 12:45 **[ТС]**

Попробовал на куске данных, а не на всех - изменения есть, но какие-то странные (зеленый график - исходные данные, оранжевый - после преобразования).

@Igor3D · 01.12.2015, 13:28

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

3. Пересчитываю скорость: v[i-1] = (v[i-1] * w[i-1] + v[i] * w[i]) / (w[i-1] + w[i]);

Так чего же первый вес w[i-1]? Это "текущий" (моментальный) вес, скорость и будет гулять как гуляла. Для начала используйте просто 2 (вместо w[i-1]), а там видно будет

@spirart · 01.12.2015, 13:38 **[ТС]**

Igor3D,

@Excalibur921 · 02.12.2015, 03:44

Придумайте данные чтобы ломанная была с клубками как в вашей картинке в первом посте. Атангенс вроде нельзя брать отбалды, там 4 четверти поэтому на графиках бред). Стройте график углов адекватно как в первом посте X шаг Y угол. Получиться погасить клубки на примере тогда настроите для реальных данных. Не сжимайте так графики. Нарисуйте вверху ломанная с клубками, внизу график углов. Тогда и метод сортировки надеться. Мне кажется нужно просто замерять угол между прошлым отрезком и текущим, если больше некого порога то это выброс, брать следующую точку, снова замер угла. Можно сверять углы не двух соседних отрезков а текущий отрезок через 2 точки следующих или через 3 т.е. порог.

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

@Igor3D · 02.12.2015, 08:06

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

Мне кажется нужно просто замерять угол между прошлым отрезком и текущим, если больше некого порога то это выброс,

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

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

Igor3D,

Не понял какой график чему соответствует. Но в любом случае что-то не так, не может угол так резко прыгать если первый вес 2. Исправьте и покрутите весы, попробуйте 3 и даже 4 (вместо 2)

Другой метод - осреднять, для каждой точки посчитать среднее напр 5 точек (2 слева + 2 справа + сама точка). Затем посчитать сумму квадратов отклонений от среднего (дисперсию) и использовать ее как вес. Новая точка получается взвешиванием начальной и осредненной. Больше дисперсия - больше вес осредненной, и наоборот. Возможно лучше осреднять не по числу точек, а по расстоянию. Попробовать 2 и более проходов. Словом - крутите велик

Новые блоги и статьи Все статьи Все блоги /
WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Old Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51

	Сглаживание кривой 25.11.2015, 17:58. Показов 7047. Ответов 27 Метки нет (Все метки) Привет! Совсем замучился с проблемой )) Помогите, пожалуйста! Есть двумерный очень большой массив точек - координаты (x,y) мест. В целом они идут по "красивой" кривой, но иногда возникают "клубки" (как на картинке - черным цветом). Я не понимаю, какой алгоритм применять для того, чтобы "клубки" убрать и просто продолжить мою кривую (на картинке - красная линия). Очень надеюсь на подсказку. Миниатюры 0

@Shamil1 Модератор 3133 / 2280 / 469 Регистрация: 26.03.2015 Сообщений: 8,876
	25.11.2015, 22:05
	А как Вы отличаете "клубки" от неклубоков? Например, почему Вы провели красную линию сквозь "клубки" по кратчайшему расстоянию, а не "горбиком"? 0

@gerMankle 0 / 0 / 0 Регистрация: 12.11.2015 Сообщений: 14
	25.11.2015, 22:31
	Хотел предложить метод главных компонент (гусеницу), но понял, что вроде не по теме )) 0

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	25.11.2015, 22:33 [ТС]
	Shamil1, мне, по сути, не важно, как именно будет линия проходить, можно и горбиком (как я понимаю, горбик будет в сторону большего скопления точек). Важно, чтобы не было запутанностей линий. 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	26.11.2015, 08:52
	мне кажется, что в вашем случае можно просто исключить точки в которых производная (угол наклона) значительно отличается от значения производной в предыдущей неисключенной точке 1

@Igor3D 1966 / 822 / 114 Регистрация: 01.10.2012 Сообщений: 4,810 Записей в блоге: 2
	26.11.2015, 11:51
	Ну вообще-то производная - тангенс угла наклона. Если нарисовать график угла вычисляя его как atan2(delta_y, delta_x), то получится какая-то гладкая кривая на которой будут "всплески". На ней уже найти ровные участки достаточной длины (параметр) и соединить их. Впрочем это велосипед, так, по-быстрому. Задача фильтра ВЧ прекрасно известна, надо читать. 1

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	26.11.2015, 13:16 [ТС]
	Igor3D, я не совсем понял, если честно, первую часть. Рисую график, строя линии между точками, ок. Посчитал atan2 между смежными линиями, ок. Что потом с этим значением делать? Как его использовать? 0

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	26.11.2015, 17:14 [ТС]
	Igor3D, спасибо )) Нарисовал график углов (на картинке). Как я понял: беру предыдущий построенный отрезок (из точки (х1, у1) в (х2, у2)) и строю следующий так: беру точку (х3, у3) += atan2(отрезок1)*cos(угол между отрезками). Что в данном контексте скорость? И время? Миниатюры 0

@hedgehogues 1 / 1 / 1 Регистрация: 20.10.2015 Сообщений: 18
	27.11.2015, 07:21
	Ваша задача очень похожа на задачу аппроксимации с выбросами. Задача аппроксимации состоит в том, чтобы провести линию через k точек, которая минимально отличалась бы от каждой из них. Если бы это было чисто сглаживание, то можно было бы применить обычный МНК. Но у Вас, помимо сглаживания, есть выбросы. В таком случае, я бы советовал смотреть в сторону робасных агоритмов. Например, робасные сглаживающие сплайны. Вики Диссертация 0

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	27.11.2015, 15:25 [ТС]
	Igor3D, Спасибо, теперь понятно )) Очень сильно помогли. Я решил свою проблему с помощью встроенной функции - нашел-таки (делаю на языке R) )) Но теперь буду руками дополнительно это же делать для понимания, потому как функцию использовать - невелик прогресс )) 0

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	01.12.2015, 12:32 [ТС]
	Igor3D, пытаюсь сделать вручную - не выходит: график вообще не меняется после преобразования. Что я делаю: в цикле по длине данных: 1. Считаю очередную скорость v[i] ( v[0] = (x[1]-x[0], y[1]-y[0]) ) 2. Считаю w (w[0] задаю = 2) как w[i] = cos(v[i-1], v[i]); 3. Пересчитываю скорость: v[i-1] = (v[i-1] * w[i-1] + v[i] * w[i]) / (w[i-1] + w[i]); 4. Добавляю следующую точку: point[i] = point[i-1] + v[i-1] (point = (x,y)) Что я делаю не так? Миниатюры 0

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	01.12.2015, 12:45 [ТС]
	Попробовал на куске данных, а не на всех - изменения есть, но какие-то странные (зеленый график - исходные данные, оранжевый - после преобразования). Миниатюры 0

@spirart 3 / 3 / 2 Регистрация: 05.12.2011 Сообщений: 51
	01.12.2015, 13:38 [ТС]
	Igor3D, Миниатюры 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	02.12.2015, 03:44
	Придумайте данные чтобы ломанная была с клубками как в вашей картинке в первом посте. Атангенс вроде нельзя брать отбалды, там 4 четверти поэтому на графиках бред). Стройте график углов адекватно как в первом посте X шаг Y угол. Получиться погасить клубки на примере тогда настроите для реальных данных. Не сжимайте так графики. Нарисуйте вверху ломанная с клубками, внизу график углов. Тогда и метод сортировки надеться. Мне кажется нужно просто замерять угол между прошлым отрезком и текущим, если больше некого порога то это выброс, брать следующую точку, снова замер угла. Можно сверять углы не двух соседних отрезков а текущий отрезок через 2 точки следующих или через 3 т.е. порог. А можно строить например параболу по трем случайным точкам и статистически анализировать какие точки принадлежат параболе +- погрешность но это медленно. Затем найдя параболу считаем расстоянии от точки до параболы, если входит в порог то клубка нет. 0