Математические задачи цифровой обработки сигналов тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

р ^ О$осковсхий ордена Ленина, ордена Октябрьской революции я ордена Трудового красного знамени г. » • 1 Г' '|С,^суД®рствеии11Й университет им. М.В.Ломоносова Механико-математический факультет

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

Поспелов Владимир Васильевич

УДК 510.6

МАТЕМАТИЧЕСКИЕ ЗАДАЧИ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ

Специальность: 01.01 .ОТ - вычислительна« математика

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

моделировали* и математических метсшов в научных исследовании

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

Москва 1994

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

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

доктор физико-мьтемнтических наук,

профессор Е.А.Гребенников

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

профессор Н.А.Кудряшов

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

доцент А.И.Чуличхов

Ведущее предприятие:

Институт прикладной математики имени М.В.Келдыша РАН

Зашита состоится 1994 г. в^нас^ мии. иа засекании

специализированного совета Л 047.01.04 Лаборатории вычислительной Техники и автоматизации Объединенного института ядерных исследований по адресу: 141980 г. Дубна Московской области, ОИЯИ, Лаборатория вычислительной техники и автоматизации.

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

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

Ученый секретарь

специализированного Совета Иванченко З.М.

2

Актуальность яребяешл.

Цифровая обработка сигналов (ЦОС) и, в частности, обработка изображений н звуковых сигналов, в последние десятилетия привлекает к себе все большее внимание кссдсчстателсй я является в настоящее время одним из главных направлений в развитии информатики и в применениях компьютерных технологий. Наиболеэ ярким выражением актуальности с одной стороны к огромных возможностей, с яругой, является появление так называемой технологиях МиШтс&а.

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

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

Цель роботы.

В работе обобаэкы математические результаты автора, полученнныо в процессе разработки автоматизированных систем обработки изображений {АСОИЗ НИЦТД) и звука (АСОЗ НИЦТД), которые были выполнены в соответствии с дополнительны» заданием к «елевой комплексной программе ГКНТОЦ027.

РпссматриБйкягса математические вопросы существования ярхосткого преобразования с заданными свойствами, проблемы сходства двухградацн-ониых изображений, метояи н алгоритмы парного ьналкт изображений-, проблема аппроксимации функций нескольких переменных суммой произведений функций одного переменного в метриках ¿1, И'*Сив тензорном произведении произвольных гильбертовых пространств, оценки погретно-' сти этих приближений на различных классах функций, доказана в определенном смысле оптимальность данного метода аппроксимации функция двух переменных, привадятся примеры применения этих результатов к за-

дачам сжатия данных.

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

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

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

Научная новизна работы.

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

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

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

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

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

Доказаны теоремы об аппроксимации суммой произведений для случая пространств Соболева. Обобщение теории на случай тензорного произведе-

ния Гильбертовых пространств дало возможность ы гоматнчесхи получить аналогичные результаты в большом количестве ноВ1 >г частных случаев.

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

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

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

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

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

Практическая ценность результатов.

Полученные в работе результаты были внедрены в разработанные под руководством и при непосредственном участии автора автоматизированные системы обработки изображений и звукозаписей в Научно-исследовательском центре технической документации (НИЦТД), в рамках дополнительного задания Государственного комитета по науке и технике к целевой комплексной программы ОЦ 027 в виде соответствующих алгоритмов и программ.

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

б

Апробация работы.

Основные результаты, изложенные в диссертации, докладывались на семинаре по обработке изображении в Институте проблем передачи кнфор-

с

