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

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

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

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

АВТОРЕФЕРАТ

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

Пермь - 2000

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

Научный руководителыкандидат физико-математических наук, доцент A.A. Калмыков (Пермский государственный университет)

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

профессор А.Р. Абдуллаев заслуженный деятель науки УР, доктор технических наук, профессор Кузнецов П.Г. (Ижевский государственный технический университет)

Ведущая организация: Пермский военный институт ракетных войск

Зашита диссертации состоится « $ » UdVfl^J_ 2000 г. в /¿7

часов на заседании диссертационного совета К 063.66.07 в Пермское государственном техническом университете по адресу: 614600, г. Пермь Комсомольский проспект, 29а, ПГТУ, ауд. 423.

С диссертацией можно ознакомиться в библиотеке ПГТУ. Автореферат разослан «_»__2000 г.

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

С.Г. Николаев

] M.JcUGtO

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. В последние десятилетия усилиями гечественных я зарубежных ученых разработаны достаточно эффективные ¡етоды восстановления и обработки сигналов. Благодаря этому сегодня опросы теории и практики восстановления, по крайней мере, двумерных игналов, достаточно хорошо изучены. Однако следует отметить, что еоретической основой восстановления сигналов является статистический ппарат и методы теории фильтрации, основанные также на статистическом одходе. Причем почти все известные vi используемые на практике методы вляются линейными, в том числе и поиск регуляричо ванного решения на снове метода А Н. Тихонова.

Разработка и исследование методов восстановления и обработки сигналов междисциплинарная комплексная проблема, для решения которой фименяются подходы функционального анализа, в том числе теория [екорректных задач, теория фильтрации, математическая статистика и нр, Изучению вопросов восстановления сигналов и разработки алгоритмов юевяшено много работ, среди которых следует отметить исследования А.Н. Тихонова, А.М. Тараторина, Г.И. Василенко, Я. Виткуса, Б.В. Лиисимова, А.Н. Ъюаревского, Ж. Макса, В.А. Омельченко, A.B. Бакушииского, А.Б. "ончарского, У. Прэтта, П.А. Чочиа и др.

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

жестких требований к времени вычислений.

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

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

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

1. Построить проекционную меру компактного самосопряженного оператора в гильбертовом пространстве.

2. Построить проекционную меру оператора циклической свертки на локально-компактной абелевой группе с инвариантной мерой.

3. Вывести формулу для локального регуляризующего алгоритма.

4. Вычислить коэффициенты Фурье для скользящего регуляризующего алгоритма.

5. Реализовать полученные регуляризующие алгоритмы на ЭВМ.

Научная новизна диссертационной работы состоит в следующем:

1. Показано, что проекционная мера компактного самосопряженного оператора задается при помощи ортобазиса в гильбертовом пространстве,

составленном из собственных векторов.

2. Впервые выписан в явном виде собственный ортобазис оператора любой свертки.

3. На основе проекционной меры построен и выписан в явном виде локальный регуляризующий алгоритм на основе регуляризатора А Н. Тихонова.

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

5. На основе разработанного пакета программ проведен анализ эффективности методов скользящей и локальной регуляризации.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на: международной научно-практической конференции «Студент и научно-технический прогресс» (Новосибирск, 1994); международной научно-методической конференции «Новые информационные технологии в университетском образовании» (Новосибирск, 1995); международной научно-практической конференции «Новые информационные технологии в образовании» (Петрозаводск, 1995); III научно-методической конференции «Рождественские чтения» из цикла информатика в школе (Пермь, 1999), семинарах кафедры прикладной математики, кафедры теоретической механики Пермского государственного технического университета.

Публикации. Основные результаты работы опубликованы в 6 статьях и тезисах докладов.

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, списка цитированной литературы и приложения (количество

страниц -_, количество рисунков -_, список литературы содержит_

источников.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Наиболее общий подход к процессу формирования изображения дается в операторном виде. Будем описывать произвольное изображение, независимо от его природы, функцией в общем случае двух переменных г(х,у), а. процессом формирования изображения будем называть преобразование исходного изображения :(х,у) в получаемое изображение а(£,т7) при помощи некоторого оператора А:

и(|,Ч) = Яг(х,>). (1)

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

г(х,у) = АМ№- (2)

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

Можно записать общее выражение для наблюдаемого изображения в виде

"(.4, п) = 12(х, у)1г(£, 17, х,у)ск(!у+п(4, г]), (3)

с

где 2(х,у)ни(^,т}) - входное и соответственно выходное изображения, Щ,т!,х,у) - весовая функция системы, определяющая все ее свойства, п(£,т]) - аддитивный

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

