Разработка подсистемы создания стереоизображения

Разработка подсистемы создания стереоизображения

Одесская государственная академия холода

Факультет информационных технологий

Курсовая работа

по дисциплине «Разработка САПР»

Одесса 2010 г.

Содержание

1. Анализ проблемы

Введение

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

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

1. Анализ проблемы

Анализ проблемы проводится с помощью пяти этапов:

1) Достижение соглашения об определении проблемы.

2) Выделение основных причин-проблем, стоящих за проблемой.

3) Выявление заинтересованных особ и пользователей.

4) Определение границы системы решения.

5) Выявление ограничений, которые необходимо наложить на решение.

Подробно останавливаясь на каждом этапе:

Этап 1. Достижение соглашения об определении проблемы.

Постановка проблемы

Этап 2. Выделение основных причин-проблем, стоящих за проблемой

В основе лежит выявление корневых причин.

В проблеме распознавания лиц лежат следующие причины:

1) Низкое качество фото.

2) Большое количество шумов на фото.

3) Скрытие части лица инородными телами.

4) Несоответствия, изменчивость света.

Этап 3. Выявление заинтересованных особ и пользователей

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

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

Может бать несколько групп заинтересованных особ. Главной является группа пользователей.

Пользователи и особы, заинтересованные в создании новой системы:

Этап 4. Определение границы системы решения

Система будет взаимодействовать с внешним окружением:

Этап 5. Выявление ограничений, которые необходимо наложить на решение

2. Теоретическая часть

2.1 Цель и постановка задачи

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

Основные задачи:

1. Поиск оптимального метода для распознавания лиц на изображении;

2. Поиск лица на статическом изображении с масштабированием;

3. Поиск лиц на объемном изображении (т.е. на изображении, содержащем большое количество лиц);

4. Поиск лиц на комплексном изображении.

2.2 Алгоритм AdaBoost

Алгоритм AdaBoost представляет собой эффективное средство обучения классификации. Особенностью используемого в нем подхода является принцип отбора и объединения набора простых и малоэффективных свойств в одно решающее правило, обладающее высокой классифицирующей способностью [1], [2]. Получение такого решающего правила является основной задачей обучения распознаванию образов. Во многих практических задачах получить его или его параметры не так просто, что связано со сложностью расположения объектов в пространстве признаков. С другой стороны, практически всегда можно эвристически сформировать целый набор достаточно простых характеристик [2], свойственных объектам распознавания, или предложить эвристическую процедуру для их генерации. Подобная процедура формирования свойств может, например, представлять собой объединение первичных признаков х1,…,хn в виде произведения различных их степеней:

yk = (1.1)

где индекс k определяет соответствующий набор (,…,).

Такой способ формирования, вообще говоря, приводит к бесконечному множеству возможных свойств. Даже если каждое из них будет обладать слабой классифицирующей силой, то их совместное использование может дать вполне приемлемый по качеству результат. Алгоритм обучения AdaBoost строит решающее правило в виде линейной комбинации выходных значений слабых классификаторов, при этом достигается экспоненциальное уменьшение ошибки с увеличением числа свойств на обучающем наборе [3].

Если представить слабый (элементарный) классификатор двух классов и ,, полученный на основе описанных выше простых свойств, в виде

hk()=бyk+в ,hk()R(1.2)

классифицирующее свойство, которого проявляется в смене знака на границе классов:

hk (x)=(1.3)

то в результате обучения будет получен классификатор вида

h()=(1.4)

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

Процедура обучения по методу AdaBoost заключается в следующем [2]. Пусть заданы обучающие объекты, принадлежащие двум разным классам, в виде

