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

ИНСТИТУТ ПРОБЛЕМ УПРЛПЛЕШШ РОССИЙСКОЙ АКАДЕМИИ НАУК

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

Впшпяеов Александр Николаевич

РАЗРАБОТКА АЛГОРИТМОВ ДЕКОНВОЛЮЦИИ

Сттопиалт.пость 05.13.01 — ''Управление в техшпсскнх системах''

АВТОРЕФЕРАТ

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

Москва - 1992

Работа, выполнена в Институте проблем управления Российской Академии Наук.

Научный руководитель: академик РАН Я. 3. ЦЫПКИН

Официальные оппоненты: доктор технических наук А. И. БАРКИН доктор технических наук Е. П. МАСЛОВ

Ведущая организация: Центральный научно-исследовательских! Институт комплексной автоматизации

Защита состоится "_"_1992 г. в_час, на

заседании специализированного совета Д002.68.02 Института проблем управления по адресу: 117806, Москва, ул. Профсоюзная, д. 65-

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

Автореферат разослан "_"_1992 г.

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

В. К. АКИНФИЕВ

РОССИЙСКАЯ ГОСУДАРСТВЕННАЯ БИБЛИОТЕКА

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования

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

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

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

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

А

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

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

Цель работы

Целью даппоч работы является:

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

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

■> построение робастпых проиедур деконволгогши

в спптео алгоритмов деконволюцни регулярных сигналов

в реализация полученных алгоритмов па ЭВМ п их испольоовапне для прикладных задач

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

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

Научная новизна

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

2. Исследованы свойства оптимального по дисперсии фильтра деконволюцпи, построенного для заданной (номинальной) системы наблюдений.

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

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

5. Разработана методика обработки сигналов переменной регулярности.

Практическая ценность

1. Предлагаемые алгоритмы д?.\опголюдпп записаны в рекуррентном виде, допускающем экономную и быструю реализацию па ЭВМ.

'2. В зависимости от характера поступления обрабатываемых да.ппых предлагаете:! два класса алгоритмов: алгоритмы деконнолюцлп текущих дачных и алгоритмы деконволюции накопленных данных.

3. На основе полученных аналитических выражении для ошпбии обработки данных робастиым фильтром деконволюции мо;кно оценить целесообразность его прнмепепп-Я.

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

5. Полученные алгоритмы н вспомогательные процедуры реализованы в виде программного продукта па языке что попускает быструю и:-: интеграцию п ре.'!лыше приложения.

Реализация результатов

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

9-86/07 — "Разработка методов идентификации и управления в задачах обработки данных сейсморазведки па нефть и газ",

310-90/07 — "Теория робастых систем управления и обработки дан-пых",

307-91/07 — "Теория робастного управления н условиях неопределенности''.

Прикладные результаты нашли применение в работах по теме "Изучение высокотемпературной сверхпроводимости", проводимой в физическом Институте РАН и по теме "Фонопы", Бсдущейся иа Физическом факультете Московского государсгаенного университета,, о чем имеются соответствующие акты внедрении:.

Апробацшх результатов работы

Результаты работы по теме диссертации докладывались на научных конференциях молодых ученых, проводимых па базе Московского физико-технического института (1987-1990). Основные положения обсуждались на научных семинарах лаборатории № 7 Института проблем управления. Ряд прикладных результатов докладывался па семинаре '"Вопросы высокотемпературной сверхпроводимости", проходившем в Физическом Институте РАН.

Публикации

По теме диссертации опубликовано 4 статьи. Структура и объем работы

Работа состоит по введения, пяти глав и заключения, изложенных на 100 страницах, содержит 39 рисунков, б таблиц, список литературы но 6С наименований. Общий объем диссертации 120 страниц.

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

Введение

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

Первая глава

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

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

э по характеру сигнала п поме,:::: о по требованиям к обрабатывавшей системе в по критерию обработки даппых

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

Вторая глава

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

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

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

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

Уравнение объекта =(к +1) = +_B(ife)ui(fc)

и(0) = г„, k = 0,J

Уравнение наблюдений: у(к) = С[к)х[к) + D(k)v(h)

Априорная ипформацпя А - А(к), В = В(к), С = С(к), D = D(k) — повестпые матрицы