Задача восстановления изображений в

большинстве случаев сводится к решению

интегрального уравнения, т.е. к

определению функции г(х,у) по

зашумленным значениям «(£,?;).

Естественно исходить из предположения,

что точные данные задачи [л,и) известны

Рис. 1

нам лишь приближенно, т.е. в

действительности считать известной пару {/1 аппроксимирующую \ выбранной топологии пару {/(,»}. Ошибки можно интерпретировать, например как неадекватность идеализированной математической модели и описываемо! ею физической реальности; кроме того, погрешность может возникнуть за счс ошибок измерения исходных данных.

Основная задача, подлежащая исследованию, заключается в построен® по приближенным данным такой последовательности приближенны?

решений гл„-, которая сходится в пространстве решений к нормальном) решению г„ уравнения при условии сходимости исходных данньи К.«.}-» \А'и } (рис.1).

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

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

Ои

Доказана следующая теорема.

Теорема 1. Пусть АеЫ(Н) - компактный самосопряженный линейный оператор на гильбертовом пространстве Н, - ортобазис в Н,

составленный из собственных векторов оператора А : А<р1=Хк<рк, причем собственные значения Ак упорядочены по убыванию модулей. Тогда на измеримом пространстве (Л,Я(Л)) (/'(К) - множество всех подмножеств) проекционная мера Л: Р(К)-> N(H) оператора А задается при помощи формулы Л<£):= ЕеР(Я). (4)

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

Утверждение. Для любой ограниченной на спектре а(А) = {Хк} функции / К >С интеграл по мере (4) вычисляется по формуле (Ее Р(Я))

(5)

г

В частности, из полученной формулы вытекает:

/х) -- х => 1хМ(х) = - А - теорема Гильберта - Шмидта. (6)

Хх) = 1 |п«(х) = / - ряд Фурье. (7)

Я »'1

Так как процесс восстановления сигнала описывается уравнением свертки, то рассмотрен частный случай теоремы 1. Построен собственный ортобазис оператора свертки на локально компактной абелевой группе с инвариантной мерой.

Теорема 2. Для оператора свертки с четным ядром на конечной группе вычетов О-Ц^. Ф//ч. ортонормированным базисом пространства 12(С) является базис, составленный из собственных векторов оператора свертки.

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

В частности, для группы С = собственные векторы и

собственные значения вычисляются по формулам

. / k,rn ¿Um-. ^

Р^кЛЩ = Хк,.кЛЩ,Щ) = е ч*' ч'г-1 , (8)

i -v. «i -jifia.*»!

(k^GAm^cd (9)

"i-i m,'i

В случае G = Z2 = Z9Z спектр оператора свертки непрерывен:

Л,,„=Я(/„Г2)= ¿ ¿ЯО^К^-^Ч (/,Л)е(0Д]х(0Д]; (10) соответствующие собственные векторы ;

= (П)

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

<т(5д) = Я(0). (12)

Если ядро Н четно: 11{-х)-Н(х) VxeG, то оператор свертки самосопряженный в I,(G) и тогда, как известно, собственные значения оператора .У., вещественные, а действительная и мнимая части каждого комплексного собственного вектора являются вещественными собственными векторами. В этом случае собственные значения и собственные векторы вычисляются по формулам

v.аз)

*VV2 Щ-t «j"! Ч ' i J

(к,,к2) е ü, (т, ,тг) е G ,

= (14)

• „ (kimi ^ («„ «)2) = sm +.

Можно показать, что <pcí:t¡ и <?л;л - пара ортогоначышх собственных векторов, отвечающих собственному значению Át¡tj (при (к17к2)=-(к„к2) получается один

собственный вектор гак как =0). Нормы собственных векторов при (к^к2)^~(к„к2) равны а при норма собственного вектора

