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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего

профессионального образования

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

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

Служивый Максим Николаевич

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

ИНТЕРПОЛЯЦИИ СЛУЧАЙНЫХ ПОЛЕЙ ПО

ДИСКРЕТНЫМ ОТСЧЕТАМ

Специальность: 05.13.18 – «Математическое моделирование, численные методы и комплексы программ»

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

Научный руководитель д. т. н., профессор К.К. Васильев Ульяновск –

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ………………………………………………………… ВВЕДЕНИЕ…………………………………………………………………………..

ГЛАВА 1. МЕТОДЫ МОДЕЛИРОВАНИЯ И ИНТЕРПОЛЯЦИИ

СЛУЧАЙНЫХ ПОЛЕЙ…………………………………………………………… 1.1. Постановка задачи…………………………………………………………….. 1.2. Методы имитации дискретных случайных полей …………………………. 1.3. Методы интерполяции случайных полей………………………………….. 1.4. Оптимальное позиционирование измерителей …………………………….. 1.5. Выводы…………………………………………………………………………

ГЛАВА 2. АЛГОРИТМЫ ИНТЕРПОЛЯЦИИ СЛУЧАЙНЫХ ПОЛЕЙ

НА МНОГОМЕРНЫХ СЕТКАХ……………………………………………..… 2.1. Постановка задачи ……………………………………………………………. 2.2. Анализ погрешностей интерполяции многомерных случайных полей по незашумленным наблюдениям………………………………………………. 2.3. Алгоритмы интерполяции случайных полей по зашумленным наблюдениям……………………………………………………………………….. 2.4. Алгоритмы интерполяции случайных полей по оптимальным оценкам….. 2.5. Выводы…………………………………………………………………………

ГЛАВА 3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ ПИЛОТ-СИГНАЛОВ

НА МНОГОМЕРНЫХ СЕТКАХ ……………………………………………….. 3.1. Постановка задачи……………………………………………………………. 3.2. Оптимизация размещения пилот-сигналов на последовательности отсчетов…………………………………………………………………………….. 3.3. Оптимизация размещения пилот-сигналов на двумерной сетке………….. 3.4. Особенности программной реализации алгоритмов размещения пилот-сигналов…………………………………………………………………… 3.5. Выводы……………………………………………………………………….

ГЛАВА 4. ПРИМЕНЕНИЯ АЛГОРИТМОВ ИНТЕРПОЛЯЦИИ И

ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ ПИЛОТ-СИГНАЛОВ…………………. 4.1. Постановка задачи…………………………………………………………. 4.2. Применения методов интерполяции при проектировании многочастотных систем связи с OFDM………………………………………… 4.3. Авторегрессионные модели замираний в многолучевом канале связи… 4.4. Приложения методов интерполяции к обработке изображений………… 4.5. Выводы……………………………………………………………………… ЗАКЛЮЧЕНИЕ………………………………………………………………….. БИБЛИОГРАФИЧЕСКИЙ СПИСОК………………………………………….. ПРИЛОЖЕНИЕ 1. Вычисление ковариаций ошибок оценивания…………… ПРИЛОЖЕНИЕ 2. Вычисление дисперсии ошибки интерполяции для различных конфигураций расположения отсчетов…………………………….. ПРИЛОЖЕНИЕ 3. Акт внедрения результатов диссертационной работы в учебный процесс…………………………………………………………………..

СПИСОК СОКРАЩЕНИЙ

АКФ – автокорреляционная функция;

ДПС – дискретное синусное преобразование;

ДПФ – дискретное преобразование Фурье;

КФ – корреляционная функция;

МСИ – межсимвольная интерференция;

ОПК – оценивание параметров канала;

ОСШ – отношение сигнал/шум;

СКО – 1) среднеквадратическая ошибка, 2) среднеквадратическое отклонение;

СП – случайное поле;

УО – устройство оценивания;

BPSK – Binary Phase Shift Keying (двоичная фазовая манипуляция);

MPSK – M-ary Phase Shift Keying (М-ичная фазовая манипуляция);

OFDM – Orthogonal Frequency Division Multiplexing (ортогональное частотное разделение каналов);

PSK – Phase Shift Keying (фазовая манипуляция);

QAM – Quadrature Amplitude Modulation (квадратурная амплитудная модуляция);

ВВЕДЕНИЕ

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

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

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

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

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

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

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

1. Провести сравнительный анализ известных алгоритмов интерполяции одно- и двумерных СП.

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

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

подвижным объектом.

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

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

Методы исследования основываются на теории вероятностей, теории оптимальной линейной фильтрации СП, методах дискретной математики. При разработке программного обеспечения применялись численные методы и методы объектно-ориентированного программирования в среде Matlab 5.3.

Научная новизна. В диссертации получены следующие новые научные результаты:

1. Предложен алгоритм интерполяции случайных полей на основе оптимальных оценок. Проведен сравнительный анализ точности алгоритмов интерполяции СП на основе зашумленных наблюдений и на основе оптимальных оценок. Показано, что при интерполяции на основе оптимальных оценок удается достичь выигрыша по дисперсии ошибки интерполяции порядка 10-30 % - для одномерного СП и в 2-3 раза – для двумерного СП по сравнению с алгоритмом интерполяции по зашумленным наблюдениям.

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих НТК:

• 6th Open German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6-2003, August 25-30, 2003);

• Х Международная НТК «Радиолокация, навигация, связь» (Воронеж, 2004 г.);

• VII Международная конференция «Распознавание образов и анализ изображений» (Санкт-Петербург, 2004 г.);

• VII-VIII Международные конференции и выставки «Цифровая обработка сигналов и ее применение» (Москва, 2005, 2006 гг.);

• 61 Научная сессия, посвященная Дню Радио (Москва, 17-18 мая 2006 г.);

• ежегодные конференции профессорско-преподавательского состава Ульяновского государственного технического университета (2004-2006 гг.).

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

Кратко описаны известные методы позиционирования датчиков на дискретной сетке.

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

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

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

ГЛАВА 1. МЕТОДЫ МОДЕЛИРОВАНИЯ

И ИНТЕРПОЛЯЦИИ СЛУЧАЙНЫХ ПОЛЕЙ

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

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

Наряду с вышеупомянутым, во многих приложениях, связанных с системами обработки данных глобального мониторинга Земли, сжатия изображений и томографии, а также при проектировании многочастотных цифровых систем мобильной связи 4 поколения [22] существует задача интерполяции непрерывного многомерного СП, заданного на прямоугольной дискретной сетке, содержащей N узлов по наблюдениям в M узлах, причем M < N ; или, другими словами, восстановления СП по неполным наблюдениям.

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

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

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

1.2. Методы имитации дискретных случайных полей При решении задач обработки СП важным этапом является выбор адекватной модели наблюдений [5, 10, 24, 44, 45]. В настоящее время не существует универсального способа формирования СП с произвольно заданными характеристиками. Поэтому известные модели СП соответствуют корреляционной функции, распределение амплитуд и т.п.) [16, 46, 57, 58, 81].

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

Наиболее изученными являются авторегрессионные (АР) модели СП [5, 7, 16, 21, 29, 30, 37, 58, 59, 77, 84, 87, 134]. Это объясняется тем, что на основе АР уравнений был разработан математический аппарат для моделирования случайных последовательностей. Центральное место в его развитии, как и в области обычных одномерных сигналов, отводится теории гауссовских полей.

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

Известно достаточно большое количество публикаций, развивающих эту область теории сигналов [16, 58, 80]. Вполне оправданным представляется большое внимание, уделяемое рекуррентным механизмам формирования полей [16, 29, 77, 87, 106]. Вместе с тем, отсутствие систематических методов в разработке моделей превращает решение каждой конкретной задачи в достаточно сложный научный процесс, что далеко не всегда оправдано. В настоящей работе при рассмотрении моделей СП используется идея представления спектрально-корреляционных характеристик многомерных сигналов в разделимой по пространственным координатам форме [58]. Это дает возможность использования достижений теории одномерных сигналов, приводя относительно простое решение ряда задач статистической обработки [77-80].

Эффективным методом решения задач статистической обработки СП служит спектральный анализ [7, 16, 21, 27, 135]. К сожалению, как уже было упомянуто, существует лишь узкий класс так называемых «разделимых» СП на многомерных сетках [58, 77-80], для которых можно получить полезные для приложений аналитические соотношения. В частности, важнейший класс изотропных СП дискретного аргумента не удается исследовать известными методами спектрального анализа. Это объясняется несоответствием декартовой системы координат в пространстве R0N точек с целочисленными координатами и естественной для изотропных СП сферической системой координат в R N.

