Гомографическое вычисление с использованием алгоритма Левенберга Марквардта

Код openCV открыт, поэтому проверьте модули. шпаргалка для openCV имеется формулировка Левенберга Марквардта, см. столбец 3, стр. 1. Вы можете использовать grep для поиска этой формулировки или только для названия метода:

grep -rnw . -e "Levenberg"

Например, вы можете найти много файлов levmar * .c в папке modules / legacy. Причина использования LMA после решения системы линейных уравнений с помощью RANSAC заключается в том, что прежние линейные уравнения оптимизируют неправильную метрику — алгебраическую ошибку в параметрах гомографии. Лучшей метрикой является сумма квадратов невязки с точки зрения координат точек. В этой метрике решение является нелинейным и должно быть найдено итеративно. Линейное решение используется для инициализации нелинейного алгоритма и увеличения его шансов сходиться к глобальным минимумам.

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

1. Оптимизация всегда может быть приведена как минимизация затрат или остатков

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

   пары [T +-] = пары [т] -k * стоимость», где t-итерация, k-шаг и ‘обозначает градиент или производную w.r.t. параметры

3. Пока все хорошо, но в некоторых случаях (представьте функцию стоимости, которая похожа на трубу для сноуборда), когда вы идете вдоль градиента, вы заставите вас промахнуться и зигзагообразно переместиться с одной стороны долины на другую, в то же время только медленно снижаясь (к общему минимуму) , Решение — используйте лучшее приближение функции (разложение Тейлора до второй производной), чтобы прийти к этому

   param [t + 1] = param [t] — (k / cost ») * cost ‘, где » — вторая производная

Интуитивно быстрая функция означает большую вторую производную, поэтому мы замедляем сходимость, уменьшая наш шаг (делив его на большое число), и наоборот.
4. Для квадратичной ошибки, которая часто представляет собой сумму квадратов невязок или некоторых расстояний, мы можем придумать аппроксимацию второй производной как продукта первых производных (называемых якобианами, которые показаны как J, что обычно является матрицей); вторая производная или гессиан = J^TJ, так оптимизация выглядит

парам [т + 1] = парам [т] — (Дж^TJ),^-1 *Стоимость’ — называется Гаусс-Ньютон

Здесь мы опускаем k как шаг для простоты; Сравните эту и предыдущие формулы, мы почти на месте! Также обратите внимание, что в википедии и других сайтах вы можете увидеть, что вместо k они используют остаточный yi-f (x, param), но вы можете пока игнорировать его. Идите дальше, только если вы знакомы с последней формулировкой.
5. Вот идет Левенберг и говорит — это здорово, но может быть нестабильно. Мы взяли слишком много с этими вторыми производными, и было бы неплохо сбросить их и сделать вещи похожими на первые производные, как и раньше. Для этого мы добавляем демпинг-фактор, который может сделать оптимизацию похожей на

парам [т + 1] = парам [т] — (Дж^TJ + лямбда * я)^-1 *Стоимость’, где я — единичная матрица, а лямбда — скаляр

Обратите внимание, что когда лямбда велика, вы можете отказаться от J^TJ и вы остались со стандартным градиентным спуском. Они делают это, когда сходимость замедляется, в противном случае они используют маленькую лямбду, что делает алгоритм более похожим на Гаусса-Ньютона. Обратите внимание, что J = d_z / d_param, стоимость ’= d_f / d_param и f = z^T* г

Вот идет Марквардт и говорит: здорово, но мне нравится, что наш градиентный спуск идет быстрее — для маленькой диагонали (J^TJ) Я бы хотел больший шаг, отсюда и окончательная формула, в которой мы делим маленькие диагональные элементы, что приводит к более быстрой сходимости при медленном градиенте:

парам [т + 1] = парам [т] — (Дж^TJ + лямбда * диагональ (J^TJ))^-1 *Стоимость’

Вот краткая сводка с использованием аналогии с горнолыжным спуском, где мы показываем выражение для изменения параметра param [t + 1] -param [t]:
1. Градиент J направлен вверх, но вы хотите спуститься на лыжах, поэтому идите против градиента -kJ;
2. Если зигзаг в «снежной трубе» движется ступеньками, обратными второй производной (H); надеюсь, вы пойдете быстрее прямо вниз: -H^-1J
3. Приближаем вторую производную с произведением первых производных — (J^TJ),^-1J;
4. Дамп, если это слишком много, и вернуться к первой производной — (J^TJ + лямбдаЯ)^-1 J;
5. не хотите застрять на ровном склоне? масштабируйте свой шаг обратно до диагонали приближенного гессиана: — (J^TJ + лямбдаDiag (Дж^TJ))^-1 J

Это большая загадка, почему все это работает, так как моя интуиция через некоторое время сдается. Может быть, сейчас самое время взглянуть на это с философской точки зрения и применить принцип бритвы Оккама — чем меньше мы предполагаем, тем лучше у нас, но если предположить, что слишком мало, мы можем не зайти слишком далеко. Все, что мы пытались сделать, — это предсказать (предположить) глобальное поведение функции, глядя на нее локально (представляя, как женятся после того, как провели вместе 1 неделю). Использование гессиана подобно тому, как иметь больше предположений с точки зрения его многочисленных параметров, в отличие от более консервативного якобиана, который имеет несколько параметров (предположений). Наконец, мы можем хотеть быть гибкими в том, чтобы быть либо консервативными, либо рискованными, и это то, чего пытаются достичь методы Левенберга-Марквардта.