л/2

равна 1.

В случае бесконечной группы 0 = 7.1 для четного ядра Н получаем следующие формулы:

Л «

^ >С05; + 'гт2)(15)

= сое+/,«2), -*-/глгг), (0,!]х(0,!]. (16)

Отметим, что в этом случае собственные векторы не содержатся в ¿2(С).

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

Третья глава посвящена построению локального и скользящего регуляризаторов.

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

£ £ г</, -./„», = иОЛ1 ^ • (П)

J¡ :—П.'

Опорную область ядра Н всегда можно считать конечной, поэтому уравнение перепишется в виде

£ £ (18)

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

вещественны. Собственные функции

('>ап + '..'г). (19)

не содержатся в и являются собственными векторами лишь в

алгебраическом смысле: &п<р = к<р. Из собственных функций можно выбрать М1-М1 собственных векторов оператора свертки так, что сужение этих векторов со всей сетки 2г на кадр измерений О, =[1,Лг,]х[1)Л/2] образует ортогональный базис в пространстве 12{Ок). Для этого достаточно положить Л2 = М2 ■ Л и взять собственные функции

где (т^т2)еЦх ФЦЫ1. Отметим, что собственные функции в этом случае определены всюду в г2, а ортогональны локально на кадре <7,. Индексы тх,тг можно выбрать в порядке убывания модулей соответствующих собственных значений Лщ„г. Обозначим через А, =Лщи^.р'= упорядоченную

последовательность собственных значений, <р, - соответствующую последовательность собственных векторов. Вычислив коэффициенты Фурье и„/ = 1,Я,М2, вектора и(»„»2), (/„/2)е Ск, найдем локальное регуляризованное решение уравнения свертки в виде

Очевидно, что полученная формула совпадает с формулой регуляризованного решения в проекционном методе, в которой т-п, а //„ и Гп - линейные оболочки первых п векторов <р, соответственно в пространстве периодических функций на г2 и в пространстве 12 (Ок).

(20)

к Хи .-1 л, + д

(21)

и

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