бесконечных размеров: J = j : { < jk < }k =1. При условии положительной определенности корреляционной функции (КФ) F ( d ) - спектральная мера на прямоугольнике = : { 1 }i =1. Если F ( d ) абсолютно непрерывна относительно меры Лебега на, то равенство Как показывает анализ, реальные возможности получения компактных расчетных соотношений для спектральной плотности (1.2) связаны с полями, КФ которых могут быть представлены в виде произведения или линейной комбинации таких произведений. Например, если наоборот. Во-вторых, должен быть задан алгоритм, определяющий, каким l J, предшествующих очередному элементу j. Такую область G j конечных размеров обычно называют каузальным окном, каузальной маской или областью локальных состояний [15, 16, 27]. Наконец, для формирования СП {x, j J } с определенными вероятностными характеристиками на каждом шаге рекуррентных вычислений функция x j = j ( xl, l G j ) должна включать случайных величин.

Таким образом, представление СП на основе рекуррентной процедуры должно иметь следующий вид где G j - области элементов l J, на которых уже определены предыдущие значения СП частным случаем (1.4) является линейное стохастическое уравнение авторегрессии-скользящего среднего [7] для случайных последовательностей.

Однако в отличие от своего одномерного аналога, свойства СП порождаемого (1.5), в настоящее время изучены не полностью даже для изменяющимся видом областей G j = G и Y j = Y :

авторегрессии [16, 77] свойства которого для двумерного СП изучались в большом числе работ [15, 27, 77-80].

Для того, чтобы уменьшить число слагаемых в (1.6), (1.7) и упростить анализ, в работе [58] вводятся векторные СП квадранта и Y G к простейшему виду:

где lk = ( 0...010...0 ) - единичный вектор k -й координатной оси; l0 = 0 ; Ak и n n -матрицы. Соответственно уравнение (1.7) пространственной следующим образом [16] Размерность n вектора x j, необходимая для преобразования уравнения (1.6) в (1.7), определяется видом области G. В работе [58] показано, что при соответствующем выборе матриц Ak, k = 1,2,..., N, возможно представление (1.6) в виде (1.8).

«трехточечная» АР-модель [16, 87]:

Порождаемое моделью (1.10) СП имеет следующую КФ:

Наиболее существенный недостаток данной модели – множительность КФ. В расположены на ромбе с центром в (i, j ). В то же время, сечениями КФ реальных полей являются обычно различной кривизны эллипсы.

Для скругления сечений КФ СП необходимо увеличивать порядок марковости (расширять область локальных состояний). Так, например, пятиточечная модель СП [16] позволяет получить СП с разнообразными формами сечений КФ. Однако применение этой модели на практике ограничено в связи с отсутствием на пятиточечной модели для произвольно заданной КФ.

В настоящее время пока не удалось получить какие-либо общие рекомендации к построению моделей неоднородных СП вида (1.6)-(1.9) из-за многообразия возможных видов определения матричных коэффициентов на n мерной сетке J. В связи с этим следует ограничиться частным, но важным для приложений классом однородных СП { x j, j J }, для которых можно получить ряд полезных результатов.

Другой вариант расчета КФ может быть основан на методах спектрального анализа [58]. Для этого выполним n -мерное z -преобразование СП (1.6). При этом нетрудно получить следующую связь x ( z ) = H ( z ) ( z ) между z преобразованиями x ( z ) и ( z ) СП x j и j, причем передаточная функция линейного фильтра (1.6); z l = z1l1 z22... z N. В этом случае спектральная плотность СП x j может быть представлена в виде Рассмотрим в качестве примера двумерное СП, заданное одной из наиболее простых моделей случае передаточная функция (1.13) фильтра запишется в виде коэффициентов [16]. Вместе с тем, для одного частного случая, когда 11 = 10 01, анализ СП упрощается. Действительно, передаточная функция (1.15) приводится к виду т.е. может быть представлена в виде произведения передаточных функций R ( r1, r2 ) = R ( r1 ) R ( r2 ) = X 10 01 КФ случайных последовательностей.

Случайные поля дискретного аргумента, спектральные плотности которых могут быть факторизованы объект для исследований. Двумерное разделимое поле впервые было рассмотрено в работе [87]. В дальнейшем полученные результаты [87] были существенным образом расширены и обобщены на СП произвольной размерности [77-80].

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

ная ПК НК Примечание. Все диагональные стрелки на рисунках соответствуют, горизонтальные – и вертикальные –.

представляющие собой аппроксимирующий шаблон некоторого непрерывного оператора в частных производных и поэтому имеющих ясный физический смысл (процессы диффузии, рождения и гибели, колебательные процессы и т.п.). Соответственно принятой классификации моделей можно указать порождающие их дифференциальные уравнения в частных производных (ДУЧП): гиперболические ДУЧП (каузальные модели), параболические некоторые из разностных операторов и соответствующих им непрерывных прототипов приведены в табл. 1.1. Параметры цифровых шаблонов (,, ) определяются разностной аппроксимацией конкретного ДУЧП [23, 66, 113, 114] или идентифицируются по КФ требуемого вида каким-либо из известных методов [21, 29, 30].

Такое соответствие имеет весьма важные последствия как для построения модели (анализ устойчивости, стационарности), так и для построения алгоритмов обработки (использование разностных методов) в силу хорошо развитой теории ДУЧП [60, 66].

В работе [21] описаны каузальные и полукаузальные модели, приводящие к преобразовать и перейти к матричной записи для ПК1 Q = I ( I – единичная матрица); для ПК2, ПК3 Q – трехдиагональная теплицева матрица:

теплицева матрица:

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

Модели высших порядков могут обеспечить лучшую аппроксимацию реальных изображений. Однако выбор модели обусловлен, помимо требования точности описания, возможностью построения эффективного алгоритма обработки [16, 135]. С учетом этого рассмотренные модели хорошо соответствуют реальным данным, обладают существенными преимуществами с вычислительной точки зрения, позволяя строить рекуррентные процедуры оценивания и использовать при обработке быстрые спектральные преобразования [27, 86, 89].

Многомерные СП стали объектом исследований сравнительно недавно и именно этим объясняется далекое от завершения, а во многих случаях носящее постановочный характер, изложение рассмотренных математических моделей на пространственных сетках. При отборе вероятностных моделей СП в данной работе предпочтение было отдано таким методам представления СП на многомерных сетках, которые позволяют дать наиболее простое и, вместе с тем, полное вероятностное описание СП, позволяющее решать разнообразные результате за рамками изложения остались важнейший класс гиббсовских СП [20, 50], имитация которых в многих случаях требует больших вычислительных затрат [20, 57], а также множество моделей, например, волновых [41] и моделирования для оценки эффективности и устойчивости алгоритмов, предназначенных для практического использования.

1.3. Методы интерполяции случайных полей В научных работах по обработке СП [12, 53, 56, 61, 63, 92] в основном, как правило, рассматриваются алгоритмы фильтрации и восстановления СП для случаев, когда область наблюдений совпадает с самим СП, т.е. когда наблюдаются все его элементы. Будем называть такие наблюдения полными, отличая их тем самым от неполных, когда наблюдаются или доступны обсуждаемой задачи термин «восстановление» означает интерполяцию, т.е. по наблюдаемой (возможно малой) области строится оценка СП на всей области его задания [21]. Задачи такого рода возникают при восстановлении пространственного сигнала по точечным измерениям с датчиков, при сжатии данных, при обработке изображений, когда некоторые области изображения (например, некоторые строки или блоки строк) необратимо искажены и т.д.

Рассмотрим основные положения теории интерполяции СП [47, 81, 93].

Интерполяция пропущенного значения.

{x (t ), t T } - стационарный процесс с абсолютно непрерывной спектральной функцией F ( ). Предположим, что известны значения x ( s ) ( s t0 ). Требуется осуществить оптимальную (линейную) интерполяцию x ( t0 ) пропущенного значения x ( t0 ). Величина значения.

