МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет Кафедра «Системы автоматизированного проектирования» РАСПОЗНАВАНИЕ ОБЪЕКТОВ С ИСПОЛЬЗОВАНИЕМ ЭТАЛОНОВ Методические указания к лабораторной работе Минск БНТУ 2013 1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет Кафедра «Системы автоматизированного проектирования» РАСПОЗНАВАНИЕ ОБЪЕКТОВ С ИСПОЛЬЗОВАНИЕМ ЭТАЛОНОВ Методические указания к лабораторной работе для студентов специальности 1-40 01 02 «Информационные системы и технологии» Минск БНТУ 2013 2 УДК 004.932.2(076.5)(0175.8) ББК 32.97я7 Р24 Составители: И. Л. Ковалева, Т. А. Мархель, Л. В. Федосова Рецензенты: Н. Н. Гурский, Т. А. Долгова Методические указания рассматривают один из разделов теории обработки и распознава- ния изображений – построение систем распознавания с «учителем». В теоретической части вводятся основные понятия и особенности построения систем. Основное внимание уделено распознаванию объектов с использованием эталонов. Изучение теоретического материала, изложенного в указаниях, и выполнение лабораторной работы дает студентам возможность понять правила построения систем распознавания объектов с «учителем» с использованием эталонов и позволяет проанализировать особенности методов в ходе самостоятельного выполнения ими обработки предложенных изображений. © Белорусский национальный технический университет, 2013 3 Цель работы: разработать систему распознавания с «учителем», использующую для построения решающего правила информацию об эталонах обучающей выборки. 1. Основные понятия и определения В зависимости от количества первоначальной априорной инфор- мации о распознаваемых объектах или явлениях системы распозна- вания могут быть разделены на системы без обучения, обучаемые (или системы «с учителем») и самообучающиеся. В обучаемых системах количество первоначальной априорной информации достаточно для того, чтобы в соответствии с избранным классификационным признаком разделить все множество объектов на классы и определить словарь признаков. Однако количества пер- воначальной априорной информации недостаточно для описания классов на языке признаков. Исходная информация, необходимая для построения обучаемых систем распознавания, позволяет различать принадлежность конкретных объектов соответствующим классам и организовывать процедуру обучения. Ее цель: определить разделя- ющие функции путем многократного предъявления системе распо- знавания различных объектов с указанием классов, к которым они принадлежат. Все эти объекты образуют так называемую обучаю- щую выборку. Обучающая выборка – это множество объектов, за- данных значениями признаков, принадлежность которых к тому или иному классу достоверно известна и сообщается «учителем» обучаемой системе. По обучающей выборке система строит реша- ющие правила. Качество решающих правил оценивается по контрольной (экза- менационной) выборке, в которую входят объекты, заданные значе- ниями признаков, принадлежность которых к тому или иному клас- су известна только «учителю». Предъявляя обучаемой системе для контрольного распознавания объекты экзаменационной выборки, «учитель» в состоянии дать оценку вероятностей ошибок распозна- вания, то есть оценить качество обучения. К обучающей и кон- трольной выборке предъявляются определенные требования. Например, важно, чтобы объекты экзаменационной выборки не входили в обучающую выборку (иногда это требование нарушается, если общий объем выборок мал и увеличить его либо невозможно, 4 либо чрезвычайно сложно). Обучающая и экзаменационная выборка должны достаточно полно представлять генеральную совокупность (гипотетическое множество всех возможных объектов каждого об- раза). Например, при обучении системы медицинской диагностики в обучающей и контрольной выборке должны быть представлены пациенты различных половозрастных групп, с различными анато- мическими и физиологическими особенностями, сопутствующими заболеваниями и т. д. При социологических исследованиях это называют репрезентативностью выборки. Построение решающих правил – это наиболее богатая в отноше- нии разработанных подходов и методов решения компонента задач распознавания. Основная цель, которая при этом преследуется, – минимизация риска потерь. Это является критерием, по которому формируется наиболее информативное признаковое пространство и наиболее эффективные решающие правила. Алфавит, признаки и решающие правила должны быть такими, чтобы, по возможности, минимизировать риск потерь. Этот критерий (характеристика рас- познающей системы) является составным. Он включает в себя по- тери (штрафы) за ошибки распознавания и затраты на измерения признаков распознаваемых объектов. Одним из подходов, применяемых при построении решающих правил, является использование для этих целей не всей совокупно- сти объектов обучающей выборки, а сформированных на ее основе эталонов классов. По существу, эталон – это усредненный по обу- чающей выборке абстрактный объект. Абстрактным его называют потому, что он может не совпадать не только ни с одним объектом обучающей выборки, но и ни с одним объектом генеральной сово- купности. В системах распознавания, использующих решающие правила на основании эталонов, в памяти машины после этапа обу- чения хранится лишь информация об эталонах, а при распознавании не требуется перебор всех объектов обучающей выборки. Примера- ми таких систем распознавания могут служить системы, реализую- щие метод построения эталонов (с решающим правилом «минимум расстояния до эталона класса») и метод дробящихся эталонов (с решающим правилом типа «метод дробящихся эталонов»). 5 2. Метод построения эталонов На этапе обучения машине последовательно предъявляются все объекты обучающей выборки с указанием того, к какому классу они относятся. Затем для каждого класса по обучающей выборке стро- ится эталон, имеющий значения признаков  0 0 0 01 2, , ..., ,Nx x x x где 0 1 1 ; K i ik k x x K    K – количество объектов данного образа в обучающей выборке; i – номер признака. Распознавание осуществляется следующим образом. На вход си- стемы поступает объект ,x принадлежность которого к тому или иному классу системы неизвестна. От этого объекта измеряются расстояния до эталонов всех образов, и x система относит к тому классу, расстояние до эталона которого минимально (рис. 1). Рис. 1. Решающее правило «минимум расстояния до эталона класса»: – эталон первого класса; – эталон второго класса Расстояние измеряется в той метрике, которая введена для реше- ния определенной задачи распознавания.                  6 3. Метод дробящихся эталонов На первом этапе в обучающей выборке «охватывают» все объек- ты каждого класса гиперсферой по возможности меньшего радиуса. Сделать это можно следующим образом. Строится эталон каждого класса. Вычисляется расстояние от эталона до всех объектов данно- го класса, входящих в обучающую выборку. Выбирается макси- мальное из этих расстояний max .r Строится гиперсфера с центром в эталоне и радиусом max εR r  . Она охватывает все объекты дан- ного класса. Такая процедура проводится для всех классов. На рис. 2 представлен пример двух классов в двумерном признаковом пространстве. Рис. 2. Решающее правило типа «метод дробящих эталонов»: – эталон первого класса; – эталон второго класса Если гиперсферы различных классов пересекаются и в области перекрытия оказываются объекты более чем одного класса, то для них строятся гиперсферы второго уровня, затем третьего и т. д. до тех пор, пока области не окажутся непересекающимися либо в об- ласти пересечения будут присутствовать объекты только одного класса. Распознавание осуществляется следующим образом. Определя- ется местонахождение объекта относительно гиперсфер первого уровня. При попадании объекта в гиперсферу, соответствующую  7 одному и только одному классу, процедура распознавания прекра- щается. Если же объект оказался в области перекрытия гиперсфер, которая при обучении содержала объекты более чем одного класса, то переходим к гиперсферам второго уровня и проводим действия такие же, как и для гиперсфер первого уровня. Этот процесс про- должается до тех пор, пока принадлежность неизвестного объекта к тому или иному классу не определится однозначно. Правда, это со- бытие может и не наступить. Неизвестный объект может не попасть ни в одну из гиперсфер какого-либо уровня. В этих случаях «учи- тель» должен в решающие правила включить соответствующие действия. Например, система может либо отказаться от решения об однозначном отнесении объекта к какому-либо классу, либо ис- пользовать критерий минимума расстояния до эталонов данного или предшествующего уровня и т. п. Какой из этих приемов эффек- тивнее, сказать трудно, так как метод дробящихся эталонов носит в основном эмпирический характер. 4. Основные этапы и требования к выполняемой работе В ходе выполнения лабораторной работы необходимо разработать систему распознавания, реализующую метод дробящихся эталонов (назовем решающее правило в этом методе решающим правилом ти- па «метод дробящихся эталонов»). Разрабатываемая подсистема яв- ляется подсистемой распознавания «с учителем», поэтому она долж- на состоять из двух частей: обучения и распознавания. А. Обучение Пользователю должна быть предоставлена возможность класси- фикации «учебного материала», в ходе которой он последовательно вводит в машину изображения обучающей выборки и информацию о том, к какому классу эти изображения относятся. Для этого долж- но быть разработано интуитивно понятное окно приложения. При- мер приведен на рис. 3. 8 Рис. 3. Окно метода дробящихся эталонов Рассмотрим основные элементы окна (см. рис. 3): 1 – начальные условия; 2 – кнопка очистки таблицы (не удаляет загруженные изображения); 3 – таблица данных (показана ниже); 4 – кнопка вызова на экран окна просмотра загруженных изоб- ражений; 5 – элементы управления для добавления нового объекта в обу- чающую выборку; 6 – кнопка запуска обучения. Пусть количество классов для распознавания равно четырем и в обучающей выборке в каждом классе предусмотрено по четыре объекта. В качестве объектов для распознавания используются зри- тельные образы – изображения цифр. При этом изображения могут быть цветными и полутоновыми (рис. 4). Рис. 4. Изображения обучающей выборки 9 Если изображения цветные, то необходимо предусмотреть пере- вод этих изображений в полутоновые. Ввод изображений осуществ- ляется с помощью элемента 5 и сопровождается параллельным за- полнением таблицы данных (рис. 5). Рис. 5. Вид таблицы данных после ввода изображений обучающей выборки (обучение еще не начато) Смысл столбцов таблицы: Объект № – номер объекта в порядке добавления; Эталон? – флаг, указывающий на то, является ли данный объект эталоном какого-либо класса; Класс – класс, к которому принадлежит данный объект; R -> A, R -> B, R -> C, R -> D – расстояние от данного объекта до эталона каждого из классов; Возможные классы – принадлежность данного объекта к классу (-ам) на основании попадания в гиперсферу (-ы); Имя файла – имя файла загруженного изображения. При выборе в таблице одного из объектов справа в окне «метод дробящихся эталонов» появляются его изображение и матрица. 10 Для запуска обучения надо нажать кнопку «Построить гипер- сферы». В этом случае будут построены гиперсферы первого уров- ня. Таблица данных изменится и будет выглядеть как на рис. 6. Рис. 6. Таблица данных после построения гиперсфер первого уровня Как видно из рис. 6, в таблице данных появились четыре эталона (по одному для каждого класса – объекты № 17, 18, 19 и 20). Так, объект № 17 является эталоном (значение «True» в столбце «Эталон?») класса 1 (значение «Класс 1» в столбце «Класс»). Рас- стояние от него до эталона первого класса равно нулю (значение «0» в столбце «R ->A»), что естественно, а расстояния до эталонов других классов не подсчитывались – они нас не интересуют. Анало- гично заполняются строки для трех других эталонов. В таблице данных появилась еще одна новая строка – строка № 0, где в столбце «Класс» записано значение «Rmax». Эта строка содержит радиусы гиперсфер. Видно, что значение «702» в столбце «R ->A» является максимальным из расстояний от эталона класса 1 до объектов класса 1. Так же дело обстоит и с тремя оставшимися радиусами. 11 Заполнились так же поля столбца «Возможные классы». Если для данного объекта значение в столбце «R ->A» меньше, чем зна- чение радиуса гиперсферы соответствующего класса (на пересече- нии строки «Rmax» и столбца «R ->A»), то объект попадает в этот класс. Только один объект (№ 5) попал на пересечение гиперсфер вто- рого и третьего классов и поэтому был отнесен к ним обоим. Из-за него потребуется построение гиперсфер второго уровня. Снова нажмем кнопку «Построить гиперсферы» для построения гиперсфер второго уровня (рис. 7). Рис. 7. Таблица данных после построения гиперсфер второго уровня Согласно алгоритму, все объекты, однозначно отнесенные к ка- кому-либо классу на первом шаге, были исключены из рассмотре- ния. Остался только один объект (№ 5). Для него была построена гиперсфера, причем так как объект один, то он и стал центром ги- персферы, а ее радиус оказался равен нулю. На этом обучение закончилось. Перейдем к распознаванию. Б. Распознавание Для распознавания нового изображения необходимо обеспечить возможность его загрузки и определения его положения относи- тельно гиперсфер, созданных на этапе обучения. Для этого нажмем кнопку «Построить гиперсферы» еще раз, а затем – кнопку «Перейти к распознаванию». Откроется окно распо- знавания, показанное на рис. 8. 12 Рис. 8. Окно распознавания На рис. 8 цифрами обозначены: 1 – таблица, в которую будут заноситься шаги распознавания; 2 – кнопка для загрузки изображения; 3 – кнопка для сброса распознавания. Нажмем кнопку «Загрузить картинку» и выберем изображение для распознавания. Окно примет вид, показанный на рис. 9. 13 Рис. 9. Загрузка изображения для распознавания Загружается полутоновое изображение цифры «4». Матрица ин- тенсивностей изображения приведена слева внизу. Нажмем кнопку «Сделать шаг». Будут проверены гиперсферы первого уровня. Поскольку принадлежность введенного изображе- ния к четвертому классу распознается на первом же шаге, увидим диалоговое окно, сообщающее о завершении распознавания, а в таблицу будут занесены соответствующие данные (рис. 10). 14 Рис. 10. Распознавание завершилось на первом же шаге Из рисунка видно, что были вычислены расстояния от изображе- ния до центров гиперсфер всех четырех классов. Только расстояние до центра гиперсферы четвертого класса оказалось меньше, чем ее радиус, поэтому программа однозначно отнесла этот объект к чет- вертому классу. Что будет, если понадобится вовлечь в распознавание гиперсферы (точнее, гиперсферу, потому что она у нас одна) второго уровня? Для этого загрузим новое изображение для распознавания – цифру «2». На рис. 11 показан результат распознавания нового изображения. 15 Рис. 11. Использование гиперсфер второго уровня Как видно из рисунка, на первом шаге (на этапе построения ги- персфер первого уровня) изображение оказалось на пересечении гиперсфер первого уровня для второго и третьего классов. Поэтому был сделан второй шаг – строились гиперсферы второго уровня. На нем оказалось, что изображение не попало в единственную ги- персферу второго уровня, поэтому вывод о принадлежности распо- знаваемого изображения надо было сделать на основании дополни- тельного решающего правила. В качестве такого правила использо- вано решающее правило «минимум расстояния до эталона класса». Было выполнено сравнение расстояний от распознаваемого изображе- ния до центров (эталонов) всех гиперсфер второго уровня. Ближе всего распознаваемое изображение оказалось к центру (эталону) гиперсферы второго класса, поэтому оно было отнесено ко второму классу. 16 Литература 1. Аркадьев, А. Г. Обучение машины классификации объектов / А. Г. Аркадьев, Э. С. Браверман. – М. : Наука, 1981. – 464 с. 2. Горелик, А. Л. Методы распознавания : учебное пособие для вузов / А. Л. Горелик, В. А. Скрипкин. – 3-е изд., перераб. и доп. – М. : Высш. шк., 1989. – 234 с. 3. Гренандер, У. Лекции по теории образов: в 3 т. / У. Гренандер; под ред. Ю. И. Журавлева. – М. : Мир, 1979–1983. 4. Дуда, Р. Распознавание образов и анализ сцен / Р. Дуда, П. Харт. – М. : Мир, 1976. – 213 с. Учебное издание РАСПОЗНАВАНИЕ ОБЪЕКТОВ С ИСПОЛЬЗОВАНИЕМ ЭТАЛОНОВ Методические указания к лабораторной работе для студентов специальности 1-40 01 02 «Информационные системы и технологии» Составители : КОВАЛЕВА Ирина Львовна МАРХЕЛЬ Тимофей Александрович ФЕДОСОВА Людмила Владимировна Редактор Т. В. Грищенкова Компьютерная верстка А. Г. Занкевич Подписано в печать 22.02.2013. Формат 6084 1/16. Бумага офсетная. Ризография. Усл. печ. л. 0,99. Уч.-изд. л. 0,77. Тираж 100. Заказ 1201. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0494349 от 16.03.2009. Пр. Независимости, 65. 220013, г. Минск.