Методы машинного обучения для построения трехмерных моделей антропогенных сцен тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

004614895

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

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

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

антропогенных сцен

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

" 2 ДЕН 2010

Москва-2010

004614895

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

Научный руководитель:

Официальные оппоненты:

Доктор физико-математических наук, профессор, член-корреспондент РАН Рудаков К. В.

Доктор физико-математических наук, профессор кафедры компьютерных методов физики физического факультета МГУ имени М. В. Ломоносова Чуличков А. И.;

Кандидат технических наук, доцент автоматики и телемеханики Тульского государственного университета Копылов А. В.

кафе;

Ведущая организация:

Институт прикладной математики РАН имени М. В. Келдыша.

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

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

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

Учёный секретарь диссертационного совета

профессор §¡¿^^7 Трифонов Н. П.

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

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

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

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

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

1 Hoiem, D., Elros, A.A., Hebert, M.: Putting objects in perspective. // International Journal of Computer Vision, 80, ^2008), pp. 2137 - 2144.

2 Saxena, A., Sun, M., Ng, A.: Learning 3-D Scene Structure from a Single Still Image. // In Proc. of 1CCV workshop on 3D representation for Recognition (2007), pp. 1-8.

3 Koutsourakis, P. Simon, L. Teboul, O. Tziritas, G. Paragios, N. Single view reconstruction using shape grammars for urban environments. // In. Proc. IEEE 12th International Conference on Computer Vision (2009), pp. 1795 - 1802

4 Freund Y., Schapire R., A decision-theoretic generalization of on-line learning and an application to boosting. // Journal of Computer and System Sciences, 904 (1995), pp. 23-37.

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

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

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

5 Schapire, R., Freund, Y., Bartlett, P., and Wee Sun Lee.: Boosting the margin: Anew explanation for the effectiveness of voting methods. // Ann. Statist. Volume 26, Number 5 (1998), 1651-1686.

6 Illingworth 3., Kittler J. A survey of the hough transform // Computer Vision, Graphics, and Image Processing Volume 44, Issue 1, October 1988, pp. 87-116.

7 Kosecka, J., Zhang, W.: Video Compass. // In Proc. of European Conference on Computer Vision 7 (2002) pp. 476-491

8 Tardif, J.P.: Non-iterative approach for fast and accurate vanishing point detection. // In: International Conference on Computer Vision. (2009) pp.1250 - 1257.

9 Criminisi A., Reid I., Zisserman A.: Single view metrology. // International Journal on Computer Vision, Volume 40, Number 2, (2000) pp. 123-148.

что позволяет избежать распространения ошибок и добиться более высокой точности и надежности метода.

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

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

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

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

• Разработка алгоритма малшгоюго обучения (шасЫпе \&атт$), более устойчивого к шуму в данных, чем существующие методы.

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

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

10 Hoiem, D., Efros, A.A., Hebert, M: Automatic photo pop-up. // ACM Trans. Graph. 24 (2005) pp. 577-584

11 Saxena, A., Chung, S., Ng, A.: Depth Reconstruction from a Single Still Image. /I International Journal on Computer Vision (2007), Volume 76, Number 1, 53-69

12 Laferty, J., McCallum, A., Pereira, F.: Conditional random fields: Probabilistic models for segmenting and labeling sequence data. // In: Proc, 18th International Conf. on Machine Learning, (2001) pp.282-289

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

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

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

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

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

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

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

На основе разработанных методов бустинга создана система автоматической трехмерной реконструкции городских сцен по одной фотографии. Данная система была разработана по заказу корпорации 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 INRJA - Microsoft Joint Center, Франция, Орсэ;

• научном семинаре по компьютерной графике и мультимедиа под руководством к. ф. м. н., доц. Ю. М. Баяковского (ф-т ВМК МГУ), Россия, Москва, 2009;

• научном семинаре отдела Интеллектуальных систем ВЦ РАН под руководствм чл. корр. РАН, д. ф.-м. н., проф. К. В. Рудакова, Россия, Москва, 2009;

• научном семинаре кафедры АСВК ВМК МГУ под руководством Jl. Н. Королева, Россия, Москва, 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(а) по горизонтальной оси отложено число слабых классификаторов в композиции, построенной стандартным методом буспшга. По вертикальной

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

Ошибка тарификации на тестовой выборке

.4Т

Ошибка классификации на обучающей выборке

Ошибка классификации на тестовой выборке

Ошибка классификации на обучающей выборке

Число итераций алгоритма обучения

Число итераций алгоритма обучения

(а)

(Ь)

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

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

На данный момент наилучшее объяснение хорошей ообщаюшей способности бустинга дает теория отступов (margin theory)13, которая предоставляет верхнюю оценку ошибки классификации, не зависящую от числа слабых классификаторов.

Определние 1. Отступом для объекта (х,у) относительно классификатора f(x) называется величина yf(x).

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

13 Schapire, R., Freond, Y., Baitlett, P., and Wee Sun Lee.: Boosting the margin: A new explanation for the effectiveness of voting methods. In Machine Learning: Proceedings of the Fourteenth International Conference (1997)

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