- его спектральная плотность, то оптимальная линейная интерполяция x ( t0 ) пропущенного значения x ( t0 ) дается формулой спектральная плотность. Обозначим через f ( (если det f ( ) 0 ) либо обобщенную обратную (если det f ( ) = 0 ). Последнее интегрируема, то оптимальная линейная интерполяция x ( t0 ) пропущенного значения x ( t0 ) дается формулой где ( ) - спектральный процесс для { x ( t ), t T }. При этом матрица ошибок Пример 1. Пусть { x ( t ), t T } - марковский в широком смысле процесс со Оптимальная линейная интерполяция x ( t0 ) пропущенного значения x ( t0 ) дается формулой Интерполирование значений стационарного процесса с непрерывным временем по наблюдениям в равноотстоящие дискретные моменты. Пусть {x (t ), t T } - скалярный стационарный процесс с непрерывным временем, спектральная функция F ( ) которого абсолютно непрерывна. Предположим, спектральный процесс. Ошибка интерполяции 2 = M x ( t ) x ( t ) В частности, если 2 = 0, то процесс { x ( t ), t T } может быть безошибочно необходимо и достаточно, чтобы f ( ) обращалась в нуль вне отрезка [, ].

В этом случае имеет место формула Котельникова-Шеннона [6, 49, 51, 90] среднеквадратической ошибки восстановления. Кроме того, наблюдения предполагаются точечными (пространственное осреднение отсутствует), а аддитивный шум измерений – белым.

Прежде чем обратиться к двумерной задаче, рассмотрим некоторые результаты для одномерных сигналов [21]. Рассмотрим задачу восстановления совокупности M её измеренных отсчетов (рис. 1.1):

где подмножество K n образовано прореживанием соответственно характеру измеряемых элементов последовательности {i1, i2,..., iM } (на рис. 1.1 указанное подмножество принимает числовые значения {3, 5, 6,..., N 2} ). В матричных обозначениях уравнение наблюдения (1.19) примет канонический вид а строки матрицы наблюдения H m определяются условием xim = H m x, m = 1, M, т.е. m -я строка H содержит единицу в позиции im и нули в остальных.

Оптимальную оценку x в (1.20) при квадратичной функции потерь и в предположении некоррелированных x и осуществляет винеровский фильтр где RX и R - корреляционные матрицы сигнала и шума.

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

(для примера на рис. 1.1 vT = [ x3, x5, x6,..., xN 2 ] ; wT = [ x1, x2, x4, x7,..., xN ].

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

1) фильтрация наблюдаемой части последовательности;

2) «растягивание» полученных оценок на неизмеряемые области.

Очевидным следствием этого утверждения является декомпозиция ошибки оптимального восстановления:

фильтрации наблюдений, второе устанавливает ошибку экстраполяции оценок и допускает последующий анализ:

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

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

Хорошо известна вычислительная экономичность рекуррентных алгоритмов оценивания [69]. С связи с этим следует проанализировать задачу (1.19) на восстанавливаемая последовательность xi, i = 1, N порождается динамической моделью, возбуждаемой белым шумом:

где uk - вектор переменных состояния; F - матрица системы; G - входная H, H k - модуляционные матрицы. Зависимость матрицы H k от матрица;

аргумента k обусловлена тем, что измерения производятся лишь на некотором подмножестве значений дискретного времени k K n.

Полагая, что оптимальная последовательная оценка единственна и существует во всех точках интервала оценивания, можно воспользоваться калмановским результатом для моментов измерений [1, 4, 9, 69, 76, 106]:

оценивания;

измерений; K k - оптимальное усиление.

Отсутствие измерений физически соответствует бесконечной дисперсии шума измерений. Поэтому для k K n уравнения оценивания можно получить, используя (1.28) с R = :

Удобнее, однако, интерпретировать (1.29) как результат эквивалентной подстановки: R = 2, H k = 0. Этим наблюдения определяются во всех точках области анализа процесса xk, т.е. неполные наблюдения сводятся к полным.

Легко убедиться в применимости такого приема и для винеровского фильтра (1.20), (1.21).

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

учитывающие и будущие (относительно текущего времени) наблюдения [106].

Соответствующие алгоритмы являются двухэтапными процедурами и известны как алгоритмы сглаживания [4, 69]. Для рассматриваемой задачи наиболее полезным представляется алгоритм сглаживания с фиксированным интервалом [69], по существу являющийся представлением (1.21) в пространстве состояний и обеспечивающий винеровскую ошибку восстановления (1.24) Здесь uk, xk - сглаженные (винеровские) оценки; uk, Pk, PЭk определяются уравнениями (1.28)-(1.30), т.е. собственно сглаживанию (интерполяции) предшествует рекуррентная фильтрация последовательности xk в прямом времени. Сглаженная оценка и дисперсия её ошибки вычисляются в обратном времени [4, 14, 69]. Последняя при этом задается соотношением Двумерное восстановление. Рассмотрение начнем с самого общего случая, когда КФ изображения xmn, m, n =1, N неразделима по координатам а M наблюдений распределены по изображению случайным образом. Для упорядоченного по строкам изображения винеровская оценка [1, 69] запишется как представляет собой N 2 M матрицу линейного преобразования, что ведет к серьезным трудностям при вычислении оценок.

Оценку можно также получить с помощью альтернативного к (1.34) выражения, принимая во внимание лемму об обращении матриц [4], из которой следует Легко убедиться, что (1.35) еще более неудобно для вычислений, поскольку связано с обращением N 2 N 2 матрицы.

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

Далее будем предполагать разделимость RX и H. Переход от неразделимой корреляционной функции к факторизованной обсуждается в п. 1.2 и поэтому будем считать, что RX = RW RV. Условие разделимости оператора наблюдения означает, что поле точечных измерений образует на изображении некоторую решетку (необязательно регулярную) и может быть записано как получим Для (1.37) можно предложить удобную вычислительную процедуру, обобщающую алгоритм одномерного восстановления (1.23). Будем считать, что измерения на изображении X упорядочены так, что В противном случае требуемую структуру матриц (1.38) обеспечит перестановка строк и столбцов X (ортогональное преобразование). Тогда соответствующей координате; RVV *, RWW * - взаимная корреляция неизмеряемых элементов с элементами решетки соответственно по строке и столбцу изображения. Из (1.40) следует, что исходная задача восстановления сведена к последовательности процедур:

1) фильтрации поля измерений 2) собственно восстановлению изображения Преимущества алгоритма (1.41), (1.42) сравнительно с исходным (1.37) очевидны:

1) на каждом из этапов восстановления решается задача пониженной размерности;

2) поле измерений образует на решетке «полные наблюдения», что позволяет использовать эффективные методы фильтрации;

3) восстановление изображения производится разделимым оператором (сам по себе винеровский фильтр неразделим даже для полных наблюдений (1.41)).

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

Подобными (1.25) преобразованиями можно установить для фильтра (1.41), (1.42) ошибку восстановления. Как и в одномерном случае, ошибка восстановления допускает декомпозицию [21] где Ф - ошибка фильтрации поля измерений;

0, 0 - ошибка экстраполяции строк (столбцов) изображения, содержащих измерения, обусловленная неполнотой наблюдений;

V, W - ошибка экстраполяции содержащих измерения строк (столбцов) изображения, вызванная аддитивным шумом измерений:

0 - ошибка восстановления области изображения, содержащей элементы, не измеряемые ни по одной из координат, определяется неполнотой измерений:

VW - дополнительная ошибка восстановления неизмеряемой области изображения, обусловленная неидеальностью измерений:

Легко убедиться, сравнив полученную ошибку восстановления с (1.26), что результаты одномерного восстановления применимы к двумерному случаю лишь при определении 0 и 0. В остальном заимствование результатов исключается и связано оно с неразделимостью винеровского фильтра (1.41), а значит, и ошибки фильтрации E *.

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

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

Использование собственного преобразования RV позволяет декоррелировать изображение по строкам, т.е. перейти к набору N одномерных задач восстановления [21] Обратная матрица в (1.44) легко вычисляется, поскольку является блочной диагональной. Тогда для каждого столбца изображения получим Следует заметить, что отыскание преобразования Карунена-Лоэва является сложной задачей и в (1.44) можно использовать асимптотически оптимальные синусоидальные преобразования, имеющие быстрые алгоритмы [21, 27]. Тогда выбранном базисе.

Удобнее, однако, и при модели (1.43) сразу воспользоваться декомпозицией задачи восстановления. Тогда алгоритм восстановления ненаблюдаемых строк изображения по предварительно отфильтрованному полю измерений примет частный к (1.42) вид X =.... Z.

Обратимся еще раз к результату (1.42), представив его в удобном для анализа виде где ZW ZV означает экстраполированное по вертикали (горизонтали) поле измерений (отфильтрованных). С чисто вычислительной точки зрения разделимость восстанавливающего оператора в (1.45) означает, что при восстановлении i -й строки (столбца) изображения используются измеренные либо экстраполированные элементы только этой строки (столбца) изображения, т.е. элементы i -й строки ZW (i -го столбца ZV ). Это в свою очередь дает возможность независимого восстановления изображения по каждой строке (столбцу). Последнее обстоятельство позволяет строить эффективные по быстродействию процедуры восстановления изображений, основанные на последовательной технике оценивания [27, 43, 63, 85, 89].

Рассмотрим восстановление изображения с биэкспоненциальной КФ [21] по измерениям, произведенным на произвольной регулярной решетке. Будем считать, что шум измерений отсутствует. В противном случае предполагается, измерений. Соответственно (1.45) опишем последовательный алгоритм восстановления изображения [21]:

1. Вычисление ZV, т.е. построчное восстановление содержащих измерения строк изображения. Эта операция в свою очередь является двухэтапной процедурой (1.28)-(1.32):

а) фильтрация (формирование) очередной строки в ZV последовательный номер j, k = 2, N.

Начальное условие б) сглаживание отфильтрованной (сформированной) строки дисперсии ошибки фильтрации Начальные условия для P ( k ) определяются значениями zV ( n,1) :

