English
Лаборатория компьютерной графики
Rus > Библиотека > Введение в машинное зрение
[Главная]
[О нас]
[Наука]
[Публикации]
[Семинары]
[Библиотека]
[Файлы]
[Ссылки]
[Форум]
 
Hosted sites
[Курсы]
[Журнал]
[Графикон]
[Сжатие]
[Графор]
 
Поиск
детальный поиск
 
Rambler's Top100

Введение в Computer Vision

Владимир Вежневец
vvp@graphics.cs.msu.su

Содержание


Введение Computer Vision

Зачем нужен этот документ


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

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

Машинное зрение и анализ изображений


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

  1. Обнаружение/распознавание/отслеживание объектов, обладающих опредленными свойствами (в самом широком смысле) на статическом изображении и в видеопотоке;
  2. Восстановление 3D формы по 2D изображениям с помощью:
  3. Стереореконструкции карты глубины
    (Shape from stereo);
  4. Реконструкции поля нормалей и карты глубины по закраске полутонового изображения
    (Shape from shading);
  5. Реконструкции карты глубины по текстуре
    (Shape from texture)
  6. Определению формы по перемещению
    (Shape from motion)
  7. Выделение на изображениях структур определенного вида (например краев - резких переходов яркости), cегментация изображений (например на области, однородные по определенному признаку);
  8. Анализ оптического потока (нахождения перемещения пикселей между двумя изображениями);

Приложения методы Computer Vision находят в следующих областях:


  1. Мультимедия-приложения, игры (реальный пример - автоматическое создание модели игрока для Quake3), расширенная реальность (комбинация виртуального окружения и реальных объектов) ;
  2. Естественный интерфейс человек-компьютер, основанный на жестах, мимике и голосовых командах пользовтаеля, не обремененный устройствами "удобными компьютеру" (клавиатурой, мышью) - human-centered computing;
  3. Медицина (автоматический анализ медицинских изображений – рентген, томография, УЗИ);
  4. Охранные системы (идентификация личности, детекторы движения, распознавание и отслеживание движущихся объектов, распознавание автомобильных номеров и т.д.);
  5. Системы распознавания рукописного и печатного текста;
  6. Сжатие видео с учетом содержимого передающегося видеопотока (content-aware video compression);
  7. Промышленность (дефектоскопия, контроль качества, промышленные роботы)
    • автомобилестроение;
    • электроника;
    • машиностроение;

Какие исследования велись и ведутся в нашей лаборатории:


Мы занимались и занимаемся следующими направлениями:

  1. Автоматический анализ изображения человеческого лица
  2. Локализация лица на статическом изображении, в видеопотоке;
  3. Локализация характерных черт лица на статическом изображении, в видеопотоке;
  4. Автоматическое определение выражения лица;
  5. Реконструкция 3D формы по изображениям;
  6. Определение положения точек в трехмерном пространстве по их проекциям на изображении;
  7. Распознавание/отслеживание объектов на изображении и в видеопотоке;

Какие приложения были созданы/создаются с использованием перечисленных методов?

Естественный интерфейс человек-компьютер


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

Проект включает в себя исследования по следующим направлениям:

  • Локализация (отслеживание) объекта (лица) на последователности кадров;
  • Локализация (отслеживание) характерных точек (черт) лица на последователности кадров;
  • Распознавание выражения лица;
  • Вычисление оптического потока;
  • Вычисление ориентации объекта в пространстве по проекциям его характерных точек на изображении;
  • Преобразование информации о положении головы пользователя в координаты перемещения курсора мыши.

Реконструкция модели головы по фотографиям


Целью проекта является реконструкция 3D модели головы по нескольким фотографиям. Результатом является текстурированная VRML модель, которая может использоваться в различных мультимедиа приложениях - таких, например, как видеоконференции, расширенная (виртуальная) реальность и синтетическое видео для сжатия видеопотока (MPEG-4). Проект ведется совместно с Samsung Advanced Institute of Technology. В рамках проекта ведутся исследования по следующим направлениям:

  • Анализ изображения лица (локализация лица, локализация черт лица);
  • Интеллектуальная модификация (морфирование) 3D модели;
  • Стереореконструкция карты глубины;
  • Реконструкция 3D модели по шумным данным карты глубины;
  • Генерация полной текстуры по одной фронтальной фотографии;
  • Реалистичная анимация 3D модели (мимика и выражения лица);

С чем в основном придется иметь дело, занимаясь Computer Vision:


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

  • Теорию вероятностей и математическую статистику;
  • Функциональный анализ;
  • Аналитическую геометрию;
  • Дифференциальные уравнения;
  • Методы оптимизации (например - линейное программирование, методы градиентного спуска, генетические алгоритмы, вариационные методы);
  • Динамическое программирование;
  • Методы распознавания и классификации (например - нейросети);
  • Линейную алгебру (например - метод главных компонент);
  • Математическую морфологию;
  • Ряд методов из области обработки многомерных сигналов;
  • Численные методы в приложении к большинству из уже перечисленного

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

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

Некоторые задачи Computer Vision


Восстановление 3D формы по 2D изображениям


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

Стереореконструкция карты глубины (Shape from Stereo)


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

Подробнее об алгоритмах и проблемах стеререконструкции можно прочесть в:
[1] – главы 12, 13; [2] – главы 12, 13; [3] – раздел 6. "Vision Geometry and Mathematics"

Реконструкции поля нормалей и карты глубины по закраске полутонового изображения (Shape from Shading);


Задача, обратная вычислению яркости точек сцены при визуализации (rendering). Яркость точки поверхности зависит от:

  • свойств источников света;
  • характеристик поверхности;
  • ориентации поверхности относительно падающего света;
  • точки зрения наблюдателя;

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

Подробнее об алгоритмах и проблемах Shape from Shading можно прочесть в:

[2] – главы 12, 13; [3] - раздел 5 "Geometric Feature Extraction Methods", [4].


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


Также можно перечислить следующие методы восстановления 3D формы:

  • Реконструкции карты глубины по текстуре (shape from texture)
  • Определению формы по перемещению (shape from motion)
  • Определение формы объекта по дефокусировке (shape from defocus)
  • Определение формы объекта по контуру (shape from contour (silhouettes))

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

[1] – главы 12 - 15; [2] – глава 12, 13; [3] – раздел 5 "Geometric Feature Extraction Methods", раздел 6. "Vision Geometry and Mathematics".


Обнаружение/распознавание/отслеживание объектов, обладающих определенными свойствами на статическом изображении и в видеопотоке;


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

Вот примеры "популярных" объектов для распознавания/обнаружения:

  • Человеческие лица, черты лиц;
  • Человеческие фигуры;
  • Автомобили, самолеты, всевозможная техника (для систем спутникового наблюдения)
  • Дорожная разметка (для систем автоматического управления автомобилем)
  • Лесные пожары, границы водоемов, лесов (для систем спутникового наблюдения)
  • Биологических объектов, патологий на медицинских изображений.
  • Символы некоторого алфавита, регулярные структуры определенного вида (распознавание печатного и рукописного текста, штрих-кодов)

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

В числе основных сложностей при решении данной задачи – большое разнообразие входных данных и трудность выделения общих свойств внешнего вида для объектов естественного происхождения. Объекты искусственного происхождения обычно(не всегда) распознавать значительно легче.

В методах описания свойств объетка для нахождения можно выделить два крайних направления:

Обощение и использование эмпирических данных и правил об объекте (top-down, bottom-up)


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

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

Хорошо, если известны дополнительные условия задачи и получения входных изображений, например:

  1. Приблизительно известны ожидаемые размеры божьих коровок (то есть известно увеличение камеры и расстояние до снимаемого объекта);
  2. Нас интересуют только божьи коровки, сидящие на листьях (значит, если принять, что листья зеленые, можно рассматривать только объекты, находящиеся на зеленом фоне);

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

Ссылки на литературу:

[5], [10] – в приложении к обнаружению/локализации лица на изображении;

Моделирование внешнего вида объекта, использование инструментария распознавания образов (pattern recognition) .


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

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

Примеры часто используемых классификаторов:

  1. Прямое сравнение по какой-либо метрике пространства векторов признаков (например, сумме разности каждого элемента вектора) тестового изображения с изображениями-шаблонами (template-matching);
  2. Нейросети (обычно для черно-белых изображений) – на входы нейросети подаются значения элементов вектора, на выходах формируется сигнал, классифицирующий объект на изображении;
  3. Метод опорных векторов (support vector machines) – для распознавания изображений;
  4. Моделирование многомерной функции распределения векторов признаков изображений объекта, оценка вероятности принадлежности тестового изображению к смоделированному распределению;

Прямое представление черно-белого изображения размера mxn в качестве вектора порождает пространство размерности m*n (яркость каждого пикселя – значение элемента вектора в таком пространстве). То есть изображение сравнительно небольшого разрешения (100x100) порождает пространство размерности 10,000. Работать в таком пространстве непросто, поэтому применяются различные методики снижения размерности, например метод главных компонент (principal components analysis, PCA)

Другие примеры харастеристик (признаков) изображений, используемых для их классификации и распознавания:

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

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

[1] – главы 25, 26;
[2] – главы 4, 8;
[5], [10] – в приложении к обнаружению/локализции лица на изображении;
[7] – использование нейросетей для обнаружению/локализции лица на изображении;
[8] – коллекция ссылок на метриалы по распознаванию образов;

Комбинированные подходы


Разумеется, помимо этих "крайностей", существует множество подходов, в которых скомбинированы идеи и методы из двух описанных областей. Комбинированные подходы встречаются значительно чаще, нежели "чистые". К ним можно отнести, например распознавание и локализацию объектов с помощью деформируемых моделей ([3] – раздел 11, [8]), сочетающих в себе как ограничения заданные разработчиком, так и моделирование статистических свойств изображений объекта.

Выделение на изображениях структур определенного вида (например, краев - резких переходов яркости), сегментация изображений (например, на области, однородные по определенному признаку);


Эту задачу можно рассматривать как более этап решения предыдущей задачи – распознавание и выделение на изображениях объектов "низкого уровня" - например:

  • Однородных областей, связных компонент;
  • Краев (edge detection), углов (corner detection), протяженных областей темных пикселей (ridge, valley detection), контуров объектов;
  • Простых геометрических фигур (прямых линий, кругов, других кривых второго порядка);
  • Скелетов объектов;

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

Хорошее описание многих известных методов и алгоритмов этой области можно найти в [1], [2], [3].

Работа с видеопотоком


Обработка видеопотока накладывает некоторые дополнительные условия и ставит дополнительные задачи, такие как, например:

  1. Определение изменившихся областей между двумя кадрами (motion detection)
    [2] – глава 9, [3] – раздел 9. Motion and Time Sequence Analysis;
  2. Автоматическое исключение статического фона из рассмотрения (background subtraction)
    [2] – глава 9, [3] – раздел 9. "Motion and Time Sequence Analysis", раздел 13. "Scene Understanding";
  3. Определение перемещения пикселей между двумя соседними кадрами (оптического потока – optical flow)
    [3] – раздел 9. Motion and Time Sequence Analysis;

Подробнее о каждой из этих задач можно прочитать в указанной литературе.

Литература и ссылки



Graphics & Media lab (webmaster@graphics.cs.msu.su)