Математическое моделирование процессов визуального восприятия и распознавания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

Ь Г о

2 1\ НО? На правах рукописи

УДК 519

Козлов Вадим Никитович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ВИЗУАЛЬНОГО ВОСПРИЯТИЯ И РАСПОЗНАВАНИЯ

Специальность 01.01.09 - математическая кибернетика

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

Москва - 1997

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова

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

академик РАН, доктор физико-математических

наук, профессор

Ю.И.Журавлев

доктор физико-математических наук А.С.Подколзин

доктор технических наук, профессор А.Б.Фролов

Ведущая организация:

Институт вычислительной математики РАН

Защита диссертации состоится 19 декабря 1997 г. в 11 часов 00 минут на заседании Диссертационного совета Д 053.05.38 при Московском государственном университете имени М.В.Ломоносова по адресу: 119899, Москва, ГСП, Воробьевы горы, МГУ, факультет ВМиК, аудитория 685.

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

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

Ученый секретарь Диссертационного совета профессор

Н.П.Трифонов

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

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

Известны работы, в которых предпринималось изучение поведения и связанных с ним явлений и процессов с позиций математики. Можно указать здесь на работы А.Тьюринга, Дж.фон Неймана, А.А.Ляпунова, С.В.Яблонского, А.Н.Колмогорова, Г.И.Марчука, и

др.

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

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

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

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

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

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

2. Предложен и развит новый подход к кодированию изображений. Доказано, что условие совпадения ¿-эквивалентности двух плоских изображений и их аффинной эквивалентности выполняется только при к = 3. Показано, что это позволяет просто и эффективно распознавать плоские изображения, отличающиеся друг от друга произвольными аффинными преобразованиями Аналогичные результаты и алгоритмы распознавания представлены для объемных изображений.

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

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

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

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

Апробация работы. Результаты работы неоднократно докладывались на Всесоюзных конференциях по проблемам теоретической кибернетики, на Международных конференциях по проблемам теоретической кибернетики, на Международных коференциях по интеллектуальным системам и компьютерным наукам, на конференциях в Берлине и в Зуле (Германия), на Ломоносовских чтениях в МГУ, на семинарах в МГУ по математическим вопросам кибернетики под руководством член-корр. РАН С.В.Яблонского, по теории автоматов под руководством академика АТН РФ В.Б.Кудрявцева, по механике и управлению движением роботов под руководством академика РАН Д.Е.Охоцимского, в Вычислительном центре РАН на семинаре

под руководством академика РАН Ю.И.Журавлева, на других конференциях, школах, семинарах.

Публикации. Основные результаты диссертации опубликованы в работах [1-24], список которых приводится в конце автореферата. Структура и объем работы. Диссертация состоит из введения, пяти глав и списка литературы. В первой главе - пять параграфов, во второй - три, в третьей - два, в четвертой - четыре, и в пятой - три параграфа. Объем работы - 211 страниц. Список литературы содержит 42 наименования.

Основное содержание работы

Во введении сделан краткий обзор основных результатов диссертации.

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

Блок восприятия и кодирования представляет ситуацию среды в виде некоторого кода. Код ситуации - это пара < М, Т > множеств, где М интерпретируется как множество объектов, из которых состоит ситуация, а Т - как множество чисел с индексами, характеризующее "взаиморасположение" объектов из Т.

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

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

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

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

Близость между ситуациями вводится следующим образом. Пусть даны ситуации А =< МА,ТА > и В =< Мв,Тв >, ||Мл|| = п, ||М*|| = тп и п > пг (||Л/„|| и ||Мв\\ - мощности множеств МА и Мв). Рассмотрим отображение ф : Мв —Мв (если п < гп, то рассматриваем ф : МА —> Мв)- Основываясь на содержательных соображениях, можно ввести некоторый 1} = р;,г € (1,...,./У) класс функций близости, каждая из которых учитывает те или иные особенности ситуаций при оценке их близости. При этом полагаем, что для каждого г каждому элементу х кода любой ситуации приписано неко-

