авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Конечных объектов: концепция, методы и компьютерная реализация

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

КАЛЯДИН НИКОЛАЙ ИВАНОВИЧ

УДК 519.712 + 510.25 + 510.67

КОНСТРУКТИВИЗАЦИЯ МОДЕЛЕЙ

КЛАССИФИКАЦИИ КОНЕЧНЫХ ОБЪЕКТОВ:

КОНЦЕПЦИЯ, МЕТОДЫ И КОМПЬЮТЕРНАЯ

РЕАЛИЗАЦИЯ

05.13.18 Математическое моделирование, численные

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

АВТОРЕФЕРАТ

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

доктора физико-математических наук

Екатеринбург 2013

Работа выполнена на кафедре Прикладная математика и ин форматика ФГБОУ ВПО Ижевский государственный технический университет имени М.Т. Калашникова (ИжГТУ имени М.Т. Калаш никова)

Официальные оппоненты:

Бельтюков Анатолий Петрович, доктор физико-математических наук, профессор, ФГБОУ ВПО Удмуртский государственный уни верситет, заведующий кафедрой Теоретические основы информа тики ;

Дикусар Василий Васильевич, доктор физико-математических наук, профессор, ФГБУН Вычислительный центр им. А.А. Дород ницына Российской академии наук, ведущий научный сотрудник сектора методов оптимизации;

Мазуров Владимир Данилович, доктор физико-математических наук, профессор, ФГАОУ ВПО Уральский федеральный универси тет имени первого Президента России Б.Н.Ельцина, профессор ка федры Эконометрика и статистика.

Ведущая организация: ФГБУН Институт механики УрО РАН, г. Ижевск

Защита состоится 26 июня 2013 г. в 13 часов на заседании дис сертационного совета Д 212.285.25 на базе ФГАОУ ВПО Ураль ский федеральный университет имени первого Президента России Б.Н.Ельцина по адресу: 620000, г. Екатеринбург, пр. Ленина, 51, зал заседаний диссертационных советов, комн. 248.

С диссертацией можно ознакомиться в библиотеке ФГАОУ ВПО Уральский федеральный университет имени первого Президента России Б.Н.Ельцина.

Автореферат разослан................................. 2013 г.

Ученый секретарь диссертационного совета доктор физико-математических наук, Пименов В.Г.

профессор

Общая характеристика работы

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

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

В основе современных наиболее развитых подходов в распознава нии образов, таких как статистические методы3, комитетные кон струкции4 5, распознавание по прецедентам6 7, нейронные сети лежит предположение о выполнении гипотезы компактности9 10 :

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

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

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

4 Мазуров В.Д. Метод комитетов в задачах оптимизации и классификации.

М.: Наука, 1990. 248 с.

5 Mazurov Vl.D., Khachay M.Yu., Rubin A.I. Committee Constructions for Solving Problems of Selection, Diagnostics and Predication. // Proceedings of the Steklov Institute of mathematics. Suppl.1, 2002. Pp. 67–101.

6 Журавлев Ю.И. Корректные алгебры над множеством некорректных (эври стических) алгоритмов // Кибернетика. Ч. 1, 1977. № 4. С. 5–17;

Ч. 2, 1977. № 6. С. 17–24;

Ч. 3, 1978. № 2. С. 35–43.

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

С. 5–68.

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

9 Белозерский Л.А. Современный взгляд на гипотезу компактности // Искус ственный интеллект. Донецк, 2005. № 3. С. 6–12.

10 Гуров С.И., Потепалов Д.Н., Фатхутдинов И.Н. Решение задач распознава...образам соответствуют компактные множества в пространстве вы бранных свойств.

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

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

Проблемами разрешимости и вычислимости различных конкрет ных теорий фундаментальных наук занимались многие зарубежные и отечественные математики: Barwise D., Bernaus P., Blum M., Co hen P.L., Chang C.C., Church A., Cutland N., Enderton H., Feferman S., Godel K., Goodstein R.L., Hilbert D., Jensen R., Keisler H.J., Kleene S.C., Lachlan A.H., Macintyre A., Post E., Robinson D., Rogers H., Sacks G., Scott D.S., Shelah S., Shoeneld J.R., Sikorski A., Tarski A., Turing A., Penrose R., Van der Waerden B.L. и другие;



Адян С.И., Барздинь Я.М., Бельтюков А.П., Гончаров С.С., Ер шов Ю.Л., Журавлев Ю.И., Заславский И.Д., Колмогоров А.Н., Куш нер Б.А., Мазуров Вл.Д., Мальцев А.И., Марков А.А., Маслов С.Ю., Матиясевич Ю.В., Минц Г.Е., Нагорный Н.М., Новиков П.С., Орев ков В.П., Палютин Е.А., Перетятькин М.Г., Тайманов А.Д., Трах тенброт Б.А., Успенский В.А., Цейтлин Г.С., Шанин Н.А., Шрей дер Ю.А., Яблонский С.В., Якубович С.М. и многие другие.

Фундаментальные результаты о разрешимости и вычислимости в конструктивных моделях для теорий получены научной школой ака демика РАН Ю.Л. Ершова11, но в распознавании образов подобных работ достаточно мало.

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

1. Предложенная в начале 70-х гг. прошлого века Вл.Д. Мазуро ния с невыполненной гипотезой компактности // Всеросс. конф. ММРО-13.

М.: МАКС Пресс, 2007. С. 27–29.

11 Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М.: На ука, 1980. 416 с.

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

Вл.Д. Мазуровым и его учениками М.Ю. Хачаем, А.И. Рыбиным, А.И. Кривоноговым, Ю.А. Зуевым, Н.Г. Белецким сформулированы и доказаны теоремы существования комитетных решений для раз личных систем ограничений. М.Ю. Хачай12 всесторонне исследовал вопросы вычислительной сложности задач о минимальном комитете.

2. Академиком РАН Ю.И. Журавлевым введены основопологаю щие понятия (разрешимость, регулярность, полнота) в некоррект ных (эвристических) информационных моделях, позволяющие син тезировать прямыми методами корректные, т.е. точные на преце дентах, алгоритмы классификации.

Задача разрешима, если существует ее решение;

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

Представителями научной школы Ю.И. Журавлева в дальней шем более детально исследованы введенные им понятия. Выполнен ный К.В. Рудаковым13 углубленный анализ ограничений для задач классификации расширил область их применений за счет привлече ния морфизмов категорий.

А.А. Черепнин14 рассмотрел класс задач с различными оценками радиусов разрешимости и регулярности.

Ю.В. Чехович15 получил критерии локальной разрешимости и локальной регулярности в задачах выделения трендов.

А.С. Вальков16 предложил критерии разрешимости и регулярно 12 Хачай М.Ю. О вычислительной сложности задачи о минимальном комитете и смежных задач // Доклады РАН. 2006. Т. 406, № 6. С. 742–745.

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

М.: Наука, 1989. Вып. 1. С. 176–201.

14 Черепнин А.А. О радиусах разрешимости и регулярности задач распознава ния // Всеросс. конф. ММРО-11. М.: Регион-Холдинг, 2003. С. 210–211.

