[МРО] Методичка МРО
.pdfМинистерство образования Республики Беларусь БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра «Системы автоматизированного проектирования»
|
|
|
|
|
|
|
|
|
|
|
У |
|
|
|
|
|
|
|
|
|
|
Т |
|
|
|
|
|
|
|
|
|
|
Н |
|
|
|
|
|
|
|
|
|
|
Б |
|
|
|
|
|
|
МЕТОДЫ РАСПОЗНАВАНИЯ О РАЗОВ |
|
|
||||||
|
|
|
|
|
для студентов спецмальнойальности |
|
|
|
|||
|
|
|
|
|
Лабораторные работы |
|
|
|
|||
|
|
|
|
|
|
по дисциплине |
|
|
|
|
|
|
|
|
|
|
|
( нап авлениям)» |
|
|
|
|
|
|
|
«Алгоритмы распознавания образов: алгоритм секущих |
|||||||||
|
|
плоскостей и алгоритм опт |
классификации» |
|
|||||||
|
|
|
|
|
|
|
р |
|
|
|
|
|
|
1–40 01 02 «Инфо мац онные с стемы и технологии |
|
||||||||
|
|
|
|
|
|
по |
|
|
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
специализации 1–40 01 02-01 «Информационные системы |
||||||||||
|
|
и технологии в пр ектировании и производстве» |
|
||||||||
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
з |
|
|
|
|
|
|
|
|
|
|
о |
|
|
|
|
|
|
|
|
|
|
п |
|
|
|
|
|
|
|
|
|
|
е |
|
|
|
|
|
|
|
|
|
|
|
Р |
|
|
|
|
|
М и н с к 2 0 0 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
УДК 681.327 |
|
|
|
|
|
|
|
|
|||
|
|
Рассматриваются элементарные алгоритмы распознавания |
||||||||||
|
образов: алгоритм секущих плоскостей и алгоритм оптималь- |
|||||||||||
|
ной классификации, используемые для создания обучаемых и |
|||||||||||
|
самообучающихся систем распознавания. |
|
|
|
||||||||
|
|
Изложена краткая теория, взятая в основу при разработке |
||||||||||
|
алгоритмов, и результаты, полученные при исследовании ра- |
|||||||||||
|
боты алгоритмов с различным числом объектов в образах. |
|||||||||||
|
Теоретические выкладки позволяют студентам самостоятель- |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
У |
|
но разработать программное обеспечение и осуществить его |
|||||||||||
|
тестирование на реальных предлагаемых задачах. |
Т |
||||||||||
|
|
|
|
|
|
|
Составитель |
Н |
|
|||
|
|
|
|
|
|
И.Л. Ковалева |
|
|||||
|
|
|
|
|
|
Б |
|
|
||||
|
|
|
|
|
|
|
Рецензенты: |
|
|
|||
|
|
|
|
С.В. Абламейко, В.Б. Ковалевский |
|
|
||||||
|
|
|
|
|
|
|
|
|
й |
|
|
|
|
|
|
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
|
р |
|
|
|
|
|
|
|
|
|
|
|
о |
|
|
|
|
|
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
|
|
и |
|
|
|
|
|
|
|
|
|
|
|
з |
|
|
|
|
|
|
|
|
|
|
|
о |
|
|
|
|
|
|
|
|
|
|
|
п |
|
|
|
|
|
|
|
|
|
|
|
е |
|
|
|
|
|
|
|
|
© Ковалева И.Л., |
|||
|
|
|
|
|
|
|
|
составление, 2004 |
||||
Р |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Лабораторная работа № 1
АЛГОРИТМ СЕКУЩИХ ПЛОСКОСТЕЙ
|
|
Цель: изучение алгоритма секущих плоскостей, разработ- |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
У |
|
ка на его основе обучающейся системы распознавания изо- |
|||||||||||
|
бражений. |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
Краткие теоретические сведения |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
Н |
|
|
|
Алгоритм обучения машины «узнаванию» образов, осно- |
||||||||||
|
ванный на методе секущих гиперплоскостей, заключаетсяТв |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
Б |
|
|
аппроксимации разделяющей гиперповерхности «кусками» |
|||||||||||
|
гиперплоскостей и состоит из следующих частей: |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
й |
|
|
|
|
А. Обучение (формирование разделяющей поверхности): |
||||||||||
|
(1) проведение секущих плоскостей; (2) исключение лишних |
|||||||||||
|
плоскостей; (3) исключение |
лишних |
|
|
||||||||
|
|
|
кусков плоскостей. |
|
||||||||
|
|
Б. Распознавание новых объектов. |
|
|
||||||||
|
|
|
|
|
|
|
стр |
|
|
|
||
|
|
|
|
Геометрическая |
ллюст ац я алгоритма |
|
||||||
|
|
|
|
|
т |
|
ение алгоритма на условных гео- |
|||||
|
|
Вначале проследим п |
|
|||||||||
|
метрических |
|
рациях. |
Предположим, что нам предстоит |
||||||||
|
|
|
|
иллюс |
|
|
|
|
|
|
||
|
обучить маш ну распознаваниюо |
трех образов, которые мы ус- |
||||||||||
|
|
|
называ |
ь образами А, В и С. В пространстве рецепто- |
||||||||
|
ловимся |
|
|
|||||||||
|
ров этим обра ам соответствуют три неизвестных, но объектив- |
|||||||||||
|
|
о |
|
|
|
|
|
|
|
|
||
|
но существующих компактных множества точек. На рис. 1.1 эти |
|||||||||||
|
мн жества и |
бражены в виде трехобластей А, В и С. |
|
|||||||||
|
п |
|
|
|
|
|
|
|
|
|
|
|
е |
|
|
|
|
|
|
|
|
|
|
|
|
Р |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
A
B
|
|
|
|
|
|
|
|
|
|
У |
|
|
|
|
|
|
|
|
|
Т |
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Появление шестой точки приводит к противоречию, причем у точки 6 оказывается сразу два оппонента – точки 4 и 5. Вначале проводится плоскость III, разделяющая точки 6 и 4, затем плоскость IV, разделяющая точки 6 и 5 (рис. 1.6).
|
|
|
|
|
|
|
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 |
Противоречие ликвидируется плоскостью VI (рис. 1.10). Появление десятой точки, вступающей в противоречие с точкой 8, приводит к появлению плоскости VII (рис. 1.11).
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|