Упрощение / оптимизация GPS трека

Question

У меня есть GPS-трек, созданный gpxlogger(1) (поставляется как клиент для gpsd ).Приемник GPS обновляет свои координаты каждую 1 секунду, логика gpxlogger очень проста, он записывает местоположение (lat, lon, ele) и временную метку (time), получаемую от GPS каждые n секунд ( n = 3 в моем случае).

После записи трека продолжительностью в несколько часов gpxlogger сохраняет файл GPX длиной в несколько мегабайт, который включает в себя несколько тысяч точек.После этого я пытаюсь нанести этот трек на карту и использовать его с OpenLayers .Это работает, но несколько тысяч точек делают использование карты неряшливым и медленным.

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

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

Существует ли какая-либо готовая утилита / библиотека / алгоритм, доступная для оптимизации треков ?Или, может быть, я пропускаю какой-то умный вариант с gpsbabel?

Answer 1

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

Легко расширить алгоритм до трехмерного случая с небольшим пониманием того, как работает алгоритм. Допустим, у вас есть входной путь, состоящий из 26 точек, помеченных от A до Z. Простейшая версия этого пути имеет две точки, A и Z, поэтому мы начнем с них. Представьте отрезок линии между A и Z. Теперь просмотрите все оставшиеся точки с B по Y, чтобы найти точку, наиболее удаленную от отрезка AZ. Скажем, что самая дальняя точка - это J. Затем вы сканируете точки между B и I, чтобы найти самую дальнюю точку от отрезка AJ, и сканируете точки от K до Y, чтобы найти точку, наиболее удаленную от отрезка JZ, и так далее, до оставшихся точек все лежат в пределах некоторого желаемого порога расстояния.

Это потребует некоторых простых векторных операций. Логически, это тот же процесс в 3D, что и в 2D. Если вы найдете алгоритм Дугласа-Пекера, реализованный на вашем языке, возможно, в нем реализована некоторая двумерная векторная математика, и вам нужно будет расширить ее, чтобы использовать 3 измерения.

Вы можете найти реализацию 3D C ++ здесь: 3D Douglas-Peucker в C ++

Ваши координаты x и y, вероятно, будут в градусах широты / долготы, а координата z (времени) может быть в секундах с начала эпохи Unix. Вы можете устранить это несоответствие, выбрав соответствующие пространственно-временные отношения; Допустим, вы хотите просмотреть один день активности на карте площадью 1 квадратная миля. Представляя эти отношения как куб 1 миля на 1 милю на 1 день, вы должны предварительно масштабировать переменную времени. Преобразование из градусов в расстояние от поверхности нетривиально, но для этого случая мы упрощаем и говорим, что один градус составляет 60 миль; тогда одна миля составляет 0,0167 градусов. Один день составляет 86400 секунд; затем, чтобы сделать единицы эквивалентными, наш коэффициент предварительной шкалы для вашей метки времени составляет 0,0167 / 86400 или около 1/5 000 000.

Если, скажем, вы хотите просматривать активность GPS в одной и той же области карты площадью 1 кв. Милю в течение 2 дней, вместо этого разрешение по времени становится вдвое менее важным, поэтому уменьшите его вдвое, до 1/10 000 000. Веселитесь.

Answer 2

Взгляните на Ramer-Douglas-Peucker алгоритм сглаживания сложных многоугольников, а также Douglas-Peucker алгоритм упрощения линий может помочь вам уменьшить ваши очки.

Answer 3

Java-библиотека OpenSource GeoKarambola (без зависимостей Android, но может использоваться в Android), которая включает в себя класс GpxPathManipulator, который выполняет как упрощение / уменьшение маршрутов, так и отслеживание (с учетом 3D / повышения). Если у точек есть метка времени, информация не будет сброшена. https://sourceforge.net/projects/geokarambola/

Это алгоритм в действии, в интерактивном режиме https://lh3.googleusercontent.com/-hvHFyZfcY58/Vsye7nVrmiI/AAAAAAAAHdg/2-NFVfofbd4ShZcvtyCDpi2vXoYkZVFlQ/w360-h640-no/movie360x640_05_82_05.gif

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

Альтернативный алгоритм для оперативного потока, такого как упрощение дорожки (я называю это «усилением»): Вы сохраняете небольшой буфер точек, которые дает вам датчик GPS, каждый раз, когда точка GPS добавляется в буфер (включая высоту), вы вычисляете максимальное XTD (расстояние между точками) всех точек в буфере до отрезка линии, который объединяет первую точку с (недавно добавленной) последней точкой буфера. Если точка с наибольшим XTD нарушает вашу максимально допустимую ошибку XTD (25 м дали мне отличные результаты), тогда вы обрезаете буфер в этой точке, регистрируете его как выбранную точку для добавления к дорожке с усилением, обрезаете заднюю часть Буфер до этой точки разреза, и продолжайте идти. В конце дорожки последняя точка буфера также добавляется / сбрасывается в решение. Этот алгоритм достаточно легкий, чтобы работать на умных часах AndroidWear, и обеспечивает оптимальную производительность независимо от того, движетесь ли вы медленно или быстро или простаиваете в одном месте в течение длительного времени. Единственная вещь, которая имеет значение, это форма вашего трека. Вы можете идти в течение многих минут / километров и, пока вы движетесь по прямой линии (коридор в пределах +/- допустимых отклонений погрешности XTD), алгоритм streamplify будет выводить только 2 точки: из выхода из последней кривой и входа на следующей кривой.

