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

[PAV]

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

Добавлено спустя 6 минут 14 секунд:

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

[PAV]

Вот такая вспомогательная задачка возникла в процессе расчета модели. Нужно решить относительно $\alpha$ следующее уравнение:

$$ \frac{\left(\sum y_i x_i^\alpha\right)\left(\sum x_i^\alpha\ln x_i\right)}{\sum x_i^{2\alpha}}=\sum y_i \ln x_i $$

все суммы по $1\le i\le n$, числа $x_i$ и $y_i$ заданы. Видно, что это что-то красивое, нет ли идей, как это можно решить?

Добавлено спустя 29 минут 13 секунд:

Я даже не очень понимаю, будет ли левая часть монотонна по $\alpha$.

(На всякий случай: $0<x_i\le 1$ для всех $x_i$).

Добавлено спустя 59 минут 17 секунд:

Монотонность левой части есть. Точнее, не совсем той, которую я написал, но немного преобразованной. Красиво, это следует из утверждений, которые я нашел в книге Беккенбах Э., Беллман Р. — Неравенства. Там доказывается, что если мы рассмотрим взвешенную сумму

$$ \left(\sum \alpha_ix_i^t\right)^{1/t}, $$

где сумма коэффициентов $\alpha_i$ равна 1, то такая функция монотонно возрастает (неубывает) при $t>0$, а если коэффициенты убрать:

$$ \left(\sum x_i^t\right)^{1/t}, $$

то функция будет монотонно убывать.

Добавлено спустя 17 минут 49 секунд:

Нет, плохо. Не получается. Затык.

[worm2]

Я бы не стал надеяться на какое-то "чудесное" решение этого уравнения. Просто взял бы да провёл несколько численных экспериментов на реальных данных ("тупым перебором" $\alpha$ с каким-то мелким шагом). Весьма вероятно, что для практически важных случаев монотонность всегда будет, и возможно, уравнение легко решается с нужной точностью за пару-тройку итераций метода Ньютона.

[PAV]

Я обошел эту задачу с другой стороны. Сегодня с утра подумал на свежую голову и понял, что совершенно по непонятной причине упустил очевидно простое решение - для приближения серии наблюдений функцией вида $f(x)=cx^\alpha$ перейти к логарифмам и решать обычную задачу линейной регрессии. Затмение какое-то нашло. Так что это простое решение я и попробую применить.

Хотя, если кто-то все-таки придумает какую-нибудь альтернативную модель, подходящую под мои условия, то я ее с интересом рассмотрю.

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

[Алексей К.]

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



(откуда взялась нижняя горизонтальная линия --- я не понял...)
В нижней части картинки имеем 31 точку чистого эллипса с полуосями 100 и 200. Далее вычислена кривизна (ориентированной) окружности, проходящей через каждые 3 соседние точки: $k_i(P_{i-1},P_i,P_{i+1})$. С накопленной длиной ломаной в качестве агрумента получаем красненький график $k(s)$. По сути, мы видим график натурального уравнения четвертинки эллипса.

Затем координаты точек были слегка подпорчены округлением до первого десятичного знака. Видно, как плавный красный график превратился в зелёненькую кардиограмму данного точечного множества (также построенную по 3-точечным кривизнам).

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

Но на рисунке мы всё равно видим вполне приличный эллипс. Искусственно внесённые погрешности порядка тех, что были на картинках PAVа, и их последствия показаны на верхнем фрагменте. Масштаб кардиограммы пришлось уменьшить в 10 раз (видно, что тот же красненький график прилип к оси абсцисс).

(Кстати, нечто подобное я бы получил и в зелёненьком случае, если бы взял 91 точку, т.е. в 3 раза ближе, через $1^\circ$, но с той же ошибкой округления --- до первого десятичного знака).

Вывод --- анализ кардиограмм в Вашей задаче вряд ли поможет.

А если строить окружность не через 3 точки, а через 5 (6, 7, ... 11?) соседних точек, т.е. МНКчить?

А может, кто-нибудь умный придумает что-то типа Fourier-Kurvier--анализа, где в качестве спектра мы увидим конкретные пики-куски такой-то кривизны?
Сложность задачи в том, что надо построить некую кусочно-какую-то модель.

Как реализованы практически и теоретически задачи сглаживания --- я не знаю. И я совсем не помню, что писали об этом Завьялов-Леус-Скороспелов на 91-й странице книги "Сплайны в инженерной геометрии". Поэтому и ссылку эту тоже не предлагаю.

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

[P.M.D.]

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

[Лиля]

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

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

И спользуйте B-Spline они как мне кажеться для вашего случая подходят удивительно хорошо

[e7e5]

PAV писал(а):

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


Характер поведения кривой меняется, причем достаточно резко. Например, идет достаточно прямая линия - затем излом - затем прямая под другим углом. Глаз это видит, человек не станет сглаживать этот излом. А сплайн его уничтожит.

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

Будет странно думать, что человек с карандашом ( художник ) думает о сплайнах. Попробуйте подальше разместить картинку от глаз, деталей будет видно меньше, но при этом плавность перехода остается. А когда летим на самолете и смотрим на дорогу - обочина и ее неровности не столь важны, важно направление. Вот как мозг сглаживает - так и на компьютере сглаживайте. Может стоит взять некое разрешение.

[PAV]

Спасибо всем, кто ответил. Постараюсь вкратце прокомментировать ответы.

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