0, если первый элемент строки измеряется ( j1 = 1), В силу регулярности измерений коэффициенты aV ( k ), PЭV ( k ), P ( k ) для всех восстанавливаемых строк изображения одинаковы и определяются лишь однажды.

2. Восстановление изображения по столбцам (т.е. растягивание ZV по вертикали):

а) фильтрация (формирование) очередного столбца X x ( k, n ) = исходного изображения не измеряются, б) сглаживание отфильтрованного столбца P ( k ) = изображения не измеряются ( ik не определено ), обрабатываемого столбца и определяются лишь однажды.

В заключение рассмотрим последовательные процедуры восстановления для рассматриваются совместно, поскольку при векторном описании изображений они идентичны с точностью до матричных множителей и имеют вид где для модели К1 F = L1 1L2, G = L1 1 ; для ПК1–ПК3 F = Q 1P, G = Q 1.

В (1.46) предполагается, что произведена статистическая декомпозиция модели за счет известных граничных условий, так что (1.46) описывает векторный марковский процесс и для обработки изображений можно непосредственно использовать результаты калмановской теории оценивания [14, 106].

Определим векторное наблюдение для каждого j :

столбце изображения. Расположение и число этих элементов определяют структуру матрицы H j и количество её нулевых элементов. При отсутствии измерений в столбце матрица H j полагается нулевой.

Оптимальные последовательная и сглаженная оценки при искажениях вида (1.47) определяются выражениями, аналогичными соответственно (1.28), (1.29) и (1.31). При этом начальные условия в (1.28), (1.29) определяются условием декомпозиции x = 0.

Отметим, что с увеличением размеров обрабатываемого изображения размерности [69]. Использование ортогональных преобразований [21], позволяющих по (1.46) перейти к совокупности несвязанных скалярных уравнений, в случае неполных измерений дает некоторые вычислительные преимущества (связанные с вычислением дисперсии ошибки предсказания в (1.28)), однако не приводит к декорреляции ошибки фильтрации и, следовательно, к понижению размерности задачи.

Анализ алгоритма восстановления поля. На примере модельной задачи [21] выясним круг вопросов, которые должны рассматриваться исследователем при восстановлении полей в системах обработки изображений. Рассмотрим поле u ( t, s ), описываемое уравнением [23, 66] где w ( t, s ) - белый по пространству и времени шум возмущений. Граничные условия без потери общности предположим нулевыми: u ( t,0 ) = u ( t,1) = 0.

С помощью устройства ввода данных в ЭВМ непрерывному полю u ( t, s ) ставится в соответствие дискретное u ( k, i ) на некотором множестве точек пространственной области: s = ih, t = k, i = 0, N + 1, k = 0,1, 2,...

При этом необходимо выполнение следующих требований:

– выбранная дискретная модель должна хорошо аппроксимировать (1.48);

восстановления;

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

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

Рассмотрим обоснование выбора рационального алгоритма восстановления.

Для этого проанализируем каждое из перечисленных требований, рассматривая два альтернативных дискретных представления (1.48) – модели ПК1 и ПК2.

аппроксимирующего (1.48) цифрового шаблона следует выбрать явную двухслойную схему (модель ПК1):

неидеальных датчиков, расположенных в некоторых пространственных точках li, i = 1, M и описываемых уравнениями вида или точке расположения i -го датчика ( li ). Матрица Bi и вектор Gi описывают наблюдения пространственного сечения поля на выходе датчика имеет вид где Ci – матрица наблюдения; i ( k ) - шум наблюдения (белый).

В монографии [11] предложена идея учета неидеальных измерений процесса, описываемых уравнениями вида (1.50), (1.51), путем расширения вектора состояния за счет динамических моделей измерителей. Используя эту идею, запишем уравнения расширенной системы для решаемой задачи:

где F, G, C - клеточные матрицы:

Алгоритм восстановления поля представляет собой последовательную проведен при следующих значениях параметров: N = 9, = 1, = 1, r = 0.1, M { ( k ) T ( k )} = Q ( k ) = I. Датчики описывались уравнениями первого порядка. Среднеквадратическая погрешность случай идеальных (неискажающих) датчиков. Получены зависимости числа датчиков и общего числа отсчетов сетки при обработке в реальном времени при различных шагах дискретизации.

В работах [123, 126] описаны разнообразные алгоритмы стохастической интерполяции случайных последовательностей и полей, а также их КФ. В работе [55] рассмотрена задача восстановления ненаблюдаемого двумерного СП в каждой точке прямоугольника по известным значениям (на всем прямоугольнике) наблюдаемого поля, которое представляет собой смесь ненаблюдаемого поля и помехи типа белого шума. В случае, когда ненаблюдаемое поле формируется с помощью дифференциального уравнения гиперболического типа (каузальная модель) для оптимальной (в смысле стохастическое уравнение с краевыми условиями.

В работе [54] для восстановления одного из пропущенных значений x ( t + ) временного ряда x ( t ), являющегося реализацией многомерного стационарного процесса с дискретным временем, предлагается линейная интерполяционная форма в виде где j и j - подлежащие определению числовые матрицы, T - длина пропуска (0 T ). Построена система нормальных уравнений относительно j и j согласно принципу наименьших квадратов. При условии, что реальный временной ряд моделируется процессом авторегрессии порядка p, для такой системы, записанной в терминах коэффициентов прогноза вперед и назад, развита итерационная процедура решения и доказана её сходимость для широкого класса случайных процессов.

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

В работе [91] рассмотрен синтез рекуррентного адаптивного алгоритма увеличении ОСШ.

предпочтение было отдано таким методам интерполяции СП на многомерных сетках, которые позволяют применять для интерполяции методы теории оптимальной линейной фильтрации, позволяющие в ряде случаев существенно снизить вычислительные затраты и повысить точность интерполяции на основе зашумленных наблюдений. В результате за рамками изложения остались методы линейной и квадратичной интерполяции [33, 71, 90], полиномы Лагранжа [67, 90], а также множество методов, связанных с интерполяцией с помощью сплайнов [2, 8, 28, 35, 82, 102], в частности кубических интерполирующих сплайнов и В-сплайнов [97, 115, 117, 118, 125], а также ряд статистических методов [26, 48], которые применяются в задачах восстановления зависимостей по отдельным значениям, а также задачах связанных с наилучшим приближением (аппроксимацией) функциональных зависимостей.

1.4. Оптимальное позиционирование измерителей В тех случаях, когда восстановление СП по неполным измерениям производится при ограничении на число измерителей, а сам характер их расположения заранее не фиксирован, естественным образом возникает задача оптимального размещения измерителей (изображены на рис. 1.2 в виде черных кружков). В монографии [21] оптимальным считается такое расположение датчиков, при котором минимизируется среднеквадратическая ошибка восстановления изображения.

В работах [95, 100, 105, 116, 124] рассматривается размещение измерителей на континуальной области и для решения используется разложение по собственным функциям соответствующей граничной задачи. Подход, развиваемый в работе [21] также основан на эквивалентном представлении моделей изображений (полей) посредством неособого преобразования состояний. При этом всегда предполагается, что проведена статистическая декомпозиция модели.

В работах [105, 116] описаны градиентные алгоритмы, позволяющие получить близкое к оптимальному решение данной задачи для полукаузальных и некаузальных моделей СП. Показано, что использование дискретного синусного преобразования (ДПС) позволяет существенно снизить вычислительные затраты при некотором увеличении дисперсии ошибки оценивания. Однако описываемые градиентные алгоритмы не всегда позволяют достичь глобально оптимального решения и зачастую выдают локально оптимальное решение за глобально оптимальное. Кроме этого, в этих алгоритмах используется критерий оптимальности, заключающийся в минимизации следа матрицы ковариаций ошибок оценивания J = Tr Pj min, в то время как зачастую возникает необходимость разработки алгоритмов, имеющих критерием оптимальности минимум максимальной дисперсии ошибки оценивания на всем СП J = Pj max min.

Задача поиска оптимального плана размещения датчиков относится к классу комбинаторных задач [3, 38, 64]. Подобные задачи решаются методами дискретной (целочисленной) оптимизации [39, 65]. В наиболее общей форме задача целочисленной оптимизации имеет следующий вид: найти вектор x с gi ( x1,..., xn ), i = 1,..., m, обусловленных спецификой задачи. С геометрической точки зрения ищется точка с целочисленными координатами в области, которая удовлетворяет ограничениям (в так называемой области допустимых значений) и минимизирует f. В задаче, рассматриваемой в данной работе, требуется определить вектор x, компоненты которого принимают только двоичные значения 0 или 1; в этом случае говорят о бивалентном программировании [65]. При этом целевой функцией f является максимальная дисперсия ошибки оценивания, а вектор x представляет собой план оптимального размещения датчиков (рис. 3.8, б). Некоторые частные случаи решения данной задачи рассмотрены более подробно в п. 3.3.

Среди зарубежных работ, касающихся оптимизации размещения пилотсигналов в системах мобильной связи можно выделить следующие: [94, 119, 128]. Следует отметить работу [107], в которой получены границы Рао-Крамера для минимальной дисперсии ошибки оценивания для различных планов расположения пилот-сигналов, в том числе и оптимальных в смысле минимума максимальной дисперсии ошибки интерполяции СП.

В работе [21] сделан ряд качественных выводов относительно оптимизации размещения датчиков:

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

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

в) разнесение датчиков также ведет к ухудшению качества восстановления.

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

