Алгоритм сглаживания (?)

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

Зависит от того, что ты хочешь получить.

Если хочешь просто сгладить углы - можешь взять прямую на 90% интервала между точками, а на первых/последних 5% - сколь угодно гладкую функцию.

Сплайны - обычно работают.

Можешь взять полином степени n+1, где n - количество твоих точек.

ломаную преобразовать в кривую, с минимальным отклонением точности

Минимальные отклонения бывают разные: абсолютное, квадратическое, максимальное, ... Они определяются метрикой. ©

Возможны разные способы интерполяции ©. Выбор — по критерию близости: из статистики, физики, практики, ... или математического волюнтаризма.

Ну или как-то болемене кратко объясните как это делается правильно.

«болемене кратко»: © :)

Это просто график значений во времени. А шляпа про которую я спрашиваю нужна для зума. Ну и да, я же не знаю какой алгоритм мне подойдет.

to tyakos

полином степени n+1, где n - количество твоих точек

И он будет работать для набора только всех точек? В смысле, если я буду брать разные срезы из разных промежутков с разным кол-вом точек, то результаты будут разными?

90% и 5%

Ну вот это будет ближе к желаемому. Выглядит рабочим, проверю как оно будет на деле. Хотя... (см. ниже)

to quickquest

отклонения бывают разные

У меня необходимо не «сбить с места» значения вершин, т.е. кривить только отрезки между ними.

Спасибо за ссылки, почитаю их через пол часика — надо детей уложить.

Сейчас самое передовое для сглаживания и интерполяции кривых (на мой взгляд) - это построение кубических B-сплайнов с помощью Z-фильтров. Для понимания, курить до просветления «B-Spline Signal Processing», Part I и Part II, под авторством M. Unser, A. Aldroubi, M. Eden.

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

Если ближайший МЛУГ после 10-го сентября, предлагаю там обсудить.

Во! Спс, поищу чтиво. Насчет реализации — тут мне проще понять как оно работает и уже затем делать, чем расколупывать готовые реализации. И да, на млуге можно будет, если заеду, я ж все, в деревне теперь, и только заездами.

Какая цель сглаживания - сделать красиво или отфильтровать погрешность?

Сплайны сделают красиво, но эта красота будет «дешёвая». Если нужен именно фильтр шумов - давай математическую модель.

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

Короче, зависит от того, откуда взялись твои данные.

Ну и да, я же не знаю какой алгоритм мне подойдет.

Тогда используй любой.

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

Тогда используй любой

Ну или меня тут пнут в сторону правильного. Потому и спросил.

Сейчас мне кажется iVS понял что мне нужно. Но это пока только догадки, пока не прочитаю все ссылки что вы мне тут понакидали.

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

Как выглядят твои точки-то хоть?

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

Одно другому не противоречит: опосля понимания скачивание готовых реализаций © экономит время.

В принципе я понимаю как запилить на сплайнах. Но я не понимаю как разруливать ситуацию когда, например, где-то есть три вершины со значениями (а=0, б=10, в=0) и в первом случае срез «абв» может получиться выпуклым, а в другом пилообразным, а в третьем перевернутым пилообразным. Потому что предыдущие или следующие вершины могли бы идти в гору или спускаться или... Т.е. на лицо — влияние соседних, а мне этого нужно бы избегать. Брать больше вершин, да. Но это может быть не вариант из-за требований максимально возможного зума (я его еще не считал). И даже если я возьму больше вершин за раз, я никуда не денусь от «шумов» на граничных вершинах среза. Об этих проблемах есть в той статье?

Просто икс и игрек, где икс это время, а у игрека есть мин и макс, но там могут быть любые перепады.

Вспомнил, что в статье речь идет о uniform B-splines. То есть, можно сказать, что есть ось времени и некая функция от времени; точки - это значения данной функции через одинаковые промежутки времени. Если бы они были неодинаковые, то нельзя использовать uniform B-splines. Но в твоем случае ничего бояться не стоит, ведь любую двумерную кривую можно параметризовать произвольным образом. Благодаря чему можно говорить о двух функциях от времени (координаты X и Y), а точки считать полученными через одинаковые промежутки времени. Вспомнил об еще одной засаде - в разных источниках приводятся чуть разные формулы для B-splines (за счет сдвига и масштаба). Еще одна причина глянуть мою реализацию :-) Но это на тот случай, если данный подход тебе подойдет.

И даже если я возьму больше вершин за раз, я никуда не денусь от «шумов» на граничных вершинах среза.

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

Общий подход к граничным условиям - экстраполяция по правилу зеркального отражения. Для случая функции одной переменной, представь, что на границе слева и справа у тебя стоит по зеркалу. Двумерный случай - условие зеркального отражения для каждой из функций X(t) и Y(t) (мы их параметризуем параметром времени). Зависимости от соседних точек не будет, но наскольно точнвм будет результат, не знаю. Кривые к тому же определяются коэффициентом сглаживания, может, его удастся удачно подобрать.

Что значит дешевая красота?

Я имел в виду, что за ними не стоит физического обоснования. Чтобы оно было - нужна модель.

