Главная > Распознавание образов > Лекции по теории образов: Анализ образов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.6. Зондирование границ

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

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

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

Пусть, например, -мерная группа Ли, в которой введена локальная система координат с началом в единичном элементе группы: . Рассмотрим класс образов где единственная образующая. Здесь предполагается, что образующая представляющая идеальное изображение известна, и наша задача заключается в отыскании преобразования подобия такого, что (см. разд. 5.1).

Границу прототипа будем записывать так:

здесь принадлежит вдоль При заданных точках мы будем наблюдать некоторое деформированное изображение

где

и подчиняется двумерному нормальному распределению с нулевым математическим ожиданием и ковариационной матрицей

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

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

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

как неизвестные, на которые наложено лишь ограничений в виде соотношений все различные), и, следовательно, мы имеем свободных параметров. Это означает, что общее число степеней свободы равно .

Начнем с того, что будем считать оценку фиксированной и оценим граничных точек Оценка по методу максимального правдоподобия дает условие

или с использованием множителей Лагранжа

Отсюда непосредственно следует, что

где следует выбирать так, чтобы выполнялось условие Это дает нам приближение первого порядка (здесь мы всегда будем пользоваться именно таким порядком аппроксимации)

где означает градиент относительно вектора вычисленный в точке Следовательно,

Теперь переходим к определению решая

где запись указывает на зависимость от неизвестного элемена группы

И снова с помощью приближения первого порядка при получаем

причем скалярные произведения — это внутренние произведения, первые в вторые в Отметим, что

Таким образом, (5.6.9) приводит к системе уравнений относительно

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

и сформируем вектор-столбец с компонентами, равный правой части (5.6.11), деленной на Тогда

очевидно, что и ковариационная матрица равна

где

С помощью определения (см. (5.6.8)) последнее выражение сводится к следующему:

В сочетании с (5.6.14) это определяет ковариационную матрицу и, таким образом, получен следующий результат обозначает теперь произвольный элемент группы).

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

распределением :

матрица определяется (5.6.12).

Чтобы сделать этот результат более конкретным, рассмотрим пример, в котором — прямое произведение переносов и изменений масштаба, а — единичный круг, так что

и

Следовательно,

и

для расположенных на границе . В соответствии с (5.6.9) мы должны решить задачу

или, что то же самое,

Если ввести четыре вектора-столбца

то решение (5.6.23) можно свести к решению

здесь матрица

Если матрица М неособенная, то мы просто обращаем ее, чтобы получить а затем и с из соотношения Матрица М, однако, является особенной в том и только в том случае, если векторы коллинеарны, и, следовательно, справедливо нетривиальное линейное соотношение

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

Радиус, в частности, можно аппроксимировать следующей функцией:

Она обладает такими свойствами:

A. R является однородной функцией первой степени, так что

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

B. R инвариантна относительно евклидовой группы на плоскости и симметрической группы перестановок индексов точек

Г. Если все точки лежат на круговой дуге радиуса то

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

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

Отметим, что эта величина связана с минимальным значением квадратичной формы (5.6.22). В самом деле, это минимум есть

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

Критерий обладает следующими свойствами:

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

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

B. Если все точки лежат на круговой дуге, то

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

Для исправления этого недостатка предлагается следующая модификация критерия круглости. Определим, во-первых, оценки a, b и с. Для расстояний имеем

и для модифицированной оценки радиуса

Пусть

где

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

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

Чтобы выяснить, каково «численное» поведение критерия х, мы промоделировали три случая, представленные на рис. 5.6.1: здесь изображены результаты деформации дуги окружности 90°. На рис. 5.6.1а а = 0 и х = 1. На рис. 5.6.16 деформации невелики, .

Рис. 5.6.1 в.

В третьем случае (рис. 5.6.16) деформации существенно сильнее, , что приводит к значению ; это определенно указывает на отклонение от круговой формы, к чему мы и стремились.

Для вычисления матрицы с помощью (5.6.12) требуется . Но из (5.6.19) можно получить непосредственно

причем третье уравнение не выполняется на Если ввести матрицу

то мы получим

и

так что если существует и матрица является неособенной, то

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

Пусть распределены асимптотически в соответствии с функцией распределения Ф и симметричны относительно Тогда

где

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

Начнем с вопроса об оптимальном размещении точек зондирования в том случае, когда основной задачей является определение радиуса с с высокой точностью. Тогда в соответствии с (5.6.38) и (5.6.40) необходимо минимизировать:

Для максимизации при заданном значении В обратим внимание на вид в (5.6.41) и воспользуемся тем же вариационным методом, к которому мы уже прибегали несколько раз раньше в этой работе (см., например, т. 1, с. 227). Пренебрегая подробностями, укажем, что должно выполняться нетривиальное линейное соотношение

справедливое для всех принадлежащих носителю Поскольку мы рассматриваем только принадлежащие интервалу , носитель может содержать самое большее две точки Пусть соответствующие вероятностные меры равны , так что

Можно записать, используя штрихи для обозначения дифференцирования по а, что

и

Рассмотрим сначала случай, когда и, следовательно, и В больше нуля. Упорядочим углы так, чтобы выполнялись неравенства непосредственная проверка (5.6.46) показывает, что минимум достигается при а, заключенном внутри отрезка [0, 1], причем

Для минимизации необходимо сделать отношение максимально возможным (напомним, что т. е.

Непосредственная проверка показывает, что это справедливо и для предельного случая

При обращении к случаю ситуация в корне меняется. Положив и

получаем минимум, непосредственно равный нулю, поскольку . Этот минимум не единственный.

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

Максимизируя поступаем, как и выше, и отыскиваем оптимальный план при

И наконец, чтобы получить с максимально возможной точностью следует минимизировать

(кликните для просмотра скана)

Для этого достаточно разместить все точки на дуге центрального угла (повторные независимые измерения):

Объединим теперь результаты, учитывая соотношение между (которое мы определили) и Ф (которое реально используется при построении плана).

Теорема 5.6.2. Асимптотически оптимальный план строится так:

(i) Радиус. Если то вычисляем отношение

и берем часть при угле и ±1/2 при каждом из углов Если долю 1/4 берем при каждом из четырех углов

Первая координата центра. Долю 1/2 берем при угле и доли при углах

Вторая координата центра. Если часть точек зондирования берем при каждом из углов Если часть точек зондирования берем при каждом из углов

Соответствующие иллюстрации приведены на рис. 5.6.2, где оптимальные положения точек зондирования указаны для дуг с центральными углами 240, 180, 120° и углом, близким к нулю. Относительное число точек зондирования при различных углах обозначено направленными вовне отрезками прямых.

Пусть теперь форма будет произвольной при соблюдении заданных условий, и пусть — переносы в Тогда

и

а также

Для того чтобы получить с помощью (5.6.12), необходимо определить член

где Геометрический смысл этого члена становится понятен, если мы параметризуем с помощью дуги длины а, измеряемой от произвольной начальной точки, и угла, образуемого

касательной в точке о и измеренного в положительном направлении от оси Вдоль границы имеет место

и

и т. д., что дает нам

С помощью функции распределения Ф вдоль границы и выраженной через длину дуги а получаем удобное выражение для

где — общая длина Последнее в сочетании с теоремой 5.6.1 позволяет получить асимптотическую ковариационную матрицу для оценки двух элементоа группы и которые в данном случае сводятся к параметрам переноса а и

Кроме того, здесь естественно возникает задача построения плана оптимального определения двух параметров переноса. Эта задача пока не изучена.

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