УДК 004.8
ББК 32.81
К48
К48 Рейнхард Клетте
Компьютерное зрение. Теория и алгоритмы / пер. с англ. А. А. Слинкин.
– М.: ДМК Пресс, 2019. – 506 с.: ил.
ISBN 978-5-97060-702-2
В этой книге рассмотрены основные аспекты компьютерного зрения:
обработка и анализ изображений, анализ плотного движения, сегментация
изображений, работа с камерами, трехмерная реконструкция, сопоставление
стереоизображений, обнаружение объектов и др. Материал дополняется
историческими справками, рекомендациями по дальнейшему чтению и
сведениями о рассматриваемых математических понятиях. В конце каждой
главы имеются проверенные на практике упражнения и вопросы на понимание
материала.
Издание предназначено широкому кругу специалистов по анализу данных
и изображений, а также может использоваться в качестве учебника для
студентов старших курсов и для самообразования.
УДК 004.8
ББК 32.81
First published in English under the title Concise Computer Vision; Copyright
© Springer-Verlag London, 2014. This edition has been translated and published under
licence from Springer-Verlag London Ltd., part of Springer Nature. Springer-Verlag
London Ltd., part of Springer Nature takes no responsibility and shall not be made liable
for the accuracy of the translation. © 2019 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена
в какой бы то ни было форме и какими бы то ни было средствами без письменного
разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку
вероятность технических ошибок все равно существует, издательство не может гарантировать
абсолютную точность и правильность приводимых сведений. В связи
с этим издательство не несет ответственности за возможные ошибки, связанные с
использованием книги.
ISBN 978-1-4471-6319-0 (англ.) © Springer-Verlag London, 2014
ISBN 978-5-97060-702-2 (рус.) © Оформление, перевод на русский язык, издание,
ДМК Пресс, 2019
Стр.5
Оглавление
Предисловие .........................................................................................................................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
Оглавление 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.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
3.3. Анализ значений изображения ....................................................................................... 147
3.3.1. Матрицы совместной встречаемости и метрики ......................................................... 148
3.3.2. Анализ участков с привлечением моментов ................................................................. 151
Стр.8
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.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
5.4. Сегментация видео и прослеживание сегментов .................................................... 247
5.4.1. Использование согласованности признаков изображений .................................... 248
5.4.2. Использование временной согласованности ............................................................... 249
Стр.9
Оглавление 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
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
Стр.11