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

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук

3

На правах рукописи

005018884

Домунян Андрей Александрович

Аппаратные и программные средства для анализа жестов руки, наблюдаемых с помощью видеокамеры

Автореферат диссертации на соискание учёной степени кандидата технических наук по специальностям:

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

05.13.05 - Элементы и устройства вычислительной техники и систем управления

3 иди 2012

Москва-2012

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В. А. Трапезникова Российской академии наук.

Научный руководитель:

к.т.н., с.н.с. лаб. №27 ИПУ РАН А.М.Михайлов

Официальные оппоненты:

д.т.н., в.н.с. лаб. №56 ИПУ РАН В.П. Морозов

д.т.н., учёный секретарь ОАО НИИ "Субмикрон" A.B. Лобанов

Ведущая организация: Федеральное государственное бюджетное учреждение науки Вычислительный центр

им. А. А. Дородницына Российской академии наук.

л (г; Защита состоится 17 мая 2012 г. в 11 ч. в большом конференц-зале на заседании диссертационного совета Д.002.226.03 Федерального государственного бюджетного учреждения науки [ Института проблем управления им. В. А. Трапезникова Российской ^академии наук по адресу: 117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Институте проблем управления им. В. А. Трапезникова Российской академии наук.

Автореферат разослан «/2» апреля 2012 г.

Ученый секретарь диссертационного совета Д.002.226.03

кандидат технических наук /j&J^L--A.A. Кулинич

Ü

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Для достижения поставленных целей решаются следующие задачи:

1) Исследование существующих методов распознавания жестов для выявления их достоинств и недостатков, а также определение вычислительной сложности таких методов.

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

3) Разработка требований к вычислительной платформе минимальной сложности, достаточной для реализации разработанных МВС-алгоритмов.

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

5) Апробация качества разработанных МВС-алгоритмов путем натурного моделирования их работы при распознавании произвольных жестов с использованием персонального компьютера.

Методы исследования

Для решения поставленных задач использовались: теория множеств, теория распознавания образов, методы компьютерного зрения, язык программирования Visual Basic 6, язык программирования JAVA и его видео библиотека (Java Media Framework API) для работы с устройствами ввода изображениями в реальном масштабе времени, видеокамера Logitech Webcam Pro 9000.

Научная новизна

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

2) Разработаны алгоритмы почти минимальной вычислительной сложности для распознавания произвольных жестов в реальном масштабе времени.

Практическая значимость работы

1) Программно реализованы алгоритмы почти минимальной сложности для распознавания произвольных жестов в реальном масштабе времени с помощью персональных компьютеров.

2) Разработаны требования к автономной вычислительной платформе, а также спецификация такой платформы, ориентированной на распознавания произвольных жестов, и характеризуемой минимальной сложностью и, соответственной, минимальной стоимостью, абсолютная величина которой зависит от существующей элементной базы.

Реализация результатов работы

Результаты теоретических и экспериментальных исследований, выполненных в диссертационной работе, были использованы компанией FirstCortex, Inc, Maryland, при создании системы MicroVision. Имеется акт о внедрении.

Апробация работы

Положения диссертационной работы докладывались и обсуждались на 53— и 54т конференциях МФТИ, научно-технической конференции "Техническое зрение в системах управления мобильными объектами-2010", международной конференции MEDIAS 2010, международной конференции ANNIE 2007, на международном конгрессе WASET 2009: World Congress on Science, Engineering and Technology, Singapore 2009, на международной конференции ICMMM 2011, Zhengzhou, China.

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

Публикации. Результаты проведенных автором научных исследований опубликованы в 6 работах, среди которых 1 статья в ведущих рецензируемых журналах из списка ВАК России.

Структура и объем работы. Диссертационная работа состоит из введения, 6 глав, заключения и приложения и содержит 124 страницы машинописного текста, включая 28 рисунков, а также список литературы (90 наименований).

На защиту выносятся следующие основные результаты и положения:

1) Метод разностных изображений для выделения признаков объектов при обработке потоков видеокадров, позволяющий существенно снизить общий объем вычислений.

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

3) Результаты экспериментального моделирования разработанных алгоритмов.

4) Требования к автономной вычислительной платформе, спроектированной по результатам моделирования, а также спецификация такой платформы, ориентированной на распознавание произвольных жестов.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, сформулирована основная цель, научная новизна и практическая значимость результатов, приведено краткое описание структуры диссертации.

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

3

преимуществ и недостатков, а также трудностей, возникающих при их программной и аппаратной реализации.

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

Во второй главе описывается постановка и решение задачи выделения признаков, описывающих произвольные жесты руки. В качестве основной характеристики объекта используется его контур. Оконтуривание является первым этапом процедуры выделения признаков. Последовательность контуров достаточно четко описывает изменяющуюся во времени форму руки, о чем свидетельствует то обстоятельство, что человеку не представляет труда распознать жест по серии его контурных изображений. Как отмечено в главе I, фундаментальным способом оконтуривания является 2-х мерное преобразование Фурье, которое позволяет выделить низкочастотную составляющую спектра для ее последующего удаления. Затем, в результате применения обратного преобразования Фурье, восстановленный исходный объект принимает вид контура, так как участкам плавного изменения яркости соответствует низкочастотная часть спектра, удаленная после прямого преобразования. Однако такой подход требует больших вычислительных ресурсов, объем которых имеет порядок 0(N 4), N х N - это размер изображения. Очевидно, что такая вычислительная нагрузка велика для работы с видеоклипами в реальном

