Федеральное агентство по образованию
ЮЖНО-УРАЛЬСКИЙГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет — Приборостроительный
Кафедра — Автоматика и управление
ПРОЕКТ ПРОВЕРЕН ДОПУСТИТЬ КЗАЩИТЕ
Рецензент Заведующий кафедрой
____________________________ ______________________
“_____” _____________ 2007__г. “ _____ “ ____________ 2007__ г.
Программное обеспечение системы обработки изображенияв реальном времени
ПОЯСНИТЕЛЬНАЯЗАПИСКА К ДИПЛОМНОМУ ПРОЕКТУ
ЮУрГУ-Д.220200068.000.ПЗ
Консультанты: Руководитель проекта:
______________________________ ___________________________
______________________________ _______________________________
“ _____ “ ______________ 2007 _г. Автор проекта
студент группы ПС-269м .
______________________________ Пушников А.А. .
“ ____ “ ________________ 2007 _ г.
______________________________ Нормоконтролер
______________________________ ______________________________
“ ____ “ ________________ 2007 _г. “ _____ “ ______________ 2007 г.
Челябинск
2007 г.
ВВЕДЕНИЕ
АНАЛИЗ ЗАДАЧИ. ОБЗОРСУЩЕСТВУЮЩИХ МЕТОДИК РЕШЕНИЯ
1. ВЫДЕЛЕНИЕ ОБЪЕКТА НАИЗОБРАЖЕНИИ1.1. ОБЩИЙАЛГОРИТМ СРАВНЕНИЯ ДВУХ ИЗОБРАЖЕНИЙ
1.2. МЕТОД МАКСИМАЛЬНЫХ ПЛОЩАДЕЙ
1.3. МЕТОД ГИСТОГРАММ
1.4. ПОДГОТОВКА ИЗОБРАЖЕНИЯ КРАСПОЗНАВАНИЮ
2. ЗАДАЧА РАСПОЗНАВАНИЕ ОБЪЕКТА
2.1. МЕТОД НАИМЕНЬШИХ КВАДРАТОВ
2.2. МОДЕЛИРОВАНИЕ МНОГОМЕРНОЙ ФУНКЦИИ. РАСПРЕДЕЛЕНИЯ ВЕКТОРОВ, ПРИЗНАКОВИЗОБРАЖЕНИЯ ОБЪЕКТА
Факторныйанализ (FA)
Метод главныхкомпонент (PCA)
Анализнезависимых компонент (ICA)
ЛинейныйДискриминантныйанализ(Linear DiscriminantAnalysis, LDA)
2.3. ДЕФОРМИРУЕМЫЕ МОДЕЛИ.
2.4. СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ(Hidden Markov Models, HMM)
2.5. МЕТОД ОПОРНЫХ ВЕКТОРОВ(Support Vector Machines, SVM)
3. РЕАЛИЗАЦИЯ ПРОГРАММНОГООБЕСПЕЧЕНИЯ
ЗАКЛЮЧЕНИЕ
Введение
В настоящее время вычислительная техника используется вомногих областях человеческой деятельности, являясь удобным и многофункциональныминструментом решения широкого круга задач. Многие отрасли техники, имеющиеотношение к получению, обработке, хранению и передаче информации, взначительной степени ориентируются в настоящее время на развитие систем, вкоторых информация имеет характер изображений. Изображение, которое можно рассматриватькак двумерный сигнал, является значительно более емким носителем информации,чем обычный одномерный (временной) сигнал. Вместе с тем, решение научных иинженерных задач при работе с визуальными данными требует особых усилий,опирающихся на знание специфических методов, поскольку традиционная идеологияодномерных сигналов и систем мало пригодна в этих случаях. В особой мере этопроявляется при создании новых типов информационных систем, решающих такиепроблемы, которые до сих пор в науке и технике не решались, и которые решаютсясейчас благодаря использованию информации визуального характера.
Цель машинного зрения — принятие решений о реальныхфизических объектах и сценах, основываясь на воспринимаемых изображениях. Машинноезрение теснейшим образом взаимодействует с областью обработки изображений,часто трудно однозначно отнести возникающие задачи и применяемые методы решенияк одной из этих областей.
Анализ задачи. Обзор существующих методик решения
Постановка задачи:
Разработать методы поиска на изображении, получаемом свидеокамеры, детали, с дальнейшей идентификацией ее к одной из трех групп, сцелью автоматизации технического процесса.
Задачу можно разделить на три основных этапа:
1. Выделение объектана изображении.
2. Подготовкаизображения к распознаванию.
3. Задача распознаваниеобъекта.Для решения каждойподзадачи, в настоящее время, существует множество различных методик./>1. Выделение объекта на изображении
Для успешного решения задачи распознавания, необходимовыделить искомый объект на изображении, и привести его к нормализованному виду,пригодному для распознавания.
Основной метод нахождения объекта на изображении – сравнениеисследуемого изображения с эталонным. При конечной его реализации, возможнызначительные изменения в алгоритме нахождения объектов.
Критерием успешности выполнения алгоритма, могут служить:
1. Оценка успешностичеловеком.
2. Анализ количестванайденных объектов.
3. Анализ размеровнайденных объектов.
4. Анализ расположениянайденных объектов.
5. Анализ цветовнайденных объектов.
1.1. Общий алгоритм сравнения двухизображений
Определим эталонное изображение, как множество /> точек />, а исследуемоеизображение, как множество />. Пусть /> - функция яркости точкиизображений, определённая на множествах /> и />. Одним из распространённыхподходов для определения областей движения между двумя кадрами изображения /> и /> основываетсяна сравнении соответствующих точек этих двух кадров. [3],[4]. Для этогоприменяется процедура формирования «разности» кадров. Разностью между двумяизображениями, является следующее множество:
/>
где /> - значение порогового уровня,выбираемое таким образом, чтобы отделить точки, в которых кадры изображениязначительно отличаются друг от друга, как правило это искомые объекты, отточек, в которых яркость изменилась незначительно, в связи с мерцаниеосвещения, вибрацией камеры и другими помехами. Изображение /> содержитпредположительные области движения объектов и аддитивный шум, искажающийтекущий кадр. Избавится от шума, позволяют морфологические операции (операциинад бинарным изображением), такие как эрозия, коррозия, а так же различныеспособы фильтрации и оптимальное (экспериментально подбираемое) значение порога/>.
Далее, можно обработать найденные объекты, для этогоиспользуются:
1. Методмаксимальных площадей.
2. Метод гистограмм.
Алгоритм был реализован с помощью библиотеки для обработки изображенийOpenСV. При тестировании алгоритма использовались изображения игровой доски дляигры в го с белыми и чёрными камнями. Пример его работы представлен на рис .
№ Эталонное изображение Исследуемое изображение
Разностное изображение />
Бинаризированое изображение />, при />=10
Отфильтрованное изображение /> 1
/>
/>
/>
/>
/> 2
/>
/>
/>
/>
/> 3
/>
/>
/>
/>
/>
Рис. Пример работы алгоритма.В первом столбце находятсяизображения доски, являющиеся эталонными. Во втором столбце – исследуемыми. Изтретьего столбца видно как изменилось положение камней на доске. В четвёртом ипятом столбцах показано соответственно результат бинаризации изображениятретьего столбца и результат последовательных применений операций коррозии иэрозии к изображению в четвёртом столбце./>1.2. Метод максимальных площадей
Метод приводит найденные объекты к форме, более удобной длядальнейшей обработки, и объединяет отдельные области на разностном изображениив области по признаку их близости друг другу [].
Необходимо выделить области правильной формы, являющиеся достаточнокрупными объектами. Задачу можно формализовать следующим образом: необходимо разбитьмножество точек /> на максимально возможное числонепересекающихся подмножеств />.
Предложим следующий алгоритм решения:
1. На множестве /> конструируем подмножества />, содержащие связанныеточки, выбранные как лежащие рядом друг с другом.
2. Конструируем новые подмножества />, охватывающие те подмножества />, которые лежатрядом друг с другом.
3. Повторяем пункт 2 до тех пор, пока не получим конечноеколичество подмножеств />.
Метод был адаптирован и реализован функциями библиотеки OpenCV. Пример его работы представлен нарис.№
Разностное изображение
/> Результат: области правильной формы Круг Прямоугольник 1
/>
/>
/> 2
/>
/>
/> 3
/>
/>
/>
Рис. Пример работы алгоритма для разных областей правильнойформы.
В первом столбце показаны изображения, полученные после алгоритма сравнения двух изображений.Во втором и третьем столбцах показаны результаты работы вышеописанногоалгоритма. Во втором столбце в результате преобразований мы получаем область ввиде круга, а в третьем в виде прямоугольника.
В первой и второй строке исходным является изображение руки.Как видно, область движения руки не является однородной. В результате работыалгоритма, область движения руки сводиться к однородной области правильнойформы (круг, прямоугольник).В третьей строке исходным являетсяизображение камня на игровой доске. Аналогично, в результате работы алгоритмаобласть движения камня сводиться к однородной области правильной формы (круг,прямоугольник)./>1.3 Метод гистограмм
В методе используется гистограмма изображения искомогообъекта для нахождения объекта с такими же цветовыми характеристиками на серииизображений.
Нужно построить изображение в оттенках серого цвета, содержащеенеобходимые нам объекты.
Введём оператор, который преобразует функцию яркости изображения/> в функциюколичественного распределения пикселей с определенным значением яркости(гистограмму)/>(где k – численное значение яркости):
/>
Обратный оператор /> преобразует гистограмму визображение в оттенках серого.
Алгоритм состоит из следующих этапов:
1. Построениегистограмм искомого объекта /> и исходного изображения />
2. Формируем новуюгистограмму, как нормированное произведение /> и />: />
3. Используяобратное преобразование />, получаем двумерную функцию,которая является искомым изображением в оттенках серого: />
Метод был адаптирован и реализован функциями библиотеки OpenCV. Результаты применения методаприведены на рис.
Доска Черный камень Белый камень Искомое изображение
/>
/>
/> Гистограмма искомого изображения
/>
/>
/> Исходное изображение По гистограмме доски По гистограмме черного камня По гистограмме белого камня №
/>
/>
/>
/> 1 2
/>
/>
/>
/> 3
/>
/>
/>
/>
Искомыми изображениями являются изображения игровой доски, чёрногои белого камня. В таблице представлены их гистограммы. Во всех трёх опытах к исходномуизображению, содержащему область движения, применялся вышеописанный метод. Врезультате в каждом из опытов были получены три изображения. Каждое из изображенийсодержит область, в которой нахождение искомого объекта максимально, т.е. максимальноколичество белых пикселей в этой области/>1.4. Подготовка изображения к распознаванию
С точки зрения задачи распознавания, более удобноиспользовать изображения объектов, имеющие одинаковый размер и приблизительноодинаковую ориентацию в пространстве. Однако, алгоритмы выделения объектов, возвращаютобъекты, искаженные перспективой – различных размеров и произвольноориентированных на изображении.
Для приведения изображения найденного объекта к общему виду,необходимо повернуть его на нужный угол. В эталонных и исследуемых изображенияхобъектов находятся две контрольные точки, после чего изображения разворачивают,так чтобы вектора, соединяющие эти точки, совпали.
Контрольными точками могут быть, например:
1. Видимый центризображения.
2. Центр массизображения.
3. Точка, заметноотличающаяся от остальных по цвету.
4. Центр маркера,поставленного на объекте
и др.
Также, необходимо, привести эталонные и исследуемыеизображения к одному размеру.
Перечисленные выше операции выполняются аффинными преобразованияминад матрицами изображений, общий вид которых:
/>
Используются частные случаи аффинных преобразованияй:
1. Растяжение(сжатие) вдоль координатных осей, задаваемое в виде:
/>
Растяжению вдоль соответствующей оси соответствует значениемасштабного множителя большего единицы. В однородных координатах матрица растяжения(сжатия) имеет вид
/>.
2. Поворот вокругначальной точки на угол />, описываемый формулой:
/>
Матрица вращения (для однородных координат)
/>.
3. Перенос,задаваемый простейшими соотношениями:
/>
Матрица переноса имеет вид
/>.
2. Задачараспознавание объекта
Данное раздел включает в себя широкий класс задач,различающихся в основном тем, каким образом задаются характеристики объекта и вкак требуется его классифицировать.
Методы, применяемые для решения поставленной задачи, вомногом зависят от особенностей объекта, который требуется локализовать.Зачастую, постановка задачи неформальна – описать свойства нужного объекта вматематических терминах бывает достаточно сложно, поэтому задание часто звучит,например, так — нужно найти на изображении все, похожее вот на «это»(картинка с примером). Или, даже просто словами – найти на изображении всех, скажем,божьих коровок. Соответственно, решение задачи заключается в формулировкесвойств распознаваемого объекта и конструировании устойчивого метода нахожденияобъектов, отвечающих указанным свойствам.
В числе основных сложностей при решении данной задачи –большое разнообразие входных данных и трудность выделения общих свойств внешнеговида для объектов естественного происхождения. Объекты искусственногопроисхождения обычно распознавать значительно легче.
В методах описания свойств объекта для нахождения можновыделить два крайних направления:
Обобщение и использование эмпирических данных и правил об объекте(top-down, bottom-up)
Идея заключается в нахождении, обобщении и формулировке в математическихтерминах эмпирических наблюдений и правил о том, как на изображениях обычно выглядитинтересующий нас объект. Продолжая пример с божьей коровкой, можно подметитьследующее:
1. Божьи коровкиобычно рыжего или красного цвета;
2. На спине у нихобычно присутствует некоторое количество черных пятнен (можно также посчитатьпримерное соотношения размера пятен с размером насекомого);
3. Спина у нихразделена на две половинки темной линией, обычно видимой. С одной из сторонэтой линии у божьей коровки голова – темная, соотносящаяся по размерам с теломв некоторой пропорции;
4. Сверху божьякоровка выглядит примерно как эллипс;
Хорошо, если известны дополнительные условия задачи иполучения входных изображений, например:
1. Приблизительноизвестны ожидаемые размеры божьих коровок (то есть известно увеличение камеры ирасстояние до снимаемого объекта);
2. Нас интересуюттолько божьи коровки, сидящие на листьях (значит, если принять, что листьязеленые, можно рассматривать только объекты, находящиеся на зеленом фоне);
Опираясь на перечисленные правила можно построить некийалгоритм их проверки и нахождения объектов на изображении, отвечающих этим правилам.Сложность заключается в том, что, во-первых, правила могут не описывать всехсвойств объекта, во-вторых, правила могут выполняться не всегда, в-третьих, впроцессе нахождения правил и их математической формулировке происходит рядупрощений, уводя все дальше от вида реального объекта. Понятно, что успешностьописанного метод напрямую зависит от фантазии и наблюдательности разработчика.
Моделирование внешнего вида объекта, использование инструментарияраспознавания образов (pattern recognition) .
Суть этого подхода заключается в вычислении некоторыхчисловых характеристик изображения моделируемого объекта (вектора признаков) иприменение различных математических методов для определения «похожести»тестовых изображений на изображение объекта, основываясь на этиххарактеристиках.
Например, само изображение требуемого объекта можно напрямуюпредставить как вектор в многомерном пространстве и натренировать некоторыйклассификатор с помощью набора примеров изображений объектов. Классификатор вданном случае означает некоторый инструмент, принимающий на вход изображение,представленное в виде вектора в многомерном пространстве, и выдающего на выходенекую информацию, классифицирующую входное изображение относительно некоторогопризнака.
Примеры часто используемых классификаторов:
1. Метод наименьшихквадратов;
2. Прямое сравнениепо какой-либо метрике пространства векторов признаков (например, сумме разностикаждого элемента вектора) тестового изображения с изображениями-шаблонами(template-matching);
3. Нейросети (обычнодля черно-белых изображений) – на входы нейросети подаются значения элементоввектора, на выходах формируется сигнал, классифицирующий объект на изображении;
4. Метод опорныхвекторов (support vector machines) – для распознавания изображений;
5. Моделированиемногомерной функции распределения векторов признаков изображений объекта,оценка вероятности принадлежности тестового изображению к смоделированномураспределению (факторный анализ, метод главных компонент, анализ независимыхкомпонент, линейный дискриминантный анализ);
6. Деформируемыемодели;
Прямое представление черно-белого изображения размера m*n вкачестве вектора порождает пространство размерности m*n (яркость каждогопикселя – значение элемента вектора в таком пространстве). То есть изображениесравнительно небольшого разрешения (100x100) порождает пространство размерности10,000. Работать в таком пространстве непросто, поэтому применяются различныеметодики снижения размерности, например метод главных компонент (principalcomponents analysis, PCA)
Другие примеры характеристик (признаков) изображений,используемых для их классификации и распознавания:
1. Статистикараспределения цветов (в различных представлениях, в том числе гистограммаизображения);
2. Статистическиемоменты (среднее, дисперсия, скрытые Марковские модели); Количество и свойства графическихпримитивов в объекте (прямых линий, окружностей – для распознавания символов)(на основе преобразования Хафа)/>/>/>2.1. Метод наименьших квадратов
Перед тем, как начинать рассмотрение МГУА, было бы полезновспомнить или узнать впервые метод наименьших квадратов — наиболее распространенныйметод подстройки линейно зависимых параметров.
Рассмотрим для примера МНК для трех аргументов:
Пусть функция T=T(U, V, W) задана таблицей, то есть из опытаизвестны числа Ui, Vi, Wi, Ti ( i = 1, …, n).Будем искать зависимость между этими данными в виде:
(ф. 1)
где a, b, c — неизвестные параметры.
Подберем значения этих параметров так, чтобы была наименьшейсумма квадратов уклонений опытных данных Ti и теоретических Ti = aUi + bVi + cWi, то есть сумма:
(ф. 2)
Величина s является функцией трех переменных a, b, c. Необходимым и достаточным условиемсуществования минимума этой функции является равенство нулю частных производныхфункции s по всем переменным, то есть:
(ф. 3)
Так как:
(ф. 4)
то система для нахождения a, b, c будет иметь вид:
(ф. 5)
Данная система решается любым стандартным методом решения системлинейных уравнений (Гаусса, Жордана, Зейделя, Крамера).
Рассмотрим некоторые практические примеры нахождения приближающихфункций:
1. y = ax2 + bx + g
Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=y, U=x2, V=x, W=1, a=a, b=b, g=c.
2. f(x,y) = asin(x) + bcos(y) + g/x
Задача подбора коэффициентов a, b, g сводится к решению общей задачи при T=f, U=sin(x), V=cos(y), W=1/x, a=a, b=b, g=c.
Если мы распространим МНК на случай с m параметрами,
(ф. 6)
то путем рассуждений, аналогичных приведенным выше, получимследующую систему линейных уравнений:
(ф. 7)где, />2.2. Моделирование многомернойфункции распределения векторов признаков изображений объекта/> Факторный Анализ(FA)
Факторный анализ (ФА), как и многие методы анализа многомерных данных, опираетсяна гипотезу о том, что наблюдаемые переменные являются косвенными проявленияотносительно небольшого числа неких скрытых факторов. ФА, таким образом, этосовокупность моделей и методов ориентированных на выявление и анализ скрытых (латентных)зависимостеймежду наблюдаемыми переменными. В контексте задач распознавания, наблюдаемымипеременными обычно являются признаки объектов.
Модели с латентными переменными применяются при решении следующихзадач:
· понижениеразмерности признакового пространства,
· классификацияобъектов на основе сжатого признакового пространства,
· косвенной оценкипризнаков, не поддающихся непосредственному измерению,
· преобразованиеисходных переменных к более удобному для интерпретации виду.
Факторный анализ использует предположение о том, что исходныенаблюдаемые переменные (распределенные по нормальному закону!) xiмогут быть представлены в виде линейной комбинации факторов, также распределенныхнормально:
xi=∑k=1..m(aikFk)+ ui; i=1,...,n;
В этой модели присутствуют две категории факторов: общиефакторы (common factors) Fk и специфические факторы(unique factors) ui.Фактор называется общим, если он оказывает влияние на две и более наблюдаемые переменные(математически это выражается в наличии как минимум двух существенноотличающихся от нуля коэффициентов aik для данного фактора Fk).Каждый из специфических факторов ui несет информацию только об однойпеременной xi. Матрица aik называется матрицей факторныхнагрузок (factor loadings) и задает влияние общих факторов на наблюдаемыепеременные.
Содержательно, специфические факторы соответствуютнеобъясненной общими факторами изменчивости набора наблюдаемых переменных.Таким образом их можно рассматривать как случайную ошибку наблюдения или шум,не являющийся ценной информацией для выявления скрытых закономерностей изависимостей. Важным предположением является независимость ui междусобой. Обычно, однако не всегда, общие факторы Fk предполагаютсянекоррелированными (ортогональными).
Важными понятиями ФА являются общность и специфичность наблюдаемойпеременной. На языке ФА доля дисперсии отдельной переменной, принадлежащаяобщим факторам (и разделяемая с другими переменными) называется общностью,дисперсия же приходящаяся на специфический фактор — специфичностью.
Целью ФА является выявление общих факторов Fk,специфических факторов ui и матрицы факторных нагрузок A такимобразом, чтобы найденные общие факторы объясняли наблюдаемые данные наилучшимобразом, то есть чтобы суммарная общность переменных была максимальна (а соответственноспецифичность — минимальна).
Отличие Факторного Анализа (Factor Analysis, FA) от МетодаГлавных Компонент (Principal Components Analysis, PCA)
· Результатом ФАявляется модель, в явном виде описывающая зависимость наблюдаемых переменных отскрытых факторов (МГК это описательный анализ данных, без получения модели);
· ФАпредусматривает ошибку моделирования (специфический фактор) для каждой изнаблюдаемых переменных, в то время как МГК пытается объяснить всю изменчивость,включая шум, зависимостью от главных компонент;
· В МГК главныекомпоненты являются линейными комбинациями наблюдаемых переменных. В ФАнаблюдаемые переменные являются линейными комбинациями общих и специфическихфакторов;
· Получаемые врезультате ФА факторы могут быть использованы для интерпретации наблюдаемыхданных;
· Главныекомпоненты некоррелированны (что эквивалентно их ортогональности при переносеначала координат в центр масс исходного набора), факторы же — не обязательно;
· МГК можнорассматривать как частный случай ФА, когда все специфические факторы принятыравными нулю, а общие факторы ортогональны./> Метод главных компонент(PCA)
Метод главных компонент применяется для снижения размерности пространстванаблюдаемых векторов, не приводя к существенной потере информативности. Пустьдан исходный набор векторов линейного пространства Rn. Применениеметода главных компонент позволяет перейти к базису пространства Rn,такому что:
Первая компонента (первый вектор базиса) соответствует направлению, вдоль которогодисперсия векторов исходного набора максимальна. Направление второй компоненты(второго вектора базиса) выбрано таким образом, чтобы дисперсия исходных вектороввдоль него была максимальной при условии ортогональности первому вектору базиса.Аналогично определяются остальные векторы базиса.
В результате, направления векторов базиса выбраны так, чтобымаксимизировать дисперсию исходного набора вдоль первых компонент, называемыхглавными компонентами (или главными осями). Получается, что основнаяизменчивость векторов исходного набора векторов представлена несколькимипервыми компонентами, и появляется возможность, отбросив оставшиеся (менеесущественные) компоненты, перейти к пространству меньшей размерности.
Результатом применения МГК является вычисление матрицы W размераm x n, осуществляющей проекцию векторов пространства Rn на подпространство,натянутое на главные компоненты:
y = Wt(x — μ), y /> Rm, x /> Rn.
Где x — вектор из исходного набора, y — координаты вектора вподпространстве главных компонент, μ — средний вектор начального набора.
Главные компоненты (векторы базиса), выбираемые с помощьюМГК, обладают следующим свойством: обратная проекция вектора y в Rnдает минимальную ошибку реконструкции (минимальное расстояние до образа вектораy). Нужно отметить, что корректное применение МГК возможно лишь припредположении о нормальном распределении векторов исходного набора.
В приложении к задаче классификации с учителем МГК обычно применяетсяследующим образом. После вычисления главных осей тренировочного набора, векторпризнаков тестового объекта проецируется на подпространство, образованное главнымиосями. Вычисляются две характеристики: расстояние от проекции тестового векторадо среднего вектора тренировочного набора — Distance in Feature Space (DIFS), ирасстояние от тестового вектора до его проекции в подпространство главныхкомпонент — Distance From Feature Space (DFFS). Исходя из этих характеристиквыносится решение о принадлежности тестового объекта классу, образованномутренировочным набором.
Отличие Факторного Анализа (Factor Analysis, FA) от МетодаГлавных Компонент (Principal Components Analysis, PCA)
· Результатом ФАявляется модель, в явном виде описывающая зависимость наблюдаемых переменных отскрытых факторов (МГК это описательный анализ данных, без получения модели);
· ФАпредусматривает ошибку моделирования (специфический фактор) для каждой изнаблюдаемых переменных, в то время как МГК пытается объяснить всю изменчивость,включая шум, зависимостью от главных компонент;
· В МГК главныекомпоненты являются линейными комбинациями наблюдаемых переменных. В ФАнаблюдаемые переменные являются линейными комбинациями общих и специфическихфакторов;
· Получаемые врезультате ФА факторы могут быть использованы для интерпретации наблюдаемыхданных;
· Главныекомпоненты некоррелированы (что эквивалентно их ортогональности при переносеначала координат в центр масс исходного набора), факторы же — не обязательно;
· МГК можнорассматривать как частный случай ФА, когда все специфические факторы принятыравными нулю, а общие факторы ортогональны. /> Анализ независимых компонент(ICA). НачалоформыКонец формы
Задачей анализа независимых компонент (Independent ComponentsAnalysis, ICA) является разложение наблюдаемых случайных переменных xjв линейную комбинацию независимых случайных величин sk:
xj=aj1s1+aj2s2+...+ajnsn для всех j.
Основными предположениями, используемыми в данном методе, являютсянезависимость компонент sk и, то, что их распределение отлично отнормального (non-gaussian). Алгоритм вычисления независимых компонент опираетсяна центральную предельную теорему, утверждающую, что при определенных условияхсумма независимо распределенных случайных величин стремится к нормальномураспределению по мере увеличения количества слагаемых. Использую этоутверждение, поиск независимых компонентов, как линейных комбинаций наблюдаемыхпеременных, ведется таким способом, чтобы получить независимые случайныевеличины, распределение которых максимально далеко от нормального. Степеньблизости распределения случайной величины к нормальному измеряется различнымспособами [Hyvarinen2000].
По своей формулировке, ICA близок к методу главных компонент(PCA) и факторному анализу (FA), однако имеет ряд существенных различий:
· В ICA существенноиспользуется предположение о том, что распределения независимых компонентотличны от нормального,
что дает возможность интерпретировать ICA как FA длянеортогональных факторов, с распределением отличным от нормального;
· В ICA понижениеразмерности не является целью, в отличии от FA и PCA;
· PCA добиваетсятого, чтобы проекции векторов исходного набора на оси главных компонент былинекоррелированы, в то время как ICA добивается их независимости (более сильноеусловие);
· Оси PCAортогональны, в то время как оси независимых компонент — необязательно; /> ЛинейныйДискриминантныйАнализ(Linear Discriminant Analysis, LDA)Линейный Дискриминантный Анализ, вотличие от МГК и ФА не ставит своей целью найти подпространство меньшейразмерности, наилучшим образом описывающее набор тренировочных изображений. Егозадача — найти проекцию в пространство, в котором разница между различным классамиобъектов максимальна. Это требование формулируется как получение максимальнокомпактных кластеров, соответствующих различным классам, удаленных намаксимально возможное расстояние. С помощью ЛДА удается получитьподпространство небольшой размерности, в котором кластеры изображенийпересекаются минимально. Производить классификацию в таком пространстве значительнопроще. />2.3. Деформируемые модели
Начало формы
Конец формы
В машинном зрении деформируемые модели являются мощным инструментоманализа и обработки данных. Деформируемые модели, в отличии от жестких (rigid),обладают большой гибкостью (имеют возможность представлять объекты с сильноразличающейся формой) и в то же время дают возможность указать достаточнострогие ограничения на нежелательные изменения формы представляемых объектов.
В качестве примеров использования деформируемых моделей можнопривести:
· выделение(локализация) объектов и структур определенного вида на 2D и 3D изображениях(черт человеческого лица, объектов на медицинских изображениях)
· отслеживанияперемещения объектов между кадрами видеопотока.
· сегментация 2D и3D изображений
· гладкаяаппроксимации разреженного облака точек
· реконструкции 3Dформы объекта по 2D изображениям — с помощью стерео, восстановления формы позакраске (shape from shading)
Использование деформируемых моделей при решение задачи обработкии распознавания изображений обычно позволяет в элегантной математической формеописать одновременное воздействие многих (возможно, противоречивых) факторов напроцесс получения оптимального решения.
Конкретная деформируемая модель характеризуется:
· Способом заданияформы модели (аналитические кривые и поверхности, конечные элементы);
· Способомизмерения критерия согласия (goodness of fit) модели и измеренных данных; Способом модификации формы модели(по каким именно правилам (формулам) происходит изменение формы модели);/>/>2.4. Скрытые Марковские Модели (Hidden Markov Models,HMM)Скрытые Марковские Модели (СММ)являются одним из способов получения математической модели (описания свойств)некоторого наблюдаемого сигнала. СММ относятся к классу стохастических моделей.Стохастические модели пытаются охарактеризовать только статистические свойствасигнала, не обладая информацией о его специфических свойствах. В основустохастических моделей положено допущение о том, что сигнал может быть описаннекоторым параметрическим случайным процессом и что параметры этого процессамогут быть достаточно точно оценены некоторым, вполне определенным способом.Настроенную СММ можно рассматривать как источник некоторого случайного сигналасо вполне определенными характеристиками. Для настроенной СММ есть возможностьподсчитать вероятность генерации тестового сигнала данной моделью. В приложениик задаче распознавания, представив вектор признаков объекта в виде сигнала(набора последовательных наблюдений), можно смоделировать класс объектов с помощьюСММ. Вероятность принадлежности тестового объекта классу, заданному СММоценивается как вероятностью генерации сигнала, соответствующего его векторупризнаков. Настройка (обучение) СММ — состоит в модификации ее параметров длятого, чтобы добиться максимальной вероятности генерации сигналов, соответствующихвекторам тренировочного набора. />/>2.5. Метод Опорных Векторов (Support Vector Machines, SVM)
Цель тренировки большинства классификаторов — минимизироватьошибку классификации на тренировочном наборе (называемую эмпирическим риском).В отличие от них, с помощью метода опорных векторов можно построитьклассификатор минимизирующий верхнюю оценку ожидаемой ошибки классификации (втом числе и для неизвестных объектов, не входивших в тренировочный набор).Применение метода опорных векторов к задаче распознавания заключается в поискегиперплоскости в признаковом пространстве, отделяющей классы. Классификация спомощью опорных векторов позволяет использовать аппарат ядерных функций длянеявного проецирования векторов-признаков в пространство потенциально намногоболее высокой размерности (еще выше, чем пространство изображений), в которомклассы могут оказаться линейно разделимы. Неявное проецирование с помощьюядерных функций не приводит к усложнению вычислений, что позволяет успешноиспользовать линейный классификатор для линейно неразделимых классов. />
3. Реализация программногообеспечения
В ходе работы над бакалаврской работой была написанапрограмма, Выделяющая на изображении искомые объекты и нормирующая их.
Программа представляет собой простое SDI-приложение, написанное в среде Builder C++ v.6.0. Для реализации обработки изображения использовалась библиотека Intel® OpenSource Computer Vision Library (OpenCV).
В программе были использованы следующие функции библиотеки OpenCV:
Функция Описание функции cvLoadImage Загружает изображение из файла cvSize Возвращает размер изображения cvCreateImage Создает новое изображение cvAbsDiff Производит вычитание по модулю двух изображений cvCmpS Бинаризирует изображении, используя порог cvErode Выполняет побитовую операцию эрозии изображения cvCamShift Реализует алгоритм сравнения двух изображений cvGetQuadrangleSubPix Производит аффинное преобразование изображения cvSetZero Заполняет изображение черным цветом cvFillConvexPoly Заполняет многоугольник на изображении заданным цветом cvCopy Копирует изображение
Также были использованы следующие классы:Класс Описание класса IplImage Изображение CvSize Размер матрицы CvPoint Точка CvRect Прямоугольник CvBox2D Прямоугольник CvMat Матрица
Алгоритм программы:
Начало → Загружаемизображение-эталон → Отображаем эталон на экране → Ждем щелчка мыши→ Загружаем исследуемое изображение → Отображаем эталон на экране →Ждем щелчка мыши → Выполняем вычитание двух изображений → Бинаризируемрезультат → Отображаем результат на экране → Ждем щелчка мыши →Выполняем эрозию результата → Отображаем результат на экране → Ждемщелчка мыши → Находим минимальный прямоугольник, охватывающий найденныеобъекты → Поворачиваем исследуемое изображение → Отображаемрезультат на экране → Ждем щелчка мыши → Нормализуем результат →Отображаем результат на экране → дем щелчка мыши → Конец
Заключение
В работе создана программа обработки изображений. Вдальнейшем планируется разработка программного обеспечения для классификации полученныхобразов.