Теорема (Шапир и др.). Пусть >' - распределение над ХхУ, Пусть 5 - выборка из т объектов, выбранных независимо из распределения р. Предположим, что задан конечный набор слабых классификаторов Н, принимающих значения из интервала^**!. Пусть также задана константа ^>0 Тогда с вероятностью не менее для выбранной случайным образом выборки ^, все функции удовлетворяют следующему неравенству для всех в > 0:

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

Теорема (Шапир и др.) Пусть метод обучения Лс1аВооИ сгенерировал простые гипотезы с ошибками на обучающей выборкеС1' "'Ет. Тогда для любого®, имеем

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

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

14 Freund Y., Sctiapire R-, A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55.1997

!>[yf{x) < 0] < Ps [>/(*) <e] + c(m,\H\,e,ö)

, причем

psb/W ä e] < 27fI

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

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

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

Определение 1. Будем называть задачу бинарной классификации в статистической постановке задачей с перекрывающимися классами, если существует множество ненулевой меры, д.1Я которого обе метки классов имеют, положительную вероятность: К11х)х 1 > о! > 0 г*

«и-ч / ^ . Если множество, на котором оое апостериорные вероятности

Р [ р(+11 .*) х 1! х) > 0] = О -Г Л положительны, имеет меру нуль ,|п 1 " 11 ' , будем говорить, что кчассы не

перекрываются.

Для задач с перекрывающимися классами введем обозначения: /^«»тах^+ЦдОЛ-Ц*)) р^(х) = тш.(Р(+1\х),Р(-1\х))

В первых работах, посвященных бустингу, рассматривалась постановка задачи классификации в рамках концептуального обучения. Авторы алгоритма АсМооэ! отмечали, что для случая перекрывающихся классов "А(1аВооз1 не является оптимальным методом обучения". Следует отметить, что для прикладных задач распознавания образов случай неперекрывающихся классов встречается крайне редко, поскольку представление реальных объектов в виде векторов признаков как правило несовершенно. Основная идея данной работы заключается в том, чтобы свести задачу с перекрывающимися классами к задаче концептуального обучения (или, другими словами, задаче с неперекрывающимися классами).

Определение 2. Будем называть две задачи бинарной классификации эквивалентными, если множества их решений совпадают.

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

Теорема 1. Для любой бинарной задачи классификации с перекрывающимися классами, заданной распределением существует эквивалентная ей задача классификации с

неперекрывающимися классами, заданная распределением ^^ и целевой функцией ^х'Х ^ , где

Р(х) = (а» М-Д*. (*))Р(х)/(1-2В) ^

с(х)^агетту(Р^1х))

Причем для любого произвольного классификатора $ верно следующее соотношение + где в _ ошибт Байгсовского классификатора на

распределении К

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

Предположим, что задан конечный набор слабых классификаторов Н. За множество с обозначим множество всех линейных комбинат)« простых гипотез го 11, где коэффициенты линейной комбинации положительны и их сумма равна 1.

Предположим, что 5 - выборка из т объектов, выбранных независимо из некоторого

распределения над Х*Г. Обозначим за ^^Ь^Х-А,*,)] и = >(*-■>').

Символом Ег(х(х'У>) будем обозначать условное матожидание величины *(Х<У) по ^'при

фиксированном *, то есть Е' = 1 *)х ^1.

Основными теорепиескими результатами работы являются следующие теоремы. Теорема 2. Пусть Р - распределение над ХхГ. Предположим, что задан конечный набор слабых классификаторов Н, принимающих значения из интервала^'^. Пусть также задана константа Пусть 5 - выборка из т объектов, выбранных независимо из

распределения и для каждого объекта известны апостериорные вероятности

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

Ф/(Х) £ 0] 5 В + (1-2В)хЯ5

где В - ошибка Байесовского классификатора на распределении

¿ = -£>.¡.00 1{т,\Н\,в,5) = е(т,]Н\,в,б)-гвЫ^

« ; ' т из Теоремы Шапира.

Теорема 3. Пусть Р - распределение над -УхУ. Предположим, что задан конечный набор сшабых классификаторов Н, принимающих значения из интервача^,+^. Пусть также задана константа <5>0, в>0 Пусть известны оценки апостериорных вероятностей для объектов ю обучающей выборки, удовлетворяющие уаювию: 1л».<л)-Л»Лд:1)|<0>'-1>-".'я_ Тогда верпа следующая верхняя оценка ошибки классификации по обучающей выборке:

р\хГ(г)< о]<

где ' т берется из Теоремы б, т'->

аР(а) непрерывно зависит от а.

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

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

Теорема 4 Пусть предложенный алгоритм построш простые классификаторы с

взвешенными ожидаемыми ошибками на тренировочной выборке "'е':

£,=У"М')р{у*К(х1)\х,) г ± л ¿в

к ' .Тогда для любого а выполняется неравенство:

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

Таблица 1 Результаты экспериментов на нескольких наборах данных из репозитория UCI

Problem AdaBoost, ODDboost, AdaBoost, ODDboost, AdaBoost, ODDboost,

