Апроксимация сплайнами, оптимизация размещения контрольных точек Опции

[ataradov]

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

На картинках изображена характерная кривая (1 - общий план, 2 - приближенное начало), которую нужно представить сплайнами или любым другим способом, занчительно снижающим объем памяти, требуемый для ее хранения, но при этом допускающий сравнительно простое восстановление по точкам, не разжимя всей кривой сразу (то-есть запаковать ее ZIP-ом нельзя ).

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

В идеале нужен алгоритм, который позволит по заданному числу контрольных точек определть их положение так, чтобы СКО было минимальным. Или наоборот, по заданному СКО определить требуемое число точек и их положение.

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

Эскизы прикрепленных изображений

 

[igorchem]

В идеале нужен алгоритм, который позволит по заданному числу контрольных точек определть их положение так, чтобы СКО было минимальным. Или наоборот, по заданному СКО определить требуемое число точек и их положение.

Если Вам необходимо найти оптимальные распределения точек для сплайн аппроксимации k-ой степени в l2 норме, можно поступить так:
вначале аппроксимируете Вашу функцию сплайном k+2 степени s_{k+2}(x).
Далее ищите разбиение x_0 < ... < x_i < ... < x_n так, чтобы
\int_{x_i}^{x_{i+1}} \left(\frac{\delta^{k+1} s_{k+2}(x)}{\delta x^{k+1}}\right)^{\frac1{k+1}} dx было одинакого на всех отрезках. Если запутаетесь или не сможете сами, постораюсь формулы выложить, но, очень надеюсь, что сами справитесь.

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

Моя идея - запишите эти функции (n штук) вначале на очень мелкой сетке с кусочно-постоянными или кусочно-линейными базисными функциями, чтобы шаг такой сетки был существенно меньше минимальной осцилляции. У Вас будет n векторов, образуйте из них матрицу. Сделайте этой матрице сингулярное разложение и выбросьте все сингулярные вектора, сингулярные значения которых будут меньше точности оцифровки вашого сигнала. Примените то, что я описал к оставшимся левым сингулярным векторам. Есть большая уверенность, что после всего этого Вы сильно сожмете эти данные, распаковка их будет съедать только несколько операций на точку, да и шум Вы тоже погасите.

Сообщение отредактировал igorchem - Mar 3 2011, 09:37