Preview

Вестник Концерна ВКО «Алмаз – Антей»

Расширенный поиск

Оптимальная регулярная локальная сплайновая интерполяция сигналов

Полный текст:

Аннотация

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

Для цитирования:


Исаков В.Н. Оптимальная регулярная локальная сплайновая интерполяция сигналов. Вестник Концерна ВКО «Алмаз – Антей». 2016;(4):24-31.

For citation:


Isakov V.N. Optimum regular local spline interpolation of signals. Journal of «Almaz – Antey» Air and Defence Corporation. 2016;(4):24-31. (In Russ.)

Введение

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

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

Классические математические подходы к задачам интерполяции подробно изложены в работе [1].

Одно из перспективных современных направлений в теории интерполирования - сплайновая интерполяция. Математические свойства сплайнов подробно исследованы в работах [2, 3]. Практические аспекты сплай- новой интерполяции рассмотрены в работе [4]. Однако основная часть указанных работ по сплайнам посвящена глобальной интерпо­ляции. Локальная сплайновая интерполяция применительно к характеристикам летатель­ных аппаратов рассмотрена в работе [5], при­менительно к сигналам - в источниках [6-12].

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

При регулярной интерполяции сетка дискретизации равномерна и бесконечна, а на каждом частном интервале дискретизации формирование интерполирующей функции осуществляется по одним и тем же правилам. Обозначим координаты узлов интерполяции tn = nT, sn = s(nT), где n = 0, ±1, ±2, ...; T - период дискретизации сигнала. Запишем выра­жение для интерполирующей функции в виде

где порождающая функция φ0(Υ) удовлетво­ряет условию

Сходимость интерполяционного процес­са при неограниченном уменьшении периода дискретизации обеспечивается при выполне­нии условия [13]

где Φ0(ω) - спектральная плотность φ0(Υ).

Из условий (2), (3) следуют нормировки

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

Локальные фундаментальные интерполяционные обобщенные сплайн-базисы

При сплайновой интерполяции фрагменты интерполирующей функции ψn (t), описыва­ющие ее на каждом частном интервале дис­кретизации t ∈ [tn; tn+1], стыкуются в узлах интерполяции так, чтобы вместе с условием согласованности (2) обеспечить непрерыв­ность ее первых r производных (значение r характеризует степень гладкости):

где  - коэффициенты линейного ал­горитма оценки i-й производной сигнала;

M - порядок алгоритма оценки производ­ных.

На рис. 1 показан пример интерполяци­онного фрагмента.

 

Рис. 1. Пример интерполяционного фрагмента

 

Фрагмент ψn (t) интерполирующей функ­ции определяется значениями M предшеству­ющих и M последующих относительно ин­тервала t ∈ [tn; tn+1] отсчетов s n-M, ···, s n-1, sn sn+1, sn+2, ..., sn+M+1 (M ≥ 0 - порядок интер­поляции) и представляет собой обобщенный многочлен

Здесь  - линейно независимая си­стема функций (первичный базис);

Cn,k - коэффициенты, которые ввиду выражения (1) линейно связаны с отсчетами сигнала:

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

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

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

Таким образом, порождающая функция (8) может быть найдена из уравнения (9). Тог­да в виду (1) для каждого интерполирующего фрагмента сможем записать

Как видно из выражения (11), вычисли­тельные затраты на расчет значения интер­полирующей функции в некоторый момент времени составляют 2M +1 умножений при условии, что значение порождающей функции, соответствующее этому моменту времени, хра­нится в памяти компьютера. Последнее обыч­но имеет место, поскольку моменты времени, в которых будет рассчитываться интерполи­рующая функция, известны заранее. При этом вычислительные затраты определяются только порядком интерполяции и не зависят от сте­пени гладкости и выбора первичного базиса. Однако если указанное условие не выполнено, то на каждое из 2M +1 умножений добавля­ются N операций умножения для расчета (8) и умножения nw , необходимые для расчета функций первичного базиса. При этом в соот­ветствии с уравнением (7) чем больше степень гладкости, тем больше вычислительные затра­ты, они составляют (2M + 1)((2r + 2) + nw).

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

В статье [13] показано, что сходимость регу­лярного метода интерполяции имеет место, когда он обеспечивает восстановление едини­цы. Рассматривая восстановление единицы, из системы уравнений (4) получим условия сходимости при локальной сплайновой ин­терполяции:

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

Анализ искажений при локальной регулярной интерполяции сигналов

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

 

Поскольку спектр дискретного сигнала

 

где S(ω) - спектральная плотность сигнала s(t);

