Оценка позы
Интерес представляет не только задача определения того, каковым является некоторый объект, но и задача определения его позы, т.е. его позиции и ориентации по отношению к наблюдателю. Например, при решении проблемы манипулирования объектами на производстве приходится учитывать, что захват робота не может взять объект до тех, пока не будет известна его поза. В случае твердотельных объектов, как трехмерных, так и двухмерных, эта проблема имеет простое и полностью определенное решение, основанное на методе выравнивания, который описан ниже.
В этом методе объект представляется с помощью м характеристик, или различимых точек т1,т2, ..., в трехмерном пространстве (в качестве таковых могут, допустим, рассматриваться вершины многогранного объекта). Координаты этих точек измеряются в некоторой системе координат, наиболее подходящей для данного объекта. После этого точки подвергаются операции трехмерного вращения R с неизвестными параметрами, за которой следует операция переноса на неизвестную величину t, а затем выполняется операция проекции, которая приводит к появлению точек характеристик изображения pl9 р2, Ры на плоскости изображения. Вообще говоря, NtM, поскольку некоторые точки модели могут закрывать друг друга, а детектор характеристик может пропустить некоторые характеристики (или выявить ложные характеристики, появление которых обусловлено наличием шума). Такое преобразование для трехмерной модели точек jn± и соответствующих точек изображения pL можно представить следующим образом:
Pi = П (Rim + t) = Q(irii)
где R — матрица вращения, t — вектор переноса; П — перспективная проекция или одно из ее приближений, такое как масштабируемая ортогональная проекция. Чистым результатом становится трансформация Q, которая приводит точки модели хп± в соответствие с точками изображения р1# При этом, хотя первоначально трансформация Q не определена, известно, что (применительно к твердотельным объектам) Q должна быть одинаковой для всех точек модели.
Задачу определения преобразования Q можно решить, получив значения трехмерных координат трех точек модели и их двухмерных проекций. В основе этого подхода лежит следующая интуитивная идея: могут быть легко составлены уравнения, связывающие координаты pL с координатами В этих уравнениях неизвестные величины соответствуют матрице вращения R и вектору переноса t. Если количество уравнений достаточно велико, то возможность получения решения для Q становится неоспоримой. Мы не будем приводить здесь доказательство этой гипотезы, а просто сформулируем следующий результат.
Если даны три точки, mi, т2 и тпз, в модели, не лежащие на одной прямой, и их масштабированные ортогональные проекции, р1} р2 и р3, на плоскости изображения, то существуют две и только две трансформации из системы координат трехмерной модели в систему координат двухмерного изображения.
Эти трансформации связаны друг с другом, поскольку зеркально противоположны относительно плоскости изображения; они могут быть вычислены на основе простого решения в замкнутой форме. Если существует возможность идентифицировать характеристики модели, соответствующие трем характеристикам в изображении, то может быть вычислена Q— поза объекта. В предыдущем подразделе обсуждался метод определения соответствий с использованием согласования контекстов формы. Если же объект имеет четко определенные углы или другие заметные точки, то становится доступным еще более простой метод. Идея его состоит в том, что необходимо повторно формировать и проверять соответствия. Мы должны выдвинуть первоначальную гипотезу о соответствии тройки точек изображения тройке точек модели и использовать функцию Find-Transform для формирования гипотезы Q.
Если принятое предположение о соответствии было правильным, то трансформация Q является правильной и после ее применения к оставшимся точкам модели приводит к получению предсказания координат точек изображения. Если принятое предположение было неправильным, то трансформация Q также является неправильной и после ее применения к оставшимся точкам модели не позволяет предсказывать координаты точек изображения.
Описанный выше подход лежит в основе алгоритма Align, приведенного в листинге 24.1. Этот алгоритм находит позу для данной конкретной модели или возвращает индикатор неудачи. Временная сложность данного алгоритма в худшем случае пропорциональна количеству сочетаний троек точек модели и троек точек изображения, или умноженному на стоимость проверки каждого сочетания. Стоимость проверки пропорциональна MlogN, поскольку необходимо предсказывать позицию изображения для каждой из м точек модели и находить расстояние до ближайшей точки изображения, что требует выполнения logAT операций, если точки изображения представлены с помощью некоторой подходящей структуры данных. Поэтому в наихудшем случае сложность алгоритма выравнивания определяется значением 0{м*Ыъ1одЫ), где Ми АГ— количество точек модели и изображения соответственно. Методы, основанные на принципе кластеризации поз в сочетании со средствами рандомизации, позволяют уменьшить сложность до О (Ж3). Результаты применения этого алгоритма к изображению степлера показаны на рис. 24.21.
Листинг 24.1. Неформальное описание алгоритма выравнивания
function Align(image, model) returns решение solution или индикатор неудачи failure inputs: image, список координат характеристик изображения model, список координат характеристик модели
for each (plt р2, рз) in Triplets(image) do
for each {mlt m2, тз) in Triplets{model) do
Q <— Find-Transform ( (pi, p2, рз), [mlt m2, тъ) ) if проекция, соответствующая гипотезе Q, позволяет распознать изображение then return Q
return failure