Выбор контрольных точек для сплайна

Из-за небольшой зашумленности искать локальные минимумы и максимумы тяжело.

Я как-то делал задачу для геофизика, там у него аналогично было, надо кучу значений от шума почистить. Использовался «метод окна» или как-то типа того. Суть такова.

Есть окошко. Скажем, в него влазит 3 показаний. Можно 5, 7, ...

Этим окошком делается прогонка по числам вот таким образом:

Шаг 1:[1 2 3]4 5 6 7 8
Шаг 2: 1[2 3 4]5 6 7 8
Шаг 3: 1 2[3 4 5]6 7 8
Шаг 4: 1 2 3[4 5 6]7 8
Шаг 5: 1 2 3 4[5 6 7]8
Шаг 6: 1 2 3 4 5[6 7 8]

Надеюсь, ты понял суть прогонки. То есть на каждый шаг у нас есть окошко, например в шаге 3 это [3 4 5].

За каждый шаг прогонки надо заменить значение посередине этого окошка (например, второе, если ширина окошка — 3 значения) на «хорошее», если оно «плохое». Там было медианное среднее или чё-то такое...

Это всё что я выудил из своей памяти.

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

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

Спрошу у знакомых геофизиков.

пока только один ответил в высшей степени расплывчато:

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

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

Если аппроксимирует, то делать то же самое, но пропустить сравнение выборки с ее сглаженным вариантом (т.е. сгладить, найти производную и по значению производной расставить контрольные точки).

// это лишь мое мнение, может существовать еще множество вариантов решения этой задачи.

Обычно делают интерполяцию

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

>Представление в виде полинома не подходит - у него получится очень большая степень. А как это обычно делают?

Сейчас модны вейвлеты: A wavelet tour of signal processing.

>способ сжать эти данные.

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

Сейчас модны вейвлеты:

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

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

Важно еще восстановление сравнительно быстрое и по точкам, так как дожно происходить в очень ограниченных ресурсах.

Сплайны в принципе подходят, ужать 500000 в 50 * 5 значений - это не плохо :) Другой вопрос, что если можно еще меньше или более оптимально, то неплохо бы это сделать.

Да и не любитель я таких брутфорсных методов, все-таки математика рулит.

ну да, он неправильно понял

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

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

ужать 500000 в 50 * 5 значений - это не плохо

Если у вас действительно настолько гладкая функция, можно и вейвлеты использовать. Главное, правильно подобрать базис и порог.

Зашумленную функцию, кстати, нельзя интерполировать - только аппроксимировать.

Если у вас действительно настолько гладкая функция, можно и вейвлеты использовать. Главное, правильно подобрать базис и порог.

Функция - примерно как затухающая зкспонента с небольшими колебаниями по мере затухания, но в начале у нее сравнительно резкие колебания (туда приходится сейчас точек 40 из 50).

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

Погуглите. Нормальной литературы на русском почти не существует, на английсом есть приличные статьи.

>Так есть все-таки инженерные статьи про вейвлеты?

Есть (PDF), но примитивные.
Книга по вышеприведённой ссылке полезнее и для понимания и для практики.

>ориентированные на практику

Для вейвлетов в Linux есть готовая библиотека: Quantization, Compression, and Coding Library (QccPack)

http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B... — это относится к вопросу?

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

мне 3 геофизика про него написали

[quote] ну можно попробовать методов наименьших квадратов, потом каждой точке мы можем задать свой вес [/quote]

>Может есть какие статьи или примеры более конкретные и ориентированные на практику, чем книжка?

http://www.gnu.org/software/gsl/manual/html_node/DWT-Examples.html

мне 3 геофизика про него написали

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

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

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

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

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

Общий вид функции примерно такой: http://dl.dropbox.com/u/6121480/synth/full.png, начало в увеличенном виде: http://dl.dropbox.com/u/6121480/synth/zoom.png.

Увеличенная часть довольно адекватно описывается 15-20 точками, но в частично ручной работой, а нужно автоматизировать.