Сплайны и модель двумерной поверхности
От: Khimik  
Дата: 25.03.19 13:18
Оценка: 4 (1)
Я пишу разные алгоритмы, помогите разобраться.
Есть двумерная карта (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-сплайном), но в Вики вроде нет по ним статьи. А я вообще запутался даже с самим простым вариантом этой задачи – элементарная линейная интерполяция.

Интерполяция – вещь вроде понятная. На рисунках красная линия – это собственно линейная интерполяция. Для одномерной задачи между двумя точками просто проводится отрезок. Можно подумать, что в двумерной задаче можно провести плоскость в каждом квадрате, на который разбито пространство, но вот нет: плоскость описывается тремя точками, а на границах квадрата есть четыре точки.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re: Сплайны и модель двумерной поверхности
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 25.03.19 13:24
Оценка:
Здравствуйте, Khimik, Вы писали:

K>Я пишу разные алгоритмы, помогите разобраться.


А что надо получить-то? Проблема поставлена? Возможно, что полиномы Чебышёва будут оптимальным вариантом.
Re[2]: Сплайны и модель двумерной поверхности
От: Khimik  
Дата: 25.03.19 14:21
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>Здравствуйте, Khimik, Вы писали:


K>>Я пишу разные алгоритмы, помогите разобраться.


N>А что надо получить-то? Проблема поставлена? Возможно, что полиномы Чебышёва будут оптимальным вариантом.


Есть например такая задача. Имеется набор точек с данными по глубине водоёма (эти данные получены на эхолотах). Нужно построить модель дна и отбраковать выпадающие точки. Точки могут выпадать по разным причинам, например лодка прыгает на воде, или весь набор точек (трек) имеет систематическую ошибку, поскольку когда эти точки замерялись, уровень воды в водоёме отличался от обычного.
Соответственно надо построить модель дна, например через би-сплайны, далее найти точки которые сильно выпадают из этой модели, выбросить их, пересчитать модель и так далее пока выпадающие точки не перестанут обнаруживаться.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re: Сплайны и модель двумерной поверхности
От: VsevolodC Россия  
Дата: 25.03.19 14:32
Оценка: 2 (1)
Здравствуйте, Khimik, Вы писали:

K>Интерполяция – вещь вроде понятная. На рисунках красная линия – это собственно линейная интерполяция. Для одномерной задачи между двумя точками просто проводится отрезок. Можно подумать, что в двумерной задаче можно провести плоскость в каждом квадрате, на который разбито пространство, но вот нет: плоскость описывается тремя точками, а на границах квадрата есть четыре точки.


Для интерполяции плоскостью, конечно, надо разбивать на треугольники.
Вот пример для построения линий уровня: алгоритм conrec.
Двумерный сплайн получается последовательным построением двух одномерных, по X и по Y.
Re[2]: Сплайны и модель двумерной поверхности
От: Khimik  
Дата: 25.03.19 14:42
Оценка:
VC>Для интерполяции плоскостью, конечно, надо разбивать на треугольники.

В самом деле, элементарно.

VC>Вот пример для построения линий уровня: алгоритм conrec.


VC>Двумерный сплайн получается последовательным построением двух одномерных, по X и по Y.


А тут пока не понял. Какой участок пространства описывает каждый би-сплайн — треугольник или квадрат7
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[3]: Сплайны и модель двумерной поверхности
От: VsevolodC Россия  
Дата: 25.03.19 14:57
Оценка:
Здравствуйте, Khimik, Вы писали:


VC>>Для интерполяции плоскостью, конечно, надо разбивать на треугольники.


K>В самом деле, элементарно.


VC>>Вот пример для построения линий уровня: алгоритм conrec.


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

VC>>Двумерный сплайн получается последовательным построением двух одномерных, по X и по Y.


K>А тут пока не понял. Какой участок пространства описывает каждый би-сплайн — треугольник или квадрат7


вообще говоря, прямоугольник, если шаги по X и Y разные
Re: Сплайны и модель двумерной поверхности
От: De-Bill  
Дата: 26.03.19 02:43
Оценка: 2 (1)
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

С реализацией некоторых моментов тоже могу подсказать, но только на питоне.
Отредактировано 26.03.2019 4:04 De-Bill . Предыдущая версия . Еще …
Отредактировано 26.03.2019 2:46 De-Bill . Предыдущая версия .
Re[2]: Сплайны и модель двумерной поверхности
От: Khimik  
Дата: 26.03.19 10:21
Оценка:
K>>Может быть, нужно ещё минимизировать интеграл от квадрата второй производной всей функции?