P.M.D.
честно говоря, не совсем понял, как предлагается определять, где закончить одну аппроксимацию и начать другую. Углы между соседними точками, как видно на картинке, меняются очень резко и это плохой признак. Очень неустойчиво.

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

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

Добавлено спустя 1 минуту 18 секунд:

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

Вот как мозг сглаживает - так и на компьютере сглаживайте.

Мне бы очень хотелось понять, как сглаживает мозг. Это было бы, наверное, идеально. Но пока что я этого не до конца себе представляю. Собственно, я и пытаюсь как-то попробовать имитировать этот процесс.

Добавлено спустя 5 минут 7 секунд:

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

Будет странно думать, что человек с карандашом ( художник ) думает о сплайнах.

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

[e7e5]

PAV писал(а):

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

Вот как мозг сглаживает - так и на компьютере сглаживайте.

Мне бы очень хотелось понять, как сглаживает мозг. Это было бы, наверное, идеально. Но пока что я этого не до конца себе представляю. Собственно, я и пытаюсь как-то попробовать имитировать этот процесс.

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

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

[Алексей К.]

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

...В нижней части картинки имеем 31 точку чистого эллипса с полуосями 100 и 200.
...Затем координаты точек были слегка подпорчены округлением до первого десятичного знака.
...На втором фрагменте, повыше, выполнено округление до ближайшего целого.

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

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

Почти так, только я бы уточнил (и как-то пытался это подчеркнуть в основном тексте): если "сопоставима" --- то с 3-точечным подходом и делать нечего. Если на 1-2 порядка меньше, то можно кое-что выдоить.
Т.е. эти мои кардиограммы --- инструмент очень чувствительный (от допускового контроля пришло).

Добавлено спустя 2 минуты 10 секунд:

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

А если строить окружность не через 3 точки, а через 5 (6, 7, ... 11?) соседних точек, т.е. МНКачить?

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

Поэтому я и пытаюсь аппроксимировать кривую ..., используя достаточно значительное количество подряд идущих точек.

Ага

[PAV]

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

Дать нескольким испытуемым людям набор указанных выше рисунков ( либо сформировать пакет таких рисунков с точками). Попросить сгладить. Набрать базу данных.
Потом для новых рисунков выискивать в базе похожие элементы и сглаживать. При необходимости дообучить программу.

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

Добавлено спустя 8 минут 41 секунду:

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

Но там что-то похоже сложнее, чем мне казалось. Выше я писал, что буду приближать набор точек функцией вида $f(x)=cx^\alpha$, возьму логарифм и применю обычную регрессию. Но это не получается. Во-первых, у меня функция перевернутая, вида $f(x)=c(1-x^\alpha)$. Даже переход к логарифму не сводит задачу к линейной регрессии. Во-вторых, я понял, что у меня реально будут попадаться очень малые значения, даже нули. Логарифмы при этом становятся бесконечными. Даже если нули проигнорировать, то все равно получится, что очень большие значения будут в регрессии давать фактически большой вес. А это по сути неправильно. Так что придется для подбора указанных параметров $c$ и $\alpha$ все равно придумывать какой-то метод, возможно, итерационный. Это будет не так быстро, как мне хотелось бы, но мне уж очень нравится эта модель и хочется все-таки довести ее до готового состояния.

Добавлено спустя 58 секунд:

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

Почти так, только я бы уточнил (и как-то пытался это подчеркнуть в основном тексте): если "сопоставима"

В моем случае явно сопоставима.

[Алексей К.]

На самом деле осталось непрояснённым (или я проглядел?) одно важное обстоятельство:

я всё время имею в виду некую кривую (или дискретное множ.) и решения, инвариантные относительно поворота (так было и с моим эллипсом);

Вы, похоже, имеете в виду график некой функции (хотя не все Ваши примеры склбняют к этой мысли);

(в каждом случае --- отпечаток наших разных профессий )

гибридная ситуация: Вы имеете в виду произвольную кривую, но работая на кусочках, позволяете себе в пределах каждой $i\ldots j-$хорды рассматривать её как график функции.

Прояснить это --- важно (пошёл поискать примеры недавних дискуссий).

Добавлено спустя 2 минуты 4 секунды:

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

Вывод МНК- формулы для окружности на плоскости прост.

[PAV]

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

гибридная ситуация: Вы имеете в виду произвольную кривую, но работая на кусочках, позволяете себе в пределах каждой $i\ldots j-$хорды рассматривать её как график функции.

Именно так.

[Алексей К.]

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

Я имел в виду 2 основных (на мой взгляд) варианта:

(1) Ваша кривая есть график некой функции. $x$ типа время или напряжение или что угодно, $y$ типа деньги, расстояния, ток, или что угодно. Построение должно быть инварантно относительно изменения масштабов любой/обеих осей. Ни о каких поворотах речи нет. Длина хорды, кривизна --- (почти) бессмысленные величины. Привлечение клотоид, окружностных сплайнов --- бессмысленно.

(2) Ваша кривая есть "именно кривая" (пардон за калобур), с геометрической подоплёкой. $x$ и $y$ --- расстояния (например, оцифрованные прибором, списанные с карты местности, вычисленные из требуемого закона движения кулачка, етц). Построение должно быть инварантно относительно гомотетии и поворотов. Накопленная длина хорды --- наиболее естественный параметр. При каких-то условиях может быть оправдано и привлечение клотоидальных, окружностных и других нестандартных сплайнов.