Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
КАЛЯДИН НИКОЛАЙ ИВАНОВИЧ УДК 519.712 + 510.25 + 510.67 КОНСТРУКТИВИЗАЦИЯ МОДЕЛЕЙ КЛАССИФИКАЦИИ КОНЕЧНЫХ ОБЪЕКТОВ:
КОНЦЕПЦИЯ, МЕТОДЫ И КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ Специальности:
05.13.18 Математическое моделирование, численные методы и комплексы программ 05.13.01 Системный анализ, управление и обработка информации (в наук
е и технике)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора технических наук Ижевск 2008
Работа выполнена в ГОУ ВПО Ижевский государственный технический университет (ИжГТУ)
Научный консультант:
заслуженный изобретатель РФ, доктор технических наук, доктор экономических наук, профессор Лялин В.Е.
(ГОУ ВПО Ижевский государственный технический университет, г. Ижевск).
Официальные оппоненты:
академик РАН, доктор технических наук, профессор Липанов А.М.
(Институт прикладной механики УрО РАН, г.Ижевск);
доктор физико-математических наук, профессор Дикусар В.В.
(Вычислительный центр им. А.А. Дородницына РАН, г. Москва);
доктор физико-математических наук, профессор Румянцев А.Н.
(ГОУ ВПО Пермский государственный университет, г. Пермь);
Ведущая организация: Институт математического моделирования РАН (г. Москва).
Защита состоится 27.02.09 г. на заседании диссертационного совета Д 212.065.04 в ГОУ ВПО Ижевский государственный технический университет (ИжГТУ) по адресу: 426076, г. Ижевск, ул. Студенческая, 7, корп. 1.
Отзыв на автореферат, заверенный гербовой печатью, просим выслать по указанному адресу.
С диссертацией можно ознакомиться в библиотеке ИжГТУ.
Автореферат разослан................................. 2008 г.
Ученый секретарь диссертационного совета Бендерский Б.Я.
доктор технических наук, профессор
Общая характеристика работы
Актуальность темы. С развитием вычислительной техники, робототехники и автоматизированных систем управления потребность в создании распознающих систем неуклонно возрастает, при этом разработка математической теории классификации или распознавания образов остается одной из центральных областей прикладной математики и кибернетики1.
В настоящее время наиболее полно разработаны статистические методы распознавания образов. В частности, в работах В.Н. Вапника, А.Л. Горелика, Н.Г. Загоруйко, В.А. Ковалевского, В.Д. Мазурова, В.Н. Фомина, А.Я. Червоненкиса и многих других авторов рассматриваются правила принятия решений и выбора признаков, позволяющие минимизировать вероятность ошибки распознавания при различных ограничениях.
Однако существующие подходы не позволяют осуществить крайне актуальную концепцию поэтапной конструктивизации в классификации образов: разрешимость, вычислимость и реализуемость на моделях классификации конечных объектов2. Кроме того, конструктивный подход в распознавании наряду с лингвистическим позволяет строить распознающие системы, работающие в реальном масштабе времени с информацией, которую статистические методы обрабатывать не могут (Русын Б.П.).
С расширением математического инструментария в распознавании образов (привлечения методов математической логики и теории алгоритмов, теории моделей и теории нумераций, математического программирования, конструктивной и дискретной математики) появляется возможность исследовать в первую очередь проблемы разрешимости и вычислимости на конструктивных моделях, решения которых на ранних этапах теории и практики распознавания образов отодвигались на второй план.
Проблемами разрешимости и вычислимости различных конкретных теорий фундаментальных наук занимались многие зарубежные В дальнейшем для простоты изложения будет использоваться один из устоявшихся терминов классификация или распознавание, если это не вызывает разночтений.
Конструктивизация образов, моделей объектов и т. п. вводятся согласно сложившимся основным понятиям конструктивной математики, в частности, конечный (конструктивный) объект есть образ, описываемый конечным объемом информации.
и отечественные математики: Barwise D., Bernaus P., Blum M., Cohen 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 A., Rogers H., Sacks G., Scott D.S., Shelah S., Shoenfield J.R., Sikorski A., Tarski A., Penrose R., Van der Waerden B.L. и другие;
Адян С.И., Барздинь Я.М., Гончаров С.С., Гуревич И.Б., Ершов Ю.Л., Журавлев Ю.И., Заславский И.Д., Колмогоров А.Н., Кузнецов А.В., Кушнер Б.А., Мальцев А.И., Марков А.А., Маслов С.Ю., Матиясевич Ю.В., Минц Г.Е., Нагорный Н.М., Новиков П.С., Нуртазин А.Т., Оревков В.П., Палютин Е.А., Перетятькин М.Г., Тайманов А.Д., Трахтенброт Б.А., Успенский В.А., Цейтлин Г.С., Шанин Н.А., Шрейдер Ю.А., Яблонский С.В., Якубович С.М. и многие другие.
Фундаментальные результаты проблем разрешимости и вычислимости в конструктивных моделях для теорий получены школой Ершова Ю.Л., но в распознавании образов подобных работ крайне мало (Журавлев Ю.И., Кондратьев А.И., Мазуров В.Д., Шрейдер Ю.А.), поэтому, оставаясь открытыми, проблемы разрешимости и вычислимости классификации образов становятся востребованными в рамках сформулированной концепции конструктивизации.
Проблема разрешимости моделей классификации конечных объектов (в дальнейшем просто проблема разрешимости) состоит в следующем: существует ли алгоритм, который по описанию на языке расширенного исчисления предикатов устанавливает принадлежность исследуемого объекта к рассматриваемому множеству M или k к одному из классов разбиения S {M1, M2,..., Mk}, M = Mi.
i=Проблема вычислимости моделей классификации конечных объектов (или просто проблема вычислимости) заключается в установлении эффективной процедуры, гарантирующей получение результатов вычислений соответствующих предикатов классификации объектов.
Возникающие при проектировании распознающих систем особенности представимости и вычислимости описания образов потребовали развития и модификации традиционных схем разрешимости и вычислимости конструктивных моделей.
Объектом исследования являются конструктивные (конечные) объекты, модели принятия решений в условиях неопределенности, язык расширенного исчисления предикатов, представление (описание) конструктивных объектов, рекурсивные функции; обучающая выборка, классы эквивалентности, спектральное представление сигнала; характеристические функции, предикаты Рaдемахера, критерии (не)разрешимости, оценки эффективной вычислимости, спектры структурных связей, условия существования симультанной (одномоментной) модели классификации; текстуры, конечные автоматы (классификаторы), компьютерные технологии.
Предметом исследования являются конструктивизация, (не-) разрешимость, вычислимость проблем классификации (распознавания); алгоритмизация, рекурсивность, m-сводимость; кластеризация, компактность, параллелизм, симультанность (одномоментность) вычислений; минимизация предикатных форм, методы и алгоритмы классификации, распознавания, идентификации конечных объектов;
частные и общие решающие правила, представимость и вычислимость описания конечного объекта, оценки сложности вычислений функций алгебры логики (ФАЛ); диагностика, мониторинг, прогноз;
синтез конечных автоматов (классификаторов); верификация, реализуемость моделей классификации.
Цель работы cостоит в получении научно-обоснованных методических и технических решений, направленных на конструктивизацию математических моделей классификации конечных объектов, базирующуюся на теории рекурсивных функций для установления разрешимости и эффективной вычислимости моделей классификации, обеспечивающей оптимизацию вычислительных затрат при аппаратно-программной реализуемости алгоритмов классификации, что будет способствовать совершенствованию вычислительных технологий классификации конечных объектов и расширению практики проектирования аппаратно-программных классификаторов.
Для достижения поставленной цели необходимо решить следующие задачи:
- рассмотреть задачи классификации конечных объектов с общей теоретико-модельной точки зрения;
- предложить алгоритмический подход к проблемам классификации, позволяющий установить однозначную разрешимость моделей классификации конечных объектов при многоальтернативных способах принятия решений;
- обосновать критерии (не)разрешимости задач классификации;
- исследовать проблемы разрешимости и вычислимости в классификации множеств по классам эквивалентности;
- построить математические модели для решающих правил, допускающих распараллеливание с целью синтеза быстрых алгоритмов классификации;
- указать условия существования предельно быстрой (однотактной, то есть симультанной) классификации конечных объектов;
- предложить конструктивные методы описания конечных объектов, эффективные по представимости (длина описания) и вычислимости (время принятия решения) для последующей реализации в классификаторах;
- получить оценки сложности вычисления функций алгебры логики для моделирования оптимальной структуры классификаторов;
- рассмотреть минимизацию вычислительных затрат на всех этапах конструктивизации (разрешимость, вычислимость, реализуемость) моделей классификации конечных объектов;
- смоделировать методики и алгоритмы практической реализуемости этапов конструктивизации наиболее динамичных и сложных в природе объектов, считающихся традиционно трудными для неконструктивных методов;
- выполнить доказательный эксперимент, подтверждающий совершенствование вычислительных технологий предложенной концепции конструктивизации в классификации конечных объектов;
- внедрить во вновь разрабатываемые аппаратно-программные комплексы распознающих систем (классификаторов) технические решения, научно обоснованные в диссертации.
Методы исследования. В теоретических исследованиях использовались методы теории множеств, математической логики и теории алгоритмов; теории моделей и теории нумераций; спектральной теории сигналов, теории распознавания образов; математического моделирования, численных методов, теории вероятностей и математической статистики; теории графов, теории принятия решений; системного анализа, методов конструктивной и дискретной математики.
Для подтверждения эффективности разработанных алгоритмов и устройств использовались методы статистического моделирования и натурных испытаний.
При расчетах систематически использовались методы вычислительного эксперимента.
Достоверность и обоснованность полученных в работе результатов и выводов подтверждается сопоставительным анализом существующих и разработанных подходов, математическими моделями и методами, экспериментальной проверкой основных теоретических выводов и положений статистическим моделированием и натурными испытаниями на разработанных и внедренных аппаратнопрограммных комплексах.
Достоверность верификации исследуемых объектов достигалась тестированием на стандартных (эталонных) сигналах с участием операторов высокого уровня.
На защиту выносятся следующие основные положения:
- концепция конструктивизации, сводящаяся к поэтапному рассмотрению разрешимости, вычислимости и реализуемости моделей классификации конечных объектов;
- алгоритмический подход к проблемам классификации, позволяющий с помощью рекурсивных функций учесть и провести формализацию на единой методологической основе, а также сформулировать критерии разрешимости и указать условия существования алгоритмов классификации конечных объектов;
- критерии (не)разрешимости проблем классификации в моделях с частично рекурсивным основным множеством и сигнатурами многоальтернативных решающих предикатов;
- теоретико-модельное описание решающих правил, как более адэкватное при использовании конкретных моделей, допускающее эффективные приемы в ходе вычислений предикатов сигнатур этих моделей;
- модели принятия решений в условиях неопределенности и многоальтернативности, допускающих распараллеливание решающих предикатов;
- доказательство существования предельно быстрой (симультанной) классификации конечных объектов, инвариантной по отношению к числу эталонов обучающей выборки и числу признаков в эталонах;
- алгоритмы и методы эффективной вычислимости в задачах распознавания булевых функций, использующие критерий компактности в спектре структурных связей между булевыми операторами;
- оценки мер сложности эффективной вычислимости правил принятия решений при классификации;
- методы эффективной представимости и вычислимости предикатных описаний конечных объектов;
- результаты реализации концепции конструктивизации моделей классфикации в прикладных задачах (классфикация текстур, компьютеризация медицинских технологий).
Научная новизна. Все выносимые на защиту результаты являются новыми. Отметим следующие элементы новизны:
- на основе системного анализа выполненных комплексных исследований сформулирована концепция конструктивизации в задачах классификации (распознавания) образов (конечных объектов);
- выделены компоненты инструментария (разрешимость, вычислимость, реализуемость) для совершенствования вычислительных технологий при конструктивизации моделей классификации конечных объектов;
- рассмотрен теоретико-модельный (алгоритмический) подход к решению проблем классификации конечных объектов на единой методологической основе, как более адэкватный с точки зрения использования конкретных интерпретаций используемых моделей;
- сформулированы условия однозначной разрешимости моделей игровых решающих правил;
- получены критерии (не)разрешимости моделей распознавания и классификации конечных объектов;
- найдены необходимые и достаточные условия существования предельно быстрой (симультанной) модели классификации как особого класса конструктивных моделей;
- разработан эффективный алгоритм вычислений булевых функций, использующий критерий компактности в спектре структурных связей между булевыми операторами в описании конечных объектов;
- получены оценки сложности вычислений функции алгебры логики (ФАЛ), как предпосылки для перехода от языка описания объектов к языку последующего синтеза конечного автомата (классификатора);
- предложены новые методы минимизации предикатных форм описаний конечных объектов для выбора их простейшего представления в моделях классификации;
- выполнен доказательный эксперимент, подтвердивший продуктивность предложенной концепции конструктивизации в классификации конечных объектов.
При решении прикладных задач разработаны:
- методики и алгоритмы классификации (распознавания) объектов со сложноструктурированной семантически насыщенной информацией на текстурных изображениях;
- новая компьютеризированная наукоемкая технология медицинского мониторинга;
- комплекс алгоритмов и программ по компьютерному анализу и прогнозированию (1990Ц2015 гг.) заболеваний населения Удмуртии (онкологических, психических, инфекционных).
Теоретическая значимость работы определяется тем, что основные идеи, методы и утверждения, предлагаемые в диссертации, развивают конструктивное направление в математическом моделировании и теории проектирования классификаторов (распознающих систем) и открывают новые возможности исследования моделей классификации конечных объектов.
Практическая ценность работы. На основе предложенной концепции конструктивизации в классификации конечных объектов разработаны методы и алгоритмы для решения ряда прикладных задач, считающихся традиционно трудными в теории и практике распознавания образов.
Разработанное под научным руководством автора диссертации математическое и программное обеспечение для измерения и оценки параметров текстурных изображений позволило создать и внедрить аппаратно-программный комплекс АРМ-Д, который использовался также для компьютерного анализа и в других областях, где носителями информации являются текстурные изображения: в авиации (аэроснимки тестовых трасс полета), медицине (рентгеновские снимки, материалы цито-, гистологических и эндоскопических исследований), технике (металловедение шлифы металлов, сварных швов), экологии (аэроснимки зон экологического загрязнения).
Полученные теоретические результаты нашли практическое применение в компьютеризации медицинских технологий, в частности, разработка и внедрение программных продуктов:
1) для компьютерного анализа и прогноза:
- онкозаболеваний населения Удмуртии в 1946Ц2015 гг. (система ОНКО, заболеваемость, смертность и выживаемость, 1991 г.);
- психических заболеваний населения Удмуртии в 1940Ц2016 гг.
(система ПСИХ, 1992 г.);
- инфекционных заболеваний (клещевой энцефалит, лайм-боррелиоз) населения Удмуртии в 1976Ц2020 гг. (система КЛЕЩ, 1997 г.).
2) для диагностики:
- состояния костей человека по их изображениям на рентгеновских снимках (система OSTEO, 1994 г.);
- эпилепсии населения Удмуртии (система ЭДИТА, 1995 г.);
- состояния желудочно-кишечного тракта по эндоскопическим исследованиям (система ЭНДО, 1995 г.).
Новизна отдельных технических решений подтверждена авторскими свидетельствами.
Реализация работы в производственных условиях.
I. В области обработки текстурных изображений.
Опытные образцы комплекса АРМ-Д (автоматизированное дешифрование аэрокосмических фотоснимков) и комплекса АМК (автоматизированное изготовление издательских оригиналов тематических карт) внедрены в ПГО Гидроспецгеология Мингео СССР (г.
Москва, 1988 г.), Госцентре Природа (г. Москва, 1990 г.).
Методика обработки текстурных изображений на комплексе АРМД использована при интерпретации результатов машинного анализа аэроснимков (ОКБ Интеграл при ЛГУ,г. Ленинград, 1988 г.), для компьютерной диагностики заболеваний костей (остеопороз) человека (Курганское НИИ экспериментальной и клинической ортопедии (г. Курган, 1988 г.), Маммологический центр Удмуртии (г. Ижевск, 1995 г.)); компьютерной диагностики онкопатологий человека (Республиканский онкологический диспансер (г. Ижевск, 1994Ц1999 гг.).
II. В компьютеризации медицинских технологий.
Разработаны, испытаны и внедрены первые в России отечественные мониторно-компьютерные системы для медицинских учреждений г. Ижевска (медсанчасть №7, 1992 г.; 1я Республиканская клиническая больница, 1994 г.; Республиканский клинический кардиологический диспансер, 1999 г.).
Апробация работы. Основные научные положения и практические результаты докладывались на следующих конференциях, симпозиумах и семинарах.
Научно-технические конференции Ижевского механического института (Ижевск, 1975Ц1991); Всесоюзный симпозиум Машинные методы обнаружения закономерностей (Новосибирск, 1976); V Всесоюзная конференция Планирование и автоматизация эксперимента в научных исследованиях (Москва, 1976); IV Всесоюзная конференция Автоматизация ввода письменных знаков в ЦВМ (Каунас, 1977); VII Всесоюзная конференция Теория кодирования и передачи информации (Москва, 1978); Всесоюзная научная конференция Автоматизация эспериментальных исследований (Куйбышев, 1980); VII Всесоюзная конференция по нейрокибернетике (Ростовна-Дону, 1980); Всесоюзных отраслевых конференциях и межведомственных совещениях Минрадиопрома, Мингео (Москва, Ижевск, 1980Ц1990 гг.); Региональная конференция Обработка изображений и дистанционные исследования (Новосибирск, 1981); Всесоюзная конференция Адаптивные работы-82 (Нальчик, 1982); Всесоюзная конференция Перспективные методы планирования и анализа экспериментов при исследовании случайных полей и процессов (Москва, 1982); IV Всесоюзная школа-семинар Распараллеливание обработки информации (Львов, 1983); I, IV Всесоюзная конференция Методы и средства обработки сложноструктурированной семантически насыщенной графической информации (Горький, 1983; Нижний Новгород, 1998); III Всесоюзная конференция Проблемы техники в медицине (Томск, 1983); Всесоюзная конференция Обработка изображений и дистанционные исследования (Новосибирск, 1984); VIII Всесоюзная конференция Автоматизация в тематической картографии (Москва, 1984); VII Всесоюзный симпозиум Логическое управление в промышленности (Ижевск, 1984); VI Всесоюзное совещание Проблемы автоматизации анализа изображений микроструктур (Пущино, 1984); 2е Всесоюзное совещание Космическая антропология: техника и методы исследования (Ленинград, 1984); II, III Всесоюзная конференция Математические методы распознавания образов (Рига, 1987, 1989); IX научные чтения по космонавтике (Москва, 1988); X Всесоюзная конференция по математической логике (Алма-Ата, 1990); Международная конференция ОИДИ-90 (Новосибирск, 1990); 1я Всесоюзная конференция РОАИ1-91 Распознавание образов и анализ изображений (Минск, 1991);
XI Междуреспубликанская конференция по математической логике (Казань, 1992); II Международная конференция Математические алгоритмы (Нижний Новгород, 1995); XI Международная конференция по нейрокибернетике (Ростов-на-Дону, 1995); Международная конференция Математическое моделирование в науке и технике (Ижевск, 1995 г.); III Всероссийская конференция РОАИ Распознавание образов и анализ изображений: новые информационные технологии (Нижний Новгород, 1997); LII научная сессия, посвященная дню радио (Москва, 1997); научно-технические конференции ИжГТУ (Ижевск, 1991Ц2004); VI Всероссийская с участием стран СНГ конференция Методы и средства обработки сложной графической информации (Нижний Новгород, 2001); научная конференциясеминар Теория управления и математическое моделирование, посвященная 50-летию ИжГТУ и 30-летию кафедры ПМИ ИжГТУ (Ижевск, 2006); Международная конференция Теория управления и математическое моделирование, посвященная памяти организатора Ижевского математического семинара, д. ф.-м. н., проф. Азбелева Н.В. (Ижевск, 2008).
Работа поддержана грантами РФФИ (03-01-00255, 04-01-96016, 0601-0074).
Прикладные результаты отражены в отчетах о НИОКР, выполненных под руководством автора, в рамках государственных, отраслевых и целевых научно-технических программ.
Публикации и личный вклад автора. Основные результаты диссертации опубликованы в 52 работах (общим объемом 50,4 п. л.).
Автор имеет 23 научных труда в изданиях, выпускаемых в РФ и рекомендованых ВАКом для публикации основных результатов диссертации на соискание ученой степени доктора наук.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и приложения, изложенных на 364 с.
машинописного текста. В работу включены 41 рис., 4 табл., список литературы из 228 наименований и приложение, в котором представлены акты об использовании результатов работы.
Краткое содержание работы Введение содержит обоснование актуальности темы, формулировку цели и задач работы, основные положения научной новизны и практической полезности и определяет содержание и методы выполнения работы.
Предлагаемая в настоящей работе концепция конструктивизации сводится к последовательному исследованию этапов разрешимости, вычислимости и реализуемости моделей классификации конечных объектов с целью совершенствования вычислительных технологий классификации.
Строгие формулировки теорем, положенных в основу разработанной концепции конструктивизации и ее алгоритмов, приводятся в тексте диссертации. В автореферате ограничимся описанием существа основных утверждений и комментариями возможностей их использования для практической реализации технических решений.
Первая глава посвящена разрешимости конструктивных моделей классификации конечных объектов.
Традиционно распознавание образов рассматривается как математическое моделирование слабо формализованных сложных задач.
Методы и алгоритмы распознавания образов в значительной мере определяются конкретной физической природой распознаваемых объектов или явлений.
Первым шагом при конструктивизации является формализация исходного описания образа 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.
Тогда целевые функции, известные как задачи распознавания, классификации и идентификации, определим через операции вычисления характеристических функций следующим образом.
1. Распознавание:
1, если X (Mi) K;
(x M)(X K) X (Mi) = 0, в противном случае.
2. Идентификация:
1, если X = Xi, i Im, (X O) X = Xi = 0, в противном случае.
3. Классификация:
1, если X Nj, j It, (X O) X Nj = 0, в противном случае.
Задачи классификации являются более общим случаем задач распознавания и идентификации. В дальнейшем без потери общности будут рассматриваться в основном задачи классификации конечных объектов. Но там, где необходимо подчеркнуть особенности именно задач распознавания или идентификации, будем переходить на использование соответствующих понятий.
В предложенном подходе к распознаванию образов показано, как сочетание геометрических и лингвистических установок при описании образов на языке расширенного исчисления предикатов в выбранном спектральном пространстве определяет экзистенциальность, то есть возможность анализа проблемы классификации на разрешимость.
О п р е д е л е н и е 1.3 Пара R (M, TD+) называется входным пространством распознающей системы, если выполняются следующие аксиомы:
(A1) x t y (существование толерантности), x, y M t D+ (A2) M t (рефлексивность), M = { (x, x)| x M}, t D+ -(A3) t = t (симметричность), t D+ (A4) (t s) (t s) (упорядоченность), t,sD+ (A5) ts t+s (квазиаддитивность), t,sD+ В автореферате принята независимая от текста диссертации система нумерации соотношений и утверждений где TD+ класс отношений толерантности (сходства) на множестве M, индексированный множеством неотрицательных вещественных чисел D+, то есть TD+ = { }tD+.
t Аксиомы (A1) (A5) определяют класс отношений сходства между элементами множества M, причем степень сходства определяется вещественным индексом соответствующего отношения толерантности.
Пусть заданы дополнительно:
мера на множестве M из входного пространства R;
P множество некоторых элементарных предикатов на множестве M;
V {M1, M2,..., Mm}, Mi M, i = 1, m, причем каждый класс (образ) Mi описывается некоторой логической комбинацией предикатов из P : Mi = { x M| Li[p1(x),..., pk (x)] & pj(x) P }, где i 1 j ki Li - некоторая пропозициональная функция.
О п р е д е л е н и е 2. Набор (R, P, V, ) называется логической моделью распознавания, если выполняются следующие аксиомы:
(K1) xy xz (связность), xMi yM zMi D+ (K2) xty (ограниченность), x,yMi tD+ (K3) (Mi) = t&(t > 0) (объемность), tD+ n n (K4) (Mi ) = (Mi\Mi )&(0 1) (отделимость).
При выполнении аксиом (K1) (K4) классы Mi называются образами. На языке метрических соотношений аксиомы (K1), (K2) эквивалентны условию компактности класса Mi.
О п р е д е л е н и е 3. Модель распознавания (R, P, V, ) называется спектрально-логической, если:
1) M = Dm, где Dm m-я декартова степень множества вещественных чисел;
2) есть лебеговская мера в m-мерном пространстве Dm;
3)TD+ класс отношений толерантности, элементы которого определены с помощью евклидовой метрики на M :
m xty (xi - yi)2 t.
i=С помощью спектрально-логической модели описание любого объекта распознавания x M может быть произведено с помощью упорядоченного набора числовых коэффициентов, определяющего некоторую точку в пространстве Dm. Такие наборы чисел и есть спектры в самом широком понимании этого термина (Трахтман А.М.).
В рамках спектрально-логического подхода осуществляется поиск критериев разрешимости и вычислимости моделей классификации конечных объектов. С этой целью исходное множество объектов из M редуцируется к множеству всех натуральных чисел N {0, 1, 2,... } через отображение : M N. Пара M, объявляется множеством конструктивных (конечных) объектов, если при этом разнозначное отображение, то пара M, называется множеством сильно конструктивных объектов.
Введенные понятия конструктивных объектов обеспечивают дальнейшую формализацию на единой методологической основе классe всех частично рекурсивных функций, совпадающих с классом всех частичных арифметических функций, допускающих эффективные вычисления.
Пусть M (M), M Ф семейство всех конечных подмножеств множества N {0, 1, 2,... }; S {Ni}iI разбиение семейства M, где I не более чем счетное индексное множество; : N стандартная нумерация.
Рассмотрим модель M; S с основным множеством M и сигнатурой S Pi, где предикаты Pi (X) будем интерпретировать iI следующим образом: (X M) [Pi (X) = 1 X Ni].
Вопрос о разрешимости предиката Pi (X) назовем проблемой рас познавания для класса Ni. Учитывая, что Pi(X) = 1-A (-1(X)), i где A характеристическая функция множества Ai -1(Ni), то i в силу тезиса Чёрча справедливо П р е д л о ж е н и е 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) -1 (Ni)], то проблема классификации m для разбиения В семейства L разрешима.
В практике классификации встречаются случаи, когда множество (M) N соответствует частично разрешимым предикатам. Тогда справедливо П р е д л о ж е н и е 3 (критерий неразрешимости 1). Пусть M, множество конструктивных объектов таково, что (M) рекурсивно перечислимо, но не рекурсивно. Тогда ни для одного конечного разбиения R множества M проблема классификации для тройки M, R, неразрешима.
Поставленная таким образом задача классификации допускает многоальтернативное решение. Одним из условий сокращения альтернатив является требование к функции : M N обладать разнозначностью, то есть когда M, сильно конструктивные объекты.
Более общим условием однозначного принятия решений является требование попарного непересечения множеств (Mi) и (Mj) (i = = j Im) для исходного разбиения множества M.
О п р е д е л е н и е 4. Семейство 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) сильно рекурсивно].
Сформулированные критерии (не)разрешимости опираются на знание априорной информации о классах объектов. На практике, как правило, такая информация отсутствует, поэтому для решения проблем классификации приходится использовать обучение.
Другим способом редукции к натуральным числам и арифметическим функциям является использование подходящей нумерации, то есть отображения : N S, где S произвольное (исследуемое) множество конечных объектов.
Изучение свойств нумераций семейств конечных объектов позволяет перенести проблему классификации из области натуральных чисел в область произвольных конечных объектов.
В настоящей работе сделано обобщение проблемы вхождения на подмножестве любого другого универсума конечных объектов K. Другим обобщением проблемы вхождения следует считать проблему классификации без учителя: существует ли алгоритм, способный указать, в какие классы K1, K2,..., Kt, где Ki = (Mi), i = 1, t попадает элемент (x) для любого x M? Сформулированы условия однозначной разрешимости (существования и единственности решений) для моделей классификации, допускающих распараллеливание в игровых решающих правилах: модели Вальда, Лапласа, Сэвиджа, коллективного голосования и сильного голосования.
Интерпретация критериев разрешимости для типовых игровых решающих правил позволила построить общую схему принятия решений M M; O; f, i, повышающую (за счет распараллеливания) вычислительную эффективность и в целом надежность классификации объектов: общее решение Rk(x) = Qi(x), где мно iDk жество номеров эталонных объектов Dk = {i|f(i) = k}, k = = 1, t; некоторая реализация объекта x = x1,..., xn M; сигна тура i = Qi1, Qi2,..., Qit из t одноместных частных решающих предикатов 1, если c(i, x) = c0;
Qi(x) = 0, в противном случае, где c0 = max(min){c(1, x),..., c(, x)}, c(i, x) некоторый функ ционал, выражающий меру близости (сходства) между эталонами обучающей выборки i O = ||uij|| n, число эталонов, n число признаков; i = ui, ui,..., ui, i = 1, и неизвестной реали1 2 n зации x = x1,..., xn, j = 1, n.
Доказано, что проблема классификации конечных множеств по классам эквивалентности разрешима, когда число классов эквивалентности конечно, а каждый класс эквивалентности есть сильно рекурсивное множество.
Вторая глава посвящена проблеме вычислимости разрешимых моделей классификации конечных множеств: когда элементы множеств максимально различны и, наоборот, когда наблюдается сильное пересечение ( сцепление ) множеств.
В зависимости от силы сцепления множеств определяются возможные пути к построению различных по эффективности вычислений предикатов классификации.
Конструктивизация направлена на то, чтобы добиться наибольшей вычислительной эффективности от схем принятия решений, распараллелить последние.
Анализ однозначной разрешимости моделей типовых игровых решающих правил позволил сформулировать условия существования и единственности решений в моделях классификации с предельно коротким циклом принятия решений.
Т е о р е м а 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\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 = i O.
Модель с условиями теоремы 1 и следствия 2 (назовем симультанной моделью классификации), имеет предельно короткий цикл принятия решения: необходимо и достаточно сравнить параллельно по всем кортежам обучающей выборки только по одному информативному значению каждого признака; при этом модель обладает свойством инвариантности: время на принятие решения не зависит ни от количества эталонов в обучающей выборке, ни от количества признаков, которыми характеризуются эти эталоны.
Найдены необходимые и достаточные условия симультанности в принятии решений, когда единичность логической матрицы ||qij||mm допускает упрощенное вычисление предиката равенства посредством вычисления предиката принадлежности элемента ( идентификационной метки ) информативной зоны соответствующему множеству.
В подобных моделях следует выделить предложенные в настоящей работе в качестве меры близости отношения толерантности как частный подкласс известных алгоритмов вычисления оценок (Журавлев Ю.И., Никифоров В.В.).
Рассмотрим класс 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; , что позволяет в целом повысить надежность классификации объектов.
Для решения традиционно трудных прикладных задач (в частности, классификации текстур) предложена иерархическая модель кластеризации M F ; F1,..., Ft с порождением отношений образов Fi, i = 1, t.
Введенные меры близости между эталонным и предъявленным описаниями конечного объекта определяют стратегию оптимизации решающих правил классификации путем оценки C(i, x) функци онала близости объекта x стратегии i O, i = 1,.
Оптимальность выбора достигается с учетом критериев эффективной представимости и вычислимости предикатов классификации (компактность, параллелизм, симультанность (однотактность)) при их последующей автоматной моделируемости.
Языком, удовлетворяющим таким критериям представимости и вычислимости, располагает система B = Bn; &, , м; 0, 1, образующая алгебру булевых функций (или функций алгебры логики ФАЛ) f(xn), xn = x1, x2,..., xn, xi {0, 1}, i = 1, n; Bn = {f|f :
{0, 1}n {0, 1}}.
F (xn) правильно построенная формула (ппф), полученная су перпозицией элементарных ФАЛ q L = {-, &, , , , , /, , } из класса P2 или переименованием переменных xi xn и скобок (, ).
Другим преимуществом языка ФАЛ является возможность эффективных вычислений (распознавания) образа f(xn) по его описа нию ппф F (xn), то есть эффективного алгоритма F (xn) f(xn).
Т е о р е м а 2. Для реализации алгоритма F (xn) f(xn) необходимо и достаточно вычислить ядро Ki и построить рекурr -1 сивный процесс вычисления Ki : F (xn) F (xn) ... F (xn).
Через шагов процесс заканчивается получением b .
.
F (xn) = f(xn), где bj {0, 1}, j = 1, 2n.
.
n bДостоинством языка ФАЛ является возможность получения коротких описаний ФАЛ известными методами минимизации в выбранном базисе, что представляет практический интерес для структурного моделирования распознающих систем (классификаторов).
Рис. 1. Примеры спектров структурных связей между признаками Для уменьшения объема памяти вычислителя, что равносильно количеству одновременно хранимых промежуточных результатов, потребуем выполнения на каждом шаге условия обеспечения компактности алгоритма использование логических связей в исход r ной формуле F (xn) согласно следующему правилу: если {Ki } O1, pj r+{Kb } O2 и существует такая операция qj, что имеет место pj r+1 pj r {Ki }qj {Kb }, то {(O1)qj (O2)} O1. Критерий компактности минимальный объем памяти при реализации алгоритма F (xn) f(xn).
Рис. 2. Виды элементарных (базовых) спектров:
а) монотонно убывающий; б) монотонно возрастающий;
в) постоянный; г) осциллирующий.
Интерпретация ппф F (xn) как описания некоторого образа f(xn) в пространстве бинарных признаков xi xn, i = 1, n позволяет обна pj pj ружить закономерности в отображении F (xn) S(qi ), где S(qi ) G {1, 2,..., j} {p1, p2,..., pj}, j N номер операции qj L\- в ппф F (xn), pj N номер (ранг) операции gj L\- в ппф F (xn).
pj S(qi ) спектр структурных связей взвешенных бинарных опеpj раций qi между признаками xi xn образа f(xn). Этот спектр есть дискретный или линейчатый.
G график зависимости величины порядка pj операции qj от ее связи и расположения ( глубины погружения ) в ппф F (xn).
pj Отметим ряд полезных свойств спектра S(qi ).
pj Л е м м а 1. Спектр S (qj ) может содержать только осциллирующие, монотонно возрастающие ( убывающие ) или постоянные участки.
Т е о р е м а 3. Для одной и той же формулы F(xn) можно pj построить один и только один спектр S (qj ), то есть инъективpj ное отображение F(xn) S (qj ).
Для построения компактного алгоритма F(xn) fk(xn) необхо димо указать правило выбора такого 1-го шага, который обеспечивал бы запоминание минимального количества промежуточных результатов при вычислении формулы F(xn).
Т е о р е м а 4 (метод сечений). Для отыскания 1-го (начального) шага компактного алгоритма F(xn) fk(xn) необходимо и достаточно:
pj 1) построить отображение F(xn) S (qj );
pj 2) провести сечение спектра S (qj ) по минимальному локальному минимуму; из двух частей спектра относительно сечения выбрать для дальнейшего вычисления ту, которая содержит наибольшее число связывающих максимальных локальных минимумов;
3) в выбранной части снова произвести сечение по правилам п.
2 и т.д. до тех пор, пока не останется в каждой части спектра не более одного связывающего локального минимума.
Операции qj L\- в исходной F(xn), соответствующие их ло кальным максимумам, и будут являться ядрами 0-го ранга.
Т е о р е м а 5 (теорема компактности). Для построения компактного алгоритма F(xn) fk(xn) необходимо и достаточно по методу сечений выбрать 1-й шаг и, выдерживая на каждом шаге условие компактности, вычислить ядра, соответствующие лоpj кальным минимумам, в порядке, обратном сечениям спектра S (qj ).
Теоремы 4, 5, исключая эвристику при построении компактного алгоритма F(xn) fk(xn), указывают пути автоматизации вычис лений булевой функции fk(xn).
Оценки сложности вычислений булевых функций.
В качестве меры сложности [F(xn)] вычисления fk(xn) введены два типа сигнализирующих функций:
1) функции, связанные с длительностью вычислений fk(xn) :
1 t[F(xn)] 2, Рис. 3. Выбор 1-го шага для получения компактного алгоритма F(xn) fk(xn) где 2 = верхняя оценка, длина формулы F(xn), 1 = t+ + нижняя оценка, 2t 2t+1;
2) функции, связанные с объемом промежуточной памяти:
+ 1 = 2 0[F(xn)] 2 =.
Полученные оценки сложности вычисления ФАЛ гарантируют реализацию классификаторов с заранее заданными вычислительными ресурсами.
В третьей главе рассматривается реализуемость концепции конструктивизации при классификации (распознавании) конечных объектов, представителями которых являются одномерные или двумерные сигналы от различных изображений.
Алгоритмы распознавания, как правило, имеют не самостоятельное значение, а реализуются в виде аппаратно-программных комплексов, являясь составными частями более сложных систем.
В работе предложены конструктивные представления конечных объектов для построения классификаторов отношений последовательно-параллельного действия на основе конечных моделей с минимально полной сигнатурой (предикатами Радемахера, использующие дискретные функции). Например, для синтеза генераторов предикатов конечной модели 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), k(x) Ri(x), если [(k - 1)]n-i+1 = 0;
где Ri = мRi(x), в противном случае, n = 2n/m; [] целая часть числа, [ (k - 1)] = 2i-1 [ (k - 1)]i;
i=[ (k - 1)]i {0, 1} ; n = y(2y m), оператор минимизации, (i = 1, n; k = 1, m).
Доказано, что любой предикат Q(x1,..., xk) на M можно разложить по предикатам Радемахера, допускающим простую аппаратную реализацию двоичными n разрядными регистрами Pr(n).
Относительная полнота и независимость сигнатур конечных моделей определяет реализуемость классификаторов отношений последовательно-параллельного действия, дешифраторов и генераторов предикатов любой местности.
П р и м е р 1. Функциональная схема классификатора для трехместных отношений будет иметь вид, указанный на рис. 4, где Pr-Cr регистр-счетчик; KC комбинационная схема;
CC схема сравнений; Cr счетчик;
x, y, z входные координаты;
P (x, y, z) классифицируемый предикат в точке x, y, z.
Рис. 4. Функциональная схема классификатора Минимизация предикатных форм в конечных моделях.
Проблема простейшего представления предикатных форм для сигнатуры сводится к выбору базиса и наиболее экономичного представления предикатов в этом базисе.
Предложенные методы минимизации дизъюнктивных нормальных предикатных форм в конечных моделях обеспечивают выполнение одного из условий конструктивизации минимизацию вычислительных затрат при реализуемости моделей классификации.
Примеры реализуемости этапов конструктивизации.
Под изображением понимается некоторое подмножество конечного множества. Вводятся операции над изображениями, рассматривается алгебра изображений с наделенными конструктивными свойствами, допускающими реализуемость адекватных моделей классификации.
Представление текстурных изображений.
При работе с текстурами важно уметь построить адекватную модель классификации для априорно заданных классов текстурных изображений. В данном случае такая модель строится для пространства наблюдений F текстурных изображений на основе обучающей информации с порождением отношений-образов двухместной операцией, определяемой с помощью полусуммы:
X1 X2 = { x, y, [f1(x, y) + f2(x, y)]/2 }, где изображения X1, X2 R, X1 = { x, y, f1(x, y) }; X2 = { x, y, f2(x, y) }, [] целая часть числа.
Пусть имеется множество текстурных изображений T с отображением : T F в пространство дискретных изображений F, где в качестве дискретных взяты изображения Xi = { x, y, f(x, y) | x, y M2, f(x, y) : M2 M}.
В пространстве наблюдений F вводится обучающая выборка O = = (X1), (X2),..., (X ) такая, что (X1) = X1,..., (X ) = X, и задается классифицирующая функция q : I It, t число классов;
I {1, 2,..., }, It {1, 2,..., t}.
На множестве F введем бинарную операцию, чтобы получить алгебру F ; с основным множеством F и операцией. С помощью бинарной операции и множеств Ak = {Xi|i Dk}, где Dk = = {i|g (i) = k}, (k = 1, t), порождаются отношения-образы Fk, (k = = 1, t), так как рассматривается модель M = Fj; F1,..., Ft с основным множеством Fj и отношениями F1, F2,..., Ft.
Построенная модель M адекватна исходной модели Q = Tj; T1,..., Tt с основным множеством Tj и некоторыми априорно заданными классами Ti T, (i = 1, t). Адекватность достигается тем, что операция отражает компактность, имеющую место между текстурами одного класса.
Важное место при решении задач классификации текстур занимают вопросы выбора оптимального количества элементов исходной обучающей выборки O, построения эффективной процедуры обучения и минимизации окончательной обучающей выборки в целях дальнейшей верификации указанных объектов.
Дискретизация обучающей, контрольных и испытательных выборок.
Исходным материалом является обучающая выборка O, класс контрольных выборок A = {K1, K2,..., Ki} и класс испытательных выборок B = {U1, U2,..., Us}.
Пусть J = O A B, где O = ij обучающая выборка, mn ij значения непрерывных признаков i = 1, m; j = 1, n. [ai, bi] интервал распределения i-го признака.
Пару i, f (i) назовем паспортом для кортежа i1,..., in ; обозначим множества номеров эталонных объектов Dk {i|f (i) = k}, k = 1, t, классифицирующую функцию f : Im It, It {1, 2,..., t}, Im {1, 2,..., m}, t, m N.
Пусть для некоторого r > 0, определяющего глубину (шаг) квантования, с помощью оператора дискретизации (0, r) получена матрица (0, r) = O (r) = lij.
mn i j Между номерами кортежей l = li1,..., lin и l = lj1, lj2,..., ljn i j установим отношение эквивалентности следующим образом: l = l (l = 1, n) [li = lj ].
2 Профакторизуем каждое множество Dk, k = 1, t по отношению эквивалентности , то есть рассмотрим фактор-множество Dk|.
Взяв по одному кортежу с паспортом i, f (i), где i принадлежит классу эквивалентности j Dk| по всем k = 1, t, и, пронумеровав всю полученную выборку от 1 до (l1 + l2 +... + lt), получим минимальную матрицу a11... a1n O (r) =.................
al +l2+...+lt... al +l2+...+ltn 1 c классифицирующей функцией f (i) такой, что 1, если 1 i l;
f (i) = 2, если l1 + 1 i l1 + l2;
t, если l1 - l2 -... - lt-1 + 1 i l1 + lt +... + lt.
Полученная матрица далее используется для классификации посредством некоторых решающих правил, например, одним из наиболее распространенных методом коллективного голосования.
Представление точечных изображений предикатами Радемахера.
Точечные изображения примем в виде функции 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 D}, которое необходимо представить в базисе предикатов Радемахера.
Пусть F = { x, y, f(x, y) | x, y D} = { i11, i12, i13,..., i 1, i 2, i 3 }.
Соответствующий этому отношению предикат 1, если x1, x2, x3 F ;
P (x1, x2, x3) = 0, в противном случае, можно записать в виде дизъюнктивного разложения по единичным значениям предиката P (x1, x2, x3) на кортежах i 1, i 2, i 3 :
P (x1, x2, x3) = Pi,i12,i13 (x1, x2, x3) ... Pi,i,i (x1, x2, x3), 11 1 2 где Pi,ij2,ij3 (x1, x2, x3) = Pi (x1) &Pi (x2) &Pi (x3), j = 1,.
j1 j1 j2 jПодставляя в последнем выражении вместо Pi (xk) jk ijk ijk ijk Pi (xk) = R1 (xk) &R2 (xk) &...&Rn (xk), jk Rp (xk), если (n - p + 1) разряд двоичного q где Rp (xk) = разложения числа q - 1 равен 0;
м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 }|.
Содержательно геометрический спектр изображения A показывает, какие базисные прямоугольники (x, y) и сколько их k (c (x, y)) содержит изображение A. Первая гармоника геометрического спектра k (1) интерпретируется как площадь изображения A (как, например, в спектре Уолша), а остальные гармоники дают представления о площадях оставшихся частей изображения 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.
О п р е д е л е н и е 8. (Критерий полноты покрытия изобP ражения A). Полным подспектром S (A) = { k (m), m } изображения A назовем подспектр изображения, удовлетворяющий условию:
r r r r r r D [a (n, m)] - D [a (ni, mi) a (nj, mj)] = n=1 m=1 ni=1 mi=1 nj=1 mj== 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 }.
Для оценки эффективности предлагаемого метода решалась на компьютере контрольная задача Робот, в которой изображение на растре 128128 требовало для описания поточечным методом 15 7ячеек памяти, неусеченное представление в спектре Уолша занимает 16 384 ячейки, а предлагаемым методом всего 40 ячеек памяти.
Новизна метода подтверждена авторскими свидетельствами [47-50].
Предложен алгоритм оптимизации, позволяющий значительно сократить объем памяти при компьютерном анализе и синтезе изображений. Доказана универсальность предложенного алгоритма для класса растровых изображений.
Четвертая глава содержит прикладные результаты по компьютерной классификации (распознаванию) наиболее динамичных и трудных для исследований объектов:
текстурных изображений, функциональных состояний человека.
Компьютерная классификация текстур.
В общем потоке исследований по распознаванию образов компьютерный анализ текстурных изображений занимает особое место, вопервых, наиболее частая встречаемость текстур в практических задачах автоматизации распознавания образов (например, в задачах медицинской диагностики, материаловедения, биофизики, дистанционного исследования природных ресурсов и т.п.); во-вторых, текстурные изображения являются составными частями любых изображений.
В системе картобеспечения рационального природопользования одно из ведущих мест принадлежит черно-белым интегральным космическим фотоснимкам (КФС) масштаба 1:180000Ц1:340000, обеспечивающим оперативное получение достоверной информации о больших площадях земной поверхности. КФС высокого разрешения представляют текстурные изображения, интерпретируемые как случайные поля оптической плотности.
Ввиду потенциальной неограниченности числа классов на КФС и слабой приспособленности зрительного анализатора человека для работы с малоразмерными, низкоконтрастными элементами (объектами) на КФС надежность визуального дешифрирования КФС по всем классам объектов, к сожалению, не превосходит 35Ц40%, а по одному из самых распространенных и сложных классов растительным покровам и грунтам (РПиГ) 20Ц30%, что не обеспечивает полноту содержания многих тематических и топографических карт, составляемых (обновляемых) по КФС.
В работе дается краткое описание разработанного на основе теоретических результатов аппаратно-программного комплексам АРМД, предназначенного для автоматизированного дешифрирования аэрокосмических фотоснимков при составлении и обновлении топографических и тематических карт.
Состав разработанного комплекса АРМ-Д.
1. Уникальное устройство ввода КФС, сопряженное аппаратно с компьютером.
2. Прикладное программное обеспечение, реализующее методику автоматизированного дешифрования КФС.
3. Информационное обеспечение, включающее банк аналитических эталонов дешифрования объектов на КФС.
Для оценки качества работы комплекса АРМ-Д в производственных условиях рассмотрено 47 типов РПиГ на 39 КФС, в пределах которых выделено 236 контуров, 528 фрагментов текстурных изображений РПиГ. Надежность их дешифрирования составила в среднем 77,4 1,7%, в том числе для районов-аналогов 77,24,2%.
Значения достоверности дешифрирования на комплексе АРМ-Д приведены в табл. 1.
Таблица Объект исследований Число Достофрагментов верность, % Класс (тип РПиГ) 125 Породный состав лесов 111 Количественные характеристики 245 растительности Литологический состав грунта 220 (до 3 метров) Уровень грунтовых вод в 3-мет- 125 ровой толще Достигнутый уровень результатов дешифрирования соответствует требованиям, предъявляемым к комплексам автоматизированного дешифрирования космических фотоснимков при обновлении и составлении карт топографических и других видов.
Универсальность комплекса АРМ-Д позволяет применять его также для решения широкого круга нетопографических задач фотограмметрии в медицине, технике, авиации, биологии, физике, экологических исследованиях.
Прикладные аспекты концепции конструктивизации рассматриваются при решении каждой из трех основных проблем компьютеризации в медицине: диагностика, мониторинг, прогнозирование.
Компьютеризация медицинских технологий Разработан и внедрен в медицинские технологии пакет прикладных программ OSTEO для компьютерного анализа состояния костей человека по их текстурным изображениям на рентгеновских снимках, позволяющий обнаружить и количественно оценить на языке вычислительного эксперимента скрытые закономерности, которые не удается вскрыть традиционными ручными методами визуального анализа.
Рис. 5. Оценка состояния костной ткани пациента (компьютерная система OSTEO ) 1. В частности, выявленные при компьютерном анализе на рентгеновских снимках скрытые дефекты (пустоты, каверны) в микроархитектонике костной ткани объясняют этиологию и патогенез подчас возникающего остеомиелита при сращивании костей человека с использованием аппарата и методики Илизарова Г.А. (Курганское НИИ экспериментальной и клинической ортопедии и травматологии, г. Курган, 1994 г.).
2. Выполненные с помощью пакета OSTEO исследования регулярности трабекулярной структуры костной ткани на рентгеновских изображениях суставов женщин предоставили возможность обнаружить и проследить возрастную динамику онкопатологий (в 20 35 50 лет), связанных с уменьшением костной массы и изменениями микроархитектоники костной ткани (Маммологический центр Удмуртии, г. Ижевск, 1995 г.).
Разработан компьютерный эндоскоп аппаратно-программный комплекс, сопряженный с эндоскопом под управлением единого программного обеспечения (система ЭНДО ).
Проведенные клинические испытания компьютерного эндоскопа (23 объекта эзофагоспии) в Республиканском онкологическом диспансере Удмуртии (1995 г.) подтвердили экспериментально повышение качества эндоскопических исследований за счет исключения субъективных ошибок врача-эндоскописта и предоставляемой ему возможности ведения диалога с компьютерной экспертной системой, накопленной базой знаний и базой данных при решении задач диагностики, мониторинга и прогнозирования.
Проблема количественного и качественного анализа данных по онкологическим заболеваниям, стоящим на одном из первых мест по заболеваемости и смертности в ряду всех болезней, имеет большую научную и общественную значимость. В работе описаны методы и приведены результаты, позволяющие на основе статистических данных прогнозировать показатели медицинской статистики на различные периоды, устанавливать факторы, влияющие на показатели заболеваемости, и связи между различными локализациями. Компьютерный ретроспективный анализ (1946Ц1990 гг.) онкопатологий населения Удмуртии позволил выполнить онкопрогноз на период 1990 - 2015 гг.
Для прогнозирования до 2015 г. показателей заболеваемости, смертности и контингента использовались регрессионные и авторегрессионные модели (информационно-аналитическая система ОНКО).
Результаты, полученные прямым и косвенным способами прогнозиРис. 6. Исследование динамики эндоскопического объекта пациента (компьютерная система ЭНДО ) рования показателей заболеваемости, смертности и контингентов онкобольных, оказались близкими.
Внедрение в психиатрическую практику интеллектуальных возможностей современных компьютерных технологий позволяет строить высокоэффективные диагностические и обучающие программы, в частности, разработанная подсистема ЭДИТА, реализующая компьютерную технологию диагностирования эпилепсии, базируется на классификаторе системе индивидуальных признаков пациента.
Разработанный комплекс алгоритмов и программ по мониторированию основных физиологических параметров человека: электрокардиограмма (ЭКГ), артериальное давление (АД), пульсоксиметрия Рис. 7. Компьютерный анализ и прогноз онкозаболеваний населения Удмуртии в 1946Ц2015 гг. (система ОНКО ) (SpO2), реография (РЕО), электроэнцефалограмма (ЭЭГ), температура (Т) реализован в различных моделях мониторно-компьютерных систем, прошедших длительную эксплуатацию в разнообразных клинических условиях (отделения реанимационные, операционные, неотложной кардиологии, палаты интенсивной терапии).
При научно-техническом руководстве и личном участии автора диссертации выполнены разработка и испытания компьютерных медицинских мониторов, комплексов и систем. В частности, - монитор компьютерный неонатальный МНК-01-НИОТК-Иж (рег. № 98/219, включен в государственный реестр медицинских изделий, разрешенных для применения в медицинской практике и к серийному производству, Минздрав РФ, М., 1999 г., доп. № 1Ц2).
Новизна и оригинальность технических решений подтверждена авторским свидетельством [52] и патентом [51].
Разработаны, изготовлены и испытаны на ФГУП ИЭМЗ Купол (г. Ижевск, 2000 г.) мониторы компьютерные медицинские: монитор анестезиологический компьютерный (МАК-01), монитор реанимационный компьютерный индивидуальный (МРКИ-01), реографический комплекс компьютерный (РКК-01); мониторно-компьютерная система реанимационная общего профиля (система МКС-ОНК-А ).
Рис. 8. Модель монитора компьютерного неонатального МНК-01-НИОТК-Иж Заключение В работе получены научноЦобоснованные методические и технические решения, направленные на конструктивизацию математических моделей классификации конечных объектов, базирующуюся на теории рекурсивных функций для первоочередного установления разрешимости моделей классификации и последующей эффективной вычислимости, обеспечивающей оптимизацию вычислительных затрат при аппаратно-программной реализации алгоритмов классификации, что способствует совершенствованию вычислительных технологий классификации конечных объектов и расширению практики проектирования аппаратно-программных классификаторов.
1. В работе впервые сформулированы и разработаны теоретические основы концепции конструктивизации при проектировании классификаторов конечных объектов, включающие компоненты инструментария вычислительных технологий: разрешимость, вычислимость и реализуемость, представляющие самостоятельный, но взаимосвязанный интерес результатами своих решений.
2. Рассмотрены проблемы классификации конечных объектов на общей методологической основе теории рекурсивных функций, тесно связанной с традиционными математическими понятиями вычислениями и числовыми функциями, что позволяет сформулировать критерии разрешимости и указать условия существования алгоритмов классификации и распознавания.
3. Обосновано первоочередное рассмотрение проблем разрешимости и вычислимости моделей классификации, которые на ранних этапах разработки теории и практики распознавания образов отодвигались на второй план. Доказательство разрешимости предопределяет конструктивные пути дальнейшего решения прикладных задач классификации конечных объектов.
4. Сформулированы и доказаны критерии (не)разрешимости проблемы классификации в моделях с конечными обучающими выборками и сигнатурами решающих предикатов, допускающих многоальтернативность, что расширяет область конструктивизации прикладных задач с дискретным описанием объектов.
5. Исследованы вопросы однозначной разрешимости и эффективной вычислимости в конструктивных моделях классификации с обучением и без обучения с использованием принципов распараллеливания, гарантирующих наибольшую вычислительную эффективность от схем принятия решений.
6. Впервые сформулирована и исследована модель симультанной (предельно быстрой) классификации конечных объектов, инвариантной по отношению к числу эталонов обучающей выборки и числу признаков в эталонах, что обеспечивает аппаратно-программную реализацию быстродействующих классификаторов.
Конструктивизация автоматной реализуемости классификаторов выполнена с учетом таких критериев вычислительной сложности алгоритмов классификации как минимальное описание конечного объекта и минимальное время вычислений.
7. Обосновано построение новых методов минимизации предикатных форм описаний конечных объектов, гарантирующих эффективность процедур вычислимости предикатов классификации при их компьютерной реализации.
8. Предложено впервые спектральное представление булевых функций, позволяющее реализовать эффективный алгоритм распознавания булевых функций по критерию компактности, обеспечивающему минимальную загрузку памяти вычислителя, что подкреплено полученными оценками сложности сигнализирующих функций.
9. Обоснован и разработан метод представления предикатами Радемахера всевозможных реальных изображений (точечных, текстурных, полутоновых), обеспечивающий синтез классификаторов отношений последовательно-параллельного действия с минимальными вычислительными ресурсами.
10. Разработаны и реализованы для ряда прикладных задач (дешифрование КФС, диагностика остеопороза, онкопатологий) методики и алгоритмы конструктивной классификации наиболее распространенных в природе объектов со сложноструктурированной семантически насыщенной информацией текстурных изображений, считающихся традиционно трудными для неконструктивных методов.
11. Разработана и практически опробирована в клинических условиях новая компьютеризированная наукоемкая технология медицинского мониторинга, позволяющая создать на единой информационной, инструментальной и технологической базе унифицированный ряд конкурентоспособных компьютерных мониторных средств для медицинских учреждений различного профиля. Встроенные вычислительные технологии медицинского мониторинга учитывают разнообразие методик анализа мониторируемых параметров и тенденции развития аппаратно-программных средств, включая создание индивидуальных банков пациентов, банков медицинских знаний, использование информационно-справочных, экспертно-диагностических систем и систем искусственного интеллекта, что повышает качество оказания медицинских услуг при снижении затрат на оснащение медицинских учреждений отечественными мониторными системами.
12. Достоверность и обоснованность полученных автором результатов и выводов подтверждается сопоставительным анализом между уже существующими и разработанными математическими моделями и методами.
13. Проведенные доказательные эксперименты, разработка и внедрение результатов исследований подтвердили продуктивность предложенной концепции конструктивизации.
14. Результаты работы внедрены более чем в 10 организациях и предприятиях, используются в выполнении НИОКР и в учебном процессе при чтении курса Дискретная математика в Ижевском государственном техническом университете.
Основное содержание диссертации отражено в следующих работах автора:
I. Монографии и учебные пособия 1. Калядин Н.И. Конструктивизация моделей классификации конечных объектов // Известия института математики и информатики УдГУ. Ижевск: Изд-во УдГУ, 2007. Вып. 1(38). С. 3Ц231.
2. Калядин Н.И. Основы теории алгоритмов и нумераций: Учебное пособие. Ижевск: Изд-во ИжГТУ, 2006. 68 с.
II. Научные статьи в центральных изданиях, рекомендованных ВАК РФ 3. Ицков А.Г., Калядин Н.И. О полноте алгебраического замыкания пространства распознающих операторов с тестовыми опорными множествами // Журнал вычислительной математики и мат. физики. М.: АН СССР, 1984. Т. 24. №4. С. 579Ц586.
4. Калядин Н.И., Леменков В.А., Липовецкий Ю.Л. и др. Комплекс автоматизированного дешифрования крупномасштабных космических фотоснимков // Геодезия и картография. М.: Геоиздат, 1991. №8. С. 18Ц23.
5. Александров Ф.М., Калядин Н.И., Липовецкий Ю.Л. и др. Автоматизированное изготовление издательских оригиналов карт // Геодезия и картография. М.: Геоиздат, 1990. №11. С. 36Ц38.
6. Калядин Н.И., Леменков В.А., Лосев И.Р. и др. Компьютеризация медицинских технологий // Медицинская техника. М.:
Медицина, 1996. №2. С. 21Ц24.
7. Калядин Н.И., Боталев А.П., Леменков В.А. Автоматизированное рабочее место врача-эндоскописта как основа компьютеризации эндоскопических исследований // Медицинская техника. М.: Медицина, 1996. №2. С. 34Ц36.
8. Ицков А.Г., Калядин Н.И., Ходырева М.Д. Статистический анализ медицинской информации по онкологическим заболеваниям // Медицинская техника. М.: Медицина, 1996. №2. С. 38Ц40.
9. Калядин Н.И., Леменков В.А., Лосев И.Р. Проблемы врачебного мониторинга больных и требования к разработке компьютерных мониторных систем // Медицинская техника. М.: Медицина, 1996.
№2. С. 25Ц28.
10. Калядин Н.И., Лекомцев В.Т., Сунцов А.А. и др. Диагностика эпилепсии в интерактивном режиме с использованием компьютерной технологии // Медицинская техника. М.: Медицина, 1996. №3.
С. 40Ц42.
11. Калядин Н.И., Белоусов В.А., Филатова С.В. Единый методологический подход при алгоритмизации и построении экспертных систем типа норма-патология в медицине // Медицинская техника.
М.: Медицина, 1996. №3. С. 6Ц7.
12. Калядин Н.И., Леменков В.А., Лосев И.Р. и др. Компьютерный монитор неонатальный // Медицинская техника. М.: Медицина, 1996. №3. С. 3Ц6.
13. Калядин Н.И., Леменков В.А., Коробейников А.В. и др. Разработка и опыт клинической эксплуатации мониторно-компьютерной системы отделения неотложной кардиологии // Медицинская техника. М.: Медицина, 2002. №1. С. 36Ц40.
14. Калядин Н.И., Кузнецов П.Г., Леменков В.А. Научные проблемы и задачи медицинского мониторирования // Медицинская техника. М.: Медицина, 2002. №1. С. 14Ц18.
15. Калядин Н.И., Леменков В.А., Коробейников А.В. Неинвазивный измеритель артериального давления // Медицинская техника.
М.: Медицина, 2002. №3. С. 30Ц32.
16. Калядин Н.И., Кузнецов П.Г., Леменков В.А. Компьютерные медицинские мониторы: состояние и перспективы // Медицинская техника. М.: Медицина, 2002. №3. С. 22Ц25.
17. Калядин Н.И. Нумерация конечных множеств для компьютерной классификации // Вестник Московской академии рынка труда и информационных технологий (МАРТИТ), 2004. №3(11). С. 64 - 69.
18. Калядин Н.И. Временная оптимизация решающих правил классификации // Вестник Московской академии рынка труда и информационных технологий (МАРТИТ), 2004. №3(11). С. 70Ц76.
19. Калядин Н.И. Преобразование Адамара-Уолша для эффективных вычислений спектров // Вестник Московской академии рынка труда и информационных технологий (МАРТИТ), 2004. №4(12).
С. 27Ц33.
20. Калядин Н.И. Симультанная классификация множеств конечных объектов // Вестник Московской академии рынка труда и информационных технологий (МАРТИТ), 2004. №4(12). С. 34Ц40.
21. Калядин Н.И. Классификация сильно слипающихся множеств // Вестник Московской академии рынка труда и информационных технологий (МАРТИТ), 2004. №4(12). С. 41Ц46.
22. Калядин Н.И. Конструктивизация в классификации образов // Вестник УдГУ. Математика. Механика. Компьютерные науки.
Вып. 2. Ижевск: Изд-во УдГУ, 2008. С. 188Ц193.
23. Калядин Н.И. Вычислимость в классификации образов // Вестник ИжГТУ. Вып. 3. Ижевск: Изд-во ИжГТУ, 2008. С. 127 - 129.
24. Калядин Н.И. Разрешимость в классификации образов // Вестник ИжГТУ. Вып. 4. Ижевск: Изд-во ИжГТУ, 2008. С. 169 - 172.
25. Калядин Н.И., Белоусов В.А. Симультанность в классификации бинарной информации // Вестник ИжГТУ. Вып. 4. Ижевск:
Изд-во ИжГТУ, 2008. С. 172Ц174.
III. Статьи в региональных журналах, сборниках научных трудов, а также материалы конференций 26. Калядин Н.И. Некоторые вычислительные аспекты в задачах распознавания булевых функций // Машинные методы обнаружения закономерностей: Материалы Всесоюз. симпозиума (5Ц7/04 - 1976 г.).
Новосибирск: ИМ СО АН CCCP, 1976. С. 128Ц138.
27. Белоусов В.А., Калядин Н.И. Алгоритмический подход к проблемам распознавания и классификации // Дискретные системы обработки информации. Вып. 4. Ижевск: Изд-во ИМИ, 1982.
С. 86Ц93.
28. Белоусов В.А., Калядин Н.И. Конечные модели и их применение к построению классификатора отношений последовательнопараллельного действия. // Дискретные системы обработки информации. Вып. 5. Ижевск: Изд-во ИМИ, 1983. С. 83Ц88.
29. Калядин Н.И. Алгоритмические и технические аспекты при автоматическом анализе текстурных изображений // Возможности исследования природных ресурсов дистанционными методами. Ленинград: Изд-во ЛГУ, 1986. С. 55Ц61.
30. Белоусов В.А., Калядин Н.И. Таксономия по связным областям как задача построения признаков для текстурных изображений // Дискретные системы обработки информации. Вып. 6. Устинов: Изд-во УМИ, 1986. С. 4Ц10.
31. Калядин Н.И. Автоматизация обработки фотоинформации // Материалы 2-го Всесоюз. совещ. по космической антропоэкологии (2Ц6/07 - 1984г.) Ленинград: Изд-во ЛГУ, 1988. С. 315Ц322.
32. Калядин Н.И. Автоматизация анализа малоразмерных малоконтрастных текстурных фотоизображений // Труды IX научных чтений по космонавтике. М.: ИИЭТ АН СССР, 1988. С. 138 - 142.
33. Калядин Н.И., Липовецкий Ю.М. Теоретико-игровой подход к классификации текстурных изображений // Труды IX научных чтений по космонавтике. М.: ИИЭТ АН СССР, 1988. С. 143 - 150.
34. Калядин Н.И., Белоусов В.А. Представление точечных изображений предикатами Радемахера // Дискретные системы обработки информации. Вып. 9. Ижевск: Изд-во ИМИ, 1989. С. 3Ц12.
35. Калядин Н.И., Белоусов В.А. Относительная полнота в конечных моделях // Дискретные системы обработки информации.
Вып. 10. Ижевск: Изд-во ИМИ, 1990. С. 5Ц12.
36. Калядин Н.И., Белоусов В.А. О задаче классификации множеств по классам эквивалентности / Ижевск, 1995. Деп. в ВИНИТИ 15.11.94, № 356 В95. 48 с.
37. Калядин Н.И., Белоусов В.А. Теория предикатов Радемахера и их применения / Ижевск, 1996. Деп. в ВИНИТИ 15.06.95, №45В96. 18 с.
38. Калядин Н.И., Белоусов В.А. Игровые решающие правила для отношений и распознавания конечных множеств / Ижевск, 1996.
Деп. в ВИНИТИ 15.01.96, №333-В96. 18 с.
39. Калядин Н.И., Белоусов В.А. Условия существования обобщенной симультанной модели распознавания изображений // Дискретные системы обработки информации. Вып. 11. Ижевск: Издво ИжГТУ, 1996. С. 20Ц25.
40. Калядин Н.И., Копосова Т.Л., Ходырева М.Д. Состояние и перспективы маммологической службы в Удмуртии // Маммология.
№4. М.: Изд-во "КАБУР", 1997. С. 15Ц24.
41. Калядин Н.И., Белоусов В.А. Алгебро-логические алгоритмы в распознавании, идентификации и классификации медицинских объектов // Вестник ПГТУ. Математика и прикладная математика.
Пермь: Изд-во ПГТУ, 2005. С. 61Ц66.
42. Калядин Н.И., Белоусов В.А. К вопросу построения медицинских экспертных систем // Вестник ПГТУ. Прикладная математика и механика. №1. Пермь: Изд-во ПГТУ, 2005. С. 113-119.
43. Калядин Н.И., Белоусов В.А. К вопросу существования симультанной модели классификации объектов // Вестник УдГУ. Математика. №1. Ижевск: Изд-во УдГУ, 2006. С. 151Ц160.
44. Калядин Н.И., Белоусов В.А. Об одном существенном условии в распознавании конечных множеств // Известия Института математики и информатики УдГУ. Вып. 2(36). Ижевск: Изд-во УдГУ, 2006. С. 113Ц116.
45. Калядин Н.И. Конструктивизация классифицируемых множеств // Вестник ПГТУ. Прикладная математика и механика. №1.
Пермь: Изд-во ПГТУ, 2006. C. 8Ц15.
46. Калядин Н.И. Нумерации в проблеме классификации // Вестник ПГТУ. Математика и прикладная механика. №1. Пермь:
РИО ПГМА, 2007. С. 51Ц55.
47. А.с. № 739595, СССР, М. Кл.2 G06K15/20. Устройство для отображения графической информации на экране электронно-лучевой трубки / Заболотских В.И., Калядин Н.И., Кацман В.Е. Заявл.
09.01.78, № 2568812/18-24; опубл. Бюл. 1980, №21.
48. А.с. № 734664, СССР, М. Кл.2 G06F3/14. Устройство для отображения графической информации на экране электронно-лучевой трубки / Заболотских В.И., Калядин Н.И., Кацман В.Е. Заявл.
05.01.78, № 2567256/18-24; опубл. Бюл. 1980, №18.
49. А.с. № 720430, СССР, М. Кл.2 G06K15/20. Устройство для формирования изображения на экране электронно-лучевой трубки / Заболотских В.И., Калядин Н.И., Кацман В.Е. Заявл. 02.08.76, № 2394579/18-24; опубл. Бюл. 1980, №9.
50. А.с. № 705485, СССР, М. Кл.2 G06K15/20. Устройство для формирования изображения на экране электронно-лучевой трубки / Заболотских В.И., Калядин Н.И., Кацман В.Е. Заявл. 11.05.77, № 2484520/18-24; опубл. Бюл. 1979, №47.
51. Патент № 2161905 от 20.01.2001 г. Электродное устройство / Калядин Н.И., Леменков В.А., Лагунов В.А. и др. Заявл. 29.07.99, № 99116409; опубл. Бюл. 2001, № 2.
52. А.с. № 25265 от 27.09.1999 г. Медицинский монитор / Калядин Н.И., Леменков В.А., Коробейников А.В. и др. Заявл. 16.12.99 № 99125594; опубл. Бюл. 2002, № 27.
Н.И. Калядин
Авторефераты по всем темам >>
Авторефераты по техническим специальностям