Во второй части главы рассмотрен случай непрерывного поступления сигнала во времени, т.е. получен скользящий регуляризующий алгоритм. В проекционном методе регуляризукнцего решения уравнения линейной свертки измеренный массив ^),('.,>,)разлагается в ряд Фурье в пространстве /.,(о\) по универсальному ортобазису, состоящему из собственных векторов любой циклической свертки на группе Ц^ ФЦКг (А', и А'г - размеры кадра на О,). Если процесс обработки идет таким образом, что кадр и'*1 получается из кадра и' сдвигом на т строк вниз, то, используя свойство дискретного преобразования Фурье о переходе оператора сдвига в умножение на характер, можно вычислить коэффициенты Фурье вектора и ~' при помощи поправок к уже вычисленным коэффициентам Фурье вектора и'.

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

где к =(к1,к2)^С <рск,фхк - нормированные собственные функции, В -нормирующий множитель.

Пусть Г(10) - оператор сдвига на вектор (0,1) е 6' ~ Ц^ ©Ц,, . Заметим сразу, что сдвиг Та о) циклический, то есть верхняя строка кадра С перемещается на место нижней, а все остальные строки сдвигаются на одну позицию вверх. Вычислим сначала коэффициенты Фурье вектора и"' = Г(Ши':

(22)

о

2як, . . 2лк. ,

HL\ = COS---US, 4-Stn--IIS.

' У, 4 Nt *

. 2пк. . 2лк. ,

us' =-sm--uc\ +COS-—-its,

* Nt JV,

где к (к,,к2), Однако это коэффициенты Фурье циклически сдвинутого массива и', а нас интересует линейный сдвиг, поэтому последнюю строку циклически сдвинутого массива и' нужно заменить вновь поступившей строкой измерений. В результате приходим к окончательным формулам для коэффициентов Фурье массива и"':

исf

ust

i COS ( 2/r-f./ Vм (JV„y)-«i'a,У)],

J'X V "2 J

1-Х

2Bk Sin [2Я^-J I«"' (N,, J) - и'(1, J)] .

J » t

(24)

4 "2 J

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

Пакет программ реализован на языке программирования Turbo Pascal. Расчеты проводились на компьютере Pentium2 - 333, 32 Mb. Пакет состоит то нескольких подпрограмм, в которых осуществляется перевод изображения в цифровой вид и обратно в точечный (формат изображений BMP), обработка изображения аппаратной функцией измерителя, т.е. его «порча», восстановление при помощи скользящего и локального регуляризующих алгоритмов.

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

Рис. 3

„**' ОуЛЕ 1?. П

ирошводетт

Рис. 4

■ ЛкрпиаьЯ жлак А фопндепиО «ТОЙ

Рис. 5

а дквгнэив «лоа ■ кгишямн

Рис. 6

Рис. 7

литературы методами. Одним из преимуществ разработанного метода является отсутствие предварительных расчетов: в качестве начального приближения берется «запорченное» изображение. Был проведен вычислительный эксперимент, где в качестве выходного сигнала взят участок текста (рис. 2).

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

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

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

Проведены исследования восстановления

«запорченных» изображений при приближенных данных о ядре. В качестве исходного сигнала взят кадр, приведенный на рис. 7. Далее он был «запорчен» сверткой с аппаратной функцией измерителя и наложением нормально распределенного шума (рис.8). Затем проведено восстановление с ядром, отличающимся на погрешность 8=0,004. Из рис. 9 видно, что полученное изображение близко к исходному (см. рис. 7).

Основные результаты и выводы

1. Построена проекционная мера компактного самосопряженного оператора в гильбертовом пространстве, составленная из

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

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

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

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

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

Рис. 9

локального и скользящего алгоритмов. Пакет программ использовался в ОКБ «Деталь», а также в учебном процессе ГТГУ и ГТГТУ.

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

1. Щепина Е.М. О скользящей регуляризации уравнения линейной двумерной свертки У/ Вестник ПГТУ. Математика и прикладная математика. Пермь: ПГТУ, 1994. № 1. С. 95-99.

2. Калмыков A.A., Щепина Е.М. Программно-методический комплекс «Регуляризация алгоритмов цифровой обработки сигналов» /У Новые информационные технологии в университетском образовании: Сборник трудов. Новосибирск, 1995. С. 69-72. .

3. Щепина Е.М. Программно-методический комплекс «Регуляризация алгоритмов цифровой обработки изображений» // Новые информационные технологии в образовании: тез. докл. науч.-практ. конф. Петрозаводск, 1995. С. 100-102.

4. Кадырова Е.М. Программно-методический комплекс «Скользящая обработка изображений» // Рождественские чтения из цикла информатика в школе: тез. докл. III науч.-метод. конф. Пермь, 1999. С. 8-10.

5. Кадырова Е.М. Вычисление проекционной меры оператора свертки;'/ Вестник ПГТУ. Математика и прикладная математика Пермь: ПГТУ, 1999. С. 35-38.

6. Кадырова Е.М. Оценка эффективности метода скользящей регуляризации с помощью пакета программ / РАН Ин-т. Пермь, 2000, Деп. в ВИНИТИ. 01.02.2000. № .

Изд. лиц. ИД №00185 от 26 10.99

Подписано в печать 29.05.2000. Формат 60*84'Лб.

Усл. печ. л. 1. Тираж 100 экз. Заказ 23.

Техническая редакция "Пермского медицинского журнала" 614000, Пермь, ул Большевистская, 85

В В Е Д Е Н И Е.

ГЛАВА 1. РЕГУЛЯРИЗАЦИЯ ОПЕРАТОРНЫХ УРАВНЕНИЙ И ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ.

1.1. некорректные математические модели.

1.2. регуляризация по а.н. тихонову.

1.3. проекционный метод в теории регуляризации.

1.4. регуляризация уравнений линейной и циклической свертки.

1.5. задача восстановления изображений.

1.6. дискретное преобразование фурье [33, 63].

1.7. постановка задачи.

ГЛАВА 2. ПОСТРОЕНИЕ ПРОЕКЦИОННОЙ МЕРЫ ОПЕРАТОРА.

2.1. свертка и преобразование фурье на локально-компактных абелевых группах с инвариантной мерой.

2.2. вычисление проекционной меры компактного самосопряженного оператора.

2.3. собственный ортобазис оператора циклической свертки.

2.4. выводы г10 главе.

ГЛАВА 3. РЕГУЛЯРИЗУЮЩИЕ АЛГОРИТМЫ НА ОСНОВЕ РЕГУЛЯРИЗАТОРА А.Н. ТИХОНОВА И ПРОЕКЦТОННОГО МЕТОДА С АДАПТАЦИЕЙ БАЗИСА.

3.1. разработка локального регуляризующего алгоритма.

3.2. применение регуляризации при скользящей обработке.

3.3. выводы по главе.

ГЛАВА 4. ПРИМЕНЕНИЕ ЛОКАЛЬНОЙ И СКОЛЬЗЯЩЕЙ РЕГУЛЯРИЗАЦИИ ПРИ ОБРАБОТКЕ ИЗОБРАЖЕНИЙ.

4.1. пакет программ «обработка изображений».

4.2. восстановление входного сигнала с помощью пакета программ.

4.3. сравнительный анализ результатов.:.

4.4. выводы по главе.

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

Разработка и исследование методов восстановления и обработки сигналов - междисциплинарная комплексная проблема, к решению которой применяются подходы функционального анализа, в том числе теория некорректных задач, теория фильтрации, математическая статистика и пр. Изучением вопросов восстановления сигналов и разработке алгоритмов посвящено много работ, среди которых следует отметить работы А.Н. Тихонова, Тараторина A.M., Василенко Г.И., Виткуса Я., Анисимова Б.В., Писаревского А.Н., Макса Ж., Омельченко В. А., Бакушинского A.B., Гончарского А.Б., Прэтта У., Чочиа П.А. и др.

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

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

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

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

1. Построить проекционную меру компактного самосопряженного оператора в гильбертовом пространстве.

2. Построить проекционную меру оператора циклической свертки на локально-компактной абелевой группе с инвариантной мерой.

3. Вывести формулу для локального регуляризующего алгоритма.

4. Вычислить коэффициенты Фурье для скользящего регуляризующего алгоритма.

5. Реализовать полученные регуляризующие алгоритмы на ЭВМ.

Научная новизна диссертационной работы состоит в следующем:

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

2. Впервые выписан в явном виде собственный ортобазис оператора любой свертки.

3. На основе проекционной меры построен и выписан в явном виде локальный регуляризующий алгоритм- на основе регуляризатора А.Н. Тихонова.

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

5. На основе разработанного пакета программ проведен анализ эффективности методов скользящей и локальной регуляризации.

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

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

Тема данной диссертации была представлена: на научно-практических конференциях «Студент и научно-технический прогресс» Новосибирск 1994 г., «Новые технологии в образовании» Новосибирск 1995 г., «Новые информационные технологии в образовании» Петрозаводск 1995 г., «Рождественские чтения» Пермь 1999 г.

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

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

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

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

Результаты опубликованы в работах [36-38, 76-77].

4.4. ВЫВОДЫ ПО ГЛАВЕ.

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

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

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

ЗАКЛЮЧЕНИЕ

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

2. Построена проекционная мера компактного самосопряженного линейного оператора на гильбертовом пространстве:

А(Е)\=^{-,(рк)(рк, ЕеР(Я), где Лк - собственные значения, а срк собственные векторы. Выведена формула для вычисления интеграла от функции, ограниченной на спектре, по проекционной мере

3. Выписана в явном виде проекционная мера оператора типа свертки на локально-компактной абелевой группе с инвариантной мерой: Л{Е) := )<рк. ЕеР(Я), где Лк - собственные значения, а срк - собственные векторы оператора свертки, вычисляемые по формулам:

1 ^ , „ ( к]т1 1 к0т2^

Л,= Н(к1}к2) = —-— ]Г 2^Н(тх,т2)соб2л

N N

12 1 = 1 «Ь v + ) (к^к2) е О, (т^т2) еС рск к1 (/я,, т2) = соб 2л v щ # 2 у (ряк к (тх,т2) = %т2л к]т]

Ы2 . J

4. Построен регуляризатор для математической модели обработки отдельно взятого кадра изображения

N Г иг (Ь ¿г) = X1-7 <Р> (*1 ,Н)> (»1 ,*г) е 22 •

1 Л + О

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

К1 Гс соэ 1

N2 г к 4 2/г А-У N.

Иад-Яи)]