= Sk,J„ £[ic(i)xg] = О A'[u?(ifc)]=0

£[«(fc)uT(n)] = 8Ы1„ Vk,n = 0 = О V£

^(¿К^)] = £knIw E[xa*l] = По Е[х0] = О

Оценка деконволюцпи: й(к) = Втхс(к + 1)

Копариациопная Х1атрпца ошибок деконсолюцип: — — ВгТ{к +

Оценка сглаживания: х(к) = R{k)xc(k) + — 1)

Коиарнационнал матрица ошибок сглаживания: I'x(£) = — R[k)T(k)R(k)

Рекурсии в прямом времени x(fc+l|fc) = Ax(k\k-l) + AR{k)C'[...}+c(k) с(к) = у(к) - - 1), я(0| - 1) = О

R(k + 1) = АД(к) Ат - АЯ(£)СТ[.. .]+СД(£)Ат + ВВТ [...] = ШЯ + CR(k)C , Л(0) = По

Рекурсии в обратном врсмеии i£(J+l) = О

Т(к) = [J-CT[...]+CJJ(ifc)].4IT(ife + l)A[/-CT[...]+CJ?(i!:)]T + + СГ[...]+С, Г(7 + 1) = О

Таблица 1 8

Уралжлио объекта x(h + 1) = +

=(0) = ю. h = Q,J

Уравнение наблюдений: y(fc) = C(¿)s(fc) 4- D(h)v(k)

Аирпорпая информация Л - Л(к), В = В(к), С = С(к), D - П{к) — пппесппи! матриц» [DffcJD^fc)] — пегиро^дргти -- 6knIw £N*)*o] = 0 A>(i)] - 0

i:[v{k)v-(n)] = skniv Vfc, n !?[*(£)*;] = о ЯК£)] = 0 vi

Оценка дскопполюцнп: tЦк) = + 1) - N(k f l)í(fc + 1)]

Кспзри-чциопиая матрица ошсбок дрегопволюцся = I»- Iir[N{k + 1) - N(h + i)I',(k + 1 )N(k. + 1)]Л

Оцепка сглаживания î(fc ! 1) = A¿(k) - BÍ...}+BTN(k-i 1),15(*) t В\...]>Втр{к \ 1) á(0) = II0[II0 + II,и\'(0)11о]-г 11^(0) [...] = 1 -r B~N(k+l)B

Койзриациоиная матрица ошибок сглажнганпя Рх(к + 1) = APzWA1 - B[.. + 1)АРЛк)Щк + 1)5[...] • Вт-

+ Bi...]+B1 Px{0) = Пп[Пп -f ПоЛг(0)Пп]+П„

Pt'xypriüi в обратном пргчсшг

гЩ - + 1) - Л?ГЦк - ^nl-.^lPpV- -г- 1) - Cr[Dir)+y(k)

p{j f 1) = о

N(J i- 1) = 0

Таблппа 2 9

Оценка дсхслшоаюции

а. w{k) = Втхс(к + 1) £с(к) = [I + N(k)R(k)]+[p(k) - N(k)z{k\k - 1)] б. Цк) - BT[f}{k + 1) - N(k + l)£(i + 1)]

Ковариациопная матрица ошибок декопволюцик

а. б. = - ВЦН(к + 1) + + 1)]+Я Р„(к) = - BT[JV(fc + 1) - N(k + l)Pr(jfc + 1 )N(k + 1 )]B

Оценка сглаживапш!

а. х(к) = Щк)хе(к) + х(к\к - 1) С. i(t) = [I + N(k)R(k)} + [R(kMk) + x{k\k~ 1)]

Ковариацпошгал матрица ошибок сглаживался

а. Р,{к) =г ЦЩ-ЦЦЩ^ + К-^ку^Цк) С. Ря(к) = [Л'(А) + Д-1(Ц]+

Рскурсии и пряном иремсш!

£(к + 1|А) = АЦк\к - 1) + ■ .V Ш - СЦк\к - 1)) £(0| — 1) ^ 0 Н(к + 1) = у1К(й)Лт - ЛЛ(£)Ст[...]+Сй(/Ь)Лт -t ВВГ [...] = DDT + CR{k)C~ , Н(0) = И0

