Модифицированный алгоритм сглаживания точек маршрута

128

ISSN 2223-1560. Известия Юго-Западного государственного университета. 2015. № 4 (61).

Размещено на http://www.allbest.ru/

Модифицированный алгоритм сглаживания точек маршрута

Введение

маршрут алгоритм линеаризация

С вычислительно-мехатронной точки зрения робототехническая машина (РТМ) представляются дискретными исполнителями, имеющими память действий и осуществляющих плановые и немонотонные движения по двух-, трехмерной цифровой карте местности (ЦКМ). С одной стороны, деятельность интеллектуальных машин опирается на планируемые действия, в том числе детерминированно вычисляемые значения (обороты двигателей, координаты машины, управление приводом, расход топлива, координаты цели и др.). С другой стороны, достижение целевой позиции связывается с немонотонным характером действий интеллектуальных машин, проявляющимся в автономных перемещениях машин в текущей обстановке, и выполнении при этом значительного объема вычислений входных изображений объектов, собственных позиций, позиций цели и препятствий, картографических трехмерных сцен [1].

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

1.Алгоритм Рамера-Дугласа-Пекера

В робототехнике классический алгоритм Рамера-Дугласа-Пекера применяется для линеаризации движения робота с учетом препятствий и возможных участков маршрута их обхода. Также данный алгоритм может применяться для исключения ошибочных измерений параметра средствами сканирования/измерения различной природы. В первую очередь речь идет об измерении движущимся РТМ расстояний до объектов на пересеченной местности. Ошибочное отражение лазерного луча от внешнего объекта, искажение изображения из-за угла смещения РТК, случайное или целенаправленное воздействие помех приводят к разбросу измеряемого значения и как следствие - к необходимости выделения информативных точек в исходном множестве. С теоретической точки зрения количество измеряемых данных не является ограничением алгоритма. С практической точки зрения речь идет о размерности исходного множества количеством 10-16 точек.

Классический алгоритм Рамера-Дуг-ласа-Пекера применяется для обработки множества точек, аппроксимированных ломанной, проходящей через подмножество базовых (опорных) точек исходного множества [2]. Исходное множество точек - это результат измерения параметра с учетом возможных погрешностей и ошибок. Большая размерность исходного множества точек является избыточной.

Для повышения оперативности обработки интерес представляют только информативные точки, задающие градиент изменения параметра по отношению к соседним значениям. Алгоритм Рамера-Дугласа-Пекера реализует сглаживание исходной многозвенной кусочно-линей-ной кривой с меньшим количеством точек, т.е. алгоритм осуществляет упрощенную аппроксимацию [2]. Точки, вошедшие в конечную кусочно-линейной аппроксимированную кривую, считаются информативно-значимыми (опорными) точ-ками. Точки, не вошедшие в конечную кривую, получили название «выколотые». Их пропуск не изменяет градиент перемещения по кривой между соседними точками.

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

Аппроксимация осуществляется с заданной точностью (>0). Точность соотносится с величиной перпендикуляра (отклонения) до прямой, соединяющей граничные (первую и последнюю) точки ломанной. В частности, если значение отклонения меньше предела точности, то такая точка располагается в коридоре погрешности, т.е. является несущественной. Ее исключение из исходного множества не изменяет градиента между соседними точками. С другой стороны, если значение отклонения больше предела точности, то позиция такой точки оказывает значимое влияние на градиент перемещения между соседними точками. Данную точку следует сохранить как информативно-значимую. Тем не менее, в такой интерпретации алгоритм сглаживания не применяется: наперед заданное значение точности (>0) никак не связано с фактическими отклонениями точек.

В результате классический алгоритм Рамера-Дугласа-Пекера предваряется этапом вычисления максимального отклонения, определения характеристик такой точки (индекс, координаты, знак отклонения.).

Основу вычисления определяет шаг поиска точки с максимальным отклонением. Далее алгоритм рекурсивно делит многозвенную ломанную на части. Для этого применяются следующие 2 правила:

а) если b_max < е, то все точки, у которых index < index_max, исключаются из подмножества опорных точек, а получившаяся прямая между первой и точкой с индексом index_max сглаживает кривую с точностью не ниже е. Далее за первую точку принимается найденная опорная точка, имеющая index_max. Процесс сглаживания начинается заново, включая шаг поиска новой точки с максимальным отклонением;

б) если b_max > е, то алгоритм рекурсивно вызывает себя на 2 наборах:

- набор от первой точки множества до точки с индексом index_max ;

- набор от точки с индексом index_max до последней точки множества (данная точка будет отмечена как опорная).

Визуализация 5 шагов работы классического алгоритма приведена на рис. 1. В результате достигнуто 50% сокращение точек ломанной кривой.

Псевдокод классического алгоритма в рекурсивной реализации имеет следующий вид:

function DouglasPeucker(PointList[], epsilon)

