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

@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 и более проходов. Словом - крутите велик

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

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

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

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	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 1969 / 825 / 115 Регистрация: 01.10.2012 Сообщений: 4,931 Записей в блоге: 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