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

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

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

Привет!

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

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

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

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

@spirart · 02.12.2015, 11:01 **[ТС]**

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

Придумайте данные чтобы ломанная была с клубками как в вашей картинке в первом посте. Атангенс вроде нельзя брать отбалды, там 4 четверти поэтому на графиках бред).

Мне не нужно придумывать данные, они мне даны, и мне необходимо их сгладить. У меня там дальше есть модифицированный график углов - первая картинка, действительно, была очень неправильная ))

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

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

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

Вот мой код:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#v - таблица с 2 колонками: x и y, скорость
#x, y - мои данные (6000 наблюдений)
#счет идет не с 0, а с 1
v$x[1] = x[2]-x[1]
v$y[1] = y[2]-y[1]
 
#начальный вес, w0
w[1] = 20
 
#df - таблица с колонками х и у, куда буду записывать получившиеся координаты
df$x[1] = x[1]
df$y[1] = y[1]
 
df$x[2] = x[2]
df$y[2] = y[2]
 
 
#len = 6000 (кол-во наблюдений)
for (i in 2:(len-1) ) {
  #вектор скорости
  v$x[i] = x[i+1] - x[i]
  v$y[i] = y[i+1] - y[i]
  
  #вес
  #с(a,b) - 2d вектор с координатами a и b
  w[i] <- cos.angle(c(v$x[i-1], v$y[i-1]), c(v$x[i], v$y[i]))
  
  #смешиваю скорости
  v$x[i-1] <- (v$x[i-1]*w[1] + v$x[i]*w[i]) / (w[1] + w[i])
  v$y[i-1] <- (v$y[i-1]*w[1] + v$y[i]*w[i]) / (w[1] + w[i])
  
  #вычисляю следующие точки
  df$x[i+1] <- x[i] + v$x[i-1]
  df$y[i+1] <- y[i] + v$y[i-1]
}

У меня есть подозрение, что считать следующую точку, прибавляя к предыдущей просто скорость, не совсем то, что надо (координата + скорость? разве это соразмерные величины?). Хочется на что-нибудь умножить.

@Igor3D · 02.12.2015, 11:49

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

У меня есть подозрение, что считать следующую точку, прибавляя к предыдущей просто скорость, не совсем то, что надо (координата + скорость? разве это соразмерные величины?). Хочется на что-нибудь умножить.

На шаг по времени = 1. Когда скорость вычисляли на время не делили, а здесь не множим - время сократилось

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

w[i] <- cos.angle(c(v$x[i-1], v$y[i-1]), c(v$x[i], v$y[i]))

А что это за косинус такой? Может он у Вас 100 и больше, тогда и выходит что ничего не меняется. Попечатайте его. Он должен вычисляться как скалярное произведение нормированных скоростей, т.е это косинус угла между отрезками

C++
1
w[i] = (v[i].x * v[i - 1].x + v[i].y * v[i - 1].y) / (length(v[i]) * length(v[i - 1]));

И здесь

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

#смешиваю скорости
v$x[i-1] <- (v$x[i-1]*w[1] + v$x[i]*w[i]) / (w[1] + w[i])
v$y[i-1] <- (v$y[i-1]*w[1] + v$y[i]*w[i]) / (w[1] + w[i])

Присваивать это [i - 1] ячейке незачем. И зачем хранить эту таблицу, нужен только накапливаемый вектор и текущий, т.е. 2 переменные

В общем, отладку никто не отменял - на любом языке программирования

@spirart · 02.12.2015, 12:27 **[ТС]**

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

На шаг по времени = 1. Когда скорость вычисляли на время не делили, а здесь не множим - время сократилось

Да, я послал вопрос и почти сразу понял, почему так ))

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

А что это за косинус такой? Может он у Вас 100 и больше, тогда и выходит что ничего не меняется.

Косинус угла между отрезками - ровно то, что Вы и написали, просто вынесено в отдельную функцию.
И возвращает ровно косинус угла между векторами, пример вывода:

Code
1
2
3
x = ( 1 0 ) y = ( 0 1 ) cos.angle(x,y) = 0
x = ( 1 0 ) y = ( -1 0 ) cos.angle(x,y) = -1
x = ( 1 0 ) y = ( 1 1 ) cos.angle(x,y) = 0.7071068

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

И зачем хранить эту таблицу, нужен только накапливаемый вектор и текущий, т.е. 2 переменные

Да, может, таблица и не нужна ))

Я пытаюсь сделать следующее: загружаю исходные точки из файла (по сути - это координаты от gps-приемника), убираю клубки, записываю новый, сглаженный массив: gps-приемник дает координаты с большой ошибкой, когда скорость его = 0 (получаются такие клубки), при движении - все в пределах допустимого. Хочу рисовать красивый маршрут на карте.

@Excalibur921 · 02.12.2015, 13:34

Не знаю что у вас тут за формулы и зачем они.
Если сделать как я говорил выше то будет примерно следующее:
Название: ScreenShot00253.jpg
Просмотров: 40

Размер: 12.6 Кб

Название: ScreenShot00253.jpg
Просмотров: 40

Размер: 12.6 Кб

@Igor3D · 02.12.2015, 13:50

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

Я пытаюсь сделать следующее: загружаю исходные точки из файла (по сути - это координаты от gps-приемника), убираю клубки, записываю новый, сглаженный массив:

Я понял, но с отладкой помочь не могу, т.к. Вашего "козырного" языка никогда не видел

На С/С++ все это делается за минуты (если графики под рукой), а тут как-то тяжеловато идет.

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

