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

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭЛЕКТРОТЕХНИЧЕСКИЙ ИНСТИТУТ имени В. И. УЛЬЯНОВА (ЛЕНИНА)

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

ДУДКИ Н Алексей Кириллович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ИДЕНТИФИКАЦИИ ОБЪЕКТОВ ИЗОБРАЖЕНИЙ В СИСТЕМАХ МАШИННОГО ЗРЕНИЯ

Специальность: 05.13.16 — применение вычислительной

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ленинград — 1691'

Работа выполнена в Ленинградском ордена Ленина и ордена Октябрьской революции электротехническом институте имени В. И. Ульянова (Ленина)

Научный руководитель —

кандидат технических наук доценг Денисов Д. Л.

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

доктор технических наук Горский Н. Д. кандидат технических наук Коровацк"й В. П.

Ведущая организация—Государственный оптический институт имени С. И. Вавилова

Защита состоится « 1991 г. в

часов на заседании специализированного совета К 063.36.12 Ленинградского ордена Ленина и ордена Октябрьской революции электротехнического института имени В. И. Ульянова (Ленина) по адресу. 197376, Ленинград, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан « » е^М^и-! 19Э1 г.

Ученый секретарь специализированного совета В. Н. БАЛАКИИ

Подписано к печати 27.06.91 г. Объем 1 п. л. Тираж 100 экз. Бесплатно. Заказ 690.

Ротапринт типография ЛЭИС. 198320.Ленинград, Свободы, 31.

I ОШШ ПРАКТЕРИСТИКА РАБОТЫ

¿■^■упдпьнооть . Машинное зрение (МЗ) как комплексная научная ощшлина сформировалась лишь в последние 10 - 15 лет. ИЗ решает проемы ряда научных направлений; важнейшие среди ник - психофизические просы зрительного восприятия, цифровая обработка п анализ нзобраяе-й, архитектура экспертных систем и технология их разработки, инаене-я знаний. Кавдое из названных направлений представляет собой само-оятельную область исследований, использует своп ттодологягз решения дач, а твкге свои классы методов и алгоритмов. Эта многогранность шаемых задач, их сложность и актуальности для широкого круга прило-еий делает МЗ одной из наиболее перспективных научных дисциплин.

Решение задачи интерпретации визуальной сцеЕЫ потачает процесс оляции объектов, их идентификацию (узнавание), установление снысло-х отношений мезду там и проведение умозаклотенкй относительно со-ркания сцены. Таким образом, базовой процедурой для систем понимания обращений, ориентированных на решение "интеллектуальных" задач зре-:я, является узнавание объектов. Существует целый класс задач, реше-:е которых полностью определяется процессами выделения и пдонгцфяка-л отделышх объектов. Примерами могут служить такие важнейшие облас-[ прплокотегй, как анализ диотанцаонных изображений Земной поверхноо-проточенная дефектоскопия, контроль за производством печатных ют, шжробиологичесий анализ и т.д. Большой объем алфавита иденти-ищруетж объектов, их содержательная интерпретируемость, неоднород-й качественный состав и значительное количество классификационных шзнаков заставляют рассматривать задачу идентификации объектов как ¡ысстоятельнув проблему МЗ, решение которой требует привлечения нн->рмациовной технологии искусственного интеллекта (ИИ). В ряде работ I.Л.Горелик и др., 1935 ; В.В.Александров и др., 1990) в связи ор [ачитёльнкм расширением сфер приложения автоматического анализа визу-гьной информации подчеркивается необходимость разработки новых мате-1тическах методов и алгоритмов принятия решений в системах анализа и шимания изображений, а такпе создания прикладных программных систем шинного зрения на основе представления и использования экспертных ганий о ропаемой задаче.

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

объектов, но и в их содержательной интерпретации, а также объяснен принятых решение .

т]алг. радоти - исследование и разработка методов и алгоритмов Щ нятия решений в машинной зрении на базе сопоставления наблюдаемой I деоинформации о моделями объектов. В диссертационной работе решают следующие задачи:

1. Исследование алгоритмических аспектов сопоставления наблюдг .(¡ой видеоинформации с моделями и трансформации математического баз! этого механизма при переходе от "низших" (сигнальных) форд IIpэдcтaвJ ния к "высшим" (символическим);

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

- разработку формальной модели предметной области, учитывал свойства формы объектов и отношения "род ' - вид", "часть - цело! "сходство" меаду объектами;

- разработку структуры представления знаний о предметной области;

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

- разработку алгоритма сопоставления описаний наблюдаемого и этало: ного объектов. .

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

мантической однородности предметной области и применение метода в даче идентификации нормальных хромосом человека;

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

5. Решение прикладных задач.

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

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

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

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

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

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

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

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

цяшюота работа. Реализовала программная система яентпфикацаш двумерных геометрических объектов в среде кокро-УАХ/ТНЗ, эзволяюцая проводить идентификацию объектов по форме в содержательных грминах.

Реализован пакет прикладных программ библиотечного типа в среде СМ ЗМ ЙБХ, позволяющий проводить вычисление метрических, параметрических структурных признаков формы областей изображений.

Спроектирована и реализована в вычислительной среде НАИБОМ-гАВ рограммная система, позволяющая решать задач у каряокширования нор-альных хромосом человека.

Диссертационная работа является составной частью исследований, вы-олненных на кафедре МО ЭВМ ЛЭТИ в 1985-1991 гг. в рамках хоздоговорах НИР ВД-22, МО-32, МО-41, МО-63, а таккэ совместных исследований с нститутом цитологии АН СССР по программе "Гечом человека", шюведен-[IX в 1989-1990 гг.

^тпрлщгъ работа. Основные положения и результаты работы были пр ставлеёы и обоуздены на 2-й ВсесоюзноЗ конференции "Автоматизировав системы обработки изображений", Львов, сентябрь 1985 г., Регнональ конференции "Обработка изображений п дистанционные исолэдовалил", восибирск, ноябрь 1987 г., 2-й Республиканском семинаре "Проблэкы. с дашя систем обработки, анализа и распознавания изобрваэЕЕЗ, Тапка ишь 1989 г., 3-2 Всесоюзной конференции "Автоматизированные сист обработки и анализа взобраЕвяпа", Ленинград, октябрь 1939 г., Иззду родной конференции "ИокуостЕснынЗ штелЕозяе-пра^здэнноэ цр^зяеш: Ленинград, .«прель 1990 г., ШэднародаоЗ коаВороадап "ОЗрабогаз г брааений н дастанцкошшэ исследования"» Новосибирск, август 1990 1-й Всесоюзной конференции "Геном человекз-90", Шреславдь-Залзссх октябрь 1990 г, иесраспублжшской конференции "Обработка растра изобрекений в автоыатичес::нх. системах", Тула, ишь 1991 г.

ПуйЕпяиггт. По материалам диссертации в открытой печати апублш«: но 17 печатных работ, список кот'орш приведен в конце автореферата, струтг-турч р-г^уш. ;шссертацнонная работа состоит кз введения, г глав, заклзочения и пяти щшюпэееЗ. Основной токся работа пздеагн 145 страницах ызшнописного текста. Работа содержат 58 рисунков ; таблиц. Список литература вкявдазт 109 наименований.

. • СОДЕИШШЕ РАБОТЫ

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

Пщшл_ЕИаз. посвящена анализу основных принципов принятия реш в аз.

Рассматривается концепция многоуровневого представления и обра кн видеоИЕфэрмашш в СШ. Исследуются четыре уровня: иконический, ментированныа, геометрический и реляционной. Наличие нерариш н ставлэния ставит проблему синтеза способов управления взагшодейст разнообразных процессов обработка как внутри уровней представления деоивформацш, так и при переходе от уровня к уровни. Днелазиру основные споообн организации управления процессом принятия рзше стратегии управления "снизу-ввэрг" (под управлением данЕ "сверху-вниз" (под управлением моделэг), комбинированная и гетерг таская стратегии. Проведен обзор п категоризация знаний, использ5

5 СМЗ. Выделены семантические и управляющие знания как категории, ¡редотавление и использование которых необходимо при решении задачи эдевтиЯикации объектов.

На основании анализа работ (М.М.Боягард, 1967 ; Н.Д.Горский, 1989) формулируется задача идентификации двумерных объектов как проблема высокоуровневого зрейия (зрения на основе знаний). Система идентификации цолта уметь выносить заключение о типах объектов, об их характерных свойствах и отличительных признаках. Задача включает в себя следующие подзадачи: >

1. Предо1авленпе семантической категории знаний о решаемой задаче.

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

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

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

вторая глава посвящена исследовании основополагающего принципа принятая репэпий в СИЗ - различим формам сопоставления наблюдаем >я и вталокной информации, я такяэ разработке метода и алгоритмов сопоставления в задаче идентификации двумерных объектов по информации о форме.

Мокно выделить три основные подхода к реализации механизма сопоставления наблюдаемых видеоданных и моделей, змеидихся в распоряке-нии системы:

1. сравнение логически совместимых структур списаний;

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

3. проверка соответствия структуры видеоданных набору правил ее Хсрш-ровашя.

Для яаздай из перечисленных форы сопоставления анализируются пряг-

б

оущие ей последовательности преобразования входной видеоинформации ыатемафчеокие модели принятия решения. Первая форма наиболее адекваз на решаемый задачам в оилу ее универсальности, допускающее интегращ процеооов обработки различных уровней. Исследуется еволзеция задач методов принятия решений в рамках первой формы сопоставления при перс ходе от низшая уровней представления видеоинформации к выежз.:. На о< новании проведенного исследования разработан цзтод вдентсфпшщш дез мерных объектов по информации о <£орлэ. В качестве предметной облаем рассматриваются разлишшэ геометрическиа ксвграгурацЕП, ташэ кг "прямоугольник", "трапзцга", "звезда", "гантель" е др. (13.И. Бснгар; 1967). Основные составляющие метода:

- структуризация предметной области посредством определения па ыногг стве эталонных объектов отнсшэниЭ "род-вид", "часть-целое" "оходство";

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

- разработка структуры представления знаний фреймового типа для фоз мализации информации о предаатно2 области;

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

Пусть 0 = (а.,, и2, ....в^) - ыпогэотво эталонных объемов. Обозш

чем через Сх^}, 1: = 1,___,11 - шоазэство Признаков формы, нэобходош

для опиоания всего множества эталонов. Првмэрами признаков формы ког! быть следуицие характеристика: "выпуклость", "параллельность сторон! "наличие прямого угла при вэраине", "существование чаоти-переаейка' "симметричность", "количество частей-дыр", "удлинешость" п т.д. Пр знаки могут прикипать значения различных типов: логические, воцес: венные, перечислздга. Каздоиу из объемов и^ мокао поставить в соо5 ветотвие «Г^ = к^*)..., } - множество ноазров признаков фо]

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

__£ (л

лиэируемый объеггг щжиедлеглт классу а^). Объедаашв соа интервалы Д^" по 1, получил совокупность СЕ^}, к = 1 мно^оотв допустаде знс

чешй признаков, представляшгкг в обдаы случае поминальные ехали: ^к = 1-1 ПрэДстаЕ1Ш множество признаков в векторной форме:

= .....г.,). сформируем г - Б^Т)^.. .уД, - множество состояний