торое число > 0 - вес этого элемента при оценке г-ой близости. Совокупность весов на элементах ситуации 5 обозначим через ^,(5') и назовем распределением г'-го веса по ситуации 5. Будем полагать, что р,- = р,(Л, В, ф,^(А),^(В)). Затем над классом V введем некоторую "интегральную" функцию близости, учитывающую в совокупности свойства, оцениваемые отдельными функциями из этого класса. Мы полагаем класс и состоящим из трех функций рьрг и рз. Функция р\ оценивает количество и значимость сопоставленных друг другу при данном отображении ф элементов из множеств Ма и Мв■ Функция рг оценивает число, однотипных, одинаковых элементов множеств Ма и Мв, сопоставленных друг другу, с учетом значимости этих элементов. Функция рз оценивает сходство во взаиморасположении объектов, из которых состоят ситуации А и В.

Каждая из функций РьР2,Рз задается системой положений. Эти положения получаются из содержательных соображений. Показано, ЧТО функции Р1, Р2 И Рз могут быть только монотонными функциями от аргументов некоторого специального вида (теоремы 1.1, 1.2, 1.3). "Интегральную" функцию Р^ = Р{Рх,Р2,Рз) определяем как РУ = Р1 + Р2 + Рз ■ Обобщенной близостью (или просто близостью) между ситуациями А и В называем величину Р(А,В) — тахР^, где максимум берется по всем возможным отображениям ф : Мд —+ Ма-

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

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

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

Концепция, положенная в основу модели главы I, позволяет с

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

В последующих главах (П, Ш и IV) схема, на макроуровне очерченная в первой главе, более подробно изучается применительно к зрительному восприятию. Это связано с особой ролью воспринимаемой зрительно информации для живого существа. Для человека, например, эта информация составляет, по некоторым оценкам, до 90% от всей сенсорной информации. Различные стороны зрительного восприятия активно изучаются биологами и психологами (работы Е.Н.Соколова, Д.Марра и др.)

В целом распознавание изображений является частью проблемы распознавания образов. В этой области ведутся, интенсивные исследования. Можно указать на широко известные работы Ю.И.Журавлева, В.Б. Кудрявцева, и др.

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

Назовем двумерным изображением конечное множество точек на плоскости. Перенумеруем некоторым образом точки изображения А так, чтобы номера были попарно различны. Обозначим через Мд множество этих номеров. Пусть 5тпк и 5*зр - площади треугольников с вершинами в тройках точек с номерами т, п, и и к,а,р и пусть Ртпи,к>р = 8тПи/Бк1р- Полагаем, что порядок номеров в тройках не важен, сами тройки различны и при = 0 значение ртПи,к!р не определено. Множество индексированных чисел ртш,к$р Для всех таких пар троек обозначим через Уд. Код изображения А - пара < Ма,Та >•

Изображения, все точки которых расположены на одной прямой, не рассматриваем, поскольку код для них не определен. Изображения А и В с кодами < Ма, Та > и < Мв,Тв > назовем эквивалентными, если существует такая биекция ф : МА —1• Мд, что для любых ш, п, и, к, из МА выполнено ртпи,к!Р = Р</.(тМлЖ«)Ж*Ж»Мр)- Ясно, что эквивалентность изображений содержательно означает одинаковость их кодов с точностью до перенумерации точек. Два изображения называем аффинно эквивалентными (а-эквивалентными), если они переводимы друг в друга аффинными преобразованиями. Изображение называем плоским, если все его точки не лежат на одной прямой или двух параллельных прямых.

Теорема 2.1. Два плоских изображения эквивалентны точно тогда, когда они а-эквивалентны.

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

Пусть и,...,г'* - номера к{к > 3) точек изображения А. Рассмотрим выпуклый многоугольник, включающий все эти точки, часть из которых (и только они) образуют его множество вершин. Ясно, что такой многоугольник определяется однозначно. Пусть 5,,.„и -площадь этого многоугольника, которую называем площадью к -точечника. Если точки г^,..., г* расположены на одной прямой, то полагаем 5,, _и = 0. Пусть ¿1, ■ ■ - ,]к - другой ¿-точечник из А. Полагаем АЧ.= При этом, если = 0,то р,-считаем не определенным. Множество всех таких индексированных чисел обозначаем через Та- Кодом изображения А называем пару < Ма,Та >■ Изображения А и В с кодами < Мд,Уд > и < Мв, Тв > называем ¿-эквивалентными, если существует такая биекция ф : Ма —1- Мв, что для любых ¿1,..., г д., ,..., ^ из МА выполнено р{=

Можно продолжить определение ¿'-эквивалентности и на случай к = 2, понимая под расстояние между точками с номерами ц и Ч-

