Глава 4. Точечные образы

4.1. Точечные образы-решетки

Рассмотрим точечные образы-решетки, подобные описанным в разд. 3.5 т.1, на которые воздействуют деформации типа "пульсирующий кристалл" (см. разд. 4.2, т. 1).

Допустим, что идеальное изображение I представляет собой регулярную решетку в Rn, и, следовательно, ее точки имеют вид

(4.1.1)

здесь α-фазовый вектор, ξ₁, ξ₂,...,ξ_n - векторы базиса решетки и υ₁, υ₂,...,υ_n - произвольные целые числа. Естественно, векторы базиса не определяются однозначно.

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

(4.1.2)

где векторы шума n_{υ1υ2....υn} статистически независимы и характеризуются нормальным распределением с нулевым вектором математического ожидания и ковариационной матрицей R. Мы хотим по деформированному изображению восстановить идеальное изображение I, т. е., другими словами, определить векторы базиса (а может быть, также и фазовый вектор).

Ситуация такова. В некоторой заданной области, скажем кубе Q_L размера L, мы наблюдаем пульсирующие точки решетки, оказавшиеся в Q_L. С первого взгляда может показаться, что возникает регрессионная задача хорошо известного типа, поскольку соотношения (4.1.1) и (4.1.2) образуют линейную модель. Это действительно так, но лишь при низком уровне шума.

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

Во-вторых, если влияние пульсаций существенно, то упорядочение может оказаться нарушенным: мы не знаем, какие индексы υ₁, υ₂,...,υ_nсоответствуют данному наблюдаемому X. Это затруднение, насколько автору известно, не нашло еще освещения в литературе. Процедуры прямого оценивания оказываются вычислительно нереализуемыми, если они связаны с полным перебором перестановок индексов.

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

Мы действительно имеем дело с составным механизмом деформаций = ₁₂ причем ₂ представляет пульсации, вызванные аддитивным шумом, как в уравнении (4.1.2), а ₁ - маскирование, исключающее все наблюдения вне Q_L.

Наш анализ должен быть инвариантным относительно перестановок, и мы положим в его основу функцию (4.1.4), обладающую сходством с фурье-анализом. Однако на самом деле это не есть фурье-анализ стандартного типа: отметим, что тригонометрические функции при наблюдениях не перемножаются - вместо этого они появляются в показателе степени.

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

Мы начнем с простейшего случая, когда опорное пространство - ось действительных чисел, а шум -гауссов. Одномерный случай в действительности представляет незначительный интерес, так как его можно проанализировать более прямым способом (см. ниже). Будет поучительно, однако, рассмотреть сначала этот случай и выяснить, какого типа анализ необходим, а затем распространить его на двумерную задачу, которая собственно и представляет интерес.

Деформированное изображение представляет собой в данном случае множество точек:

(4.1.3)

где Q_L - интервал (0, L). Как указывалось выше, механизм деформации состоит из ₂ - аддитивного шума и ₁ - экранировки пространства, окружающего Q_L. Разумеется, число наблюдаемых точек заранее неизвестно. Мы принимаем допущение о том, что n_υ = N(0, σ²), но результаты можно распространить на случай шумов, обладающих распределениями более общего вида.

