Главная > Интеллектуальные системы > Зрение роботов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

17.3. Поступательное движение

В этом разделе мы рассмотрим случай, когда движение камеры имеет чисто поступательный характер. Как и раньше, пусть скорость камеры. Тогда выполняются следующие уравнения:

17.3.1. Подобные поверхности и подобные движения

Мы хотим показать, что если два чисто поступательных движения порождают один и тот же оптический поток, то две поверхности и два движения камеры подобны. Пусть — две поверхности, а определяют два различных движения камеры, так что и а также порождают один и тот же оптический поток, т. е.

Исключая из этих уравнений и получим выражение . Перепишем его в виде или

Поскольку мы предположили, что и , а также порождают один и тот же оптический поток, то это уравнение должно выполняться для всех х и у. Отсюда следует:

Перепишем эти уравнения в виде отношения из которого следует, что подобно Ясно, что масштабный множитель между и (или, что то же, между и ) нельзя определить из оптического потока, сколько бы точек не было известно. Это означает, что движение камеры восстанавливается однозначно с точностью до масштабного множителя.

17.3.2. Формулировка метода наименьших квадратов

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

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

В дальнейшем будем предполагать, что плоскость изображения ограничена прямоугольником . Тот же метод применим к изображениям любой другой формы. (Фактически в случае, когда объекты внешнего мира могут перемещаться относительно друг друга, необходимо было бы использовать области изображения, относящиеся к отдельным объектам.) Обычно существует нижняя граница расстояния между объектом и камерой, так что мы можем считать отношение ограниченной функцией. Кроме того, большинство сцен состоит из некоторого числа объектов с непрерывными поверхностями, так что глубина непрерывна «почти везде». Предположим, что множество точек, где терпит разрыв, имеет меру нуль. (Это означает, что равен нулю интеграл от характеристической функции, которая равна единице в этих точках и нулю во всех других). Это условие гарантирует нам, что можно выполнять интегрирование всегда, когда это понадобится.

Зададимся целью минимизировать выражение

В этом случае мы определяем наименьшее отклонение в смысле нормы которое описывается формулой

Метод наименьших квадратов состоит из следующих шагов: вначале мы определяем величину которая минимизирует подынтегральное выражение в каждой точке а затем определяем величины и которые минимизируют интеграл.

Удобно определить Заметим теперь, что поток, задаваемый величинами будет просто определяться отношениями Тогда мы можем переписать предыдущий интеграл в виде

Переходим к первому шагу минимизации. Дифференцируя подынтегральное выражение по и приравнивая результат нулю, получим

Отсюда можно найти

Это уравнение, между прочим, накладывает ограничение на и так как должно быть положительным. Особой пользы для нас в этом нет, хотя и помогает в выборе между двумя возможными противоположными движениями. Теперь имеем

Предыдущий интеграл можно теперь переписать в виде

Ясно, что однородное масштабирование и не изменит величины интеграла. Это отражает тот факт, что мы можем определить параметры движения лишь с точностью до постоянного множителя.

Прежде чем перейти ко второму шагу, дадим геометрическую интерпретацию сделанного до сих пор. Предположим, что заданы параметры движения и . В некоторой точке оптический поток зависит не только от параметров движения, но и от величины функции в данной точке. Однако направление не зависит от Точка должна лежать на прямой в плоскости определяемой уравнением Пусть результат измерения оптического потока в точке будет , а ближайшей к нему точкой на прямой будет . Это соответствует некоторому Остаточная ошибка — это расстояние от точки до прямой Квадрат этого расстояния входит в рассматриваемый интеграл в качестве подынтегрального выражения.

На втором шаге мы дифференцируем интеграл по и и приравниваем нулю полученные выражения:

Введем сокращение

тогда уравнения можно переписать в виде

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

17.3.3. Использование других норм

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

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

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

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

оптического потока. Заметим еще, что, если мы хотим на самом деле вычислить минимум в смысле нормы мы можем использовать результаты минимизации по в качестве начального приближения численного процесса.

Используем теперь наш метод наименьших квадратов для случая, когда в качестве нормы выбрана Сначала мы определяем путем дифференцирования подынтегрального выражения по и приравнивания результата нулю. Получим

откуда следует, что Теперь мы хотим минимизировать

Если мы обозначим этот интеграл через то, поскольку имеем

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

Очевидно, что эта система имеет ненулевое решение тогда и только тогда, когда определитель системы равен нулю. Тогда три уравнения линейно зависимы и определяется с точностью до постоянного множителя. Однако в общем случае, поскольку данные содержат шум, функцию нельзя сделать равной нулю для ненулевой поступательной скорости, и таким образом, будет единственным решением. Чтобы показать это другим способом, заметим, что функция имеет вид где к — константа. Ясно, что достигает своего минимума при

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

ничную длину, то минимум функции это наименьшее собственное значение матрицы то значение при котором достигает минимума, можно найти как собственный вектор, соответствующий этому собственному значению. Это следует из того, что является квадратичной формой, которую можно записать в виде Заметим, что является положительной полуопределенной эрмитовой матрицей, поскольку . (Последние три неравенства следуют из неравенства Коши — Шварца.) Следовательно, все собственные значения являются действительными и неотрицательными; они находятся как корни многочлена третьей степени:

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

Заметим, что является собственным значением тогда и только тогда, когда вырождена, т. е. свободный член полинома равен нулю. Действительно, если детерминант равен нулю, мы можем найти поступательную скорость которая обращает функцию в нуль. Как следует из теоремы математического анализа, это может случиться, только если оптический поток правильно, без ошибок, определен почти всюду, т. е. когда множество точек, в которых нарушается правильность, имеет меру нуль. Эта теорема утверждает, что если интеграл от квадрата ограниченной непрерывной функции равен нулю, то равна нулю и сама функция. Следовательно, ошибки могут быть только в точках, в которых оптический поток терпит разрыв, и это как раз те точки, где нарушается непрерывность функции определяющей поверхность. (Именно в этих местах существующие методы определения оптического потока дают большие ошибки.)

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

случиться только при нулевом оптическом потоке. Скорость при этом тоже нулевая.

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

Так как является собственным значением, уравнения линейно зависимы. Временно допустим, что все собственные значения различны, т. е. ранг матрицы равен двум, где I — матрица тождественного преобразования. Тогда мы можем использовать любую пару уравнений и выразить и V через Сделать это можно тремя способами. Для получения симметричного ответа мы сложим все три результата:

Заметим, что значение X! должно быть небольшим при хороших данных, и мы могли бы просто аппроксимировать точное решение, используя эти уравнения при (Тогда, естественно, нет необходимости определять собственные значения.) В любом случае результирующую скорость теперь можно нормализовать, так чтобы ее абсолютная величина была единичной. Остается одна трудность, вытекающая из того факта, что если является решением минимизационной задачи, то — также является решением. Однако лишь одно из этих решений будет соответствовать положительному значению Это можно легко проверить, приписав значение некоторой точке изображения. Случай, когда имеются два совпадающих наименьших собственных значения, будет обсуждаться ниже.

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

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

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

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

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

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

Здесь скорость оптического потока для точек, которые больше удалены, имеет больший вес. Это условие наиболее благоприятно, когда измерение больших скоростей осушествляется с меньшей точностью. Мы приходим к квадратичной форме, аналогичной однако здесь интегралы для вычисления констант более сложные. Как ни странно, они зависят лишь от направления оптического потока, а не от его величины.

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление