Про зрение (компьютерное)

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

Intel всегда славилась особым интересом к разработкам в области расширения возможностей компьютера по взаимодействию с окружающим миром. Наиболее известный сегмент в этом контексте -- распознавание речи. Но вот совсем недавно компания объявила о новых разработках в другой области -- компьютерном зрении. Как выяснилось, в не таком уж далеком от нас Нижнем Новгороде один за другим "выпекаются" релизы библиотеки OpenSource Computer Vision Library (OpenCV). Она стала настоящим хитом в научном мире -- общее количество загрузок приближается к 76 тысячам. И по этому интегральному показателю совместное творение исследовательских лабораторий Intel, расположенных в Нижнем и Санта-Кларе, в состоянии поспорить с популярными играми.

"Швейцарский нож" из Нижнего

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

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

В пятницу, 5 марта 1999 г., свет увидел первый релиз библиотеки CVL. 6 июня 2000 г. появился Web-сайт проекта с официальной документацией, а спустя ровно месяц родилась новая форма старой сущности -- OpenCV 00.00.32. Код приобрел статус открытого, начала формироваться коммуна независимых разработчиков, которые хотели и могли внести вклад в развитие технологии. Соответствующий раздел был открыт на сайте sourceforge.net/projects/opencvlibrary/, откуда любой желающий может загрузить 60-мегабайтовый пакет исходных кодов. Дискуссионная группа, насчитывающая около 2 тыс. человек, функционирует на сайте www. yahoogroups.com/group/OpenCV. С точки зрения интерфейсов и совместимости библиотека тоже достаточно открытая. В данный момент существуют версии как для Windows, так и для Linux, налажено взаимодействие с пакетом MathCAD.

Несмотря на то что процесс разработки еще не завершен, множество организаций уже приступили к практическому воплощению возможностей OpenCV. Например, в числе пользователей библиотеки такие структуры, как NASA (управление роботом на основе отслеживания движений человека), InSpeck (оптические измерительные системы), eRT (игрушки-роботы). Потенциально же область применения библиотеки гораздо шире -- от эмуляции "синего экрана" в кинематографе (на основе выделения фона по статистическим измерениям или по удаленности расположения от стереокамеры) до отслеживания человеческой мимики в аудиовизуальных системах распознавания речи.

Механика чудес

Библиотека функций... Насколько прозаично это звучит, настолько же прозаично ее содержание, и тем впечатляюще выглядят результаты. Описание ее начнем с наименее интеллектуально ценных, но абсолютно необходимых элементов любой системы обработки изображений -- подсистемы работы с памятью. Все операции базируются на использовании блоков фиксированного размера, образовывающих некое подобие стековой структуры (ее заголовок содержит указатель на текущий незаполненный блок и число свободных байтов в нем). Функции извлечения и записи в стек элементов носят соответствующие названия: cvSeqPop, cvSeqPush. Вы обратили внимание на приставку Seq? Да, метафора стека определяет лишь самый нижний уровень хранилища, на более высокой ступени находятся последовательности, или sequences. Они представляют собой нечто вроде цепочки блоков файла, размещенных в секторах жесткого диска, -- своего рода надструктуру. Последовательности, в свою очередь, стали строительным элементом для конструирования графоподобных структур, т. е. в OpenCV изображения или любые иные допустимые типы данных можно оформить как иерархический граф. Это, пожалуй, наиболее распространенный способ сохранения информации о сцене и составляющих ее объектах.

Если же говорить о том, что находится в структурах данных OpenCV, то первое, о чем следует упомянуть, это, собственно, изображения. Поскольку библиотека создана лабораторией Intel, нет ничего удивительного в использовании для этих целей IplImage -- формата, заимствованного из Intel Image Processing Library (IPL). Впрочем, в IplImage инкапсулируются другие стандартные форматы изображений. Помимо глобальных операций по созданию нового изображения или удалению существующего, есть несколько макросов попиксельного редактирования.

Первый шаг к выделению составляющих зафиксированной сцены -- детектирование краев предметов. Для этих целей применяются две группы функций: одна из них базируется на модифицированных фильтрах Собеля (Sobel filters), а другая -- использует трансформации Хоуга (Hough transform). Наиболее просты для понимания алгоритмы последнего упомянутого семейства. Все обнаруженные линейно расположенные пикселы отмечаются единичками в массиве-дубликате растрового кадра. За каждый пиксел, принадлежащий текущей рассматриваемой линии, ко всем ее элементам прибавляется единица. По завершении обработки изображения к массиву применяется пороговый фильтр, обнуляющий все элементы, набравшие недостаточное количество баллов. Таким образом удается убрать мелкие помехи и случайные огрехи. На базе этой простой методики разные ученые умудрились построить массу гораздо более совершенных алгоритмов, описывать которые здесь нет возможности.

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

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