масштабе времени.

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

4

только динамику ее движения. Кроме того есть возможность избавиться от сомножителя 0(М2), если рассматривать только точки изображения без их локальных окрестностей. С учетом вышесказанного в работе выбрана стратегия анализа пар изображений, результатом которого является разностное изображение. При этом, если объект неподвижен, то разностное изображение не существует, так как оно представлено в этом случае пустым множеством точек. Разностное изображение формируется путем поточечного сравнения двух кадров и использования порога яркости Г. Если разность яркостей двух точек с одинаковыми координатами (х, у) меньше заданного порога, то в разностном изображении будет отсутствовать точка с координатами (х, у). Разностное изображение представляется неупорядоченным списком выделенных точек, то есть, списком координат (хи у,), (х2, у2),..., (хР, уР), длина которого меняется в зависимости от степени различия сравниваемых изображений.

Второй этап выделения признаков начинается с прореживания разностного списка. При прореживании в списке оставляется только каждая к-ая точка (например к = 10). Второй этап заканчивается определением угловой ориентации контурных точек по отношению к каждой точки списка. Для этого каждая точка списка окружается квадратной локальной рамкой. Точки рамки перенумеровываются от 0 до Ь - 1, где Ь - это число точек в рамке. Если рамка пресекает контур объекта в точке а, то признак описывается значением а. Если рамка пресекает контур объекта в точках а и в, то признак описывается значениями (а, в) и т.д.

Рис. 1. Определение локального признака

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

Последовательность выделенных признаков является входной информацией для системы распознавания признаков, выходом которой является множество имен распознанных признаков и которая завершает этап выделения признаков.

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

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

0(РОТ,1/) = гшпО(^,[/)

Здесь О (Рт, и) - это расстояние между множествами Рп и V.

Каждое множество Р„, а также множество С/ - это множества чисел {а,, а2, аР}, значения которых равны локальным ориентациям контурных точек относительно центральной точки локальной рамки, как это описано в главе II. Поскольку множества {а,, а2, ..., аР} могут иметь разное число элементов, то рассматриваемая задача не сводится к сравнению Р-мерных векторов, а требует сравнения множеств переменной длины. Для этого используется метод позиционного расстояния, предложенный

А.М.Михайловым.

Поскольку максимальное число угловых ориентаций, представляющих локальный признак равно Ь, то каждое множество ^ можно взаимнооднозначно представить бинарной последовательностью содержащей Ь разрядов. Так, если ¿=8, то набор чисел 0, 4 и 6 представляет последовательность 10001010. В общем случае нормализованное к единице позиционное расстояние между двумя множествами имеет вид:

£п(&к(апХ(ЖЬп.к))/

°Р(А'В)= /1п(апОЯЬп.к) 0)

Здесь \к\<Я, п = 1, 2, ..., I и Я - это радиус ступенчатой функции.

Так, если А = 1000110000100100001 и

В = 0100001001000010010, то позиционное расстояние между А и В равно нулю Ор(А, В) = 0 при Я = 2. Это означает, что смещение позиций точек внутри радиуса Я не влияет на позиционное расстояние между последовательностями.

Нормированное позиционное расстояние изменяется в интервале от 0 до 1. Если расстояние р между неизвестным входным признаком и

6

ближайшим признаком из базы данных, содержащих на текущий момент N признаков, превышает порог Tt, то неизвестный признак получает имя N + 1 и заносится в базу данных. Создаваемое новое имя по существу является именем нового класса, к которому будут отнесены все признаки, являющимися соседями (с точностью до порога Т{) признака, занесенного в базу данных. Если р < Т,, то входной признак идентифицируется именем его ближайшего соседа. Таким образом, база признаков, вначале пустая, постоянно расширяется.

Задача распознавания отдельных контуров по совокупности описывающих их признаков ставится следующим образом. Входной информацией служит набор имен признаков, описывающих текущий контур. Если признак повторяется в контуре I несколько раз, то число повторений игнорируется. Обозначая контур, подлежащий идентификации через U, а число контуров в базе контуров на текущий момент через С, мы приходим к необходимости минимизации следующего выражения:

D7(/, [/)-> min, 1еС где расстояние DT (/, U) = х°*'ц"} (2)

2,n('n OR ип)

вычисляется путем представления множеств I и U в виде бинарных последовательностей, аналогично тому, как это делалось при решении первой задачи. Как и при решении первой задачи, если расстояние р между неизвестным входным описанием контура и ближайшим контуром из базы данных, содержащих на текущий момент С контуров, превышает порог Тг, то неизвестный контур получает имя С + 1 и заносится в базу данных. Создаваемое новое имя будет именем нового класса, к которому будут отнесены все контуры, являющимися соседями (с точностью до порога Т2) контура, занесенного в базу данных.

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

Dm(K U) -> min, VeC

•"'WM't^äs <3>

V пробегает имена клипов-кандидатов, U - это имя идентифицируемого клипа, а коэффициенты а„,Ъ„ - это веса элементом аппроксимирующих множеств.

Перед началом обучения фиксируются внешние классы клипов, число которых равно числу жестов, подлежащих распознаванию. Однако, при выбранном значении порога 3-го уровня Т3 < 1 меньше единицы, число внутренних классов, то есть классов автоматически создаваемых системой на третьем уровне, может превышать число внешних классов третьего уровня. Таким образом, несколько внутренних классов могут соответствовать одному внешнему классу, что учитывается с помощью функции соответствия f\ внешний класс =/ (внутренний класс). Заметим, что на 1-м и 2-м уровне внешние классы отсутствуют.

Четвертая глава посвящена разработке архитектуры программного обеспечения, реализующего индексные структуры хранения и извлечения данных, разработанные А.М.Михайловым и П.Я. Мином. Индексная система содержит:

1) Слиски элементов.

2) Модуль записи, обновляющий списки элементов.

3) Модуль чтения, подсчитывающий активность элементов списков и выделяющий наиболее активные элементы.

4) Модуль обратной связи, сравнивающий наиболее активные образы с входным образом.

При решении прикладных задач параметрами, подлежащими заданию, являются

1) R - число списков.

Параметр Я определяет число элементов (адресного) массива, адреса которого соответствуют номерам списков.

2) G - общее число элементов в прямых списках.