зте:т пдэптгфпсвцйи. В этом случае какдоа г.гооггескзо «7^, 1 = 1....Д, -эдедяет проекции вектора X нэ осп Ц1' Л'^1'.....

х(1)=й> (1) ,(1) ,(1) Х • 2(1) 6 •

0 г'*^- гпсяоство всех та ¡гаг проекций.

СясзОохвша 1. Пара сталстпга сбьехясз и^, а^ пранадлегат ю-нааозсму отзсзекйю ЕН1 £ Охй тогда я только тогда, когда

гдэ о^— объект - предок, обмкт-паслэдгзпк. Прп сспсстсзленяи списания наблюдаемого объекта с эталонами отпоено родо-видовой иерархии указывает "вертикальное" направление сбхо-структуры эталонов. "Горизонтальное" направление обхода ногет бнть брано за счет учета отношения сходства. ОтюеОелеихю 2. Пара объектов удовлетворяет огнсшэнш) сходства тогда н только тогда, когда существует группа ключевых

О с-

язнаков г,г , 1 = 1,2,... , <5 л ОТ., таких, что

».(1) ( ^ 5 N и Т»Т> чг(1) 1-ГТ л ТТЛи-я Г» . П

* / ' * , » —Т. ——I .<.,_ .Ц...1 , и!

¡ответственно, р - расстояние, определенное на икало и, , д. -порог

4 К1

мдстаа для птязпака х,, , 1 = 1,...,!,,. -'м

Определенна 3. Пара объектов удовлетворяет отнесению "часть-целое" ЕН3 тогда и только тогда, когда существует признак х,,: кеЛ^

I о

к $ "

Тегам образом, отношение "часть-целое" огрзказт еозыогяость ошса-1Я сбъзэта через форму его частей и подразумевает рекурсивные Зрацения к процедуре идентификация с выделенная! частями объектов.

В результате модель предметной области представляется четверкой *= (О, ВН.], Ей2, Ей^) > Ей^е 1=1,...3, вклтатщей как описания талонных объектов О, так и определенные выше стпсяеиия. В качестве орыализма представления знаний о предметной области был выбран фрейм Мавдермот, Чарниак, 1985, Г. А.Поспелов, Д.¿.Поспелов, 1385). азработана структура .обладающая олвдувдша свойствами:

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