//Находим точку с максимальным расстоянием от прямой между первой и последней точками набора

dmax = 0

index = 0

for i = 2 to (length(PointList) - 1)

d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))

if d > dmax

index = i

dmax = d

end

end

//Если максимальная дистанция больше, чем epsilon, то рекурсивно вызываем её на участках

if dmax >= epsilon

//Recursive call

recResults1[] = DouglasPeucker(PointList[1...index], epsilon)

recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

// Строим итоговый набор точек

ResultList[] =

{recResults1[1...end-1]

recResults2[1...end]}

else

ResultList[] = {PointList[1], PointList[end]}

end

// Возвращаем результат

return ResultList[]

end

Рис.1. Шаги работы классического алгоритма Рамера-Дугласа-Пекера

2.Модифицированный алгоритм сглаживания точек маршрута

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

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

В алгоритме модификации подлежит второе правило рекурсивного деления ломанной на части. При выполнении условия b_max > е выполняется проверка соотношений:

b_max/ b_min> , (1)

b_max/ b_min> е, (2)

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

Если конъюнкция условий (1) и (2) ложная, то выполняются шаги классического алгоритма сглаживания. Если конъюнкция условий (1) и (2) истинная, то выполняется дополнительная проверка количественных соотношений отклонений точек:

count_max/n<₁, (3)

count_min/n>₂. (4)

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

При выполнении условий (3) и (4) точки трактуются как шум в исходном наборе, который подлежит удалению. В результате будет сформирована сокращенная ломанная без «зашумленных» точек.

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

Например, для списка из 10 точек A, B, C, D, E, F, I, G, H,J (рис. 2) вычисляются отклонения:

b₂= b₅= b₆= b₉=2

b₃= b₇=5

b₄=7

b₈=3.

В отличие от классического алгоритма анализируются не все отклонения b_i (i=2-8), а лишь первые k отклонений (k=3). В результате предварительно выбирается точка D: b_max=7, index_max=4.

Рис. 2. Сглаживание с отсечением точки-шума D

Тем не менее, указанная фиксированная погрешность е=5 показывает, что точка D с индексом index_max=4 не может считаться опорной при сглаживании, так как понимается как шум. В итоге за первую опорную точку выбирается точка С c index_max=3. Процесс выбора опорной точки С и сглаживания отмечен красными линиями, а сглаженная ломанная указана штриховым вектором.

Рисунки 3 и 4 отражают последующие шаги работы модифицированного ал-горитма сглаживания (синий и зленный цвета соответственно). Также анализируются первые k точек и выбирают максимальное отклонение, но не превышающее значение погрешности.

Алгоритмическая особенность сглаживания с отсечением точки-шума I связана с тем, что в случае, если точка-шум является последней среди k анализируемых, то за опорную берется k+1 точка.

Рис. 3. Сглаживание с отсечением точки-шума I

Рис. 4. Сглаживание последнего набора точек

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

Для сравнения на рис. 6 приведена сглаженная кривая как результат работы классического алгоритма Рамера-Дугласа-Пекера.

Анализ рис.5 и рис.6 показывает, что количественно сглаженные ломанные имеют одинаковое число участков - 4. Для классического алгоритма - это путь ADFJ. Для модифицированного алгоритма - это путь ACGJ. Тем не менее, средний размах отклонений по ADFJ и ACGJ составил 34% и 22% соответственно. В результате движение робота по сглаженной ломанной по модифицированному алгоритму будет отличаться лучшими ходовыми качествами, что необходимо при работе в опасной, техногенной среде без присутствия оператора [3, 4, 5]. Также данный алгоритм имеет применение для организации поиска в пространстве состояний, понимаемом как неориентированный граф [6].

Рис. 5. Итоговая сглаженная ломанная по модифицированному алгоритму

Рис.6. Сглаженная ломанная по классическому алгоритму Рамера-Дугласа-Пекера

Вывод

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

Список литературы

1. Емельянов С.Г., Курочкин А.Г., Гривачев А.В. Модифицированная модель Туэ как базовая модель координации группы машин при разрешении конфликтов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: сборник материалов XII Междунар. науч.-техн. конф. - Курск, 2015. - С. 129-132.

2. Хаггарти Р. Дискретная математика для программистов. - М.: Техносфера, 2005. - 400 с.

3. Курочкин А.Г., Емельянов С.Г., Бородин М.В. Продукционная модель для координации бесконфликтного расположения группы автономных роботов // Информационно-измерительные и управляющие системы. - 2015. - Т.13, N6. - С. 10-14.

4. Гривачев А.В., Емельянов С.Г., Бородин М.В. Структурно-функциональ-ная схема распознавания и оценки риска в системе управления роботизированными много-функциональных машинами // Информационно-измерительные и и управляющие системы. - 2016. - Т.12, N5. - С. 17-19.

Размещено на Allbest.ru