Оглавление
Предисловие.........................................................................................................................11
Предмет книги...................................................................................................................................11
Характер изложения.......................................................................................................................11
Целевая аудитория..........................................................................................................................12
Использование материала на практике.................................................................................12
Замечания для преподавателя и рекомендуемый порядок использования
книги..............................................................................................................................................13
Дополнительные ресурсы.............................................................................................................13
Благодарности (в алфавитном порядке по фамилии).......................................................13
Обозначения.........................................................................................................................16
Глава 1. Данные изображения...........................................................................................18
1.1. Изображения в пространственной области..................................................................18
1.1.1. Пиксели и окна .............................................................................................................................19
1.1.2. Значения и основные статистики изображения.............................................................21
1.1.3. Пространственные и временные меры данных .............................................................26
1.1.4. Ступенчато-граничная модель................................................................................................29
1.2. Изображения в частотной области...................................................................................34
1.2.1. Дискретное преобразование Фурье....................................................................................34
1.2.2. Обратное дискретное преобразование Фурье...............................................................35
1.2.3. Комплексная плоскость.............................................................................................................37
1.2.4. Данные изображения в частотной области......................................................................39
1.2.5. Фазово-конгруэнтная модель признаков изображения..............................................44
1.3. Цвет и цветные изображения.............................................................................................47
1.3.1. Определения цвета.....................................................................................................................49
1.3.2. Цветовое восприятие, дефекты зрения и уровни серого...........................................51
1.3.3. Представления цвета .................................................................................................................56
1.4. Упражнения ................................................................................................................................61
1.4.1. Упражнения по программированию....................................................................................61
1.4.2. Упражнения, не требующие программирования............................................................64
Глава 2. Обработка изображений......................................................................................65
2.1. Точечные, локальные и глобальные операторы..........................................................65
2.1.1. Градационные функции.............................................................................................................65
2.1.2. Локальные операторы...............................................................................................................68
2.1.3. Фильтрация Фурье ......................................................................................................................71
2.2. Три процедурных компонента............................................................................................75
2.2.1. Интегральные изображения ...................................................................................................75
2.2.2. Регулярные пирамиды изображений..................................................................................76
2.2.3. Порядок обхода ...........................................................................................................................78
Оглавление  7
2.3. Классы локальных операторов ..........................................................................................80
2.3.1. Сглаживание ..................................................................................................................................80
2.3.2. Повышение резкости .................................................................................................................85
2.3.3. Простые детекторы границ .....................................................................................................86
2.3.4. Простые детекторы углов.........................................................................................................91
2.3.5. Удаление артефактов освещения..........................................................................................95
2.4. Более сложные детекторы границ....................................................................................98
2.4.1. LoG и DoG и их пространства масштабов..........................................................................98
2.4.2. Встроенная уверенность........................................................................................................ 103
2.4.3. Алгоритм Ковеси ....................................................................................................................... 107
2.5. Упражнения .............................................................................................................................113
2.5.1. Упражнения по программированию................................................................................. 113
2.5.2. Упражнения, не требующие программирования......................................................... 115
Глава 3. Анализ изображений ..........................................................................................117
3.1. Основы топологии изображений........................................................................................... 117
3.1.1. 4- и 8-смежность в бинарных изображениях ............................................................... 118
3.1.2. Топологически непротиворечивая смежность пикселей.......................................... 123
3.1.3. Трассировка краев ................................................................................................................... 126
3.2. Анализ двумерных геометрических фигур.................................................................130
3.2.1. Площадь........................................................................................................................................ 130
3.2.2. Длина............................................................................................................................................. 133
3.2.3. Кривизна...................................................................................................................................... 136
3.2.4. Дистанционное преобразование....................................................................................... 140
3.3. Анализ значений изображения....................................................................................... 147
3.3.1. Матрицы совместной встречаемости и метрики......................................................... 148
3.3.2. Анализ участков с привлечением моментов................................................................. 151
3.4. Поиск прямых и окружностей..........................................................................................153
3.4.1. Прямые.......................................................................................................................................... 153
3.4.2. Окружности ................................................................................................................................. 160
3.5. Упражнения .............................................................................................................................162
3.5.1. Упражнения по программированию................................................................................. 162
3.5.2. Упражнения, не требующие программирования......................................................... 167
Глава 4. Анализ плотного движения ...............................................................................169
4.1. 3D-движение и двумерный оптический поток .........................................................169
4.1.1. Локальное смещение и оптический поток..................................................................... 169
4.1.2. Проблема апертуры и градиентный поток .................................................................... 173
4.2. Алгоритм Хорна–Шанка.....................................................................................................175
4.2.1. Подготовительная часть......................................................................................................... 175
4.2.2. Алгоритм....................................................................................................................................... 183
4.3. Алгоритм Лукаса–Канаде.................................................................................................. 187
4.3.1. Линейное решение методом наименьших квадратов.............................................. 188
4.3.2. Оригинальный алгоритм и алгоритм с весами............................................................. 191
8  Оглавление
4.4. Алгоритм BBPW......................................................................................................................193
4.4.1. Исходные предположения и функция энергии............................................................ 193
4.4.2. Краткое описание алгоритма .............................................................................................. 195
4.5. Оценка качества алгоритмов вычисления оптического потока ........................ 197
4.5.1. Стратегии тестирования......................................................................................................... 197
4.5.2. Меры ошибки для сравнения с контрольными данными........................................ 200
4.6. Упражнения .............................................................................................................................202
4.6.1. Упражнения по программированию................................................................................. 202
4.6.2. Упражнения, не требующие программирования......................................................... 204
Глава 5. Сегментация изображений................................................................................206
5.1. Простые примеры сегментации изображений......................................................... 207
5.1.1. Бинаризация изображения................................................................................................... 209
5.1.2. Сегментация путем выращивания семян........................................................................ 212
5.2. Сегментация методом сдвига среднего.......................................................................218
5.2.1. Примеры и подготовка........................................................................................................... 218
5.2.2. Модель сдвига среднего........................................................................................................ 221
5.2.3. Алгоритмы и оптимизация по времени........................................................................... 224
5.3. Сегментация изображений как задача оптимизации............................................230
5.3.1. Метки, пометка и минимизация энергии........................................................................ 231
5.3.2. Примеры членов данных и гладкости.............................................................................. 234
5.3.3. Передача сообщений.............................................................................................................. 237
5.3.4. Алгоритм распространения доверия................................................................................ 239
5.3.5. Распространение доверия в задаче о сегментации изображений...................... 245
5.4. Сегментация видео и прослеживание сегментов.................................................... 247
5.4.1. Использование согласованности признаков изображений.................................... 248
5.4.2. Использование временной согласованности ............................................................... 249
5.5. Упражнения .............................................................................................................................254
5.5.1. Упражнения по программированию................................................................................. 254
5.5.2. Упражнения, не требующие программирования......................................................... 257
Глава 6. Камеры, координаты и калибровка.................................................................262
6.1. Камеры......................................................................................................................................263
6.1.1. Свойства цифровой камеры ................................................................................................ 263
6.1.2. Центральная проекция........................................................................................................... 268
6.1.3. Система с двумя камерами................................................................................................... 271
6.1.4. Системы панорамных камер................................................................................................ 273
6.2. Координаты .............................................................................................................................276
6.2.1. Мировые координаты............................................................................................................. 276
6.2.2. Однородные координаты...................................................................................................... 279
6.3. Калибровка камеры.............................................................................................................281
6.3.1. Калибровка камеры с точки зрения пользователя..................................................... 282
6.3.2. Ректификация пар стереоизображений.......................................................................... 286
6.4. Упражнения .............................................................................................................................292
Оглавление  9
6.4.1. Упражнения по программированию................................................................................. 292
6.4.2. Упражнения, не требующие программирования......................................................... 294
Глава 7. Трехмерная реконструкция ...............................................................................296
7.1. Поверхности ............................................................................................................................296
7.1.1. Топология поверхности .......................................................................................................... 297
7.1.2. Локальные параметризации поверхности ..................................................................... 301
7.1.3. Кривизна поверхности ........................................................................................................... 304
7.2. Структурная подсветка........................................................................................................308
7.2.1. Проекция световой плоскости............................................................................................. 308
7.2.2. Анализ световой плоскости .................................................................................................. 311
7.3. Стереоскопическое зрение................................................................................................314
7.3.1. Эпиполярная геометрия ......................................................................................................... 314
7.3.2. Бинокулярное зрение в канонической геометрии стереоскопической
системы......................................................................................................................................... 316
7.3.3. Бинокулярное зрение в конвергентной системе......................................................... 319
7.4. Фотометрический метод анализа стереоизображений.........................................324
7.4.1. Ламбертовская отражательная способность.................................................................. 325
7.4.2. Восстановление градиентов поверхности...................................................................... 327
7.4.3. Интегрирование градиентных полей................................................................................ 331
7.5. Упражнения..............................................................................................................................340
7.5.1. Упражнения по программированию ................................................................................. 340
7.5.2. Упражнения, не требующие программирования ......................................................... 343
Глава 8. Сопоставление стереоизображений ................................................................345
8.1. Сопоставление, стоимость данных и уверенность...................................................346
8.1.1. Общая модель сопоставления............................................................................................. 347
8.1.2. Функции стоимости данных................................................................................................. 351
8.1.3. От глобального сопоставления к локальному............................................................... 354
8.1.4. Тестирование функций стоимости данных..................................................................... 358
8.1.5. Меры уверенности................................................................................................................... 360
8.2. Сопоставление методом динамического программирования ...........................362
8.2.1. Динамическое программирование................................................................................... 363
8.2.2. Ограничение порядка............................................................................................................. 364
8.2.3. Сопоставление методом динамического программирования
с использованием ограничения порядка.................................................................................. 367
8.2.4. Алгоритм DPM с ограничением гладкости..................................................................... 373
8.3. Сопоставление методом распространения доверия..............................................379
8.4. Техника третьего глаза........................................................................................................382
8.4.1. Построение виртуального изображения, снятого третьей камерой.................... 383
8.4.2. Сходство между виртуальным и третьим изображениями ..................................... 388
8.5. Упражнения .............................................................................................................................391
8.5.1. Упражнения по программированию................................................................................. 391
8.5.2. Упражнения, не требующие программирования......................................................... 393
10  Оглавление
Глава 9. Обнаружение и прослеживание признаков ...................................................396
9.1. Инвариантность, признаки и множества признаков..............................................396
9.1.1. Инвариантность......................................................................................................................... 396
9.1.2. Особые точки и векторы трехмерного потока ............................................................. 398
9.1.3. Множества особых точек в соседних кадрах................................................................ 402
9.2. Примеры признаков ............................................................................................................ 407
9.2.1. SIFT-признаки ............................................................................................................................ 407
9.2.2. SURF-признаки.......................................................................................................................... 410
9.2.3. ORB-признаки............................................................................................................................ 411
9.2.4. Оценка признаков.................................................................................................................... 414
9.3. Прослеживание и обновление признаков ................................................................. 417
9.3.1. Прослеживание – задача разреженного соответствия............................................. 419
9.3.2. Прослеживатель Лукаса–Канаде....................................................................................... 420
9.3.3. Фильтр частиц............................................................................................................................ 426
9.3.4. Фильтр Калмана........................................................................................................................ 435
9.4. Упражнения .............................................................................................................................442
9.4.1. Упражнения по программированию................................................................................. 442
9.4.2. Упражнения, не требующие программирования......................................................... 447
Глава 10. Обнаружение объектов....................................................................................449
10.1. Локализация, классификация и оценка ....................................................................449
10.1.1. Дескрипторы, классификаторы и обучение................................................................ 450
10.1.2. Качество детекторов объектов......................................................................................... 456
10.1.3. Гистограмма ориентированных градиентов ............................................................... 458
10.1.4. Вейвлеты и признаки Хаара.............................................................................................. 460
10.1.5. Метод Виолы–Джонса.......................................................................................................... 464
10.2. AdaBoost................................................................................................................................. 467
10.2.1. Алгоритм.................................................................................................................................... 468
10.2.2. Параметры................................................................................................................................ 470
10.2.3. Почему именно такие параметры?................................................................................. 474
10.3. Случайные решающие леса ...........................................................................................476
10.3.1. Энтропия и информационный выигрыш...................................................................... 476
10.3.2. Применение леса................................................................................................................... 479
10.3.3. Обучение леса......................................................................................................................... 481
10.3.4. Леса Хафа.................................................................................................................................. 486
10.4. Обнаружение пешеходов................................................................................................488
10.5. Упражнения...........................................................................................................................491
10.5.1. Упражнения по программированию.............................................................................. 491
10.5.2. Упражнения, не требующие программирования ...................................................... 493
Предметный указатель .....................................................................................................495
Предислов