LINUX.ORG.RU

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

 , ,


0

3

Есть набор точек в двумерном пространстве. Это вершины ломаной.

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

Я нагуглил кривые безье, вот это все. Вроде как это то что нужно. А может быть нет. Ибо они там N-мерные (с разным кол-вом опорных точек, e.g. квадратичные, кубические). И даже если они это то что мне нужно — по каким правилам я должен выбирать из существующих точек или манипулировать дополнительными?

Уверен что сплайны/безье это не единственный подход. И, возможно в моем варианте даже не подходящий.

Мне нужен пинок в какую сторону гуглить. Что искать? Ну или как-то болемене кратко объясните как это делается правильно.

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

peregrine ★★★★★ ()
Последнее исправление: peregrine (всего исправлений: 2)

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

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

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

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

tyakos ★★★ ()

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

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

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

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

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

quickquest ★★★★★ ()
Ответ на: комментарий от peregrine

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

to tyakos

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

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

90% и 5%

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

to quickquest

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

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

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

deep-purple ★★★★★ ()

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

iVS ★★★★★ ()
Ответ на: комментарий от iVS

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

iVS ★★★★★ ()
Ответ на: комментарий от iVS

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

deep-purple ★★★★★ ()

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

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

Pythagoras ★★ ()
Ответ на: комментарий от deep-purple

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

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

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

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

tyakos ★★★ ()
Ответ на: комментарий от Pythagoras

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

deep-purple ★★★★★ ()
Ответ на: комментарий от tyakos

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

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

deep-purple ★★★★★ ()
Ответ на: комментарий от tyakos

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

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

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

iVS ★★★★★ ()
Ответ на: комментарий от deep-purple

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

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

quickquest ★★★★★ ()
Ответ на: комментарий от iVS

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

deep-purple ★★★★★ ()
Ответ на: комментарий от tyakos

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

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

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

iVS ★★★★★ ()
Ответ на: комментарий от deep-purple

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

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

quickquest ★★★★★ ()
Ответ на: комментарий от deep-purple

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

iVS ★★★★★ ()
Ответ на: комментарий от deep-purple

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

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

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

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

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

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

Pythagoras ★★ ()
Ответ на: комментарий от deep-purple

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

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

iVS ★★★★★ ()
Последнее исправление: iVS (всего исправлений: 1)
Ответ на: комментарий от Pythagoras

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

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

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

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

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

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

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

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

tyakos ★★★ ()
Ответ на: комментарий от tyakos

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

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

экспонентой

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

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

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

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

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

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

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

tyakos ★★★ ()
Ответ на: комментарий от tyakos

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

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

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

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

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

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

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

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

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

quickquest ★★★★★ ()
Ответ на: комментарий от quickquest

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

deep-purple ★★★★★ ()
Ответ на: комментарий от quickquest

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

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

iVS ★★★★★ ()
Ответ на: комментарий от quickquest

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

iVS ★★★★★ ()
Ответ на: комментарий от iVS

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

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

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

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

quickquest ★★★★★ ()
Ответ на: комментарий от iVS

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

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

quickquest ★★★★★ ()
Ответ на: комментарий от iVS

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

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

Pythagoras ★★ ()
Ответ на: комментарий от Pythagoras

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

iVS ★★★★★ ()
Ответ на: комментарий от Pythagoras

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

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

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

iVS ★★★★★ ()
Ответ на: комментарий от iVS

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

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

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

Pythagoras ★★ ()
Ответ на: комментарий от iVS

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

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

Pythagoras ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.