Однако, следует учесть, что эти выводы сделаны с точки зрения минимизации следа матрицы ковариаций ошибок оценивания J = Tr Pj min, в то время как в настоящей работе критерием оптимальности служит минимум максимальной дисперсии ошибки оценивания СП J = Pj max min.

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

1.5. Выводы 1. Анализ различных авторегрессионных моделей случайных полей, широко применяемых в приложениях, показал, что для представления многомерных СП наиболее предпочтительным является класс моделей авторегрессии с разделимой КФ, поскольку это один из немногих классов моделей, для которого можно разработать оптимальные алгоритмы дискретной фильтрации и реализовать их на ЭВМ.

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

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

4. Таким образом, представляются важными следующие задачи:

интерполяции одно- и двумерных СП.

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

• Синтез алгоритмов поиска оптимального плана размещения датчиков на преимуществ оптимального плана размещения датчиков по сравнению со случаем регулярного размещения.

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

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

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

СЛУЧАЙНЫХ ПОЛЕЙ НА МНОГОМЕРНЫХ

СЕТКАХ

2.1. Постановка задачи Во многих современных информационных системах используется представление массивов поступающих данных в виде многомерных изображений (случайных полей) [52, 89]. Одной из важных проблем обработки многомерных (СП) X = { x ( u ), u R N }, по наблюдениям суммы информационного СП и белого шума в n точках. При этом возникают задачи построения наилучших оценок x ( u ), u R N, выбора числа и расположения точек в пространстве, а также анализа погрешностей восстановления СП по дискретным данным. Значимость рассматриваемого класса задач обусловлена широким спектром практических приложений для решения проблем экологического мониторинга, восстановления медицинских изображений, построения динамических карт амплитуднофазовых искажений в системах мобильной связи.

Вначале предположим, что область G совпадает со всем пространством R N. Тогда для однородного СП все наблюдения оказываются равноценными и должны производится в узлах бесконечной N -мерной сетки отсчетов функция (КФ) может быть задана на сетке J в виде В случае гауссовской модели наблюдений наилучшее в смысле минимума многомерного аналога уравнения Винера-Хопфа:

Решение может быть найдено с помощью N -мерного z -преобразования:

H (, u ) = f x ( ) x + f x (, u ), а минимально достижимая дисперсия ошибки такого восстановления Анализ показал, что точные результаты удается получить только для разделимых СП с экспоненциальными КФ для точек u, совпадающих с узлами многомерной сетки.

Наибольший практический интерес представляет значение максимальной дисперсии ошибки восстановления, соответствующей центральной точке u, равноудаленной от имеющихся отсчетов наблюдений z j на многомерной сетке j J. В общем случае для получения такой интерполяционной оценки требуются существенные вычислительные затраты, связанные с учетом всех имеющихся наблюдений z j. Однако, в инженерных приложениях часто возникает необходимость в алгоритмах интерполяции, требующих сравнительно малые вычислительные затраты. В связи с этим возникает задача оценки потенциальной точности алгоритмов интерполяции по малому количеству наблюдений при различных параметрах сигнала x ( uk ) и шума ( uk ). В данной главе представлен сравнительный анализ эффективности различных алгоритмов получения оптимальных линейных интерполяционных оценок для случая однородных гауссовских СП.

2.2. Анализ погрешностей интерполяции многомерных случайных полей по незашумленным наблюдениям X = { x j, j J } определенного на N -мерной прямоугольной сетке отсчетов соответствующих осей координат [129, 130, 131].

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

Наблюдения на N -мерной прямоугольной сетке J представляют собой аддитивную смесь полезного сигнала и белого гауссовского шума:

белый гауссовский шум с нулевым средним и дисперсией 2.

Интерполяционную оценку x0 = f { x j, j, j J } в N -мерном непрерывном пространстве соответствующем N -мерной прямоугольной сетке J, можно сформировать в виде линейной комбинации зашумленных наблюдений z j с соответствующими весовыми коэффициентами j :

В дальнейшем под интерполяционной оценкой подразумевается оценка x0 в центре между равноотстоящими наблюдениями z j в N -мерном пространстве R N.

Оптимальность алгоритма рассматривается в смысле минимума дисперсии ошибки оценивания по параметрам линейной комбинации (2.5).

предположим, что восстанавливается случайный процесс xu по наблюдениям k = 0, ± 1, ± 2,... В этом случае для СП с экспоненциальной КФ установившаяся формуле [89] интерполяции дисперсия ошибки Pu уменьшается и находится с помощью известных формул [16, 69]:

где PЭ = 2 P + x (1 2 ). Наконец, установившаяся дисперсия ошибки в определить максимальную дисперсию ошибки восстановления одномерного СП при любых параметрах информационного СП и помехи.

формируется на основе ближайших симметричных относительно центра K = 2 N отсчетов: x0 = i xi, поэтому можно считать i =. Минимальная дисперсия ошибки интерполяции вычисляется из условия На рис. 2.3 снизу показано исходное изображение с отчетливо видными полосами, отражающими пропущенные отсчеты. На том же рисунке сверху показано изображение, восстановленное по неполным наблюдениям по формуле x0 = i xi при нулевых ошибках в узлах СП (рис. 2.1, 2.2), из чего видно сглаживание пропущенных отсчетов посредством интерполяции.

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

Относительно простые выводы для полей произвольной размерности могут быть сделаны при условии отсутствия погрешностей наблюдения 2 = 0 [131].

Вначале рассмотрим интерполяцию по наблюдению в одной точке x0 = x1, Дисперсия ошибки интерполяции между двумя точками (рис. 2.1) находится из формулы Таким образом, в случае двух узлов с наблюдениями относительная корреляции за счет отхода от точки с высоким качеством оценивания.

Действительно, уход на 1 = 0.1 дает 2 = 0.1 x, т.е. 2 = 0.31 x. Если же Рассмотрим точность интерполяции при нулевых ошибках наблюдения в случае четырех узлов (рис. 2.2). Линейная интерполяционная оценка имеет вид x0 = i xi и соответствующая дисперсия ошибки интерполяции минимальна, Для случая, когда интерполяционная оценка вычисляется в середине, системы уравнений В произвольной точке внутри квадрата, составленного из наблюдений x1, x2, x3, x4, коэффициенты корреляции будут различны и система уравнений примет вид c =, D = 2 и = (1 + ). Найдем минимальную дисперсию, имея 2min На основании проведенного анализа можно сделать вывод, что дисперсия интерполяции в произвольной точке между двумя отсчетами (рис. 2.1) к местоположения интерполируемого значения между двумя известными отсчетами, которым соответствуют в данном случае i = 0 и i = 200. Анализ графика показывает, что с увеличением коэффициента корреляции данное отношение стремиться к единице, т.е. различие между известным отсчетом и значением, интерполируемым на его основе, уменьшается.

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

Данную кривую можно получить по формуле (2.8) при i = N 2.

На рис. 2.6 (для сравнения с рис. 2.4) показаны зависимости отношения интерполяции между двумя известными отсчетами (в центре), которым соответствуют в данном случае i = 0 и i = 50, при различных отношениях сигнал/шум q и различных коэффициентах корреляции между известными отсчетами Калмана (при наличии аддитивного белого гауссовского шума наблюдений и n = 100 ). Из рис. 2.4 и 2.6 можно сделать вывод о том, что при достаточно сильных шумах q < 10 дБ ошибки в центре между отсчетами и в точках отсчетов наблюдений мало отличаются друг от друга. Кроме этого, при увеличении коэффициента корреляции между отсчетами наблюдений это различие становится еще менее заметным (рис. 2.6 а, б).

2.3. Алгоритмы интерполяции случайных полей по зашумленным наблюдениям Для получения оптимальных (в смысле минимума дисперсии ошибки) оценок x j СП x j по наблюдениям z j, j J, используются винеровские или калмановские процедуры линейной фильтрации [1, 16, 69]. Для ряда моделей таких СП получены оценки эффективности фильтрации [15]. Вместе с тем, в известных работах практически отсутствуют результаты анализа алгоритмов интерполяции СП, т.е. получение оценок наблюдениям z j в отдельных точках СП. В работе [18] получены относительно простые формулы для максимальной дисперсии ошибки интерполяции СП в R N по наблюдениям z j в точках j, находящихся в ближайших узлах N мерной прямоугольной сетки (рис. 2.7).

