Я пишу разные алгоритмы, помогите разобраться.
Есть двумерная карта (x,y и z — глубина), точнее набор точек, надо описать её некой моделью. Проще всего, наверно, построить двумерный полином:
Z=a+bx+cx^2+dx^3+…+gy+hy^2+iy^3+...
Имеем набор коэффициентов a,b,c…,g,h… Их можно подогнать для минимизации среднекрадратичного отличия от исходных значений z каждой точки и рассчитанных согласно модели. Эта задача, как я понял, достаточно простая: мы знаем что в минимуме производная МНК-функционала (сумма квадратов различий исходных данных и рассчитанных) по каждому оптимизируемому коэффициенту равна нулю.
Правда я уже путаюсь, не меняется ли картина при переходе от одномерной модели к двумерной (для одномерной я давно уже делал все эти преобразования, надо найти старый код и вспомнить).
Я думаю, в целом этот подход не особо подходящий, поскольку полином обладает таким свойством – он часто петляет вверх-вниз, особенно на краях функции. Вот пример:
Более правильно, как я понимаю, использовать сплайны: функция разбивается на отдельные участки, каждый описывается степенной функцией, например y=a+bx+cx^2+dx^3.
Вот здесь проводятся сплайны третьей степени между точками (это не аппроксимация а интерполяция):
Хотя я сам написал этот код, я его не очень понимаю. Формулы были взяты из книги “Численные методы” (автора не помню). Хочу понять общий смысл этих формул.
Предположим, у нас есть 6 эвкидистантных точек, которые надо интерполировать сплайном. Это значит что у нас 5 интервалов, на каждой из которых проведён свой сплайн.
Мне понятна эта задача, если степень сплайна равна двум: y=a+bx+cx^2. Значит в данном случае мы имеем 5*3=15 коэффициентов, которые надо найти. В каждом интервале мы знаем два значения сплайна (слева и справа), это уже 5*2=10 уравнений. Ещё мы знаем, что для четырёх граничных точек первые производные сплайна слева и сплайна справа совпадают, соответственно имеем ещё 4 уравнения. Чтобы довести число уравнения до числа коэффициентов (15), нужно добавить ещё одно, например такое: для самого левого сплайна первая производная в его левой границе равна производной в правой границе. Действительно, ведь если мы имеем всего 2 точки и один интервал, то сплайн второй степени можно провести бесконечным числом способов, т.е. надо ещё добавить какое-то условие.
В моей же программе, в которой взяты формулы из книги “Численные методы”, сплайн не второй, а третьей степени. Значит, коэффициентов, которые нужно найти, в 4/3 раза больше, т.е. надо добавить ещё уравнений. Я тут не очень понимаю – каких именно? Может быть, нужно ещё минимизировать интеграл от квадрата второй производной всей функции?
А когда я буду переходить от одномерной задачи к двумерной, тут вообще получается тёмный лес. Кажется есть “би-сплайны” которыми надо аппроксимировать данные (не путать с B-сплайном), но в Вики вроде нет по ним статьи. А я вообще запутался даже с самим простым вариантом этой задачи – элементарная линейная интерполяция.
Интерполяция – вещь вроде понятная. На рисунках красная линия – это собственно линейная интерполяция. Для одномерной задачи между двумя точками просто проводится отрезок. Можно подумать, что в двумерной задаче можно провести плоскость в каждом квадрате, на который разбито пространство, но вот нет: плоскость описывается тремя точками, а на границах квадрата есть четыре точки.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, Khimik, Вы писали:
K>>Я пишу разные алгоритмы, помогите разобраться.
N>А что надо получить-то? Проблема поставлена? Возможно, что полиномы Чебышёва будут оптимальным вариантом.
Есть например такая задача. Имеется набор точек с данными по глубине водоёма (эти данные получены на эхолотах). Нужно построить модель дна и отбраковать выпадающие точки. Точки могут выпадать по разным причинам, например лодка прыгает на воде, или весь набор точек (трек) имеет систематическую ошибку, поскольку когда эти точки замерялись, уровень воды в водоёме отличался от обычного.
Соответственно надо построить модель дна, например через би-сплайны, далее найти точки которые сильно выпадают из этой модели, выбросить их, пересчитать модель и так далее пока выпадающие точки не перестанут обнаруживаться.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>Интерполяция – вещь вроде понятная. На рисунках красная линия – это собственно линейная интерполяция. Для одномерной задачи между двумя точками просто проводится отрезок. Можно подумать, что в двумерной задаче можно провести плоскость в каждом квадрате, на который разбито пространство, но вот нет: плоскость описывается тремя точками, а на границах квадрата есть четыре точки.
Для интерполяции плоскостью, конечно, надо разбивать на треугольники.
Вот пример для построения линий уровня: алгоритм conrec.
Двумерный сплайн получается последовательным построением двух одномерных, по X и по Y.
VC>Для интерполяции плоскостью, конечно, надо разбивать на треугольники.
В самом деле, элементарно.
VC>Вот пример для построения линий уровня: алгоритм conrec.
VC>Двумерный сплайн получается последовательным построением двух одномерных, по X и по Y.
А тут пока не понял. Какой участок пространства описывает каждый би-сплайн — треугольник или квадрат7
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
VC>>Для интерполяции плоскостью, конечно, надо разбивать на треугольники.
K>В самом деле, элементарно.
VC>>Вот пример для построения линий уровня: алгоритм conrec.
по этой ссылке как раз от переход прямоугольников к треугольникам
VC>>Двумерный сплайн получается последовательным построением двух одномерных, по X и по Y.
K>А тут пока не понял. Какой участок пространства описывает каждый би-сплайн — треугольник или квадрат7
вообще говоря, прямоугольник, если шаги по X и Y разные
K>Имеем набор коэффициентов a,b,c…,g,h… Их можно подогнать для минимизации среднекрадратичного отличия от исходных значений z каждой точки и рассчитанных согласно модели. Эта задача, как я понял, достаточно простая: мы знаем что в минимуме производная МНК-функционала (сумма квадратов различий исходных данных и рассчитанных) по каждому оптимизируемому коэффициенту равна нулю.
Это линейная в параметрах модель и имеет простое решение в матрицах (если матрица full column rank). Единственное, для твоего случая такой подход не работает. Но в нём есть один полезный момент: использование техники basis expansion — входной вектор (x, y) расширяется до (1, x, y, x^2, y^2,...). Сплайны также используют basis expansion, только более навороченный.
K>В моей же программе, в которой взяты формулы из книги “Численные методы”, сплайн не второй, а третьей степени. Значит, коэффициентов, которые нужно найти, в 4/3 раза больше, т.е. надо добавить ещё уравнений. Я тут не очень понимаю – каких именно?
Лучше почитать в литературе (гугли по Natural Cubic Spline и B-spline), но, насколько я помню, ограничения на узлы для кубических сплайнов: равенство значений, равенство первой производной, равенство второй производной (три уравнений на узел), узлов на 1 меньше, чем регионов, 4 параметра на регион. Плюс в Natural Cubic Spline есть ограничение на поведение сплайна за границами крайних узлов (линейное). Но всё это не сильно важно. Важно, что как и в твоём варианте, это basis expansion. Ты входной вектор (x) в одномерном варианте расширяешь до вектора (1, x, h1(x), h2(x), ...). Далее получается линейная в параметрах модель.
K>Может быть, нужно ещё минимизировать интеграл от квадрата второй производной всей функции?
Есть и такой подход. Это smoothing spline. Проблема предыдущего подхода — выбор узловых точек. Не совсем понятно, как и где их расставлять. Подход с интегралом — расставляем точки во всех уникальных значениях x (которые у тебя есть), а чтобы линия не сильно виляла, добавляем регуляризацию: минимизируем квадрат ошибки плюс интеграл второй производной, помноженный на какой-то численный параметр. Для одномерного случая делается несложно, но муторно. Для двухмерного, наверное, всё гораздо сложнее.
K>А когда я буду переходить от одномерной задачи к двумерной, тут вообще получается тёмный лес.
Для многомерных сплайнов есть несколько подходов:
1. Basis expansion без взаимодействия (x, y) -> (1, x, h1(x), h2(x), ..., y, n1(y), n2(y), ...)
2. Basis expansion с тензорным произведением (x, y) -> (1, x, h1(x), h2(x), ..., y, n1(y), n2(y), ..., h1(x)*n1(y), ... всевозможные произведения)
Здесь также получается линейная модель с кучей параметров.
3. Thin-plate spline: с регуляризацией, например, в виде интеграла квадрата второй производной.
Вообще, не уверен, что чем-то тебе помог, гугли по ключевым словам:
1. Linear regression.
2. Linear regression with basis expansion
3. Linear regression with regularization
4. Natural cubic spline
5. B-Spline
6. Multidimensional spline
7. Thin-plate spline
С реализацией некоторых моментов тоже могу подсказать, но только на питоне.
K>>Может быть, нужно ещё минимизировать интеграл от квадрата второй производной всей функции?
DB>Есть и такой подход. Это smoothing spline. Проблема предыдущего подхода — выбор узловых точек. Не совсем понятно, как и где их расставлять. Подход с интегралом — расставляем точки во всех уникальных значениях x (которые у тебя есть), а чтобы линия не сильно виляла, добавляем регуляризацию: минимизируем квадрат ошибки плюс интеграл второй производной, помноженный на какой-то численный параметр. Для одномерного случая делается несложно, но муторно. Для двухмерного, наверное, всё гораздо сложнее.
Я помню, как раз это и делал: только у меня функция задавалась не сплайнами, а банальным набором точек.
Как вы думаете, такой подход (минимизация суммарного интеграла квадрата второй производной, добавляемого к суммарному квадрату ошибки с каким-то коэффициентом) методически самый правильный? Я уже писал, что у меня задача — создание модели дна водоёма, построенной по набору измерений с эхолота.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>Есть например такая задача. Имеется набор точек с данными по глубине водоёма (эти данные получены на эхолотах). Нужно построить модель дна и отбраковать выпадающие точки. Точки могут выпадать по разным причинам, например лодка прыгает на воде, или весь набор точек (трек) имеет систематическую ошибку, поскольку когда эти точки замерялись, уровень воды в водоёме отличался от обычного. K>Соответственно надо построить модель дна, например через би-сплайны, далее найти точки которые сильно выпадают из этой модели, выбросить их, пересчитать модель и так далее пока выпадающие точки не перестанут обнаруживаться.
1. Казалось бы, почему не изучить, чем пользуются в отрасли и описано? Можно найти готовые библиотеки с открытыми исходниками и посмотреть, благо всевозможных ГИС систем с реализацией полно. Кажется, что с самодельными сплайнами изобретается сферический конь в вакууме, веь у формирования земной поверхности и дна есть свои особенности, это не абстрактная поверхность.
2. Если говорить не просто о решении задачи, но и о скорости с отображением, то не проще произвести триангуляцию, посчитать нормали и отправить в OpenGL или DirectX, чтобы оно само сделало тебе поверхность?
K>Как вы думаете, такой подход (минимизация суммарного интеграла квадрата второй производной, добавляемого к суммарному квадрату ошибки с каким-то коэффициентом) методически самый правильный? Я уже писал, что у меня задача — создание модели дна водоёма, построенной по набору измерений с эхолота.
Ты решаешь задачу восстановления данных (интерполяции), зная набор точек — т.е. просто нужно провести через него (набор) гладкую кривую... либо интерполируя квадратичным или кубическим сплайном.
Со сплайнами все просто: любую гладкую функцию можно разложить в степенной ряд. Чем больше членов ряда, тем более точно функция описывается. Можно разложить в линейный ряд, т.е. соединить прямыми. Можно разложить в квадратичный, т.е. описать параболами, но в точках соединения нужно что бы был плавный переход. Соответственно направление параболы в точке описывается производной в точке. Посчитать производную легко как разницу между двумя точками приближенно как разница по y к разнице по x. Можно описать кубическим сплайном, т.е. нужно знать и первую и вторую производную. Для второй производной нужно уже больше точек... На этом все и строится...
Двух, трех и N мерность тут уже фигня. Так как производная в точке есть сумма частных производных по каждому из направлении.