3) М- максимально возможное число разных элементов в списках

Модуль чтения. Концептуально наиболее простой вычислительной

структурой, реализующей модуль чтения индексного алгоритма, является множество одномерных массивов фиксированной длины, ячейки каждого из которых предназначены для хранения элементов соответствующих списков. Такая система может быть программно задана как двухмерный массив lnd[R, М], где М - это максимальное число элементов в списке. Кроме того, необходимо использовать одномерный массив последних элементов списков E[RJ и гистограмму активности элементов Н[А{]. При поступлении на вход адреса списка add, из данного списка последовательно считываются хранящиеся в нем имена элементов, и строится гистограмма их активности.

for (x = 0; x <= E[add]; x ++) { H[Ind[add, xJJ ++;

;

Поскольку идентифицируемый вход представлен совокупностью адресов, то этот цикл повторяется для всех адресов из входной совокупности.

Работа модуля чтения завершается нахождением максимально активного элемента я:

п: Н[п] = max Щп], п е Еа п

Здесь Еа с Е, это подмножество активных элементов.

Недостаток такой схемы состоит в нерациональном использовании памяти. Нерационально используется память потому, что списки могут иметь разную длину, изменяющуюся в широком диапазоне и, тем самым, большая часть зарезервированной памяти, общим размером M x R, не будет использована. Поэтому в данной работе списки определяются динамически.

Для экономии памяти, вместо одного двухмерного массива IndfR, M] определяются три одномерных массива - массив адресов AfRJ, массив имен N[G] и массив связей LfGJ. Такой подход позволяет использовать память наиболее рационально, так как при этом не требуется делать предположений о неизвестных размерах списков.

В отличие от вышерассмотренного двухмерного способа реализации модуля чтения, при поступлении на вход адреса списка add из массива адресов A[R] считывается адрес первой связи р -- A[add], а адрес второй связи и адреса всех последующих связей р = Afp] считываются из массива связей вплоть до обнуления адреса связи. Каждая связь р не только итеративно указывает на следующую связь р = Afp], но и указывает с помощью массива имен N[G] на имя, ассоциированное с ней и =N[pJ. Последнее обстоятельство позволяет построить гистограмму активности имен. Таким образом, алгоритм построения активности при использовании одномерного модуля чтения имеет следующий вид:

р = A [add];

while (р> 0) {

H[N[L[p]]] ++;

}

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

Модуль записи построен аналогично модулю чтения с той разницей, что после обнуления связи в результате итеративного процесса создается новая связь в массиве связей и по адресу, определяемому этой новой

9

связью, создается новое имя в массиве имен. Значение этого имени определяется путем увеличения значения последнего созданного имени на единицу.

р - Afadd];

while (р> 0) { р = L[p] ++;

}

L[p]=p + 1;

NfpJ = п + 1;

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

Общая процедура обновления модулей

В целом процедура обновления прямых и обратных списков состоит в следующем.

1) При поступлении на вход неизвестного образа производится считывание информации из прямого модуля и выделяется множество наиболее активных имен образов с использованием гистограммы активности.

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

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

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

. Структура прямого модуля содержит: (А) адресный массив (¿) массив связей (ТУ) массив имен

(Я) массив для хранения гистограммы

Размер адресного массива равен числу значений признаков образа. Размер массива связей равен числу идентифицируемых образов Р, умноженному на среднюю длину образа 5: Ь = РБ.

