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

[PAV]

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

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

Спасибо за ссылку, посмотрю.

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

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

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

Этот вариант. На самом деле кривая нарисована человеком.

[Алексей К.]

PAV писал(а):

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

Чего-то не стыкуется --- пока не понимаю, как соотносятся подобные модели с функцией, график которой опирается на хорду ---

PAV писал(а):

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

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

Именно так.

Варианты: $f(x)=x(1-x)(ax+b)$ (подразумевается фиксированная единичная хорда). Задачка линейная. Но полиномы Вы за что-то не любите.
Штуки типа $f(x;\alpha,\beta,c)=cx^\alpha(1-x)^\beta$ я бы МНКачил линеаризацией и итерациями, найдя как-то первое приближение $(\alpha_0,\beta_0,c_0)$

$$f_1(x;\alpha,\beta,c)=f(x;\alpha_0,\beta_0,c_0)+f'_\alpha(\ldots)\Delta\alpha+f'_\beta(\ldots)\Delta\beta+f'_c(\ldots)\Delta c,$$

далее линейный МНК по дельтам, и $\alpha_1=\alpha_0+\Delta\alpha,\quad \ldots$.

(Добавлено через часок):

PAV писал(а):

Я думал над трехпараметрическим семейством вида $y(x)=cx^\alpha(1-x)^\beta$, где $\alpha>0$ и $\beta>0$. Фактически это один из частных случаев плотности бета-распределения. Но мне не нравится то, что производные в концевых точках равны либо $0$, либо $\infty$, за исключением вырожденного случая $\alpha=\beta=1$. А мне бы хотелось, чтобы производные на концах могли бы принимать произвольные значения.

Прочитал это только сейчас (совпадению буковок не удивляюсь)...

Добавлено спустя 1 час 40 минут 22 секунды:

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

Сейчас мне видится наилучшим с точки зрения содержания следующее 4-х параметрическое семейство. Каждая кривая склеена из двух,

Эта Ваша конструкция напомнила бидугу. Посмотрите, может понравится...

[e7e5]

PAV писал(а):

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

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

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

Ранее вы указали, что "хорошо бы понять, как мозг сглаживает". Не имея опытных данных, боюсь, все ухищрения будут далеки от реальности.
Попробуйте сгенерить 10-15 рисунков с точками. Дайте своим знакомым, с просьбой сгладить точки кривой ( ничего не поясняя). Потом дайте новое задание - на каждом рисунке дать пояснения, почему они так решили сгладить.
Потом эти результаты стоит осмыслить, глядишь новые идеи появятся, как сглаживать.

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

[mserg]

Насколько я понимаю, нужно:
1. Найти точки излома линии
2. Подавить шумы
3. Получить компактное и точное представление линии.

Не вполне ясно, что дано в задаче. Предположим, что задана последовательность точек $<x_k,y_k>$, где $k$ – номер точки в последовательности.

Для обнаружения точек излома линии нужно для каждой точки построить «касательные» «до» и «после» текущей точки. Если угол между касательными больше заданного порога, то имеет место точка излома. Технически можно использовать довольно значительные окрестности «до» и «после» текущей точки, касательные находить методом наименьших квадратов. Вычисление в каждой точке даст функцию угла между касательными «до» и «после» в зависимости от номера точки. Экстремумы и будут точками излома (конец одной плавной линии и начало другой).

Для подавления шума можно воспользоваться аппроксимацией в окрестности данной точки $x_k,y_k$ полиномом 3-ей степени. Т.е. получаем полином в окрестности, находим незашумленные значение в данной точке. Такой метод удаляет шумы практически идеально, форма линии не искажается.

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

Схема без гарантии правильности, так сказать FYI. Есть над чем подумать на краях линии и в окрестностях точек излома, и т.д. Как кажется на первый взгляд, при правильной организации вычислений, затыка по производительности и памяти быть не должно.

[PAV]

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

конструкция напомнила бидугу. Посмотрите, может понравится...

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

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

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

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

[Алексей К.]

PAV писал(а):

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

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

[P.M.D.]

Гораздо проще не строить кривую аналитически, а изменять положения точек в начальной последовательности. Я бы сделал так: Исходные точки нарисованы чёрным. Для i-й точки находим среднюю точку между (i+1) -й и (i -1) -й (обозначена зелёным), потом находим среднюю точку между полученной и i-й (обозначена красным). Такую процедуру повторяем для всех точек кроме крайних. Последовательность из новых точек (красных) является сглаженной, но сохраняет все перегибы исходной.

[PAV]

Подход интересный, спасибо за идею. Я делал что-то похожее, но это технически получше. Единственное, что меня в нем немного смущает, это вот что. Мы сглаживаем точку, опираясь на положение только ее непосредственных соседей. А что если картинка будет такой же, как у Вас (те же линии), только точек больше: строго на линиях расположим по одной-двух-трех дополнительных точек. Тогда это сглаживание получается не сработает. Можно ли эту процедуру подправить так, чтобы она была инвариантна относительно такого преобразования? Дело в том, что у меня есть материалы с разной частотой точек. Поэтому мне не хочется жестко опираться на их количество, а лишь на смещения, которые я считаю "допустимыми для сглаживания", и на какую-нибудь разумную модель.

[Алексей К.]

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

[P.M.D.]

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

[PAV]

mserg в сообщении #198334 писал(а):

Для обнаружения точек излома линии нужно для каждой точки построить «касательные» «до» и «после» текущей точки. Если угол между касательными больше заданного порога, то имеет место точка излома. Технически можно использовать довольно значительные окрестности «до» и «после» текущей точки, касательные находить методом наименьших квадратов. Вычисление в каждой точке даст функцию угла между касательными «до» и «после» в зависимости от номера точки. Экстремумы и будут точками излома (конец одной плавной линии и начало другой).

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

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

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

Так что решение о наличии излома я считаю правильным принимать именно по сопоставлении аппроксимации какой-то моделью, включающей в себя кривые линии, "до" точки, "после" точки и, возможно, объединяя куски "до" и "после".

[mserg]

Когда я писал о касательных, то по умолчанию имелось в виду следующее. Исходная заданная линия - параметрическая. Т.е. например, в первой точке параметр равен 0; во второй точке параметр равен расстоянию от первой точки до второй; значение параметра в третье точке равно значению параметра во второй точке плюс расстояние от второй до третьей точки и т.д. Т.е. исходная линия определяется параметром и имеет вид x=x(t), y=y(t), где t - параметр.
Взяв некоторое количество точек <до> рассматриваемой, можно с помощью МНК сделать аппроксимацию полиномом каждой из координат x и y в отдельности. Исходя из тех требований, которые заданы - это полином 3-ей степени. Производные этих полиномов в рассматриваемой точке дадут касательную. То же самое можно сделать с точками <после> - использовать аппроксимирующие полиномы.

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

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

[PAV]

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

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

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



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

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

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

[ewert]

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

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

[PAV]

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

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

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

$$f(x)=\frac{x^2}{x^2+\alpha}$$

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

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

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