Answer 4

Попробуйте, это бесплатно и с открытым исходным кодом онлайн-сервис:

http://labs.easyblog.it/maps/gpx-simplify-optimizer/

Answer 5

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

Answer 6

Это, вероятно, NP-жесткий. Предположим, у вас есть точки A, B, C, D, E.

Давайте попробуем простой детерминированный алгоритм. Предположим, вы рассчитываете расстояние от точки B до линии A-C, и оно меньше вашего порога (1 метр). Таким образом, вы удаляете B. Затем вы пытаетесь сделать то же самое для C в строке A-D, но она больше, а D для C-E, которая также больше.

Но оказывается, что оптимальным решением является A, B, E, потому что точки C и D находятся близко к линии B-E, но с противоположных сторон.

Если вы удалите 1 точку, вы не можете быть уверены, что это должна быть точка, которую вы должны сохранить , если вы не попробуете каждое возможное решение (которое может быть размером n^n, и т. Д. n=80 это больше, чем минимальное количество атомов в известной вселенной).

Следующий шаг: попробуйте алгоритм brute force или branch and bound . Не масштабируется, не работает в реальном размере. Вы можете смело пропустить этот шаг:)

Следующий шаг: Сначала выполните детерминированный алгоритм и улучшите его с помощью метаэвристического алгоритма (поиск по табу, моделируемый отжиг, генетические алгоритмы). В Java есть пара реализаций с открытым исходным кодом, таких как Drools Planner .

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

Далеким родственником этой проблемы является, вероятно, вариант задачи коммивояжера, в котором продавец не может посетить все города, но должен выбрать несколько.

Answer 7

Я столкнулся с подобной проблемой.Скорость, с которой устройство GPS набирает очки, намного выше необходимой.Многие точки географически не удалены друг от друга.Подход, который я выбрал, заключается в том, чтобы вычислить расстояние между точками, используя формулу haversine.Если расстояние не превышало моего порога (в моем случае 0,1 мили), я отбрасывал точку.Это быстро уменьшает количество баллов до приемлемого размера.

Я не знаю, какой язык вы ищете.Вот проект C #, над которым я работал.Внизу вы найдете код haversine.

http://blog.bobcravens.com/2010/09/gps-using-the-netduino/

Надеюсь, что это заставит вас двигаться.

Answer 8

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

Это можно сделать в & Omicron; (n log (n)), составив список каждого индекса и его угла, отсортировав этот список в порядке убывания угла, сохранив необходимое количество в начале списка, отсортировав этот более короткий список в порядке убывания индекса и удаления индексов из списка точек.

def simplify_points(points, how_many_points_to_remove)
  angle_map = Array.new
  (2..points.length - 1).each { |next_index|
    removal_list.add([next_index - 1, angle_between(points[next_index - 2], points[next_index - 1], points[next_index])])
  }
  removal_list = removal_list.sort_by { |index, angle| angle }.reverse
  removal_list = removal_list.first(how_many_points_to_remove)
  removal_list = removal_list.sort_by { |index, angle| index }.reverse
  removal_list.each { |index| points.delete_at(index) }
  return points
end

Answer 9

Не уверен, насколько хорошо это будет работать, но как насчет составления списка точек, определения расстояния между ними и, следовательно, общего расстояния маршрута, а затем определения расстояния разрешения и затем просто линейной интерполяции положения на основе каждый шаг х метров. т. е. для каждого исправления у вас есть мера «расстояние от начала», и вы просто интерполируете, где n * x для всего вашего маршрута. (Вы можете решить, сколько точек вы хотите, и разделить общее расстояние на это, чтобы получить разрешение вашего расстояния). Вдобавок к этому вы можете добавить оконную функцию, берущую, может быть, текущую точку +/- z точек и применяя весовые коэффициенты, такие как exp (-k * dist ^ 2 / precision ^ 2), чтобы получить средневзвешенное значение набора точек, где dist - это расстояние от необработанной интерполированной точки, а точность - это предполагаемая точность позиции GPS.

Answer 10

Полагаю, вам нужно хранить точки, в которых вы меняете направление. Если вы разбили свою дорожку на набор интервалов постоянного направления, вы можете оставить только граничные точки этих интервалов.
И, как указал Райдвальд, вы захотите оставить точки, где ваше ускорение не равно нулю.