Алгоритмы устранения ложных и избыточных данных в GPS-потоке

  • Tutorial


Разработка электроники на базе GPS/ГЛОНАСС-технологий — одна из наших любимых тем на Хабре. Мы уже писали обзорную статью на эту тему, рассказывали про систему «ЭРА-ГЛОНАСС» и даже определяли своё местоположение по сетям сотовой связи.

В этот раз наш пост призван дать ответ на конкретный практический вопрос: «Как уменьшить объем потока данных с навигационно-связных терминалов без потери информативности?». Эта тема весьма актуальна, ведь услуги беспроводной связи составляют значительную часть финансовых затрат на обслуживание систем мониторинга транспорта.

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

На рисунке ниже представлена блок-схема данного процесса:



Этап формирования точки, от момента получения координат с GPS-приемника до момента передачи на сервер, можно разделить на три подготовительных части: стабилизация, фильтрация и прореживание.

Стабилизация и фильтрация — это опциональные этапы, они нужны для исправления несовершенства качества приема GPS-сигнала. Зачастую задачу стабилизации позволяет решить установленный на устройстве акселерометр, а также алгоритм усреднения точек. Таким образом мы избавляемся от так называемых «звезд» на стоянках транспортных средств и можем привязаться к статичной позиции, когда транспортное средство покоится.

Фильтрация предназначена для отслеживания физически невозможных бросков координат. Такая ситуация возникает в кратковременных критических условиях приёма (например под линиями электропередач).

И, наконец, прореживание точек или децимация — самый распространённый и логичный этап в задаче уменьшения объема передаваемых данных, его мы рассмотрим в данной статье.

1. Прореживание точек или децимация в навигационных системах


Допустим, что каждая навигационная точка содержит информацию о местоположении транспортного средства, информацию, полученную от датчиков, установленных на борту и какие-либо статусы, характеризующие состояние системы. Обычно информация от GPS-приёмника поступает каждую секунду, т.е. каждую секунду мы имеем сформированный набор данных, который без алгоритма децимации пришлось бы передавать полностью. Эта информация по большей части является избыточной.

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



В рамках этого примера мы сэкономили 72% данных в случае со средней степенью прореживания и целых 96% в случае с жесткими условиями прореживания! Как видно, этот простой метод дает колоссальное преимущество в экономии объема памяти.

Но в реальных условиях, когда навигационные данные дополнены информацией от бортовых датчиков, алгоритм немного усложняется, так как возникает необходимость передавать данные ещё и по системным событиям. Поэтому все критерии прореживания можно разделить на группы по приоритетам: системные события («прерывания») и информация о навигационных характеристиках транспортного средства.

К системным можно отнести такие события: включение / выключение питания, установление / потеря соединения со спутниками и т. д. Очевидно, что системные прерывания являются более приоритетными, чем общая информация. Отношения между приоритетностью и важностью информации можно представить следующей блок-схемой:



При выполнении одного из условий, пакет передается дальше на проверку остальных условий либо отправляется в нелинейный буфер. Если ни одно из условий не выполнено, то пакет выбрасывается из потока.

Примерная реализация алгоритма прореживания на языке си может быть следующей:

#define TIME_LIMIT        60 //sec
#define HDOP_LIMIT        400
#define DISTANCE_LIMIT    300 //m
#define SPEED_LIMIT       4000//km/h
#define COURSE_LIMIT      9000 //deg
GPS_DATA previous_sample;
int GPS_decimator(GPS_DATA * sample) {
        if (sample->time.sec + sample->time.min*60 + sample->time.hour*3600 - previous_sample.time.sec - previous_sample.time.min*60 - previous_sample.time.hour*3600 > TIME_LIMIT) {
                return 1;
        }
        if (sample->hdop > HDOP_LIMIT) {
                return 0;
        }
        double UTMNorthing;
        double UTMEasting;
        double GPS_passed_northing;
        double GPS_passed_easting;
        char UTMZone[4];
        double la;
        modf(sample->la/100,&la);
        la += ((sample->la)-la*100)/60;
        double lo;
        modf(sample->lo/100,&lo);
        lo += ((sample->lo)-lo*100)/60;
        //convert coordinates to UTM
        LLtoUTM(la, lo, &UTMNorthing, &UTMEasting, UTMZone);
        double pla;
        modf(previous_sample.la/100,&pla);
        pla += ((previous_sample.la)-pla*100)/60;
        double plo;
        modf(previous_sample.lo/100,&plo);
        plo += ((previous_sample.lo)-plo*100)/60;
                //convert coordinates to UTM
        LLtoUTM(pla, plo, &GPS_passed_northing, &GPS_passed_easting, UTMZone);
        if (sqrt(pow(UTMNorthing-GPS_passed_northing,2)+pow(UTMEasting-GPS_passed_easting,2)) >= DISTANCE_LIMIT) {
                return 1;
        }
        if ((previous_sample.speed - sample->speed)*(previous_sample.speed - sample->speed) >= SPEED_LIMIT*SPEED_LIMIT) {
                return 1;
        }
        if ((previous_sample.course - sample->course)*(previous_sample.course - sample->course) >= COURSE_LIMIT*COURSE_LIMIT) {
                return 1;
        }
        return 0;
}

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