Отношения /г-эквивалентности и аффинной эквивалентности являются отношениями эквивалентности. Порождаемые ими на множе-

стве всех плоских изображений разбиения на классы эквивалентности обозначим соответственно через и Яа.

Теорема 2.2. Разбиения Е,к(к > 2) и Л.а совпадают только при к = 3.

В главе I предполагалось, что основу для распознавания и организации целенаправленного поведения составляет существование своего рода " внутренней" модели внешнего мира. Это приводит к задаче описания совокупности тел и одного тела. В главе Ш представлено описание тела, инвариантное к аффинным преобразованиям его в пространстве.

Назовем трехмерным изображением А или телом конечное множество точек в трехмерном евклидовом пространстве. Занумеруем попарно различными номерами точки изображения А. Пусть МА множество этих номеров, Утпи„ и Ук>Рд - объемы тетраэдров с вершинами в четверках точек с номерами т,п,и,у и к,в,р,д и пусть Ртпм,к>рЯ = Угппиу/Укт- Полагаем, что порядок номеров в четверках не важен, сами четверки различны и для случая, когда Ук,рд = О, РтпмМря не определено. Множество индексированных чисел ртПиу,у.*рд для всех таких пар четверок обозначим через Та • Кодом тела А назовем пару < Ма,Тд >. Тела А и В с кодами < Мд,Та > и < Мв,Тд > назовем эквивалентными, если существует такая би-екция ф : Ма Мв, что для любых га, п, и, V, к, б, р, д из МА выполнено Ртпт,к)РЧ = Р4>(™)Ф(п)^{иЩи),ф(Щ{,)ф(р)ф(д)- Тела, все точки которых расположены в одной плоскости, называем двумерными и для них рассматриваемый код не определен. Тела называем аффинно эквивалентными (а-эквивалентными), если они переводятся друг в друга аффинными преобразованиями.Трехмерное изображение назовем объемным, если все его точки не лежат в одной плоскости или в двух параллельных плоскостях.

Теорема 3.1. Два объемных изображения эквивалентны точно тогда, когда они аффинно эквивалентны.

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

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

Отметим, что в целом теоремы 2.1,2.2 и 3.1 дают интересную возможность свести геометрию конечных совокупностей точек к свойствам их кодов, т.е., условно говоря, к внутренним свойствам этой совокупности, без использования какой-либо системы отсчета (системы координат). В связи с этим можно вспомнить, что в геометрии Евклида объекты рассматриваются, как правило, безотносительно к их, например, положению или размерам. Геометрия Евклида в этом смысле имеет, можно считать, некоторые черты модели зрительного восприятия. Может быть это обстоятельство и обусловило в какой-то мере (конечно, в ряду других причин) и появление, и конкретный вид геометрии.

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

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

Главная проблема в рамках машинного стереозрения - это проблема идентификации соответствующих друг другу точек на двух проекциях. Когда таких точек много, то неясно, какую из них на одной проекции сопоставлять данной точке на другой. Это нельзя сделать, например, простым наложением изображений на сетчатках друг на друга, поскольку эти изображения разные за счет разных ракурсов. Предполагать, что уже "распознано", какие части изображений соответствуют друг другу, и на этой основе сопоставлять точки проекций тоже нельзя, т.к. задача распознавания предполагается решаемой на более поздних этапах и ее решение отчасти должно основываться на результатах восстановления трехмерного изображения. В целом рассмотрения такого рода приводят к необходимости восстанавливать трехмерное изображение не только по данной паре £1 и 5г его плоских проекций, но и по любой паре ^ и §2, полученной из соответственно и £2 аффинными преобразованиями-.

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

Рассмотрим тело Т и прямую, называемую направлением проекции. Направления проекции назовем разными, если они не параллельны. Проведем через каждую точку тела Т прямые, параллельные направлению проекции а и называемые лучами. Полагаем а таким, что на каждом луче находится только одна точка тела. Таких направлений проекции бесконечное множество, не таких - только конечное. Назовем плоскость, пересекающую лучи, плоскостью проекции, изображение, образованное точками пересечения лучей с плоскостью проекции - проекцией тела (на данную плоскость и по данному направлению). Рассматриваем проекции тела Т по разным направлениям и на разные плоскости. Оговорим, что если Т -двумерное изображение, то ос полагаем не параллельным плоскости этого изображения. Взаимнооднозначное соответствие между точками двух изображений назовем их разметкой. Соответствующие друг другу точки будем обозначать одной буквой (с разными индексами). Ясно, что описанным выше устанавливается взаимнооднозначное соответствие между точками тела Т и точками проекций 5,-(г = 1,2,...).

Если а - точка тела Т, то точку проекции 5,-, лежащую с ней на одном луче, обозначим через о,- и будем называть проекцией точки а. Это устанавливает и взаимнооднозначное соответствие между точками проекций и Sj: соответствующие друг другу точки являются проекциями одной и той же точки тела Т. Размеченные изображения Л и В назовем а'-эквивалентными, если можно перевести их одно в другое аффинными преобразованиями так, что совместятся соответствующие друг другу точки (обозначение:Л га В). В противном случае А а В назовем а'-разными.

Далее в главе IV описана процедура А1дТ' построения некоторого тела Т' по И §2, где Бу б'х, §2 и .5'г, и 5х и - а'-разные проекции тела Т. _у'

Теорема 4.1. Если 5"! и ^ суть а'-разные проекции тела Т,§1 ш 5\, §2 ~ ¿г и тело Т' построено по ¿1 и §2 использованием А1дТ', то тела Т и Т1 а'-эквивалентны.

Содержательно теорема 4.1 состоит в следующем. В процедуре А1дТ' присутствует много моментов, которые могут варьироваться. Можно, например, выбирать разные 01 и §2, по разному брать исходную четверку точек на §\ (или на >§2) и т.д. Варьируя такие моменты, можно построить некоторое множество Т' тел. Теорема, однако, утверждает, что все они а'-эквивалентны телу Т и, значит, а'-эквивалентны между собой. Тело посредством процедуры А1дТ' восстанавливается, тем самым, с точностью до аффинных его преобразований. При этом нет необходимости знать расстояние между проекциями и 6*2 (аналог расстояния между сетчатками глаз), тело Т' строится по произвольным образом сдвинутым, повернутым, сжатым или растянутым, уменьшенным или увеличенным проекциям тела Т.

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

Работа с восстановленным телом может включать в себя постро-

ение его проекций по произвольным направлениям (своеобразный аналог разглядывания тела с разных позиций "внутренним взором"). Конечно, имея восстановленное тело, можно построить произвольную его проекцию. Однако любую проекцию можно получить непосредственно по £¡1 к §2 , не прибегая к восстановлению тела в качестве, так сказать, промежуточного этапа. Такие построения могут оказаться полезными, например, в компьютерных играх. Далее описывается процедура А1дво построения по ¿'1 и £2 некоторого изображения 5о и две теоремы, характеризующие свойства А1дЗо. Теорема 4.2. Если ^ и 5г суть а' -разные проекции тела Т, » ¿х,£2 ж £2 и изображение 5о построено по §1 и §2 использованием А1дБо- то существует тело Т', а'-эквивалентное телу Т и такое, что изображение £о является его проекцией (возможно неполной) по некоторому направлению.

Теорема 4.3. Если Т - объемное тело, и £2 - проекции его по разным направлениям »1 и с*2, ¿>1 ~ ^, §-г ~ £2 и Т'- некоторое тело, а'-эквивалентное телу Т, то по 5] и £'2 использованием А1дво можно получить любую (включая неполные) проекцию тела Т.