5. Разработан пакет прикладных программ, реализующий расчеты по обработке изображений с использованием данные предложенных в диссертации регуляризующих алгоритмов. Пакет программ использовался в ОКБ «Деталь», а также в учебном процессе ПГУ и ПГТУ (см. приложение 1).

6. Исследована эффективность предложенных методов в сравнении с уже известными. Показано значительное (на порядок) уменьшение времени восстановления сигнала.

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

1. Адаптивные методы обработки изображений. М.: Наука, 1988. - 244с.

2. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений: Учеб. пособие для студентов вузов. М.: Высш. шк.,1983. 295 с. ил.

3. Аряшев С.И., Бобков С.Г. Нейронные сети: основные типы, перспективы развития.// Вопросы кибернетики. Сб. статей под ред. В.Б. Бетелина. Москва, 1997, С. 120-137.

4. Ахмед Н., Pao K.P. Ортогональные преобразования при обработке цифровых сигналов: Пер. с англ. / Под ред. И.Б. Фоменко. М.: Связь, 1980. -248 с.

5. Бакушинский А.Б., Гончарский A.B. Итеративные методы решения некорректных задач. М.: Наука. Гл. ред. физ.-мат. Лит., 1989. - 128 с.

6. Бакушинский А.Б., Гончарский A.B. Некорректные задачи. Численные методы и приложения. М.: Изд-во Моск. ун-та, 1989. - 199 е.: ил. 28.

