Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 95
Текст из файла (страница 95)
Длн начала перепишем формулу (17) гл. 1О, которая задает общее перспективное преобразование в однородных координатах: чр —— Рб ееТч. Затем мы определим матрицу У размерностью 4 си, содержащую и векторов чь ~'=-1,... „и, в качестве столбцов, а также матрицу У' размерностью 3 хи, содержащую в качестве столбцов и векторов чр,. Другими словами, матрица У составлена из набора и точек модели (в однородных координатах), а матрица У' — из набора и наблюдаемых точек изображения. Определим матрицу Н размерностью 3 х 4 как произведение матриц Р0НТ со стертой второй строкой. Нам хотелось бы теперь иметь вазможность сформулировать нашу задачу как задачу отыскания матрицы Н, такой, что НУ= =- У'.
Или, на словах, мы ищем для заданных точек модели и изображения перспективное преобразование Н (которое учитывает относительное расположение модели и камеры), такое, что каждая точка модели проектируется в соответствующую ей точку изображения. К сожалению, ситуация оказывается несколько более сложной. Во-первых, хотя матрица Н содержит!2 компонент, имеется только пять независимых параметров, а именно зто три параметра переноса и два параметра вращения камеры. Каждая нз 12 компонент матрицы Н является функцией этих параметров.
Таким образом, в принципе мы не имеем вазможности выбирать произвольную матрицу Н. й(ы проигнорируем эту трудность ради простоты изложения, но, поступая так, мы должны подчеркнуть, что результирующий анализ является только приближенным. Второе усложнение связано с тем обстоятельством, что мы не можем одновременно задать масштаб и точки объекта (в однородных координатах), и соответствующей ей точки изображения (также, конечно, в однородных координатах). А именно, если у нас есть точка объекта ч=(х, у, г)' н точка изображения чр=(хр, г')', мы не можем произвольно записать их однородные представления в виде ч=-(х, у, г, еп)' и ч,',= =(хр, г', ш)', поскольку для этого потребовалось бы, чтобы в перспективйом преобразовании Н одно и та же число ш фигурировало в качестве последней однородной координаты и точки объекта, и соответствующей ей точки изображения.
Чтобы избежать этой ловушки, мы введем диагональную матрицу масштаба Р, которая Гл. !л. Соотаоление и обработка оаиеаниб 470 позволит нам масштабировать каждый однородный вектор изображения посредством произвольного коэффициента. В соответствии с этим мы сформулируем теперь нашу первоначальную задачу следующим образом: найти матрицу Н размерностью Зх4 и диагональную матрицу Р размерностью пхл так, чтобы НУ= У'Р. В этом матричном уравнении имеется я+12 неизвестных, из которых и входят в матрицу Р, а 12 — в матрицу Н, и всего имеется Зл уравнений.
Следовательно, мы можем рассчитывать найти решениео если и равно по крайней мере б. На практике мы, по-видимому, будем пытаться получить более чем шесть точек модели, и поэтому естественно решать это уравнение методом наименьших квадратов. А именно нам хотелось бы найти такие матрицы Н иР, чтобы сумма квадратов разностей между компонентами НУ и У'Р была минимальна. Эта задача минимизации приводит к обычным преобразованиям; и поэтому мы просто выпишем результат, который, к сожалению, имеет несколько беспорядочный вид. Пусть Ауе(ууе)1ул пусть (р =(у')еу', и пусть 5 представляет собой матрицу, (1, 1)-й элемент которой зы=аыд;.
(Или, словами, матрица Я образована поэлементным перемножением матриц А и Я'.) Пусть п-мерный вектор д имеет в качестве компонент диагональные элементы матрицы Р. Тогда решение задачи минимизации сводится к использованию в качестве диагональных элементов матрицы Р решения однородного уравнения и к вычислению Н укРуе(ууе)-л (2) Прежде чем двигаться дальше, сделаем паузу и прокомментируем форму решения.
Заметим, во.первых, что, хотя однородная форма перспективного преобразования и полезна, она не может замаскировать существенно нелинейную природу этого преобразования. Использование диагональной матрицы Р представляет собой ловкий прием, призванный компенсировать другой прием— однородные координаты. Подобным же образом определение матрицы Я включает явно нелинейную операцию над матрицами. После того как получена матрица Н, мы можем найти значения геометрических параметров, приравняв соответствующие компоненты матрицы Н и компоненты произведения РОЮТ. Например, с помощью непосредственного перемножения мы находим, что компонента (1, 1) произведения РСКТ равна соз О, и поэтому мы можем 471 12ЛЬ Анализ многогранников немедленно найти величину угла поворота камеры ').
После того как наилучшие значения геометрических параметров найдены, модель можно спроектировать на плоскость картинки и сравнить с изображением. Степень достигнутого соответствия (измеряемая, скажем, суммой квадратов ошибок) представляет собой окончательныйчисловой результат процедуры и служит основой для принятия решения о том, подходит ли данная конкретная моделы представленным на изображении данным. Элементы метода подбора модели появляются во многих различных формах. Мы упоминали раньше о возможности того, что в некоторых случаях важные сведения о моделях могут быть переведены в простые сведения об их изображениях.
В отличие от этого предположим, что наша задача заключается в том, чтобы убедиться, что данная картинка отображает какие-либо новые признаки окружающей трехмерной обстановки, например либо объект передвинулся, либо появился новый объект. Основной подход к этой задаче сводится к тому, чтобы сравнить новую картинку с проекцией старой модели окружающей обстановки. В простом случае с неподвижной камерой это сравнение может быть выполнено поэлементным вычитанием последовательных картинок и регистрацией существенных изменений. Если камера между съемкой изображений двигалась, простое вычитание не годится; вместо этого мы, возможно, захотим запоминать трехмерную модель окружающей обстановки и сравнивать новую картинку с вычисленной проекцией модели. Прежде чем завершить наше обсуждение, мы должны сделать замечание по поводу тесной связи между подбором модели и некоторыми разделами машинной графики, В обеих областях, например, задачи часто включают вычисление двумерного изображения трехмерной сцены.
Это вычисление, в свою очередь, часто требует решения так называемой проблемы невидимых линий, т. е. задачи определения, какие части трехмерных объектов загорожены в данной проекции. На этом мы прекращаем обсуждение, а ссылки на нужную литературу даются в конце главы. 12.4. АНАЛИЗ -МНОГОГРАННИКОВ В последнем разделе мы обсуждали некоторые методы использования очень точных знаний об окружающей трехмерной обстановке (в предельном случае — полного знания структуры объектов). Очень часто, однако, такие полные знания недоступны; в самом деле, получение в точности такого рода информации может быть целью ') В то же самое время приравнивание соответствующих элементов может также обнаружить грубость нашего приближенного ааализа. Например, оказывается, что элемент (1, 2) произведения РОРТ равен а)п В, но нет никакой уверенности, что существует угол В, косинус и синус которого равны соответственно элементам (1, 1) и (1, 2) вычисленной нами матрицы Ц. 472 Гл.
!2. Составление и обрабоааеа оаисаниа анализа сцены. С другой стороны, если у нас совсем нет предварительных знаний о трехмерном мире, мы, очевидно, вынуждены довольствоваться весьма ограниченными видами анализа. В большинстве типичных случаев задача находится между этими крайностями; мы можем обладать предварительными знаниями о всей совокупности объектов окружающей обстановки, но не иметь предварительных знаний одетальной структуре.
Среди задач этого класса анализ изображений многогранников (тел, ограниченных плоскостями) занимает выдающееся место. В последующем изложении мы представим несколько общих методов для извлечения трех различных видов информации из картинок с многогранниками. Эти методы представляют значительный интерес ие только потому, что многогранники являются основными геометрическими «строительными блоками», но также и потому, что мы должны досконально разобраться с этими простыми телами, прежде чем сможем надеяться анализировать более сложные тела. !2.4.!. СЕМАНТИКА ЛИНИЙ Нас интересует здесь занимательная с виду задача поиска «смысла» в линиях картинки.
Эта задача достойна внимания только в том случае, если, во-первых, мы сможем точно указать, что означает выраженйе «лнния имеет смысл», и, во-вторых, если сможем найти разумные методы установления такого смысла. Получается так, что оба эти условия удовлетворяются; мы можем очень легко уточнить понятие смысла линии иа изображении многогранника, и, более того, существует простой и остроумный способ установить его. Если мы сможем успешно приписать некоторый смысл каждой линии картинки, то анализ сцены в каком-то плане будет полным. Прежде чем начать, сделаем два допущения. Мы примем, что окружающая обстановка содержит только многогранники степени 3, т. е.
в точности три плоских поверхности сходятся вместе в каждой из вершин многогранников. (Такие многогранники называют иногда епрехграннилеи телами ) Мы примем далее, что камера находится в оби(ни положении относительно объектов окружающей обстановки. Это означает, что при небольшом изменении позиции камеры получается в основном такая же картинка — число линий и конфигураций, которые они образуют, не изменяется. Наше первое важное наблюдение состоит в том, что (при наших допущениях) одна линия на картинке может иметь в точности четыре значения: она может представлять вогнутый край многогранника, не закрывающий выпуклый край или закрывающий (загораживающий) выпуклый край, который закрывает более удаленные части сцены либо с одной стороны, либо с другой.
Для простоты мы будем называть незакрывающие выпуклые края просто выпуклыми краями, а закрывающие выпуклые края — закрывающими краями. Все !2.4. Анализ многогранников эти типы краев представлены в сцене рис. 12.7, на которой показан камин с приподнятым основанием. Например, линии АгИ и Е6 представляют собой вогнутые края, линии ВУ и 0Š— выпуклые края, а линии АВ, ВС и Е7 — закрывающие края. Важно отметить, что, поскольку мы имеем дело с объектами, ограниченными плоскостями, смысл линии должен оставаться неизменным по всей ее длине.
В качестве обозначения мы будем отмечать выпуклые линии знаком плюс, вогнутые — знаком минус и закрывающие линии— стрелкой. Направление стрелки выбирается таким образом, что, если вы мысленно встанете на плоскость картинки и посмотрите на Рис. !2.7. Камин с основанием. линию в направлении стрелки, незакрытая плоскость будет лежать справа от линии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