15 Чехович Ю.В. Мощности окрестностей в задачах выделения трендов // Все росс. конф. ММРО-11. М.: Регион-Холдинг, 2003. С. 215–216.

16 Вальков А.С. Задачи распознавания с отношением соседства на объектах.

Критерии разрешимости и регулярности // Всеросс. конф. ММРО-10. М.:

сти в задачах распознавания с отношением соседства на объектах.

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

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

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

– проблема разрешимости моделей классификации конечных объ ектов (в дальнейшем просто проблема разрешимости) состоит в следующем: существует ли алгоритм, который по описанию на язы ке расширенного исчисления предикатов устанавливает принадлеж ность исследуемого объекта к рассматриваемому множеству M или k к одному из классов разбиения S {M1, M2,..., Mk }, M = Mi ;

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

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

Методы исследования. В работе использовались методы тео АЛЕВ-В, 2001. С. 17–20.

17 Горелов Ю.И. О разрешимости и регулярности задач управления, решае мых в рамках теории распознавания образов // Всеросс. конф. ММРО-10. М.:

АЛЕВ-В, 2001. С. 33–34.

рии множеств, математической логики и теории алгоритмов;

теории моделей и теории нумераций;

спектральной теории сигналов, теории распознавания образов;

математического моделирования, численных методов, теории вероятностей и математической статистики;

теории графов, теории принятия решений;

методы конструктивной и дис кретной математики;

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

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

Научная новизна. Отметим элементы новизны результатов дис сертации, выносимые на защиту.

1. Разработан на единой методологической основе теоретико-мо дельный подход к проблеме классификации, позволивший получить новые критерии (не)разрешимости моделей классификации конеч ных объектов.

2. Исследованы вопросы представимости и вычислимости описа ния конечных объектов с целью оптимизации вычислительных за трат при компьютерной реализации алгоритмов классификации:

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

– найдены впервые необходимые и достаточные условия суще ствования предельно быстрой (симультанной) модели классифика ции;

– получены новые методы сокращения времени классификации в моделях, допускающих распараллеливание;

– рассмотрены быстрые спектральные преобразования Адамара – Уолша.

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

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

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

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

Практическая ценность работы.

I. В области обработки текстурных изображений.

Разработанный под научным руководством автора диссертации аппаратно-программный комплекс АРМ-Д для дешифрирования аэрокосмических снимков нашел практическое применение в техно логиях двойного назначения, где носителями информации яв ляются текстурные изображения: в авиации (аэроснимки тестовых трасс полета), медицине (рентгеновские снимки, материалы цито-, гистологических и эндоскопических исследований), технике (метал ловедение шлифы металлов, сварных швов), экологии (аэроснимки зон экологического загрязнения).

Опытные образцы комплекса АРМ-Д и комплекса АМК (автома тизированное изготовление издательских оригиналов тематических карт) внедрены в ПГО Гидроспецгеология Мингео СССР (г. Москва, 1988 г.), Госцентре Природа (г. Москва, 1990 г.).

Методика обработки текстурных изображений на комплексе АРМ Д использована при интерпретации результатов машинного анализа аэроснимков (ОКБ Интеграл при ЛГУ, г. Ленинград, 1988 г.), для компьютерной диагностики заболеваний костей (остеопороз) челове ка (Курганское НИИ экспериментальной и клинической ортопедии (г. Курган, 1988 г.), Маммологический центр Удмуртии (г. Ижевск, 1995 г.));

компьютерной диагностики онкопатологий человека (Рес публиканский онкологический диспансер (г. Ижевск, 1994–1999 гг.).

II. В компьютеризации медицинских технологий.

Разработан и внедрен комплекс алгоритмов и программ по ком пьютерному анализу и прогнозированию (1940–2020 гг.) заболева ний населения Удмуртии (онкологических, психических, инфекци онных).

Разработаны, испытаны и внедрены первые в России отечествен ные мониторно-компьютерные системы для медицинских учрежде ний г. Ижевска (медсанчасть №7, 1992 г.;

1я Республиканская клини ческая больница, 1994 г.;

Республиканский клинический кардиологи ческий диспансер, 1999 г.).

В работе представлены акты внедрения от Уральского регио нального отделения Академии медико-технических наук Российской Федерации, ОАО Ижевский Мотозавод Аксион-Холдинг, ФГУП Ижевский механический завод, ОАО Ижевский электромехани ческий завод Купол.

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

Научно-технические конференции Ижевского механического ин ститута (Ижевск, 1975–1991);

Всесоюзный симпозиум Машинные методы обнаружения закономерностей (Новосибирск, 1976);

IV Все союзная конференция Автоматизация ввода письменных знаков в ЦВМ (Каунас, 1977);

VII Всесоюзная конференция Теория коди рования и передачи информации (Москва, 1978);

I, IV Всесоюз ная конференция Методы и средства обработки сложнострукту рированной семантически насыщенной графической информации (Горький, 1983;





Нижний Новгород, 1998);

Всесоюзная конференция Обработка изображений и дистанционные исследования (Новоси бирск, 1984);

VIII Всесоюзная конференция Автоматизация в те матической картографии (Москва, 1984);

VI Всесоюзное совеща ние Проблемы автоматизации анализа изображений микрострук тур (Пущино, 1984);

2е Всесоюзное совещание Космическая ан тропология: техника и методы исследования (Ленинград, 1984);

II, III Всесоюзная конференция Математические методы распознава ния образов (Рига, 1987, 1989);

IX научные чтения по космонавти ке (Москва, 1988);

Международная конференция ОИДИ-90 (Новоси бирск, 1990);

1я Всесоюзная конференция РОАИ-1-91 Распознава ние образов и анализ изображений (Минск, 1991);

II Международ ная конференция Математические алгоритмы (Нижний Новгород, 1995);

Международная конференция Математическое моделирова ние в науке и технике (Ижевск, ИПМ УрО РАН, 1995 г.);

III Все российская конференция РОАИ Распознавание образов и анализ изображений: новые информационные технологии (Нижний Новго род, 1997);

научно-технические конференции ИжГТУ (Ижевск, 1991– 2004);

VI Всероссийская с участием стран СНГ конференция Мето ды и средства обработки сложной графической информации (Ниж ний Новгород, 2001);

научная конференция-семинар Теория управ ления и математическое моделирование (Ижевск, 2006);

Междуна родная конференция Теория управления и математическое модели рование, посвященная памяти д. ф.-м. н., проф. Азбелева Н.В., орга низатора Ижевского математического семинара (Ижевск, 8.05.2008);

научный семинар ИММ УрО РАН (г. Екатеринбург, 16.10.2009).

Работа поддержана грантами РФФИ (03-01-00255, 04-01-96016, 06 01-0074).

Прикладные результаты отражены в отчетах о НИОКР, выпол ненных под руководством автора в рамках государственных, отрас левых и целевых научно-технических программ.

Публикации и личный вклад автора. Основные результаты диссертации опубликованы в 44 работах, из которых 28 в рецензи руемых журналах и изданиях, определенных ВАК. Список публика ций приведен в конце автореферата. Из совместных работ в диссер тацию вошли результаты, полученные лично автором.

Структура и объем работы. Диссертация состоит из введения, четырех глав, объединяющих 20 параграфов, заключения, приложе ния и списка литературы из 263 наименований. В работу включены 47 рисунков, 7 таблиц и акты о внедрении результатов работы. Об щий объем работы 339 страниц.

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

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

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

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

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

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

Пусть M исходное множество классифицируемых (распознава емых) образов x произвольной природы;

K множество конструк тивных (конечных) объектов;

: M K функция кодирования классифицируемых (распознаваемых) образов x конечным множе ством из K.

обучающая выборка семейство мно O {X1, X2,..., Xm } жеств Xi, i Im {1, 2,..., m}, то есть набор известных реализаций (описаний) Xi классифицируемых (распознаваемых) образов x.

X неизвестная реализация классифицируемого (распознаваемо го) образа x.

S {N1, N2,..., Nt } разбиение обучающей выборки на классы (эталоны) Nj, j It {1, 2,..., t};

Ni Nj = для i = j.

классифицирующая функция, закрепляющая но f : Im It мера i Im элементов обучающей выборки Xi O за номерами эталонов классов Nj S, j It.

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

1. Распознавание:

если X (Mi ) K, 1, (x M )(X K)X (Mi ) = в противном случае.

0, 2. Идентификация:

если X = Xi, i Im, 1, (X O)X = Xi = в противном случае.

0, 3. Классификация:

если X Nj, j It, 1, (X O)X Nj = в противном случае.

0, 18 Минский М., Пейперт С. Персептроны. М.: Мир, 1971. 261 с.

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

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

О п р е д е л е н и е 1.19 Пара R (M, TD+ ) называется вход ным пространством распознающей системы, если выполняются сле дующие аксиомы:

+ x t y (существование толерантности), (A1 ) x,yM t D M t (рефлексивность), M = { (x, x)| x M }, (A2 ) t D+ t = t1 (симметричность), (A3 ) t D+ s) (t s ) (упорядоченность), (A4 ) (t t,sD+ (квазиаддитивность), (A5 ) t s t+s t,sD+ где TD+ класс отношений толерантности (сходства) на множестве M, индексированный множеством неотрицательных вещественных чисел D+, то есть TD+ = { t }tD+.

Пусть заданы дополнительно:

µ мера на множестве M из входного пространства R;

множество некоторых элементарных предикатов на множе P стве M ;

V {M1, M2,..., Mm }, Mi M, i = 1, m, причем каждый класс (образ) Mi описывается некоторой логической комбинацией элемен тарных предикатов pj (x) P : Mi = { x M | Li [p1 (x),..., pki (x)]}, где Li – некоторая пропозициональная функция, j = 1, ki.

О п р е д е л е н и е 2. Набор (R, P, V, µ) называется логиче ской моделью распознавания, если выполняются следующие аксио мы:

19 В автореферате принята независимая от текста диссертации система нуме рации соотношений и утверждений (связность), (K1 ) x y x z D+ xMi yMi zMi xt y (ограниченность), (K2 ) tD+ x,yMi µ(Mi ) = t, (t 0) (объемность), (K3 ) tD+ 1) (отделимость).