соответствовать оценке x0 = xu в точке u, находящейся в центре N -мерного наблюдений интерполяционная оценка оказывается наиболее простой:

дисперсия ошибки оптимальной интерполяции находится по формуле где X = M { x0 }. Таким образом, при заданных вероятностных характеристиках СП zu и xu может быть рассчитана максимальная дисперсия оптимальной линейной интерполяции.

В качестве примера рассмотрим разделимое СП xu с корреляционной функцией (КФ) где R ( k ) - нормированная КФ по k -й координате. При этом будем полагать, информационного СП и независимых гауссовских случайных величин с нулевыми средними и дисперсиями 2 = M { 2 }.

получаются в случае интерполяции в N -мерном пространстве на основе n = 2 N формируется в виде линейной комбинации наблюдений zi с одинаковыми весовыми коэффициентами : x0 = zi.

Дисперсия ошибки интерполяции в центре имеет вид При этом имеют место следующие соотношения:

Вычислив производную d 2 d = 0, получим оптимальное значение весового коэффициента С учетом выражений (2.13)-(2.15) формула (2.12) преобразуется к виду В частности, при оценивании по двум наблюдениям ( N = 1 ) при оценивании по четырем наблюдениям («в центре квадрата») при оценивании по восьми наблюдениям ( N = 3 ) («в центре куба», рис. 2.7) корреляции между элементами СП x j вдоль соответствующих координатных осей.

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

интерполяции для крайнего (в узле) и центрального (в центре между двумя соседними узлами) отсчетов последовательности при различных ОСШ где 2 - дисперсия ошибки оценивания в узле; 20 - дисперсия ошибки позволяют сделать вывод о том, что с увеличением ОСШ растет разница в дисперсии ошибки интерполяции на краях (узлах или, что то же самое, местах расположения пилот-сигналов) и в центре. Сравнив рис. 2.9 с рис. 2.5 можно убедиться, что наибольшая разность дисперсии ошибки интерполяции достигается при отсутствии шума.

коэффициента корреляции при заданном граничном условии 2 X < 0. для различных размерностей случайного поля, выраженных количеством точек наблюдений (узлов) ( M =2, 4, 8 соответствуют одно-, двух- и трехмерному полю), равноотстоящих от точки, в которой делается прогноз ( 2 - дисперсия ошибки оценивания в точке наблюдения). Это позволяет сделать вывод о том, коррелированных сигналах граничный коэффициент корреляции возрастает с увеличением размерности случайного поля.

q, дБ Данные кривые ограничивают области значений (, q ) (над кривыми) при которых ещё имеет смысл производить интерполяцию в центре на основе имеющихся M наблюдений.

На рис. 2.11 показаны зависимости интервала корреляции m = 1 (1 ) между соседними отсчетами наблюдений от отношения сигнал/шум q при котором выполняется условие 20 X < 0.01 для последовательности отсчетов (кривая 1) и для случайного поля отсчетов (кривая 2). В данном случае дисперсия ошибки интерполяции 20 в центре между наблюдениями zi вычислена с помощью оптимального линейного фильтра, т.е. является предельно достижимой величиной.

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

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

Нетрудно показать, что дисперсия ошибки оптимальной интерполяции для одно- и двумерного СП по нескольким соседним отсчетам оценок z j находится по формулам [19] где коэффициенты, 1, 2, 3 вычисляются из условия минимума дисперсии ошибки интерполяции (см. Приложение 2).

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

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

В работе [19] получены зависимости для максимальной дисперсии ошибки интерполяции СП по дискретным наблюдениям z j и по оптимальным оценкам x j находящимся в ближайших узлах одно- и двумерной прямоугольной сетки.

соответствует оценке x0 = xu в точке u, находящейся в центре N -мерного параллелепипеда (рис. 2.7).

Интерполяционную оценку x0 = f { x j, j J } в N -мерном непрерывном пространстве соответствующем N -мерной прямоугольной сетке J, можно сформировать в соответствующими весовыми коэффициентами j :

соответствующие интерполяционные оценки имеют вид:

где 0 - оптимальный весовой коэффициент, вычисляемый из условия минимума дисперсии ошибки интерполяции. Дисперсия ошибки интерполяции оценивания j, т.е. M { zi i } = 0 [45, 69, 83].

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

имеем для среднего квадрата оптимальной оценки M { xi2 } = M { xi2 } M { i2 }.

Аналогично, в общем случае ковариация оценок равна и с учетом того, что ковариация ошибок оценивания и M { z j i } = 0, имеем для ковариации оптимальных оценок Ковариации ошибок оценивания M { i j } могут быть найдены с помощью теории фильтра Винера [1, 69], для чего необходимо сделать ряд интегральных преобразований (приложение 1).

Метод интерполяции на основе оптимальных оценок, описанный в настоящем разделе, можно интерпретировать как алгоритм интерполяции, состоящий из двух этапов:

оптимальных оценок;

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

Нетрудно показать, что дисперсия ошибки оптимальной интерполяции для одно- и двумерного СП по нескольким соседним отсчетам оценок x j находится по формулам [19, 75] где коэффициенты i вычисляются из условия минимума дисперсии ошибки интерполяции d 20 d = 0 (см. Приложение 2).

На рис. 2.13–2.15 (а – последовательность, б – двумерное поле) показаны сравнительные графические зависимости относительной дисперсии ошибки интерполяции 20 X по зашумленным наблюдениям z j (пунктирная линия) и случайного поля при отношениях сигнал-шум 0, 10 и 20 дБ.

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

Кроме этого, для последовательности отсчетов СП при интерполяции по оптимальным оценкам дисперсия ошибки практически не зависит от количества отсчетов, на основе которых выполняется интерполяция (рис. 2.13а), в то время как в аналогичном случае двумерных СП зависимость дисперсия ошибки от количества отсчетов более заметна (рис. 2.13-2.15, б). На рис. 2.13 (а) отдельно показана кривая, соответствующая интерполяции с помощью фильтра Калмана при количестве отсчетов используемых для интерполяции равном 100. В остальных случаях (рис. 2.14-2.15, а) аналогичная кривая практически совпадает с кривыми для интерполяции по оптимальным оценкам (различие составляет около 0.1%).

Для анализа вычислительных затрат рассмотрим СП размером n n элементов, описываемое разделимой экспоненциальной КФ (1.11). При оптимальной винеровской фильтрации на 1 отсчет поля будет приходиться O ( n 2 ) вычислительных операций (умножений) [21], а при рекуррентной калмановской фильтрации метод позволяет существенно снизить удельные вычислительные затраты (количество операций на 1 отсчет) при непосредственной интерполяции, которые не зависят от размеров СП, что показано в табл. 2.1, 2.2. Однако, при этом добавляются вычислительные затраты, необходимые для получения оптимальных оценок и составляющие O ( 4n ) операций на один отсчет СП.

В табл. 2.1 показано количество умножений при обработке случайной последовательности из n отсчетов.

В табл. 2.2 показано количество умножений при обработке двумерного СП размера n n отсчетов.

Таким образом, исходя из графических зависимостей (рис. 2.13-2.15), можно сделать вывод, что при оптимальной линейной интерполяции по оценкам x j достигается существенный выигрыш по дисперсии ошибки по сравнению с оптимальной интерполяцией по зашумленным наблюдениям z j, который возрастает с увеличением коэффициента корреляции СП. Кроме этого, при увеличении количества наблюдений (оценок) в окрестности интерполируемого отсчета (рис. 2.12 б, г) данный выигрыш увеличивается. Основное преимущество предлагаемого алгоритма заключается в повышении точности интерполяции по сравнению с точностью, получаемой при калмановской фильтрации СП зашумленных наблюдений при практически одинаковых вычислительных затратах (табл. 2.1, 2.2).

2.5. Выводы 1. Впервые проведен сравнительный анализ алгоритмов интерполяции СП, на основе зашумленных наблюдений z j и на основе оптимальных оценок x j.

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

2. Впервые разработан алгоритм интерполяции СП на основе оптимальных оценок, полученных с помощью фильтра Калмана. Данный алгоритм требует примерно столько же умножений, как и оптимальный алгоритм интерполяции СП на основе зашумленных наблюдений (табл. 2.1, 2.2), реализованный на основе фильтра Калмана. Показано, что при интерполяции на основе оптимальных оценок удается достичь существенного снижения дисперсии ошибки интерполяции (особенно при малых ОСШ и высоких корреляциях) порядка 10-30 % - для одномерного СП (последовательности) и в 2-3 раза – для двумерного СП по сравнению с алгоритмом интерполяции с помощью фильтра Калмана по зашумленным наблюдениям для СП размеров 100х100 элементов.

