Н.В. Бейлина
Постановка задачи
Геолокационные данные, описывающие перемещение наблюдаемого объекта, представляют собой последовательность кортежей вида (lon, lat, time,...), где lon, lat — географические координаты объекта (широта и долгота), time — время получения координаты, а многоточием обозначены дополнительные данные, такие как высота над уровнем моря, мгновенная скорость и так далее.
Геолокационные данные, поступающие в информационные системы от датчиков GPS/Глонасс, зачастую избыточны: к примеру, многие датчики передают координаты один раз в секунду, тогда как для реального применения достаточно данных с точностью до минуты, а иногда существенно реже.
Предположим, что в информационную систему передаются лишь широта, долгота, штамп времени (по 64 бита), высота над уровнем моря и скорость (по 16 бит). Без учета накладных расходов каждая запись имеет размер 28 байт. Однако, если данные поступают раз в секунду, за сутки от одного наблюдаемого объекта в систему поступит около 2,3 МБайт данных, 840 Мбайт в год. Понятно, что построение различных аналитических отчетов по таким объемам может быть затруднительно для небольших организаций, не обладающих оборудованием с соответствующей вычислительной мощностью.
С учетом того, что информация, по эмпирическим подсчетам, избыточна приблизительно в 60 раз, весьма актуальным является вопрос фильтрации поступающих в информационную систему данных, по возможности осуществляемый одновременно с приемом данной информации либо с небольшой задержкой, но небольшими блоками.
Очевидно, что (lon, lat), расположенные в порядке возрастания времени, представляют собой вершины ломаной. Для упрощения ломаных линий часто используется алгоритм Рамера — Дугласа — Пекера [1; 2]. Он отличается простотой реализации, высокой эффективностью, а его сложность оценивается как O(n2). Именно этот алгоритм используется в большинстве геоинформационных систем для отображения конечному пользователю траектории движения наблюдаемого объекта на карте.
Формально алгоритм Рамера — Дугласа — Пекера можно применить к любой ломаной, т. е. к любой части имеющихся данных. Алгоритм сохраняет т. н. ’’характерные” точки ломаной, удаляя из нее те, что лежат на расстоянии, не превосходящем £ от прямой, соединяющей другие точки. Однако среди этих точек могут оказаться также и точки, несущие дополнительную смысловую нагрузку, например, точки длительного простоя наблюдаемого объекта или промежуточные точки на длинных прямолинейных участках магистралей — они являются излишними с точки зрения алгоритма Рамера — Дугласа — Пекера, но могут являться важным элементом для других бизнес-процессов предприятия, эксплуатирующего информационную систему.
Типичными ’потерями” при применении алгоритма Рамера — Дугласа — Пекера (и многих других алгоритмов упрощения ломаных) к данным геолокации являются:
потеря мест ’простоя” наблюдаемого объекта, когда становится невозможно определить, как долго на самом деле находился объект в окрестности некоторой точки;
потеря промежуточных точек наблюдаемого объекта при его движении по прямолинейному шоссе.
Это связано с тем, что алгоритм Рамера — Дугласа — Пекера учитывает лишь расстояния (в простейшем случае — на плоскости), но не учитывает время.
Кроме того, многие алгоритмы упрощения ломаных, и в частности алгоритм Рамера — Дугласа — Пекера, не являются поточными, т. е. требуют наличия всех входных данных сразу, в данном случае — всей ломаной, тогда как имеется необходимость в блочно-поточной фильтрации поступающих данных.
Цель данной работы — разработать простой блочно-временной алгоритм фильтрации геолокационных данных, который позволяет сохранять дополнительные характерные точки, такие как:
”точки простоя” наблюдаемого объекта,
”контрольные точки” по расстоянию и времени.
Таким образом, предлагается сначала выделить на треке ”точки простоя” и ”контрольные точки” и использовать их как точки разбиения исходной ломаной на подломаные, к каждой из которых уже применять классические алгоритмы упрощения ломаных, например, алгоритм Рамера — Дугласа — Пекера.
Алгоритм выделения ”точек простоя”
”Точка простоя” характеризуется тем, что в течение некоторого промежутка времени, не менее т, все координаты попали в окружность радиуса S, а все более ранние и более поздние точки лежат на расстоянии не менее S2 от этой окружности. Всю группу точек, попавшую в эту окружность, мы будем заменять не одной, а двумя точками: самой ранней и самой поздней. Таким образом, мы сохраним информацию о времени прибытия наблюдаемого объекта на стоянку и времени выезда со стоянки. Если же данная группа точек по времени попадает в диапазон т, мы заменим данную группу точек не двумя, а одной. Таким образом, кроме выделения ”точек простоя” данная часть алгоритма будет дополнительно фильтровать входные данные по принципу ”ближайший сосед”.
На вход алгоритма поступают геолокационные данные, которые накапливаются в буфере parking, пока радиус окрестности, описанной вокруг точек этого буфера, не превышает £.
for point in input_stream:
Если все точки помещаются в нужну окрестность - пусть помещаются if circle(parking + point).radius < delta:
parking.append(point)
если же новая точка не лезет, пора заканчивать else:
# если прошло больше tau - то это стоянка, добавляем первую и последнюю if parking.last - parking.first.time > tau: output.append(parking.first) output.append(parking.last) else: # время небольшое, сжимаем крайние точки в одну "среднюю"
midpoint = (parking.last + parking.first) / 2 output.append(midpoint)
очищаем парковку parking = []
и точку, которая не влезла в предыдущую парковку, кладем в новую parking.append(point)
Если использовать эффективный алгоритм нахождения радиуса описанной окружности, например [3], имеющий сложность O(n), то в худшем случае сложность предлагаемого алгоритма будет O(n2).
Недостатком данного алгоритма является возможность разрастания временного буфера parking, например в случае, если отслеживаемый объект слишком долго находится на стоянке. Однако и этот недостаток легко устраняется — достаточно лишь добавлять в parking только те точки, которые приводят к росту окрестности.
Если пожертвовать точностью и вместо окружности использовать прямоугольную окрестность, алгоритм, очевидно, будет иметь сложность O(n).
Реализация и апробация результатов
Алгоритм был реализован на языке Python и используется в составе программного комплекса ’Кто куда” (ООО ”Лаб М”) для фильтрации геолокационных данных от аппаратных GPS/Глонасс-трекеров, установленных на автомобилях, передвигающихся по г. Самара и области и передающих геоданные в среднем 10 раз в минуту.
Данные поступали в фильтр, выделяющий ”точки простоя”, с выхода этого фильтра — в промежуточный буфер. К данным в промежуточном буфере применялся алгоритм Рамера — Дугласа — Пекера, для блока данных между ”точками простоя” и ”контрольными точками”.
Данные записывались в базу данных со входа фильтра и с выхода фильтра. Эксплуатация показала не менее чем десятикратное снижение количества записываемых в базу данных геопозиций без ущерба для качества представления (при движении в городском режиме).
Списоклитературы
Ramer Urs. An iterative procedure for the polygonal approximation of plane curves // Computer Graphics and Image Processing. 1972. № 1(3). P. 244-256. (DOI: 10.1016/S0146-664X(72)80017-0).
Douglas David, Peucker Thomas. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature // The Canadian Cartographer. 1973. № 10(2). P. 112-122. (DOI: 10.3138/FM57-6770-U75U-7727).
Emo Welzl. Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science // Lecture Notes in Computer Science. 1991. V. 555. P. 359-370.