Главная › Статьи

Об авторах

• Шевченко Евгений Валерьевич, студент 5 курса механико-математического факультета Южного Федерального Университета,специальность "Прикладная математика и информатика".
• Беляков Алексей Владимирович, студент 3 курса факультета информационных систем и защиты информации Санкт-Петербургского Государственного Университета Аэрокосмического Приборостроения, специальность "Автоматизированные системы обработки информации и управления".
• Галин Артем Сергеевич, студент 3 курса факультета информационных систем и защиты информации Санкт-Петербургского Государственного Университета Аэрокосмического Приборостроения, специальность "Автоматизированные системы обработки информации и управления".

Санкт-Петербургский офис Intel (Intel Lab), ментор Белоголовый Андрей Владимирович.

Аннотация

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

Disclaimers

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

Все используемые алгоритмы были реализованы авторами собственноручно. Никаких сторонних библиотек типа OpenCV, AForge.NET не использовалось.

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

Программирование разных частей проекта велось на языках С++ и C#.

Введение

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

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

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

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

"Большой взрыв"

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

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

Рис.1 Функциональное разделение проекта

В задаче прослеживается две линии (Рис.1):

1. Устройство ввода информации в "калькулятор" - Input Device. С этими задачами призваны справляться алгоритмы компьютерного зрения, которые позволят выполнять слежение за пальцем, т.е. получать его пространственные координаты в каждый момент времени.
2. Устройство вывода информации - Output Device, т.е. устройства распознавания полученной от пользователя информации. Используются методы машинного обучения.

Критерии, по которым происходило тестирование алгоритмов:

1. Качество - насколько алгоритм инвариантен к фотометрическим изменениям видеоизображения, к трансформации отслеживаемых объектов.
2. Скорость - сможет ли комбинация выбранных алгоритмов успевать работать в режиме реального времени.

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

Резюмирую, каждая деталь схемы, описанной ниже, была получена тестированием и отбором среди десятков ранее предложенных нами или известными до нас. Последние были изучены в статьях http://www.ieee.org/ и общением с сотрудниками английского и французского университетов.

Input Device

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

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

Модель обучения ID:

Рис. 2, Модель обучения ID

Модель обучения работает единовременно, чтобы получить информационный вектор руки. В модели есть блок, который определяет взмах руки, точнее область, в которой происходит взмах. О работе этого блока будет рассказано ниже. Таким образом, чтобы обучить модель узнавать руку, необходимо в начальный момент произвести взмах. После захвата области последняя обрабатывается фильтром Гаусса для уменьшения количества шумов, возникающих в процессе снятия изображения. Дальнейший перевод в систему HSV связан с тем, что она больше всего отвечает модели человеческого глаза. Если пиксель имеет низкую насыщенность, то человеческий глаз не сможет распознать его цвет. Так же происходит и с пикселями, имеющими очень низкую или очень высокую яркость. Таким образом, логично поставить фильтр по S,V координатам, который будет отсеивать пиксели, в которых не выполняется установленные пользователем коридоры по значения S и V, чтобы уменьшить процент ошибок модели.

Захват руки:

На вход блоку подаются пары кадров (текущий и предыдущий) до тех пор, пока возвращаемое значение не будет равно 1. Это будет означать, что координаты и размеры области успешно вычислены. При поступлении пары кадров выполняется их перевод в градацию серого по формуле :
Y = 0.3*R + 0.59*G + 0.11*B

Для увеличения скорости вычислений оба кадра уменьшаются в два раза путём вычисления среднего значения по 4м пикселям. Это даёт возможность увеличения радиуса поиска “похожих” блоков на последующих шагах. Далее производится попиксельное вычитание изображений. На основе этой разности мы создаём битовую карту, в которой значения пикселей будут изменяться от 0 до 1. Значение 0 приписывается пикселу в битовой карте в том случае, если разность пикселей в исходных изображениях не превысила определённого порога. В противном случае пиксел получает значение 1. Значение порога необходимо выбирать в зависимости от качества камеры. В нашем случае мы остановились на значении 20. Далее необходимо разбить всю область изображения на блоки фиксированного размера, для которых будет производиться накопление информации о движении. В нашем случае размер блока составляет 16Х16 пикселей. После этого для уменьшения объёма вычислений для каждого блока необходимо определить количество пикселей, в которых разность превысила порог. Если количество таких пикселей превышает половину пикселей блока, то блок будет помечен для дальнейшего рассмотрения. Для всех помеченных блоков необходимо выполнить процедуру поиска наиболее “похожих” блоков в предыдущем кадре в некоторой окрестности. Размер окрестности выбирается сравнительно небольшой, т.к. работа с кадрами меньшего размера позволит нам её увеличить. В данном случае в два раза.

Мерой сходства блоков мы выбрали метрику Sum of Absolute Difference (SAD).

