4.3. Отмеченные точки

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

Выберем в качестве образующих точки в R^p так что образующая g характеризуется своими координатами x₁(g), x₂(g),...,x_p(g) и, кроме того, другими признаками, определяющими цвет, тип материала и т. д. Индекс класса образующих α(g) задан натуральным числом (тип отмеченной точки), причем А = {1, 2,..., q}, и, следовательно, q - число типов. Арность g должна быть неограниченной, и все показатели связи определяются вектором x₁(g), x₂(g), ..., x_p(g), α(g).

При типе соединения "полный" отношение связи βρβ' означает, что

(4.3.1)

здесь {к_αα'} - некоторая заданная матрица положительных чисел. Преобразования подобия должны состоять из EG(p), совместных с заданной структурой связей (см. разд. 2.1, т. 1). Это определяет регулярную конфигурацию, причем следует заметить, что для любой регулярной конфигурации с справедливо соотношение #(c) ≤ q.

Пусть изображения идентифицируются как конфигурации; рассмотрим классы образов sI₀, построенные на основе прототипов I₀, где I₀ -известен и фиксирован и s∈S. Важная задача - отыскать расположение изображения, или, что эквивалентно, значения s, если наблюдается некоторое деформированное изображение

(4.3.2)

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

На определение s с высокой точностью можно рассчитывать только в том случае, если сведения о sI₀ и I₀ однозначно определяют s, т. е., другими словами, если накрывающая группа прототипа сводится к единичному элементу (см. разд. 3.1, т. 1). Мы приведем условия, при выполнении которых это действительно будет иметь место после доказательства следующей теоремы.

Пусть деформированное изображение I^D состоит из n точек I^D_j, j = 1, 2, ..., n, так что его можно представить матрицей размера n×p:

(4.3.3)

Мы приходим к следующему методу определения преобразований подобия s.

Теорема 4.3.1.Чтобы получить методом максимального правдоподобия оценку s^* преобразований подобия s, сформируем матрицу W с элементами w_υμ:

(4.3.4)

где g_jυ - υ-я координата g_j и запишем ее в виде W = UDV, где U и V взаимно ортогональны и D = [λ₁, λ₂,..., λ_p], λ_j ≥ 0. Тогда результат имеет следующий вид (расшифровку обозначений см. ниже):

(4.3.5)

Замечание. То, что матрицу можно представить в таком виде, как мы представили выше матрицу W, - это классический результат, принадлежащий Жордану (см.,например,Макдаффи (1946), с. 78).

Доказательство. Преобразование подобия s можно представить как поворот, т. е. как ортогональную матрицу О, за которым следует перенос, осуществляемый с помощью вектора υ, так что υ-я точка деформированного изображения I^D определяется как

(4.3.6)

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

(4.3.7)

Сначала, оставляя матрицу О фиксированной, изменяем вектор v с тем, чтобы минимизировать сумму. Как обычно, в результате получаем, что

(4.3.8)

и, следовательно, естественно ввести

(4.3.9)

после этого остается минимизировать выражение

(4.3.10)

что, несомненно, представляет собой нетривиальную часть задачи.

Воспользовавшись тем обстоятельством, что матрица О ортогональна и сохраняет расстояние, выражение (4.3.10) можно

записать как

(4.3.11)

при этом представлении остается максимизировать третью сумму - первые две суммы не содержат матрицу О.

Определим матрицу W как описано выше:

(4.3.12)

третью сумму в (4.3.11) можно записать как

(4.3.13)

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

(4.3.14)

Но так как VOU = M представляет собой (произвольную) ортогональную матрицу с несколькими элементами m_μ, m_υμ < 1 то, следовательно,

(4.3.15)

Этой верхней грани можно достичь, выбирая М = I или O = V^-1U^-1 что доказывает утверждение (4.3.5).

Этот результат действительно единственный, если все λ_j > 0, т. е. матрица W не особенная. Чтобы выяснить, как обстоит дело при отсутствии деформаций, т. е. когда σ = 0, заметим, что в этом случае система (4.3.9) сводится к следующей:

так что из (4.3.12) следует

(4.3.17)

где Г - матрица с векторами-строками g_j = . Чтобы матрица W была не особенной, необходимо, чтобы матрица Г имела ранг р, т. е. векторы g_j - , j = 1,2, ..., n, должны стягивать пространство R^P. Тогда существует в точности одно преобразование подобия s, переводящее заданный прототип I₀ в наблюдаемый прототип sI₀.

Если вместо евклидовой группы мы в качестве преобразований подобия воспользуемся афинными преобразованиями g → υ + Ag, где υ - произвольный р-мерный вектор и A - произвольная не особенная матрица s = (υ, A), то определение преобразований подобия s по sI₀ оказывается существенно проще решения первой задачи. Действительно, эта задача легко сводится к стандартной задаче, возникающей при проверке обычной линейной статистической гипотезы. Выполнить это сведение мы предоставляем читателю.

Здесь мы займемся изучением более интересного вопроса: каким образом следует модифицировать процедуру теоремы 4.3.1, если = ₁₂, где ₂ - то же, что и выше, ₁ - некоторый (сингулярный) проекционный оператор (см. разд. 4.6, т. 1).

Пусть для простоты р = 2 и Y = R² проектируется на ось х. Тогда деформированное изображение ^D представляет собой просто вектор x₁, x₂, ..., x_n, и нам предстоит решать задачу минимизации

(4.3.18)

по вектору υ и матрице О. Естественно, вектор υ входит в (4.3.18) лишь посредством своих х-компонент, и, следовательно, мы не сможем делать каких-либо выводов относительно υ_y. В этом есть свой резон. Ответ же содержится в следующей теореме.

Теорема 4.3.2.Для определения вектора υ_x и матрицы О методом максимума правдоподобия строим вектор а = Г^Tξ, где ? - деформированное изображение I^D₁, приведенное посредством вычитания среднего, и матрица В = Г^ТГ, где ξ также приводится посредством вычитания (см. ниже). Компонент преобразований подобия, представляющий вращение, - матрица О - определяется из уравнения (В - λI)^-1 а = O^Тх, x = (1,0), причем λ выбирается так, чтобы вектор, стоящий слева, имел единичную норму.

(4.3.19)

Доказательство. В первую очередь необходимо определить υ_x, но поскольку это делается в полном соответствии со вторым уравнением (4.3.5), то никаких проблем в связи с этим не возникает. Записав приходим к минимизации следующего выражения (с учетом того, что O = {o_υμ}):

(4.3.20)

или, в матричной форме,

(4.3.21)

Здесь использованы следующие обозначения:

(4.3.22)

Сначала займемся основным случаем a ≠ 0. Пусть y = O^Тх, тогда y - это произвольный вектор единичной длины, поскольку О - произвольная ортогональная матрица. Следовательно, необходимо решить уравнение

(4.3.23)

что нетрудно сделать, воспользовавшись, например, множителем λ Лагранжа

(4.3.24)

причем λ следует выбирать так, чтобы у имел единичную норму. В результате получаем

(4.3.25)

Симметрическая матрица В является неотрицательно определенной, некоторые из ее собственных значений λ₁λ₂ ≥ 0, поэтому λ следует выбирать так, чтобы при В = С^тdiag [λ_υ]С

(4.3.26)

Введя вектор α = а_ТС_Т с компонентами α_υ, приходим к следующему уравнению:

(4.3.27)

Левой части уравнения (4.3.27) соответствует график на рис. 4.3.1 либо при λ₁ = λ₂ график, соответственно скорректированный. Следовательно, уравнение (4.3.27) может иметь четыре, три или два корня, из которых самое большее два представляют минимумы, поскольку мы оперируем на циклической группе вращения. Чтобы отыскать их, следует просто вычислить соответствующие значения выражения (4.3.21), которое можно выразить с помощью введенных выше величин:

(4.3.28)

Рис. 4.3.1

Рассмотрим теперь частный случай а = 0. Поскольку а = Г^Tξ, матрица Г имеет неполный ранг, если пренебречь тривиальным случаем ξ = 0, рассмотрение которого не вызывает никаких затруднений. Тогда матрица В особенная, единичного ранга (нулевой ранг -это еще один тривиальный случай), и нам необходимо минимизировать выражение х^ТО^ТВОх. Эту задачу можно решить, введя поворот, который переводит собственный вектор матрицы В, соответствующий ее некоторому положительному собственному значению, в положение, ортогональное х. На этом наше обсуждение завершается.

Как и в случае предыдущей теоремы, интересно выяснить, как будут обстоять дела, если деформации ₂ - аддитивный шум - имеют дисперсию σ² = 0. Чтобы определить преобразования подобия s по деформированному изображению I^D= ₁1sI₀, нужно решить уравнение

(4.3.29)

относительно υ_x и О. В данном случае е обозначает вектор с единичными компонентами. Умножив предварительно на е^Т и решив это уравнение относительно υ_x, мы приходим к уравнению

(4.3.30)

Можно, исключив υ^x, получить уравнение, аналогичное уравнению (4.3.29), но с указанными подстановками и не содержащее члена υ_x. Умножаем это новое уравнение на Г^Т, так что

(4.3.31)

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

(4.3.32)

которое однозначно определяет поворот О в пространстве R². В этом случае преобразования подобия единственны, если наблюдается деформированное (спроектированное) изображение I^D₁.

Если, с другой стороны, матрица В имеет единичный ранг, то образующие g_j коллинеарны, и очевидно, что допустимы два вида поворотов - O и O^-1. На рис. 4.3.2 левое идеальное изображение I₁ соответствует прототипу с не особенной матрицей В, и очевидно, что преобразования подобия s единственные. Правое идеальное изображение I₂ соответствует коллинеарному прототипу, матрица В особенная, и, как показывает пунктир для I₂', допустимы повороты двух видов.

Рис. 4.3.2

Замечание 1. Было бы очень интересно обобщить наш последний результат на случай Y = R^p ДЛЯ произвольного р, когда деформации ' соответствуют проецированию в подпространство R^r, r < р. Особое практическое значение имеет случай р = 3 и r = 2.

Замечание 2. Вместо ортогональных проекций, введенных в теореме 4.3.2, можно воспользоваться центральными проекциями (см. разд. 4.6, т. 1). Тогда деформации могут быть представлены отношениями линейных функций и может оказаться необходимым прибегнуть к методу линеаризации.