(),…, ( , где (1.5)

где вектор признаков, определяющий объект распознавания,

-

число, определяющее его классовую принадлежность,

m - объем обучающей выборки.

Изначально каждому обучающему объекту задается одинаковый вес

(1.6)

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

Для каждого цикла обучения t=1, ..., ,T :

1. Выбирается лучший элементарный классификатор дающий минимальную ошибку на обучающем наборе с учетом текущих весов объектов минимальную ошибку на обучающем наборе с учетом текущих весов объектов D .

В более простом случае используются классификаторы вида ;

2. Выбирается действительное число >0;

3. Выполняется «пере взвешивание» обучающего набора согласно следующей зависимости

(i)= (1.7)

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

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

(1.8)

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

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

Алгоритм обучения AdaBoost может быть успешно применен для решения задач распознавания изображений, в частности для быстрого поиска на изображении произвольных объектов [4]. Требования к быстродействию алгоритмов классификации при решении последней задачи являются очень жесткими [5]. Для обеспечения требуемого быстродействия в работе предложены два основных принципа.

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

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

2.3 Использование примитивов Хаара для описания свойств изображений

Основными критериями качества признака для решения широкого круга задач, и в особенности задач распознавания зрительных образов, являются его разделительные свойства и сложность его получения, учитывая необходимость быстрого поиска области объекта, что предполагает классификацию большого числа кандидатов при обработке одного изображения [5]. С точки зрения необходимости использования достаточно простых алгоритмов получения признаков, перспективным является использование Хаар-подобных свойств, в отличие от предложенных в [4] и [6], представляющих собой результат сравнения яркостей в двух прямоугольных областях изображения (рис. 1).

Рисунок 1 - Вид прямоугольных свойств, используемых в качестве признаков при обнаружении объектов: а) - области не пересекаются; б) - области пересекаются

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

R= (1)

в случае непересекающихся областей (рис. 1а), и

R= (2)

в случае пересечения областей (рис. 1б). Здесь индексы Ч и Б означают черную и белую области соответственно, а Ч ? Б обозначает область пересечения областей черного и белого цвета; S - сумма яркостей пикселей изображения, находящихся под областью; N - число пикселей изображения, находящихся под областью. Таким образом, соответствующие отклики означают разность средних яркостей пикселей реальной области изображения, находящейся под белой частью изображения свойства, и находящихся под его черной частью (рис. 1а, б). Отклик такого свойства не зависит от масштаба изображения и смещения изображения по шкале яркости. Кроме приведенных выше выражений для отклика признака на конкретную область изображения (1) и (2) в качестве значения отклика на свойство можно использовать и следующие выражения:

1) в случае непересекающихся областей

R= (3)

В случае пересечения областей

R= (4)

2) в случае непересекающихся областей

R= (5)

В случае пересечения областей

R= (6)

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

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

2.4 Обучение классификации

Исследования эффективности предложенных свойств для решения задач обнаружения объектов на изображениях проводились на задаче обнаружения лиц. Обучение классификации лицо/фон выполнялось на основе метода AdaBoost. Для обучения использовалась база данных изображений лиц, содержащая 2000 изображений. Каждое изображение было размечено вручную и масштабировано к масштабу 12Ч12 пикселей. В базе данных содержались изображения лиц людей разных рас, полученные при разном угле и интенсивности освещения, изображения лиц с очками различной формы, бородой и (или) усами, имеющие отклонения от фронтального ракурса съемки до 30 градусов. Для расширения базы данных и учета изменения направления освещения она была дополнена зеркальными отражениями каждого изображения лица. Таким образом, итоговая база изображений лиц содержала 4000 изображений размером 12Ч12 пикселей.

Для формирования базы изображений фона была разработана специальная программа, которая на основе сформированного набора изображений разного размера (около 400 изображений), не содержащих лица, случайным образом формировала 100 000 изображений. При этом случайным образом выбирались как положения области фона на изображения, так и ее масштаб. Предполагая необходимость формирования в конечном итоге каскада классификаторов, в программе была учтена возможность формирования набора изображений фона, удовлетворяющих заданному условию, в частности условию прохождения изображения фона через все предыдущие классификаторы. Таким образом, программа позволяет формировать базу изображений фона, трактуемых уже обученными классификаторами как лица. Необходимость подобной программы объясняется тем фактом, что после обучения ошибка ложного обнаружения должна быть очень низкой (порядка <10-6), а соответственно число обучающих объектов фона как минимум больше 106, что при использовании алгоритма обучения AdaBoost влечет значительные вычислительные затраты, существенно затрудняющие анализ получаемых результатов.

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