Несмотря на схожие названия, функции морфинга и математическая морфология относятся к разным областям науки обработки изображений. Две основные операции морфологии получили меткое название в меню Corel PhotoPaint -- Grow, что значит нарастить, и Feather -- истончить. В операции участвуют два изображения: исходное и заготовка. Исходное обычно содержит объект -- форму, которую необходимо укрупнить или, наоборот, уменьшить. По мере наращивания заготовке разрешается принимать только такие положения, когда в области объекта есть как минимум один ее пиксел. В режиме уменьшения заготовка должна при любом корректном положении полностью помещаться внутри объекта. На заготовке находится пиксел-перо, отрисовывающий новую "толстую" или "истощенную" реинкарнацию исходного объекта. Самая простая аналогия напрашивается в случае круга: обезьяна и перо на привязи -- если привязь будет длиннее радиуса круга, то примат произведет операцию увеличения, если меньше -- уменьшения.

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

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

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

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

На более высоком уровне обработки располагаются функции выделения контуров. Они работают только с черно-белыми, бинарными изображениями. Распознанные контуры запоминаются в виде цепочки Фримена (Freeman Method) или стандартного набора координат для ломаной. Цепочка представляет собой координаты начальной точки контура, дополненные списком цифр от 0 до 7, указывающих направление, в котором надо искать следующую точку (как вы понимаете на пиксельной плоскости как раз 8 возможных направлений движения).

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

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

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

Другой вариант фиксирования движения -- Motion Gradient Image. Данная разновидность основывается на подсчете градиентов комплексного изображения-истории с помощью фильтров Собеля. Поскольку отсчет времени ведется от момента запуска приложения в миллисекундах и временные отметки в Motion History Image конвертируются в единое число, то, если отобразить его на экране, получится ряд накладывающихся друг на друга бледнеющих силуэтов, самым ярким из них будет последний. Фильтры Собеля позволяют определить направление "течения" комплексного силуэта и тем самым выявить направление движения. Если на изображении присутствует сразу несколько подвижных объектов, выбрать интересующий нас и фазы его движения можно с помощью функции сегментации движения. Она поочередно рассматривает наиболее яркие (следовательно, последние) силуэты и изучает их границы. Как только обнаруживаются более ранние фрагменты силуэтов, непосредственно граничащие с исходными, они присоединяются к ним. На выходе получается несколько так называемых "сегментов движения", каждый из них описывает перемещение одного объекта.

Еще одна группа методик детектирования движения базируется на оптических потоках (optical flow). Не вдаваясь в подробности, укажем только, что эти функции отслеживают изменения яркости изображения. Алгоритм предполагает, что яркость перемещающегося предмета остается неизменной. Действительно, функцию сравнения кадров проще простого "сбить с толку": повесьте на окна жалюзи или включите узконаправленную настольную лампу.

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

Особого внимания разработчиков библиотеки удостоились жесты, а точнее, их распознавание. Раздел Gesture Recognition содержит готовые макрофункции (в данном случае слово "макро" относится к их сути), детектирующие изображение человеческой руки. Здесь активно используются возможность измерения расстояний, обеспечиваемая стереорежимом, метод определения позиций трехмерных моделей, гистограммы и детектирование объектов по характерному распределению яркости и цвета. OpenCV способна и на решение классической задачи по распознаванию лиц с помощью скрытых моделей Маркова (Hidden Markov Models).

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

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

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

Библиотека OpenCV стремительно развивается, о чем свидетельствуют многочисленные опечатки в справочнике функций, местами аскетическая краткость описаний, нереализованные, хотя и отмеченные как перспективные, методики. Вдобавок ко всему некий шутник подписал страницы с алфавитным указателем грозным штампом: "Intel Restricted Secret". Но самый большой секрет сотрудников Intel заключается в том, что они одни из немногих, если не единственные, кто работает над внедрением технологий компьютерного зрения в повседневную практику. Остается только пожелать им преодолеть все "детские болезни", а признание не заставит себя долго ждать. Об этом свидетельствует график темпов загрузки библиотеки с сайта компании. Кроме того, никому не возбраняется принять и личное участие в работе.

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365