Теорему 4.2 можно рассматривать как в некотором смысле прямое утверждение: если есть две проекции тела Т , то в результате использования А1дБо получается изображение, которое тоже является проекцией тела Т (или тела, а'-эквивалентного телу Т). Теорему 4.3 можно интерпретировать как своего рода обратное утверждение: если Бх - проекция тела Т (или тела, а'-эквивалентного телу Г), то

можно получить как результат использования А1дЗо.

До сих пор предполагалось, что точки на и §2 размечены. Положим теперь, что разметка неизвестна. Если каждое из £>1 и §2 состоит из п точек, то возможны п! вариантов разметки. Пусть при данном варианте разметки точкам ж,-,,..., на ¿х ставятся в соответствие точки у^,..., У]а на §2- Пусть существует тело Т' из точек г\,..., гп и его проекции и такие, что « ¿>1,~ £2 и точки и являются проекциями точки = 1,...,п). Тогда данный вариант разметки назовем приемлемым или решением. Далее описана процедура, позволяющая найти все приемлемые варианты разметки.

В руководствах по робототехнике и машинному зрению при описа-

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

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

Поле зрения 3 определяется как множество всех ячеек квадратной декартовой сетки. Строки сетки соответствуют полям зрения отдельных фоторецепторов левого глаза (с одномерной сетчаткой). Столбцы соответствуют, аналогично, фоторецепторам правого глаза. Левый глаз " рассматривает" поле 3 слева, а правый глаз - снизу. Изображение (объект) определяется как подмножество / поля J . Правый край изображения Кр представляет собой граничные ячейки объекта, видимые правым глазом. Аналогично определяется левый край изображения К¡~ . Край изображения ('форма' объекта) - К[ — К^ и К] . Рассматривается только класс стандартных изображений. Он состоит из изображений со связными проекциями (при этом изображение не обязательно связно). Ввиду этого помимо поля 3 вводится для каждого I редуцированное поле ./ , образованное ячейками прямоугольной сетки размерности д * И , где в каждом из /г столбцов и в каждой из д строк есть ячейки изображения.

