приближение последовательности точек на плоскости кривой

[e7e5]

PAV писал(а):

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

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

Может, что-то упустил. Допустим есть программа, которая сглаживает почти как человек - на экране компьютера появляется жирная плавненькая кривая. А дальше? Для чего она ( сглаженная кривая) нужна?

[PAV]

e7e5 в сообщении #199009 писал(а):

Может, что-то упустил.

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

[e7e5]

PAV писал(а):

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

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

[Алексей К.]

Алексей К. в сообщении #196258 писал(а):

Мои соображения вряд ли конкретно помогут, но я решил их выложить. Быть может, это подскажет "так делать не надо" или наведёт на другие мысли.

А нижеследующие мои соображения вообще не помогут! И опять "я решил их выложить". Что за напасть?! Предлагать людям в здравом уме минимизировать целочисленную функцию 1000 (тысячи) переменных?! При том, что мотив скорости вычсилений явно звучал в постановке задачи.

Вернёмся к моему эллипсу и кардиограммам. Предположим, что я там не с четвертинкой эллипса игрался, а с замкнутым эллипсом. N точек на нём. Координаты точек практически точные. Строим кардиограмму. Получаем ломанную (с виду --- гладенький график) с 4 (четырьмя) экстремумами. Меньше никак (теорема о четырёх вершинах овала).
Начинаем точечки портить, допустим, в некоторых ограниченных пределах, типа $\sqrt{\Delta x^2 + \Delta y^2}<\varepsilon$. На кардиограмме получаются всякие дёргания (биения? колебания? см. те же примеры). Количество экстемумов увеличивается и может дойти до величин порядка $N$ (359, например).

А вот уменьшить количество эктремумов --- никак. Т.е. можно извратиться, сделать 2 (никак не 3!), преобразовав такими искажениями эллипс в лемнискату, но если самопересечения запретить, то меньше 4-х --- никак! Теорема о четырёх вершинах овала!

Пусть не эллипс, а какая-нибудь приличная незамкнутая кривая. У лог. спирали --- 0 вершин, у кубической параболы, даже $y=x^3$, --- две, у какой-нибудь другой --- 5. Что-то разумное, количество экстремумов некой приличной функции. Но не 359, и не 999!

А теперь подумаем в обратную сторону. Нам выдают уже искажённые точки (бывшего эллипса, бывшей бидуги, бывшей спирали Ферма/Корню, етц). Нам выдают 1000 точек. 2000 координат ("подков четыре тыщи! счастия они не принесли..."). Мы строим кардиограмму, и получаем свои 999 экстремумов (или мы гладкий кубич. сплайн строим, и наверняка получим кривую с чем-то типа 1517 вершин). Но, подвигав точки в пределах того же вышеупомянутого $\varepsilon$, мы уменьшим к-во вершин=экстремумов_кривизны до четырёх! До нуля! До наименьшего возможного значения.

Таким образом, варьируя 1998 переменных $x_i,y_i$ (первую точку мы зафиксировали), мы ищем все возможные кривые $\Gamma(\Delta x_i ,\Delta y_i)$, на которых реализуется минимальное количество вершин. Нам казалось, что минимум равен 10, но вот нашлось 9, и мы все предыдущие выкинули, и теперь ищем варианты с не более 9!

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

Соображения, позволяющие мне считать найденную область удивительно узкой, а также мысли о том, где бы PAVу отыскать суперЭВМ, я постараюсь привести попозже. Ибо

AD в сообщении #187735 писал(а):

(7) ... Только сейчас спатки пора, потом что-нибудь напишу.

[PAV]

e7e5 в сообщении #199066 писал(а):

На основе этой информации вы можете посчитать кривизну, динамику и.т.п? Или Вам по прежнему нужна некая формула, параметрическое представление и.т.п?

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

[e7e5]

Алексей К. писал(а):

Мои соображения вряд ли конкретно помогут, но я решил их выложить. Быть может, это подскажет "так делать не надо" или наведёт на другие мысли.

Итак. будем искать сглаженную кривую в виде массива $(x_i;y_i)$

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

Значит мне для сглаживания, когда вырисовываю кривую карандашом, нужно смотреть вперед, чтобы кривая плавненькая вышла. Это кажется понятно из опыта?
Этим хочу сказать, что для получения массива точек сглаженной кривой нужно будет брать точки, которые относительно далеко от того места, где генерится текущая пара $(x_i;y_i)$

У Вас такой же результат опыта получается?

[PAV]

e7e5 в сообщении #199443 писал(а):

Этим хочу сказать, что для получения массива точек сглаженной кривой нужно будет брать точки, которые относительно далеко от того места, где генерится текущая пара $(x_i;y_i)$

У Вас такой же результат опыта получается?

В общем-то да. Совсем маленькой окрестностью (типа нескольких точек) обойтись не удастся. Нужно взять столько точек, сколько необходимо, чтобы установить общий "характер движения" и затем уже по этой информации сглаживать.

(я извиняюсь, что так долго не реагирую, сейчас на некоторые другие задачи пришлось переключиться и эта немного отодвинулась)

[e7e5]

PAV в сообщении #201012 писал(а):

В общем-то да. Совсем маленькой окрестностью (типа нескольких точек) обойтись не удастся. Нужно взять столько точек, сколько необходимо, чтобы установить общий "характер движения" и затем уже по этой информации сглаживать.

Для указанного набора точек может попытаться, как то ( как?), понять, а вообще этот набор насколько случаен?

[age]

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

Если неизвестен, то можно 10-12 известными способами регрессий обсчитывать все точки (а не только от желтой до красной) начальной кривой. Из оценок выбирать наибольший $R^2$ и по нему определять вид исходной кривой (вид регрессии). Затем использовать эту регрессию на изучаемом отрезке для точек.

Потом также можно аппроксимировать определенные отрезки кривых между двумя максимумами (экстремумами). Отыскать экстремумы просто. Затем для полученного интервала получить возможные оценки $R^2$. Выбрать наибольшую. Определить вид зависимости. Использовать для изучаемых точек.