мадии, на семинаре проф. Теляковского С.А. в Матоиатячзском институте PAII, на семинаре проф. СтвчишаС.Б. в Математическом институте РАН, на семинаре акад. Гончаре А.А. в Математическом институте РАН, на общественном обсуждении при представлении системы обработки изображений на государстве)-ную премию в Институте проблем управления, на семинаре акад. Ю.И.Журавлева в ВЦ РАН, на семинаре акад. Бахвалова П.С. на кафедре вычислительной математики механнко-математнческого факультета Московского государственного универснтеа, на научном семинаре ЛВТА по вычислительно^ и прикладной математике ОИЯЭ (г. Дубна), на сеюшаре проф. Морозова В. А. в Научно-исследовательском вычислительном центре МГУ, на семинаре проф. Пытьева Ю.П. на физическом. факультете МГУ им. М.В. Ломоносова, на семинаре в институте Высокопроизводительных Вычислительных Систем РАН, на конференции по теории приближений в г. Ленинград (1989 г.), на 6-й Всесоюзной конференции "Вычислительная техника и системы управления в кинематографии'" (1081), на конференции по теории приближений функций в г. Уфа (1987 г.). На конференции по обработке изображений в г. Дилижан (Армения) (1965 г.). На конференции по обработке изображений в г. Новосибирск в (1988 г.). Отдельные результаты докладывались на Ломоносовских чтениях в МГУ в 1988, 89, 90 годах.

Публнхадяш.

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

Структура я объем диссертации.

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

б

Обзор содержания диссертации

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

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

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

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

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

Коррекция яркостных характеристик заключается в выполнении преобразования:

v = G(ь),

я = «(¡г) - исходное изображение,» — «(») - изображение после обработки, О - передаточная функция яркостного преобразования, ® - точка поля зрения X С Л1 (в дискретном случае х - элемент растра).

Вычисление значений функции О не вызывает затруднений. Проблема заключается в том, как найти такую функцию О, которая обеспечивала бы улучшение контраста изображения. Одним из наиболее эффективных способов нахождения такой функции является приведение распределения яркостей изображения «(г) : = те/(х : и(г) < <) к заданному рас-

пределению #(<). Это значит, что для изображения к должно выполняться тождество

*•„(«) = тпе«(а : Ф) <0 = 0. (1Л)

где г>(а>) = 0(и(л)).

Через (а : А) обозначается шгажество точек I, удовлетворяющих условию А.

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

гистограммой изображения и,

В первом параграфе устанавливаются небходимые и достаточные условия существования монотонного преобразования О, удовлетворяющего (1.1).

Обозначим через Л у область значений функции

