Компьютерное зрение. Теория и алгоритмы

Рейнхард Клетте

Компьютерное зрение

Теория и алгоритмы

Concise Computer Vision

An Introduction into Theory and Algorithms

Reinhard Klette

Москва, 2019

Рейнхард Клетте

Компьютерное зрение

Теория и алгоритмы

УДК   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

Всем, кто любит мечтать

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

Оглавление

Предисловие .........................................................................................................................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

 Оглавление

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

 Оглавление

Глава 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