.объектов Объединение осуществляется за счет слота "наследии моделирующего родо-видовую иерархию на С .

2. Эталон 01 ("корневой" эталон) представляется фреймом, все су которого пусты, за исключением слота "наследники". Эталоны термин: ного'уровня представлены фреймами с пустыми слотами "наследники"; слоты заполняются при расширении базы знаний системы.

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

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

5. Слот "сходство" представляет информацию об объектах,находяп в отношении сходства с данным.

Сопоставление описаний еталонного и наблюдаемого объектов осуп вляется как процесс означивания фрейма. Первоначально фрейм пуст ( чевия переменных х^ слотов "ограничения" для все! объектов и^ не с делены). В процессе работы алгоритма сопоставления происходит оз! вание 8тих переменных посредством инициализации процедур вычислен: слотов "процедуры". Полученные значения передаются как параметры цедурам частичного сопоставления из слотов "процедуры". Последовав ность означивания подфргймов (фреймов), представляющих информацт объектах а^, определяется наполнение!! слотов . "наследники" "сходство", в зависимости от результатов сопоставления на текущем вне иерархии. При удачном сопоставлении с еталоном и^ (в процесс начивания подфрейма объекта и^), выносится решение о типе наблада объекта.' Окончательное решение принимается по означенному подф максимального уровня вложенности.

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

Рассмотренная в главе 2 схема сопоставления в задаче идентифи двумерных объектов на основе''информации о форме оставляет откг некоторые принципиальные вычислительные проблемы принятия решеш наиболее существенным из них относятся проблема выбора равноз!