3. Показано, что при интерполяции СП на основе оптимальных оценок удается достичь значительного снижения погрешностей интерполяции по сравнению с глобально оптимальными алгоритмами на основе зашумленных наблюдений при незначительном увеличении вычислительных затрат (табл. 2.1, 2.2). В то же самое время в ряде случаев (при больших ОСШ вычислительные ресурсы) было бы целесообразнее использовать интерполяционные оценки на основе зашумленных наблюдений.

4. Впервые получены выражения для дисперсии ошибки интерполяции в N мерном пространстве на основе n = 2 N элементов, равноотстоящих от точки x0 .

Проанализированы зависимости ОСШ от коэффициента корреляции при заданном граничном условии 2 X < 0.1 для СП различных размерностей ( 2 - дисперсия ошибки оценивания в точке наблюдения), что позволяет сделать вывод о том, что оценку целесообразно производить при достаточно сильно коррелированных сигналах > 0.9 и слабых шумах q > 10 дБ.

соседними отсчетами наблюдений от ОСШ q при которых выполняется 20 X < 0.01 для одно- и двумерного СП ( 20 - дисперсия ошибки условие интерполяции в центре между узлами с наблюдениями). Показано, что с увеличением коэффициента корреляции, предельно допустимое ОСШ снижается, что позволяет по заданной допустимой дисперсии ошибки определить необходимые корреляционные расстояния между наблюдениями, требуемыми для восстановления непрерывного информационного СП с заданным ОСШ.

ГЛАВА 3. АЛГОРИТМЫ РАЗМЕЩЕНИЯ ПИЛОТСИГНАЛОВ НА МНОГОМЕРНЫХ СЕТКАХ

3.1. Постановка задачи Многие современные системы извлечения информации представляют собой пространственные апертуры датчиков и имеют ограниченные размеры. При этом датчики можно интерпретировать как источники опорной информации, на основе которой производится восстановление значений СП в узлах, где отсутствуют датчики [21]. Аналогичная задача возникает при синтезе устройств оценивания текущего состояния канала с быстрыми замираниями в интерпретировать в виде двумерной сетки «время-частота», на которой некоторым образом распределены т.н. пилот-сигналы, играющие роль датчиков и несущие в себе опорную информацию об амплитудно-фазовых искажениях полезного сигнала в канале [34, 42, 119]. Поскольку восстановление СП по неполным измерениям производится при ограничении на число измерителей (датчиков), а сам характер их расположения заранее не фиксирован, естественным образом возникает задача оптимального размещения измерителей. В настоящей работе будем считать оптимальным такое расположение датчиков, при котором минимизируется среднеквадратическая ошибка восстановления СП.

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