После нахождения минимума функции SAD мы сможем определить направление и длину смещения блока относительно положения в предыдущем кадре. Далее мы находим самую частую длину вектора, на которую сместились блоки. Для этого мы строим гистограмму, в которой подсчитывается количество векторов разной длины, и находим в ней максимальное значение. После этого необходимо увеличить счетчик для каждого блока, который имеет вектор смещения данной длины. После чего выполняется проверка на то, достигли ли счётчики определённого количества блоков - заданного порога. Количество блоков будет влиять на размер области. Порог будет влиять на время для выделения области. В нашем случае: количество блоков – 15, порогов – 10. Если условие не выполняется, то программа вернёт значение 0, а координаты области не будут определены. Следовательно, на вход программе необходимо будет подавать очередные пары кадров (текущий и предыдущий). После того, как условие выполнится, мы должны сгруппировать расположенные рядом блоки. Далее нам остаётся только найти группу с максимальным количеством блоков.После чего мы определяем координаты и размеры области, в которую попадают блоки этой группы.

Модель сегментации ID:

Рис. 3, Модель сегментации ID

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

Происходит захват всей области изображения, где может появиться рука. Поэтапно происходит обработка изображения фильтром Гаусса, конвертация в HSV, фильтрация по S-V. Новым этапом является вычитание фона: подразумевается, что в начальный момент времени руки в кадре нет. В этот момент можно зафиксировать картинку как фон. И в дальнейшем на этапе,когда рука появится в кадре, сможем вычитать фрейм фона из настоящего фрейма. Таким образом, получится отсечь часть статических предметов, которые по определению не должны сегментироваться.

Backprojection. Имеется некий вектор, полученной моделью обучения ID, g[k] , где k от 0 до 15. Назовем его информационный вектор руки. На основе него построим матрицу обратных проекций по следующему правилу: B[i,j] = g[k]*255 , где A[i,j] принадлежит интервалу k гистограммы g. A[i,j] - пиксель изображения в координатах i,j. g - является нормализованной. Таким образом, чем темнее получился у нас пиксель, тем больше вероятность того, что он принадлежит к искомой руке. Далее устанавливается порог вероятности, по которой мы можем утверждать,что этот пиксель принадлежит руке. Все пиксели вероятность, которые превышает установленный порог, устанавливают значение 255, иначе 0. Таким образом, получается битовая маска. Битовую маску можно наблюдать в видео-демонстрации.

Аппарат математической статистики. В полученной битовой маске находится центр масс. Далее происходит поиск самой удаленной от центра масс "кучности", что и есть кончик пальца. Для упрощения ввода информации были созданы два режима: режим рисования, режим распознавания. Режим рисования включается, когда вытянут один указательный палец. Режим распознавания нарисованной цифры включается, когда ладонь показывает все пять пальцев. Реализовано это в этом же блоке: происходит подсчет соотношения пикселей, попавших в интервал [0.7R,R] и общего количества, где R - расстояние от центра масс до самой удаленной кучности. И в зависимости от соотношения переключаются режимы.

Таким образом, Input Device получает на выходе: координаты трека цифры, нарисованной пользователем. Передача координат в Output Device происходит в момент переключения в режим распознавания, т.е. в момент разжатия всех пальцев.

Output Device

Вектор наблюдений:

Вектор наблюдения является входным параметром Output Device. Обратимся к Рис.4. Разобьем трек, нарисованный пользователем, на фиксированное количество точек x[i] , равноудаленных друг от друга. Вычислим каждый угол вектора, опущенного из точки x[i] в точку x[i+1]. Угол считается от 0 до 360. Далее происходит квантование угла по 20 интервалам. Таким образом, вектор наблюдений будет состоять из фиксированного количества квантов, описывающий цифру.

Рис. 4, Вектор наблюдений

Классификатор - Hidden Markov Model:

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

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

Рис. 5, Output Device

Вычисление полученного арифметического выражения происходит с помощью алгоритмов ПОЛИЗ.

Командная работа

Хочется отметить, что благодаря проекту получилось приобрести навыки работы в команде. Это не только brainstorming, обсуждения алгоритмических сложностеей на митингах, но и командная работа по части программирования: разные модули проекта были написаны на разных языках. Использование маршалинга в dotnet позволило успешно отладить и слинковать все модули, т.е. объединить управлямый и неуправлямые коды.

Видео

Здесь представлена видео-демонстрация проекта.

Благодарности:

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

• Нашему ментору Белоголовому Андрею Владимировичу, который организовывал нашу работу, консультировал нас и брал над нами шефство в самые тупиковые периоды:)
• Тройновскому Борису Константиновичу (доц. СпбГУАП) за проведенную лекцию по скрытым марковским моделям.
• Всем организатором Intel Summer School 2010 за безумно интересно проведенное время.

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

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

Комментарии (8)

Обратная ссылка (1)

• Немного о лете или Как студенты проводят лето с пользой и с Интел – Блоги Intel® Software Network
  11.10.2010 01:07

Оставить комментарий  

Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*