Методы машинного обучения для построения трехмерных моделей антропогенных сцен

Московский государственный университет имени М. В. Ломоносова

Факультет вычислительной математики и кибернетики

На правах рукописи

Баринова Ольга Вячеславовна

Методы машинного обучения для построения трехмерных моделей антропогенных сцен

Специальность 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени

кандидата физико-математических наук

Москва – 2010

Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: Доктор физико-математических наук, профессор,

член-корреспондент РАН

Рудаков К. В.

Официальные оппоненты: Доктор физико-математических наук, профессор

кафедры компьютерных методов физики

физического факультета

МГУ имени М. В. Ломоносова

Чуличков А. И.;

Кандидат технических наук, доцент кафедры автоматики и телемеханики

Тульского государственного университета

Копылов А. В.

Ведущая организация: Институт прикладной математики РАН

имени М. В. Келдыша.

Защита состоится «17 декабря» 2010 г в 11 часов на заседании диссертационного совета

Д 501.001.44 в Московском государственном университете по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ.

С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ имени М. В. Ломоносова http://www.cmc.msu.ru в разделе «Наука» - «Работа диссертационных советов» -

«Д 501.001.44».

Автореферат разослан 17 ноября 2010 г.

Учёный секретарь

диссертационного совета

профессор Трифонов Н. П.

Общая характеристика работы

Объект исследования, актуальность и структура работы

Одной из задач компьютерного зрения является задача извлечения информации о трехмерной структуре сцены из двумерных изображений. С развитием компьютерного зрения появились методы, позволяющие анализировать геометрию трехмерных сцен всего лишь по одному двумерному изображению. Класс изображений антропогенных сцен (городские сцены, снимки, сделанные в помещениях) представляет особый интерес, поскольку фотографии антропогенных сцен составляют большой процент любительских фотографий, и, кроме того, они часто содержат большое число линий, которые являются проекциями параллельных в трехмерной сцене прямых, лежащих на одной плоскости (например, линии границ окон зданий, границы стен зданий, дорожная разметка). Анализ геометрии антропогенных сцен используется в системах поиска объектов и распознавания для повышения точности и надежности их работы 1. Также анализ геометрии антропогенных сцен по одному двумерному изображению используется для ориентации в пространстве роботов с одной камерой2, построении трехмерных компьютерных моделей зданий для создания трехмерных карт3.

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

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

Как было сказано выше, линии, параллельные в реальной сцене, предоставляют ценную информацию для анализа геометрии антропогенных сцен. Однако существующие методы поиска прямых линий, в частности широко используемый метод Хафа6, и группировки их в семейства параллельных прямых7 8, не обладают достаточной точностью и надежностью. Во второй главе работы предлагается новый метод поиска прямых линий на карте краев изображения, а также метод их группировки в семейства параллельных линий, оба метода основаны на использовании аппарата графических моделей. В отличие от метода Хафа6, в предложенном методе поиска прямых линий не требуется решать проблему нахождения локальных максимумов, поэтому метод не требует использования таких эвристик, как подавление не-максимумов.

Согласно правилам перспективной проекции, проекции копланарных параллельных прямых пересекаются в одной точке на плоскости изображения, которая называется точкой схода9. Точка схода задает направление прямых линий и соответствующих плоскостей в трехмерном пространстве. Если на изображении присутствуют несколько семейств параллельных линий, лежащих на разных плоскостях в трехмерном пространстве, соответствующие им точки схода лежат на одной и той же прямой. Изображения антропогенных сцен часто содержат несколько семейств горизонтальных линий, лежащих на разных вертикальных плоскостях (например, линии окон лежат на стенах домов). В таком случае прямая, которая содержит соответствующие точки схода, называется горизонтом. Проекции параллельных вертикальных линий пересекаются в точке, которая называется зенитом. Во второй главе работы предлагается новый метод поиска геометрических примитивов различных уровней (прямые линии, точки схода, зенит и горизонт) в рамках одной вероятностной модели. Поиск оценки максимума апостериорной вероятности для предложенной вероятностной модели осуществляется методами дискретной оптимизации. В отличие от существующих методов7 8, где геометрические примитивы различных уровней обнаруживаются последовательно, в предлагаемом методе они обнаруживаются одновременно, что позволяет избежать распространения ошибок и добиться более высокой точности и надежности метода.

Как правило, городскую сцену можно представить упрощенной трехмерной моделью, которая состоит из нескольких плоскостей, соответствующих земле и стенам зданий10. Существующие методы построения таких трехмерных моделей10 11 работают недостаточно надежно и не позволяют получать модели приемлемого визуального качества. В третьей главе работы предлагается алгоритм автоматического построения трехмерных моделей по одной фотографии антропогенной сцены. Предложенный метод основан на распознавании образов и использует алгоритм машинного обучения, предложенный в первой главе работы. Поиск оптимальных параметров трехмерной модели сводится к оценке максимума апостериорной вероятности в графической модели условного случайного поля12 и осуществляется методами дискретной оптимизации. Ориентация вертикальных плоскостей модели определяется на основе анализа прямых линий и точек схода. Предложенный метод позволяет получать трехмерные модели антропогенных сцен более высоко визуального качества по сравнению с существующими методами10 11.

Цель диссертационной работы

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

Основные задачи работы:

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

Научная новизна работы

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