Процесс поиска наиболее эффективного свойства на каждом этапе обучения, предусмотренном используемым алгоритмом обучения, предполагает перебор всех возможных прямоугольных свойств, и выбор из них наилучшего, в смысле минимума ошибки, вычисленной по взвешенной обучающей базе данных изображений, соответствующей данному этапу обучения. Так как число вариантов прямоугольных свойств даже для используемого масштаба изображений велико, чтобы осуществить полный перебор (порядка 4Ч107, то есть для полного перебора необходимо выполнить указанное число оценок ошибок классификации по имеющейся базе данных обучающих объектов, а это сама по себе вычислительно сложная задача, учитывая размеры обучающих выборок), поиск наилучших свойств выполнялся в два этапа. На первом этапе выполнялся поиск свойства, дающего наименьшую ошибку из всех отобранных случайным образом. На втором этапе методом последовательных приближений найденное на первом этапе прямоугольное свойство уточнялось по критерию минимизации ошибки. Такой подход позволил успешно проводить обучение каждого классификатора каскада за удовлетворительное время (0,5 - 3 часа). В ходе обучения необходимо учитывать необходимость включения в исследуемый набор свойств и классификаторов, которые с точки зрения классификации взвешенного обучающего набора не имеют смысла, например, классифицируют все изображения как 1 объект. Если таких свойств не будет, то скорость спада ошибки обучения в зависимости от цикла обучения может существенно замедлиться. Это связано с балансом весов объектов одного и другого классов. В ходе обучения этот баланс может существенно смещаться как в одну, так и в другую сторону и ошибка принятия всех объектов 1-го класса за 2-й класс может оказаться наименьшей из всех других исследованных классификаторов на данном этапе. Введение подобных «бесполезных» классификаторов позволяет поддерживать при обучении приемлемый баланс между суммарными весами объектов обоих классов. С точки зрения итогового решающего правила в виде линейной комбинации элементарных классификаторов это означает смещение классифицирующей поверхности, определяемой линейной комбинацией простых классификаторов, относительно начала координат. Для ускорения процесса обработки изображений с целью обнаружения лиц, количество свойств, используемых на начальных каскадах, должно быть, с одной стороны, минимально возможным, а с другой, обеспечивать допустимый пропуск ложных лиц на следующие, более вычислительно сложные и обеспечивающие более тонкое разделение лиц и фона, этапы обработки.

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

Ограничение на ошибку пропуска лиц - не более 1% - принято, так как для решения задачи классификации с заданным качеством (95% правильного) планировалось использовать не более 5 классификаторов в каскаде. Как видно из приведенной на рис. 2 зависимости, значения ошибки ложной тревоги достаточно быстро уменьшаются с увеличением числа используемых прямоугольных свойств. При этом функцию ошибки можно с удовлетворительной точностью в области больших значений числа используемых свойств аппроксимировать экспоненциальной зависимостью. Рассчитанные параметры и вид этой аппроксимирующей функции приведен на рис. 2. Из графика также видно, что для отсеивания на первом этапе 99% ложных лиц достаточно использовать 47 прямоугольных признаков и линейную разделяющую функцию, получаемую на выходе алгоритма обучения.

Рисунок 2 - Зависимость ошибки ложной тревоги от числа используемых элементарных признаков, при ограничении на ошибку пропуска лица 1%

Рисунок 3 - Зависимость среднего числа используемых при прохождении двух каскадов прямоугольных свойств (К) от числа свойств, используемых на промежуточном первом каскаде (К1)

