Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

SET OF INTERPOLATION POINTS OPTIMIZATION USING DISRETE DYNAMIC PROGRAMMING PRINCELPES

Belyakov A.K. 1 Kritsyna N.A. 2 Kulyabichev Yu.P. 2 Sukhanov A.A. 2
1 JSC “Concern “SYSTEMPROM”
2 National research nuclear university “MEPhI”
Рассматривается метод формирования оптимальной упорядоченной выборки М точек из общего набора интерполяционных точек кривой, обеспечивающих минимум интеграла квадрата ошибки интерполя-ции. Для решения задачи предлагается критерий, представленный в виде суммы частных интегральных критериев. Данный подход позволяет использовать для решения общей оптимизационной задачи прин-цип дискретного динамического программирования Беллмана. Предлагаемый метод разрабатывается для использования в геоинформационных системах при формировании баз данных, содержащих интер-поляционные точки линий (дорожная сеть, различные границы и прочие линейные объекты) для после-дующего их отображения на карте местности. А также для предварительной фильтрации данных, вы-званной ограничениями оперативной памяти при использовании в специализированных навигационных устройствах.
In article we suggests method of forming the optimal ordered set of points from the set of interpolation points described an arbitrary curved line. Our method providing a minimum integral square error of interpolation. To solve the problem we suggest a criterion presented in the form of a sum of partial integral criteria. This approach allows use Bellman’s general principle of the discrete dynamic programming to solve the optimization problem. The proposed method are being developed for use in geographic information systems at formation of databases containing lines presented as set of interpolation points (roads, borders and various other linear objects) for subsequent displaying on a map of the area. Also for the preliminary filtering of data for use in specialized navigation devices, caused by the limitations of memory of such devices.
line node points
graph of solutions
optimization criteria
interpolation
Geographic Information Systems
dynamic programing

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

В этой связи актуальной становится задача определения упорядоченного набора M точек из первоначального множества точек , (). В качестве критерия выбора точек рационально поставить условие минимизации площади, находящейся между линией, построенной по M упорядоченным точкам (линия ), и линии, построенной по N упорядоченным точкам (линия ). Такой критерий эквивалентен интегралу квадрата отклонения точек линии от соответствующих точек линии (рис. 1).

Рис. 1. Пример формирования линии .

Для примера: N=11, M=6.

Пусть , – число точек множества между точками множества , тогда справедливы следующие соотношения:

1. - первые и последние точки множеств и совпадают;

2. - узловые точки линий и совпадают.

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

(1)

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

Так как общее число точек множества равно , то нетрудно заключить, что если первые точек последовательностей совпадают, то интервал между последними точками и будет содержать точек множества , и, наоборот, если последние точек последовательностей совпадают, то интервал между первыми точками и будет содержать точек множества . Кроме того, общее число точек – N. Таким образом, ограничения, накладываемые на аргумент оптимизации, будут иметь вид:

, - целое число. (2)

. (3)

Представление критерия (1) в виде суммы дает основание использовать принцип метода дискретного динамического программирования [3; 4].

Решение данной оптимизационной задачи удобно представить в виде ограниченного графа на сетке решений (рис. 2) [2; 5].

Рис. 2. Граф решения задачи методом дискретного динамического программирования.

Для примера:

Красной пунктирной линией отмечены «условно» оптимальные пути,

красной линией отмечен оптимальный путь.

По горизонтальной оси будем откладывать уровни решения задачи, причем число уровней соответствует числу точек множества ; по вертикальной оси – точки множества , в которые можно попасть на i-м уровне. Очевидно, в силу ограничений (2) и (3), каждый уровень (кроме первого и последнего) содержит точек.

Так как на первом уровне имеется единственная точка , то в точку второго уровня возможно попасть только единственным путем (рис. 2). При этом каждой точке уровня 2 будет соответствовать площадь фигуры , опирающейся на хорду между точками и (рис. 1). Значения этих площадей запоминаем.

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

. (4)

(5)

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

, (6)

(7)

Полученные значения , запоминаем. На рисунке в качестве примера оптимальные пути для точек уровня 3 выделены красным цветом.

Описанную выше процедуру формирования точек уровня 3 повторяем для уровней В результате для уровня будем иметь следующие соотношения:

, (9)

(10)

Полученные значения , запоминаем.

Последний уровень M имеет только одну точку , попасть в которую можно из точек предыдущего уровня (рис. 2). Причем каждому пути будет соответствовать значение площади:

(11)

Найдем единственный путь, обеспечивающий минимум критерия (11):

, (12)

(13)

Используя соотношения (12), (9) и (6), пройдем весь путь по оптимальным точкам в обратном направлении:

(14)

Перечисленная в (14) последовательность будет оптимальным набором точек множества , обеспечивающих минимум критерия (1).

Зная номера точек множества , входящих в множество , нетрудно найти оптимальное число точек между узлами .

Приведенный алгоритм может быть применен в информационных системах различного назначения для «фильтрации» большого объема данных при обработке линейных объектов. В частности, маршрутов (треков), полученных с помощью автоматизированных средств записи перемещения объектов (GPS/ГЛОНАСС-приемники), для уменьшения времени обработки изображений различных линейных объектов в ГИС.

Кроме того, многие специализированные навигационные устройства позволяют загружать в память пути (треки) с ограниченным количеством точек (например, максимальное количество точек пути, которые можно загрузить в популярные устройства серии FORERUNNER производства компании GARMIN составляет 500 точек). Приведенный метод позволяет осуществлять предварительную обработку данных для загрузки в такие устройства [1]. Особенностью метода является максимальное сохранение степени кривизны исходного линейного объекта при заданном уровне фильтрации.

Рецензенты:

Загребаев Андрей Маркоянович, д.т.н., профессор, Национальный исследовательский ядерный университет (МИФИ), г. Москва.

Крянев Александр Витальевич, д.ф-м.н., профессор, Национальный исследовательский ядерный университет (МИФИ), г. Москва.