µ (Min ) = µ (Mi \Min ), ( (K4 ) µ О п р е д е л е н и е 3. Модель распознавания (R, P, V, µ) на зывается спектрально-логической, если:

1) M = Dm, где Dm m-я декартова степень множества веще ственных чисел;

2) µ есть лебеговская мера в m-мерном пространстве Dm ;

3)TD+ класс отношений толерантности, элементы которого опре делены с помощью евклидовой метрики на M :

m (xi yi ) xt y t.

i= В спектрально-логической модели описание любого объекта рас познавания x M может быть произведено с помощью упорядо ченного набора числовых коэффициентов, определяющего некото рую точку в пространстве Dm. Такие наборы чисел и есть спектры в самом широком понимании этого термина (Трахтман А.М.).

В рамках спектрально-логического подхода осуществляется по иск критериев разрешимости и вычислимости моделей классифика ции конечных объектов. С этой целью исходное множество объек тов из M редуцируется к множеству всех натуральных чисел N {0, 1, 2,... } через отображение : M N. Пара M, объяв ляется множеством конструктивных (конечных) объектов, если при этом взаимно однозначное отображение, то пара M, называ ется множеством сильно конструктивных объектов.

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

Пусть M (M ), M Ф семейство всех конечных подмно жеств множества N {0, 1, 2,... };

S {Ni }iI разбиение семей ства M, где I не более чем счетное индексное множество;

: N стандартная нумерация.

Рассмотрим модель M;

S с основным множеством M и сигна турой S Pi iI, где предикаты Pi (X) будем интерпретировать следующим образом: (X M) [Pi (X) = 1 X Ni ].

Вопрос о разрешимости предиката Pi (X) назовем проблемой рас познавания для класса Ni. Учитывая, что Pi (X) = 1Ai ( 1 (X)), где Ai характеристическая функция множества Ai 1 (Ni ), то в силу тезиса Чёрча справедливо П р е д л о ж е н и е 1 (критерий разрешимости 1). Пробле ма распознавания для класса Ni конечных множеств разрешима то гда и только тогда, когда Ni сильно рекурсивно.

Вопрос о существовании алгоритма, позволяющего указать номер i класса Ni S, для которого Pi (X) = 1, где X Ф, назовем пробле мой классификации для разбиения S {Ni }iI семейства M Ф.

П р е д л о ж е н и е 2 (критерий разрешимости 2). Пробле ма классификации для разбиения S {Ni }iI семейства M разре шима тогда и только тогда, когда I конечно и для всякого i I [Ni сильно рекурсивно].

Отношение m (m-сводимости) позволяет расширить критерий разрешимости (предложение 2) для различных конечных объектов (множеств, кортежей, отношений) в виде С л е д с т в и е 1. Если проблема классификации для разби ения S {N1,..., Nr } семейства M разрешима, B {A1, A2,..., Ar } такое разбиение семейства L, что для любого i r N [ 1 (Ai ) прообраз стандартной нумерации элементов разбиения B m-сводит ся к прообразу 1 (Ni ) стандартной нумерации элементов разбие ния S, то есть 1 (Ai ) m 1 (Ni )], то проблема классификации для разбиения В семейства L разрешима.

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

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

Более общим условием однозначного принятия решений является требование попарного непересечения множеств (Mi ) и (Mj ) (i = = j Im ) для исходного разбиения множества M.

О п р е д е л е н и е 4.20 Семейство 0 конечных мно жеств называется сильно перечислимым (сильно рекурсивным), если множество 1 (0 ) рекурсивно перечислимо (рекурсивно).

Вводя 0 как сильно перечислимое (сильно рекурсивное) множество в сужении : M, = для стандартной нумера ции : N, получим П р е д л о ж е н и е 4 (критерий неразрешимости 2). Пусть (M ) сильно перечислимо, но не сильно рекурсивно. Тогда для лю бого конечного разбиения R множества M проблема классификации для тройки M, R, не является разрешимой.

