Содержание к диссертации
Введение
Глава I. Проблемы приближения и сглаживания функций 36
1.1 Проблемы полиномиальной аппроксимации функций 36
1.2 Трудности задачи сглаживания результатов наблюдений 39
1.2.1 Трековые задачи 44
1.3 Непараметрические методы сглаживания 45
1.3.1 Метод ядерного сглаживания 48
1.3.2 Оценки к-ближайших соседей. Суперсглаживатель 52
1.3.3 Сглаживание сплайнами 55
1.3.4 Локально-полиномиальное разложение 57
1.3.5 Метод скользящего среднего (МСС)
1.3.6 Рекуррентные методы сглаживания 59
1.3.7 Медианный сглаживатель 60
1.4 Вейвлетный анализ 61
Глава II. 4-точечные преобразования на координатной плоскости. Адаптивные проективные фильтры 66
2.1 Дискретные проективные преобразования на координатной плоскости 67
2.1.1 Функции двойного отношения четырех точек 67
2.1.2 CR-функции и квадратичная парабола 71
2.1.3 Определение и геометрический смысл DPT 72
2.1.4 dpT-алгоритм 75
2.1.5 Устойчивость DPT к ошибкам наблюдений 76
2.2 Адаптивные проективные фильтры (АПФ) 78
2.2.1 Задача обнаружения и распознавания треков 78
2.2.2 DPT как модель линейной системы 80
2.2.3 Алгоритм адаптивных проективных фильтров (АПФ) 84
2.2.4 Применение АПФ для обнаружения трековых сегментов (TS). 88 Глава III. Параметризация функций и DPT-приближение 95
3.1 D-преобразование степенного базиса 95
3.1.1 Многочлены Gn{x;A,L) 97
3.1.2 L, Л- параметризация базиса {хп} 99
3.2 4-точечный подход к аппроксимации и сглаживанию функций 103
3.2.1 TPS-модель 105
3.2.2 TPS-приближение гладкой функции 1 3.2.3 Среднеквадратичное приближение y(x)eL2[a,b] 109
3.2.4 Разложение q{x)e C{n)[X,L] по базису {Sn{x;A,L)} 111
3.2.5 TPS-сглаживание 113
3.3 DPT-аппроксимация и другие методы приближения функций 117
3.3.1 Аппроксимация и и - преобразование 117
3.3.2 DPT-приближение 118
3.3.3 Сравнение с другими методами аппроксимации 119
Глава IV. Кусочно-кубическое приближение и сглаживание кривых в режиме адаптации 123
4.1 Выбор модели локальной аппроксиманты 127
4.2 Локально-оптимальное кубическое сглаживание кривых 129
4.2.1 Устойчивость к ошибкам 130
4.2.2 Итерационная процедура для вычисления оценки в 133
4.2.3 Коррекция фиксированных параметров 138
4.2.4 Алгоритм LOCUS 140
4.3 Переход к вычислению по параметрам 146
4.3.1 Вычисление оценки свободного параметра 149
4.3.2 О коррекции реперных точек в LOCUS-P 152
4.3.3 Примеры сглаживания процедурой LOCUS-P 153
4.4 Сравнение LOCUS с другими сглаживателями 156
Глава V. DPT-подход к сглаживанию поверхностей 163
5.1 Бикубические модели с реперной привязкой 164
5.1.1 НБМ - модель с девятью опорными точками 164
5.1.2 Полная бикубическая модель 170
5.2 Бикубическое сглаживание поверхности 171
5.2.1 Регрессионная процедура для НБМ 171
5.2.2 Примеры 173
5.3 Выводы к главе V 177
Основные результаты и выводы 179
Литература
- Непараметрические методы сглаживания
- Определение и геометрический смысл DPT
- Локально-оптимальное кубическое сглаживание кривых
- НБМ - модель с девятью опорными точками
Непараметрические методы сглаживания
В общем случае производные /(ч-) можно вычислять во внутренних точках х11,/л = \,2 отрезка [-Я,Я] . Применение такой схемы для приближения гладких функций на [-Я,Я] , при х0 = 0 , позволяет найти ак, зависящие от f (xM), dfk\xM),i = 1,2,3 и 4+2(хм) где Н Ь M = U2: k = l,2,...,n/2, j = l,2,-,n . Получено выражение матричных элементов sfJ2(xM) через индексы степени (у + 2) и -е производные /(t)(jc) . Следует отметить, что выбор внутренних точек хм существенно влияет на точность аппроксимации. Рассмотрен пример применения этой схемы для приближения синуса на отрезке [-я,л], в котором ошибка аппроксимации почти на два порядка меньше ошибки разложения синуса по формуле Тейлора для и =9. Приведены графики изменения ошибки в зависимости от выбора хм [53].
В п. 3.2.1 строится модель трехточечного локального сплайна (TPS) с одним свободным параметром. Приведен пример применения TPS для приближения функции на отрезке. Полученное решение совпадает с решением, которое дает классический кубический сплайн.
В п.3.2.3 рассмотрена задача среднеквадратичного куби-чекого приближения f{x) є L2[Л,L] с использованием TPS-модели. Задача приближения /(х)еС(-")[Я,Ц в базисе {S„(x;A,L) } рассматривается в п.3.2.4.
Проведено исследование приближения функций с применением DPT. Показана зависимость ошибки аппроксимации от выбора точек вычисления производных (хи) на интервале при нахождении коэффициентов разложения. В п.3.2.5 третьей главы рассмотрена стандартная задача сглаживания точек, рассеянных вблизи кубической кривой с применением TPS-модели. Алгоритм сглаживания кубической кривой на основе TPS использует оценки ординат реперных точек в качестве фиксированных параметров, а оценка свободного параметра, находится методом наименьших квадра тов. В результате оценка параметра находится по схеме простой линейной регрессии. Проведено сравнение с результатами сглаживания с использованием традиционной МНК-процедуры. Для оценивания параметров TPS-модели используется в 3-4 раза меньше арифметических операций по сравнению с классической кубической моделью [53].
Сравнение "4-точечного" приближения действительных функций с приближениями, основанными на разложениях Паде и «-преобразованиях [64], а также с приближениями по многочленам П. Л. Чебышева [1,2,3] рассматривается в п.3.3. На конкретных примерах, путем численных рассчетов с использованием пакета Maple показано, что точность DPT-аппроксимант более высокая на границах промежутка и носит равномерный характер на всем интервале по сравнению с Паде-аппроксимантами. Показано, что DPT-аппроксиманты по сравнению с и-аппроксимантами дают меньшую максимальную ошибку на всем промежутке и лишь немного уступают точности классической чебышевской аппроксимации.
В четвертой главе диссертации предложен простой итерационный метод для локального приближения и сглаживания кривых с использованием 3-точечного кубического сплайна. Метод основан на 4-точечных преобразованиях и на рекурсивном методе наименьших квадратов. Получен рекуррентный алгоритм цифрового сглаживающего фильтра третьего порядка, в котором свободный параметр TPS-модели определяется по типу известной в теории стохастической аппроксимации процедуры Роббинса-Монро [42,43]. Степень подавления ошибок и скорость адаптации алгоритма к локальной форме кривой могут контролироваться параметрами и составляют величину 0(п ). Алгоритм устойчив к случайным аддитивным ошибкам, простой в реализации, использует небольшие ресурсы памяти и может работать в режиме поступления данных . Это актуально при решении задач по обнаружению и распознаванию треков, цифровой обработки сигналов, сглаживанию контуров и т.п. Предложенный метод может быть ис пользован также для восстановления сложных зависимостей [94], поиска корней функции и экстремумов. Приведены рабочие характеристики алгоритма.
Создание простых, надежных и экономичных сглаживающих алгоритмов является актуальной задачей для широкого спектра исследований и практических приложений. В частности, такие алгоритмы используются при обработке экспериментальных данных и численном решении прикладных задач в различных областях науки и техники [13,19,93,46,107-109].
В прикладных задачах, как правило, функции часто задаются не формулой, а с помощью какого-либо вычислительного процесса различной сложности. Например, функции могут являться результатом численного интегрирования дифференциального уравнения на заданном отрезке или вычисляться по сложной итерационной схеме и т.п. В таких случаях их называют вычислимыми функциями. Значения таких функций известны с заданной точностью, однако их явный вид заранее не известен, так же, как и их общие свойства. Все операции над такими функциями могут выполняться только посредством вычисления значений самой функции. Более сложные ситуации возникают при обработке эмпирических данных, получаемых в измерениях при наличии посторонних шумов, например, в системах автоматической обработки контурных изображений, в системах адаптивного управления динамическими объектами, при цифровой обработке сигналов и т.п. [13,19,93,107,109]. Как правило, анализ данных в таких системах выполняется в режиме реального времени, для которого существуют жесткие ограничения и противоречивые требования к алгоритмам обработки. Такие алгоритмы должны обеспечивать заданную точность и высокую скорость вычисления параметров при ограниченных ресурсах памяти и быть устойчивыми к фону и ошибкам.
Определение и геометрический смысл DPT
Справедливость этих формул проверяется непосредственной подстановкой выражений для соответствующей функции из таблицы 2.1.
Ортогональная связь pt с точками евклидовой плоскости, расположенными на прямых линиях и/или квадратичных параболах (см. ниже (2.7)). Мы видим, что функции двойного отношения образуют некоторую замкнутую ситему. Структура этой системы имеет тройную симметрию. Например, из рг легко получить все остальные функции. Так рх и р2 получаются из формулы для ръ формальной перестановкой в ней параметров и переменной: А г т и L T соответственно, а функции dt определяются через pi по (2.5).
Тройная симметрия для р, хорошо видна из диаграммы их вычисления (рис.2.3), где структура системы условно изображена в виде трех перекрывающихся треугольников - X ,L и г. Шесть их вершин попарно расположенны в трех точках. Остальные вершины свободные. Общие точки обозначены как разности (Aj-Aj), а изолированные точки - как произведения величин (со знаками), не повторяющиеся в остальных вершинах треугольника. Функция pt(r,X,L) вычисляется делени ем величины в изолированной вершине соответствующего треугольника на произведение величин, расположенных в его двух противоположных вершинах. Из диаграммы видно, что для вычисления всех трех функций в текущей точке т необходимо выполнить 12 операций. Шесть операций 1-го уровня
Ръ XL находятся в вершинах треугольников. Операции 2-го уровня - это три умножения попарных разностей. На последнем уровне выполняются операции деления. Вычисления на каждом уровне можно выполнять параллельно, благодаря чему все Рис. 2.3. три функции могут быть посчитаны за время выполнения трех операций: -, х и -г-, что в среднем составит по одной операции на функцию.
Простое правило получения формул из таблицы 2.1 с учетом двойного отношения (2.3) определяется равенствами: Мы видим, что левый циклический сдвиг тройки Я L т дает нам функции pi , а четверки для dt находятся простой перестановкой местами точек 0 -»г . Примечание 1. Интересно отметить, что функции /7,-,/ = 1,2,3 также могут быть определены через координаты векторного произведения
Особый интерес с точки зрения DPT представляет семейство квадратичных парабол с вертикальной осью: y(x) = ax2 +bx + c , (2.6) где a,b,c -действительные числа. Из координат произвольной четверки точек на кривой (2.6) Рк(хк,ук) , к = 0,Л,Цт составим два вектора AYT =[Ауг,Ау2,Ау3] , Ау,- =у{ -у0 , г = Я,1,т и Рг = [р},р2,Р3], где Я = хл -х0 , L = xL -х0 , т = хт -х0 , a Pj определены в (2.4) и таблице 2.1. Тогда (P,AY) = 0, (2.7) т.е. Р и AY ортогональны. Равенство (2.7) проверяется простой подстановкой в него всех указанных величин. Свойство (2.7) представляет собой простой классификатор, с помощью которого можно определять лежат ли заданные четыре точки плоскости на прямой или квадратичной параболе.
Используем свойство (2.7) для построения 4-точечных преобразований, или DPT. Для этого на произвольной гладкой кривой /(х)єС зафиксируем три различные точки или репер полюсных точек Pz(xx,A) и PL L /L) Тогда для произвольной текущей точки Px(x,f(x)) и трех фиксированных точек репера 91 условие (2.7) будет выполняться только тогда, когда все четыре точки кривой окажутся также на прямой линии или на квадратичной параболе. В остальных случаях правая часть в (2.7) будет давать нам число, отличное от нуля. Таким образом, мы получим отображение текущей точки Рх в другую точку Ph = Рк(т,к(т)) , т = х-х0 , т.е.
При отображении (2.8) ордината текущей точки образа Ph определяется точкой пересечения параболы (или прямой), проходящей через три точки Рк , PL и Рх с осью г = 0 (х = х0) (рис.2.4). Базисная точка Р0 остается неподвижной, а трансформация опорных точек Рх, PL происходит асимптотически через предел при х- хх и х-» х соответственно (см. ниже) . Величины х0, Л, L , а также "реперные ординаты" fx , fL и /0 являются параметрами преобразования. Отсюда следует зависимость преобразований от параметров, т.е. вид и положение кривой h(r) на плоскости определяются не только функцией f(x) , но и выбором репера 91. Отображение (2.8) (прямое и обратное преобразования) выполняется на основе двух взаимообратных операций, для обозначения которых введем следующие записи:
Геометрический смысл T)[/0);9t] для различных реперов Щ и Щ . Операция / (л:;91) по аналогии с производной имеет наглядный геометрический смысл (рис. 2.4): кривая h{r) = f (x;4R) является геометрическим местом точек, ординаты которых равны ординатам точек пересечения параболы П(х;9?) (или прямой) , проходящей через три точки (РЛ,РЬ,РХ) с базисной осью г=0. При обратном преобразовании ордината текущей точки берется на h(r), а точки пересечения берутся на перпендикулярах к соответствующей оси в точке Т=Х-Х0 и в точке пересечения с базисной осью.
Локально-оптимальное кубическое сглаживание кривых
Возможности четырехточечного подхода для сглаживания экспериментальных данных показаны на примере решения актуальной в физике элементарных частиц задачи по обнаружению и распознаванию треков [4 9] . В этой задаче на основе линейно-квадратичной модели разработан алгоритм адаптивных проективных фильтров (АПФ), предназначенных для обнаружения и распознавания участков зашумленных траекторий на изображениях многотрековых событий, регистрируемых современными физическими установками. АПФ-алгоритм обобщен для слежения за кривыми более сложной формы [61], что актуально при решении задачи нахождения контуров сложной формы. На практике, при описании контура на плоскости, широко используются дуги кубических парабол (кубические сплайны). Покажем преимущества TPS-модели при сглаживании точек, рассеянных около кубической дуги по сравнению с классической четырехпараметрической моделью (3.18). Так как измеренные на кубической параболе точки с помощью DPT преобразуются в точки, группирующиеся около прямой (см. рис.3.7) и DPT - образом модели тоже является отрезок прямой (3.19), то модель (3.17) является достаточно гибким структурным элементом при разработке адаптивных алгоритмов для решения многих прикладных задач. Три параметра этой модели (репер) выбираются из входных данных и их точность определяется измерительными ошибками, влияние которых на форму кубической дуги можно регулировать подходящим выбором базы Н=Ь-Я и операцией DPT. При удачном выборе реперепера форма TPS-модели легко трансформируется с помощью только одного свободного параметра а .
DPT-преобразование кубической параболы. Эти свойства модели позволяют в несколько раз уменьшить число арифметических операций при сохранении необходимой точности вычислений. Рассмотрим стандартную задачу сглаживания для кубической модели. Задача ТЗ. Найти кубическую параболу, наилучшим образом описывающую на заданном отрезке соотношение между измеренными координатами {xj} и {/, } , j = l,2,--,N; N»3, где Jj = fj+ejl ej N(0,cr2), a xj измерены без ошибок. Классическое решение этой задачи дается методом наименьших квадратов (МНК) для модели (3.18), в результате чего находятся оценки ее четырех параметров. Для TPS-модели из условия
В частности, из (3.35) и (3.34) видно, что число арифметических операций для TPS-модели значительно меньше, чем для модели (3.18). Кроме того, табулированием семи функций di,d2,d3,zdl,zd2,z и г2 в узлах сетки {TJ}&[A.,L] выбранного окна можно дополнительно сократить число динамических операций. Оценка показывает, что даже при табулировании базисных функций {х},т = 1,2,...,6 в модели (3.18) и в зависимости от объема выборки N , требуется в 3-4 раза больше операций, чем в TPS-модели. Другое решение задачи ТЗ можно найти на основе свойства DPT подавлять ошибки измерений и понижать степень многочлена на два. В этом случае МНК-оценка а находится из условия в следующем виде где Nk N , (N»4) . Индекс і относится к тем точкам, для которых г(. -Л Тп и г,--L Гп , где Т„ - порог, задающий ширину "шумовой" зоны. В этом случае, из-за "полюсных шумов" выбираются только те точки, для которых модуль ошибки их DPT-преобразования не превосходит заданного порога. При этом кубическая модель исходных данных переходит в модель прямой линии почти для всех преобразованных точек, за исключением, может быть, тех, которые попадают в зону неустойчивости (рис.2.5). Тем самым размерность исходной зада 115 дачи уменьшается на два. Пример сглаживания модельных данных по формуле (3.35) показан на рис.3.8.
На решетке 100x100 пикселей задан набор точек {ф} } кубической параболы, к ординатам которой добавлены случайные отклонения {Sj }, распределенные нормально с дисперсией равной 10 пикселям. На графике выделены три реперные точки, по которым определены параметры преобразования.
Все точки {фк}, кроме реперных, преобразованы в точки {Цк }, группирующиеся вдоль прямой линии (а) с угловым коэффициентом aXL . По точкам прямой получена МНК-оценка й (формула (3.35)), после чего обратным преобразованием точек {Як} были найдены оценки {фк } искомой кривой (Ь) и
На рис. 3.8(b) показана также прямая, полученная V-преобразованием фита, с использованием МНК-оценок параметров традиционной модели (3.18). Параллельность прямых указывает на совпадение результатов обработки, полученных разными методами. Внизу показана гистограмма преобразованных точек Лк . В работе [54] выполнено сравнение результатов, полученных с помощью DPT-аппроксимации действительных гладких функций ф(х) еС " [Л,] с аппроксимациями многочленами Чебы шева [21] и с «-аппроксимацией [64], которая имеет более высокую точность чем аппроксимация Паде на концах промежутка. Показано, что максимальная ошибка DPT-аппроксимант меньше максимальной ошибки, полученной м-приближенями на всем промежутке и несколько больше, максимальной чебышев-ской ошибки. На концах интервала точность приближения методом DPT значительно лучше точности, которую дает метод «-преобразований.
НБМ - модель с девятью опорными точками
В пятой главе диссертации предлагается новый подход к задаче полиномиального сглаживания поверхностей от двух переменных бикубической моделью с использованием опорных (реперных) точек поверхности [56]. Рассматривается модель для регрессионной задачи о вычислении в заданной точке (x.,j») оценки & некоторой функции F(x,y) по ее измеренным значениям {Fk }. Алгоритмы, использующие реперные точки при аппроксимации и сглаживании одномерных функций, рассматривались в работах [49,53-55,62].
Как известно, сглаживание функций двух и более переменных характеризуется повышенной трудоемкостью и сложностью, в том числе из-за увеличения размерности матрицы системы нормальных уравнений. Это наглядно демонстрируется уже при интерполировании функций двух переменных, которое становится более громоздким по сравнению с интерполированием функции одной переменной [6,7].
При использовании полиномиальной модели число коэффициентов, подлежащих определению, заметно растет с увеличением порядка приближения. Известны также трудности, связанные с плохой обусловленностью полиномиальных моделей регрессии для полиномов степени шесть и выше, особенно при равномерном задании узлов, когда регрессионная матрица соответствующей модели становится плохо обусловленной [26,37]. Для локального сглаживания поверхности здесь предлагается использовать кубическую по каждой переменной модель, в которой одна часть параметров (биквадратная) выбирается на поверхности в виде реперных точек, а другая часть (бикубическая) включает свободные параметры. Такая конструкция модели дает возможность более чем в два раза понизить размерность матрицы системы нормальных уравнений.
Базисные функции предлагаемой бикубической модели зависят от координат узлов 9-точечной прямоугольной репер-ной сетки и выражаются через одномерные весовые функции 3-точечного кубического сплайна, предложенного в четвертой главе настоящей диссертации и в работе [53] . В этом случае мы получаем неполную бикубическую полиномиальную модель (НБМ), в которой коэффициент при Xіуъ равен нулю. Реперная привязка НБМ к поверхности позволяет ослабить вычислительные трудности, связанные с плохой обусловленностью системы нормальных уравнений при увеличении порядка аппроксимирующего полинома [37] , и почти в три раза повысить скорость вычислений. Эти качественные характеристики являются весьма актуальными при использовании модели для решения практических задач, особенно в системах, работающих в реальном времени.
Необходимость в алгоритмах аппроксимации и сглаживания поверхностей возникает в ряде научных и прикладных задач при замене сложной функциональной зависимости более простой (полиномиальной) для сглаживания экспериментальных данных, в частности, при обработке изображений, исследовании поверхностей отклика [37], при анализе зависимостей магнитных структур и др.
Рассмотрим представление поверхности, в котором прямоугольная область R : а х Ъ ; с у d делится на прямоугольники Ry : хм х х„ум y yjr (i = l,2,...,N;j = 1,2,...,М ) . На каждом таком прямоугольнике определяется поверхность F(x,y), совпадающая вдоль каждой из его четырех сторон с одной из заданных кривых ft(x), gj(y), определенных на отрезках, разбивающих R на Ry (представление по Кунсу [26]).
Разделим Ry на четыре части отрезками вдоль координатных осей и построим 9-точечную сетку (рис. 5.1а), на которой будем аппроксимировать поверхность F(x,y), используя в качествеfj(x) и gj(y) кубические функции. Построим модель поверхности, локально аппроксимирующую функцию двух переменных F(x,y) на 9-точечной сетке А = АЛ х Дл прямоугольника R :Xu u Lu, Av v Lv, (5.1) где Ак :Ли=х -х0 х0 хк -x0=Lu Ак : Л,„ = ук- у0 у0 уц -y0=Lv, а и-х — хй, v = у - у0 . Пусть в узлах сетки Д заданы значения функции Ftj = F\xl,yj), і, j = 1,2,3 . Для упрощения формул перенесем начало координат в точку F(x0,y0) : ф = Р(х-х0,у-у0)-Р(х0,у0) = ф(и,у) . Набор значений функции в узловых точках обозначим через {фу} (рис. 5.16), параметры сетки - через Auv : {ЛИ;ЛУ} ,