Сформируем "преобразование Фурье" по Бартлетту (1964) (см. также Бартлетт (1975):

(4.1.4)

Нам будет удобно реализовать анализ в комплексной форме.

Математическое ожидание m(λ) определяется как

(4.1.5)

здесь мы положили а = 0, что будет скомпенсировано позже умножением на e^iaλ. Введем теперь функцию

(4.1.6)

Благодаря равномерной сходимости (4.1.6) функция р непрерывна; кроме того, она положительная и периодическая с периодом ξ. Тогда

(4.1.7)

и, введя абсолютно сходящийся ряд Фурье

(4.1.8)

можно записать, что

(4.1.9(

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

Теперь мы должны выделить случай, когда λ - это k-е кратное 2π/ξ, тогда

(4.1.10)

Отметим, что если пользоваться определением р (4.1.8), то

(4.1.11)

Это означает, что p_k, убывая, стремится к нулю чрезвычайно быстро при стремлении |k| к бесконечности. Если же, с другой стороны, λ не есть кратное 2π/ξ, то сумма в (4.1.9) стремится к нулю. Следовательно, функция математического ожидания m(λ) будет представлена графиком типа приведенного на рис. 4.1.1,

Рис. 4.1.1

Теперь займемся оцениванием дисперсии:

(4.1.12)

Вклад членов

υ ≠ μ при определяем как

(4.1.13)

так как лишь при X_υ и X_μ∈Q_L они вносят вклад в φ(λ).

Далее следует просуммировать (4.1.13) по всем υ и μ, что дает в результате

(4.1.14)

учитывая только, что (4.1.13) несправедливо при υ = μ. Поэтому необходимо вычесть члены вида (4.1.13) для всех υ = μ, и добавить правильные выражения. Сделав это, получаем следующее:

(4.1.15)

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

(4.1.16)

поскольку

(4.1.17)

и мы ввели

(4.1.18)

- периодическую непрерывную и положительную функцию.

Покажем, что LV(λ) стремится к пределу при L → ∞. Очевидно, что

(4.1.19)

(см. (4.1.11)).

Для второго интеграла в (4.1.16) можно, не учитывая один из множителей L знаменателя, записать, что

(4.1.20)

где использована замена переменных

(4.1.21)

а множитель 2 в знаменателе порождается якобианом преобразования (4.1.21). Интервал интегрирования имеет вид

(4.1.22)

так что m(A(s))∼2L при фиксированных s. Тогда на основании сходимости мажоранты в качестве предела (4.1.20) получаем, что

(4.1.23)

Но из (4.1.18) следует, что

(4.1.24)

Объединяя последнее выражение о (4.1.16), получаем, что

(4.1.25)

Это означает, что мы доказали следующую теорему.

Теорема 4.1.1.Для восстановления идеального изображения решетки по деформированному изображению (4.1.3) мы строим функцию φ(λ), (4.1.4). Тогда при L → ∞ справедливо следующее:

(4.1.26)

и

(4.1.27)

Для дисперсии справедливо соотношение:

(4.1.28)

Важность данной теоремы определяется тем обстоятельством, что оно может служить нам средством, позволяющим избавиться от осложнений, возникающих в связи с маскирующим эффектом второго механизма деформации ₂ и отсутствием сведений об "истинном" упорядочении точек в I^D. Автору известно (Маклур (1975)), что ковариации также асимптотически стремятся к нулю в соответствии с (4.1.28).

Кроме того, данный метод при правильном применении показывает, как можно обнаруживать отклонения от постулируемой модели. Мы обсудим это позже.

Нужно вычислить функцию φ(λ) для довольно большого набора значений λ, зависящего от того, какими априорными сведениями относительно идеальной решетки мы располагаем. Затем следует построить графики действительной и мнимой частей φ и попытаться определить максимумы |φ(λ)|, особенно первый, который должен быть близок к 2π/ξ, если длина L достаточно велика. Величины нескольких первых максимумов позволяют нам также получить некоторое представление о а, исходя из характера убывания ординат (см. (4.1.26)). Могут оказаться полезными некоторые процедуры сглаживания, но здесь мы не будем обсуждать эту возможность.

Допустим теперь, что наблюдаются образы, которые порождены не деформацией линейной решетки, а имеют более хаотический характер. Предположим для начала, что пуассоновский процесс с интенсивностью р порождает множество {Х_υ}. Тогда получаем, что

(4.1.29)

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

Дисперсию можно получить также, если записать

(4.1.30)

где N - считающий процесс, соответствующий пуассоновскому процессу. Поскольку N - ортогональный процесс, для которого E[dN(x)]² = p dx, то

(4.1.31)

Эта величина стремится к нулю при L → ∞. Изучение φ(λ) должно помочь нам при решении вопроса о том, соответствует ли имеющимся данным образ регулярной решетки или более хаотическая пуассоновская модель.

В более общем случае для стационарного процесса восстановления мы получаем аналогичный результат для m(λ). В самом деле, пусть распределение промежуточных интервалов F не арифметрическое и характеризуется математическим ожиданием μ, так что расстояние от начала до первой наблюдаемой точки определяется как

и

(4.1.32)

Тогда

(4.1.33)

Воспользовавшись классическим результатом (см. Феллер (1957), т. 2, с. 354), получаем следующее:

(4.1.34)

поэтому

(4.1.35)

точно так же, как и для пуассоновского процесса.

В данном случае функцию дисперсии мы не получили.

Теперь посмотрим, как можно перейти к не гауссовому случаю. Вместо предположения о нормальности шума вводится весьма общее допущение о том, что члены, представляющие в (4.1.3) шум, характеризуются функцией распределения ξ, которая предполагается четной и интегрируемой с квадратом. Эти условия не являются необходимыми, но упрощают рассмотрение.

Введем функцию

(4.1.36)

этот ряд сходится почти везде. Очевидно, что функция неотрицательная и периодическая с периодом |. Теперь мы можем про

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

Вместо (4.1.7) получаем следующее:

(4.1.37)

и при L → ∞

(4.1.38)

если λ к не есть кратное 2π/ξ это выражение стремится к нулю.

В противном случае λ = 2πk/ξ и

(4.1.39)

Для дисперсии, аналогично уже рассмотренному частному случаю, получаем следующее:

(4.1.40)

где

(4.1.41)

Сделав замену переменных, записываем второй интеграл в (4.1.40) как

(4.1.42)

Здесь

(4.1.43)

при s > 0; аналогичное выражение справедливо для отрицательных s. Благодаря периодичности для любого s

(4.1.44)

Кроме того, поскольку функция распределения f положительна, ядро K_L мажорируется кратным ядра K. Однако K принадлежит L₁ поэтому

(4.1.45)

Если преобразование Фурье от f обозначить через , то мы приходим к следующей теореме.

Теорема 4.1.2.Если шум характеризуется четной и интегрируемой с квадратом функцией распределения f, то

(4.1.46)

кроме того,

(4.1.47)

Пусть теперь идеальное изображение состоит из точек:

(4.1.48)

где фаза а и векторы базиса ξ₁ и ξ₂ принадлежат R². Эти векторы, естественно, не определяются решеткой однозначно. Введем также обратную решетку R с базисными векторами η₁ и η₂ так, что

(4.1.49)

Деформированное изображение снова вводится с помощью = ₁₂ а, но члены, представляющие шум, являются в данном случае векторами на плоскости и характеризуются двумерной функцией распределения f, a ₁ определяет маскирование за пределами квадрата Q_L со стороной L.

Введем

где λ - фиксированный вектор на плоскости. Для математического ожидания имеем следующее:

(4.1.51)

Здесь

(4.1.52)

Этот ряд почти везде сходится к неотрицательной функции с периодами ξ₁ и ξ₂, принадлежащей R². Теперь снова свернем р на одном из фундаментальных параллелограммов Р исходной решетки, учитывая, что

(4.1.53)

где Х₀∈Р и X = X₀ + υ₁₁ + υ₂ξ₂, так что

(4.1.54)

если X представляется через параметры обратной решетки R:

(4.1.55)

Это означает, что при суммировании геометрического ряда по параллелограммам, принадлежащим Q_L (сравните с (4.1.38)),

(4.1.56)

и, следовательно, если λ∉2πR, то

(4.1.57)

Если λ∈2πR, так что λ = 2π(h₁η₁ + h₂η₂), где h₁ и h₂ целые, то

(4.1.58)

где ψ - угол между двумя базисными векторами в исходной решетке.

Итак, для дисперсии имеем следующее:

(4.1.59)

где u и υ принадлежат R², а

(4.1.60)

Эти выражения аналогичны выражениям (4.1.40) и (4.1.41) и, проводя анализ подобно тому, как это было сделано выше, приходим к непосредственному аналогу выражения (4.1.45).

Теорема 4.1.3. Для двумерной решетки с базисными векторами ξ₁ и ξ₂ и обратной решетки R (см. (4.1.49)) среднее функции (4.1.50) определяется асимптотически как

(4.1.61)

Асимптотическая дисперсия равна

(4.1.62)

где Р - фундаментальный параллелограмм исходной решетки, - двумерное преобразование Фурье f.

В приложениях значение фазы а неизвестно, но так как это влияет лишь на φ(λ), то при помощи умножения на множитель е^i(λ,a) абсолютная величина которого равна единице, мы получаем возможность работать с |φ(λ)| и отыскивать наибольшие локальные максимумы. Рассмотрим первый локальный максимум k = 1 в (4.1.46) и обратимся для начала к одномерному случаю.

Можно ожидать, что значение ординаты приближенно равно (при k = 1)

(4.1.63)

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

(4.1.64)

Если (4.1.64) по порядку совпадает с (4.1.63) или превышает его, то мы не можем рассчитывать на обнаружение максимума. Такая ситуация возникнет, если

(4.1.65)

откуда следует, что

(4.1.66)

При n = N (0, σ²) мы имеем

и неравенство (4.1.66) принимает вид

(4.1.67)

Если, с другой стороны, n = R(-d, d), то

(4.1.68)

Следовательно, учитывая (4.1.66), можно считать допустимыми такие значения d, при которых справедливо неравенство

(4.1.69)

Если d мало, то это условие, конечно, приводит к малым значениям L, однако, когда d достигает значения 1/2, это условие "взрывается". При d = 1/2 любой объем выборки оказывается недостаточным для принятия решения об образе. Причина, совершенно очевидно, заключается в том, что функция р (4.1.36) в данном случае тождественно равна постоянной.

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

Рис. 4.1.2

В двумерном случае трудности проявляются в полной мере, так как здесь уже важна структура направлений решетки. В качестве численного примера рассмотрим идеальное изображение, приведенное на рис. 4.1.2; здесь

(4.1.70)

а базисные векторы обратной решетки равны

(4.1.71)

Вычислим значение φ для кратных векторов η₁ и η₂, а и для векторов

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

Рис. 4.1.3

Рис. 4.1.4

Рис. 4.1.5а

Рис. 4.1.5б

Рис. 4.1.5в

Рис. 4.1.6

Рис. 4.1.7а

Рис. 4.1.7б

Рис. 4.1.7в

Деформированная решетка, приведенная на рис. 4.1.4, дает графики ψ = φ/, соответствующие ориентациям η₁, λ₁ и λ₂. Эти графики показаны на рис. 4.1.5 а, б и в соответственно.

Мы видим, что умеренно деформированная решетка, приведенная на рис. 4.1.4, приводит к появлению функций ψ, имеющих вполне определенный максимум около 1 в случае (а), но не имеющих его в случаях (б) и (в). Это именно тот тип поведения, который нас интересовал.

Что касается хаотической картины типа представленной на рис. 4.1.6, где изображена сильно деформированная решетка, то с функцией соответствующей ориентации λ₁ и имеющей максимум вблизи 1 (см. рис. 4.1.7а), все в порядке: точно так же все в порядке и с функцией ψ, соответствующей ориентации λ₁ и не имеющей явных максимумов (см. рис. 4.1.76). С другой стороны, показанный на рис. 4.1.7в график, соответствующий ориентации λ₂, имеет слабо выраженный максимум в точке 1,0 и более выраженный максимум в точке 1,5. Следовательно, деформации оказались слишком велики для того, чтобы оказалось возможным восстановление с хорошим качеством при выборке заданного размера.

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