Ты абсолютно доверяешь твоим точкам? То есть линия обязана через них проходить?

Однако, фокус в том, чтобы предыдущий сплайн(?) между двух вершин не влиял (или влиял минимально) на следующий

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

А чем тебя ломаная (кусочно линейная) не устраивает? Ну и что, что углы?

не трогать значения вершин, и максимально плавно перетекать от вершины к вершине.

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

Годная инфа.

Нет у меня никакой модели. Что ты хочешь от человека с 9-ю классами вечерки? ))

Ломаная не устраивает потому, что мне нужно получить что-то типа envelope (огибающей). Я пробовал через low pass filter — там, во первых есть эта твоя гладкая лесенка, во вторых портятся значения, если сказать радиотехнически то там сильно падает амплитуда и смещается фаза, и невозможно подобрать фиксы фазы и амплитуды, т.к. поведение lpf сильно зависит от входных значений. Короче мне не удалось получить вменяемый результат.

И вот я пришел к безье и сплайнам. Взял точки, где каждая из них это максимальное значение на её участке (и легко будет сделать и среднее и минимальное). И еще думается это будет гибко в том плане, что можно выбирать размер участка (а-ля cutoff freq у фильтра). И через сплайны я получу намного более корректную огибающую, для моего случая, нежели через lpf.

Хотя и этот подход может оказаться не верным.

Теперь это другая история.

Для начала, возьми свои пики и пофить их экспонентой.

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

это другая история

Вовсе нет. То что я спрашивал — это часть «истории». Ведь правильнее задавать простые вопросы, чем описывать полную картину. Иначе этому — место в разделе job ))

экспонентой

Кажется тут я опять упрусь в подбор магических чисел, как и с lpf, и в одном месте будет хорошо, а в другом плохо. Или нет? Ведь перепады могут быть любыми. Ты сам делал так? Я могу в принципе реализовать все варианты и сравнить. Но все же быстрее будет взять уже обкатанный.

Ведь правильнее задавать простые вопросы, чем описывать полную картину.

Нет, если ты сам не понимаешь, чего хочешь. Понятно, за тебя работу тут делать не будут, но почитать абзац текста легче, чем подключать libastral.so.

Кажется тут я опять упрусь в подбор магических чисел, как и с lpf, и в одном месте будет хорошо, а в другом плохо. Или нет? Ведь перепады могут быть любыми. Ты сам делал так?

Ты используешь функцию на точках, она возвращает тебе 2 параметра - линейный и экспонентный коэффициенты.

Я использовал для оценки силы сигнала и скорости его затухания. Использовал точки - пики сигнала.

если ты сам не понимаешь

Огибающая должна использоваться для максимально плавной автоматизации некоторой реакции на входные данные. И что тебе прояснило такое объяснение? Оно же ничем не отличается от «я хочу красивую картинку».

для оценки силы сигнала и скорости его затухания

Подойдет ли мне эта «экспоненциальная плавность». Вот в чем вопрос. Надо пробовать.

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

В переводе на язык математики: добиваются непрерывности первой и второй производной.

Оно же ничем не отличается от «я хочу красивую картинку».

Отличается: красивость для глаза != устойчивость регулирования системы. ©

О, дак там по ссылке интересные вещи. Походу то что нужно. Спасибо. Ушел курить их.

добиваются непрерывности первой и второй производной.

Непрерывность второй производной никому, обычно, не нужна. Кубических кривых, обеспечивающих гладкость, хватает в 99.9%.

Там на хабре, при построении кривых Безье, заложились на знание касательных к графику. Всегда ли есть эта инфа? Я думал о задаче ТС как об интерполяции, т.е. даны значения точек без производных в них.

Непрерывность второй производной никому, обычно, не нужна. Кубических кривых, обеспечивающих гладкость, хватает в 99.9%.

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

В системах самонаведения аналогичные требования для «правильного поведения» по критериям устойчивости.

А для глаза — 2 производная конечно же «нинужна» :)

Я думал о задаче ТС как об интерполяции, т.е. даны значения точек без производных в них.

Этого никто, кроме ТСа не знает, да и он тоже :)

Там на хабре, при построении кривых Безье, заложились на знание касательных к графику. Всегда ли есть эта инфа?

Они их там просто подбирают. Формулы есть.

У кривой Безье четыре параметра, тогда как координаты начала и конца дают только два параметра. Очевидно, что еще два подбирают. Вопрос не в этом, а в том как их правильно подбирать. Насколько я понял из поста, ничего лучше, чем построить касательные в точках, там не предложили. Естественно, речь об автоматическом построении кривых Безье, ручная подгонка — удел дизайнеров. Так вот, вопрос что делать, если касательные неизвестны, там остался открытым.

Формулы есть.

Методом проб и ошибок эвристика для расчёта расстояния от точки интерполируемой последовательности до промежуточной контрольной получилась такой:

Это не формулы, а детский сад.

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

Так вот, вопрос что делать, если касательные неизвестны, там остался открытым.

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

Это не формулы, а детский сад.

Ну я с этим не спорю. Но у них такая задача была.