Обработка изображений методами нелинейной динамики в одномерных динамических системах тема автореферата и диссертации по физике, 01.04.03 ВАК РФ

Р Г 5 ОД

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ РАДИОТЕХНИКИ И ЭЛЕКТРОНИКИ

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

Андреев Юрий Вениаминович

ОБРАБОТКА ИЗОБРАЖЕНИЙ МЕТОДАМИ НЕЛИНЕЙНОЙ ДИНАМИКИ В ОДНОМЕРНЫХ ДИНАМИЧЕСКИХ СИСТЕМАХ

01.04.03 — Радиофизика

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

Москва - 1993

Работа выполнена в Институте Радиотехники и Электроники РАН, г.Москва.

Научный руководитель — доктор физико — математических

наук, ведущий научный сотрудник Дмитриев A.C.

Официальные оппоненты — доктор физико-математических

наук, ведущий научный сотрудник Малинецкий Г.Г. — кандидат физико-математических наук, доцент Кузнецов Ю.И.

Ведущая организация: Нижегородский Государственный университет

Защита состоится 1993 г. в // ч ¿О мин на

заседании специализированного совета Д.002.74.02 в Институте Радиотехники и Электроники РАН по адресу: 103907, Москва, ГСП-3, ул.Моховая, 11.

С диссертацией можно ознакомиться в библиотеке ИРЭ РАН.

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

Ученый секретарь специализированного совета, кандидат технических наук

Голубцов М.Г.

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

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

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

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

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

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

В 1991 году А.С.Дмитриевым предложен принцип записи и восстановления информационных сигналов на устойчивых предельных циклах одномерных динамических систем. Дальнейшие исследования (Дмитриев и др., 1991 — 1993) показали, что испльзование непрерывных одномерных отображений отрезка в себя и их обобщений на двумерный и многомерные случаи в качестве систем для записи, хранения и обработки информации - открывает широкие перспективы при решении ряда важных задач анализа сигналов и изображений. В частности, были установлены свойства ассоциативности для "памяти", основанной на использовании устойчивых предельных циклов, а также принципиальная возможность распознавания записанных образов на основе записи эталонных сигналов на неустойчивых предельных циклах.

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

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

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

* Дмитриев A.C. Запись и распознавание информации в одномерных динамических системах // Радиотехника и электроника. 1991. Т.36. № 1. С.101-108

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

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

информационными сигналами.

Основные задачи, решаемые в работе:

— исследование динамики нелинейной колебательной системы типа одномерного отображения отрезка в себя с записанной информацией;

— определение информационной емкости метода записи на аттракторах динамических систем и поиски путей ее увеличения;

— разработка метода записи и восстановления изображений на аттракторах динамических систем;

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

Научная новизна результатов работы заключается в том, что:

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

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

— на основе результатов этого исследования предложено использование в качестве носителей информации хаотических аттракторов типа циклов интервала;

— предложен способ организации хаотического сканирования информации, записанной в памяти на основе одномерного отображения;

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

ДостоверЕшсть научных выводов подтверждается согласием результатов аналитических исследований и математического

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

На защиту выносятся следующие основные положения:

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

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

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

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

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

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

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

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

Апробация работы, публикации, внедрение и использование результатов: материалы диссертационной работы докладывались на международном семинаре "Нелинейные цепи и системы" (Москва, 1992), II международном семинаре "Клеточные нейронные сети и их приложения" (Мюнхен, ФРГ, 1992), международном семинаре — совещании "Алгоритмы обработки информации в нейроподобных системах" (Нижний Новгород, 1993); на III Школе "Стохастические колебания в радиофизике и электронике" (г.Саратов—1991г.); докладывались на научных семинарах в Институте радиотехники и электроники РАН, МГУ, Институте прикладной математики РАН, Институте высшей нервной деятельности РАМН, Институте атомной энергии, семинаре Российского общества по нейронным сетям, Институте математики АН Украины, НИИ Прикладной механики и кибернетики (г.Горький), университете Беркли (США), НИЦ компании Hewlett —Packard (Бристоль, Англия). Результаты исследований вошли в работу, представленную на конкурс компании Hewlett —Packard по распознаванию образов в 1992 г., которой был присужден Главный приз этого конкурса.

По теме диссертации опубликовано 8 печатных работ [1—8].

Структура и объем работы: диссертационная работа состоит из введения, четырех глав, заключения и списка цитированной литературы. Содержит страниц текста, _2«_ рисунков, 3

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

Краткое содержание диссертационной работы

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

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

Опубликованные по этой проблеме данные можно условно разделить на следующие группы:

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

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

— данные о хаотической электрической активности мозга человека и животных, а также о хаотическом характере электрической активности в отдельных нейронных подсистемах;

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

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

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

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

— определение информационной емкости метода записи на аттракторах динамических систем и поиски путей ее увеличения;

— разработка метода записи и восстановления изображений на аттракторах динамических систем;

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

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

опубликованные математические результаты по кусочно — линейным отображениям.

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