В силу однозначности и вычислимости нумерация сводит про блему классификации для тройки M, R, к уже известной пробле ме классификации для тройки M, R, :

П р е д л о ж е н и е 5. (критерий разрешимости для M, R, ). Проблема классификации для тройки M, R, разреши ма тогда и только тогда, когда (Mi R) [(Mi ) сильно рекурсивно].

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

Сформулированы (§3) условия однозначной разрешимости (суще ствования и единственности решений) для моделей классификации, допускающих распараллеливание в известных решающих правилах:

моделей Вальда, Лапласа, Сэвиджа, Евклида, коллективного голо сования и сильного голосования.

20 Ершов Ю.Л. Теория нумераций. –М.: Наука, 1977.– 416с.

Вторая глава (§§5–11) посвящена проблеме вычислимости раз решимых моделей классификации конечных множеств;

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

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

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

Т е о р е м а 1 (о существовании информативных элементов).

Пусть (i Il ) [Xi = ] и (i = j Il ) [qij = 1 qji = 0]. Тогда су ществует l информативных элементов ai Vil+1 таких, что пре дикат классификации i (X) = ai X & ¬ aj X & qij jIl \{i} обращается в единицу тогда и только тогда, когда X = Xi, где X O0, Vij+1 - индексные множества, получаемые по рекуррентной схеме:

Vij \Xj, если Vij \Xj = ;

i, j = 1, l, Vij+1 = Vij, в противном случае.

элементы вспомогательной логической матрицы q = qij :

0, если Vij \Xj = ;

qij = 1, в противном случае.

С л е д с т в и е 2. Пусть O = uij таково, что (i Il ) [Xi = ] и (i Il ) Xi \ Xj =. Тогда существует l ин jIl \{i} формативных элементов ai Vil+1 таких, что предикат Mi () = x 1, если ai = xj ;

= где x = x1,..., xn O, и индекс j вы 0, в противном случае, бран из условия cj cj xj cj + cj, обращается в единицу тогда и только тогда, когда x = ui O.

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

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

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

С каждым разбиением S {N1,..., Nr } семейства M связана мо дель M;

S с основным множеством M и сигнатурой S P1,..., Pr.

Одноместные предикаты классификации Pi на модели M;

S ин терпретируются так: (X M) Pi (X) = 1 X Ni, i = 1, r.

Ставится следующая задача минимизации предикатов классифи кации: для любого разбиения S {N1,..., Nr }, (i = 1, r) семей ства M найти r минимальных (по числу элементов) подмножеств Ei O(M) для вычисления предикатов Pi (X) модели M;

S с помо щью подмножеств Ei (системы подмножеств).

Через S обозначим класс всех разбиений S элементов из R.

П р е д л о ж е н и е 6. Для любого разбиения S S2 и для любого i Im, где m номер разбиения S, если [qij = 1 qji = 0], то Pi (X) = Ri (X) &¬ Rk (X) &qik, kIm \{i} 1, если Ei O (1 (i)) =, i, j Im ;

qij = где 0, в противном случае, O(1 (i)) объединение образов гёделевой нумерации 1.

Задача классификации для разбиений S из семейства M эффек тивно решается путем построения процедур для вычисления преди катов моделей O (S) ;

S, соответствующих разбиению S, посред ством выявления минимальных подмножеств Ei, i = 1, r, где r = = |S|.

Интерпретация критериев разрешимости для типовых игровых решающих правил позволила построить общую схему принятия ре шений M M ;

O;

f, i, повышающую (за счет распараллелива ния) вычислительную эффективность и в целом надежность класси фикации объектов: общее решение Rk () = Qi (), где мно x x iDk жество номеров эталонных объектов Dk = {i|f (i) = k}, k = = 1, t;

некоторая реализация объекта x = x1,..., xn M ;

сигна тура i = Qi1, Qi2,..., Qit из t одноместных частных решающих предикатов 1, если c(i, x) = c0 ;

u Qi () = x 0, в противном случае, где c0 = max(min){c(1, x),..., c(, x)}, c(i, x) некоторый функ u u u ционал, выражающий меру близости (сходства) между эталонами обучающей выборки ui O = ||uij ||n, число эталонов, n число признаков;

ui = ui1, ui2,..., uin, i = 1, и неизвестной реали зации x = x1,..., xn, j = 1, n.

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

Языком, удовлетворяющим критериям представимости и вычис лимости, располагает система B = Bn ;

&,, ¬;

0, 1, образующая ал гебру булевых функций (или функций алгебры логики ФАЛ) f (n ), x xn = x1, x2,..., xn, xi {0, 1}, i = 1, n;

Bn = {f |f : {0, 1}n {0, 1}}.

правильно построенная формула (ппф), полученная су F (n ) x перпозицией элементарных ФАЛ q L = {, &,,,,, /,, } из класса P2 или переименованием переменных xi xn и скобок (, ).

Другим преимуществом языка ФАЛ является возможность эф фективных вычислений (распознавания) образа f (n ) по его описа x нию ппф F (n ), то есть алгоритма A: F (n ) f (n ).

x x x Т е о р е м а 2. Для реализации алгоритма A: F (n ) f (n ) x x необходимо и достаточно вычислить ядро Ki и построить рекур сивный процесс вычисления Ki : F (n ) F 1 (n )... F 0 (n ).

r x x x Через шагов процесс заканчивается получением b.

F 0 (n ). = f (n ), где bj {0, 1}, j = 1, 2n.

x x.

b2n Для уменьшения объема памяти вычислителя (количество од новременно хранимых промежуточных результатов) потребуем вы полнения на каждом шаге условия обеспечения эффективности ал использование логических связей в исходной формуле горитма r+ F (n ) согласно следующему правилу: если {Ki } O1, {Kb } r x pj r pj r+ O2 и существует такая операция qj, что имеет место {Ki }qj {Kb }, pj то {(O1 )qj (O2 )} O1. Критерий эффективности минимальный объем памяти при реализации алгоритма A: F (n ) f (n ).

x x Рис. 1. Виды элементарных (базовых) спектров:

а) монотонно убывающий;

б) монотонно возрастающий;

в) постоянный;

г) осциллирующий.

Интерпретация ппф F (n ) как описания некоторого образа f (n ) x x в пространстве бинарных признаков xi xn, i = 1, n позволяет обнаружить закономерности (упорядоченность) в отображении :

p p F (n ) S(qi j ), где S(qi j ) G {1, 2,..., j} {p1, p2,..., pj }, j N x номер операции qj L\ в ппф F (n ), pj N порядок (ранг) x операции gj L\ в ппф F (n ). x p S(qi j ) спектр структурных связей взвешенных бинарных опе p раций qi j между признаками xi xn образа f (n ). Этот спектр есть x дискретный или линейчатый.

G график зависимости величины порядка pj операции qj от ее связи и расположения ( глубины погружения ) в ппф F (n ).x p Отметим ряд полезных свойств спектра S(qi j ).