gps-приемник дает координаты с большой ошибкой, когда скорость его = 0 (получаются такие клубки), при движении - все в пределах допустимого. Хочу рисовать красивый маршрут на карте

Тогда есть резон осредняться "по длине" как я писал выше. Только в качестве критерия лучше брать угол. Схема:

- для каждой точки просматриваем массив вперед и назад на заданную длину. Попавшие в диапазон точки принимаются для осреднения с весом 1, крайние - с частичным, пропорционально захваченной длине. Имеем для точки среднее значение.

- вычисляем сумму квадратов отклонений углов (а не позиций) и используем ее как вес для взвешивания между исходной и осредненной. Для крайних точек (не вошедших в диапазон) используем их частичные веса

Добавлено через 2 минуты

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

Если сделать как я говорил выше то будет примерно следующее:

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

@Excalibur921 · 02.12.2015, 14:16

К примеру так Даны 4 точки ABCD. Находим абсолютный угол AB,AC,AD.Если разность углов AB и AC<порог и разность углов AB и AD<порог то точка A принадлежит графику.

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

это координаты от gps-приемника

С этого нужно было начинать.
ТС может вы вообще не так подходите к вопросу?
Сейчас вы показываете координаты GPS типа X Y координаты на местности, а если построить два графика типа
1) X ось это время Y ось это X координаты
2) X ось это время Y ось это Y координаты
Тогда клубков не будет вообще никогда, появиться просто шум на графиках остановки GPS .В любом случае сильно упростит анализ, и тема эта должна быть очень известная. А значит велик не нужен.
И может такой вопрос задать в теме GPS по типу Метод сглаживания GPS данных?
К примеру: http://habrahabr.ru/post/140274/
И вообще поискать типа Убрать шум на графике, сглаживание GPS данных.

@Igor3D · 02.12.2015, 15:06

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

А значит велик не нужен.
И может такой вопрос задать в теме GPS по типу Метод сглаживания GPS данных?
К примеру: http://habrahabr.ru/post/140274/
И вообще поискать типа Убрать шум на графике, сглаживание GPS данных.

Я тоже рекомендовал "открыть книгу" и все такое

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

В общем, такие ссылки хорошо сливать другим, но не юзать самому

Что впрочем совершенно нормально - автор не обязан следовать собственным рекомендациям - они ведь пишутся для других

В конце-концов велик - двигатель прогресса, а если попробовать легко - так чего ж нет.

@Excalibur921 · 02.12.2015, 17:05

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

что-то не выходит, по крайней мере "сходу"

Эта ссылка просто пример =). А вообще направление поиска должен выбрать ТС.
А эта проблема была всегда… когда хочешь что-то повторить, вроде ну вот же 10 листов описание 30 промежуточных формул ( зачем? в итоге 3 для практики)а как понять что куда и как =). Такое чувство, что когда математический уровень программиста проходит какой-то порог, он перестает адекватно писать формулы простыми обозначениями и простым языком пояснять расчет.. И в других форумах бегло глянул вроде как упоминают Калмана для этой задачи наверно ж не зря, упоминают же там GPS.
http://delirium-00.livejournal... tml?page=1

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

Надо осознать параметры (которых не так уж мало),

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

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

1) X ось это время Y ось это X координаты
2) X ось это время Y ось это Y координаты

И к таким графикам уже применять:

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

К примеру так Даны 4 точки ABCD. Находим абсолютный угол AB,AC,AD.Если разность углов AB и AC<порог и разность углов AB и AD<порог то точка A принадлежит графику.

Хотя это суть как и здесь почти, только в обе стороны:

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

для каждой точки просматриваем массив вперед и назад на заданную длину.

А может и так хватит и углов нет. https://ru.wikipedia.org/wiki/Скользящая_средняя
“Нашёл что это как правило МНК, Калмен, Сплайн, ну и нечто логическое, аля статик навигейшн с СИРФ3... Но это всё не подтвержденные/общие данные.”
Похоже каждый делает как может(вариантов очень много) а коммерческие наверно секретны. На одном форуме говорят сплайн Акимы, создавал давно вопрос этот и глухо.

А если не записывать координаты когда автомобиль остановлен? И все…И ничего не нужно сглаживать =).

Новые блоги и статьи Все статьи Все блоги /
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .	21 мат мед. Планы на развитие модели здравоСохранения anaschu 01.06.2026 AnyLogic: план развития симуляционной модели рабочего коллектива — динамический абсентеизм, реальные данные, три сценария сравнения Продолжаю серию постов о дискретно-событийной модели рабочего. . .	20. Мат мед. Абсентеизм как отдельный тип простоя anaschu 29.05.2026 Апдейт модели: исправленные баги, абсентеизм и новые механизмы Продолжаю развивать ранее описанную модель рабочего коллектива на AnyLogic. За последние несколько дней был проведён серьёзный. . .	19. здоровье, усталость и психотип работника влияют на производительность предприятия, и наоборот, производительность на здоровье, усталось и психотип anaschu 28.05.2026 Дискретно-событийная модель рабочего коллектива на AnyLogic: здоровье, выгорание, психотипы и микростимуляция Привет, коллеги. Хочу поделиться итогами нескольких недель работы над симуляционной. . .
"Прокси" для последовательного порта Eddy_Em 28.05.2026 Эту штуку написал я достаточно давно. Но сейчас вот понадобилось настроить датчик грозы, но при этом не отключать его от "метеодемона". Соответственно, надо запустить этот "прокси": метеодемон будет. . .	Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .

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

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

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	02.12.2015, 13:34
	Не знаю что у вас тут за формулы и зачем они. Если сделать как я говорил выше то будет примерно следующее: 0