автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Библиотека классов для кластеризации и распознавания топологических форм

На правах рукописи

003055Ви (

Бредихин Руслан Николаевич

БИБЛИОТЕКА КЛАССОВ ДЛЯ КЛАСТЕРИЗАЦИИ И РАСПОЗНАВАНИЯ ТОПОЛОГИЧЕСКИХ ФОРМ

Специальность 05.13.11. — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2007

003055807

Работа выполнена на кафедре Математического моделирования Московского энергетического института (технического университета).

Научный руководитель: доктор технических наук, профессор

Фролов Александр Борисович

Официальные оппоненты: доктор технических наук, профессор

Дзегеленок Игорь Игоревич

кандидат физико-математических наук, доцент Строгалов Александр Сергеевич

Ведущая организация: Физический факультет Московского

государственного университета им. М.В. Ломоносова

Защита состоится «20» апреля 2007 г. в 18 ч. 00 м. в ауд. Г-306 на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (техническом университете) по адресу: 111250, г. Москва, ул. Красноказарменная, д. 17.

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (технического университета).

Отзывы в двух экземплярах, заверенные печатью организации, просьба отправлять по адресу: 111250, г. Москва, ул. Красноказарменная, д. 14, Ученый совет МЭИ (ТУ). "

Автореферат разослан «19» марта 2007 г.

Ученый секретарь

диссертационного совета,

кандидат технических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы

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

В области распознавания образов сложился ряд научных школ, различающихся подходами к этой проблеме. Комбинаторно-логический подход характерен для школы C.B. Яблонского и В.Б. Кудрявцева, берущей начало от фундаментальной работы А.И. Чегис и C.B. Яблонского о контроле электрических схем, первой в мировой науке работы по теории построения тестов. Алгебраический подход сформировался в работах Ю.И. Журавлева. Метод физических аналогий в распознавании образов оформился в теории потенциальных функций и морфологическом анализе (М.А. Айзерман, Э.М. Браверман, Л.И. Розо-ноэр, Ю.П. Пытьев). Особое место занимают подходы к распознаванию образов на основе нейронных сетей и параметрический подход на основе статистических свойств ансамбля классифицируемых объектов.

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

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

Данная работа посвящена обоснованию и созданию библиотеки классов для программирования задач кластеризации и распознавания топологических форм.

Топологической формой1 будем называть конфигурацию, которая состоит из определенного числа объектов, обладающих некоторыми свойствами из конечного числа свойств и участвующих в отношениях на множестве объектов. Конфигурации такого типа достаточно широко встречаются во многих областях науки и техники, среди которых теория молекулярных форм в стереохимии, распознавание оптических образов текстов, геоинформатика и др. И во многих случаях в связи с топологическими формами возникают задачи их распознавания и кластеризации. Однако, несмотря на то, что отдельные задачи, связанные с описанными конфигурациями, в частных вариантах решаются вполне успешно, в общем случае единые правила и методы моделирования, кластеризации и распознавания структур, названных в данной работе топологическими формами, прежде не рассматривались.

'Использованное в данной работе понятие топологических форм является обобщением понятия молекулярных форм, описанных П. Мезсем в его работах по молекулярной химии, в частности, Mezey P.G. Shape in Chemistry: An Introduction to Molecular Shape Topology. - New York: John Wiley & Sons. - 1993. - P.531.

Для успешного решения задачи распознавания требуется некоторая функция расстояния на множестве пар объектов, в частности, функция, удовлетворяющая аксиомам метрики. Как правило, такая функция определяется на основе той или иной математической модели объекта, допускающей сравнение объектов и их множеств.

Формирование модели конкретного объекта называют этапом его параметризации — определения набора значений характеризующих объект атрибутов. Например, часто в качестве исходных данных для параметризации используются результаты измерений геометрии объекта. В этом случае модель изображения формируется на основе вектора его размеров в некотором метрическом пространстве.

Однако подход, требующий помещения объекта в метрическое пространство, на практике оказывается не всегда эффективным. В некоторых областях применения систем автоматического распознавания рассматриваемые объекты, имея одинаковую структуру, могут существенно отличаться друг от друга по геометрическим характеристикам. Используемые для распознавания в таких условиях методы (в частности, разработанный на основе теории построения тестов C.B. Яблонского принцип конечной топологии2) существенно отличаются тем, что основным предметом их рассмотрения являются не размеры и геометрические параметры объекта, а его структура и взаимосвязи между его отдельными составляющими.

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

Цель работы

Целью настоящей работы явилось обоснование и создание библиотеки классов для программирования задач кластеризации и распознавания топологических форм. При этом ставились следующие задачи:

1. Проанализировать существующие способы моделирования топологических форм, выявить особенности их описания и обосновать выбор методов моделирования, кластеризации и распознавания.

2. Модернизировать известные методы принципа конечной топологии с целью повышения эффективности процессов кластеризации и распознавания.

3. Создать структуру классов, поддерживающих описания топологических форм на основе принципа конечной топологии.

'JF'rûIov A.B., Jako Е.: Mezey P.G. Logical models of molecular shapes and their families /'/ Mathematical Chemistry. - 30(4). - 2001. - P. 389-409; Frolov A.B.. Jako E., Mezey P.G. Metric properties of factor space of molecular shapes // Mathematical Chemistry. - 30(4). - 2001. - P. 411-428.

4. Снабдить классы объектов необходимыми подпрограммами (методами) для кластеризации и распознавания.

о. Обеспечить высокое быстродействие и эффективное использование оперативной памяти при использовании библиотеки.

Методы исследования

Для проведения исследований были использованы методы теории распознавания образов, топологии, теории построения тестов, теории решеток. При создании программного обеспечения использовались методы объектно-ориентироваиного программирования.

Научная новизна

• Реализованная в библиотеке классов модернизированная модель топологической формы допускает несимметричность и неортогональность отношений на базовых элементах топологической формы.

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

• Обоснован и реализован в библиотеке классов метод построения тестов для топологических форм, имеющих несущественные отличия (обобщенных эталонов).

• Реализованы методы кластеризации и распознавания топологических форм.

Практическая значимость работы

Использование метрики, порождаемой сравнением моделей на тестовых наборах существенно, в несколько раз, ускоряет процедуру кластеризации и распознавания, а также сокращает объем информации об эталонах. Представление совокупности несущественно отличающихся топологических форм в виде множеств логических моделей позволяет использовать обобщенные эталоны, что повышает качество и скорость процедур кластеризации и распознавания. Разработанная библиотека классов использована при создании ОС11-системы. Библиотека может использоваться также для классификации и распознавания молекулярных форм, объектов геоинформатики и в других областях. Результаты диссертации были внедрены в Центральном научно-исследовательском институте машиностроения (ФГУП ЦНИИМаш) для повышения скорости обработки целевой информации при управлении космическими

аппаратами типа "Коронас-Ф" и "Канопус-В" в Российском государственном научно-исследовательском испытательном центре подготовки космонавтов им. Ю.А. Гагарина (РГНИИЦПК им. Ю.А. Гагарина) при создании программного обеспечения функционально-моделирующего стенда подготовки космонавтов, а также использованы при выполнении НИР «Информационные технологии классификации и распознавания на основе принципа конечной топологии» и НИР «Методы реализации вычислений в конечных алгебраических структурах применительно к задачам защиты информации и распознавания образов» в МЭИ (ТУ).

Обоснованность и достоверность результатов

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

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на:

в Шестой, седьмой, восьмой, девятой Московской международной телекоммуникационной конференции студентов и молодых ученых «Молодежь и наука», Москва, 2003, 2004, 2005, 2006;

• Девятой, десятой, одиннадцатой и двенадцатой международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Москва, 2003, 2004, 2005, 2006;

в Тринадцатой международной научно-технической конференции «Информационные средства и технологии», Москва, 2005.

Публикация

Основное содержание диссертации отражено в 13 публикациях. Структура и объем диссертационной работы

Работа состоит из введения, пяти глав, заключения, библиографического списка, включающего 123 наименования, и приложений, содержащих 5 дополнительных рисунков. Основной текст занимает 158 машинописных страниц, в том числе 35 рисунков и 32 таблицы. Общий объем диссертации составляет 177 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы, сформулированы цели и основные задачи исследования, показана научная новизна и практическая значимость результатов, приведены сведения об апробации работы.

В первой главе рассматривается понятие топологических форм и приводятся примеры областей науки и техники, где возникают задачи, связанные с анализом, распознаванием и классификацией подобных конфигураций.

Например, топологические формы достаточно часто встречаются в стереохимии при описании форм молекул с помощью поверхностей уровня (путем указания точек, в которых значение того или иного свойства, величины является постоянным) или на основе модели Ван-дер-Ваальса.

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

Топологические формы также широко распространены в геоинформатике и часто встречаются при работе с географическими информационными системами (ГИС), которые представляют собой современные компьютерные технологии, предназначенные для картографирования и анализа объектов реального мира, различных событий и явлений, как происходящих, так и прогнозируемых.

Кроме того, в главе дается краткий обзор некоторых известных моделей топологических форм, таких как графы, гиперграфы и мографы.

Во второй главе рассматривается принцип конечной топологии — новый3 подход к классификации и распознаванию топологических форм, согласно которому может быть осуществлено моделирование рассматриваемых конфигураций, анализ и поиск тестовых наборов для полученных логических моделей, а также разбиение совокупности этих моделей на классы.

Принцип конечной топологии был разработан A.B. Фроловым совместно с П. Мезеем и Е. Яко на основе изучения многообразия дискретных моделей, используемых для отображения конфигураций, характерных для молекулярных форм4.

Логические модели, конструируемые согласно принципу конечной топологии, позволяют производить исследование, кластеризацию и распознавание для объектов с геометрическими и топологическими свойствами, описывающимися

3См. сноску 2.

4Под молекулярной формой понимается множество обладающих некоторым общим свойством точек области пространства, в которой размещены образующие молекулу атомы. Таким свойством может быть значение той или иной физической характеристики (например, электрического потенциала или заряда). В других случаях это сеойство может определяться некоторой геометрической моделью (например, как поверхность Ван-дер-Ваальса).

системой отношений на базе конечной топологии Т соответствующего топологического пространства (Х,Т). Для этого необходимо выполнить следующие действия:

1. Для построения логической модели нужно задать отвечающее реальному объекту множество X и его конечное разбиение, некоторое подмножество В которого принимается за базу конечной топологии соответствующего объекту топологического пространства (Х,Т).

2. Свойства элементов базы и отношения на них должны быть занумерованы.

3. На основе сформированных данных необходимо построить логические модели реальных объектов в виде целочисленных псевдобулевых функций / : Вп —» Z, областью определения которых служит единичный п-мерный куб Вп, изоморфный булевой подрешетке конечной топологии Т. Эти функции сопоставляют каждому элементу базы идентификатор присущего ему свойства, а совокупностям из mt базовых элементов номер t симметричного отношения, в котором участвуют эти элементы для моделируемого объекта. Остальным вершинам Вп, которые не соответствуют входящим в заданные отношения подмножествам базы, функция / сопоставляет нулевые значения.

4. Для выявления структурных различий между моделями к семейству F логических моделей применяется процедура построения тестов5 и определяется метрика (полуметрика) р : F х F —► R на множестве логических моделей, отражающая число бинарных наборов, на которых различаются модели.

5. На основе полученной метрики может быть построено разбиение множества логических моделей F (и множества реальных объектов) на кластеры.

Упомянутая выше процедура построения тестов заключается в следующем. Пусть m — число логических моделей, составляющих семейство F, и каждая из них представляет собой 2п-мерный вектор вида (z\, z^,..., ¿г»), где Zj G Z, j = 1,2,..., 2", n — количество базовых элементов. Задача построения теста состоит в определении минимального подмножества Q ~ {oi, аг,... ,аг} множества индексов признаков {1,2,..., 2"}, которое позволило бы отличить рассматриваемые объекты друг от друга и описать их взаимные различия. Очевидно, решение этой задачи неоднозначно, и в общем случае могут существовать несколько таких минимальных множеств.