p Л е м м а 1. Спектр S (qj j ) может содержать только осцил лирующие, монотонно возрастающие (убывающие) или постоянные участки (рис.1.).

Т е о р е м а 3. Для одной и той же формулы F (n ) можно x pj построить один и только один спектр S (qj ), то есть инъектив p ное отображение : F (n ) S (qj j ).

x Для построения эффективного алгоритма A: F (n ) fk (n ) x x необходимо указать правило выбора такого 1-го шага, который обес печивал бы запоминание минимального количества промежуточных результатов при вычислении формулы F (n ).

x Т е о р е м а 4 (метод сечений). Для отыскания 1-го (началь ного) шага эффективного алгоритма A: F (n ) fk (n ) необходимо x x и достаточно:

p 1) построить отображение : F (n ) S (qj j );

x pj 2) провести сечение спектра S (qj ) по минимальному локально му минимуму;

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

3) в выбранной части снова произвести сечение по правилам п.

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

Операции qj L\ в исходной F (n ), соответствующие их ло x кальным максимумам, являются ядрами 0-го ранга.

Т е о р е м а 5. Для построения эффективного алгоритма A:

F (n ) fk (n ) необходимо и достаточно по методу сечений вы x x брать 1-й шаг и, выдерживая на каждом шаге условие эффективно сти, вычислить ядра, соответствующие локальным минимумам, в p порядке, обратном сечениям спектра S (qj j ).

: ( j ).

Рис. 2. Выбор 1-го шага для получения эффективного алгоритма A: F (n x Теоремы 4, 5, исключая эвристику при построении эффективно го алгоритма A: F (n ) fk (n ), указывают пути автоматизации x x вычислений булевой функции fk (n ).

x Оценки сложности вычислений булевых функций.

В качестве меры сложности [F (n )] вычисления fk (n ) введены x x два типа сигнализирующих функций:

1) функции, связанные с длительностью вычислений fk (n ) :

x 1 t [F (n )] x 2, где 2 = верхняя оценка, длина формулы F (n ), 1 = t + x + t t+ нижняя оценка, 2 2;

2) функции, связанные с объемом промежуточной памяти:

+ 1 = 2 0 [F (n )] x 2 =.

В третьей главе (§§12–16) рассматривается реализация концеп ции конструктивизации при классификации (распознавании) конеч ных объектов, представителями которых являются одномерные или двумерные сигналы от различных изображений.

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

, где M {a1, a2,..., am }, R1, R2,..., Rn, необходимо, в первую очередь, через предикаты Радемахера представить точечные предикаты P1, P2,..., Pm, где 1, если x = ai ;

i = 1, m ;

Pi (x) = 0, в противном случае.

Т е о р е м а 6. Для любого k Im {1, 2,..., m}, m N точечные предикаты Pk (x) представимы через предикаты Ра k демахера Ri (x) :

k k k Pk (x) = R1 (x)&R2 (x)&...&Rn (x), Ri (x), если [(k 1)]ni+1 = 0;

k где Ri (x) = ¬Ri (x), в противном случае, n = 2n /m;

[·] 2i1 [ · (k 1)]i ;

целая часть числа, [ · (k 1)] = i= [ · (k 1)]i {0, 1} ;

n = µy(2y m), µ оператор минимизации, (i = 1, n;

k = 1, m).

Доказано, что любой предикат Q(x1,..., xk ) на M можно разло жить по предикатам Радемахера, допускающим простую аппаратную реализацию двоичными n разрядными регистрами Pr (n).

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

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

Проблема простейшего представления предикатных форм для сигнатуры сводится к выбору базиса и наиболее экономичного представления предикатов в этом базисе (§14).

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

Примеры реализации этапов конструктивизации.

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

Представление текстурных изображений (§15).

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

Пусть имеется множество текстурных изображений T с отобра жением : T F в пространство дискретных изображений F, где в качестве дискретных взяты изображения Xi = { x, y, f (x, y) | x, y M 2, f (x, y) : M 2 M }.

В пространстве наблюдений F вводится обучающая выборка O = = (X1 ), (X2 ),..., (X ) такая, что (X1 ) = X1,..., (X ) = X, и задается классифицирующая функция q : I It, t число классов;

I {1, 2,..., }, It {1, 2,..., t}.

На множестве F введем бинарную операцию с помощью полу суммы:

X1 X2 = { x, y, [f1 (x, y) + f2 (x, y)]/2 }, где изображения X1 = { x, y, f1 (x, y) };

X2 = { x, y, f2 (x, y) }, [·] целая часть числа, чтобы получить алгебру изображений F ;

.С помощью бинарной операции и множеств Ak = {fi (x, y)|i Dk }, где Dk = {i|g (i) = k}, (k = 1, t), порождаются отношения-образы Fk в модели M = F ;

F1,..., Ft.

Построенная модель M адекватна исходной модели Q = T ;

T1,..., Tt с основным множеством T и некоторыми априорно заданными классами Ti T, (i = 1, t). Адекватность достигается тем, что опера ция отражает компактность, имеющую место между текстурами одного класса.

Представление точечных изображений предикатами Ра демахера.

Точечные изображения примем в виде функции f (x, y) двух пе ременных с областью определения Df = x, y x, y = 1, 2,..., 2n, областью изменения f {1, 2,..., 2n} для некоторого n N {0, 1, 2,...}. Для функции f (x, y) можно взаимно однозначно сопо ставить отношение F следующего вида: F = { x, y, f (x, y) | x, y Df }, которое необходимо представить в базисе предикатов Раде махера.

Пусть F = { x, y, f (x, y) | x, y Df } = { i11, i12, i13,..., i1, i2, i3 }.

Соответствующий этому отношению предикат 1, если x1, x2, x3 F ;

P (x1, x2, x3 ) = 0, в противном случае, можно записать в виде дизъюнктивного разложения по единич ным значениям предиката P (x1, x2, x3 ) на кортежах i1, i2, i3 :

P (x1, x2, x3 ) = Pi11,i12,i13 (x1, x2, x3 )... Pi1,i2,i3 (x1, x2, x3 ), где Pij1,ij2,ij3 (x1, x2, x3 ) = Pij1 (x1 ) &Pij2 (x2 ) &Pij3 (x3 ), j = 1,.

Подставляя в последнем выражении вместо Pijk (xk ) ij ij ij Pijk (xk ) = R1 k (xk ) &R2 k (xk ) &...&Rn k (xk ), Rp (xk ), если (n p + 1) разряд двоичного разложения числа q 1 равен 0;

где Rp (xk ) = q ¬Rp (xk ), в противном случае, (k =1, 2, 3) получаем требуемое разложение отношения по предикатам Радема хера.

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

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

Минимальное разбиение растрового изображения.

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

О п р е д е л е н и е 5. Классом базисных прямоугольников назовем множество прямоугольников { (x, y)} со сторонами x, y N \0, удовлетворяющих условию (i, j N \0) (k N \0) [ (xi, yi ) (xj, yj ) = (xk, yk )].

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

