Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 319
Текст из файла (страница 319)
Если дано множество стоимостей Сы согласованиЯ междУ всеми паРами точек 2 на первой форме и точек 7' на второй форме, то может быть принято решение минимизировать общую стоимость согласования с учетом ограничения, что это согласование должно выполняться на основе взаимно-однозначного соответствия. Это— пример задачи поиска паросочетаиий взвешенного двухдольиого графа, которая может быть решена за время О(и') с использованием так называемого венгерского алгоритма (Нппяаг)ап а!яог)гйгп). Если известны соответствия в точках выборки, то данные о соответствии можно распространить на всю форму, оценивая стоимость согласующего преобразования, которое позволяет отобразить одну форму на другой. Особенно эффективным является подход с использованием регуляризованного тонкостенного сплайна (геяп)апгес1 )Л)п р)а)е зрйпе).
После того как формы будут согласованы, задача вычисления оценок подобия становится относительно несложной. Расстояние между двумя формами может быть определено как ювешенная сумма расстояний контекстов форм между соответствующими точками и как энергия изгиба, связанная с тонкостенным сплайном. После получения такой меры расстояния для решения задачи распознавания можно использовать простой классификатор по ближайшим соседним точкам.
Превосходная иллюстрация, демонстрирующая высокую эффективность применения этого подхода при классификации рукописных цифр, приведена в главе 20. Оценка позы Интерес представляет не только задача определения того, каковым является некоторый объект, но и задача определения его позы, т.е. его позиции и ориентации по отношению к наблюдателю. Например, при решении проблемы манипулирования объектами на производстве приходится учитывать, что захват робота не может взять объект до тех, пока не будет известна его поза.
В случае твердотельных объектов, как )!76 Часть УП. Общение, восприятие и осуществление действий трехмерных, так и двухмерных, эта проблема имеет простое и полностью определенное решение, основанное на 'т. методе выравнивания, который описан ниже. В этом методе объект представляется с помощью )и характеристик, или различимых точек т,, т„..., ти в трехмерном пространстве (в качестве таковых могут, допустим, рассматриваться вершины многогранного объекта). Координаты этих точек измеряются в некоторой системе координат, наиболее подходящей для данного объекта. После этого точки подвергаются операции трехмерного вра(цения н с неизвестными параметрами, за которой следует операция переноса на неизвестную величину е, а затем выполняется операция проекции, которая приводит к появлению точек характеристик изображения р„р,, ..., рп на плоскости изображения.
Вообще говоря, )Чхм, поскольку некоторые точки модели могут закрывать друг друга, а детектор характеристик может пропустить некоторые характеристики (или выявить ложные характеристики, появление которых обусловлено наличием шума). Такое преобразование для трехмерной модели точек т, и соответствую)цих точек изображения р„ можно представить следуюшим образом: р, = П (нт, + е) = С)(т.) где и — матрица врагцения, е — вектор переноса; П вЂ” перспективная проекция или одно из ее приближений, такое как масштабируемая ортогональная проекция. Чистым результатом становится трансформация Ц, которая приводит точки модели т„ в соответствие с точками изображения р„.
При этом, хотя первоначально трансформация О не определена, известно, что (применительно к твердотельным объектам) (7 должна быть одинаковой для всех точек модели. Задачу определения преобразования О можно решить, получив значения трехмерных координат трех точек модели и их двухмерных проекций. В основе этого подхода лежит следуюгцая интуитивная идея: могут быть легко составлены уравнения, связываюшие координаты рь с координатами т,. В этих уравнениях неизвестные величины соответствуют матрице врашения н и вектору переноса е.
Если количество уравнений достаточно велико, то возможность получения решения для О становится неоспоримой. Мы не будем приводить здесь доказательство этой гипотезы, а просто сформулируем следующий результат. Если даны три точки, т„т, и тм в модели, не лежашие иа одной прямой, и их мпсштабироваииые ортогоиальиые проекции, р„р, и р„на плоскости изображения, то сушествуют две и только две трансформации из системы координат трехмерной модели в систему координат двухмерного изображения, Эти трансформации связаны друг с другом, поскольку зеркально противоположны относительно плоскости изображения; они могут быть вычислены на основе простого решения в замкнутой форме.
Если сушествует возможность идентифицировать характеристики модели, соответствую)цие трем характеристикам в изображении, то может быть вычислена 0 — поза объекта. В предыдушем подразделе обсуждался метод определения соответствий с использованием согласования контекстов формы. Если же объект имеет четко определенные углы или другие заметные точки, то становится доступным еше более простой метод. Идея его состоит в том, что необходимо повторно формировать и проверять соответствия. Мы должны выдвинуть первона альную гипотезу о соответствии тройки точек изображения тройке точек модели и использовать функцию афпг)-Тгапэбогт для формирования гипотезы О.
1177 Глава 24. Восприятие Если принятое предположение о соответствии было правильным, то трансформация (2 является правильной и после ее применения к оставшимся точкам модели приводит к получению предсказания координат точек изображения. Если принятое предположение было неправильным, то трансформация 0 также является неправильной и после ее применения к оставшимся точкам модели не позволяет предсказывать координаты точек изображения. Описанный выше подход лежит в основе алгоритма л11дп, приведенного в листинге 24.1. Этот алгоритм находит позу для данной конкретной модели или возврашает индикатор неудачи.
Временная сложность данного алгоритма в худшем случае пропорциональна количеству сочетаний троек точек модели и троек точек изображения, или умноженному на стоимость проверки каждого сочетания. Стоимость проверки пропорциональна )ч1од)з(, поскольку необходимо предсказывать позицию изображения для каждой из м точек модели и находить расстояние до ближайшей точки изображения, что требует выполнения 1од)зг операций, если точки изображения представлены с помошью некоторой подходяшей структуры данных. Поэтому в наихудшем случае сложность алгоритма выравнивания определяется значением 0(р)з)з)з1оди), где м и )з) — количество точек модели и изображения соответственно.
Методы, основанные на принципе кластеризации поз в сочетании со средствами рандомизации, позволяют уменьшить сложность до 0 (мз)з ) . Результаты применения этого алгоритма к изображению стеллера показаны на рис. 24.21. Листинг 24.1. Неформальное описание алгоритма выравнивания ЕппоеЕоп л11дп(1таде, тес(е1) геепгпв решение яо1ис1ол или индикатор неудачи Еа11 иге Епрпен: 1таде, список координат характеристик изображения тес)е1, список координат характеристик модели Еог еао)з (рз, рз, рз) Еп Тгвр1еся(1таде) йо Еог еао)з (тз, тз, тз) хп Тгдр1еся (тес)е1) йо (7 ь- рьпб-тгапягогт((рз, рз, рз), (тз, тз, тз) ) ЕЕ проекция, соответствуюшая гипотезе д, позволяет распознать изображение Е)зеп геепгп (2 гевпгп Еа11иге 24.6.
ИСПОЛЬЗОВАНИЕ СИСТЕМЫ МАШИННОГО ЗРЕНИЯ ДЛЯ МАНИПУЛИРОВАНИЯ И ПЕРЕДВИЖЕНИЯ Одно из наиболее важных направлений использования систем машинного зрения состоит в получении информации как для манипулирования объектами (определения их местоположения, захвата, изменения их положения в пространстве и т.д.), так и для передвижения без столкновений с препятствиями. Способность использовать зрение для этих целей присуша системам зрения даже самых примитив- !!80 Часть Ч!!. Общение, восприятие и осуществление действий машинного зрения, в которых используются эти методы, показали свою способность двигаться в течение продолжительных периодов времени на максимальных скоростях, разрешенных на автомагистралях.
Приведенный выше пример решения проблемы вождения позволяет очень четко подчеркнуть одну мысль: е для решения конкретной задачи нет необходимости извлекать из изображения всю информацию, которая может быть в принципе получена с его помощью. Не требуется восстанавливать точную форму кажлого встречного или попуз ного автомобиля, решать задачу определения формы на основании текстуры для поверхности травы, растущей вдоль автомагистрали, и т.д. Потребности данной задачи определяют необходимость в получении лишь информации определенных видов, и поэтому можно добиться значительного повышения скорости вычислений и надежности.
восстанавливая только эту информацию и в полной мере применяя ограничения проблемной области. Наша цель при обсуждении общих подходов, представленных в предыдущем разделе, состояла в демонстрации того, что они формируют общую теорию, которую можно специализировать в интересах решения конкретных задач. 24.7. РЕЗЮМЕ Хотя на первый взгляд кажется, что люди осуществляют действия по восприятию без каких-либо усилий, для обеспечения восприятия требуется большой объем сложных вычислений. Задача зрения состоит в извлечении информации, необходимой для решения таких задач, как манипулирование, навигация и распознавание объектов.
° Геометрические и физические аспекты процесса формирования изображения глубоко изучены. Если дано описание трехмерной сцены, можно легко сформировать ее изображение из любой произвольной позиции видеокамеры (это — задача компьютерной графики). Задача организации обратного процесса, в котором происходит переход от изображения к описанию сцены, является более сложной. ° Для извлечения визуальной информации, необходимой для решения задач манипулирования, навигации и распознавания, необходимо создавать промежуточные представления. В ранних алгоритмах обработки изображения для систем машинного зрения предусматривалось извлечение из изображения таких примитивных характеристик, как края и участки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