Размер массива имен равен размеру массива связей. Размер гистограммы равен числу образов: Н = Р.

Таким образом, объем памяти прямого модуля равен

МО - А + РБ + Р = А +Р($+1) Структура обратного модуля идентична структуре прямого модуля, за исключением того, что в нем отсутствует гистограмма и размер адресного модуля равен числу образов, то есть

М = Р + РЗ = Р($+1) Следовательно, общий объем памяти равен

,М = А+2Р(3+1) (4)

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

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

М = В(ЦАк + 2Рк(Бк + 1)) к = 1,2,..., К

где К — это число уровней и В — это число байт, использованных для представления целочисленных переменных.

Оценка объема памяти, необходимой для решения задачи распознавания видеоклипов, дается в главе V главе на основании результатов экспериментального моделирования.

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

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

В системе также предложено использовать индексы образов, работающие последовательно на 3-х уровнях. Индекс первого уровня распознает локальные признаки контура руки. Двухмерные (х, у) координаты локальных признаков являются неупорядоченным множеством. В данной задаче из случайного списка координат контурных точек выделяется с шагом 5=16 некоторый подсписок точек. Затем центр окна 5x5 помещается в каждую выделенную точку. Последовательно просматриваются точки рамки окна, которым присвоены номера от 0 до 4* 5-1. В массив из 4*5 -х ячеек заносятся единицы, каждая из которых означает пересечение рамки с контуром в соответствующей позиции. Полученная бинарная последовательность представляет локальный признак. Хотя использованный подход к выделению локальных признаков, очевидно, является далеко не идеальным, более сложный подход потребовал бы большего количества вычислительных операций.

Индекс первого уровня описывается индексной парой {p}f, {f}p, в которой позиция р определяется позицией единичного бита в бинарной последовательности, например, 0110000000101000000000001, представляющей локальный признак f. Пример индекса образов, содержащий копии двух имен, показан на рис. 2.

2 2 2

11 2 11 12 1

0110000000101000000000001 (1-й признак) 0100100000001000000001001 (2-й признак) 012345... (координаты колонок)

Рис. 2. Индекс образов

Здесь числа под разделительной линией представляют имена признаков, занесенных в соответствующие колонки {/}р, координаты которых определяются позициями единиц в представлении признаков с помощью бинарных последовательностей. При поступлении на вход неизвестного признака и, колонки^?,, сканируются для подсчета чисел появлений имен признаков, то есть строиться гистограмма Нф. Координаты отсчетов, превышающих порог распознавания 7}, признаков, выбираются в качестве имен признаков-кандидатов. Затем признаки-

кандидаты С, сравниваются с входом и с помощью позиционного расстояния (1) с целью минимизации выражения:

Dp(f, и) -> min, f еС где / - это имена признаков-кандидатов. Имя победителя становится именем идентифицированного признака. Но если множество признаков-кандидатов пусто, то поступивший признак считается новым и ему присваивается новое имя в результате увеличения значения последнего зарегистрированного признака на единицу (в данном примере имя 3). Затем копии имени 3, число которых равно размеру числу единиц в представляющей его бинарной последовательности, заносятся в колонки (f}p, координаты которых соответствуют положению единиц в поступившей последовательности, представляющей данный признак. Число идентифицируемых классов признаков зависит от порога распознавания признаков Tf. Если 7} = 1, то признаки не различимы. В другом крайнем случае, когда, Tf = 0, все признаки различны. Это означает, что малейшая вариация признака приводит к регистрации нового класса признаков. Если просмотреть видеоклип при 3} = 0, то число классов признаков увеличивается практически неограниченно. Экспериментально установлено, что в рассматриваемом приложении число идентифицируемых классов равно 29 при 7/= 0.5.

Данный алгоритм повторяется на уровнях 2 и 3. На уровне 2 создается индексная пара {j}it {i}f, где /' - это имя кадра с изображением руки. Координаты индекса кадров или изображений {i}f- это имена признаков, содержащихся в изображении i. Если признак повторяется в изображении i несколько раз, то число повторений игнорируется. Таким образом, изображения представлены множествами признаков, а не множествами взвешенных признаков. Заметим, что, хотя взвешенные признаки повышают качество разделения признаков, в то же время, взвешенные признаки снижают разрешающую способность системы. После построения гистограммы H(i) и задания порога распознавания изображений 7}, выбираются изображения-кандидаты С и минимизируется расстояние:

DAi, и) -> min, ieC где используется мера (2). При этом i пробегает по именам изображений-кандидатов, au- это неизвестное изображение. Было экспериментально установлено, что данной задаче число классов-изображений равно 99 при Г,- = 0.4.

На третьем уровне порядок изображений в видеоклипе учитывается при анализе последовательности их имен i. Эти последовательности приближенно описываются с помощью взвешенного алфавита 2-го порядка. При этом исходный алфавит имен Р заменяется на алфавит,

13