О п р е д е л е н и е 6. Геометрическим спектром (ГС) изоб ражения A относительно класса базисных прямоугольников назо вем график S (A) { k (c (x, y)), c (x, y) }, где c (x, y) канторовская нумерация пар x, y базисных прямо угольников (x, y), а соответствующая k-я гармоника геометриче ского спектра есть натуральное число k (c (x, y)) = |{g (tx, ty ) |g (tx, ty ) (x, y) A }|.

О п р е д е л е н и е 7. Структурным графиком изображе ния A, образованного из базисных прямоугольников класса с помо щью преобразований из группы G = {g (tx, ty )}, преобразований g (tx, ty ), назовем график GG, (A) { c(tx, ty ), c(x, y) |a(n, m) = g(tx, ty )( x, y) A}, где c (tx, ty ) = n, c (x, y) = m есть соответственно канторовские номе ра пар tx, ty, x, y ;

a (n, m) прямоугольный элемент изображе ния A, операция композиции преобразований.

P О п р е д е л е н и е 8. Полным подспектром S (A) = = { k (m), m } изображения A назовем подспектр изображения, удо влетворяющий условию:

r r r r r r D [a (n, m)] D [a (ni, mi ) a (nj, mj )] = ni =1 mi =1 nj =1 mj = n=1 m= = k (1), где i, j N, ni, mi = nj, mj ;

r число элементов подграфика структурного графика GG, (A) изображения A, соответствующего минимальному полному подспектру;

D [a (n, m)] = l (m) · r (m) есть площадь элемента a (n, m).

Т е о р е м а 7. Минимальное разбиение изображения A явля ется подграфиком его структурного графика GG, (A) = { n, m }, P соответствующим минимальному полному подспектру S (A) = = { k (m), m }.

Предложен алгоритм оптимизации, значительно (почти в 400 раз) сокращающий объем памяти при компьютерном анализе и синтезе растровых изображений. Новизна метода подтверждена авторским свидетельством [27].

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

1) задачу синтеза построить спектр c наперед заданными свой ствами, определяемыми некоторым модулятором;

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

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

Четвертая глава (§§17–20) содержит прикладные результаты по компьютерной классификации (распознаванию) наиболее динамич ных и трудных для исследований объектов:

текстурных изображений, функциональных состояний человека.

Компьютерная классификация текстур (§§17–18).

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

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

В системе картобеспечения рационального природопользования одно из ведущих мест принадлежит черно-белым интегральным кос мическим фотоснимкам (КФС) масштаба 1:180000–1:340000, обеспе чивающим оперативное получение достоверной информации о боль ших площадях земной поверхности.

Ввиду потенциальной неограниченности числа классов на КФС и слабой приспособленности зрительного анализатора человека для работы с малоразмерными, низкоконтрастными элементами (объек тами) на КФС надежность визуального дешифрирования КФС по всем классам объектов, к сожалению, не превосходит 35–40%, а по одному из самых распространенных и сложных классов расти тельным покровам и грунтам (РПиГ) 20–30%, что не обеспечивает полноту содержания многих тематических и топографических карт, составляемых (обновляемых) по КФС.

На основе выполненных теоретических исследований разработан 21 Кельманов А.В. Апостериорный подход к решению типовых задач анализа и распознавания числовых квазипериодических последовательностей: обзор ре зультатов // Всеросс. конф. ММРО–12. М.: МАКС Пресс, 2005. С. 125–128.

аппаратно-программный комплекс АРМ-Д для автоматизированного дешифрирования аэрокосмических фотоснимков при составлении и обновлении топографических и тематических карт [4, 5].

Для оценки качества работы комплекса АРМ-Д в производствен ных условиях проведены сопоставительные контрольные испытания:

рассмотрено 47 типов РПиГ на 39 КФС, в пределах которых выде лено 236 контуров, 528 фрагментов текстурных изображений РПиГ.

Надежность их дешифрирования составила в среднем 77,4 ±1,7%, в том числе для районов-аналогов 77,2±4,2%.

Универсальность комплекса АРМ-Д позволила применить его так же для решения широкого круга нетопографических задач фото грамметрии в медицине, технике, авиации, биологии, физике, эко логических исследованиях.

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

Компьютеризация медицинских технологий (§19).

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

В частности, выявленные при компьютерном анализе на рентге новских снимках скрытые дефекты (пустоты, каверны) в микроар хитектонике костной ткани объясняют этиологию и патогенез под час возникающего остеомиелита при сращивании костей человека с использованием аппарата и методики Илизарова Г.А. (Курганское НИИ экспериментальной и клинической ортопедии и травматологии, г. Курган, 1994 г.).

2. Выполненные с помощью пакета OSTEO исследования регу лярности трабекулярной структуры костной ткани на рентгеновских изображениях суставов женщин предоставили возможность обнару жить и проследить возрастную динамику онкопатологий (в 35 50 лет), связанных с уменьшением костной массы и изменени ями микроархитектоники костной ткани (Маммологический центр Удмуртии, г. Ижевск, 1995 г.).

3. Разработан компьютерный эндоскоп аппаратно-программный Рис. 3. Оценка состояния костной ткани пациента (компьютерная система OSTEO ) комплекс, сопряженный с эндоскопом под управлением единого про граммного обеспечения (система ЭНДО ).

Проведенные клинические испытания компьютерного эндоскопа (23 объекта эзофагоспии) в Республиканском онкологическом дис пансере Удмуртии (1995 г.) подтвердили экспериментально повыше ние качества эндоскопических исследований за счет исключения субъ ективных ошибок врача-эндоскописта и предоставляемой ему воз можности ведения диалога с компьютерной экспертной системой, на копленной базой знаний и базой данных при решении задач диагно стики, мониторинга и прогнозирования.

4. Проблема количественного и качественного анализа данных по онкологическим заболеваниям, стоящим на одном из первых мест по заболеваемости и смертности в ряду всех болезней, имеет большую Рис. 4. Исследование динамики эндоскопического объекта пациента (компьютерная система ЭНДО ) научную и общественную значимость. В работе описаны методы и приведены результаты, позволяющие на основе статистических дан ных прогнозировать показатели онкостатистики на различные пери оды, устанавливать факторы, влияющие на показатели заболеваемо сти, и связи между различными локализациями. Компьютерный ре троспективный анализ (1946–1990 гг.) онкопатологий населения Уд муртии позволил выполнить онкопрогноз на период 1990–2015 гг. (си стема ОНКО ).

5. Разработан и внедрен пакет прикладных программ для ком пьютерного анализа и прогнозирования:

– психических заболеваний населения Удмуртии в 1940–2016 гг.

Рис. 5. Компьютерный анализ и прогноз онкозаболеваний населения Удмуртии в 1946–2015 гг. (система ОНКО ) (система ПСИХ, 1992 г.);

– инфекционных заболеваний (клещевой энцефалит, лайм-борре лиоз) населения Удмуртии в 1976–2020 гг. (система Клещ, 1997 г.).

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