Рассматривается множество всех пар функций (fp,fq), р ф q, p,q Е {1,2,... ,m}. Минимальное подмножество О. множества номеров признаков

5Чегис А.И., Яблонский C.B. Логические способы контроля работы электрических схем // Труды математического института им. В.А.Стеклова. М.: АН СССР. - Т. 51. - 1958. - С. 270-360.

{1,2,... ,2™} называется минимальным тестовым набором для множества функций Р, если для Ур ф д,р, д е {1,2,..., т} существует признак с номером 3 такой, что /рС?) ф /,(;').

Для определения минимального тестового набора вводятся соответствующие парам (/р, /9), р ф д, р, д е {1,2,..., т}, различающие функции

Рассматривая эти различающие функции как векторы-столбцы по 2П компонент, можно построить двоичную таблицу С = ||с,-,*|| размера 2П х т{т — 1)/2, где с^ = ¡рл{з), к - номер пары {р, д) при алфавитном упорядочении. Минимальные тестовые множества соответствуют минимальным покрытиям этой двоичной таблицы строками.

Описанная процедура позволяет вместо исходного множества Р логических моделей / : Вп —> Ъ рассматривать множество Ф функций (р : £1 Z, где П — множество двоичных наборов, составляющих тестовый набор для множества функций Р.

Утверждение 2.1: Пусть П — тестовый набор для множества функций Р, и множество Ф состоит из функций <£>•;, для которых (р{(а) = /¿(а), Уа 6 Г2,г =

Тогда функция ра : Р х Р X такая, что

где г = 1,...,т,з = 1 ,...,т, а квадратные скобки соответствуют переходу от логического значения "истина" к числовому 1 и от значения "ложь" к О, является метрикой на множестве Р.

Доказательство. Симметричность очевидна: исходя из определения функции ра имеем ра(/г, /;) = рШз, /¿). ^г = 1,... ,т,з = 1,..., т.

Очевидно также, что если = то рп{кЛ) = 0, Уг = 1 ,...,т,з = 1,..., т. Обратное утверждение тоже верно, ибо в противном случае, при ф существует набор а £ Г2 такой, что /¡(а) ф /¿(а), то есть </?,(а) ф щ{а). Значит, [у>,-(а) © = 1 и рп(/», ЛО Ф 0 — противоречие.

Что же касается неравенства треугольника, то его справедливость вытекает из того, что для любого набора а £ П

для произвольных индексов {1,3,к) £ {1,...,т}3. Действительно, нарушение этого неравенства было бы возможно лишь в том случае, когда его правая часть была бы равна нулю, т.е. <#(а) = <л(а) = и ПРИ этом левая часть рав-

нялась бы единице, т.е. Ф^а) ф а), но эти два условия противоречат друг

\<Рг{а) © 4>]{а)) < Ыа) © ^(а)] + Ыа) © ^'О)],

ДРУГУ-

Следовательно,

pn{fi, fj) < Pn{fi, fk) + pn{fk, fj)-

Таким образом, pa является метрикой на множестве функций F, утверждение доказано.