Приведенная зависимость позволяет оценить вычислительную сложность алгоритма классификации, состоящего из двух каскадов. Если мы зададимся ограничением ошибки пропуска лиц в 2% и требованием к ошибке ложного обнаружения - 1%, то для среднего числа используемых свойств при прохождении двух каскадов будем иметь зависимость, приведенную на рис. 3. При получении этой зависимости учитывалось, что второй классификатор каскада содержит 47 свойств, что гарантированно обеспечивает ошибку ложного обнаружения менее 1%. Анализируя приведенные данные можно заключить, что в данном случае оптимальным с точки зрения минимизации вычислительной сложности алгоритма при прохождении каскада из двух классификаторов является использование в первом классификаторе 10 прямоугольных признаков. Это, согласно приведенным на рис. 3 данным, позволяет уменьшить вычислительные затраты более чем 2,5 раза по сравнению с использованием только одного второго классификатора. Получение подобных зависимостей позволяет управлять вычислительной сложностью алгоритма каскадной классификации и настраивать этот параметр исходя из требований к скорости обнаружения лица на изображении. Наряду с исследованием скоростных характеристик алгоритма каскадной классификации были проведены исследования по определению зависимости качества классификаторов от используемых выражений для определения отклика прямоугольных свойств на изображение. Методом AdaBoost были экспериментально получены зависимости ошибки классификации от числа используемых свойств в случае использования выражений для отклика изображения на прямоугольное свойство (1, 2) и (5, 6). Сравнительные данные приведены на рис. 4. Исходя из приведенных данных можно говорить о том, что при одном количестве используемых прямоугольных свойств суммарная ошибка классификации лицо/фон при использовании выражений (1, 2) меньше, чем при использовании выражений (5, 6). Используя отклики прямоугольных свойств, получаемые на основе выражений (1, 2), был получен каскад из 4 классификаторов, содержащих соответственно 5, 8, 100, 200 признаков. При этом два первых классификатора использовали квадратическую разделяющую функцию, полученную методом, описанным в [7], а два последних - линейную, полученную методом AdaBoost. Достигнутые после обучения классификаторов показатели качества составили 0,04 - вероятность пропуска лиц, и 8Ч10-6 - вероятность ложного обнаружения. При этом была получена скорость обнаружения - 30 кадров размером 640Ч480 пикселей в секунду при поиске лиц в диапазоне ,с шагом в 1,1 раза на компьютере Pentium Core2Duo с частотой процессора

Рисунок 4 - Зависимость суммарной ошибки от числа используемых признаков для разных способов получения отклика свойства на изображение

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

2.5 Концептуальная модель системы

Разрабатываемая система, по сути, представляет собой своеобразный «конвейер», на вход которого подается изображение. (Оно и являются основными входными данными). Далее происходит сам процесс распознавания лиц, используя алгоритм AdaBoost и примитивы Xaapa. На выходе получаем изображение с выделенными лицами. Процессом подачи изображения управляет оператор.

Общая концептуальная схема

Общая схема системы

I этап. Поиск лица в видеопотоке

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

Этот алгоритм обеспечивает такие преимущества данной технологии как устойчивость к шуму и неравномерной засветке лица.

II этап. Отслеживание лица между кадрами видеопотока.

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

III этап. Выделение основных признаков лица

На этом этапе с использованием алгоритма анализа контуров производится выделение на видеоизображении лица его основных признаков: глаз, носа, рта и т. Д.

Преимуществом этого метода является надежная работа при нефронтальном позиционировании лица.

IV этап. Нормализация изображения лица

После выделения основных признаков лица, его изображение приводится к стандартному виду: для надежного распознавания изображение лица должно иметь определенные размеры, необходимо выдержать расстояние между глазами, положение лица относительно центра. Для этого изображение масштабируется, разворачивается, в некоторых случаях также определяется положение лица (фас, положение в три четверти или точные 3D координаты), автоматически нормализуется яркость и контрастность.