7. Разработанный комплекс алгоритмов и программ по монитори рованию основных физиологических параметров человека: электро кардиограмма (ЭКГ), артериальное давление (АД), пульсоксимет рия (SpO2 ), реография (РЕО), электроэнцефалограмма (ЭЭГ), тем пература (Т) реализован в различных моделях мониторно-компью терных систем, прошедших длительную опытную эксплуатацию в разнообразных клинических условиях (отделения реанимацион ные, операционные, неотложной кардиологии, палаты интенсивной терапии).

При научно-техническом руководстве и личном участии автора диссертации выполнены разработка и испытания компьютерных ме дицинских мониторов, комплексов и систем. В частности, – монитор компьютерный неонатальный МНК-01-НИОТК-Иж (рег. № 98/219, включен в государственный реестр медицинских из делий, разрешенных для применения в медицинской практике и к серийному производству, Минздрав РФ, М., 1999 г., доп. № 1–2).

Новизна и оригинальность технических решений подтверждены авторским свидетельством [28].

8. Разработаны, изготовлены и испытаны на ФГУП ИЭМЗ Ку пол (г. Ижевск, 2000 г.) мониторы компьютерные медицинские: мо нитор анестезиологический компьютерный (МАК-01), монитор ре анимационный компьютерный индивидуальный (МРКИ-01), реогра фический комплекс компьютерный (РКК-01);

мониторно-компьютер ная система реанимационная общего профиля (система МКС-ОНК А ).

Рис. 6. Модель монитора компьютерного неонатального МНК-01-НИОТК-Иж Заключение В работе впервые сформулирована и разработана концепция по этапной конструктивизации: разрешимость, вычислимость и реали зация моделей классификации конечных объектов, обеспечивающая оптимизацию вычислительных затрат при аппаратно-программной реализации алгоритмов классификации, что способствует совершен ствованию вычислительных технологий классификации конечных объектов и расширению практики проектирования аппаратно-про граммных классификаторов.

1. Разработан на единой методологической основе теоретико-мо дельный подход к проблеме классификации, позволивший получить новые критерии (не)разрешимости моделей классификации конеч ных объектов.

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

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

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

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

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

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

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

– распознавание текстур (дешифрирование КФС, диагностика остеопороза, онкопатологий);

– функциональных состояний человека (при медицинском мони торинге).

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

10. Разработан и внедрен комплекс алгоритмов и программ по компьютерному анализу и прогнозированию (1940–2020 гг.) заболе ваний населения Удмуртии (онкологических, психических, инфекци онных).

11. Результаты работы внедрены более чем в 10 организациях и предприятиях, используются в выполнении НИОКР и в учебном про цессе при чтении курса Дискретная математика в ИжГТУ имени М.Т. Калашникова.

Основное содержание диссертации отражено в следующих работах автора:

I. Статьи в рецензируемых научных журналах и издани ях, определенных ВАК 1. Калядин Н.И. Диагностическое значение пальцевой денсогра фии / Е.М. Гнедина, Э.Н. Ипатова, Н.И. Калядин, В.В. Певчих // Казанский медицинский журнал, Казань.: Изд-во ТАТОб, 1974.

№6. – С.24 – 25.

2. Калядин Н.И. Использование ЭВМ Мир-2 для визуального вывода полутоновых изображений / В.И. Заболотских, Н.И. Каля дин, В.Е. Кацман // Жур. Приборы и техника эксперимента.

М.: АН СССР, 1979. – №2. – С.90 – 92.

3. Калядин Н.И. О полноте алгебраического замыкания простран ства распознающих операторов с тестовыми опорными множествами / А.Г. Ицков, Н.И. Калядин // Журнал вычислительной математики и мат. физики. М.: АН СССР, 1984. – Т. 24. – №4. – С.579 – 586.

4. Калядин Н.И., Александров Ф.М., Липовецкий Ю.Л. и др. Ав томатизированное изготовление издательских оригиналов карт // Геодезия и картография. М.: Геоиздат, 1990. – №1. – С.36 – 38.

5. Калядин Н.И., Леменков В.А., Липовецкий Ю.Л. и др. Ком плекс автоматизированного дешифрирования крупномасштабных кос мических фотоснимков // Геодезия и картография. – М.: Геоиздат, 1991. – №8. – С.18 – 25.

6. Калядин Н.И. Единый методологический подход при алгорит мизации и построении экспертных систем типа норма-патология в медицине / Н.И. Калядин, В.А. Белоусов, С.В. Филатова // Меди цинская техника. – М.: Медицина, 1996. – № 3. – С.6 – 7.

7. Kalyadin N.I. A Simultaneous Apporach to Decision Making / V.A.

Belousov, N.I. Kalyadin // Pattern Recognition and Image Analysis.

1998. vol.8, no. 2, pp.106 – 107.

8. Kalyadin N.I. Problems of Recognition and Classication for Families of Subsets of Natural Numbers / V.A. Belousov, N.I. Kalyadin // Pattern Recognition and Image Analysis. 1998. vol.8, no.2, pp.108 – 109.

9. Kalyadin N.I. On the Problem of Classication of Sets of Natural Numbers / V.A. Belousov, N.I. Kalyadin // Pattern Recognition and Image Analysis. 1998. vol. 8, no. 2, pp. 157 – 159.

10. Kalyadin N.I. Computer Prediction of Infectious Disiases / N.I.

Kalyadin, M.D. Khodyreva, T.T. Sadykov, K.E. Shumilov // Pattern Recognition and Image Analysis. 1998. vol.8, no.2, pp.414 – 415.

11. Калядин Н.И. Нумерация конечных множеств для компьютер ной классификации // Вестник Московской академии рынка труда и информационных технологий. – 2004. – №3(11). – С.64 – 69.

12. Калядин Н.И. Временная оптимизация решающих правил клас сификации // Вестник Московской академи и рынка труда и инфор мационных технологий. – 2004. – №3(11). – С.70 – 76.

13. Калядин Н.И. Преобразование Адамара-Уолша для эффек тивных вычислений спектров // Вестник Московской академии рын ка труда и информационных технологий. – 2004. – №4(12). – С. 27 – 33.

14. Калядин Н.И. Симультанная классификация множеств конеч ных объектов // Вестник Московской академии рынка труда и ин формационных технологий. – 2004. – № 4(12). – С.34 – 40.

15. Калядин Н.И. Классификация сильно слипающихся множеств // Вестник Московской академии рынка труда и информационных технологий. – 2004. – № 4(12). – С.41 – 46.

16. Калядин Н.И. Конструктивизация в классификации образов // Вестник Удмуртского университета. Серия "Математика. Меха ника. Компьютерные науки". – Вып.2. – Ижевск: Изд-во УдГУ, 2008.

– С.188 – 193.

17. Калядин Н.И. Вычислимость в классификации образов // Вестник ИжГТУ. – Вып. 3(39). – Ижевск: Изд-во ИжГТУ, 2008. – С.127 – 129.

18. Калядин Н.И. Разрешимость в классификации образов // Вест ник ИжГТУ. – Вып.4(40). – Ижевск: Изд-во ИжГТУ, 2008. – С.169 – 172.