7. Бахтиаров Г.Д. Цифровая обработка сигналов: пробелмы и основные направления повышения эффективности // Зарубежная радиоэлектроника.1984, № 12. С. 48-66.

8. Ю.Бахтин И. А. О равенстве спектральных чисел линейныхположительных операторов // Воронеж, весен, мат. шк. «Современные методы в теории краевых задач», «Понтрягин. чтения 9», Воронеж, 3-9 мая, 1998: Тез. докл. - Воронеж, 1998. С. 22.

9. Безрук A.A., Лебедев Д.С. Выделение контуров на основе иерархической двухуровневой вероятностной модели ансамбля изображений. // Иконика: Цифровая обработка видеоинформации. М.: Наука, 1989. - С. 5 - 18.

10. Бейтс Р., Мак-Доннелл М. Восстановление и реконструкция изображений: Пер. с англ. М.: Мир, 1989. 336 с.

11. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. М.: Мир, 1989. - 448 е., ил.

12. Бокштейн И.М. Возможности повышения резкости цветных изображений. // Иконика: Цифровая обработка видеоинформации. М.: Наука, 1989. - С. 60 - 65.

13. Быстрые алгоритмы в цифровой обработке изображений /Т.С. Хуанг, Дж.-О. Эклунд. Г.Дж. Куссбаумер и др.; Под ред. Т.С. Хуанга: Пер. с англ. М.: Радио и связь, 1986. - 304 е., ил.

14. Василенко Г.И. Теория восстановления сигналов: О редукции к идеальному прибору в физике и технике. М.: Сов. радио, 1979. - 272 с.

15. Василенко Г.И., Тараторин А.М. Восстановление изображений. М.: Радио и связь. 1986. - С. 6-20

16. Виткус Р.Ю., Ярославский Л.П. Адаптивные линейные фильтры для обработки изображений // Адаптивные методы обработки изображений. М.: Наука, 1988. С. 6-35.

17. Габдулхаев Б.Г. Решение проблемы саморегуляризации некорректно поставленных задач // Алгебра и анализ: Тез. докл. шк.-конф., посвящ. 100-летию со дня рожд. Б.М. Гагаева, Казань, 16-22 июня, 1997. Казань, 1997. С. 51-52.

18. Гахов Ф.Д., Черский Ю.И. Уравнения типа свертки. М.: Наука. Главная редакция физико-математической литературы, 1978. - 296 с.

19. Гинзбург В.М. Формирование и обработка изображений в реальном времени, методы быстрого сканирования. М.: Радио и связь, 1986. 232 с.

