Перейти к:
Оптимальная регулярная локальная сплайновая интерполяция сигналов
https://doi.org/10.38013/2542-0542-2016-4-24-31
Аннотация
Ключевые слова
Для цитирования:
Исаков В.Н. Оптимальная регулярная локальная сплайновая интерполяция сигналов. Вестник Концерна ВКО «Алмаз – Антей». 2016;(4):24-31. https://doi.org/10.38013/2542-0542-2016-4-24-31
For citation:
Isakov V.N. Optimum regular local spline interpolation of signals. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2016;(4):24-31. https://doi.org/10.38013/2542-0542-2016-4-24-31
Введение
Рассмотрена задача регулярной интерполяции сигнала со спектром, ограниченным частотой ω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. https://doi.org/10.38013/2542-0542-2016-4-24-31
For citation:
Isakov V.N. Optimum regular local spline interpolation of signals. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2016;(4):24-31. https://doi.org/10.38013/2542-0542-2016-4-24-31