Рекурсии в обратном времени

р(к) N(k) = AJp(k + 1) - АЧ1(к + 1)В[.. + 1) + C[DI>T]+y(fe) + = 0 = + \)А- A!N(k + l)B[...]+BTW()b + 1)Л + [...] = J + BTAT(i +l)ii, JV(J 4-1) = 0

Таблица 3

Треть л глава

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

Пусть модель паблюдешти некоторого неизвестного сигнала. и(к) описывается уранением;

у(к) = Щд)и(к) + ((к), (1)

где q — оператор папаздывапия. т.е. с[и{к) — и(к — /); п(к), и ((к) — сигнал и помета — взаимно независимые последовательности случайных чисел с пулевым средним и спектральными плотностями 5Ц(<}) и соответственно. Дискретная передаточная функция принадллежит некоторому классу передаточных функции <7, геометрическим местом частотных характеристик которых является некоторая, вообще говоря, произвольная область ("трубка") 0(ш) па комплексной плоскости.

д = {№(?) : <Е ш = 0^} (2)

Интервал квантования выбран разным единице.

Оценку неизвестного сигнала и(к) будем искать а виде:

й(к) = (.4)

где Т и — соответственно прямое и обратное дискретные преобразования Фурье, а К (и) — иеко горы» фильтр.

Задача робасшои декошадлюцип заключается в поиске такого фильтра К(и>), чтобт.т зпергия ошибки е(к) = и{к) —й(к) не превышала некоторой пеличипы для любой допустимой передаточной функции Иг(а) € О, и зта величина была бы как мо".;шо меньше

,7 = плитах / 5,(и>(4)

л \vaaj о 1 1

Зе(ш) — спектральная плотность ошибки е(/:). Фильтр Л'(ы), минимизирующий критерии (4) будем называть робастпым оптимальным (фильтром деконволтонии.

Как видно (4), сул&гарная^шгабки^анергия декопволюции представляет собой сумму энергий ошибок на каждой из частот ш -- 0,2тг, поэтому процедура поиска оптимального фильтра эквивалентно переформулируется для произвольной частоты. Для простоты и удобства параметр ш в обозпаченнях передаточных фуикции, фильтра и спектральных плотностей далее опускается.

Спектральная плотность Se{w) ошибки декопволюции с{к) — и {к) — й(к) согласно (1) и (3) запишется в виде

St = (1 - А'Н')(1 -KW)SU + KKSt (5)

Таким образом, за дача поиска оптимального робастного фильтра де-копволющш К (4) может быть сформулирована как задача поиска мини-Mai;ca. неотрицательной действительной функции комплексных перемен-шлх St(K, IV) (5), при отом

J' - nii_n тах[5<,(Я, W)) (6)

— дисперсия ошибки деконволюцин в наихудшем случае.

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

Утверждение 1. Всякий фильтр К гарантирует, что для произвольной модели наблюдения IV из круга ЩС, г), где С = 1/К — центр круга, а г — его радиус, дисперсия ошибг;и декопволюции не превосходит величины

« -

*~ |ср '

где Би и — спектральная плотность входного сигнала и помехи соответственно.

Утиержденпе 2. РобастныИ оптимальный фильтр дсконоолюции определяется выражением

Г" 1

где С* — центр круга Д(С*,г*), доапавляюи^го минимум функционалу

где С? — область допустимых частотных характеристик \¥.

Для ряда непараметрнческих неопределенностей (прямоугольник, пл-пипс, ромб) получены аналитические выражения для робастного оптимального фильтра декопволгошга и для дисперсии ошибки БЦ в паихудшем случае. Сравнение этой ошибки с ошибкой оптимального фильтра, построенного для номинальной модели наблюдения, в иаихудшем случае 5" н в точке оптимума приводит к неравенствам

< 5'' < Б'е'.

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

Чевертаа глава

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

Я(д)л(й) = О, Я(0) ^ О,

где Н(д) — полином поглощенпя.

Регулярные сигналы — ото полностью предсказуемые сигналы, т.е.

л(п) = П1(д).ч{к), I — п — к.

где 1)( — полином предсказания па 1 шагов. Показано, что полипом предсказания удовлетворяет нолнпомпальному уравнению

Н{чШч) + з'ВД -1.

Задача заключается в том, чтобы для заданной ARMA модели на блюдешш

Q(q)y(h) = B(q)s(k) + СШ'О, ~™<h< ОС

и для заданного N пайтп фильтр декоиволюцип типа "скользящего среднего"

K(q) = а0 H aig Ч-... + asqN из условия минимума днсперспп ошибки оценивания

Е [(Л(п) - пин,

ирн условии несмещенности оценкн

¿(n) = K(q)y(k) = з(п) + сп{к), Е [еп(/о)] = 0. Окончательный результат формулируется в виде утверждения

Утверждение 3. Оптим/мьный фильтр дсионаолюции конечной заданной степени N опредмяетем по формуле

K(q) = K'(q) -) ВДЯ'Ы.

càc K'(q) минимальное решение полиномиального уравнения

B(q)K'(q) + H{q)Gk-n(q) = ak'nA{q),

а полином R'(q) степени

deg R' — N - deg H — 1 минимизирует функционал ошибки

J = _L / КЪМдЩдЩд^Щд-ЧЛд 2nj J\q\-i A{q)A{q~1) q '

где S((q) — спектральная плотность помехи.

Д:ш упрощенной модели наблюдении

У(к)=--А{к)+((к),

где £(/;) — стационарный процесс — белый гпуссопский шум, вычисление оптпмальпого фильтра сущестпешга упрощается, при этом справедливо следующее утвер.хдепие

Утверждение -1. Оптимальная по конечной выборке оценка декопво-люции определяется по формуле

( т \

¿(Л" - 1) I 5(0) /

Г

( у{Щ \

у(Н- 1)

\ 3/(0) )

при этом

Р = 1 - Е{НЧ1)-ХН\ где матрица II — .чатрица коэффициентов полинома поглощения Н(д)

I А0 0 ••• 0 \ Л0 ••• 0

: ' •. :

II — Л.у : '■■ Л0 0 Нц : /ц

V 0 0 ••• Ллг )

Так как II ■ Р = 0, то как оптимальная оценка так и коэффициенты оптимального фильтра деконволюцпи (строки матрицы .Р) удовлетворяют тому же условию регулярности, что и оцениваемый сигнал.

Решение задачи деконво.иоцип рекуррентным способом сводится к оцениванию вектора приведенных начальных условий, полностью одре-деляющих величину оценки з(к) в произвольный момент к на основании доказанного свойства регулярности оцепки. Процедура оценивания основапа на решении рекуррентного матричного уравнения, размерность которого определяется степенью полинома компенсации ■?/(</)• Так как Dia размерность, как правило, невелика, то реализации алгоритма не встречает серьезных вычислительных затруднений.

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

Питал глава

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

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

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

Заключение

Основные результаты диссертации состоят в следующем:

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

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

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

3. Предлагаемые алгоритмы деконволюции регулярных данных допускают как рекуррептиую, так и нерекуррептиуго реализацию. В пе-рекурреитном виде оценка деконволюции представляет собой взвешенную сумм}' наблюдений. Коэффициенты oí ого фильтра удовлетворяют тому же условию регулярности, что и оцениваемый сигнал. Это же утверждение справедливо и для оценки деконволюцпп по накопленным дакпым.

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

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

ПУБЛИКАЦИИ

Опубликованные работы

По результатам диссертации опубликованы следующие работы:

1. Вишняков А.Н. Идентификация немшпшалыю-фазовых систем при неизвестном нсгауссовском входном воздействии // Труды конференции молодых ученых. - МФТИ, - 1988.

2. Вишняков А.Н. Деконволюцпя по текущим п накопленным данным. Различные критерии // Труды конференции молодых ученых. -МФТИ, - 1988.

3. Вишняков А.Н., Цыпкин Я.8. Адаптивный метод обнаружения на-рушеннй закономерностей по наблюдаемым данным // АиТ. -1991. -'И 0. с. 127-135.

А. Вишняков А.П., Цыпкпн Я.З, Обнаружение парушепип закономерностей по наблюдаемым данным при наличии помех. // АиТ. -1991. - N 12. с. 128-137.

Личный вклад автора

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