[МРО] Методичка МРО

У

Т

Н

Б

МЕТОДЫ РАСПОЗНАВАНИЯ О РАЗОВ

для студентов спецмальнойальности

Лабораторные работы

по дисциплине

( нап авлениям)»

«Алгоритмы распознавания образов: алгоритм секущих

плоскостей и алгоритм опт

классификации»

р

1–40 01 02 «Инфо мац онные с стемы и технологии

по

т

специализации 1–40 01 02-01 «Информационные системы

и технологии в пр ектировании и производстве»

и

з

о

п

е

Р

М и н с к 2 0 0 4

УДК 681.327

Рассматриваются элементарные алгоритмы распознавания

образов: алгоритм секущих плоскостей и алгоритм оптималь-

ной классификации, используемые для создания обучаемых и

самообучающихся систем распознавания.

Изложена краткая теория, взятая в основу при разработке

алгоритмов, и результаты, полученные при исследовании ра-

боты алгоритмов с различным числом объектов в образах.

Теоретические выкладки позволяют студентам самостоятель-

У

но разработать программное обеспечение и осуществить его

тестирование на реальных предлагаемых задачах.

Т

Составитель

Н

И.Л. Ковалева

Б

Рецензенты:

С.В. Абламейко, В.Б. Ковалевский

й

и

р

о

т

и

з

о

п

е

© Ковалева И.Л.,

составление, 2004

Р

Цель: изучение алгоритма секущих плоскостей, разработ-

У

ка на его основе обучающейся системы распознавания изо-

бражений.

Краткие теоретические сведения

Н

Алгоритм обучения машины «узнаванию» образов, осно-

ванный на методе секущих гиперплоскостей, заключаетсяТв

Б

аппроксимации разделяющей гиперповерхности «кусками»

гиперплоскостей и состоит из следующих частей:

й

А. Обучение (формирование разделяющей поверхности):

(1) проведение секущих плоскостей; (2) исключение лишних

плоскостей; (3) исключение

лишних

кусков плоскостей.

Б. Распознавание новых объектов.

стр

Геометрическая

ллюст ац я алгоритма

т

ение алгоритма на условных гео-

Вначале проследим п

метрических

рациях.

Предположим, что нам предстоит

иллюс

обучить маш ну распознаваниюо

трех образов, которые мы ус-

называ

ь образами А, В и С. В пространстве рецепто-

ловимся

ров этим обра ам соответствуют три неизвестных, но объектив-

о

но существующих компактных множества точек. На рис. 1.1 эти

мн жества и

бражены в виде трехобластей А, В и С.

п

е

Р

3

У

Т

C

Н

Рис.1.1. Образы А, В и С

Б

й

Проведение секущих плоскостей

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

р

образам. Машина запоминает коо д наты точек в пространстве

рецепторов (точки 1 и 2 на с. 1.2) проводит произвольную

плоскость II, разделяющую этиточки. Пространство рецепторов

может

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

рых на данном э апе алг ритма отождествляется с одним из двух

образов.

и

о

з

оказаться очень неудачным, как это по-

Разбиен

е

казано на р с. 1.2, где большая часть области В лежит, в ре-

о

зультате проведенной нами процедуры, в полупространстве,

отнесенн м к образу А.

п

е

Р

4

I

2

A

B

У

1

Т

Н

C

Б

Рис. 1.2. ПроведениеI секущейплоскости

пространство, отнесенн е к «плоскостисвоему» образу. При этом ма-

После проведения первой

в машину вводится

р

третий объект. Возможны два случаяй:

1) объект относится к об азам А

ли В и попадает в полу-

шина,

носи

т

запомнив к

рдинаты появившегося объекта, готова к

восприятию следующего;

либо

ся к образу С, либо, являясь объек-

2) объект

о

том образов А ли В, попадает не в «свое» полупространство.

з

Тогда в одном полупространстве оказываются точки, отно-

о

сящиеся к ра ным образам. Назовем такой случай противоре-

чием. В нашем случае точка 3, относящаяся к образу А, попа-

п

п лупространство, отнесенное ранее к образу В, и

дает в

всту ает в противоречие с точкой 2 (рис.1.3).

е

Р

5

I

2

3

У

1

Т

Рис.1.3. Пример противоречия

Н

(Точки, с которыми очередной объектБвступает в противо-

речие, будем называть оппонентами). Машина ликвидирует

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

й

(точку 2) и точку 3. Тепе ь маш на относит к образу А облас-

ти DEF и DEG, а к

В – область GEH (рис. 1.4).

и

G

II

р

I

образу 2

H

т

и

3

з

E

о

D 1

п

F

е

Р

Рис. 1.4. Проведение II секущей плоскости

6

После проведения второй плоскости число частей, на которое

разбивается пространство рецепторов, оказывается больше числа

появившихся точек. При проведении последующих плоскостей

число частей пространства возрастает чрезвычайно быстро (при-

близительно как 2n, где п – количество плоскостей), значительно

быстрее, чем число точек. Поэтому проведение новых плоско-

стей, с уточнением границы областей А, В, С, одновременно со-

провождается появлением большого числа «пустых» частей про-

странства, которые не могут быть отнесены к какому-либо обра-

зу (например, область FEH на рис. 1.4). Появление новой точкиУ

теперьможетпривестиктремситуациям:

Т

1) возникает противоречие;

2) противоречие не возникает, так как точка попадает в

«свою» часть пространства;

Н

3) противоречие не возникает, так как точка попадает в «пус-

тую», не поименованную часть пространства. В этом случае ма-

Б

шина запоминает координаты новой точки и относит область, в

которуюпопалаэтаточка, ксоответствующемуобразу.

Именно такая ситуация возн каетйпри появлении точки 4

(рис. 1.5). Не возникает п

во еч я

при появлении точки 5.

и

Машина запоминает к динаты точек 4 и 5, но не проводит

новых плоскостей,

ся всю область FEH к образу С.

р

II

G

I

от

тн

2

H

и

3

з

6

о

E

D

1

п

4

е

F

5

Р

Рис. 1.5. Построение 4, 5 и 6 точек

7

IV

G

II

III

У

I

Т

2

H

3

Н

6

E

Б

D

1

й

F

4

5

Рис.1.6. Проведение III

IV секущ х плоскостей

р

воречие с точкой 6, что

Точка 7 (рис. 1.7) вступает в п от

о

приводит к появлению пл ск стиV (рис. 1.8).

т3

II

III

IV

G

и

2

H

з

о

E

6

п

D

1

е

4

5

7

F

Р

Рис. 1.7. Построение точки 7

8

IV

II

III

I

2

3

У

6

1

Т

4

5

7

V

Рис.1.8. Проведение V секущей плоскости Н

йII

, но затем

Точка 8 попадает в «пустую» часть пространстваБ

и

становится оппонентом точки 9 (р с. 1.9)

IV

р

III

о

I

2

т

и

3

6

з

8

о

1

9

п

4

5

7

V

е

Р

Рис. 1.9. Построение точек 8 и 9

9

IV

II

III

I

У

2

3

Т

6

Н

8

VI

1

9

Б

7

4

5

V

секущей

и

плоскости

Рис. 1.10. Проведен е VI

IV

р

II

III

о

I

т

2

и

3

з

6

о

10

5

8

VI

п

1

9

VI I

е

4

7 V

Р

Рис. 1.11. Проведение VII секущей плоскости

10