Теорема 1.1 Для того чтобы существовала неубывающая функция 8, такая, что тпем(х : 6(и(г)) < {) = 11(1), необходимо и достаточно чтобы выполнялось условие

Дд С Дг- (1.2)

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

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

В $2 рассматриваются структуры сходства и качества изображении.

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

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

р(А,В)= [ (2.1)

•'л

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

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

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

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

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

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

Я Л-аппроксимация в среднеквадратичной метрике впервые была изучена еще в начале века в работе Шмидта. Затем этот способ аппроксимации был надолго забыт. В 1957 и в 197Б гг. появились работы М.Р.Шура-Бура и Р.Д.Баглая и К.К.Смирнова, в значительной степени повторяющие работу Шмидта.

В то же время за рубежом (в особенности в США) этот метод широко применяется в задачах цифровой обработки изображений.

Из недавних работ в этой области можно назвать статьи Мнрощина II. В. и Хромомва В.В., работы Темлякова В.И. н Бабаева М.

Основные результаты этой главы срдержатся в следующих теоремах.

Пусть ч, к — 1,2,..., - сингулярные числа оператора А, дествующего из гнльбертоного пространства Я\ в гильбертово пространство упорядоченные следующим образом:

М > Ы > - > к.1 >

а V'» удовлетворяют сооттношениям

*ф*Аф, ,ф = Атф, М = 1№1Ь = 1- (3.14)

Пусть <7 = ^ в Я2 - тензорное произведение пространств Пу) Любую функцию и € <7 можно разложить в билинейный ряд:

(3.15)

Ото вытекает из следующей теоремы.

Теорема 3.1 Для любого и € С? = Н\ ® II

шГ 11« - г.; 0 == ||и - Чф< 0 ЛНс. (3-16)

Скорость сходимости и оиеих:! погрешности приближения суммой про-изведенчй устанавливаются в следующих теоремах. Теорема 3.3 Если и, (А.)"1«», (0„)г*и € I,, то

£п(и) = «("")> (п — оо), г ~ (гцгз), Г = «»Оа!{г1,Г,}.

Теорема 3.4 Если функция и е ¿а(Я) ан&литична по одной из переменных при каждом фиксированном значении другого переменного, то

Еп = 0(е~'п), (гп -» оо), & = соп«< > 0.

В качестве следствия из общих теорем в тензороном произведении гильбертовых пространств получены результаты по аппроксимации в пространствах Соболева И^''(О), являющихся тензорным произведением пространств Ж3'(/) и с нормой

1М1<"(0) = (Г/ (7.3)

о о

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

пространство И^ (й) с нормой

Н!»^«) = (/ / ("*(■» *) + ») + ^(■» у))^у)1,г> (7.4) о о

в котором свойство

1!«®/3||(у1,1(0) = ИЦЧ/) х (7.1)

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

Для пространств Ии получены ннтегро-днфферепциалыше

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

Вопросы оптимальности данного способа приближенна рассматриваются в теореме 4.1.

Теорема 4.1 Если « 6 то для меры оптимальности метопа приближенна отрезком билинейного ряда с дне ретизадиен фуякикй Шмидта на фиксированной сетке, не зависящей от их номера, справедлива оценка

i<contiM~ , а --, j> = tmnii.r}, q = me*{J,r>. (4.9)

p + g + 1

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

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

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

Пусть И - гильбертово пространство. Рассмотрим оператор А, действующий из прямого произведения Я х Я в Я:

т-А(у,г), >,у, к € Я.

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

Введем понятие сопряженных билинейных операторов. У билинейного (итератора их два. Положим по определению

(а, Л(»,*))=(У.Л" (».■»)). (5.1)

(Б.2)

Опрсяеяеиие 5.1 Если для некоторого А 6 Л и некоторых векторов »,У,* € В таких, что а = у = х = I, справедливы равенства

то число Л — 1/г называете* нормальным значением, в векторы в, у, г -нормальными векторами билинейного оператора А.

Определение 5.2 Билинейный оператор Л называется раздельно вполне непрерывным, если он вполне непрерывен по каздоыу и? аргументов при фиксированном другом аргументе.

Определение 5.3 Билинейный оператор А называется вполне непрерывным по совокупности аргументов, если он каждое ограниченное множество из В х Я отображает в компактное множество из И.

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

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

Для линейных операторов из полной непрерывности оператора А следует полная непрерывность сопряженного оператор». Для билинейных операторов это не так. Например, оператор А(х,у) г» (с,О,О,....О,...), где с = (а, у) = Цаш, вполне непрерывен по совокупности аргументов. При этом оба сопряженных оператора А'1 к Д*' не являются даж^ раздельно вполне непрерывными. Для этого оператора при « = 1 любая тройка в, у, я вркторов, где в = у, ||х|| = 1, * = (1,0,...,О,...) будет решением системы уравнений (Б.8).

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

Определение 5.4 Билинейный оператор называется вполне непрерывным, если каждый из операторов Л, А*1, А*г вполне непрерывен по совокупности аргументов.

Теорема 6.1 Если билинейный оператор А ■. В х Я В вполне непрерывен по совокупности аргументе®, то существует по меньшей мере одно нормальное значение.

*г = А(у, х), $у = Л'1(*. *). " = *),

(5.8)

Теорема 5.2 Если и в -Ы/3), то существует число » и функции а^й, гх е (I = {0,1]) такие, что

тЬ 11« - а © у © = II» — ац ® V! Ъ = -

Ы1 = 1ЫЫЫ = 1-

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

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

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

«С*1.*».<в> — +

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

В рассматривается задача приближения функции двух переменных с уймой произведений функций одного переменного в норме С. Этот случай значительно труднее, чем аналогичная задача в среднеквадратической норме. Достаточно сказать, что наилучшее приближение может не суив-ствсяать, о чем свидетельствует теорема Брауна: существует функция вида *чМ®)(у)> определенная на некотором прямоугольнике Я = {(», у) : а <а <Ь,с <у < <!,}, для которой не существует наилучшего приближения ЕГ_г*(*М»)в С.

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

Дл» случал равномерной ие1рики в диссертации получены следующие результаты:

Теорема 0.1 Для того чтобы фо ® фо бы>:о наилучшим приближением чеобходнмо, чтобы выполнялись следующие условна:

X). Для всякой функции а 6 С([0, X]) существует точка (»', у') такая, что

[«(»',«') - < 0;

2). Для всякой функции /? € С{[0,1]) существует точка (»",у") такая, что

[»(•",»") - М*")Му"ШУ"Ш'") < о-

Определение 6.1 Бели одна из функций фиксирована и ннфимум

Фо, Фо ■■ II» - А) ® ^о||с = ьг ||1» - ф ® =

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

Теорема 6.2 Условия 1), 2) необходимы и достаточны для того, чтобы ш( |[и - ф 0 ,Со)||с = 11« - Фо ® *о)||<;,