19. Калядин Н.И. Симультанность в классификации бинарной информации /Н.И. Калядин, В.А. Белоусов // Вестник ИжГТУ. – Вып.4(40). – Ижевск: Изд-во ИжГТУ, 2008. – С.172 – 174.

20. Калядин Н.И. Компьютерное моделирование спектров струк турных связей / Н.И.Калядин, Д.Н. Сандалов // Вестник ИжГТУ.

– Вып.2(42). – Ижевск: Изд-во ИжГТУ, 2009. – С.141 – 144.

21. Калядин Н.И. Конструктивизация в логико-алгебраических моделях // Вестник ИжГТУ. – Вып.2(42). – Ижевск: Изд-во ИжГТУ, 2009. – С. 144 – 147.

22. Калядин Н.И. Установление фрактальности в синтезирован ных спектрах / Н.И. Калядин, Д.Н. Сандалов // Вестник ИжГТУ.

– Вып.3(43). – Ижевск: Изд-во ИжГТУ, 2009. – С.127 – 129.

23. Калядин Н.И. Распознавание отношений методом коллектив ного голосования // Вестник Удмуртского университета. Серия "Ма тематика. Механика. Компьютерные науки". – Вып. 3. – Ижевск:

Изд-во УдГУ, 2011. – С.154 – 162.

24. Калядин Н.И. Моделирование экспертных систем для распо знавания отношений // Вестник ИжГТУ. – Вып.4(52). – Ижевск:

Изд-во ИжГТУ, 2011. – С.170 – 174.

25. Калядин Н.И. Минимизация представления предикатных форм в конечных моделях // Вестник ИжГТУ имени М.Т. Калашникова.

- Вып.1(53). – Ижевск: Изд-во ИжГТУ, 2012. – С.137 – 142.

26. Калядин Н.И. Симультанность в задачах классификации ко нечных объектов // Вестник Удмуртского университета. Серия "Ма тематика. Механика. Компьютерные науки". – Вып.1. - Ижевск: Изд во УдГУ, 2012. – С.133 – 143.

II. Авторские свидетельства 27. Авторское свидетельство №739595, СССР, М. Кл2 G06K15.20.

Устройство для отображения графической информации на экране электронно-лучевой трубки / В.И. Заболотских, Н.И. Калядин, В.Е.

Кацман – Заявл. 09.01.78, № 2568812;

опубл. – Бюл. 1980, №21.

28. Авторское свидетельство № 25265 от 27.09.1999 г. Медицин ский монитор / Н.И. Калядин, В.А. Леменков, А.В. Коробейников и др. – Заявл. 16.12.99 № 99125594;

опубл. – Бюл. 2002, №27.

III. Монография 29. Калядин Н.И. Конструктивизация моделей классификации конечных объектов // Известия института математики и информа тики УдГУ. Ижевск: Изд-во УдГУ, 2007. – Вып. 1(38). – С.3 – 231.

IV. Учебное пособие 30. Калядин Н.И. Основы теории алгоритмов и нумераций: Учеб ное пособие. – Ижевск: Изд-во ИжГТУ, 2006. – 68с.

V. Другие публикации 31. Калядин Н.И. Некоторые вычислительные аспекты в задачах распознавания булевых функций // Машинные методы обнаружения закономерностей: Материалы Всесоюз. симпозиума (5-7/04 – 1976 г.).

- Новосибирск: ИМ СО АН CCCP, 1976. – С. 128 – 138.

32. Калядин Н.И. Алгоритмический подход к проблемам распо знавания и классификации / В.А. Белоусов, Н.И. Калядин // Дис кретные системы обработки информации. – Вып.4. - Ижевск: Изд-во ИМИ, 1982. – С.86 – 93.

33. Калядин Н.И. Конечные модели и их применение к построе нию классификатора отношений последовательно-параллельного дей ствия / В.А. Белоусов, Н.И. Калядин // Дискретные системы обра ботки информации. – Вып.5. – Ижевск: Изд-во ИМИ, 1983. – С.83 – 88.

34. Калядин Н.И. Теоретико-игровой подход к классификации текстурных изображений / Н.И. Калядин, Ю.М. Липовецкий // Тру ды IX научных чтений по космонавтике. – М.: ИИЭТ АН СССР, 1988.

– С.143 – 150.

35. Калядин Н.И. Представление точечных изображений преди катами Радемахера / В.А. Белоусов, Н.И. Калядин // Дискретные системы обработки информации. – Вып.9. – Ижевск: Изд-во ИМИ, 1989. – С.3 – 12.

36. Калядин Н.И. Относительная полнота в конечных моделях / В.А. Белоусов, Н.И. Калядин // Дискретные системы обработки информации. – Вып.10. – Ижевск: Изд-во ИМИ, 1990. – С.5 – 12.

37. Калядин Н.И. Алгебро-логические алгоритмы в распознава нии, идентификации и классификации медицинских объектов / Н.И.

Калядин, В.А.Белоусов // Вестник ПГТУ. Математика и приклад ная математика. – Пермь: Изд-во ПГТУ, 2005. – С.61 – 66.

38. Калядин Н.И. К вопросу построения медицинских экспертных систем / Н.И. Калядин, В.А.Белоусов // Вестник ПГТУ. Прикладная математика и механика. - №1. - Пермь: Изд-во ПГТУ, 2005. – С. – 119.

39. Калядин Н.И. К вопросу существования симультанной моде ли классификации объектов / Н.И. Калядин, В.А.Белоусов // Вест ник Удмуртского университета. Математика. – №1. – Ижевск: Изд-во УдГУ, 2006. – С.151 – 160.

40. Калядин Н.И. Об одном существенном условии в распознава нии конечных множеств / Н.И. Калядин, В.А.Белоусов // Известия Института математики и информатики Удмуртского государствен ного университета. – Вып. 2(36). – Ижевск: Изд-во УдГУ, 2006. – С.113 – 116.

41. Калядин Н.И. Конструктивизация классифицируемых мно жеств // Вестник ПГТУ. Прикладная математика и механика. – №1.

– Пермь: Изд-во ПГТУ, 2006. – C.8 – 15.

42. Калядин Н.И. Нумерации в проблеме классификации // Вест ник ПГТУ. Математика и прикладная математика. – №1. – Пермь:

РИО ПГМА, 2007. – С.51 – 55.

43. Калядин Н.И. Оценки мощности множеств синтезированных спектров структурных связей / Н.И. Калядин, Д.Н. Сандалов // Труды Первой международной конференции Трехмерная визуали зация научной, технической и социальной реальности. Кластерные технологии моделирования. – Том 3. – Ижевск: Изд-во УдГУ, 2009.

– С.38 – 41.

44. Калядин Н.И. Фрактальность в спектрах структурных свя зей / Н.И. Калядин, Д.Н. Сандалов // Труды Первой международ ной конференции Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования.

– Том 3. – Ижевск: Изд-во УдГУ, 2009. – С.41 – 45.

Н.И. Калядин

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.