Численные рецепты / многомерный поиск корней (с использованием тритона): как минимизировать максимальную ошибку

Question

Этот вопрос относится к книге «Числовые рецепты на С ++», поэтому он будет зарезервирован для людей, которые немного о нем знают, а также о многомерной оптимизации.

Я пишу программу, которая должна искать многомерный корень, и для ее решения я использую многомерный метод поиска корня ньютона, а именно "newt" процедура.

Для тех, кто интересуется деталями, я пытаюсь подогнать деформируемую 3D-модель к стереоскопическому изображению объекта на основе нескольких характерных точек (характерных точек, которые видны двумя камерами).

Для этого я использую процедуру newt со следующим:

• 11 Входные параметры: Моя деформируемая модель может быть смоделирована с 11 параметрами (составленными из 5 геометрических параметров и 6 степеней свободы для местоположения трехмерного объекта):
• 14 Выходные параметры , для которых мне нужно найти корень: на основе характерных точек, которые определены камерой, и с учетом набора «входных параметров», я могу рассчитать набор расстояний между характерные точки, видимые камерой, и их теоретическое расположение. У меня есть 7 из этих точек, так что я получаю 14 параметров (7 расстояний, умноженных на 2, поскольку я рассчитываю расстояния на обеих камерах)

Моя проблема в том, что у меня больше выходных параметров (14), чем входных параметров (11): всякий раз, когда я вызываю «newt», алгоритм всегда сходится, однако он найдет решение, которое почти идеально минимизирует 11 первых выходных параметров, но это имеет много ошибок по 3 оставшимся параметрам.

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

Я уже попробовал подходы, описанные ниже:

1. Попробуйте объединить 14 выходных параметров в 11 параметров (для Например, вы берете среднее значение некоторых расстояний, вместо того, чтобы использовать оба расстояния). Однако я не на 100% удовлетворен этим подходом
2. Смешайте несколько решений по следующему принципу:
   • Вызовите mnewt и запомните найденный корень
   • Изменить порядок 14 выходных параметров
   • Повторный вызов mnewt и запоминание найденного корня
   • Вычислить решение - среднее из двух найденных корней

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

Answer 1

Вы пытаетесь минимизировать F(x), решая f(x)=0, где x - это m-мерный вектор, а f отображает это в n-мерный вектор. Ваша проблема оптимизации недоопределена , если m < n (в вашем случае 11 <14). </p>

Для таких систем общий способ их решения состоит в минимизации вектора норма на x. Вы можете сделать это, свернув систему x^T A x + c f(x)^T f(x) относительно x и множитель Лагранжа c. Без дополнительной информации вы можете принять A за матрицу тождеств nxn . Это найдет x, который решает f(x)=0, имея наименьшую норму.

Подробнее о том, как сделать это с помощью метода Ньютона, см., Например, это бумага .