- частота дискретизации, последнее выражение перепишем в виде

Спектральная плотность интерполиру­ющей функции представляет собой результат выделения спектра исходного сигнала S (ω) из спектра дискретного сигнала Sд(ω) путем умножения порождающей функции Φ0(ω) (рис. 2) на спектральную плотность. Точным такое выделение является в случае, когда Φ0(ω) представляет собой прямоугольную функцию, что при локальной интерполяции исключено, поскольку ввиду ограниченно­сти во времени порождающей функции φ0(t) ее спектральная плотность Φ0(ω) является аналитической функцией и, не являясь тожде­ственным нулем, не может обращаться в нуль ни на каком конечном интервале. В связи с этим при условии ωд > 2ωm интерполирующую функцию ψ(t) можно формально рассматри­вать как результат искажений исходного сиг­нала s(t), при которых для каждой гармоники сигнала частоты ω независимо от других при умножении на Φ0(ω) происходит изменение ее амплитуды и наложение на сигнал колебаний частот kωд + ω, k = 0, 1, 2, ..., с амплитуда­ми, пропорциональными Ф0(kωд + ω). При этом комбинационного взаимодействия между гармониками сигнала не происходит, поэтому минимизацию искажений можно осуществлять отдельно для каждой гармоники.

 

Рис. 2. Графики спектра дискретного сигнала Sд(ω) и спектральной плотности порождающей функции Φ0(ω)

 

Искажения отдельной гармонической составляющей сигнала будем характеризовать коэффициентом искажений, определяемым как отношение действующего значения совокуп­ности нежелательных гармоник, возникших при интерполяции, к действующему значению восстанавливаемой гармоники. При этом, рас­сматривая только такую интерполяцию, при которой обеспечивается сходимость, т. е. с уче­том условия (3), Φ0(0) = T, запишем выраже­ние для коэффициента искажений:

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

Анализ зависимости Ки(ω) может быть положен в основу определения требуемого значения частоты дискретизации и/или выбо­ра метода интерполяции при заданном уровне искажений. Выбор допустимого уровня ис­кажений Ки,доп зависит от специфики реша­емой задачи и определяет граничную часто­ту ωгр для метода интерполяции, такую, что Ки(ω ≤ωгр ) ≤ Ки, доп. Для восстановления сиг­нала с максимальной частотой спектра ωm с заданным уровнем искажений требуется обе­спечить ωm ≤ ωгp , при этом каждая гармоника сигнала частоты ω восстанавливается с Ки(ω) ≤ Kи,доп.

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

При заданных допустимом уровне искажений Ки,доп, первичном базисе , порядке интерполяции M и степени гладкости r тре­буется отыскать набор элементов матрицы D (10), удовлетворяющий условиям сходимо­сти (12), который обеспечивает максималь­ную граничную частоту ωгр коэффициента искажений (14):

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

Методы решения задачи синтеза оптимального интерполяционного сплайн-базиса

Задача синтеза оптимального интерполяцион­ного сплайн-базиса (16) - это многопараметри­ческая однокритериальная задача оптимиза­ции. Замкнутый вид целевой функции задачи получить затруднительно, что обусловило оты­скание приближенных (квазиоптимальных) решений численными методами, включая ме­тоды случайного поиска и генетический алго­ритм [14, 15], и потребовало разработки про­граммного обеспечения большого объема.

При вычислениях учитывался убыва­ющий характер спектральной плотности по­рождающей функции, вместо выражения (14) использовалось (15) для Κ10и(ω). Для вычис­лений по выражению (15) была решена задача спектрального анализа порождающей функции при локальной полиномиальной сплайн-интер­поляции в общем виде [16].

Отметим также, что дополнительное привлечение взаимосвязей (13) позволяет сок­ратить количество параметров задачи.

Некоторые квазиоптимальные локальные полиномиальные сплайн-базисы

При полиномиальной сплайновой интерполя­ции первичный базис образован степенными функциями wk(t) = tk, k = 0, N -1, где N определено (7). Порождающие функции опти­мальных интерполяционных сплайн-базисов при Ки,доп = 0,001 для интерполяции поряд­ка M = 1, 2, 3 и степеней гладкости r = 1, 2 приведены в таблице. Там же даны значения граничных частот в нормированных едини­цах. Графики коэффициентов искажения по­казаны на рис. 3. Номера линий на рис. 3 со­ответствуют номерам, указанным в крайнем правом столбце таблицы.

 

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

 

Рис. 3. Коэффициент искажений для методов интерполяции из таблицы:

1 - M = 1, r = 1; 2 - M = 2, r = 1; 3 - M = 3, r = 1;

4 - M = 1, r = 2; 5 - M = 2, r = 2; 6 - M = 3, r = 2

Заключение

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

Численно-аналитическими методами по­лучены квазиоптимальные решения поставлен­ной задачи синтеза оптимального интерполя­ционного сплайн-базиса в виде порождающих функций фундаментальных интерполяцион­ных полиномиальных сплайн-базисов при ин­терполяции порядка M = 1, 2, 3 и степенях гладкости r = 1, 2. Даны практические рекомендации по их использованию: допустимые искажения обеспечиваются, если максималь­ная частота в спектре сигнала не превышает граничной частоты коэффициента искажений.

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

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

Список литературы

1. Гончаров В. Л. Теория интерполирования и приближения функций. М.: Гос. изд-во техн.-теор. лит., 1954. 330 с.

2. Ahlberg J. H., Nilson E. N., Walsh J. L. The theory of splines and their applications. New York: Academic Press, 1967. 292 p.

3. Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. М.: Наука, 1980. 355 с.

4. De Boor C. A practical guide to splines // Applied Mathematical Sciences. 1978. Vol. 27. 292 s.

5. Сухорученков Б. И., Меньшиков В. А. Методы анализа характеристик летательных аппаратов. М.: Машиностроение, 1995. 365 с.

6. Денисенко А. Н., Исаков В. Н. Применение различных методов восстановления непрерывных сигналов по их дискретным значениям // Радиотехника. 2001. № 10. С. 16–20.

7. Денисенко А. Н., Исаков В. Н. Сравнительный анализ методов восстановления непрерывных сигналов по их дискретным значениям, основанных на локальных сплайнах различной степени гладкости // Вопросы повышения эффективности радиоэлектронных систем: межвуз. сб. науч. трудов. М.: МИРЭА, 2001. С. 101–106.

8. Денисенко А. Н., Исаков В. Н. Методы сплайновой интерполяции сигналов // 52 науч.-техн. конф. МИРЭА. Сб. трудов. Ч. 2. Физико-математические науки. М.: МИРЭА, 2003. С. 79–84

9. Денисенко А. Н. Сигналы. Теоретическая радиотехника. М.: Горячая линия–Телеком, 2005. 704 с.

10. Crochiere R. E., Rabiner L. R. Interpolation and decimation of digital signals: a tutorial review // Proceedings of the IEEE. 1981. Vol. 69. No. 3. Pp. 300–331.

11. Schafer R. W., Rabiner L. R. A digital signal processing approach to interpolation // Proceedingsof the IEEE. 1973. Vol. 61. No. 6. Pp. 692–702.

12. Unser M. Splines: a perfect fit for signal and imageprocessing // IEEE Signal Processing Magazine. 1999. Vol. 16. № 6. Pp. 22–38.

13. Исаков В. Н. Сходимость при регулярной интерполяции и локальные интерполяционные базисы // Наукоемкие технологии. 2013. № 4. С. 40–46.

14. Исаков В. Н. Алгоритмы случайного поиска в задачах численной оптимизации // Сб. науч. трудов II междунар. науч.-практ. конф. «Актуальные проблемы и перспективы развития радиотехнических и инфокоммуникационных систем» (РадиоИнфоКом-2015). М.: МГТУ, МИРЭА, 2015. С. 146–151.

15. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: пер. с польск. И. Д. Рудинского. М.: Горячая линия–Телеком, 2007. 452 с.

16. Исаков В. Н. Фундаментальные интерполяционные базисы и спектральный анализ при локальной интерполяции обобщенными сплайнами // Вестник МГТУ МИРЭА. 2015. № 1 (6). С. 144–154.


Об авторе

В. Н. Исаков
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский технологический университет»
Россия

Исаков Владимир Николаевич – старший преподаватель кафедры теоретической радиотехники и радиофизики

Область научных интересов: теория сигналов, цифровая обработка сигналов, интерполяция, экстраполяция и аппроксимация сигналов, оптимальная обработка сигналов.

г. Москва



Для цитирования:


Исаков В.Н. Оптимальная регулярная локальная сплайновая интерполяция сигналов. Вестник Концерна ВКО «Алмаз – Антей». 2016;(4):24-31.

For citation:


Isakov V.N. Optimum regular local spline interpolation of signals. Journal of «Almaz – Antey» Air and Defence Corporation. 2016;(4):24-31. (In Russ.)

Просмотров: 34


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2542-0542 (Print)