гипотез о типе объекта (указанная проблема особенно актуальна для задач, в .которых предметная область слабо структурируема, либо не поддается структуризации), проблема выбора шкалы для значений признаков, связанная напрямую с вычислительными погрешностями методов дискретной геометрии, а танке проблема шумов, приводящих к неоднозначности ди-скриминантных свойств признаков, что. ставит вопроо о необходимости применения статистических методов принятия решений. Указанные причины заставляют выделить проблему принятия решений через выдвижение и проверку гипотез о типах' объектов в самостоятельное направление исследований. С точки зрения методологии распознавания (Фишер, 1989), целью процессов выдвижения и проверки гипотез является направленный отбор наиболее вероятных моделей-кандидатов на сопоставление из общего множества эталонов. Суть указанных процессов - вычислительная реализация механизма предположения о типе объекта (в отличие от утверадения) с сценкой его достоверности. Психофизиологической предпосылкой процессов выдвижения и проверки гипотез является необходимость перестройки внутренних свойств системы зрения в зависимости от наблюдаемых видеоданных (Пспф, 1966), что и обусловливает использование комбинированной стратегия управления "снизу-вверх" и "сверху-вниз" в процессе принятия решения.

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

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

еого роиетя .

2.;Этап Еэрзфиканкк гипотез осуществляется в порядке, определяете вычисленными ЕНЕчевияыи правдоподобия. Процедура Бзрп&гкащш соатве1 ствувщэй гшотезн строится на основе детального структурного анализ форьш и яркости объекта, выраконного в установлении соответствия иэад структурнпхх влонентагш наблюдаемого объекта и модели, а та:с,е оцеш согласованности взаимосвязей шэд виши блементшп. Б случае устано! лэяая факта согласованности подструктур объекта к {¿одели выносится ш лосательное рэиение о кзпо данного объекта, соответствующем рассыагр; ваемой гипотезе.

Пусть 0 = (И.,, 0^) - алфавит классификации (инокество ет!

ленных объектов некоторой предметной области). Рассмотрим вектор пр

ГР

знаков ХА= (г*, .....х^), где казддй пз Хд отражает свойство раем:

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

Д- I

где Р,. - ещшораая вероятность Ь-й составдящэй: емзеи;

К® = (н^,...-вектор математического ожидания к~й составляют сызю

г2

О ... а^ J

днагональаая матрица коварашш к-й соек лящзй смэсл,' к.= 1,2,..-.,Д. Тогда Байесовское рашавдее правило «огне представить в следуете« вид Вт. : X -» ьь , если и1п г,, = г, ,

1 2о к к о

где гк = 1/2 * п|[( х^ - 4 + 1л 4 ] - 1л Рк ,

В = (а^,... - алфавит классификации.

¿нализ признакового пространства часто позволяет выделить прав]

покрытия областей классов гиперпараллелепипедами в подпространс

признаков, размеры которых, а такке координаты подпространства опре,

дяатся в процессе обучения. Другими словами, могло выделить промз:

точный алфавит классЕ^жации О8 = (и* .....а* ), |ы*|« К. М*

¡¡с % * ' ** ^

а^ л и^ * в, где каздый из классов ии с достаточной степенью достов

эоти покрывается гиперпараллелепипедами. Таким образом, в этом случае эшавдэе правило имеет вид:

Br2 : X -» ü^ , если X е^и Hj ,

рП - *(и> „ А(т)„ Ли) д(ш) - гт(в) (и) , це Bf - А1 « Д2 х ....Aj, . Д-j - l-j min . Xj ^j.

к1 : XsR1'1, m=1,2,'...,M; II * K.

Совместное примепенго правил Er^, ESg позволяет провести рактическа безоппбочную власскфпкацпг) в промзпуточно?! атфэштэ * - (0^ ) И'получить гипотезу О тппо Объекта {Pjj.—» öj, 6

такав правдоподобие етой гипотезы .

Фактически, применение резака,ого правила Ег^ поолэ йг^ означает тсев всех недостоверных гипотез, попавши в число наиболее провдо-одобных вслэдстше ошибки при вьганслешш величины г.,. Крсмэ того, азыер промежуточного алфавита аи устанавливает количество гипотез, одлевэдах верж'шмцж!, решая текли образом проблему остсношог процео-а.

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

ai. существования P^Cf, , Tz.....0^), где У- характеристика ыэото-

:олог:ення данной подструктуры (расстояние до центра тяезстп объекта,

iepa близости к границе и т.д.), а ^.ig«___параметры (пороговые

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

LP^ = i&f I^Y, I1,T2.....,

де Qj,- количество предикатов, характеризущих еталонный объект к-го тага üjj , установит факт согласованности описаний наблюдаемого обье1йа [ эталонного объекта.. Таким образом, решающее правило, па основании :оторого строится процесс верш&кацип гипотез, представляется в следу-a,su еэдэ:

Er3 : J?-* а,, , если LPt(F) = true. ■де Р - наблидаенсй объект; LP,,.- логическая функция определенного "-jhsd ¡ида; Kjj.ea .

Рассматривается применение разработанпого метода з задаче кзриотхг-шрозанзя похвальных хроцосом человека. Традициошча подход к рэпонпга

данной задачи базируется на методолопш статистического распознавай образов и ве использует экспертные патогенетические знания о предме ной области (Ландстин, 1980; Воссеполь, 1987), что приводит к негис кии решающий правилам и требует колоссальных затрат на проведен этапа обучения и настройки параметров системы. В то же время, заде караотишрования хромосом является характерной задачей идентификаг двумерных объектов. Решение задачи идентификации хромосом осложняв! рядом факторов (шумы, микроскопические размеры объектов, неравнсморг освещенность, разнородное качество препарата и т.д.). Наличие указ': ных факторов обусловливает необходимость приыэнешя метода идентафп ции на осноыз выдвижения и проверки гипотез. В процессе применения ^ тода были предлоаены следующие алгоритмические решения:

- выделение объектов осуществляется на основе алгоритма быстрого к; стер-анализа изображений (Д.А.Денисов, 1986), аккумулирующего идеи I раметрического и Iнепараметрического мастеринга, а также методов по] говой обработки;

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

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

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

управление процессом сопоставления реализуется по прзнщшу псмбнпй-ип стратегий! "сверху-вниз" л "снизу-вверх". Прп етом процессы сетсп-8цяя п вычисления признаков протекает в традацаанной послэдовотсльео-ти под управлением "снизу - вверх", тогда как идентфзкацая осветляется посредством сопоставлевпя с- модель» со прянцгшу "cEepsy-ггг^з"

422S2E223_Eii5ll2l посвяцона разработке л охаяертеставьЕСУ? поохо^а-¡аяпа программной спотсш ндсзззйшащаи явунорпых объоктоз но еп о фор«э, рэштуЕдоЗ сдгогата означивания фрейма прогйтггс.'! ойгсэ-зз. Вши ретегш сладуз^то зодачл:

• реадазецая структура спзсгаия еталопшв • объектов (содерлгсй !тг-Зо2>~ :сцгпэ о яр-эдг.согнсП облаотз) з рлде ФзОлоеш: структур. з

цгскозсЗ пемяга ЗШ;

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

- разработка и уэалкзыся псдепотеин бспоотсзлвн^л спгошЛ

еиого я эталонного оСьсжсз, мзшапулзругпюЗ со ospysryps."; srvermi сппсепзЗ н зшпцгшшйругя;®!! згшаявшэ цроцэдур гзтасдетггя

фор.и наблюдаемого оводагтэ;

- разработка и роггпкяля подстоте>га объяснения п коррэгасга, зуирй инфоруздаонниз гшгзз?й>2о о подьзозателда и яро?око,с7р;/~-гл

дни идетвсЗявацва. Использовалась тшгологая конструкровкгия с;кпзуг-ннх систем анализа ЕзобрггзэЕЕй (В.В. Александров в др., 1937).

Все програк-ы реаяззовспа з шчя&епэльясЭ среде кзхрэ- ТЛУП'З на языках ПАСКАЛЬ и OOFIPAH - 77'. Отдельные подсистема порвнесзнц в зкгчн-слительну® среду RSI C?J БШ. Эксперименты показала работоспосоЛлость данной щюграшнзЭ cz crew. В со объекта, прэ дот азленныо нз тестовых изображениях,' баш иденифщированы правильно. Исояздсвссто «ктекги пдентификацап на реальных кзобракетаях прэдотавляз? порсяо:таноэ направление работы.

П-22Л2_ХЛ22а посвядена разработка я експорихоптальпому иослэдоваиэ програг-ашой системы кариотшщрозеашя портальных хрсаооом человека в вычислительной ерзде СЕК !liGISCAH-2iH. Система реализует штод пдзетп-фикащл на основа выдвижения н проверки пжотоз о типа объ sire а., разработка программной системы проводилась в соответствии о прпвщшемг модульного програг&зровення о нспользовашеы стратегия -¡исходящего про-

актирования на языке ПАСКАЛЬ. При реализации была использована библиотека прикладных программ, входящая в состав ПО СВК ВШЯ5САН-2АК. Бьш разработаны подсистеш выделения объектов, вычисления признаков объектов, принятия решения и отображения результатов. Каздая подсистема организована в форда библиотеки прикладных программ, логически независимой от остальной части системы. Информационный интерфейс мевду модулями подсистем организован как процесс замены формальных параметров н; фактические. Существенное внимание при разработке программной систем: уделено информационному интерфейсу с пользователем. Реализованы про грашные средства взаимодействия с оператором с использованием свето' вого пера. Пользователь получил возможность корректировать результат; работы каздой из функциональных подсистем. Система была апробирована ; Институте цитологии АН СССР и показала хорошую работоспособность в се рии экспериментов, проделанных на препаратах института. Результат окспериментов (средняя оценка верша решений - 89,4 %) сравнимы с ре зультатахш, показанными на тех ае препарата^ системой ШСКв, входяще в состав ПО СВК ЦАИБ011'Ь2АН. В настоящее время система проходит ппнт ную эксплуатацию в Институте цитологии АН СССР.

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

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

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

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

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

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

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

7. Разработан комплекс программ вычисления геометрических и яр-костных признаков объектов изобракений.

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

Публикации по теме диссертации:

1. Денисов Д.А., Дудкин А.К., Плакош М.В. Представление и обработай видеоинформация в системах машинного зрения// Изв. АН СССР. Тех. кибернетика. - 1989. -N.5.- С.205-228.

2. Денисов Д.А., Дудкин А.К., Пяткга Б.П. Цифровой анализ изобранений. Методы описания геометрических структур.- Новосибирск: ВЦ СО АН СССР, 1987. - (Препринт 747).- 54 С.

3. Денисов Д.А., Дудкин А.К., Пяткан В.П. Структурные методы описания объектов изобрагсзпй?.-Новосибирск:ВЦ СО АН СССР,

19S8.-(Препринт 799).- 40 С.

4. Денисов Д.А., Дудкин А.К., Меденников П.А. Алгоритм вычисления геометрических характеристик изображений, представленных квадродере-вьями// Изв. ЛЭТИ : Сб. науч. тр./ Ленингр. електротехн. ип-т им. В.й.Ульянова (Ленина).-Л.: ЛЭТЙ, 1986.-Вып.377.- С.70 -77.

5. Denisov D.A., Buüüin A.K. Knowledge-Based Visual Object Identlii-oatlon// Abstract ol рарегз Int. Coni. Artlf. Intell. - Industrial Applications. Leningrad, 15 - 19 apr. 1990. - Leningrad: LIIAN, 1990.-PP. 290 - 295,

6. Дудкин A.K. Система идентификации двумерных объектов на основе признаков форыы//Обработка изобранений и дистанционные исследования. (0ЙДЙ-90):Тез. докл. Ыевдунар. конф. ,19-21 авг. 1990 г., Новосибирск.-Новосибирск,1990.-С. 82- 84.

7. Дудкин А.К. Система, интерпретирующая двумерные геометрические конфигурацет//Изв. ЛЭТЙ: сб. науч. тр./Ленингр. влектротбхн. ин-т им. В.Й.Ульянова(Ленина). - Л.:ЛЭТИ, 1990,- Вш.423.-С. 103- 106.

8. Денисов Д.А., Дудкин А.К. Метод идентификации визуальных объектов и его прялоаение в цитогенетике //Автоматизированные системы оора-

ботки изображений (АСОИз-89) :Тез. докл. III Всесоюз. конф.,24-26 cei 1S89 Г., Ленинград.- Л., 1989.- С. 155

9. Денисов Д.А., Дудкин А.К. Методы описания геометрических отрут пзобретений// Автоматизированные системы обработки изобракений (ACOi Вб): Тез. докл. II Всесоюз. кон®., 5-7 сент. 1986 г., Львов.- Ь 1986.- С. 15 - 16.

10. Алгоритмы и программы вычисления геометрических структур изоб! сений/Д.А.Денисов, А.К.Дудкнн, П. A.Meденников, Н.Н.Садыкова//0брабо1 изображений и дистанционные исследования (0ЙДИ-87): Тез. докл. Реи нальной кон$.,10-12 нояб. 1987 г.,Новосибирск.-Новосибирск,1987.-С.£

11.Денисов Д.А.,Дудкнн А.К. .Садакова H.H. Программный комплекс ; задачи списания геометрических структур изображений// Изв. ЛЭТИ : с науч. тр./ Лэагнгр. влектротехн. ин-т ем. В.И.Ульянова (Ленина). - I ЛЭТИ, ,1983.-ВШ.394.- С.66 -70.

12'. Дудан A.ív, ©атькан И.В. Разработка библиотечного пакета про '¿¡¿.•и вычисления геометрических-признаков изобрааений//Изв. ЛЭТИ : с науч. тр./Левшгр. влектротехн. ш-т ем. В.И.Ульянова (Ленина).-Л ЛЭТИ, 1989.-Вып.415.- С.101 -104.

13. Денисов Д.А.,Оркни A.B. .Дудкпн А.К. Иерархические ыодульно-пр дукцасниые ыодали для идентификации объектов ЕзобраЕений//Проблеш с здания csoreïi обработай, анализа и распознавания изображений:Тез. док II Республ. ешзн.,6-8 лшя 1989 г., Ташкент.-Таккент, 1989.- С.21-2

14. Денисов Д.Д., Дудкин А.К., ©атькан И.В. Внчисление геометраче izn " характеристик объектов изображений/ Г0СФЛП. - и ГР 5089000110 $0.05.0053// Алгоритмы и программы .-1S39 Г.-Н.8.- С.8.

15. OHILD - система автоматического шализа хромосом человека на о нова Бконоретыж знаний/ I.A.Денисов, А.К.Дудан, С.Е.Мамаева, К.С.По, лесиыз, Л.Г. Савельова, Э.Я.Эноон// Геном человека - 90: Тез. док I Всосою. копф.,8-12 окт. 1990 г., Перославль-Залесский.-М., 1990. С.204 - 205.

16. Денясоз Д.А.,. Дудкин А.К.,Савельева Л.Г. Информационная технол гея мйЕлНЕого зрения в анализе и распознавании хромосом// НОВИНТЕХ 1991.- Н.2- С. 39-47.

17. Дудкин А.К. Система вдентЕфикациа нормальных хршооо» человека Обработка растровых изобраааний в автоматических системах: Тез. докл мвЕреспубл. конф., 4-6 есня 1991 г., Тула. - Тула, 1991.-С.108-110.