Способ сегментирования лазерных сканов и система для его осуществления
Владельцы патента RU 2606370:
Общество с ограниченной ответственностью "РОБОСИВИ" (ООО "РОБОСИВИ") (RU)
Изобретения относятся к области обработки цифровых данных на основе использования сканирующих устройств и может найти применение для лазерных сканов (ЛС) в системах позиционирования и навигации автономных машин погрузчиков. Технический результат – повышение быстродействия. Для этого процесс сегментирования двумерного ЛС содержит этапы, на которых: разворачивают ЛС в одномерный сигнал (массив значений); обрабатывают полученный массив с помощью численного дифференцирования значений массива; получают массив значений дифференциала и второго дифференциала, который разбивается на сегменты в виде массива массивов значений, причем каждый упомянутый сегмент представляет собой набор точек, принадлежащих отдельному объекту на ЛС; определяют для каждого сегмента крайние точки, характеризующие объект; определяют углы от точки начала отсчета ЛС до каждой из упомянутых крайних точек объекта (крайние углы); осуществляют определение значений центральных углов объектов с помощью полученных значений крайних углов методом подсчета среднего значения; создают список, который включает в себя значения углов от точки начала отсчета ЛС до каждой из крайних точек, центральный угол и соответствующий объекту набор точек, характеризующих объект. 2 н. и 2 з.п. ф-лы, 4 ил.
Область техники
Заявленная группа изобретений относится к области обработки цифровых данных, в частности, лазерных сканов (ЛС), которые применяются в системах навигации автономных машин погрузчиков при их перемещении внутри помещений.
Известен способ сегментации и выделения геометрических примитивов из 2D лазерных сканов для применения в приложениях, предназначенных для роботизированных машин (Cristiano Premebida, Urbano Nunes «SEGMENTATION AND GEOMETRIC PRIMITIVES EXTRACTION FROM 2D LASER RANGE DATA FOR MOBILE ROBOT APPLICATIONS»).
В известном способе границы объектов определяются медленным последовательным сравнением расстояний между двумя соседними точками с использованием модифицированного фильтра Калмана. Основным недостатком известного решения является медленная скорость работы при определении границ объекта, который заключается в сравнении сегментов между кадрами.
Раскрытие изобретения
Задачей, на решение которой направлено заявленное изобретение, является создание способа сегментирования лазерных сканов, позволяющего с более высокой скоростью определить границы объектов, представленных на них.
Техническим результатом является повышение скорости сегментирования ЛС и скорости поиска соответствий между объектами в последовательных кадрах.
Технический результат достигается за счет способа сегментирования двумерного лазерного скана (ЛС), содержащий этапы, на которых:
- разворачивают ЛС в одномерный сигнал (массив значений);
- обрабатывают полученный массив с помощью численного дифференцирования значений массива;
- получают массив значений дифференциала и второго дифференциала, который разбивается на сегменты в виде массива массивов значений, причем каждый упомянутый сегмент представляет собой набор точек, принадлежащих отдельному объекту на ЛС;
- определяют для каждого сегмента крайние точки, характеризующие объект;
- определяют углы от точки начала отсчета ЛС до каждой из упомянутых крайних точек объекта (крайние углы);
- осуществляют определение значений центральных углов объектов с помощью полученных значений крайних углов методом подсчета среднего значения;
- создают список, который включает в себя значения углов от точки начала отсчета ЛС до каждой из крайних точек, центральный угол и соответствующий объекту набор точек, характеризующих объект.
Технический результат достигается так же за счет способа сопровождения распознанных объектов на ЛС во времени, содержащий этапы, на которых:
- осуществляют сегментацию ЛС с помощью способа по п. 1 и получают новый список объектов;
- проверяют, пуст ли текущий список объектов;
- если текущий список объектов пуст, то всем объектам из нового списка выдают уникальные УИД и все объекты вместе с УИД добавляют в текущий список, иначе осуществляют сравнение объектов из текущего и нового списков с помощью алгоритма ближайшего соседа, при котором происходит сравнение текущего и нового списков, содержащих значения центральных углов объектов от точки начала ЛС, и получают список соответствий между объектами в текущем и новом списках;
- проверяют, пуст ли новый список объектов, и если он пуст, то удаляют оставшиеся в текущем списке объекты, которые не были сопоставлены с каким-либо объектом в новом списке, иначе
- выбирают объект из нового списка и проверяют наличие соответствия этого объекта какому-либо объекту из текущего списка и если в текущем списке существует подобный объект, то обновляют параметры (набор точек, крайние углы, центральный угол) этого объекта в текущем списке на основе параметров объекта в новом списке, в противном случае объект считают появившимся в поле зрения, ему присваивают новый УИД и объект добавляют в текущий список;
- убирают объект из нового списка и итеративно повторяют этапы способа с этапа проверки, пуст ли текущий список объектов, до момента, когда новый список опустеет и все несопоставленные объекты удалятся из текущего списка.
Заявленный результат достигается также за счет системы, для сегментирования двумерного ЛС, содержащей по меньшей мере один процессор, по меньшей мере одно средство памяти, содержащее машиночитаемый инструкции, которые при их исполнении побуждают по меньшей мере один процессор выполнять вышеупомянутый способ сегментирования ЛС.
Описание графических изображений
Фиг. 1 иллюстрирует крупные шаги этапов способа по распознаванию объектов на последовательных ЛС.
Фиг. 2 иллюстрирует общую схему последовательности действий при выполнении способа сегментации ЛС.
Фиг. 3 иллюстрирует общую схему последовательности действий при сопровождении объектов.
Фиг. 4 иллюстрирует систему для выполнения заявленного способа.
Осуществление изобретения
Согласно Фиг. 1 заявленное изобретение включает в себя три основных этапа, которые выполняются последовательно. На этапе 100 осуществляется получение ЛС для его последующего сегментирования на этапе 200, определения объектов на ЛС и их последующего анализа и сопровождения на этапе 300.
Каждая точка скана представляется в виде единственного значения - удаленности точки от сканера. Точки упорядочиваются по возрастанию угла сканирования. Согласно Фиг. 2 при осуществлении способа сегментирования 200 на этапе 201 выполняется разворачивание (преобразование) ЛС в одномерный сигнал (массив значений). Способ сегментации предназначен для быстрого анализа ЛС и выделения в нем границ объектов в целях использования для их идентификации и последующего сопровождения.
После разворачивания ЛС (этап 201) на этапе 202 выполняется обработка сигнала (массива значений), полученного на этапе 100, для чего выполняется численное дифференцирование значений массива, а также повторное численное дифференцирование массива дифференциалов. Создается два новых массива значений, короче, соответственно, на один и на два элемента, чем оригинальный ЛС. В полученный первый массив 2021 записывается значение разности удаленности точки с тем же индексом и точки с индексом на единицу больше. Во второй массив 2022 записывается значение разности значения из первого массива 2021 с тем же индексом и значения из первого массива 2021 с индексом на единицу больше. В двух полученных массивах дифференциала и второго дифференциала значения сравниваются с заданными порогами для каждого массива. Точки из массива ЛС, соответствующие значениям, превышающим порог в двух других массивах 2021 и 2022, считаются границами объекта, точки, лежащие между ними, собираются в отдельные массивы, соответствующие разным объектам.
На этапе 203 определяют для каждого сегмента крайние точки, характеризующие объект, которые являются, в частности, крайней левой и крайней правой точками из набора точек, характеризующих объект. Поскольку массив ЛС отсортирован, такими точками будут являться первая и последняя точки из сегмента в качестве начала и конца объекта.
На этапе 204 для каждого объекта, выявленного на ЛС, рассчитывают углы от начала отсчета ЛС до крайних точек.
На этапе 205 осуществляют определение значений центральных углов объектов с помощью полученных на этапе 204 крайних углов методом подсчета среднего значения.
На этапе 206 создается новый список объектов, который включает в себя информацию, полученную на предыдущих этапах, в частности значения углов от точки начала отсчета ЛС до каждой из крайних точек, центральный угол и соответствующий объекту набор точек, характеризующих объект.
На Фиг. 3 представлена последовательность этапов способа 300, применяющегося для сопровождения объектов на ЛС. Способ 300 использует данные, полученные при осуществлении способа сегментирования 200.
На этапе 301 проверяется, пуст ли текущий список объектов.
Если текущий список объектов пуст, то осуществляется переход на этап 302 на котором всем объектам из нового списка выдаются уникальные УИД, и все объекты вместе с УИД добавляются в текущий список. Иначе осуществляется переход на этап 303.
На этапе 303 осуществляют сравнение объектов из текущего и нового списка с помощью алгоритма ближайшего соседа (см. ниже), при котором происходит сравнение текущего и нового списков, содержащих значения центральных углов объектов от точки начала ЛС. Новый список был получен при осуществлении способа сегментирования 200. После сравнения получается список соответствий между объектами в текущем и новом списках.
Далее на этапе 304 проверяется, пуст ли новый список объектов, и если он пуст, то в этапе 305 удаляются оставшиеся в текущем списке объекты, которые не были сопоставлены с каким-либо объектом в новом списке. Это те объекты, которые не были найдены на новом ЛС. Т.е. считается что эти объекты были утеряны из поля зрения и более не должны сопровождаться.
Если же новый список не пуст, то на этапе 306 выбирается объект из нового списка и на этапе 307 проверяется наличие соответствия этого объекта какому-либо объекту из текущего списка. Если в текущем списке существует подобный объект, то на этапе 308 обновляются параметры (набор точек, крайние углы, центральный угол) этого объекта в текущем списке на основе параметров объекта в новом списке. Если же подобного объекта не получается найти в текущем списке, то объект считается появившимся в поле зрения. Далее на этапе 309 ему присваивается новый УИД и объект добавляется в текущий список.
Далее на этапе 310 объект убирается из нового списка и снова проверяется условие на этапе 304.
Таким образом, последовательно выбираются объекты из нового списка, сопоставляются с объектами из текущего списка и удаляются из нового списка. Через определенное количество итераций новый список опустеет и будет осуществлен переход на этап 305.
Алгоритм ближайшего соседа, примененный к новому и текущему спискам, строит сопоставления между объектами в них.
В общем случае алгоритм ближайшего соседа заключается в следующем, есть два списка, а и b, с количеством элементов соответственно n и m. Для каждого элемента последовательности a (a(i*); i=[1…n]) находится элемент b(j*); j=[1…m] такой, что наименьший среди всех j=[1…m]. Поиск делается перебором всех значений j. Отсюда определяется, что a(i*) и b(j*) - ближайшие соседи. Поскольку количество элементов в последовательностях может быть разным, некоторые элементы могут не получить ближайшего соседа.
В другом частном случае поиск наименьшего 
среди всех j=[1…m] делается с помощью предварительного создания k-d дерева по списку b и дальнейшего использования этого дерева. Т.е. делается несколько уровней кластеризации по углу для списка b, которые отличаются размерами кластеров. Получается дерево кластеров, в котором каждый кластер на определенном уровне содержит 2 или более кластеров уровнем ниже. Поиск по такому дереву кластеров будет происходить быстрее при большом количестве объектов в последовательности b.
Последовательно применяя описанный выше подход к каждому новому ЛС, возможно сопровождать объекты (знать точки, принадлежащие одному и тому же объекту) на протяжении всего времени нахождения объекта в поле зрения сканера. На Фиг. 4 представлен общий вид системы 300 для выполнения процедур сегментирования ЛС.
Система 400 включает в себя один или более вычислительных процессоров 410, одно или более средство памяти 420 (ОЗУ, ПЗУ, NAND, EEPROM и т.п.), одно или более средств для хранения данных 430 (HDD, SSD, флэш-накопители и т.п.), интерфейсы 440 и устройства 450 ввода/вывода, средства коммуникации 460 (LAN, WLAN, irDa и т.п.), соединенные с помощью общей шины данных 470.
Система 400 может реализовываться на базе широко известных IBM PC совместимых устройств, например ПК, ноутбук, мейнфрем, суперкомпьютер и т.п., либо выполняться на базе мобильных вычислительных устройств, например планшета или мобильного телефона.
Система 400 также может являться частью роботизированной машины для обеспечения процесса автономной навигации машин внутри помещений.
1. Способ сегментирования двумерного лазерного скана (ЛС), содержащий этапы, на которых:
- разворачивают ЛС в одномерный сигнал (массив значений);
- обрабатывают полученный массив с помощью численного дифференцирования значений массива;
- получают массив значений дифференциала и второго дифференциала, который разбивается на сегменты в виде массива массивов значений, причем каждый упомянутый сегмент представляет собой набор точек, принадлежащих отдельному объекту на ЛС;
- определяют для каждого сегмента крайние точки, характеризующие объект;
- определяют углы от точки начала отсчета ЛС до каждой из упомянутых крайних точек объекта (крайние углы);
- осуществляют определение значений центральных углов объектов с помощью полученных значений крайних углов методом подсчета среднего значения;
- создают список, который включает в себя значения углов от точки начала отсчета ЛС до каждой из крайних точек, центральный угол и соответствующий объекту набор точек, характеризующих объект.
2. Система для сегментирования двумерного ЛС, содержащая по меньшей мере один процессор, по меньшей мере одно средство памяти, содержащее машиночитаемые инструкции, которые при их исполнении побуждают по меньшей мере один процессор выполнять способ по п. 1.
3. Способ сопровождения распознанных объектов на ЛС во времени, содержащий этапы, на которых:
- осуществляют сегментацию ЛС с помощью способа по п. 1 и получают новый список объектов;
- проверяют, пуст ли текущий список объектов;
- если текущий список объектов пуст, то всем объектам из нового списка выдают уникальные УИД и все объекты вместе с УИД добавляют в текущий список, иначе осуществляют сравнение объектов из текущего и нового списков с помощью алгоритма ближайшего соседа, при котором происходит сравнение текущего и нового списков, содержащих значения центральных углов объектов от точки начала ЛС, и получают список соответствий между объектами в текущем и новом списках;
- проверяют, пуст ли новый список объектов, и если он пуст, то удаляют оставшиеся в текущем списке объекты, которые не были сопоставлены с каким-либо объектом в новом списке, иначе
- выбирают объект из нового списка и проверяют наличие соответствия этого объекта какому-либо объекту из текущего списка и если в текущем списке существует подобный объект, то обновляют параметры (набор точек, крайние углы, центральный угол) этого объекта в текущем списке на основе параметров объекта в новом списке, в противном случае объект считают появившимся в поле зрения, ему присваивают новый УИД и объект добавляют в текущий список;
- убирают объект из нового списка и итеративно повторяют этапы способа с этапа проверки, пуст ли текущий список объектов, до момента, когда новый список опустеет и все несопоставленные объекты удалятся из текущего списка.
4. Способ по п. 3, отличающийся тем, что в алгоритме ближайшего соседа выполняется создание k-d дерева с последующим поиском по нему.
