АВТОМАТИЧЕСКОЕ ВЫДЕЛЕНИЕ ОБЪЕКТОВ В ДАННЫХ ЛАЗЕРНОГО СКАНИРОВАНИЯ Роман ШАПОВАЛОВ Научный руководитель: к.ф.-м.н., н.с. Антон КОНУШИН 24 мая 2010

Применение лазерного сканирования Навигация мобильных роботов Создание моделей зданий Картография и паспортизация Контроль качества продукции Сохранение культурного наследия 2

Цели работы Провести обзор методов классификации лазерных сканов Разработать алгоритм классификации лазерных сканов на основе машинного обучения Реализовать этот алгоритм в системе классификации лазерных сканов 3

Постановка задачи Вход – набор точек трёхмерного пространства Выход – метки классов, сопоставленные каждой точке 4

Формальная постановка задачи Стадия обучения: – Вход: множество четвёрок (x, y, z, c) (x, y, z) R 3 – точки облака c {1, …, K} – метки классов – Выход: параметры алгоритма классификации Стадия классификации: – Вход: вектор троек ((x 1, y 1, z 1 ), (x 2, y 2, z 2 ), …, (x 1, y 1, z 1 )) – Выход: вектор (c 1, c 2, …, c n ) 5

Данные для сегментации Данные – сцены, снятые вне помещений – Аэросъёмка – Съёмка с транспорта – Стационарная съёмка Классы: – Поверхность земли – Здания – Растительность – Транспорт – и т.д. 6

Критерий качества F-мера для каждого класса – Корректна для несбалансированной выборки 7 Классификатор принял H 0 Классификатор отверг H 0 H 0 вернаTPFP H 0 не вернаTNFN

Ассоциативные Марковские сети [Anguelov, 2005] [Munoz, 2008] Минимизируется функция энергии Потенциалы – линейная комбинация признаков: – Ассоциативные парные потенциалы: log φ(k, l) = 0 при k l Существующие методы 8

Схема метода Предобработка – Построение индекса; пересегментация Назначение потенциалов – Унарные потенциалы: рандомизированные деревья – Неассоциативные парные потенциалы Классификация – Вывод в Марковской сети: TRW-S [Kolmogorov, 2006] 9

Унарные потенциалы Дескриптор «Спин-изображения» Признаки матрицы ковариаций – Спектральные признаки – Признаки направления Цилиндрические признаки 10 Выход мультиклассового классификатора «Рандомизированные деревья»

Парные потенциалы Линейная комбинация признаков: – Угол между нормалями в точках – Угол наклона к горизонту отрезка, соединяющего точки, и его абсолютное значение – Расстояние между точками Рассматриваются также неассоциативные парные потенциалы вида φ(k, l) при k l 11

Научная новизна Пересегментация – Ускоряет классификацию на порядки – Признаки рёбер (направление, длина) становятся статистически значимыми Неассоциативные парные потенциалы – Позволяют выразить отношения между объектами разных классов, такие как «дерево находится выше земли» 12

Пример результата классификации Красный – земля, чёрный – крыша, зелёный – дерево, синий – автомобиль, голубой – кусты 13 Верная разметка Ассоциативная Марковская сеть Предлагаемый метод

Экспериментальное сравнение Лазерный скан, полученный аэросъёмкой Миллион точек, 30 тысяч сегментов 14 лучше предло- женный метод

Программная реализация C++ В рамках системы реализована функция детектирования поверхности земли на данных, снятых с транспортного средства – Применяется в НПО «Регион» для картографирования дорожного покрытия 15

Результаты Проведён обзор методов классификации лазерных сканов Разработан алгоритм классификации лазерных сканов на основе неассоциативных Марковских сетей Реализована система классификации лазерных сканов с произвольными классами Результаты опубликованы 16

Публикации по теме дипломной работы А. Велижев, Р. Шаповалов, Д. Потапов, Е. Третьяк, А. Конушин, «Автоматическая сегментация облаков точек на основе элементов поверхности», GraphiCon, Moscow: Р. Шаповалов, «Классификация трёхмерных облаков точек с помощью неассоциативных Марковских сетей», Ломоносов-2010, Москва R. Shapovalov, A. Velizhev, O. Barinova, A. Konushin, «Using Non-Associative Markov Networks for Point Cloud Classification», Photogrammetric Computer Vision and Image Analysis, Paris:

18 СПАСИБО ЗА ВНИМАНИЕ!

Результат классификации 19

Лазерные сканы и изображения Преимущества: Присутствует информация о трёхмерной структуре сцены Инвариантность относительно освещения и погодных условий Недостатки: Объект может быть загорожен другими объектами или сам собой Сканы зашумлены и разрежены Часто отсутствует цветовая информация Затруднена обработка с помощью стандартных средств ввода-вывода 20