Далее, в главе рассматривается математическая модель системы распознавания6, решающая функция которой описывается набором пар F = {(а®, г,-), i = 1,.. •, q}, где аг — некоторое множество векторов в пространстве описаний объектов V, а Г{ — номер кластера, которому оно соответствует. Пару (аг,Г{) будем называть обобщенным эталоном. Пусть также имеется некоторая совокупность X = {ßi,j = 1,. ■ ■, t} множеств из V, на которой система должна быть определенной. Остановимся на случае, когда для всех г = 1,..., q и j = 1,..., t множества аг и ß3 являются гранями декартова произведения С\ х С2 х ... х С„, т.е. имеют вид

а* = {a\, а\,..., агп) = а\ х а\ х ... х а'п

ßj = (ßißi...,ßl) = ß{xßix...x0i,

где а] С Chßi С Съ Vi = 1,..., q, j = 1,..., t, l = 1,... ,n.

Модель (F, X) системы распознавания называется непротиворечивой, если для всех i,j £ {1,..., q] при Г{ Tj имеем

aWn^y/) =0,

т.е. непротиворечивость системы говорит о том, что обобщенные эталоны, соответствующие разным кластерам, не могут пересекаться.

Модель (F, X) называется полной, если имеет место вложение:

U ßl С ü а,:.

1 ¿=1

Для полной и непротиворечивой модели (F,X) распознавание поступающего на вход системы вектора / = (/1; /2,..., /„), / € ßs для некоторого s G {l,...,i}, сводится, очевидно, к поиску обобщенного эталона (a,г) £ F такого, что / € а. Всегда существует по крайней мере один такой эталон, если же их несколько, то они непременно соответствуют одному и тому же кластеру с номером г.

На практике условие принадлежности распознаваемого вектора области определения, соответствующей полной модели, часто не выполняется. В этом случае для классификации объекта обычно используется функция расстояния, позволяющая найти ближайший к распознаваемому вектору эталон.

6Ололченов A.B., Фролов А.Б. Синтез и верификация систем принятия решений функционального тила //' Известия РАН. Сер. Теория и системы управления. - 2002. - №5. - С. 101-110.

В развитие работы, указанной в сноске 6, введем следующие понятия. Проекцией модели системы распознавания {Е, X) на множество = 0ь;?2, • • ■Лт} С {1,2,... ,п] называется модель для которой

Ра = {{а\п), г = 1,. ..,д},

где йг = (а},, а}2,..., а)т), ¡З3 = ■ ■ ■, /3*т). Очевидно, взятие проекции

соответствует исключению из рассматриваемых векторов всех компонент, кроме тех, номера которых принадлежат множеству О.

Будем называть набор индексов Г2 тестовым набором или просто тестом для модели X), если соответствующая проекция является непро-

тиворечивой моделью.

Утверждение 2.2: Пусть П — тестовый набор для полной непротиворечивой системы (Р.Х).

Тогда для произвольного вектора /, принадлежащего некоторой грани области определения £ X, имеет место следующее: если

/ 6 а\ (а\г») Е и/ей', (а*, г*) е ¿Ъ, где / = (fj1,..., — проекция распознаваемого вектора на то

П - гк.

Доказательство. Пусть / € а\(аг,г;) € Р, / е ак,

(.ак,гк) £ Рп. Тогда

= /3- £ а®- = а®- и £ а^, V? € П. Следовательно, /еа'П а* и, поскольку / € /З5, то

(2.1)

Если r^ ф гк, то (2.1) означает, что система (Р^,Хп) противоречива, но это невозможно, ибо по условию О, — тест для X). Значит, г, = гк, и утверждение доказано.

Из этого утверждения следует, что использование теста Г2 С {1,2,..., п} позволяет снизить размерность рассматриваемой задачи распознавания до количества элементов ¡П| в тестовом множестве, откуда автоматически возникает вопрос о поиске минимального тестового набора. Приведенный в главе алгоритм поиска такого набора распространяет классический алгоритм построения тестов на случай множественных эталонов.

При использовании логических моделей для распознавания топологических форм на практике часто возникают конфигурации, в которых отдельные объекты или связи между ними являются малозначимыми или и вовсе не существенными (например, в случае введения фиктивных элементов). Этот факт является основанием для использования обобщенных эталонов, которые представляют собой пары вида (а\тч), где а1 — множества логических моделей, а

г, — кластеры, которым они соответствуют. Пусть имеется q таких эталонов, соответствующих кластерам в количестве q*.

Будем рассматривать множества аг, представимые в виде векторов

а* = К, 4,..., а*„), а} е {{0}, {1}, • ■ •, {*}, х}, VI = 1,..., 2", (2.2)

где х — {0,1,..., А;}. Такие вектора, очевидно, соответствуют совокупностям моделей, некоторые компоненты которых зафиксированы, а остальные (компоненты, признанные малозначимыми) принимают все допустимые значения.

Рассмотрим следующий алгоритм И распознавания на основе множественных эталонов описанного вида.

1. Пусть на вход процедуры распознавания поступает логическая модель / = (А,..., А") распознаваемого объекта, где fc & {0,..., к}, Vi = 1,..., 2".

2. Для каждого обобщенного эталона (а\ г,:) вычисляется расстояние d(f, аг) от распознаваемой модели до этого эталона по следующей формуле:

ПП

d{f,ai) = tG({fj},a% (2.3)

j = l

ГД6

G{A,B) = \]: еслиЛп£ = 0, ^ ' [0, иначе. v '

3. Определяется номер г* эталона, на котором достигается минимум расстояния d(f, аг):

= .min </,аг).

Если имеется несколько таких эталонов, то выдается отказ от распознавания (и, возможно, запрос на обучение с созданием нового кластера). Если же имеется единственный такой эталон, то выдается решение о классификации распознаваемого элемента в кластер с номером г>.

В главе доказывается справедливость следующих утверждений. Утверждение 2.3: Для определенной согласно (2.3) и (2.4) функции расстояния d(f, а), где / — логическая модель, а — множество вида (2.2), справедлива следующая формула:

¿(/,аг) = min p(f,z), (2.5)

гба'

где

3=1

Утверждение 2.4: Алгоритм 7Z является метрическим. Утверждение 2.6: Пусть — тестовый набор для непротиворечивой моде-

q