20. Горбунов В.К. Регуляризация компактно разрешимых задач // Вест. МГУ. Сер. 15 1999.-№ 1. С. 20-23.

21. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1989.-232 с.

22. Грибков И.В., Захаров A.B. и др. Предобработка и распознавание двумерных изображений.// Вопросы кибернетики., Сб. статей под ред. В.Б. Бетелина. Москва, 1997. - С. 3-72.

23. Гурарий В.П. Групповые методы коммутативного гармонического анализа. // Итоги науки и техники. Современные проблемы математики. Фундаментальные направления. Т. 25. - С. 141 - 174.

24. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов: Пер. с англ. М.: Мир, 1988. - 488 с.

25. Данфорд Н., Шварц Дж. Линейные операторы (спектральная теория). -М.: Мир, 1966.-1064 с.

26. Доманский E.H. О регуляризации по. Маслову возмущенного линейного операторного уравнения первого рода. // Докл. РАН. 1997. - 353, № 4. - С. 442 - 444.

27. Долманский E.H. Эквивалентность сходимости регуляризационного процесса существованию решения некорректной задачи // Челябинск: Изд-во Гос. Тех. Ун-та, 1996. 159 с.

28. Донченко С.Е., Матвеев Ю.Н., Очин Е.Ф. Принципы организации параллельных процессоров цифровой свертки изображений // Зарубежная радиоэлектроника. 1987, № 7. - с. 84 - 102.

29. Дуда Р., Харт П. Распознавание образов .и анализ сцен. М.: МирЮ 1976.-511 с.

30. ЗЗ.Залманзон Л. А. Преобразование Фурье, Уолша, Хаара и их применение в управлении, связи и других областях. М.: Наука. Гл. ред. физ.-мат. лит. , 1989.-496 с.

31. Иванов В.К., Васин В.В., Танана В.П. Теория линейных некорректных задач и ее приложения. М.: Наука, 1978. - 206 с.

32. Иган Дж. Теория обнаружения сигналов и анализ рабочих характеристик / Пер. с англ. М.: Наука. Гл. ред. физ.-мат. лит., 1983. 216 с.

33. Кадырова Е.М. Вычисление проекционной меры оператора свертки// Вестник ПГТУ. Математика и прикладная математика. Пермь: ПГТУ, 1999. -С.

34. Кадырова Е.М. Программно-методический комплекс «Скользящая обработка изображений». // Тезисы докладов III научно-методической конференции «Рождественские чтения» из цикла информатика в школе. -Пермь, 1999.-С. 8-10.

35. Калмыков A.A., ЕЦепина Е.М. Программно-методический комплекс «Регуляризация алгоритмов цифровой обработки сигналов» // Тезисы научно-практической конференции «Новые технологии в образовании». Новосибирск, 1995. С. 69- 72.

36. Келли М., Спайс Н. Язык программирования ФОРТ. М.: Радио и связь, 1993.-318 с.

37. Кириллов A.A., Гвишиани А.Д. Теоремы и задачи функционального анализа: Учеб. пособие для вузов. 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 400 с.

38. Кучеренко К.И., Очин Е.Ф. Двумерные медианные фильтры для обработки изображений // Зарубежная радиоэлектроника. 1986, № 6, С. 50-61.

39. Лаврентьев М.М. Условно-корректные задачи для дифференциальных уравнений. Новосибирск: НГУ, 1973.

40. Лаврентьев М.М., Савельев Л.Я. Линейные операторы и некорректные задачи. М.: Наука, 1991. - 331 с.

41. Линдли К. Практическая обработка изображений на языке Си: Пер. с англ. М.: Мир, 1996. - 512 е., ил.

42. Lloyd N.G. A survey jf Degree Theory: Basis and Development // IEEE Trans. On circuits and systems. 1983, №8. P. 607-616.

43. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. -М.: Наука, 1965. 520 с.

44. Макс Ж. Методы и техника обработки сигналов при физических измерениях: В 2-х томах. Пер. с франц. М.: Мир, 1983. - Т. 1., 312 е., ил.