1 итер. 1 итер. 100 irrep. 100 итер. 500 итер. 500 итер.

austra 13.2±0.5 13.2±0.5 14.2±0.2 12.1±0.1 16.0±0.1 13.1±0.1

australian 15.0±0.5 15.0±0.5 14.5±0.2 13.0±0.1 17.4±0.1 13.0±0.1

breast-cancer 8.5±0.3 7.5±0.3 4.5±0.1 4.2±0.0 5.4±0.0 4.4±0.1

checker9 47.0±0.4 46.0±0.4 28.8±0.4 27.5±0.2 29.5±0.4 27.0±0.2

german 39.0±0.3 38.0±0.3 23.7±0.2 26.6±0.2 25.7±0.3 25.0±0.1

madelon 37.5±0.3 37.6±0.3 40.1±0.5 38.7±0.2 41.5±0.3 38.0±0.1

magic04 26.4±0.2 26.4±0.2 17.0±0.5 17.6±0.2 17.9±0.1 16.4±0.1

page blocks 6.3±0.1 6.4±0.1 3.4±0.2 3.6±0.1 3.3±0.1 2.9±0.1

pima-indians- 26.3±0.3 25.2±0.3 25.5±0.5 24.2±0.2 26.2±0.1 24.7±0.2

diabetes

T 31.9±0.3 31.8±0.3 15.0±0.2 14.1±0.1 16.2±0.2 14.6±0.0

vote 4.4±0.2 4.4±0.2 3.7±0.2 4.3±0.2 4.6±0.2 4.3±0.2

XOR 54.0t0.3 57.0±0.3 46.2±0.4 47.4±0.3 46.8±0.4 49.0±0.3

Total: 2 1 6 12 1 14

В таблице 1 приведены результаты экспериментов на данных из репозитория 11С1, в которых предложенный метод бустинга с вероятностными входами (СЮОЬоозу сравнивается со стандартным методом АдаВоо$1. В последней строке поведена статистика, за каждый наилучший результат метод получает 2 балла, за каждое второе место метод получает 1 балл. Видно, что в большинстве случаев использование метода бустинга с вероятностными входами позволяет добиться более высокой точности классификации, чем при использовании стандартного метода АдаВооБ!

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

15 Friedman, J., Hastie, T., & Tibshirani, R.: Additive Logistic Regression: a Statistical View of Boosting. The Annals of Statistics, 28,

2,(2000)337-407

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

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

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

Эксперименты на стандартном наборе данных, описанные в работе, показывают более высокую точность предлагаемого метода по сравнению с базовым методом преобразования Хафа с последующим поиском локальных максимумов Хаф-карты и подавления немаксимумов в случае, когда на изображении присутствуют несколько объектов интереса. Результаты работы предложенного алгоритма сравнивались с результатами преобразования Хафа с последующим подавлением ие-максимумов. Кривые Отклик-Точность для предложенного метода и классического преобразования Хафа с последующим подавлением немаксимумов показаны на рисунке ниже.

Рисунок 2. Результаты экспериментов по поиску прямых линий на наборе изображений «Йорк», и. По вертикаьлной оси отложена характеристика точность, по горизонтальной оси отложена характеристика отклик.

Видно, что предложенный метод работает лучше классического метода по обоим показателям точности и отклика.

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

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

линия горизонта

\

--«fei

/1 "■'■ точка схода

\

точка схода

Рисунок 3. Точки схода, зенит и горизонт. Обозначим пиксели краев за р = где каждый pt соответствует позиции пикселя

на плоскости изображения. Линии, присутствующие на изображении, обозначаются через ' = U)'lr Обозначим через г положение зенита (точку схода для семейства вертикальных линий). Через Ь = {й;.}"1 обозначим точки схода, соответствующие горизонтальным линиям. Таким образом, точки Л,.^,...,^ должны лежать недалеко от одной прямой (это условие будем называть далее ограничением на горизонт).

Общая энергия, таким образом, определяется по формуле:

W.b,r|p) = ¿^ЫО + ^ХвМ + £ ^(MylsJ+S^ah)

i=l 1-1 1 SiZjiH

где Epnor( l,h) = Л,й,|1|+Д1г, |h| - штраф за добавление большого количества линий (согласно принципу минимальной длины описания) 111= L и за добавление большого количества точек схода |h|=#, таким образом предпочтение отдается более простым описаниям сцены. Константы Я&е и Д, являются параметрами алгоритма. Энергия краев задается следующим образом:

(р 11) = min [ebs, min 9äk, ■ d(p, l,) ,

где d обозначает евклидово расстояние на плоскости изображеши между пикселем края и прямой линией, 0Ь> - константа, которая соответствует правдоподобию фона, и 0Ъ: -

константа, которая отвечает за разброс пикселей вокруг одной линии.

Член энергии для прямых линий задается следующим выражением:

£„„, (' I h, z) = min [ribs, min • ф (l, zf j

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

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

Е^ (и, /г | г) = к^ х 1ёу (и - И, I. (г)),

где (р - модуль утла между вектором и перпендикуляром к ¿(г), а кЙ0Г- константа,

параметр алгоритма.

Общая энергия, таким образом, объединяет вместе компоненты изображения не-Манхеттенской сцены на разных уровнях, и геометрический парсинг сцены на основе анализа линий происходит посредством минимизации энергии.

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

у -{>;^и г. Значение дискретной функции энергии вычисляется как значение

непрерывной функции энергии на соответствующем подмножестве кандидатов в лиши и в точки схода.

Фактор-граф, соответствующий получившейся энергии показан на рисунке внизу.

Кандидаты в точки схода

Кандидаты влинии

^«заграничные пиксели

Рисунок 4. Графическая модель, соответствующая дискретной энергии.

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

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

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

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

Как видно из результатов, предложенный метод дает лучшие результаты, чем существующие метода как на базе изображений Йорк, так и на наборе изображений, собранном автором работы.

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

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

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

(а) (Ь)

Рисунок 6 (а) - входное изображение; (Ь) - сгенерированный новый вид.

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

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

В работе предлагается двухэтапный алгоритм поиска параметров модели, то есть задача построения трехмерной модели сцены делится на две подзадачи. Решение каждой из подзадач сводится к нахождению оценки максимума апостериорной вероятносги для условного случайного поля, имеющего структуру графа-цепочки. Благодаря простоте структуры графов достигается более высокая вычислительная эффективность предложенного метода трехмерной по сравнению с существующими методами. Ориентация вертикальных плоскостей в работе определяется посредством нахождения точек схода для отрезков горизонтальных прямых. Для настройки условного случайного поля используется метод кусочной настройки, для этого была создана база примеров изображений, для которых параметры модели были заданы вручную. На этом наборе размеченных изображений настраивается несколько классификаторов, вероятностные выходы которых используются при вычислении потенциалов условного случайного поля. Предложенный метод автоматической трехмерной реконструкции городских сцен по одной фотографии реализован в виде программной системы. Метод запатентован в России [14,15], США [16] и Южной Корее [17].

В заключении описываются основные результаты работы.

Основные результаты работы

Результаты, полученные в настоящей диссертационной работе, состоят в следующем:

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

2. Разработана новая вероятностная модель для поиска многих объемов (в частности, прямых линий). Разработан метод геометрического парсинга антропогенных сцен, позволяющий находить в рамках единой вероятностной модели прямые линии, точки схода, зенит и линию горизонта.

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

Список публикаций

1. О. Barinova. Incorporating posterior estimates into AdaBoost. // Pattern Recognition and Image Analysis, MAIK Nauka/Interperiodica, Volume 19, Number 3 / Сентябрь 2009 г., стр. 421-434.

2. О. Бариноеа. Трехмерная реконструкция городских сцен по одному изображению. // Вестник Компьютерных и информационных технологий, издательство «Машиностроение», Номер 5,2010 год

3. О. Barinova, V. Lempitsky, P. Kohli. On detection of multiple object instances using Hough transform. // In: Computer Vision and Pattern Recognition.; 2010.

4. O. Barinova, V. Lempitsky, E. Tretiak, P. Kohli. Geometric Image Parsing in ManDMade Environments. // In: European Conference on Computer Vision.; 2010.

5. О. Бариноеа, Д. Ветров. Оценки обобщающей способности бустинга с вероятностными входами // труды Конференции ММРО, 2009, стр. 184-188.

6. О. Barinova, D. Vetrov. ODDboost: Incorporating posterior estimates into AdaBoost // Lecture Notes in Computer Science, Springer Berlin / Heidelberg, Volume 5632/2009, Machine Learning and Data Mining in Pattern Recognition, pp. 178-190

7. О. Бариноеа, В. Конушин, А. Соболев, А. Кузъмишкина, А. Якубенко, А. Конушин. Быстрая автоматическая трехмерная реконструкция городских сцен по одному изображению. // в трудах конференции Графикон 2008, том 1., стр. 234-242.

8. О. Бариноеа, В. Конушин, А. Якубенко, А. Конушин. Быстрый метод семантической сегментации изображений для автоматической трехмерной реконструкции городских сцен по одной фотографии. // в трудах конференции Интеллектуализация обработки информации 2008, стр. 22-24.

9. О. Barinova, V. Ronushin, A. Yakubenko, К. Lee, Н. Lim, A. Konushin. Fast Automatic SingleView 3-d Reconstruction of Urban Scenes. // In: Proc. of European Conference on Computer Vision, 2008 (II). Pp. 100-113.190.

10. О. Бариноеа, А. Вежневец. Повышение обобщающей способности бустинга в задачах с пересекающимися распределениями классов // труды 50-й юбилейной Конференции МФТИ 2007, стр 91-93.

11.0. Бариноеа, А. Вежневец, В. Вежневец. Повышение обобщающей способности бустинга в задачах с перекрывающимися классами // труды Конференции ММРО 2007, стр. 82-84.

12. О. Barinova, A. Kuzmishkina, A. Vezhnevets and V. Vezhnevets, Learning class specific edges for vanishing point estimation. // In: Proc. of Graphicon'2007, pp. 86-89.

13. A. Vezhnevets, O. Barinova.. Avoiding Boosting Overfitting by Removing Confusing Samples. // Lecture Notes in Computer Science, Springer Berlin / Heidelberg, Volume 4701/2007, Machine Learning: ECML 2007, pp. 430-441.

14. METHOD FOR DETERMINING GROUND LINE, 2008132273, RU, 17.07.2008, Chae Sunhyuck, Kim Dokyoon, Lee KeeChang, Lim Hwasup, Konushin Anton, Barinova Olga, Konushin Vadim, Yakubenko Anton

15. IMAGE PROCESSING METHOD, 2008129149, RU, 17.07.2008, Lim Hwasup, Lee KeeChang, Barinova Olga, Konushin Anton, Konushin Vadim, Yakubenko Anton

16. METHOD FOR DETERMINING GROUND LINE, 1911.1137, US, Chae sunhyuck, Kim Dokyoon, Lee KeeChang, Lim Hwasup, Konushin Anton, Barinova Olga, Konushin Vadim, Yakubenko Anton

17. METHOD FOR DETERMINING GROUND LINE, 10-2008-0105977, 28.10.2008, Chae Sunhyuck, Kim Dokyoon, Lee KeeChang, Lim Hwasup, Konushin Anton, Barinova Olga, Konushin Vadim, Yakubenko Anton

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 12.11.2010 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 514. Тел. 939-3890. Тел./факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

СОДЕРЖАНИЕ РАБОТЫ ПО

ГЛАВАМ.

БЛАГОДАРНОСТИ.

1. НОВЫЙ МЕТОД ПОСТРОЕНИЯ КОМПОЗИЦИЙ

КЛАССИФИКАТОРОВ.

3.1. Алгоритмы бустинга для задачи классификации.

Формальные постановки задачи классификации.

Проблема переобучения и обобщающая способность.

Композиции классификаторов.

Алгоритм АскВооБ! (бустинг).

Оценки обобщающей способности для классификаторов, построенных бустингом.

Модификации бустинга устойчивые к шуму в обучающей выборке.

3.2. Новые оценки обобщающей способности для линейных комбинаций классификаторов.

3.3. Новый метод построения композиций классификаторов.

Метод оценивания условных вероятностей.

Результаты экспериментов.

3.4. ВЫВОДЫ.

2. РАЗВИТИЕ МЕТОДОВ АНАЛИЗА ГЕОМЕТРИИ АНТРОПОГЕННЫХ СЦЕН НА ОСНОВЕ АНАЛИЗА ПРЯМЫХ ЛИНИЙ.

2.1. Усовершенствованное преобразование Хафа для поиска многих объектов.

Обзор модификаций преобразования Хафа для поиска прямых линий

Анализ вероятностной модели в основе преобразования Хафа.

Предлагаемая вероятностная модель.

Вывод в предлагаемой вероятностной модели.

Эксперименты.

2.2. Геометрический парсинг фотографий городских сцен.

Обзор методов поиска точек схода.

Предлагаемый подход.

Описание предлагаемой вероятностной модели.

Вывод в модели.

Эксперименты.

2.3. ВЫВОДЫ.

3. ПОСТРОЕНИЕ ТРЕХМЕРНЫХ МОДЕЛЕЙ ГОРОДСКИХ СЦЕН ПО ОДНОЙ ФОТОГРАФИИ.

3.1. Существующие подходы к построению трехмерных моделей сцен по одному изображению.

3.2. Предлагаемый метод построения трехмерных моделей городских сцен по одному изображению.

Структура трехмерной модели и общая схема работы предлагаемого алгоритма.

Предобработка изображения.

Вероятностная модель.

Поиск точек перегиба ломаной линии.

Вертикальное позиционирование ломаной линии.

3.3. Результаты работы метода трехмерной реконструкции.

3.4. ВЫВОДЫ.

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ ПО ГЛАВАМ

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

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

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

БЛАГОДАРНОСТИ

Автор выражает глубокую признательность к.ф.-м.н. Ю.М. Баяковскому и проф. д. ф.-м. н. Рудакову К. В.

3.4. ВЫВОДЫ

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

ЗАКЛЮЧЕНИЕ

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

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

1. ВапникВ.Н. Восстановление зависимостей по эмпирическим данным М. Наука. 1979.

2. Вапник В. Н., Червоненкис А. Я.: Теория распознавания образов. — М.: Наука, 1974.

3. Воронцов К. В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. — 2004.

4. Воронцов К. В. Комбинаторные обоснования обучаемых алгоритмов // ЖВМиМФ. — 2004. — Т. 44, № 11. — С. 2099-2112.

5. Воронцов К. В. Слабая вероятностная аксиоматика и надежность эмпирических предсказаний // Математические методы распознавания образов-13. — М.: МАКС Пресс, 2007. — С. 21-25.

6. Воронцов К. В., ИнякинА. С., Лисица А. В. Система эмпирического измерения качества алгоритмов классификации // Математические методы распознавания образов-13.— М.: МАКС Пресс, 2007.— С. 577-580.

7. Воронцов К.В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ЖВМ и МФ. 2000. Т. 40, №1.

8. Воронцов, К. В. Комбинаторная теория надёжности обучения по прецедентам: Дис. док. физ.-мат. наук: 05-13-17.— Вычислительный центр РАН, 2010.

9. Докукин А. А. Об одном методе построения оптимального алгоритма вычисления оценок // Журнал вычислительной математики и математической физики, 2006, № 4. С. 755-762.

10. Журавлев Ю.И. Рудаков К.В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М. Наука, 1987. С. 187-198.

11. И.Рудаков К.В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. №3. с. 106- 109.

12. Рудаков К.В., Воронцов К.В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // ДАН. 1999. Т. 367 №3. С. 314-317

13. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации//ЖВМ и МФ. 1981. Т. 21, № 6 с. 1533-1543.

14. Цюрмасто П. А., Воронцов К. В. Анализ сходства алгоритмов классификации в оценках обобщающей способности // Интеллектуализация обработки информации (ИОИ-2008): Тезисы докл. — Симферополь: КНЦ HAH Украины, 2008. — С. 232-234.

15. Aguilera, D.G., Lahoz, J.G., Codes, J.F.: A new method for vanishing points detection in 3d reconstruction from a single view. // In: Proc. of ISPRS Commission V. (2005)

16. Amit Y., Geman D., and Fan X. A coarse-to-fine strategy for multi-class shape detection. // In: TP AMI, 26(12):1606-1621, 2004.

17. Andriluka M., Roth S., and Schiele В. People-tracking-by-detection and people-detection-by-tracking. // In: CVPR, 2008.

18. Antone M.E., Teller S.J.: Automatic recovery of relative camera rotations for urban scenes. // In: CVPR. (2000) 2282-2289

19. Almansa A., Desolneux A., Vamech S.: Vanishing point detection without any a priori information. // IEEE Trans. Pattern Anal. Mach. Intell. 25 (2003) 502-507

20. Ballard D. H. Generalizing the hough transform to detect arbitrary shapes. // Pattern Recognition, 13(2):111-122, 1981.

21. Barinova O., Kuzmishkina A., Vezhnevets A., Vezhnevets V.: Learning class specific edges for vanishing point estimation. // In Proc. of Graphicon (2007) 162-165

22. Barinova O., Lempitsky V., and Kohli P. On detection of multiple object instances using hough transforms. //In: CVPR. (2010)

23. Barnard, S.: Interpreting perspective images. //Artificial Intelligence 21 (1983)435-462

24. Beardsley, P., Murray, D.: Camera calibration using vanishing points. // In: BMVC. (1992) 416-425

25. Besag J.: On the statistical analysis of dirty pictures. // Journal of the Royal Statistical Society B-48 (1986) 259-302

26. Bourdev L. and Malik J. Poselets: Body part detectors trained using 3d human pose annotations. // In. ICCV, 2009.

27. Boser B.; Guyon I.; Vapnik, V. A training algorithm for optimal margin classifiers. // Fifth Annual Workshop on Computational Learning Theory. ACM Press, Pittsburgh, (1992).

28. Blake C. L., & Merz C. J.: UCI repository of machine learning databases (1998)

29. Breiman L.: Bagging Predictors. // Machine Learning, 24, 2, (1996) 123140

30. Breiman Leo (2001). Random Forests. // Machine Learning 45 (1): 5-32

31. Canny J.: A Computational Approach To Edge Detection. // PAMI 8 (1986)

32. Caruana R., Niculescu-Mizil A.: An Empirical Comparison of Supervised Learning Algorithms // Proceedings of the 23rd International Conference on Machine Learning (ICML "06).

33. Collins M., Schapire R. E. and Singer Y.: Logistic regression, AdaBoost and Bregman distances. I I Machine Learning (2001)

34. Cipolla R., Drummond T., Robertson D.P.: Camera calibration from vanishing points in image of architectural scenes. // In: BMVC. (1999)

35. Chum O., Matas J., Kittler J.,: Locally Optimized RANSAC. // DAGM Symposium on Pattern Recognition 25 (2003) 236-243

36. Comaniciu D., Meer P.: Mean shift: A robust approach toward feature space analysis. // IEEE Trans, on Pattern Analysis and Machine Intelligence (2002) 24,5.

37. Collins R., Weiss R.: Vanishing point calculation as a statistical inference on the unit sphere. // In: ICCV. (1990) 400-403

38. Coughlan J.M., Yuille A.L.: Manhattan world: Compass direction from a single image by bayesian inference. // In: ICCV. (1999) 941-947

39. Criminisi A., Reid I., Zisserman A.: Single view metrology. // IJCV, 40 (2000)

40. Desai C. F, Ramanan D. Discriminative models for multi-class object layout. ICCV, 2009.

41. Delage E., Lee H., Ng A.: Automatic single-image 3d reconstructions of indoor manhattan world scenes. // In Proc. of ISRR (2005)

42. Delage, E., Lee, H., Ng, A.: A dynamic bayesian network model for autonomous 3d reconstruction from a single indoor image. // In Proc. of CVPR (2006)

43. Deutscher, J., Isard, M., MacCormick, J.: Automatic camera calibration from a single manhattan image. // In: ECCV (4). (2002) 175-205

44. Denis, P., Elder, J.H., Estrada, F.J.: Efficient edge-based methods for estimating manhattan frames in urban imagery. // In: ECCV (2). (2008) 197210

45. Duric, Z., Rosenfeld, A.: Image sequence stabilization in real time. // RealTime Imaging 2 (1996) 271-284

46. Dietterich, T., G.: An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. // Machine Learning, 40 (2) (1999)

47. Domingos, P.: A Unified Bias-Variance Decomposition for Zero-One and Squared Loss. // In Proc. of the 17th National Conference on Artificial Intelligence. (2000).

48. Domingo C., Watanabe O.: Madaboost: A modication of adaboost. // In 13th Annual Conference on Comp. Learning Theory, (2000)

49. Freund Y., Schapire R., A decision-theoretic generalization of on-line learning and an application to boosting. // Journal of Computer and System Sciences, no. 55. 1997

50. Friedman, J., Hastie, T., & Tibshirani, R.: Additive Logistic Regression: a Statistical View of Boosting. // The Annals of Statistics, 28, 2, (2000) 337407

51. Friedman, J.: Greedy function approximation: A gradient boosting machine. //Annals of Statistics, 29, 5. (2001)

52. Frey B. J. and Dueck D. Clustering by passing messages between data points. // Science, 315:972-976, 2007.

53. Gall J. and Lempitsky V. Class-specific hough forests for object detection. // CVPR, 2009.

54. Gu C., Lim J. J., Arbelaez P., and Malik J. Recognition using regions. // CVPR, 2009.

55. Hoiem, D., Efros, A., Hebert, M.: Geometric context from a single image. // In Proc. oflCCV (2005)

56. Hoiem, D., Sten, A.N., Efros A.A., Hebert, M.: Recovering Occlusion Boundaries from a Single Image. // In Proc. of ICCV (2007)

57. Hoiem D., Rother C., and Winn J. M. 3d layoutcrf for multi-view object class recognition and segmentation. // CVPR, 2007.

58. Hoiem, D., Efros, A.A., Hebert, M.: Automatic photo pop-up. // ACM Trans. Graph. 24 (2005) 577-584l.Hoiem, D., Efros, A.A., Hebert, M.: Putting objects in perspective. // International Journal of Computer Vision 80 (2008) 3-15

59. Hough P. Machine analysis of bubble chamber pictures. // Int. Conf. High Energy Accelerators and Instrumentation, 1959.

60. Hulse, J., Khoshgoñaar, T., Napolitano, A.: Experimental perspectives on learning from imbalanced data. // In Proc. of ICML (2007) 935-942

61. Kanevskiy D. Y., Vorontsov K. V. Cooperative revolutionary ensemble learning // Multiple Classifier Systems: 7th International Workshop, Prague, Czech Republic, May 23-25, 2007. — Lecture Notes in Computer Science. Springer-Verlag, 2007. — Pp. 469-478.

62. Kang, H., Pyo, S., Anjyo, K., Shin, S.: Tour into the picture using a vanishing line and its extension to panoramic images. // In Proc. Eurographics (2001)132141.

63. Kosecka, J., Zhang, W.: Video Compass. // In Proc. of ECCV 7 (2002) 476491

64. Kearns, M., Vazirani, U.: An Introduction to Computational Learning Theory. // MIT Press, 1994

65. Kovesi P., Shapelets Correlated with Surface Normals Produce Surfaces. // 10th IEEE International Conference on Computer Vision. Beijing, pp 9941001.2005.

66. Koutsourakis, P. Simon, L. Teboul, O. Tziritas, G. Paragios, N. Single view reconstruction using shape grammars for urban environments. // In. Proc. IEEE 12th International Conference on Computer Vision, 2009 , pp. 1795 1802

67. Langford J. and Blum A. Microchoice Bounds and Self Bounding learning algorithms. // COLT99, pages 209-214 (2002)

68. Laferty, J., McCallum, A., Pereira, F.: Conditional random fields: Probabilistic models for segmenting and labeling sequence data. // In Proc. of ICML (2001)

69. Lazic N., Givoni I., Frey B., and Aarabi P. Floss: Facility location for subspace segmentation. // ICCV, 2009.

70. Leibe B., Leonardis A., and Schiele B. Robust object detection with interleaved categorization and segmentation. // IJCV, 77(l-3):259-289, 2008.

71. Langford J., Seeger M., and Megiddo N. An Improved Predictive Accuracy Bound for Averaging Classifiers // In Proc ICML2001

72. Langford J., Caruana R., (Not) Bounding the True Error // NIPS2001

73. Langford J., Seeger M., Bounds for Averaging Classifiers // Technical report, Carnegie Mellon 2001

74. Langford J. and McAllester D. Computable Shell Decomposition Bounds. // InJMLR

75. Langford J. Combining Train Set and Test Set Bounds. // ICML2002

76. McLean, G.F., Kotturi, D.: Vanishing point detection by line clustering. // IEEE Trans. Pattern Anal. Mach. Intell. 17 (1995) 1090-1095

77. Mason L, Baxter J, Bartlett P, Frean M.: Boosting algorithms as gradient descent, // Neural Information Processing Systems 12, MIT Press, (2000) 512-518

78. Nemhauser G. L. and Wolsey L. A. Best algorithms for approximating the maximum of a submodular set function. // Mathematics of operations research, 3(3): 177-188, 1978.

79. Niculescu-Mizil, A., Caruana, R.: Obtaining Calibrated Probabilities from Boosting. // In Proc. of UAI (2005) 413-42085.0kada. R. Discriminative generalized hough transform for object detection. //ICCV, 2009.

80. Pearl. J. Probabilistic Reasoning in Intelligent Systems. // Morgan Kaufmann, Palo Alto, 1988.

81. Perrone M.: Improving regression estimation: Averaging methods for Variance reduction with extension to General Convex Measure Optimization, // Ph.D. Thesis, Brown University, (1993)

82. Ratsch. G.: Robust Boosting and Convex Optimization. // Doctoral dissertation, University of Potsdam, (2001)

83. Reyzin, L., & Schapire, R.: How boosting the margin can also boost classifier complexity. // In Proceedings of the 23rd International Conference on Machine Learning (2006)

84. Rosset S.: Robust Boosting and Its Relation to Bagging. // KDD-05 (2005)

85. Rother, C.: A new approach for vanishing point detection in architectural environments. // In: BMVC. (2000)

86. Robert E. Schapire, Marie Rochery, Mazin Rahim and Narendra Gupta. Incorporating prior knowledge into boosting. // In Machine Learning: Proceedings of the Nineteenth International Conference, 2002.

87. Saxena, A., Sun, M., Ng, A.: Learning 3-D Scene Structure from a Single Still Image. // In Proc. of ICCV workshop on 3D representation for Recognition (2007)

88. Saxena, A., Chung, S., Ng, A.: Depth Reconstruction from a Single Still Image. // IJCV (2007)

89. Saxena, A., Chung, S., Ng, A.: Learning Depth from Single Monocular Images. //In Proc. of NIPS 18 (2005)

90. Schindler, G., Dellaert, F.: Atlanta world: An expectation maximization framework for simultaneous low-level edge grouping and camera calibration in complex man-made environments. // In: CVPR (1). (2004) 203-209

91. Sutton, C., McCallum, A.: Piecewise training of undirected models. // In Proc. of UAI 21 (2005)

92. Sheikh Y., Khan E. A., and Kanade T. Mode-seeking by medoid-shifts. // ICCV, 2007.

93. Shotton, J., Winn, J., Rother, C., Criminisi, A.: TextonBoost for Image Understanding: Multi-Class Object Recognition and Segmentation by Jointly Modeling Texture, Layout, and Context. IJCV (2007)

94. Schapire, R., Freund, Y., Bartlett, P., and Wee Sun Lee.: Boosting the margin: A new explanation for the effectiveness of voting methods. // In Machine Learning: Proceedings of the Fourteenth International Conference (1997)

95. Schapire, R. and Singer, Y.: Improved Boosting Algorithms Using Confidence-rated Predictions, // In Machine Learning, 37(3):297-336, 1999

96. Schapire R, Rochery M, Rahim M., Gupta N. Incorporating prior knowledge into boosting, // In Machine Learning, 2002

97. Taniguchi M, Tresp V.: Averaging Regularized Estimators, // In Neural Computation (1997)

98. Tardif, J.P.: Non-iterative approach for fast and accurate vanishing point detection. // In: ICCV. (2009)

99. A. Torralba and A. Oliva. Depth estimation from image structure. // IEEE Trans Pattern Analysis and Machine Intelligence (PAMI), 24(9): 1-13, 2002.

100. Tuytelaars, T., Gool, L.J.V., Proesmans, M., Moons, T.: A cascaded hough transform as an aid in aerial image interpretation. // In: ICCV. (1998) 67-72

101. Tu, Z., Chen, X., Yuille, A.L., Zhu, S.C.: Image parsing: Unifying segmentation, detection, and recognition. // International Journal of Computer Vision 63 (2005) 113-140

102. Vezhnevets, V., Konushin, A., Ignatenko, A.: Interactive image-based urban modeling. // In Proc. of PIA (2007) 63-68

103. Viola, P., Jones, M.: Robust Real-time Object Detection. // IJCV (2001)

104. Vezhnevets A, Barinova O.: Avoiding boosting overfitting by removing confusing samples, // In Proc. Of European Conference on Machine Learning (2007)

105. Vorontsov K. V. Combinatorial probability and the tightness of generalization bounds // Pattern Recognition and Image Analysis. — 2008. — Vol. 18, no. 2. — Pp. 243-259.

106. Wasserman, L.: All of Nonparametric Statistics. // Springer, 2006.

107. Winn J. M. and Shotton J. The layout consistent random field for recognizing and segmenting partially occluded objects. // CVPR (1), pp. 3744, 2006.