Также в работе представлена новая новая вероятностная формулировка для поиска нескольких объектов на изображениях, в отличие от преобразования Хафа, не требующая поиска локальных максимумов и применения постобработки. Также предложен метод для решения задачи геометрического парсинга изображения, который одновременно осуществляет поиск геометрических примитивов разных уровней. В отличие от существующих методов поиска геометрических примитивов, работающих по принципу «снизу вверх», предложенный метод осуществляет поиск примитивов разного уровня в рамках одной вероятностной модели, что позволяет избежать распространения ошибок.

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

Практическая значимость

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

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

На основе разработанных методов бустинга создана система автоматической трехмерной реконструкции городских сцен по одной фотографии. Данная система была разработана по заказу корпорации Samsung в ходе совместного проекта лаборатории Компьютерной Графики и Мультимедиа МГУ и Samsung Advanced Institute of Technology. Метод трехмерной реконструкции, лежащий в основе системы, запатентован в России [14, 15], США [16] и Южной Корее [17].

Личный вклад автора

Автором разработаны метод обучения по прецедентам с вероятностными входами на основе бустинга, а также получено его теоретическое обоснование. Автором были разработаны и реализованы методы поиска прямых линий на изображениях и геометрического парсинга изображений. Под руководством автора и при непосредственном участии автора разработана система трехмерной реконструкции городских сцен по одной фотографии, в которой применены разработанные методы бустинга с вероятностными входами.

Результаты и положения, выносимые на защиту

На защиту выносятся следующие основные результаты и положения:

1. Новый алгоритм машинного обучения (machine learning). Новые уточненные оценки обобщающей способности для линейных комбинаций классификаторов и доказано, что предложенный алгоритм минимизирует эти оценки.
2. Новый метод геометрического парсинга изображений, позволяющий находить геометрические примитивы разных уровней (пиксели краев, прямые линии, точки схода, зенит и горизонт) в рамках единой вероятностной модели, вывод в которой осуществляется методами дискретной оптимизации.
3. Новый метод автоматического построения трехмерных моделей антропогенных сцен по одной фотографии на основе машинного обучения и дискретной оптимизации.

Апробация работы

Результаты работы докладывались и обсуждались на:

• научном семинаре 6th Annual Watson Workshop “Emerging Leaders in Multimedia and Signal Processing”, в исследовательском центре IBM, США, Хоторн;
• научном семинаре VASC - The Vision and Autonomous Systems Center в университете Карнеги-Меллон, США, Питтсбург, 2010;
• научном семинаре Joint Institutes Workshop INRIA - Microsoft Joint Center, Франция, Орсэ;
• научном семинаре по компьютерной графике и мультимедиа под руководством к. ф. м. н., доц. Ю. М. Баяковского (ф-т ВМК МГУ), Россия, Москва, 2009;
• научном семинаре отдела Интеллектуальных систем ВЦ РАН под руководствм чл. корр. РАН, д. ф.-м. н., проф. К. В. Рудакова, Россия, Москва, 2009;
• научном семинаре кафедры АСВК ВМК МГУ под руководством Л. Н. Королева, Россия, Москва, 2009;
• международной конференции «European Conference on Computer Vision», Ираклион, Греция, 2010;
• международной конференции «Computer Vision And Pattern Recognition», Сан Франциско, США, 2010;
• 14-ой Всероссийской Конференции «Математические Методы Распознавания Образов», Суздаль, 2009;
• международной конференции «Machine Learning and Data Mining in Pattern Recognition», Лейпциг, Германия, 2009;
• международной конференции «European Conference on Computer Vision», Марсель, Франция, 2008;
• 18-ой международной конференции по компьютерной графике и машинному зрению «Graphicon-2008», Москва, Россия, 2008;
• 7-ой международной конференции «Интеллектуализация обработки информации», Алушта, Украина, 2008;
• юбилейной 50-ой научной конференции МФТИ, Долгопрудный, Россия, 2007;
• 13-ой всероссийской конференции «Математические Методы Распознавания Образов», Зеленогорсий район, Пансионат Гелиос, 2007;
• 17-ой международной конференции по компьютерной графике и машинному зрению «Graphicon-2007», Москва, Россия, 2007;
• международной конференции «European Conference on Machine Learning», Варшава, Польша, 2007;

Публикации

Всего автором диссертации опубликовано 25 научных работ, из них 12 по результатам диссертации, включая 2 статьи в рецензируемых научных журналов из списка ВАК [1,2], 6 статей в сборниках международных научных конференций [3, 3, 6, 7, 9, 13], 1 статью в сборнике всероссийской научной конференции [5] и 3 тезисные публикации в сборниках трудов международных и всероссийских конференций [8, 10, 11]. Автор диссертационной работы является соавтором 4 патентов в России, США и Южной Корее.

Объем диссертации

Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Содержание работы изложено на 155 страницах. Список литературы включает 122 наименования. В работе содержится 33 рисунка и 6 таблиц.

Содержание работы

Во введении формулируются цели и задачи диссертации, показывается актуальность, научная новизна и практическая значимость работы. Описывается структура диссертации.

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

В первом разделе главы рассматривается задача классификации и проблема переобучения.

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

При использовании такого подхода на практике исследователи столкнулись с проблемой переобучения. Чем больше у алгоритма свободных параметров, тем меньшего числа ошибок на обучении можно добиться путём оптимизации. Однако по мере нарастания сложности модели «оптимальные» алгоритмы начинают слишком хорошо подстраиваться под конкретные данные, улавливая не только черты восстанавливаемой зависимости, но и ошибки измерения обучающей выборки, и погрешность самой модели. В результате ухудшается качество работы алгоритма вне обучающей выборки, или, иными словами, его способность к обобщению.

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

(a)	(b)