2. Использование оптимального протокола передачи данных


Второй путь уменьшения объема передаваемых данных – это использование оптимального протокола передачи данных. Для начала выделим два основных типа протоколов: текстовый и двоичный или бинарный.

Текстовым протоколом, например, является NMEA, который используется в GPS-приемниках. Для передачи навигационной информации в простейшем случае может быть достаточно передачи RMC-строки данного протокола.

Основные черты текстового протокола:
  • удобен для визуального восприятия;
  • один пакет содержит одну путевую точку;
  • целостность гарантируется контрольной суммой;
  • имеет фиксированное количество полей в пакете;
  • данные передаются в открытом виде;
  • все численные данные необходимо переводить в текстовый вид и обратно;
  • протокол не предполагает экономии количества байт в пакете.

Пример использования текстового протокола:



На фото: персональный GPS-навигатор с электронным компасом — давний проект команды инженеров Promwad, один из первых опытов в сфере навигации. Это простое устройство возвращает пользователя в точку старта или заранее отмеченное место на системе координат.

В рамках проекта использовался текстовый протокол NMEA. Аппаратная платформа навигатора была построена на базе электронных компонентов с оптимальными параметрами, чтобы обеспечить низкую себестоимость устройства (на уровне 30 USD при партии от 10 000 шт.). В результате нам пришлось решать интересные задачи по оптимизации алгоритмов расчёта расстояния и направления.

GPS-модуль навигатора отправлял координаты в формате NMEA на микроконтроллер Freescale MC9S08QE8, по ним определялось расстояние и вектор движения до заданной точки. Т.к. объём памяти микроконтроллера был крайне ограничен, мы реализовали преобразование координат в целочисленную форму, при этом погрешность вычислений осталась в допустимых пределах. Подробнее об этой разработке можно прочитать в PDF-файле с техническим описанием проекта.


Второй тип — бинарный протокол, имеет только один недостаток — он неудобен для визуального восприятия без применения специальных средств. Его использование с тем же количеством параметров, что и в текстовом варианте, позволяет сэкономить на объеме данных более чем в два раза с одного пакета.

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

Бинарный протокол также позволяет производить аутентификацию устройств на сервере сбора данных и передавать различную сервисную информацию в двухстороннем порядке. Конечно же, некоторые из этих вещей можно передавать и с использованием текстового протокола, но это нецелесообразно.

Ещё одной прекрасной возможностью, которую дает бинарный протокол, является переменная длина пакетов. Благодаря этому устройства с различной конфигурацией периферийных датчиков могут работать в одной системе. Каждый пакет имеет неделимую часть, состоящую из заголовка и навигационной информации – часть, которая является идентификационной, и дополнительные поля с информацией, полученной от датчиков. Причём в каждый момент времени могут быть добавлены только необходимые данные.

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

Итого


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

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

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

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