шГ||и -фа»= 11«- Фо в 1М1|с-*

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

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

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

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

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

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

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

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

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

И** - »~ц < ?<i.

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

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

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

Краткая формулировка иетеда. Рассмотрим систему линейных алгебраических уравнении

¿3 = /, я,/6 Я, (8.1)

где Я - Евклидово пространство размерности п со скалярным произведением (.,.) , Л - матрица размерности », возможно вырожденная. Решение ¡■рапнепнл (9.1) будем понимать в смысле минимизации невязки

в:<щп||Л* —/||, что эквивалентно системе уравнений

Л'Лг = Л"/- (9.2)

Пусть задан некоторый базис «»1>...,»»„, такой, что (ш4,и/,-) = по крайней мере для одного из вектороз VI/ Лад/ ф 0 и (Д Аы/) Ф 0 коти бы для одного ].

Для численного решении (9.1) предлагается следующий итерационный процесс

«°=0, = (9.5)

д = атдтах{—-———•: ф 0), (9.4)

¡ ЦЛ^-1!

- индекс, при которой достигается максимум в (9.4). Если таких индексов несколько, то берется любой, например, наименьший, Максимум берется по тем индексах!, для которых Лшу ^0.

Так как /*+1 + Ла'+' = + Л»* = ... = + Л»° = /, то /* = /—Ля* и соотношения (9.Б),(9.6) можно записать в виде одной итерационной формулы:

" = ' + ПЛ.,,)!!' (9'7)

Итерационный процесс (S.3),{9.4),(9.7) сходится со скоростью геометрической прогресня без каких-либо ограничений на матрицу А.

Теорема 9.1 Пусть / 6 ¡т{А), тогда я методе (9.3),(9.4),(9.7) последовательность является фундаментальной я сходится к некоторому решению системы уравнений (9.2) со скорость» геометрической прогрессии, т. е.

¡1«* - в~!| < Сд\ 9 < 1, lim г\

i—оо

где д - константа, зависящая от базиса {v>j} и от оператора Л.

Замечание. Векторы vi} не обязательно водки ы быть Ъртоиормнро-ваннымч н нх число может быть меньше размерности пространства.

От условия / е 1т(А) можно освободиться. Справедлива следующая

Теорема 9.2 В методе (9.3),(9.4),(9.7) последовательность »* является фундаментальной и сходится к некоторому решению системы уравнений

А'Аа = А* f со скоростью геометрической прогрессии, т. е.

II®* - »"II < Ggk, q < 1, »"= lim »*,

Ь—со

где j - константа, зависящая от базиса } и от оператора А.

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

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

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

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

Формулировка метода дм реализации на спецпроцессорах.

Пусть F матрица перехода от базиса ej ж базису u/j, (Беля wj базис дискретного преобразования Фурье (ДПФ), т.е.

/ч ,

iiy(») = eajK——),

то преобразование совладает с обычным ДПФ). Будем называть преобразование

а = {(/,«>о).....(/,^-1)}

дискретным преобразованием Фурье по базису Ы). Запишем вектор у с компонентами

У! - -Аа1")^)

с помощью матрицы ДПФ по базису {ад,-}: у = — Л>*)]-

Определим оператор Ма:

М у = { вСЛИ ~ " ЛЛХ' " 0, в противном случае.

С помощью этих операторов итерационный процесс (9.7) можно модифицировать следующим образом

»*+1 = + чР~хМаР(А*и ~ Ая*)). (9.18)

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

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

Б $10 рассматривается одномерная лебеговсяая аппроксимация и ее применение к задачам сжатия одномерных массивов информации. Доказаны некоторые теоремы о сходимости предлагаемых методов. *

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

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

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

В $12 рассмотрена задача аппроксимации оператора дифференцирования рекурсивным фильтром. При ее исследовании получены новые теоретические результаты по теории рациональной аппроксимации функции

* + 1

log-

* - 1

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

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

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

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

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

В §12 рассматривается задача интегрирования сигнала рекурсивным фильтром.

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

Исследование устойчивости при условии максимальной аппроксимации приводит к интересным математическим задачам, связанным с теорией ортогональных многочленов. Этим вопросам посвящен §12.

Пусть у(зс) достаточно гладкая функция. Обозначим через D оператор дифференцирования: (Dy)(x) = у'(ав); через Е/, - оператор сдвига:

(А\у)(я) = 1/(1 + Л); и через I тождественный оператор. Любой конечно-разностный оператор можно представить в виде многочлена от оператора сдвнга. Задача аппроксимации оператора дифференцирования устойчивыми конечно-разностными операторами ставится следующим образом: найти такие конечно-разностные операторы р(£\) и а{Е\) (многочлены р(С) и а(() называются характеристическими многочленами этих операторов), чтобы в соотношении

{,(£„') - ЬП<,(Ь\)Мг) ~ , (^ —► О) (12.9)

число р было максимально возможным. Бели а/, /Э/ - коэффициенты многочленов р(С) и а [О соответственно, то величина рт4г.(п) определяется по формуле

Рт«,(п) = тахр(а0,...,ап; (80.....Рп)>

где максимум берется по всем таким параметрам а,-, /Зу, что многочлен />(0 устойчив (его корни по модулю не превосходят единицу, а кратные - строго меньше единицы).

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

В работе Бахвалова Н.С. для г» < 10, а затем в работе Далькыиста для любых п был получен следующий результат: Если разностный оператор р(£\) устойчив и

а» 5*0. (12Ю)

то для максимального значения р в соотношении (12.9) справедлива формула

• , . ( п + 2,если п—четно, /.„..>

Р,П»*(") = \ ' (12.11)

V п + 1,если я —нечетно,

Хотя частные примеры формул без условия (12.10) с более высоким порядком, чем определено формулой (12.11), были известны уже в 1970 г., в общем случае найти выражение для рта*(п) не удавалось. В работе автора в 1988 г. Сила напучена оценка

РтаЛ») >П+С1п + С2,

где Ci > 0, cj - абсолютные константы; для них вычислены оценки.

Основным результатом этого параграфа является следующая теорема.

Теорема 12.1. Существует устойчивый конечно-разностный оператор />(£*) — ЛОи(^д), для максимальной степени аппроксимации которого справедлива оценка

7W»(») >п+ -г~—п + Си (12,12)

V2 + 1

где Ci, - абсолютная константа.

Данная задача сводится к аппроксимации функции /од~1 ^^ рациональными функциями с ограничением на расположение полюсов - они все должны лежать в левой полуплоскости или в точке г = 1, Полюс в точке z = 1 соответствет полюсу в бесконечно удаленной точке в плоскости а это в свою очередь означает равенство нулю одного или нескольких (в зависимости от кратности полюса) старших коэффициентов многочлена />({).

Исследования этого параграфа основаны на изучении нового класса ортогональных многочленов на отрезке [—1,1] с весом

,.(*) = (1 - *) V + (12.16)

1 - а

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

Определение 12.1. Рассмотрим систему ортогональных многочленов {Р„(х)} на отрезке {—1,1] с некоторым весом />(х). Назовем показателем устойчивости системы ортогональных многочленов такое целое число М, что при всех п < M все корни многочленов Рл(г) отрицательны, а при п > M у многочлена Рп(г) имеется по крайней мере один положительный корень.

Очевидно, если взять вес р,(г), то M будет функцией от /: M = M(i). Вычисление этой функции лежит в основе доказательства оценки (12.12).

Характеристическим свойством функции M (г) является то, что при к < М(») многочлен Pkt,(x), ортогональный с весом р,(z), не имеет корней, больших нуля (устойчив), а при h > M(t) обязательно имеет хотя бы один такой корень (неустойчив).

Таким образом, М(») - это то критическое значение степени многспле-на при переходе через которое устойчивость многочлена сменяется

неустойчивостью.

Теорема 12.2. Для функции М{г) справедлива двусторонняя оценка

——, + Сх <, Лф) < -у-« + С„

где Ох, О7 - некоторые абсолютные константы.

Отсюда уже нетрудно доказать основную теорему 12.1 об оценке максимальной степени аппроксимации устойчивого интегрирующего фильтра. Этот результат может быть сформулирован также следующим образом: Теорема 12.3. Пусть рациональная функция

аппроксимирует функцию ¡од~1 ^у в следующем смысле:

¡0д -" ~ --ТГ~(~Г> {*-*«>),

г-1 Нп- Ця) х

причем, на нули знаменателя наложено условие: они лежат либо в левой полуплоскости, либо в точке х «= 1. Тогда максимальный порядок аппроксимации р удовлетворяет неравенству

•/з-х

~г—* ^3 + 1

Рт««(»>) > » + ~р-П + Оа,

г да Оа - абсолютная константа.

Пример устойчивой конечно-разностной аппроксимации оператора дифференцирования с порядком п + 3 построен в работе автора [18]. В этом примере п = б, р = 9, <»4 = = ае = О.

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

В приложениях приведены примеры цифровой обработки черно-белых и цветных фотографий с помощью автоматизированном системы обработки изображений (ЛСОИЗ) НИЦТД СССР, разработанной под руководством и при непосредственном участии автора в соответствии с дополнительным заданием к целевой комплексной программе ГКНТ ОЦ 02?, а также таблицы и графики, иллюстрирующие методы и алгоритмы цифровой обработки

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

ОсЕоанме результаты

- Теорема о необходимых и достаточных условиях существования яр-костного преобразования к заданному распределению;

- Алгоритмы парного анализа изображений при яркости ых преобразованиях;

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

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

- Доказательство оптимальности £П - аппроксимации и получение соответствующих оценок;

- Теория ЕП - аппроксимации для Соболевских пространств;

- Теорема о необходимых условиях существования наилучшего приближения в метрике С;

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

- Разработка метода решения задачи восстановления утраченных частей сигнала и обобщение метода на случай вырожденных систем линейных алгебраических уравнений;

- Доказательство теоремы сходимости метода оптимального спуска по базису при самых общих условиях иа матрицу и получение оценки скорости сходимости;

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

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

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

___ - Внедрение рассмотренных выше результатов в процессе разаработки двух автоматизированных систем (обработки изображений - АСОИЗ и обработки звукозаписей - АСОЗ) в соответствии с дополнительным заданием

х целевой комплексной программе ОЦ 027 Государственного Комитета по науке и технике.

Основные результаты диссертации опубликованы в следующих работах: 1. Морозов В. А., Поспелов В.В. Цифровал обработка сигналов.- М.: Нзд-1Ю МГУ, 1987.

2. Борилин Б.Л., Поспелов В.В. Реставрация и консервация фотодокументов с помощью ЭВМ// Экспресс-информация ВНИИДАД. 1980. N2(11).

0.1-е.

3. Борилин Б.Л., Поспелов В.В. Автоматизированная реставрация кинофотодокументов с помощью ЭВМ// Техника кино и телевидения. 1981. N9.

4. Борилин Б.Л., Поспелов В.В. Автоматизированная реставрация кинофотодокументов с помощью ЭВМ// Тезисы докладов б Всесоюзной конференции "Вычислительная техника и системы управления в кинематографии". 1981.

Б. Горбунов А.Л., Поспелов В.В. О разрешимости и сходимости метопов типа Адамса с неустойчивым оператором // Ж. вычисл. матем. и матем. физ. 1976. т16. N2. О. 369-371.

6. Жихарев В.Ф., Поспелов В.В. Применение ЭВМ для реставрации звукозаписей// Труды НИЦТД СССР. 1984. С.26-33.

7. Извольский В.А., Поспелов В.В. Цифровая реставрация звукозаписей// Труды НИЦТД СССР. 1985.

8. Крылов Б.В., Поспелов В.В., Эрастов Д.П. Реставрация документов оптихо-фотографическимн методами совместно с цифровыми методами обработки изображений / / Проблемы физико-химической сохранности, организации отбора, хранения и поиска архивных документов (Исследования и методические разработки НИЦТД СССР) ч.Ц. М., 1983. С. 71-77.

9. Крылов Б.В., Поспелов В.В. Восстановление информации текстовых документов с помощью ЭВМ// Труды НИЦТД СССР. 1985. С.24-37.

10. Малышев М.И., Поспелов В.В. Использование автоматизированной системы обработки изображений для обеспечения сохранности особо ценных фотодокументов// Экспресс-информация ВНИИДАД. 1984. N4. С.12-23

11. Михайлов O.A., Малышев В.В., Поспелов В.В. Основные проектные решения по разработке автоматизированной системы обработки изображений (АСОИЗ) НИЦТД СССР// Труды НИЦТД СССР. 1985. С.3-17

12. Носков Ю.В., Поспелов В.В. Об одном классе ортогональных многочленов // Вестник МГУ, Сер. 16, Вычисл. матем. и киберн. 1990. N 4. сс. 44-48.

13. Поспелов В.В., О семействе операторов продолжения, Матем. заметки, 22, вып.2, 1977, сс.216-219.

14. Поспелов В.В., О приближении функций нескольких переменных произведениями функций одного переменного: Препринт К 32. М.: ИПМатем. АН СССР, 1978.

15. Поспелов В.В., О погрешности приближения функции двух переменных суммами произведений функций одного переменного// Ж. вычисл. матем. н матем. физ. 1978. Т.18. N 5. с.1307-1308.

16. Поспелов В.В., Чичагов А.В., Метод восстановления утраченных фрагментов сигнала// Автометрия, 1988, N1, с. 60-64

17. Поспелов В.В. Методы типа Адамса с неустойчивым оператором // Ж. вычисл. матем. и матем. физ. 1976. т16. N6. С. 1467-1479.

18. Поспелов В.В. Об одном методе исследования устойчивости и аппроксимации разностных схем// Ж. вычисл. матем. и матем. фиэ. 1988. т28. N2. С. 198-208.

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

20. Поспелов В.В. Исследования в области применения автоматизированной системы обработки изображений// Труды НИЦТД СССР, 1979. N2. С. 85-95.

21. Поспелов В.В., У разов В.О. Технология страхового копирования в цифровой форме особо ценных документов// Труды НИЦТД СССР. 1984. С.49-52

22. Поспелов В.В. О максимальной степени аппроксимации операторов дифференцирования устойчивыми конечно-разностными операторами// Всесоюзный симпозиум по теория приближения функций, (тезисы доклада) Уфа, БФ АН СССР. 1987. С.133-134.

23. Поспелов В.В. Об одном численном метопе коррекции контраста изображений// Автометрия. 1988. N1. С.54-59.

24. Поспелов В.В. Метод оптимального спуска по базису для решения вырожденных систем линейных алгебраических уравнений // Ж. вычисл. матем. н матем. физ. 1990. т.31. N 7. сс. 962-969.

25. Поспелов В.В. О приближении функции двух переменных суммой произведений функций одного переменного в пространствах Соболева// Вести. Моск. ун-та. Сер. 1, Математика. Механика. 1990. N 4. сс. 6-10.