45. Милюкова О.П. Изображение как функция с ограниченной полной вариацией. // Иконика: Цифровая обработка видеоинформации. М.: Наука, 1989. - С. 19-25.

46. Моделирование сигналов и обратная задача радиотеплолокации. Регуляризация обратной задачи радиотеплолокации (заключительный отчет). // Отчет о научно-исследовательской работе. Пермь: ПГУ, 1988, - 79 с.

47. Морозов В.А. Регулярные методы решения некорректных задач. М.: Изд-во МГУ, 1974.- 360 с.

48. Pereversev S.V., Solodky S.G. An efficient discretization for folding ill-posed problems // Math. Numer. Anal.: AMS-SIAM Summer Semin. Appl. Math., Park City, Utah, July 17 Aug. 11, 1995, Providence (R.I.), 1996. - P. 643-649.

49. Petrushin W.V. Fixed points and surjectivity theorems via the A-proper mapping theory with application to differential equations // Lect. Notes in Math.1981, V. 886, P. 367-397.

50. Петухова H.B. Исследование, разработка и применение программно-методических комплексов в высшем образовании. //Диссертация. Новосибирск, 1996.

51. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир,1982.-кн. 1.-3 12 е., ил.

52. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов: Пер. с англ. / Под ред. Ю.Н. Александрова. М.: Мир, 1978. - 848 с.

53. Романовский П.И. Ряды Фурье. Теория поля. Аналитические и специальные функции, преобразование Лапласа: Учеб. пособие для втузов.

54. M.: Государственное издательство технико-теоретической литературы, 1957. -292 с.

55. Сидоренко C.B. Регуляризованные следы возмущенных самосопряженных операторов // «Понтрягинские чтения-10» на Воронеж, весен, мат. шк. «Современные методы в теории краев. Задач», Воронеж, 3-9 мая, 1999: Тез. докл. Воронеж, 1999. С. 226.

56. Соломатин О.Д. К вопросу об инвариантных подпространствах локально выпуклых пространств // Фунд. и прикл. мат. 1997. - 3, № 3. - С. 937-946.

57. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. -М.: Наука, 1979. 285 с.

58. Тихонов А.Н., Дмитриев В.И., Гласко В.Б. Математические методы в разведке полезных ископаемых / Новое в жизни, науке, технике. Сер. «Математика, кибернетика», № 12. М.: Знание, 1983. - 64 с.

59. Ускова Н.Б. О собственных векторах возмущенных дискретных самосопряженных операторов // Конф. по функц. анал. и уравн. мат. физ., посвящ. 80-летию С.Г. Крейна, Воронеж, 7-10 окт., 1997: Тез. конф. Воронеж, 1997, С.51.

60. Федотов A.M. Линейные корректные задачи со случайными ошибками в данных. Новосибирск: Наука, 1982. - 189 с.

61. Федотов A.M. Некорректные задачи со случайными ошибками в данных. Новосибирск: Наука. Сиб. отд-ние, 1990. - 280 с.

62. Функции с двойной ортогональностью в радиоэлектронике и оптике. США, 1961 1968 гг. Перевод и научная обработка М.К. Рахманинова и В.М. Яковлева. М.: Советское радио, 1971. - 256 с.

63. Функции с двойной ортогональностью в радиоэлектронике и оптике. США, 1961-1968 гг. Перевод и научная обработка М.К. Размахнина и В.М. Яковлева. М.: Советское радио, 1971. -256 с.

64. Чочиа П.А. Вероятностная модель контурного изображения. // Иконика: Цифровая обработка видеоинформации. М.: Наука, 1989. - С. 25 - 34.

65. Щепина Е.М. Программно-методический комплекс «Регуляризация алгоритмов цифровой обработки изображений».// Тезисы докладов научно-практической конференции «Новые информационные технологии в образовании», Петрозаводск, 5 июня 1995 г. С. 100-102.

66. Эдварде Р. Ряды Фурье в современном изложении: В 2-х т. Т. 1. Пер. с англ. М.: Мир, 1985. - 264 с.

67. Jublin J., Chunli L. The expression jf the solution of the first kind ill-posed operator equation // Shu xue wuli xuebao = Acta Math. Sei., 1998 18, №3. P. 264269.