Рассматриваются бифуркационные явления в отображении х„+] = /(*„),где /(*)= /(х,Р), в зависимости от параметра р — наклона информативных отрезков отображения, определяющего устойчивость предельных циклов. Анализ бифуркационных диаграмм показывает, что потеря устойчивости предельных циклов при переходе параметра Щ через 1 происходит через бифуркацию рождения хаотического аттрактора типа цикла интервалов. Это хаотический атграктор размерности 1 с положительным коэффициентом Ляпунова ~ 0.1—0.7, ненулевой мерой по параметру р и обладающий своим бассейном притяжения. Показывается, что для каждого из записанных на отображении информационных сигналов, как правило, одновременно рождаются 2 интервальных цикла, располагающихся на краях информативных отрезков. Условия существования и устойчивости этих хаотических аттракторов определяются не только наклоном информативных отрезков /?, но и наклонами примыкающих неинформативных отрезков, и потому различны для различных аттракторов, в связи с чем одни из них теряют устойчивость раньше, а другие позже.

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

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

Показано, что описанный в первой главе принцип синтеза одномерных динамических систем с заданными информационными

предельными циклами может быть обобщен на класс хаотических аттракторов — циклов интервалов. Как следует из анализа бифуркационных диаграмм, фазовых портретов и временных серий, движение по интервальному циклу хаотично, однако он устойчив и ограничен в фазовом пространстве информативными интервалами соответствующего информационного цикла, к тому же имеет довольно широкую область существования по параметру р. Если рассмотреть дискретный информационный поток, порождаемый отображением хп+1 = /(*„) при движении на этом аттракторе, то оказывается, что он совпадает с записанным информационным блоком.

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

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

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

Исследован вопрос об информационной емкости памяти на основе одномерного отображения. Установлено, что предельная емкость памяти (полная длина всех информационных блоков,

и

которые могут быть одновременно записаны на одном отображении) при алфавите N на уровне записи <7 — Л/т.е. достаточно велика даже при скромных параметрах записи.

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

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

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

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

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

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

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

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

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

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

Обсуждаются проблемы представления данных: изображений, отображения с записанной информацией, алфавита. Рассматриваются ограничения, налагаемые аппаратными ресурсами ЭВМ (разрядность, объем ОЗУ) на размеры записываемых изображений, общего объема записываемой информации и возможного алфавита. Приведены оценки предельных объемов записи при использовании исходного метода без кодирования информационных сигналов для ЭВМ типа IBM PC.

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

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

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

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

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

Основные полученные результаты:

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

2. Предложен и реализован принцип хаотического сканирования памяти на основе явления перемежаемости.

3. Предложен и обоснован метод записи информации па хаотических аттракторах — циклах интервалов.

4. Проведен анализ информационной емкости записи.

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

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

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

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

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

Автор выражает глубокую благодарность своему научному руководителю А.С.Дмитриеву за постоянную помощь в работе, С.О.Старкову и А.И.Панасу за постоянное внимание и критические замечания, а также Ю.Бельскому и Д.Куминову за помощь в оформлении диссертационной работы.

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

1. Андреев Ю.В., Вельский Ю.Л., Дмитриев А.С. Information processing in nonlinear systems with dynamic chaos.// Доклады Международного Семинара "Нелинейные цепи и системы". Москва. 1992. T.l. С.51-60.

2. Andreev Yu.V., Dmitriev A.S., Chua L.O. and Wu C.W., Associative and Random Access Memory Using One —Dimensional Maps. Memorandum No.UCB/ERL M92/32. 1992. Electronics reseach laboratory. College of Engineering. University of California, Berkeley. 58 pages.

3. Andreev Yu.V., Dmitriev A.S., Chua L.O. and Wu C.W., Associative and Random Access Memory Using One —Dimensional Maps. International Journal of Bifurcations and Chaos. 1992. V.3 N.2 P.483 —504.

4. Андреев Ю.В., Дмитриев .А.С. "Хаос и информационные процессы в одномерных динамических системах". СНГ VIII конференция "Качественная теория дифференциальных уравнений". Самарканд 1992. Тезисы докладов, с.9.

5. Yu.Andreyev, Yu.Belsky, A.Dmitriev, D.Kuminov "Inhomogenuos CNN: possibility of functional device design" Proceedings oi CNN'92 workshop, Munich 1992. p. 135-140.

6. Андреев Ю.В., Дмитриев A.C., Старков С.О. Обработка изображений на основе одномерных динамических систем. Программный комплекс "ИнформХаос". // Препринт ИРЭ РАН. Москва 1993. 30 е..

7. Andreyev Yu.V., Dmitriev A.S. Graphic Images as Limit Cycles of Nonlinear Dynamic Systems. Abstracts of XXIII Gen. Assembly of URSI. 1993. P. ют.

8. Андреев Ю.В., Вельский Ю.Л., Дмитриев A.C., Куминов Д.А. Динамические системы с детерминированным хаосом как среда для хранения и обработки информации. // Международный Семинар "Алгоритмы обработки информации в нейроподобиых системах". Нижний Новгород. 1993. Тезисы докладов. С. 12.