DB>Есть и такой подход. Это smoothing spline. Проблема предыдущего подхода — выбор узловых точек. Не совсем понятно, как и где их расставлять. Подход с интегралом — расставляем точки во всех уникальных значениях x (которые у тебя есть), а чтобы линия не сильно виляла, добавляем регуляризацию: минимизируем квадрат ошибки плюс интеграл второй производной, помноженный на какой-то численный параметр. Для одномерного случая делается несложно, но муторно. Для двухмерного, наверное, всё гораздо сложнее.


Я помню, как раз это и делал: только у меня функция задавалась не сплайнами, а банальным набором точек.
Как вы думаете, такой подход (минимизация суммарного интеграла квадрата второй производной, добавляемого к суммарному квадрату ошибки с каким-то коэффициентом) методически самый правильный? Я уже писал, что у меня задача — создание модели дна водоёма, построенной по набору измерений с эхолота.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re[3]: Сплайны и модель двумерной поверхности
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 26.03.19 10:52
Оценка:
Здравствуйте, Khimik, Вы писали:

K>Есть например такая задача. Имеется набор точек с данными по глубине водоёма (эти данные получены на эхолотах). Нужно построить модель дна и отбраковать выпадающие точки. Точки могут выпадать по разным причинам, например лодка прыгает на воде, или весь набор точек (трек) имеет систематическую ошибку, поскольку когда эти точки замерялись, уровень воды в водоёме отличался от обычного.

K>Соответственно надо построить модель дна, например через би-сплайны, далее найти точки которые сильно выпадают из этой модели, выбросить их, пересчитать модель и так далее пока выпадающие точки не перестанут обнаруживаться.

1. Казалось бы, почему не изучить, чем пользуются в отрасли и описано? Можно найти готовые библиотеки с открытыми исходниками и посмотреть, благо всевозможных ГИС систем с реализацией полно. Кажется, что с самодельными сплайнами изобретается сферический конь в вакууме, веь у формирования земной поверхности и дна есть свои особенности, это не абстрактная поверхность.

2. Если говорить не просто о решении задачи, но и о скорости с отображением, то не проще произвести триангуляцию, посчитать нормали и отправить в OpenGL или DirectX, чтобы оно само сделало тебе поверхность?
Re[3]: Сплайны и модель двумерной поверхности
От: De-Bill  
Дата: 26.03.19 10:58
Оценка:
K>Как вы думаете, такой подход (минимизация суммарного интеграла квадрата второй производной, добавляемого к суммарному квадрату ошибки с каким-то коэффициентом) методически самый правильный? Я уже писал, что у меня задача — создание модели дна водоёма, построенной по набору измерений с эхолота.

Честно говоря, не знаю. Лучше начать с поиска релевантных статей по теме. Наверняка кто-то уже делал подобное. Типа
https://core.ac.uk/download/pdf/54849232.pdf
https://link.springer.com/article/10.1007/s00343-009-0117-9
Re[3]: Сплайны и модель двумерной поверхности
От: ylem  
Дата: 27.03.19 23:13
Оценка:
K> Я уже писал, что у меня задача — создание модели дна водоёма, построенной по набору измерений с эхолота.

Может вам триангуляции хватит?
Re: Сплайны и модель двумерной поверхности
От: Bjorn Skalpe Земля  
Дата: 28.03.19 20:53
Оценка:
Ты решаешь задачу восстановления данных (интерполяции), зная набор точек — т.е. просто нужно провести через него (набор) гладкую кривую... либо интерполируя квадратичным или кубическим сплайном.
Со сплайнами все просто: любую гладкую функцию можно разложить в степенной ряд. Чем больше членов ряда, тем более точно функция описывается. Можно разложить в линейный ряд, т.е. соединить прямыми. Можно разложить в квадратичный, т.е. описать параболами, но в точках соединения нужно что бы был плавный переход. Соответственно направление параболы в точке описывается производной в точке. Посчитать производную легко как разницу между двумя точками приближенно как разница по y к разнице по x. Можно описать кубическим сплайном, т.е. нужно знать и первую и вторую производную. Для второй производной нужно уже больше точек... На этом все и строится...

Двух, трех и N мерность тут уже фигня. Так как производная в точке есть сумма частных производных по каждому из направлении.
Отредактировано 02.04.2019 5:34 Bjorn Skalpe . Предыдущая версия . Еще …
Отредактировано 28.03.2019 20:55 Bjorn Skalpe . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.