состоящий из сдвоенных символов. Например, если алфавит состоит из 3-х символов (а, Ъ, с), то алфавит второго порядка РР содержит символы А=аа, В=аЪ, С=ас, 1)=Ьа, Е=ЪЬ, Р=Ьс, С=са, Н~сЪ и 1-сс. В этом случае последовательности, например аЪсЪ и ЪсаЪ, записываются с помощью алфавита второго порядка как ВРН и РОВ, соответственно. Таким образом, вместо индексной пары

{¡}т где V — это имя видеоклипа, создается индексная пара {1}ю {у};, в которой координаты / - это буквы алфавита 2-го порядка. После построения гистограммы Н (у) и задания порога распознавания Т„ видеоклипа выбираются клипы-кандидаты и минимизируется расстояние:

где используется мера расстояния (3), V пробегает имена клипов-кандидатов, а и- это имя идентифицируемого клипа.

Для тестирования системы были записаны 3 видеоклипа, показанные на рис. 2, 3 и 4. Каждый клип содержит от 400 до 600 кадров. При частоте 20 кадров в секунду один клип длится около 25 секунд. Из-за ограниченных размеров страницы на рисунках показаны только несколько фрагментов каждого жеста. В каждом клипе соответствующий жест повторяется 5-6 раз. При этом повторы разделены 3-2 секундными интервалами. Очевидно, что человек не может абсолютно точно воспроизводить свои жесты. Поэтому первые три жеста в каждом клипе использовались для обучения системы, а оставшиеся жесты для ее тестирования. Было установлено, что после обучения система оказалась способной правильно распознать оставшиеся жесты. Были выбраны следующие пороги распознавания: 7} = 0.5, Т, =■ 0.4, 7'у =0.5. В результате выбора таких значений были идентифицированы 29, 99 и 17 внутренних классов на уровнях 1, 2 и 3, соответственно. Следует отметить, что при обучении порог распознавания клипа 1\, был равным величине 0.5, а при распознавании - величине 0.99. Последний выбор повышает обобщающую способность системы на этапе распознавания.

ВТп{у, и) —» ттуеС

Рис. 2. Фрагменты первого жеста из видеоклипа 1, показанные в виде двух строчек по направлению справа налево.

Г

) \

\ \ '

/Г- ' (

о

лП

л

Рис. 3. Фрагменты второго жеста из видеоклипа 2, показанные в виде двух строчек по направлению справа налево.

щ..

I

9>

г

П \ . Г-

1»

Н

У. ■ > <-..

V

Рис. 4. Фрагменты третьего жеста из видеоклипа 3, показанные в виде двух строчек по направлению справа налево.

Объем памяти, необходимой для решения задачи распознавания видеоклипов. Число значений признаков первого уровня А/ = 64, так как локальная рамка представлена 64 точками. Число образов первого уровня Р1 = 29, так как по результатам моделирования число идентифицируемых признаков равно 29. Средняя длина образа первого уровня не превосходит максимальной длины, равной 5у = 64, что определяется размером локальной рамки. Подставляя данные значения в выражение (4), имеем:

М, = 64 + 2*29*(64+1) = 3834 Число значений признаков второго уровня А2 = 29, так как число образов первого уровня, равное числу идентифицируемых признаков, равно 29. Число образов второго уровня Р2 = 99 по результатам моделирования. Средняя длина образа второго уровня не превосходит

числа образов первого уровня, то есть, = 29. Подставляя данные значения в выражение (4), имеем:

М2 = 29 + 2*99*(29+1) = 5969 Число значений признаков третьего уровня Аз = 2562, так как используется алфавит пар символов, каждый из которых принимает одно из 256 А8С-значений. Число образов третьего уровня Р3 = 17 по результатам моделирования. Средняя длина образа третьего уровня не превосходит числа образов второго уровня, то есть, Б3 - 99. Подставляя данные значения в выражение (4), имеем:

М3 = 65536 + 2*17*(99+1) = 68936 Поскольку все элементы и адреса массивов представлены целыми 2-х байтными числами, то суммарный объем памяти составляет:

М=2(М, + М2 + М3) = 2*(3834+5969+ 68936) = 157478 байт Следует учитывать, что оценка объема памяти выполнена для 3-х произвольных жестов. При этом в оценке памяти максимальной составляющей является Аз, которая, являясь фиксированной величиной, не возрастает с увеличением числа распознаваемых жестов.

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

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

Архитектура системы МикроЗрение. Разработанные алгоритмы легко реализуются на обычном персональном компьютере, снабженном веб-камерой. Однако коммерческое применение такой системы будет весьма ограниченно, поскольку средняя стоимость ноутбука на сегодняшний момент составляет примерно 30000 руб. Главой целью, достижению которой посвящена настоящая работа, является разработка специализированной вычислительной платформы стоимостью примерно 300 руб. Такая проектируемая платформа получила название МикроЗрение, представляя собой НТМ-интерфейс. Ее основные компоненты — это микрокамера и микропроцессор. В настоящее время микрокамеры в основном используются в мобильных телефонах. В такую микрокамеру встраивается микропроцессор, в котором жестко запрограммированы алгоритмы предобработки, обеспечивающие автоматическое фокусирование, подбор выдержки в зависимости от внешней освещенности и ряд других функций. Однако производители не предоставляют пользователю возможностей их программирования. Для решения поставленных в работе задач дополнительно требуется модуль

