Автоматическое выделение объектов в данных лазерного сканирования

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

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

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

Формальная постановка задачи
Стадия обучения:
Вход: множество четвёрок (x, y, z, c)
(x, y, z) ∈ R3 – точки облака
c ∈ {1, …, K} – метки классов
Выход: параметры алгоритма классификации
Стадия классификации:
Вход: вектор троек
((x1, y1, z1), (x2, y2, z2), …, (x1, y1, z1))
Выход: вектор (c1, c2, …, cn)

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

Критерий качества
F-мера для каждого класса
Корректна для несбалансированной выборки

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

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

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

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

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

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

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

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

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

Публикации по теме
дипломной работы
А. Велижев, Р. Шаповалов, Д. Потапов, Е. Третьяк, А. Конушин, «Автоматическая сегментация облаков точек на основе элементов поверхности», GraphiCon, Moscow: 2009.
Р. Шаповалов, «Классификация трёхмерных облаков точек с помощью неассоциативных Марковских сетей», Ломоносов-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: 2010.

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

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