Аппроксимация облака точек цилиндром

[dj_bios]

Всем доброго времени!
Встала задача, для меня, программиста с познаниями в математике на уровне, очевидно, недостаточном, весьма нетривиальная. Собственно есть облако точек, экспериментально полученное с помощью 3D сканирования. Сканировался цилиндр. Необходимо получить уравнение этого цилиндра.
Я попытался сделать следующее:
Задаю цилиндр при помощи осевой прямой (вектор+точка) и радиуса. Расстояние от всех точек цилиндра до прямой = радиус. Далее использую функцию 10ти переменных (где $x_{0i}$, $y_{0i}, $ $z_{0i}$ - i-я точка из облака, $r$ - радиус, $x_1$,$y_1$, $z_1$, $m$, $n$, $p$ - точка и вектор, определяющий осевую прямую), $f(x_0, y_0, z_0, r, x_1,y_1,z_1,m,n,p) =$ сумма по $i$ от ((расстояние от прямой до точки $((x0,y0,z0)-r)^2)$. Минимум этой функции - набор $r$, $x_1$, $y_1$,$z_1$, $m$, $n$, $p$, соответствующий наилучшему приближению (в теории). Дальше нахожу минимум методом COBYLA. И результат - печальный.

Прошу совета, как лучше решить задачу?

ЗЫ Программирую на C#

[realeugene]

Ловите локальный минимум, когда вам интересен глобальный?

[dj_bios]

realeugene в сообщении #1161575 писал(а):

Ловите локальный минимум, когда вам интересен глобальный?

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

[realeugene]

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

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

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

[dj_bios]

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

-- 21.10.2016, 15:05 --

Кстати, мое решение работает плохо еще и потому, что облако точек не покрывает цилиндр со всех сторон, то есть я имею сектор цилиндра.

[realeugene]

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

[levtsn]

Может сперва найти его направление, а потом уже диаметр? Направление оси по проекции можно искать. При виде сверху все точки попадут на одну окружность, кроме тех что на крышках.

[Vince Diesel]

А для такой функции

$f(x_0, y_0, z_0, r, x_1,y_1,z_1,m,n,p) =$ сумма по $i$ от ((расстояние от прямой до точки $(x0,y0,z0)^2-r^2)^2)$.

лучше не станет?

[lovsander]

vince diesel круто сказал)) у меня зародись чувство что оцениваемая функция некорректна. Возведение в квадрат как я заметил, уменьшает влияние мелких вкладов, и именно крупные вклады играют роль при суммировании.

А почему не оценивать расстояние от каждой точки облака до поверхности цилиндра? Например, выразив XY через угол в полярных координатах. Берем точку облака, получаем ее угол, и подставляем этот угол в формулу. Координата Высоты при этом тоже зависит от чего-то, кажется от наклона оси, и также учитывается в оценке расстояния между точками.

Собираюсь решать сходную задачу, если есть опыт у кого, прошу поделиться