Данная задача предполагает применение методов математического программирования и относится к классу экстремальных задач, в которых задается некоторое множество C допустимых решений, представляющих собой возможные планы размещения датчиков, а на этом множестве задается целевая функция f ( x ) = Pmax, представляющая собой максимальное значение дисперсии ошибки интерполяции, и требуется найти такой элемент x0 = Copt, Copt C, на котором значение допустимое решение связан с рядом ограничений на конфигурацию датчиков (симметричность расположения относительно центра, отсутствие наложения оптимальным (экстремальным) решением и представляет собой план размещения датчиков, на котором достигается наименьшее допустимое значение максимальной дисперсии ошибки интерполяции [38, 39, 62, 64, 65].

В известных работах [95, 100, 105, 116, 124] подобные задачи решались преимущественно градиентными методами, однако во многих случаях (особенно на многомерных сетках) их эффективность зависит от удачного выбора начальных точек. Кроме этого возникает опасность попадания в ложный оптимум, и поэтому применение градиентных алгоритмов для решения вышеупомянутой задачи зачастую представляется затруднительным.

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

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

В связи с этим возникает задача снижения максимальной дисперсии ошибки или сокращения количества пилот-сигналов при заданном допустимом значении максимальной дисперсии. Очевидно, что одним из путей снижения дисперсии ошибки является разработка алгоритма поиска некоторой, в общем случае неравномерной, оптимальной расстановки пилот-сигналов, позволяющей минимизировать дисперсию ошибки [17].

Одним из возможных способов решения данной задачи является полный перебор всех возможных вариантов (планов) расстановки пилот-сигналов [72, 73]. Однако при больших размерах сетки подобный способ может потребовать значительных вычислительных затрат. В связи с этим возникает необходимость разработки алгоритма улучшенного перебора вариантов расстановки.

Алгоритм полного перебора. Исходными данными являются длина последовательности n элементов, количество пилот-сигналов m p и параметры модели случайной последовательности, представляющей собой в общем случае уравнение авторегрессии-скользящего среднего [7] с добавлением аддитивного шума : коэффициент корреляции и отношение сигнал/шум q = X 2.

Блок-схема алгоритма изображена на рис. 3.3.

Вначале задаются начальные позиции пилот-сигналов p ( k ), где k порядковый номер, присваиваемый каждому конкретному пилот-сигналу, причем k = 1... m p, p = 1... n. При этом всегда необходимо выполнение условия: p ( k ) > p ( k 1) + 1, т.е. k -й пилот-сигнал может перемещаться только соответственно. Кроме этого, между двумя соседними пилот-сигналами должен быть хотя бы один информационный символ. Если количество пилот-сигналов m p - нечётное число, очевидно, что для соблюдения условия симметричности (график дисперсии ошибки оптимальной линейной фильтрации всегда симметричен относительно центра) длина последовательности тоже должна быть нечетным числом и один пилот-сигнал всегда будет находиться в центре последовательности (восьмая позиция на рис. 3.1).

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

Причем расстановка осуществляется для пилот-сигналов, находящихся на левой половине последовательности, а правая половина затем получается в виде зеркального отображения левой части с пилот-сигналами (рис. 3.1). Ниже будем считать величину m ' - количеством пилот-сигналов, размещаемых на одной половине последовательности.

Вначале со своей стартовой позиции pb ( m ') перемещается m ' -й пилотсигнал до тех пор, пока не достигнет своей конечной позиции p f ( m ') и затем возвращается на другую позицию, отстоящую на шаг вперед pb ( m ') + 1. После этого перемещается предыдущий пилот-сигнал с позиции pb ( m ' 1) на позицию pb ( m ' 1) + 1, а последующий m ' -й пилот-сигнал делает очередной цикл со своей текущей стартовой позиции pb ( m ') + 1 и затем возвращается на новую текущую стартовую позицию, отстоящую на шаг вперед pb ( m ') + 2. После этого предыдущий пилот-сигнал делает еще один шаг с позиции pb ( m ' 1) + на позицию pb ( m ' 1) + 2 и так до тех пор, пока все пилот-сигналы не займут свои конечные позиции p f ( k ), k = 1... m '.

Общее количество планов расстановки можно вычислить по следующей формуле где s - количество подвижных пилот-сигналов, находящихся на левой воспользоваться уравнениями Калмана [4, 69]. Тогда получение дисперсии ошибок оценивания СП и включает в себя следующие шаги:

PЭk = 2 Pk 1 + k k - дисперсия ошибки экстраполяции ( PЭ1 = VX ), где - коэффициент корреляции, vk = X 1 2, V1 = qk = X 2, Ck - k -й элемент вектора C плана расстановки; C = [1 0 0 1 0 0 0 1... 0 0 1], причем единицы расположены на позициях, соответствующих пилот-сигналам.

Для сглаживания оценок осуществляется обратный проход:

PN = PN, Pk = Pk + Ak Pk+1 PЭ( k +1) Ak, При этом в точках, где отсутствуют наблюдения, при фильтрации полагаем ОСШ qk =0. Далее находится максимальное значение дисперсии ошибки для данной j -й последовательности (плана расстановки) Pj*max и сравнивается с предыдущим, если Pj*max < P(*j 1) max, то за оптимальный план расстановки принимается Copt = C ( j ) и так до тех пор, пока не будут «проверены» все возможные планы расстановки пилот-сигналов. В конечном итоге получается максимальной дисперсией ошибки интерполяции.

На рис. 3.2 показаны зависимости дисперсии оценивания при разных схемах расстановки одного и того же количества пилот-сигналов: а – равномерная расстановка, б – оптимальная расстановка.

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

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

ИСХОДНЫЕ ДАННЫЕ

Если Pmax(i)< Pmax(i–1), то Copt=C(i) Вычисление дисперсии ошибки

КОНЕЦ ЦИКЛА

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

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

где pr ( k ) - позиция k -го пилот-сигнала при равномерной расстановке.

Данные соотношения (3.1), (3.2) ни разу не нарушались для случаев n = 31 ( m p = 7, 11) и n = 49 ( m p = 5, 9, 13) при изменении параметров случайной сильном шуме q < 10 дБ в случае оптимальной расстановки все пилотсигналы «прижимаются» к краям одномерной сетки. В то время как при слабых корреляциях < 0.9 и(или) слабом шуме q > 15 дБ оптимальная расстановка пилот-сигналов приближается к равномерной (регулярной).

Параметры плана расстановки Полный перебор Улучшенный перебор На рис. 3.5 (а, б) показаны зависимости выигрыша оптимального плана размещения по сравнению с регулярным по максимальной дисперсии ошибки интерполяции для последовательности отсчетов. На основании этих графиков можно сделать вывод о том, что при уменьшении количества пилот-сигналов, увеличиваются. Кроме этого, выигрыш увеличивается с увеличением ОСШ q.

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

ИСХОДНЫЕ ДАННЫЕ

Если Pmax(i)< Pmax(i–1), то Copt=C(i) Вычисление дисперсии ошибки причем с увеличением коэффициента корреляции от = 0.999 и выше (при q > 20 дБ) дисперсия ошибки интерполяции изменяется несущественно и практически не зависит от количества пилот-сигналов m p. В то же самое время при сильных шумах ( q < 0 дБ) приемлемого качества интерполяции можно достичь лишь при очень сильной корреляции > 0.999 и большом количестве пилот-сигналов m p n 4. Кроме этого, на графиках можно наблюдать сходимость максимальной дисперсии ошибки интерполяции к некоторому асимптотическому значению при m > 104.

3.3. Оптимизация размещения пилот-сигналов на двумерной сетке До настоящего времени задача поиска оптимального плана размещения пилот-сигналов на двумерной сетке решалась в ряде зарубежных работ [95, 100, 105, 116, 124], в которых рассмотрены градиентные алгоритмы, позволяющие полукаузальных и некаузальных моделей СП. Однако описываемые в этих работах градиентные алгоритмы не всегда позволяют достичь глобально оптимального решения и зачастую дают локально оптимальное решение. Кроме этого, в известных алгоритмах используется критерий оптимальности, требующий минимизации следа матрицы ковариаций ошибок оценивания J = Tr Pj min, в то время как зачастую возникает необходимость получения плана размещения пилот-сигналов с минимумом максимальной дисперсии ошибки оценивания на всем СП J = Pj max min.

Рассмотрим данные алгоритмы подробнее.

Полукаузальные модели. Все рассматриваемые в литературе [16, 134] полукаузальные модели допускают единое представление где матрицы F и G определены соотношениями (1.17), (1.18), (1.46).

Не нарушая общности задачи, запишем уравнение наблюдения в виде Дисперсия калмановской ошибки восстановления для системы (3.3), (3.4) на j -м шаге, представляющем собой очередной анализируемый план размещения датчиков, имеет вид Оптимальным для момента j считается такое расположение датчиков, при котором Минимум в (3.6) ищется по текущим координатам расположения датчиков.

Пусть в момент j измерения производятся l датчиками, расположенными в последовательных (произвольных) точках i j = [i1, i2,..., il ] (рис. 3.8, а). При этом ставится задача перейти к оптимальной по критерию (3.6) конфигурации В работе [21] отмечается, что дискретное синусное преобразование (ДПС) позволяет перейти от (3.3) к несвязанным скалярным уравнениям, т.е. является полукаузальной модели. Переопределим задачу, осуществив переход поэтому можно перейти к эквивалентному критерию Из (3.5) следует Теперь, определив градиент функционала (3.7) ik H j = ( ik ) H j - матрица, лишь одна из строк которой (с номером ik ) отлична от нуля и образована элементами можно для отыскания i* воспользоваться каким-либо из градиентных методов.

В работах [95, 116] для этой цели используется модифицированный метод градиентов:

где {•} означает операцию округления к ближайшему целому;

j ( n ) = diag (1 ( n ),..., l ( n ) ) - матрица множителей, которая используется для ускорения сходимости.

На первых шагах алгоритма = 0 (метод градиентов) вблизи оптимума для ускорения сходимости можно положить = 1 (метод сопряженных градиентов).

Следует заметить, что процедура отыскания i*j многошаговая. В случае, когда интерес представляет лишь асимптотическое размещение измерителей ( j, R = const, l = const ), итерации i j можно совместить с решением (3.8).

В работе [95] доказывается сходимость такой процедуры.

Некаузальные модели. Из (1.34) можно получить винеровскую ошибку восстановления упорядоченного по строкам изображения [1, 69] где определяется моделью изображения, а измерению с координатами (k,l ) соответствует строка матрицы H, содержащая N 2 1 нулей и единицу в Собственным преобразованием рассматриваемых некаузальных моделей является ДПС. При этом матрица преобразования запишется как =, где - матрица ДПС, которая соответствует N -точечному ДПС.

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

Задача оптимального размещения датчиков теперь заключается в том, чтобы минимизировать J на множестве пар Определяя его столбцами = [f1,..., f N ], получим В остальном задача полностью аналогична уже рассмотренной, и алгоритм размещения разнится с предшествующим лишь в очевидных деталях, связанных с появлением вектора направления.

Описанный алгоритм использовался в работе [21] для расстановки датчиков в марковском поле (модель НК1 в табл. 1.1). Исследования показали, что обсуждаемый алгоритм оптимального размещения дает устойчивые результаты, фиксируя измерители в непосредственной близости от точек оптимума начальном расположении измерителей). При этом различия в ошибке восстановления не превышают 1%.

Следует подчеркнуть, что рассмотренные выше алгоритмы оптимального размещения точечных измерителей применимы ко всем описанным прежде полукаузальным и некаузальным моделям (параболические и эллиптические уравнения) и легко обобщаются на модели высших порядков (бигармоническое уравнение и т.д.), т.е. они могут быть широко использованы при обработке полей, описываемых уравнениями математической физики [23, 66].

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

Если некоторые области поля следует восстановить с повышенным качеством, можно от (3.6) перейти к модифицированному функционалу где C – диагональная матрица весовых коэффициентов, E - единичная матрица. В остальном схема решения остается прежней.

Очевидно, проверить качество вышеупомянутых алгоритмов можно только с помощью некоторого глобально оптимального алгоритма, которым является алгоритм полного перебора всех возможных планов размещения датчиков (пилот-сигналов) [72, 73].

Алгоритм полного перебора. Как и в случае алгоритма полного перебора для последовательности отсчетов на начальном этапе формируется общая стратегия перебора вариантов расстановки (рис. 3.9). Исходными данными являются размеры поля n n элементов, количество пилот-сигналов m p и параметры модели случайной последовательности где коэффициент межстрочной корреляции, r - коэффициент внутристрочной корреляции. При этом СП предполагается однородным, т.е. коэффициенты корреляции в обоих направлениях одинаковы = r. Блок-схема алгоритма полного перебора на двумерной сетке отсчетов изображена на рис. 3.9.

В двумерном случае имеется ряд особенностей и ограничений, отсутствующих в одномерном случае и вызывающих усложнение алгоритма. Одним из ограничений является кратность количества пилот-сигналов четырем, т.е. сетка разбивается на четыре квадранта, причем в каждый квадрант должно попадать одинаковое количество пилот-сигналов. Кроме этого, следует учитывать, что с целью упрощения построения алгоритма полного перебора вначале общего количества пилот-сигналов m1 4 позиционируется в одном из квадрантов и затем соответствующим образом зеркально отображается на остальные три части сетки. Внутри квадранта следует отдельно формировать множества пилот-сигналов, позиционируемых на диагонали - назовем их диагональными пилот-сигналами, и в остальной части квадранта ps ( k ) боковые пилот-сигналы. Если количество пилот-сигналов – нечетное, то на диагонали всегда будет размещаться нечетное число пилот-сигналов. Вначале на диагонали размещается наименьшее возможное количество пилот-сигналов.

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

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

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

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

Общее количество планов расстановки можно вычислить по следующей формуле где s - количество подвижных пилот-сигналов, находящихся относительно диагонали на одной стороне квадранта, ks = k s 1 =... = k1 = этом внутри квадранта находится m1 4 = 2 s + d пилот-сигналов, где d количество диагональных пилот-сигналов.

Общее количество наборов пилот-сигналов, размещаемых на диагонали где ceil - функция округления до наибольшего целого, floor - функция округления до наименьшего целого, rem ( a, b ) - остаток от деления числа a на число b.

После этого выполняется процедура сокращения количества допустимых планов размещения пилот-сигналов путем введения дополнительных ограничений, заключающихся в том, что два пилот-сигнала могут находиться рядом только в диагональном направлении, но никак не в горизонтальном или вертикальном направлениях, т.е. одновременно должны выполняться неравенства X p(i ) X p( j ) и Yp(i ) Yp( j ). На следующем этапе осуществляется расчет дисперсий ошибки фильтрации для допустимых планов размещения C пилот-сигналов. Обозначим k -ю строку матрицы C как S k, а также введем матрицу Ck = S k E, где E - единичная матрица.