анализа изображений. Для обеспечения такой возможности принято решение о соединении микрокамеры с внешним по отношению к ней микропроцессором.

Формат изображения выбирался на основе результатов моделирования из соображений минимизации объема буферной памяти изображений.

1) По результатам моделирования сделан вывод, что для решения поставленных задач распознавания жестов использование только красной составляющей RGB-видеосигнала не приводит к снижению качества.

2) При моделировании использовались изображения с разрешением в 640 х 480 пикселов. Вместе с тем производители микрокамер указывают в спецификациях, что в микрокамерах применяется формат Байера (Bayer pattern). В этом формате красная составляющая считывается из зарядных элементов пиксельной матрицы с шагом 2. Поэтому реальное разрешение красной составляющей изображения составляет 320 х 240 пикселов. В системе используются буферное изображение и бинарное разностное изображение. С учетом использования только красной составляющей полученного изображения, объем буферной памяти для изображения может быть выбран, при представлении пиксела одним байтом, равным 320*240 = 76800 байт. При этом объем памяти бинарного изображения равен 76800 бит.

3) Оценка глубины пикселов. В соответствии с результатами главы И, выходом системы зрения является разностное изображение, то есть список координат точек, в каждой из которых разность красных пикселов двух последовательных изображений превыщает заданный порог Т. По результатам моделирования было выбрано значение Т- 32.

Очевидно, что для создания разностного изображения достаточно использовать только одно буферное изображение. Действительно, первое изображение заносится в буфер без изменения. При поступлении очередного пиксела q второго изображения

- пиксел q сравнивается с соответствующим пикселом р буферного изображения;

- если абсолютная разность превышает порог, то есть, | р - q \ > Т, то координатная пара, представляющая сравниваемые пикселы, пополняет список точек разностного изображения.

; - пиксел р первого изображения заменяется на пиксел q.

Далее, вместо соотношения | р - q \ > Т были использованы соотношения:

| р /16 - ^/16 | > 0 и | р /16 - ^/16 | > 1 что эквивалентно использованию только 4-х старших разрядов красной яркости. В результате математического моделирования было установлено, что

соотношение | р /16 — ц /16 | > 0 приводит к 2.6% ложных позитивных сигналов, а соотношение | р /16 - #/16 | > 1 - к 2.9% ложных негативных сигналов. И тот и другой исход приводит к искажению менее 3% точек разностного изображения, что практически не влияет на качество распознавания жестов.

По этим соображениям, окончательная глубина представления пикселя была выбрана равной 4-м разрядам. С учетом всего вышесказанного в этом разделе, объем В буфера изображений был выбран равным В = 76800/2= 38400 байт.

Таким образом, алгоритм вычисления разностного изображения работает следующим образом.

1) первый видеокадр заносится в буфер изображения. При этом в каждом пикселе учитываются только 4 старших разряда.

2) первый пиксель (координаты (0, 0)) первого кадра считывается из буфера.

3) первый пиксель второго кадра (координаты (0, 0)) поступает из видеокамеры.

4) в нем рассматриваются 4-е старших разряда.

5) значение яркости одного пикселя вычитается из другого.

6) берётся модуль получившегося выражения.

7) если модуль положительный, то точку бинарного изображения с координатами (0, 0) записывается 1; в противном случае - 0.

8) первый пиксель второго кадра заменяет первый пиксель первого кадра.

9) перейти к 2) и повторить процедуры для всех пикселей текущего кадра.

10) передать управление алгоритму анализа.

11) если выход алгоритма анализа равен 0, то перейти к (2).

12) задержка длительностью в 1-2 сек. переход к (1).

Оценка необходимого быстродействия микропроцессора.

1) Обновление разностного изображения: I = 320x240x8 = 614400 обращений к памяти.

2) Алгоритм анализа: обращение к спискам индексов на трех уровнях при вычислении гистограммы.

Число обращений к ячейкам памяти N = 3 *Н*Б, где Н - максимальная длина списка, 8- число обрабатываемых списков. Из таблицы результатов эксперимента.

Бтах =99, Нтах =99/29 (уровень 2) = 4. Таким образом, число обращений к спискам в прямой связи ЫП=3*Нтах*Бтах = 3*99*4 = 1200 обращений.

Аналогично, в обратной связи число обращений ЫВ не превышает

величины 1200.

Таким образом, общее число обращений не превышает величины N08 = 2400.

Число операций при поиске максимума гистограммы не превышает максимального числа классов Ртах = 99 (на втором уровне).

Поскольку каждое обращение к памяти сопровождается одной операцией суммирования, то общее число арифметических команд при анализе видеоинформации можно оценить как 2*Ж>5 = 4800 команд

3) Вычисление локальных признаков: ЫЬ - Ь*Р, где ¿—число точек разностного изображения не превышает 2000 (по результатам эксперимента). При этом обрабатывается каждая 8-я точка 64. Т7 — это число точек локальной рамки. Следовательно, Ж=2000*64/8 = 16000 обращений к памяти.