Вводится отображение Р , которое краю Кг изображения I ставит в соответствие пару проекций [Ь, Д] изображения I, где - матри-

цы, соответственно, размерностей 3*д и 3*Л. Правой проекцией ячейки правого края из к-го столбца сетки является к-ый (ац, аг*, аз*)Г столбец матрицы Л. Если 1 < к < /г, то а^ равно числу строк между положением ячеек правого края из к-го и (к — 1)-го столбцов сетки, азк равно числу строк между положением ячеек К^ из к-го и (к + 1)-го столбцов сетки, а^к аналогично соответствует (к — 1)-му и (к + 1)-му столбцам. Для первого и для последнего столбцов сетки проекции определяются особо. Аналогично (по строкам сетки) определяется левая проекция Ь изо бражения I.

Задается класс матриц ^о такой, что 1) для любого изображения I его проекция Е(К]) = [Ь, /2] € и 2) если для [Л, В] существует

изображение I такое, что Р(Кг) = [А, В], то [А, В\ Е При этом

для некоторых пар матриц [£, Я] 6 Оо * ^о выполняется Щ ~

{}■

Далее рассматривается задача о восстановлении по паре [Ь,Щ края К[ такого, что Г (К/) = [Ь, Щ.

Моделирование процесса описания человеком объектов реального мира должно отражать неопределенность выбора конкретного значения признака при описании конкретного объекта. В связи с этим в §2 главы V вводится понятие степени нечеткости для нечеткой лингвистической шкалы (НЛШ) и рассматриваются основные его свойства. Степень нечеткости вводится аксиоматически. Определяется класс функций, входящих в состав множества шкальных значений рассматриваемых шкал и ограничения на совокупность таких функций. Под степенью нечеткости НЛШ понимается значение некоторого функционала, определенного на множестве функций принадлежности шкальных значений рассматриваемых шкал.

В §3 главы V рассмотрена задача, возникающая следующим образом. Некоторая фигура проецируется на прямоугольный ячеистый экран размером п * ш ячеек. Ячейке, на которую попадает контур фигуры, сопоставляется единица, в противном случае - ноль. Получающаяся матрица размерами п * гп из нулей и единиц называется изображением. Задается некоторая кодировка экрана как взаимнооднозначного соответствия между элементами матрицы и (п * номерного вектора. Соответствующие элементы матрицы и компонен-

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

Автор выражает глубокую благодарность В.Б.Кудрявцеву за постоянное внимание к работе.

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

1. Козлов В.Н., Математическое моделирование зрительного вопри-ятия. Сб. "Математические вопросы кибернетики", вып.6,М., Наука, 1996,С. 321-338.

2. Kozlov V.N., Image Coding and Recognition and Some Problems of Stereovision // Pattern Recognition and Image Analysis, Vol.7, N4, 1997, pp.448 - 466.

3. Козлов B.H., О кодировании дискретных фигур //Дискретная математика, том 8, вып. 4, 1996, С. 57 - 61.

4. Козлов В.Н., О кодировании проекций внешней среды на сетчатку глаз и о восстановлении трехмерных изображений по этим проекциям // ДАН России,т. 347, N1, 1996, С. 19 - 22.

5. Козлов В.Н., О кодировании и распознавании плоских и объемных дискретных изображений. Сб. "Компьютерные аспекты в научных исследованиях и учебном процессе",М., Изд. Моск. ун-та, 1996, С. 103 - 106.

6. Козлов В.Н., О распознавании точечных изображений и о моделировании стереозрения. Сб. "Проблемы теоретической кибернетики. Материалы XI Международной конференции", М., Рос. гуманит. ун-т, 1996, С. 91 - 92.

7. Желудкова H.H., Козлов В.Н., О связи кодирования изображений с суперпозициями булевых функций в задачах распозна-

вания. Сб."Проблемы теоретической кибернетики. Материалы XI Международной конференции", М., Рос. гуманит. ун-т, 1996, С. 63-64.

8. Kudrjavcev V., Rijov A., Kozlov V., Strogalov A., An expert system for the evaluetion of the negative effects of environment on person during the liquidation of nuclear, industrial, and ecological accidents, Proceedings of the 1st FLINS Workshop, Mol, Belgium, 1994, pp. 266 - 270.

9 Козлов B.H., О кодировании плоских и объемных изображений. Сб. "Методы и системы технической диагностики", вып. 18, Саратов, Изд. Саратовского ун-та, 1993, С. 85 - 86.

10 Козлов В.Н.,Тихонравова В.В., Царев В.А., О связи кодирования изображений с функциями алгебры логики в задачах распознавания, Сб. "Методы и системы технической диагностики", вып. 18, Саратов, Изд. Саратовского ун-та, 1993, С. 86 - 88.

11 Козлов В.Н. Дискретный подход к моделированию в естествознании и модели в биологии. М., Изд. Моск. ун-та, 1990.

12 Крушинский JI.B., Козлов В.Н., Кудрявцев В.Б., О некоторых результатах применения математики к моделированию в биологии, Сб. "Математические вопросы кибернетики", вып.1, М.,Наука, 1988, С. 52 - 86.

13 Козлов В.Н., О математическом моделировании некоторых механизмов поведения животных,Сб." Проблемы теоретической кибернетики. Тезисы докладов VIH Всесоюзной конференции", Горький, 1988, С. 161 - 162.

14 Козлов В.Н., О некоторых свойствах одной модели элементарной рассудочной деятельности. Сб."Методы и системы технической диагностики", вып. 4, Саратов, Изд. Саратовского ун-та, 1985, С. 61 - 69.

15 Козлов В.Н., Моделирование поведения, связанного с поиском в среде, Тезисы докладов УП Всесоюзной конференции "Проблемы теоретической кибернетики", Иркутск, 1985, С. 94 - 95.

16 Козлов В.Н., О математическом моделировании элементарной рассудочной деятельности. Сб. "Методы и системы технической диагностики", вып. 3, Саратов, Изд. Саратовского ун-та, 1984, С. 31-39.

17 Козлов В.Н., О математическом моделировании некоторых сложных форм поведения. Сб. "Проблемы кибернетики", вып. 39, Наука, 1982,С. 223 - 256.

18 Козлов В.Н., Об одной модели прогнозирования и распознавания в нервной системе. Сб. "Математические методы в биологии", Киев, Наукова думка, 1982, С. 202 - 209.

19 Козлов В.Н., О математическом моделировании элементарной рассудочной деятельности. ДАН СССР, т.259, N2, 1981, С. 509

- 512.

20 Козлов В.Н., Об одной математической модели поведения в опытах по изучению элементарной рассудочной деятельности, Тезисы докладов V Всесоюзной конференции по проблемам теоретической кибернетики, Новосибирск, 1980, С. 121 - 123.

21 Kozlov V.N., Uber ein Modell von Prognosen- und Erkennungmechanismen von Bildern in Nervensystemen, Wissenschaftliche Zeitschrift der Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Reihe, N6, 1975, S. 748 - 750.

22 Козлов B.H., Рефлексы, модели поведения и распознавание образов. Сб."Проблемы кибернетики", вып. 28, М., Наука, 1974, С. 223

- 238.

23 Козлов В.Н., Модели поведения и распознавание образов. Журнал высшей нервной деятельности им.И.П.Павлова, N2, 1974, С. 306 - 312.

24 Козлов В.Н., О моделировании прогнозирования и распознавания в нервной системе. Тезисы докладов Ш Всесоюзной конференции по проблемам теоретической кибернетики, Новосибирск, 1974, С. 169-170.