Реферат: Методические указания к лабораторной работе

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

"ХАРЬКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ"


МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к лабораторной работе

"Распознавание изображений по углу между векторами, скалярному произведению и по принадлежности к заданной области пространства"

для студентов специальностей 7.091501, 7.091502, 7.091503

дневной и заочной форм обучения


Харьков НТУ "ХПИ" 2002


1. Цель лабораторных занятий

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


^ 2. Краткие сведения из теории

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

Мера сходства изображений в n-мерном векторном пространстве вводится как функцию двух переменных L(Sk, Si), где Sk, Si S; S = {S1, S2, …, Sn}  конечное множество изображений в рассматриваемом пространстве. При этом функция L(Sk, Si) обладает следующими свойствами:

 свойством симметрии, т.е. L(Sk, Si) = L(Si, Sk);

 областью значений функции является множество неотрицательных чисел, т.е. L(Sk, Si)  0, k, i = 1, 2, …, n;

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








 в случае компактных образов функция L(Sk, Si) является монотонной функцией удаления точек Skи Si друг от друга в n-мерном пространстве.

В n-мерном пространстве мера сходства изображений может быть введена многими способами. Рассмотрим несколько из них. При этом во всех случаях будем полагать, что эталонные изображения X1, X2, …, Xmm различных классов изображений или образов в n-мерном пространстве задаются в виде векторов с проекциями на оси координат: X1 = (x11, x12, …, x1n), X2 = (x21, x22, …, x2n), …, Xm = (xm1, xm2, …, xmn). Любое входное изображение Si S также представляется в виде вектора Si = (si1, si2, …, sin) в этом пространстве.


^ 2.1. Распознавание по углу между векторами

Мера близости между двумя векторами в n-мерном векторном пространстве может быть задана в виде угла. Если задано входное изображение Si = (si1, si2, …, sin) и векторы эталонных изображений X1 = (x11, x12, …, x1n), X2 = (x21, x22, …, x2n), …, Xm = (xm1, xm2, …, xmn), то мера сходства между входным и эталонными изображениями определяется выражением


(1)

где  соответственно длины векторов

Принадлежность входного изображения Si к одному из m образов определяется с помощью решающего правила


(2)


При этом в решающем правиле и далее по тексту для обозначения j-го образа и эталонного изображения j-го образа применяется одно и тоже обозначение .


^ 2.2. Распознавание изображений по скалярному произведению

Мера близости изображений по углу между векторами (1) основана на скалярном произведении векторов:


(3)


Некоторые системы распознавания используют непосредственно скалярное произведение в качестве меры сходства изображений в n-мерном векторном пространстве:

(4)


В этом случае принадлежность входного изображения Si к какому-либо образу определяется с помощью решающего правила


(5)


^ 2.3. Распознавание изображений по принадлежности к заданной области пространства


При этом способе распознавания все пространство изображений V разбивается на непересекающиеся области V1, V2, …, Vm, Vm+1, где V1, V2, …, Vm  области, содержащие изображения только одного соответствующего образа X1, X2, …, Xm; Vm+1  область, не содержащая изображений, относящихся к указанным образам. В этом случае принадлежность входного изображения Si = (si1, si2, …, sin) к некоторому j-му образу определяется решающим правилом


(6)


Если области заданы в евклидовом пространстве в виде шаров с центрами в точках и радиусами Rj, то решающее правило (6) принимает вид


(7)


Для конструирования областей в пространстве изображений могут использоваться любые меры сходства, например, расстояния с весовыми коэффициентами (8)  (10), расстояние по Камберра (11) и т.д.


(8)


(9)


(10)


(11)


 весовые коэффициенты;   целое положительное число, большее двух.

Решающее правило (6) для расстояний (8)  (10) принимает вид





где Rij  расстояние, заданное одним из выражений (8)  (11), между предъявленным изображением Si и центром шара, содержащего изображения j-го образа; Rj  радиус шара, содержащего изображения j-го образа.

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




где  угол между предъявленным изображением Si и эталонным изображением Xj;  предельно допустимый угол для j-го образа между эталонным и распознаваемым изображениями.


^ 3. Индивидуальные задания

3.1. Разработайте алгоритм и программу, моделирующую распознавание различных объектов в n-мерном векторном пространстве по углу между векторами и скалярному произведению.

3.2. Задайтесь размерностью n-мерного векторного пространства, числом m эталонных объектов образов (n и m должны быть не менее 5) и несколькими распознаваемыми объектами. С помощью угла между векторами и скалярного произведения определите принадлежность предъявленных объектов к тому или иному образу.

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

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


4. Содержание отчета

4.1. Тема лабораторных занятий.

4.2. Индивидуальное задание.

4.3. Результаты выполнения пунктов 3.1  3.4 индивидуального задания.