Общее число команд при предобработке и анализе видеоинформации складывается из команд обращения к памяти Я и из арифметических операций А -сложений, вычитаний и сравнений. При этом:

Я = N013 + ЫЬ = 2400+16000= 18400 обращений к памяти

А = А'ОВ + Ртах = 2400+99 = 2499 арифметических команд

Время обращения определяется быстродействием памяти. Также предполагаем, что одна арифметическая операция выполняется за, максимум, 256 тактов. Поэтому время обработки одного разностного изображения составляет:

ТА = А + Я = 639744 тактов м/процессора + 18300 обращений к памяти. Общее время (считывание кадра, предобработка и анализ) = / + Я + А = 632800 обращений к памяти + 639744 тактов микропроцессора. Учитывая, что обрабатываются 30 кадров в секунду, оцениваем требующуюся частоту микропроцессора и памяти как

^ = 1 /1 + Я+А = 38.2 МГц (26 наносекунд).

Требования к вычислительной платформе

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

А. Назначение устройства

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

Б. Состав устройства

1) Миниатюрная видеокамера (чип-камера)

- оптическая линза камеры должна обеспечивать четкое изображение объекта на расстоянии от 25 см до 2-х метров при нормальном уличном или комнатном освещении.

- частота кадров: 20 - 30 кадров в сек; разрешение 640 х 480 пикселов х 8 разрядов (только 4 старших разряда будут использоваться в приложениях).

- 8Ш (или более) разрядный параллельный видеоинтерфейс.

- питание от внешнего источника до 3.6 вольт.

- от 6.5 до 27 МГц кварцевый осциллятор.

2) Микропроцессор (120 МГц), содержащий

- статическую память объемом 128 Кбайт и внутреннюю флэш-память объемом от 512 до 1024 Кбайт.

- USB-интерфейс для программирования микропроцессора.

- 8Ш (или более) разрядный параллельный интерфейс для подключения видеокамеры.

- питание от внешнего источника до 3.6 вольт.

- от 4 до 27 МГц кварцевый осциллятор.

- цифро-аналоговый преобразователь.

- коммуникационный интерфейс 12С и USB 2.0 интерфейс.

- порты входа/выхода для прерываний.

3) Печатная плата (материнская плата) интегрирующая части в единое устройство.

Буфер изображения

Используется только красная составляющая изображения размером 320 х 240 при глубине представления пиксела в 4 байта.

Следовательно, объем буфера изображения равен 38400 байт.

Выход системы зрения

- Список координат точек разностного изображения: < 3000 точек, представленных 2-х байтовыми числами, то есть, < 6000 байт.

- 2-х мерный массив разностного изображения 320 х 240 х 1 бит = 9600 байт.

Общий объем памяти, для хранения информации, представляющей текущий видеокадр: 54000 байт.

Программное обеспечение содержит 2 части:

Считывание изображения: сканирование пикселов матрицы видеокамеры, обновление буфера изображения и формирование бинарного разностного изображения и списка его точек. Алгоритм считывания рассмотрен в разделе Требования к формату изображения (Глава VI).

Алгоритм анализа изображения: вычисление признаков, распознавание признаков, распознавание контура объекта, содержащегося

в кадре и распознавание последовательности контуров движущегося объекта. Выходом алгоритма анализа является команда, передаваемая в цифро-аналоговый преобразователь. Алгоритм анализа рассмотрен в главе V. Оценка объема памяти, используемой алгоритмом анализа, дана в главе V и равна 212000 байт.

Таким образом, общий объем памяти, для обеспечения работы обеих частей программного обеспечения не превышает 512000 байт. При этом для представления информации текущего кадра и алгоритма считывания отводится статическая память микропроцессора объемом в 128 Кбайт, а для алгоритма анализа — внутренняя флэш-память объемом в 512000 байт.

В. Требования к разработке печатной платы

- Прототип печатной платы должен позволить разработчику прототипа и заказчику проверить идеи, заложенные в устройство, в том числе путем создания и отладки

программного обеспечения, ориентированного на применение в выбранном процессоре.

- Не требуется проводить минимизацию размеров прототипа печатной платы.

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

- Физические размеры устройства не должны превышать 1.5 х 1.5 х 1 см (в таком устройстве интегральные микросхемы могут устанавливаться на шлейф, для максимального снижения стоимости устройства в массовом производстве).

- Устройство должно работать от внешнего источника питания, с напряжением, не превышающим 4.6 вольт и потребляемым током не более 80 мА в активном режиме.

- Цена устройства в массовом производстве не должна (на сегодняшний день) превышать 300 рублей, включая компоненты и сборку.

Г. Рекомендуемые компоненты

Микропроцессор STM32F207 имеет следующие характеристики:

- размер подложки 4x4 мм.

- частота 120Мгц.

- 128 Кбайт внутренняя статическая память.

- встроенная флэш-память (128 Кбайт, 256 Кбайт, ..., 1024 Кбайт).