V этап. Преобразование индивидуальных признаков лица

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

Система отслеживания лиц на видеопотоке- это второй этап.

Функционально, программа состоит из следующих подсистем:

-Отслеживание лиц на видеопотоке - нахождения лица.

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

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

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

Задачи и цели разрабатываемой системы направлены на перевод ручного труда на ЭВМ (т.е его ускорение) и устранение человеческого фактора при проведении исследований компьютерных систем .

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

· Работа с видео

· Выделение контуров

· Математический аппарат для информационных исследований

· Набор форм выходных документов передачи на следующий этап «распознавания».

3. Реализация программной системы

3.1 Среда разработки « Borland Delphi»

Это интегрированная среда разработки ПО для Microsoft Windows на языке Delphi (ранее носившем название Object Pascal), созданная первоначально фирмой Borland и на данный момент принадлежащая и разрабатываемая Embarcadero Technologies. Embarcadero Delphi является частью пакета Embarcadero RAD Studio и поставляется в трёх редакциях: Professional, Enterprise и Architect.

Новое в Delphi 2010

§ Поддержка Windows 7 API, Direct2D и мультисенсорного ввода.

§ Поддержка касаний и жестов для Windows 2000, Windows XP, Windows Vista и Windows 7.

§ IDE Insight в Delphi 2010 -- мгновенный доступ к любой функции или параметру.

§ Delphi 2010 включает свыше 120 усовершенствований для повышения производительности.

§ Визуализаторы отладчика.

§ В Delphi 2010 включена поддержка Firebird с помощью dbExpress.

§ Классический интерфейс Delphi 7 и панель инструментов со вкладками как опция.

Редакция Delphi 2010 Professional

§ Локальное подключение к базам данных InterBase, Blackfish SQL и MySQL при подключении через dbExpress.

§ Развертывание Blackfish SQL в системах с одним пользователем и размером базы данных 512 МБ.

§ Веб-библиотека VCL с ограничением числа подключений (не более 5).

Редакция Delphi 2010 Enterprise

§ Delphi 2010 Enterprise включает все возможности редакции Delphi 2010 Professional и ряд дополнительных возможностей.

§ Подключение к серверам баз данных InterBase, Firebird, Blackfish SQL, MySQL, Microsoft SQL Server, Oracle, DB2, Informix и Sybase при подключении через dbExpress.

§ Разработка многоуровневых приложений баз данных DataSnap.

§ Развертывание Blackfish SQL в системах с пятью пользователями и размером базы данных 2 ГБ.

§ Веб-библиотека VCL без ограничения числа подключений.

§ Дополнительные возможности UML-моделирования.

Редакция Delphi 2010 Architect

§ Delphi 2010 Architect включает все возможности редакции Delphi 2010 Enterprise и ряд дополнительных возможностей.

§ Обратное проектирование, анализ и оптимизация баз данных.

§ Создание логических и физических моделей на основе сведений, извлеченных из баз данных и файлов сценариев.

§ Удобные для восприятия и навигации диаграммы.

§ Delphi 2010 Architect дает возможность прямого проектирования путем автоматического создания кода базы данных из моделей.

§ В Delphi 2010 Architect усовершенствовано двунаправленное сравнение и объединение моделей и структур баз данных.

Литература

1. Leith E. N. and Upatnieks J. Wavefront reconstruction with diffused illumination and three-dimensional objects // J. Opt. Soc. Am.--1964.--V. 54.--P.1295.

2. Денисюк Ю. Н., Суханов В. И. Голограмма с записью в трехмерной среде как наиболее совершенная форма изображения // Успехи физических наук.-1970.-Вып. №6.

3. Система голографического кино. сайт лаборатории ЛФР-Медиа.

4. Ray Zone, Stereoscopic cinema & the origins of 3-D film (University Press of Kentucky, 2007) ISBN 0-8131-2461-1, p. 110