Comments 24

    +4
    >> (previous_sample.course — sample->course)*(previous_sample.course — sample->course) >= COURSE_LIMIT*COURSE_LIMIT)

    А как оно обрабатывает переход через 360 градусов?

    И положите исходники на гитхаб, что ли.
      0
      Думаю, такую разницу лучше нормализовать до (-180°; 180°], нежели возводить в квадрат.
        0
        Вы правы, переход через 360 градусов в этом случае не обрабатывается. Можно предложить, например, такую формулу для нахождения разности курсов: (360 + (course2-course1)) % 360
          0
          Скажите, у вас в компании практикуют код-ревью?
            0
            Да, на всех коммерческих проектах код-ревью — это обязательная процедура.
        0
        Посмотрел исходник из аттача.

        Скажите, а зачем там переход в UTM вообще? Расстояния куда лучше считать напрямую из градусов координат.
          0
          Komzpa, спасибо за интерес к теме.

          Скажите, а зачем там переход в UTM вообще? Расстояния куда лучше считать напрямую из градусов координат.

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

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

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

          Подход, который вы предлагаете, мы использовали в самом начале, но потом от него отказались. Если у вас есть более простое рабочее решение — предлагайте. Мы уверены, что читателям этой статьи будет интересно его увидеть.
            0
            1) расстояние между двумя позициями на сфере считается напрямую, gis-lab.info/qa/great-circles.html — переход в UTM создаёт проблемы с масштабом на краю зоны, и зачем-то ограничивает область применимости вашего устройства.

            2) сильно меняется — это по косинусу. cos(lat) и cos^2(lat) — множители, которые позволяют корректно считать расстояния/площади для небольших изменений по широте. Между двумя измерениями GPS-трекера широта меняется незначительно, если только вы не делаете что-то из аэрокосмической области — но тогда у вас и чипы будут другими.

            Заходите по четвергам в минский хакерспейс на день открытых дверей, порисуем на доске.
              0
              Спасибо за комментарий и за приглашение!
          +8
          Вообще, тема не раскрыта.

          Топик называется «Алгоритмы устранения ложных и избыточных данных в GPS-потоке», а рассказано только про избыточные данные.

          Как фильтровать «узелки» на стоянках?
            0
            Это совсем не сложная задача. В ats24.ru мы решили ее на примитивном уровне — перемещение, относительно нескольких предыдущих координат < диаметра погрешности gps-модуля. Это если совсем упрощенно.
              0
              Да понятно, что Дуглас-пойкером давить — тоже вариант. Но у меня есть кучка треков, на которых узелки так не давятся :)
                0
                Есть способ, он не универсален, но неплохие результаты дает, если его правильно настроить.
                Вокруг трека строится буфер, далее по области, покрытой буфером, пробегаем скользящим окном с радиусом, который несколько больше радиуса буфера (этот параметр подлежит подбору). Помечаем области, где окно попало внутрь буфера целиком. А дальше просто удаляем то, что попало в те области, где окно уместилось в буфер. Оно, конечно, может выкинуть и области честных петель трека, но если подойти к задаче творчески — можно свести это к минимуму.
                А так, если пишете треки для OSM и т.п., запаситесь нормальным приемником, который не собирает мусор много ниже уровня шумов и не рисует фантазии, а для полного счастья — еще и акселерометром. Тогда уж точно с фильтрацией проблем не будет.
              0
              Как фильтровать «узелки» на стоянках?

              Действительно, тема устранения не раскрыта.

              Мы перепробовали разные способы устранения узелков и остановились на использовании акселерометра. В нём использовался режим установки сигнала при превышении порога внешнего воздействия (т. е. когда транспортное средство начинает движение). Параметр был подобран экспериментально. Этот сигнал переводил прибор из режима покоя в режим движения.
              0
              Всё классно, если вы работаете с проверенным знакомым прибором и можете доверять его данным.
              На практике китай-трекеры(а равно и отечественные говнотахографы) могут не то, что HDOP не передавать(это вообще редкость), но и врать насчёт кол-ва спутников/курса/скорости, передавать данные в чёрт-пойми каком порядке и т.п.
                0
                Не используйте китай-трекеры. :) Если ваш прибор врёт, то не стоит рассчитывать на волшебный алгоритм.
                  0
                  Была б моя воля… Да клиентам, знаете, подешевле подавай.
                0
                Странно, что такие оптимизации до сих пор имеют место в современной электронике.
                А если данные сжимать, — сколько экономии будет? Или они и без этого уже сжимаются при передаче?
                А что, если детальные данные хранить и сбрасывать только тогда, когда машина в зоне действия предустановленных или бесплатных wifi?

                Что-то вспомнилась система мониторов в Киевском метрополитене: поезда по линиям катались с текущим контентом и обновляли базу данных, когда подключались к wifi в депо.
                  0
                  miha2, данные сжимать можно, но сомнительна реальная выгода от этого, ведь это усложняет и протокол, и позиционирование прибора в псевдореальном времени (имеет смысл сжимать пакет данных, а не отдельные сэмплы), ну и сложность разработки не нужно исключать.

                  А насчёт накопления: представьте себе маршрут, который занимает не один, а несколько дней (международные перевозки). В этом случае накладываются серьёзные ограничения на общий объём хранимых данных. Но такие схемы, как вы упомянули, тоже используются. Всё зависит от конкретных задач.
                  0
                  Плохо, что ваш алгоритм «срезает угол». Это, как раз, и есть потеря важной информации.
                    0
                    Тоже сразу обратил на это внимание. А также на каляки-маляки на правом верхнем углу, которые, очевидно, избыточны для этой картинки и которые срезаются элементарным прореживаем/слиянием ближайших точек (у меня скрипт на питоне написанный на коленке удалял подобные звёздочки-артефакты).
                      –1
                      barker, если вы обратите внимание на самую первую блок-схему, то увидите ещё два этапа «Стабилизация» и «Фильтрация». В рамках этих этапов мы можете произвести усреднение, слияние и т. д. И только после этого мы переходим к анализу и избавлению от избыточных точек. То, что вы видите на картинке, это «сырые» NMEA-данные, полученные с GPS-приёмника без всяческой предобработки.
                        0
                        Не, ну просто алгоритм (прореживания, показанный на картинках) ваш как-то неравномерно преобразует данные. Нужную информацию (см. срезанный угол) он убрал, а ненужную (звёздочка, которая крайне просто определяется) оставил.
                      –1
                      aryeh, всё определяется теми настройками, которые вы делаете. Можно увеличить чувствительность на смену курса и получится более приятная для глаз картина.

                    Only users with full accounts can post comments. Log in, please.