- прямой доступ в память.

- интерфейсы 12С и USB 2.0.

- контроллеры прерываний.

- 16 МГц осциллятор используется по умолчанию при запуске.

- работает с внешним источником питания в 3.6 вольт.

- интерфейс для подключения цифровой камеры (8ми и 14й1 разрядный параллельный интерфейс, поддерживает передачу до 27 Мбайт в сек при 27 МГц или 48 Мбайт в сек. при 48 Мгц, поддерживает 8-ми разрядный монохромный видеосигнал или сигнал в формате Байера).

- цифро-аналоговые и аналого-цифровые преобразователи. Ориентировочная стоимость - $5 при размере партии более 100000

штук.

Микропроцессор STM32F207 по своим характеристикам отвечает требованием, сформулированным в разделе «Требования к вычислительной платформе».

Микрокамера (камера на одной микросхеме) vs6724 имеет следующие характеристики:

- размер изображения 1600 х 1200 пикселей.

- 30 кадров в сек.

- размер устройства 3x3 мм с линзой.

- 8-ми разрядный параллельный видеоинтерфейс .

- диапазон напряжения питания 3-5 вольт.

- стоимость $2 при заказе больших партий.

Микрокамера vs6724 по своим характеристикам отвечает требованием, сформулированным в разделе «Требования к вычислительной платформе». Кроме того, суммарная стоимость выбранных компонентов равна $7, что меньше проектной стоимости всего устройства, равной $10. Реализация проекта МикроЗрение

Проект МикроЗрение является результатом сотрудничества с компанией

FirstCortex, Inc 5817 Edson Lane Rockville, MD 20852 Tel: (301) 792-1354 e-mail: vfe@mai 1 works .org

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

Анализ, проведенной компанией FirstCortex подтвердил техническую реализуемость проекта и возможность обеспечения заявленной стоимости устройства в массовом производстве ($10).

Был составлен список работ, проведение которых необходимо для

реализации проекта, то есть для разработки полной технической документации и 10 образцов устройства. Этот список включает: Задачи

Разработка детальной технической спецификации устройства Разработка технической документации Сборка прототипа устройства Тестирование и отладка

Контроль за ходом работ и консультации с клиентом

Стоимость_

Инженерно-управленческие работы $ 142000

Компоненты, программные средства, производство и сборка $8410 Общая стоимость $ 150410

Акт об использовании результатов компанией Б^СоЛех, 1пс вынесен в приложение к диссертации.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

2) Разработаны алгоритмы почти минимальной вычислительной сложности для распознавания произвольных жестов в реальном масштабе времени.

3) Программно реализованы алгоритмы почти минимальной сложности для распознавания произвольных жестов в реальном масштабе времени с помощью персональных компьютеров.

4) Разработаны требования к автономной вычислительной платформе, а также спецификация такой платформы, ориентированной на распознавания произвольных жестов, и характеризуемой минимальной сложностью и, соответственной, минимальной стоимостью, абсолютная величина которой зависит от существующей элементной базы.

5) Разработанные требования к автономной вычислительной платформе, ориентированной на распознавания произвольных жестов, переданы компании Рнв^оПех. Анализ требований, выполненный компанией, подтвердил практическую реализуемость проекта. Стоимость реализации оценена компанией в размере $150000 тысяч долларов США. Полученное заключение прилагается.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Домунян A.A. Кортексный сканер // Труды МФТИ том 3, № 2 (10) (2011). ISSN 2072-6759. - С. 80 - 83.

2. Домунян А. А. Программно-аппаратная реализация кортексного сканера. Техническое зрение в системах управления мобильными объектами-2010 // Труды научно-технической конференции-семинара Выпуск 4.-С.310-316.

3. Домунян А. А. Программно-аппаратная реализация кортексного сканера // MEDIAS2010 Труды Международной научной конференции. ISBN 978-5-88835-030-0. - С.28 - 31.

4. М.Н. Сергийчук, A.A. Домунян. Решение задачи эталонного поиска методом нейронного кортекса // Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть IX. Инновации и высокие технологии.— М.: МФТИ, 2010. — 132 с. ISBN 978-5-7417-0391-5. - С. 103 - 104.

5. A.A. Домунян, М.Н. Сергийчук. Кортексный сканер // Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть I. Радиотехника и кибернетика. Том 1.— М.: МФТИ, 2010. — 178 с. ISBN 978-5-7417-0322-9. - С. 45-49.

6. A.A. Домунян, А. М. Михайлов, М.Н. Сергийчук. Поисковая система Кортекс // Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных наук в современном информационном обществе». Управление и прикладная математика. Том 2. — М.: МФТИ, 2011. — 148 с. ISBN 978-5-7417-0404-2. - С. 121 - 122.

Личный вклад диссертанта в публикациях, выполненных в соавторстве: в [4] обосновал метод нейронного кортекса и привёл пример его применения, в [5] автор научно обосновывает применение используемого алгоритма, в [6] автор описывает поисковую систему и описывает метод определения расстояний.