ли системы распознавания (F, А'), и имеется совокупность векторов Z С L) а\

¿=1

соответствующих различным кластерам, т. е. 'izl,z; 6 Z,zl ф zJ, существуют обобщенные эталоны (а®, и (aJ, rj), для которых z% €Е а®, €Е qj и rj Tj.

Тогда множество индексов Г2 будет являться тестом для совокупности векторов Z.

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

Также в главе описывается возможность применения несимметричных и неортогональных отношений в логических моделях, построенных по принципу конечной топологии. Здесь же введены некоторые численные характеристики систем распознавания, которые могут быть использованы для их анализа. Кроме того, произведено сравнение моделей, построенных по принципу конечной топологии, с другими конфигурационными моделями дискретной математики — графами, гиперграфами, мографами — и показано, что логические модели, построенные на основе принципа конечной топологии, обеспечивая все необходимые функции, допускают сравнение по наборам числовых параметров, а не по структурным характеристикам, и введение метрики без явного погружения в метрическое пространство.

Моделируемые конфигурации могут состоять из большого числа объектов и таких конфигураций может быть достаточно много. Автоматизация процесса моделирования, несомненно, предполагает использование компьютерной техники для организации работы с логическими моделями. В результате очевидна необходимость проектирования программных средств для реализации моделирования по принципу конечной топологии.

В третьей главе рассматривается библиотека FTLIB классов для логического моделирования на основе принципа конечной топологии.

Основные возможности библиотеки можно разделить на три категории:

1. задание и хранение логических моделей и организацию семейств моделей в оперативной памяти (сюда входят объекты классов, соответствующих элементам отношения, моделям и семействам моделей, включая методы модификации этих объектов);

2. сохранение моделей и их семейств в файлах специального формата и в формате XML (к этой категории относятся методы сохранения семейств моделей в файлы особого формата, методы записи семейства в документ XML, а также методы сохранения разбиения семейства, полученного в результате кластеризации в группу различных файлов);

3. выявление структурных различий между моделями (построение тестов) и кластеризация семейств логических моделей (включая методы сравнения моделей, построения тестов для семейства моделей и разбиения его на кластеры с помощью различных алгоритмов, а также сохранение в оперативной памяти тестовых наборов и результатов кластеризации).

Перечисленные возможности реализованы в виде нескольких классов объектов, включающих в себя данные особой структуры и соответствующие методы для их обработки.

Ключевыми являются следующие классы библиотеки:

1. класс RelEl элемента симметричного отношения;

2. класс Model, соответствующий логической модели топологического пространства;

3. класс семейства логических моделей SetOfModels.

Эти классы созданы с помощью языка программирования С++ на базе системы быстрой разработки программ Borland С++ Builder и собраны в библиотеку классов.

В четвертой главе изложены различные аспекты построения программного обеспечения на основе созданной библиотеки классов FTLIB.

Эффективность и удобство использования библиотеки классов для логического моделирования FTLIB были подтверждены путем создания на ее основе нескольких программ.

Программная система FM-ORGANIZER предназначена для задания, хранения. редактирования, построения тестов и классификации семейств логических моделей.

Программа XML4FM используется для автоматизированного интерактивного составления XML-документов, описывающих семейства логических моделей. Написание таких документов производится на основе специальной XML-схемы7.

Программа TOCR Demo предназначена для демонстрации использования принципа конечной топологии в OCR. Она позволяет производить распознавание классов толерантности шейпов8 оптических образов символов с помощью функций, представленных в библиотеке FTLIB. Для распознавания используется специальный алгоритм [6]. Программа TOCR Demo позволила опробовать использование принципа конечной топологии в распознавании оптических образов символов и послужила основой для построения более мощной OCR-системы.

Система TOCR, распознавания оптических образов текстов построена на основе принципа конечной топологии с помощью библиотеки классов FTLIB. Эта система предназначена для решения задачи сопоставления изображению текста на некотором языке последовательности символов алфавита этого языка. При этом производится кластеризация изображения, позволяющая выделить отдельные символы, после чего уже осуществляется и само распознавание.

7Э. Р. Гарольд, В. С. Мине XML: справочник. М.: Символ-Плюс. - 2001. - 463 С.

8Фролов А.Б., Болотов A.A. Классификация и распознавание в дискретных системах. - М.: Издательство МЭИ. - 1997. - 187 С.

0 ^ © © О © ® ®0 О © ® ■ .............—...........1 © ©

®© @ © ® ® ® 0 ® е?® е !

О, в А © ^^ I © ;

! | (у бГ®

Рис.1

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

Принцип конечной топологии как метод логического моделирования конфигураций объектов находит широкое применение в стереохимии, позволяя описывать молекулярные формы, характеризовать их различия и классифицировать их в группы с помощью предварительно введенной функции расстояния.

Пример. Рассмотрим семейство молекулярных форм для этилового спирта С2Я5ОЯ. Построенные по данным из книги П. Мезея (См. сноску 1.), схематичные изображения поверхностей уровня плотности и разбиений этих поверхностей при различных значениях а порога плотности (измеряемой в атомных единицах) представлены на рисунке 1 (слева направо и сверху вниз по мере понижения порога плотности).

Элементы разбиения были занумерованы в порядке их появления по мере понижения порога плотности, причем в базу топологии вошли лишь элементы, соответствующие отдельным атомам водорода, углерода и кислорода, составляющим рассматриваемую молекулу. Следует отметить, что полный набор базовых элементов присутствует лишь при малых значениях порога плотности. Для больших же значений порога при построении окончательных логических моделей использовалось введение в первичные модели при необходимости фиктивных переменных, соответствующих отсутствующим в плотностном контуре областям. В результате было получено четырнадцать логических моделей на основе девяти базовых множеств, пронумерованных на рисунках цифрами от 1 до 9.

Построение первичных логических моделей / было осуществлено по следу-

(а) ю fi f2 f3 и и fe fr f8 и fio fu fia fu fl4

5 0 0 0 0 0 0 0 0 0 0 0 0 1

6 0 0 0 0 0 0 0 0 0 0 1 1 1 1

12 3 0 0 0 0 0 0 1 1 1 1 1 1 1

18 3 3 0 0 0 0 0 0 0 0 0 1 1 1

33 3 3 3 0 0 0 1 1 1 1 1 1 1 1

66 3 3 3 3 0 0 0 0 0 0 0 0 1 1

132 3 3 3 3 3 0 0 0 1 1 1 1 1 1

258 3 3 3 3 3 0 0 0 0 1 1 1 1 1

Кластеры 1 1 1 2 2 3 3 3 3 3 3 3 I 3 3

ющим общим правилам:

1. /(О,..., 0,1,0,..., 0) = 3, i = 1,2,..., 9, при условии, что г-я перемен-

i

ная не является фиктивной (значение 3 отражает тот факт, что базовые множества выпуклы);

2. /(0,..., 0,1,0, — 0,1,0,..., 0) = 1, если i-e базовое множество соединя-

» ' 3

ется с j-тым;

3. /(а) = 1 для а = (оi,..., ад) G {0,1}9 веса |а| > 3, если соответствующее вершине а единичного 9-мерного куба множество топологии представляет собой целый домен одинаковой плотности — одну из компонент связности поверхности уровня плотности.

Значения функции / на остальных вершинах единичного 9-мерного куба полагаются равными нулю.

В результате было получено семейство из четырнадцати логических моделей, соответствующих формам рассматриваемой молекулы этанола при различных значениях порога плотности. Для выявления структурных различий между моделями (и соответствующими молекулярными формами) к полученному семейству была применена процедура построения тестов, которая определила тестовый набор для совокупности имеющихся моделей: {5,6,12,18,33,66,132,258} при десятичном представлении аргументов или

{(0,0,0,0,0,0,1,0,1), (0,0,0,0,0,0,1,1, 0),

(0,0,0,0,0,1,1,0,0), (0,0,0,0,1,0,0,1,0),

(0, 0,0,1,0,0,0,0,1), (0,0,1,0,0,0,0,1,0),

(0,1,0,0,0,0,1,0,0), (1,0,0,0,0,0,0,1,0)}

при двоичном представлении с нумерацией справа налево (см. Таблицу 1: столбец (а)ю содержит значения аргумента из минимального тестового набора в десятичном представлении; также здесь приведены результаты кластеризации).

Для кластеризации был выбран метод с минимальной энергией8, в качестве потенциала использовался весовой функционал на множестве различающих функций. Результаты кластеризации приведены в Таблице 1 в виде соответствующих моделям номеров кластеров.

Вычисления были произведены с использованием упомянутой выше компьютерной программы FM-ORGANIZER.

Также в главе приводятся примеры использования программы TOCR, созданной с помощью библиотеки классов FTLIB для распознавания оптических образов текстов, включая серию экспериментов по распознаванию оптических образов полифонтовых текстов, в результате которых было установлено, что метод допускает существенную экономию числа операций и объема используемой памяти при распознавании текстов разных шрифтовых гарнитур. Кроме того, проведен анализ характеристик разработанной системы распознавания и ее сравнение с аналогичной системой, подтвердившее эффективность предложенного подхода.

В заключении приведены основные результаты работы.

Приложения содержат тексты XML-описаний, дополнительные иллюстрации, копии актов о внедрении и листинги программного кода.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

1. Дан краткий обзор некоторых областей науки и техники, в которых возникают задачи, связанные с анализом, распознаванием и классификацией топологических форм. Проведен сравнительный анализ различных методов моделирования топологических форм, включая принцип конечной топологии. В результате было показано, что принцип конечной топологии является универсальным (применимым для общего случая многомерных отношений) способом моделирования топологических форм, допускающим сравнение по наборам числовых параметров, а не по структурным характеристикам, и позволяющим определить метрику на множестве топологических форм, избегая явного погружения в метрическое пространство.

2. При рассмотрении принципа конечной топологии автором расширяется область применимости метода на случай несимметричных и неортогональных

'J Болотом A.A. О метрической кластеризации ,// Дискретная математика. - Т. 8. - Л"е4. -- 1996. - С. 62-78.

отношений на базовых элементах топологической формы.

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

4. В работе показано, что предложенный алгоритм распознавания для обобщенных эталонов на основе множеств логических моделей является метрическим.

5. Рассмотрена математическая модель системы распознавания на основе обобщенных эталонов, для нее введено понятие теста и показана возможность понижения размерности системы путем использования ее проекции на тестовый набор,

6. Показано, что использование метрики, порождаемой сравнением моделей на тестовых наборах существенно, в несколько раз, ускоряет процедуру кластеризации и распознавания, а также сокращает объем информации об эталонах.

7. В результате выявления в ходе проведенного анализа необходимости проектирования программных средств для реализации моделирования по принципу конечной топологии разработана специальная библиотека классов для логического моделирования. Спроектированная структура классов реализована с помощью языка программирования С++.

8. Разработанная библиотека позволяет создавать различные программные средства для логического моделирования, построения тестов и классификации с помощью принципа конечной топологии. В частности, на основе библиотеки классов FTLIB автором разработан ряд демонстрационных программ, позволяющих задавать, хранить, редактировать, осуществлять поиск тестовых наборов и классификацию логических моделей и их семейств, создавать в диалоговом режиме описания семейств логических моделей в виде XML-документов, а также использовать принцип конечной топологии для распознавания оптических образов символов.

9. В работе приведены результаты проведенных экспериментальных исследований применимости библиотеки классов FTLIB для логического моделирования на основе принципа конечной топологии в молекулярной химии и распознавании оптических образов текстов.

10. Специальная схема параметризации и распознавания, позволяющая использовать библиотеку классов FTLIB в OCR была реализована в экспериментальной системе TOCR распознавания оптических образов текстов. С

целью ускорения работы системы было обосновано и реализовано использование процедуры построения тестов для специального преобразования системы эталонов в процессе обучения, благодаря чему удалось добиться увеличения скорости распознавания в 4-5 раз. Проведенная серия экспериментов по распознаванию для различных шрифтовых гарнитур позволила установить, что предложенный метод допускает существенную экономию числа операций и объема используемой памяти при распознавании полифонтовых текстов. Анализ характеристик разработанной системы и ее сравнение с аналогичной системой подтвердили эффективность предложенного подхода.

ОСНОВНЫЕ ПУБЛИКАЦИИ

1. Бредихин Р.Н. Библиотека классов FTLIB для логического моделирования; Московский энергетический институт (технический университет) .М., 2005 - 23 С.: ил. 10, библиогр. 19 назв.- Рус,- Деп. В ВИНИТИ 27.05.2005., №754.

2. Бредихин Р.Н. Библиотека классов для логического моделирования на основе принципа конечной топологии // Вестник МЭИ.- 2005,- №5.- С. 101-110.

3. Бредихин Р.Н. Моделирование несимметричных отношений в рамках принципа конечной топологии, рук. д.т.н., проф. Фролов А.Б. // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Десятая международная научно-техническая конференция студентов и аспирантов: Тез. докл. Том 1- Изд-во МЭИ,- 2004,- С. 276-277.

4. Бредихин Р.Н. О принципе конечной топологии и его применении; Московский энергетический институт (технический университет).- М., 2004.- 18 С.: ил. 16, библиогр. 21 назв.- Рус,- Деп. В ВИНИТИ 19.04.2004, №637.

5. Бредихин Р.Н. Об одной метрике в пространстве функциональных моделей, рук. д.т.п., проф. Фролов А.Б. // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Одиннадцатая международная научно-техническая конференция студентов и аспирантов: Тез. докл. Т. 1,-Изд-во МЭИ,- 2005,- С. 301.

6. Бредихин Р.Н. Об одном подходе к распознаванию оптических образов текстов // Вестник МЭИ,- 2005,- №2,- С. 134-141.

7. Бредихин Р.Н. Применение принципа конечной топологии в системах принятия решений, рук. д.т.н., проф. Фролов А.Б. // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Девятая международная

научно-техническая конференция студентов и аспирантов: Тез. докл. Т. 1- Изд-во МЭИ,- 2003.- С. 251-252.

8. Бредихин Р.Н. Принцип конечной топологии в распознавании оптических образов текстов, рук. д.т.н., проф. Фролов A.B. // Научная сессия МИФИ-2005. Сборник научных трудов. В 15 томах. Т. 14. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. М.: МИФИ,- 2005.- С. 50-51.

9. Бредихин Р.Н. Принцип конечной топологии в системах принятия решений функционального типа, рук. д.т.н., проф. Фролов A.B. // Научная сессия МИФИ-2003. Сборник научных трудов. В 14 томах. Т. 13. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. М.: МИФИ,- 2003,- С. 99-100.

10. Бредихин Р.Н. Принцип конечной топологии для несимметричных отношений, рук. д.т.н., проф. Фролов A.B. // Научная сессия МИФИ-2004. Сборник научных трудов. В 14 томах. Т. 14. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. М.: МИФИ-2004,- С. 70-71.

11. Бредихин Р.Н. Распознавание оптических образов символов в условиях помех на основе принципа конечной топологии, рук. д.т.н., проф. Фролов A.B. // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Двенадцатая международная научно-техническая конференция студентов и аспирантов: Тез. докл. Т. 1- Изд-во МЭИ - 2006 - С. 348-349.

12. Бредихин Р.Н. Система TOCR распознавания оптических образов текстов на основе принципа конечной топологии // Труды международной научно-технической конференции "Информационные средства и технологии". 1820 октября 2005 г. В 3-х т. Т. 2. М.: Янус-К - 2005,- С. 102-105.

13. Бредихин Р.Н. Сравнение множеств логических моделей, построенных по принципу конечной топологии, рук. д.т.н., проф. Фролов А.Б. /'/ Научная сессия МИФИ-2006. Сборник научных трудов. В 16 т. Т. 15. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. Экономика и управление. М.: МИФИ - 2006 - С. 106-107.

Подписано в печать ä.Oi.-O^ Зак ££ Тир. ^ П. л. $,1Ь

Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д. 13

Введение Топологические формы и методы их моделирования

1.1. Топологические формы

1.1.1. Молекулярные формы в химии

1.1.2. Распознавание оптических образов текстов

1.1.3. Географические информационные системы

1.1.4. Морфологический анализ изображений

1.2.1. Графы

1.2.2. Гиперграфы

1.2.3. Мографы

1.3. Выводы по главе

1.2. Некоторые методы моделирования топологических форм Принцип конечной топологии, его свойства и преимущества

2.1. Моделирование топологического нространства с конечной тонологией

2.2. Логические модели и их свойства

2.3. Методы сравнения и классификации

2.4. Принцип конечной топологии

5. Порождение метрики на тестовом наборе

2.6. Система расиознавания на основе обобщенных эталонов

2.7. Тестовая проекция системы распознавания

2.8. Множества логических моделей как обобщенные эталоны

2.9. Численные характеристики системы распознавания

0. Сравнительный анализ некоторых методов моделирования топологических форм

1. Выводы по главе Описание разработанной библиотеки классов д л я логического моделирования на основе принцина конечной тонологии

3.1. Назначение библиотеки FTLIB и ее возможности

3.2. Описание основных классов библиотеки

3.2.2. Описание класса элемента отношения RelEl

3.2.3. Описание класса модели Model и особенности представления логических функций

3.2.4. Описапие класса семейства моделей SetOfModels

3.3. Выводы по главе Разработка программного обеспечения на основе созданной библиотеки классов

4.1. Общие принципы построения программ на основе библиотеки классов

4.2. Примеры программ, использующих библиотеку классов для логического моделирования V

3.2.1. Описание шаблона класса однонанравленного списка Lst S

4.2.1. Описание разработанной программы FM-ORGANIZER

2.2. Программа XML4FM

4.2.3. Программа TOCR Demo

4.3. Экспериментальная система TOCR распознавания оптических образов текстов

4.4. Выводы по главе Результаты экспериментальных исследований для заданных предметных областей

5.1. Логические модели молекулярных форм

5.1.1. Модели поверхностей уровня

5.1.2. Метрика или полуметрика на семействе молекулярных форм

5.2. Построение XML-описания семейства логических моделей

5.3. Распознавание оптических образов символов на основе принципа конечной топологии

5.3.1. Выделение скелета изображения символа и определение критических точек

5.3.2. Построение логической модели и введение метрики на основе метода назначения

5.3.3. Система эталонов, распознавание символа

5.3.4. Использование тестовых наборов для ускорения работы системы распознавания

5.3.5. Примеры распознавания

5.3.6. Распознавание оптических образов текстов

5.3.7. Исследование работы системы с различными шрифтовыми гарнитурами

3.8. Анализ характеристик предложенной системы распознавания оптических образов текстов и сравнение ее с аналогичной системой

5.4. Выводы по главе

Заключение Литература

Приложения

Приложение 2: Дополнительные иллюстрации к примерам распознавания оптических образов текстов

Приложение 3: Копии актов о внедрении результатов диссертационной работы

Приложение 1: XML-схема для описания семейств логических моделей159

Приложение 4: Заголовочный файл библиотеки классов FTLIB

Актуальность работы Одной из ключевых задач информатики является задача распознавания образов. Интерес к ней обусловлен существованием широкого круга задач различных отраслей науки и техники, связанных с разбиением множества объектов на классы и распознаванием класса, которому принадлежит данный объект. В области распознавания образов сложился ряд научных школ, различающихся подходами к этой проблеме. Комбинаторно-логический подход характерен для школы СВ. Яблонского и В.В. Кудрявцева [45, 93], берущей начало от фундаментальной работы А.И. Чегис и СВ. Яблонского о контроле электрических схем [86], первой в мировой науке работы по теории построения тестов. Алгебраический подход сформировался в работах Ю.И. Журавлева [34, 36]. Метод физических аналогий в распознавании образов оформился в теории потенциальных функций и морфологическом анализе (М.А. Айзерман, Э.М. Враверман, Л.И. Розоноэр, Ю.П. Пытьев) [1,59-61,122]. Особое место занимают подходы к распознаванию образов на основе нейронных сетей и параметрический подход на основе статистических свойств ансамбля классифицируемых объектов. В настоящей работе используются методы комбинаторно-логической теории распознавания образов. В каждом из направлений развитие теории распознаваний сопровождается обоснованием и созданием нрограммных средств для реализации основных подходов и методов с учетом особенностей предметной области. Данная работа посвящена обоснованию и созданию библиотеки классов для программирования задач кластеризации и распознавания топологичвских форм. Топологической формой будем называть конфигурацию, которая состоит из определенного числа объектов, обладающих некоторыми свойствами из конечного числа свойств и участвующих в отношениях на множестве объектов. Конфигурации такого типа достаточно широко встречаются во многих областях науки и техники, среди которых стереохимия, распознавание оптических образов текстов, геоинформатика и др. И во многих случаях в связи с топологическими формами возникают задачи их распознавания и кластеризации. Однако, несмотря на то, что отдельные задачи, связанные с описанными конфигурациями, в частных вариантах решаются вполне успешно, в общем случае единые правила и методы моделирования, кластеризации и распознавания структур, названных в данной работе топологическими формами, прежде не рассматривались. Для успешного решения задачи раснознавания требуется некоторая функция расстояния на множестве пар объектов, в частности, функция, удовлетворяющая аксиомам метрики. Как правило, такая функция определяется на основе той или иной математической модели объекта, допускающей сравнение объектов и их множеств. Использованное в данной работе понятие топологических форм является обобщением понятия молекулярных форм, описанных П. Мезеем в его работах по молекулярной химии, в частности, [117] Формирование модели конкретного объекта называют этаном его параметризации определения набора значений характеризующих объект атрибутов. Например, часто в качестве исходных данных для нараметризации используются результаты измерений геометрии объекта. В этом случае модель изображения формируется на основе вектора его размеров в некотором метрическом нространстве. Однако нодход, требующий помещения объекта в метрическое пространство, на практике оказывается не всегда эффективным. В некоторых областях применения систем автоматического раснознавания рассматриваемые объекты, имея одинаковую структуру, могут существенно отличаться друг от друга по геометрическим характеристикам. Используемые для распознавания в таких условиях методы (в частности, разработанный на основе теории построения тестов СВ. Яблонского нринцип конечной топологии [106, 107]) существенно отличаются тем, что основным предметом их рассмотрения является не размеры и геометрические параметры объектов, а структура объекта, взаимосвязи между его отдельными составляющими. Таким образом, задача обоснования и создания программных средств д.пя реализации известных методов, алгоритмов и систем распознавания топологических форм и усовершенствования этих методов является актуальной. Цель работы Целью настоящей работы явилось обоснование и создание библиотеки классов для нрограммирования задач кластеризации и распознавания тонологических форм. При этом ставились следующие задачи: 1. Проанализировать существующие способы моделирования топологических форм, выявить особенности их описания и обосновать выбор методов моделирования, кластеризации и распознавания. 2. Модернизировать известные методы принцина конечной топологии с целью повышения эффективности процессов кластеризации и распознавания. 3. Создать структуру классов, поддерживающих описания топологических форм на основе принципа конечной топологии. 4. Снабдить классы объектов необходимыми подпрограммами (методами) для кластеризации и распознавания. 5. Обеспечить высокое быстродействие и эффективное использование оперативной памяти при использовании библиотеки. Методы исследования Для проведения исследований были использованы методы теории распознавания образов, топологии, теории построения тестов, теории решеток. При создании программного обеспечения использовались методы объектноориентированного программирования. Научная новизна Реализованная в библиотеке классов модернизированная модель топологической формы допускает несимметричность и неортогональность отношений на базовых элементах тонологической формы. Обоснован и реализован в библиотеке метод порождения метрики на множестве топологических форм путем сравпения моделей на тестовых наборах. Обоснован и реализован в библиотеке классов метод построения тестов для топологических форм, имеющих несущественные отличия (обобщенных эталонов). Реализованы методы кластеризации и распознавания тонологических форм. Практическая значимость работы Использовапие метрики, порождаемой сравнением моделей на тестовых наборах существенно, в несколько раз, ускоряет нроцедуру кластеризации и распознавания, а также сокращает объем информации об эталонах. Представление совокунности несущественно отличающихся топологических форм в виде множеств логических моделей позволяет использовать обобщенные эталоны, что повышает качество и скорость процедур кластеризации и распознавания. Разработанная библиотека классов использована при создании OCR-системы. Библиотека может использоваться также для классификации и распознавания молекулярных форм, объектов геоинформатики и в других областях. Результаты диссертации были внедрены в Центральном научноисследовательском институте машиностроения (ФГУП ЦНИИМаш) для повышения скорости обработки целевой информации при управлении космическими аппаратами типа "Коронас-Ф" и "Канопус-В" в Российском государственном научно-исследовательском иснытательном центре нодготовки космонавтов им. Ю.А. Гагарина (РГНИИЦПК им. Ю.А. Гагарина) при создании программного обеспечения функционально-моделирующего стенда подготовки космонавтов, а также использованы при выполнении НИР «Инфор10 мационные технологии классификации и распознавания на основе принципа конечной топологии» и НИР «Методы реализации вычислений в конечных алгебраических структурах нрименительно к задачам защиты информации и распознавания образов» в МЭИ (ТУ). Обоснованность и достоверность результатов Результаты диссертации обоснованы с помощью известных теоретических методов, и их достоверность подтверждена экспериментально путем испытаний созданной на их основе системы распознавания оптических образов текстов. Анробация работы Основные результаты диссертационной работы докладывались и обсуждались на: Шестой, седьмой, восьмой, девятой Московской международной телекоммуникационной конференции студентов и молодых ученых «Молодежь и наука», Москва, 2003, 2004, 2005, 2006; Девятой, десятой, одиннадцатой и двенадцатой международной научнотехнической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика», Москва, 2003, 2004, 2005, 2006; Тринадцатой международной научно-технической конференции «Информационные средства и технологии», Москва, 2005. Публикация Основное содержание диссертации отражено в 13 публикациях. 11 Структура и объем диссертационной работы Работа состоит из введения, пяти глав, заключения, библиографического списка, включающего 123 наименования, и приложений, содержащих 5 дополнительных рисунков. Основной текст занимает 158 машинописных страниц, в том числе 35 рисунков и 32 таблицы. Общий объем диссертации составляет 177 страниц. Основное содержание работы Во введении обоснована актуальность темы, сформулированы цели и основные задачи исследования, показана научная новизна и практическая значимость результатов, приведены сведения об апробации работы. В первой главе рассматривается понятие топологических форм и приводятся примеры областей науки и техники, где возникают задачи, связанные с анализом, распознаванием и классификацией подобных конфигураций. Также здесь дается краткий обзор некоторых методов моделирования топологических форм, таких как графы, гиперграфы и мографы. Во второй главе рассматривается припцип конечной топологии новый [106,107] подход к классификации и распознаванию топологических форм, согласно которому может быть осуществлено моделирование топологических форм, апализ и сравпение полученных логических моделей, а также их разбиение на классы. При этом автором снимаются ограничения на симметричность и ортогональность отношений на совокупности объектов, а также рассматривается схема сравнения не отдельных моделей, а их множеств. В главе проведено сравнение принципа конечной топологии с другими способами моделирования топологических форм и отмечено, что логические модели. 12 построенные на основе нринципа конечной тонологин, обеспечивая все необходимые функции, допускают сравнение, в отличие от других моделей, по наборам числовых параметров, а не по структурным характеристикам. В третьей главе описывается разработанная автором библиотека FTLIB классов для логического моделировапия на основе принципа конечной топологии. Приводится список возможностей библиотеки и описания основных классов. В четвертой главе описаны различные аспекты построения программного обеспечения на основе созданной библиотеки классов FTLIB. Также здесь приведены описания программ, разработанных автором с помощью предложенной библиотеки классов. В пятой главе приведены результаты экспериментальных исследований возможностей использования принципа конечной тонологии при решении задач кластеризации и распознавания для некоторых предметных областей. Проиллюстрированы возможности библиотеки для логического моделирования на основе принципа конечной тонологии, использованной для описания молекулярных форм, а также ее применение при распознавании оптических образов текстов. В заключении приведены основные результаты работы. Приложения содержат тексты XML-описаний, дополнительные иллюстрации, копии актов о внедрении результатов работы и текст заголовочного файла спроектированной библиотеки классов. 13

1. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод нотенциальных функций в теории обучения машин. М.: Наука, 1970.

2. Аркадьев А.Г., Браверман Э.М. Обучение машины классификации объектов. М.: Наука, 1971. 3. Ахо А., Хонкрофт Дж., Ульман Дж. Ностроение и анализ вычислительных алгоритмов. М.: Мир, 1979.

3. Бадд Т. Объектно-ориентированное нрограммирование в действии. СПб.: Нитер, 1997.

4. Бакстон Ш., Роберте Бведение в стереохимию органических соединений: от метана до макромолекул. М.: Мир, 2005.

5. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

6. Болотов А.А. О метрической кластеризации Дискретная математика, 8, т, 1996, стр. 62-78.

7. Борисович Ю.Г., Близняков Н.М., Израилевич Я.А., Фоменко Т.Н. Бведение в топологию. М.: Наука, 1995.

8. Браверман Э.М., Мучник Н.Б. Структурные методы обработки эмнирирических данных. М.: Наука, 1983. 146

9. Бредихин Р.Н. Библиотека классов для логического моделирования на основе принципа конечной топологии Вестник МЭИ, 2005, JV5, стр. 101-110.

10. Бредихин Р.Н. Моделирование несимметричных отношений в рамках принципа конечной тонологии, рук. д.т.н., проф. Фролов А.Б. РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Десятая международная научно-техническая конференция студентов и аспирантов. Тезисы докладов. Том 1. Изд-во МЭИ, 2004, стр. 276-277.

11. Бредихин Р.Н. О принципе конечной топологии и его применении; Московский энергетический институт (технический университет). М., 2004. 18 с ил. 16, библиогр. 21 назв. Рус. Деп. В ВИНИТИ 19.04.2004, №637 В 2004.

12. Бредихин Р.Н. Об одной метрике в прострапстве функциональных моделей, рук. Д.Т.Н., проф. Фролов А.Б. РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Одиннадцатая международная научно-техническая конференция студентов и аспирантов. Тезисы докладов. Том

13. Издательство МЭИ, 2005, стр. 301.

14. Бредихин Р.Н. Об одном подходе к распознаванию оптических образов текстов Вестник МЭИ, 2005, X2, стр. 134-141. 147

15. Бредихин Р.Н. Принцип копечной топологии в распознавании оптических образов текстов, рук. д.т.н., проф. Фролов А.Б. Научная сессия МИФИ-2

16. Сборник научных трудов. В 15 томах. Т.

17. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. М.: МИФИ, 2005, стр. 50-51.

18. Бредихин Р.Н. Принцип конечной топологии в системах принятия решений функционального типа, рук. д.т.н., проф. Фролов А.Б. Научная сессия МИФИ-2

19. Сборник научных трудов. Б 14 томах. Т.

20. Конференция "Молодежь и паука". Компьютерные пауки. Информационные технологии. М.: МИФИ, 2003, стр. 99-100.

21. Бредихин Р.Н. Принцип конечной тонологии для несимметричных отношений, рук. д.т.н., проф. Фролов А.Б. Научная сессия МИФИ-2

22. Сборник научных трудов. Б 14 томах. Т.

23. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. М.: МИФИ, 2004, стр. 70-71.

24. Бредихин Р.Н. Распознавание оптических образов символов в условиях помех на основе принципа копечной топологии, рук. д.т.н., проф. Фролов А.Б. РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА. Двенадцатая международная научно-техническая конференция 148

25. Бредихин Р.Н. Система TOCR распознавания оптических образов текстов на основе принципа конечной топологии Труды международной научно-технической конференции "Информационные средства и технологии". 18-20 октября 2005 г., в 3-х томах. Т 2. М.: Янус-К, 2005, стр. 102-105.

26. Бредихин Р.Н. Сравнение множеств логических моделей, построенных по принципу конечной топологии, рук. Д.Т.Н., проф. Фролов А.Б. Научная сессия МИФИ-2

27. Сборник научных трудов. В 16 томах. Т.

28. Конференция "Молодежь и наука". Компьютерные науки. Информационные технологии. Экономика и управление. М.: МИФИ, 2006, стр. 106107.

29. Бугаевский Л.М., Цветков В.Я. Геоинформационные системы, М.: Златоуст, 2000.

30. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.: Наука, 1974.

31. Биркгоф Г. Теория решеток. М.: Наука, 1984.

32. Гарольд Э. Р., Мине В. С, XML: справочник. Символ-Нлюс, 2001.

33. Горбатов В.А. Основы дискретной математики. М.: Высшая школа, 1986.

34. Горбатов В.А. Теория частично упорядоченных систем. М.: Сов. радио, 1976. 149

35. Горелик А.Л.,Скрипкин В.А. Методы распознавания. М.: ВШ. 1989.

36. Гретцер Г. Общая теория решёток. М.: Мир, 1982.

37. Дейл Н., Уимз Ч., Хедингтон М. Программирование на С+4-. М.: ДМК, 2000.

38. Дуда Р., Харт П. Распознавание образов и анализ сцен, М.: Мир, 1967.

39. Дюкова Е. В., Журавлев Ю. И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности Ж. вычисл. матем. и матем. физ. 2000. т.4О, Ш, стр. 1264-1278.

40. Дюкова Е.В., Песков П.В. Поиск информативных фрагментов описаний объектов в дискретных процедурах распознавания Ж вычисл. матем. и матем. физ. 2002. т.42, М, стр. 741-753.

41. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации Проблемы кибернетики. М.: Паука, 1978. Вып. 33. стр. 5-68.

42. Загоруйко П. Г. Методы распознавания и их применение. М.: Сов. Радио, 1972.

43. Зейферт Г., Трельфалль В. Топология. Пер. с нем. П. Гордона; Под ред. П.С. Александрова. 2-е изд. М.; Ижевск: ПИЦ "Регулярная и хаотическая динамика, 2001. 150

44. Иванова Г. С, Ничушкина Т. Н., Пугачев Е. К. Объектно- ориентированное программирование. М.: Издательство МГТУ им. Н. Э. Баумана, 2003.

45. Калверт Ч., Рейсдорф К. Borland C++ Builder 5. М.: ДиаСофт, 2001

46. Келли Дж. Л. Общая топология. М.: Наука, 1968.

47. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. М: Наука, 1976.

48. Кошкарев А.В., Тикунов B.C. Геоинформатика, под ред. Д.В. Лисицкого. М.: Картгеоцентр-Геоиздат, 1993.

49. Кудрявцев В.В., Алешин СВ. Комбинаторно-логический нодход к распознаванию образов Интеллектуальные системы, 1997, т.1, вып. 1-4, стр. 31-40.

50. Кузин Л. Т. Основы кибернетики, том 1, М.: Энергоатомиздат, 1994.

51. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера, М.: Энергия, 1980.

52. Лафоре Р. Объектно-ориентированное программирование в C++. СПб.: Питер, 2003.

53. Мищенко А.С, Фоменко А.Т. Курс дифференциальной геометрии и топологии. М.: Мир, 1988.

54. Моррисон М. HTML к XML для начинающих. М.: Эком, 2002. 151

55. Ополченов А.В., Фролов А.Б. Синтез и верификация систем принятия решений функционального тина Известия РАН, сер. Теория и системы унравления, 2002, №5, стр. 101-110. 53. Оре О. Теория графов. М., Наука, 1968.

56. Павлидис Т. Алгоритмы машинной графики и обработки изображений, М.: Радио и связь, 1986.

57. Павловская Т. А., Щупак Ю. А. C++. Объектно-ориентированное программирование. Практикум. СПб.: Питер, 2004.

58. Питц-Моултис Н., Кирк Ч. XML. Снб.: BHV-Санкт-Петербург, 2000. 57. Пол А. Объектно-ориентированное программирование на C++, СПб.: Бином, Невский Диалект, 2001.

59. Потапов В.М. Стереохимия. М.: Химия, 1988, 464.

60. Пытьев Ю.П. Морфологические понятия в задачах анализа изображений, Докл. АН СССР, 1975, т. 224, М, 1283-1286.

61. Пытьев Ю.П. Морфологический анализ изображений, Докл. АН СССР, 1983, т. 296, Я5, 1061-1064.

62. Пытьев Ю.П., Чуличков А.И. ЭВМ анализирует форму изображений. М.: Знание, 1988, 48.

63. Роберте Ф. Дискретные математические модели. М., Наука, 1986.

64. Рохлин В.А., Фукс Д.Б. Начальный курс топологии. М.: Наука, 1977. 152

65. Скотт Д. Теория решеток, типы данных и семантика// Данные в языках программирования. М.: Мир, 1982. 25-53.

66. Соколов В.И. Введение

67. Стинрод Н., Чинн У. Первые понятия топологии: Геометрия отображений отрезков, кривых, окружностей и кругов. Новокузнецк: НФМИ, 2000.

68. Страуструп Б. Язык программирования C++. СПб.: Бином, Невский диалект, 1999.

69. Теобалд Д. О шейпинге на покрытиях. Топология и шейп-файлы ArcReview, 4 (19), 2001, стр. 20-21.

70. Тикунов B.C. Моделирование в картографии. М.: Изд-во МГУ, 1997. 71. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978.

71. Фарамазян Н.В. Схема распознавания оптических образов текстов на основе кластеризации Вестник МЭИ, 2000, K5, стр. 71-76.

72. Фоменко А. Т. Дифференциальная геометрия и топология. М.: МГУ, 1983.

73. Фоменко А.Т., Фукс Д.Б. Курс гомотопической топологии. М.: Наука, 1989. 75. Фор А. Восприятие и распознавание образов. М.: Машиностроение. 1989.

74. Фридман А.Л. Основы объектно-ориентированного нрограммирования на языке Си++, М.: Горячая линия-Телеком, 2001. 153

75. Фролов А.Б., Андреев А.Е., Болотов А.А., Коляда К.Б. Прикладные задачи дискретной математики и сложность алгоритмов. М.: Издательство МЭИ, 1997.

76. Фролов А.Б., Болотов А.А. Классификация и распознавание в дискретных системах. М.: Издательство МЭИ, 1997.

77. Фролов А.Б., Фролов Д.А. Алгоритмы раснознавания унорядоченных объектов в системах принятия решений функционального тина Вестник МЭИ, т, 1996, стр. 67-78.

78. Фролов А.Б., Фролов Д.А., Четрафилов И.Д. Распознавание в интеллектуальных системах функционального типа Интеллектуальные системы, том 2, вын. 1-4, 1997, стр. 201-210.

79. Фролов А.Б., Фролов Д.А., Яко Э. Функциональные схемы для распознавания унорядоченных объектов Известия РАН. Серия Теория и системы управления. №5, 1997, стр. 85-97.

80. Фролов А.Б., Четрафилов И.Д. О некоторых подходах к распознаванию оптических образов текстов Интеллектуальные системы, 1997, Т.2, вып. 1-4, стр. 189-200.

81. Фролов А.Б., Четрафилов И.Д. Сети нринятия решений для раснознавнаия оптических образов при наличии искажений Бестник МЭИ, N6, 1997, стр. 83-92. 154

82. Фукс Л. Частично упорядоченные алгебраические системы. М.: Мир, 1965.

83. Хабибуллин И. Самоучитель XML. СПб.: БХВ-Петербург, 2003.

84. Харари Ф. Теория графов, М.: Мир, 1973.

85. Холл М., Комбинаторика. М.: Мир, 1970.

86. Цыпкин Я.З. Основы теории обучающихся систем. М.: Наука, 1970.

87. Чегис А.И., Яблонский С Б Логические способы контроля работы электрических схем. Труды математического института им. Б.А.Стеклова. М.: АН СССР, т. 51, 1958, стр. 270-360.

88. Четрафилов И. Д. Исследование и разработка методов и систем распознавания оптических образов полиязыковых текстов: 05.13.11 Математическое и программное обеспечепие вычислительных машин, комплексов, систем и сетей Диссертация кандидата технических наук. Московский энергетический институт (ТУ) М., 1997. 111.

89. Шамис Б.А. Бог1апс1 C++ Би11с1ег

90. Техника визуального программирования. М.: Нолидж, 2001. 155

91. Учебный курс. СПб.: Питер, 2002.

92. Шварц Дж. Дифференциальная геометрия и топология. Новокузнецк: ПФМИ, 2000.

93. Эдди Э. XML. Справочник. Наиболее полное руководство. СПб.: Питер, 1999.

94. Элиенс А. Принципы объектно-ориентированной разработки программ, М.: Вильяме, 2002.

95. Яблонский СВ. Введение

96. Arteca G.A., Mezey P.G., International Journal of Quantum Chemistry, 34, 1988, p. 517.

97. Cagle K., Cibbons D., Hunter D., Ozu N., Pinnock J., Cagle C. Beginning Xml. Chicago: Peer Information Inc., 2000.

98. Dykstra C.E. Ab Initio Calculation of the Structures and Properties of Molecules. Elsevier, Amsterdam, 1988.

99. Enderton H. B. Elements of set theory. Academic Press, New York, 1977.

100. Frolov A.В., Jako E. Algorithms for Recognition of Partially Ordered Objects and Their Application Scripta Technica, Wiley, 1991, pp. 122-148.

101. Frolov A.В., Jako E., Mezey P.C. Logical models of molecular shapes and their families Mathematical Chemistry, 30(4), 2001, pp. 389-409.

102. Frolov A.B., Jako E., Mezey P.C. Metric properties of factor space of molecular shapes Mathematical Chemistry, 30(4), 2001, pp. 411-428. 156

103. Hrbacek K., Jech T. Introduction to Set Theory, New York, Marcel Dekker Inc., 1999.

104. Kier L.B., Hall L.H. Molecular Connectivity in Chemistry and Drug Research. Academic Press, New York, 1976.

105. Lidl R., Pilz C. Applied Abstract Algebra. Springer Verlag, 1984. 112. McCluskey E.J. Logic Design Principles. Prentice Hall. Englewood Cliff, New Jersey, 1986.

106. Mezey P.G. Dimension concepts and redused dimensions in toxicological QShAR databases as tools for data quality assessment Journal of Mathematical Chemistry, 2001, p. 375-398.

107. Mezey P.G. Concepts and Applications of Molecular Similarity, ed. Jonson M.A. and Maggiora, Wiley, New York, 1990.

108. Mezey P.G. Functional groups in quantum chemistry Advances in Quantum Chemistry, №27, 1996, p. 163-222.

109. Mezey P.G. Potential Energy Hypersurfaces. Elsevier, Amsterdam, 1987.

110. Mezey P.G. Shape in Chemistry: An Introduction to Molecular Shape Topology, John Wiley к Sons, New York, 1993.

111. Munkres J.R. Elementary differential topology. Princeton: Princeton Univ. Press, 1983. 157

112. Pavlidis Т., АИ F., Computer recognition of hand written numerals by poligonal approximation IEEE Trans. Syst.,Man.Cybern., vol. SMC-5, 1975, pp. 161-178.

113. Persoon E., Fu K.S. Shape determination using Fourier descriptors. IEEE T. Syst. Man. Cyb. V7, 1977, pp. 36-57.

114. Pytev Yu.P. Morphological Image Analysis, Patt. Recogn. and Image Analysis, 1993, v.3, №1, pp.19-28.

115. Zadeh L.A. Fuzzy Logic and Approximate Reasoning, Sunthese, 1975. 158