4.5. Неполные наблюдения

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

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

Определение 4.5.1. Пусть для заданного семейства множеств деформированное определяется как сужение изображения-соответствия I на

В таком случае называется окном деформации и отождествляется с называется деформацией маски.

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

Наблюдения в принципе не определяют однозначно. Изображение позволяющее при данном окне получить данное называется совместимым с деформированным изображением.

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

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

Теорема 4.5.1. Пусть одиночное окно есть множество, определяющее связи. В таком случае деформация маски (4.5.1) есть гомоморфизм.

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

Следовательно, согласно теореме 3.1.2, достаточно показать, что используется правило идентификации более грубое, чем правило, приводящее к Очевидно, однако, что является дозволенным правилом идентификации (см. четыре условия, сформулированные в определении 3.1.1). Отметим, во-первых, что действует в два этапа: сначала применяется а затем (4.5.1), — поэтому означает, что имеют одинаковые внешние связи и представляют одну и ту же функцию, определенную на окне откуда следует, что отношение эквивалентности. Кроме того, должны обладать одинаковыми показателями связей. В таком случае выполнены два последних условия определения (3.1.1), так что действительно правило идентификации. Разумеется, точнее и, следовательно, доказательство завершено.

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

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

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

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

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

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

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

Такие деформации не зависят в явном виде от идеального изображения; обычно они налагаются на X посредством процедуры

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

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

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

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

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

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

Теорема 4.5.2. (Кендалл (1948)). Величина есть случайная переменная со средним значением и дисперсией такой, что

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

Доказательство. Значение зависит от и является периодическим относительно обеих переменных с периодом единица; воспользуемся формальным разложением в ряд Фурье на основном интервале

где

F - индикаторная функция окружности с центром (0,0) и радиусом Следовательно,

если в остальных случаях.

Каковы бы ни были свойства сходимости разложения (4.5.4), мы по меньшей мере остаемся в классе и поэтому на основании равенства Парсеваля получаем

(отбросив член )

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

Итак, среднее значение определяется как

а дисперсия ограничена величиной

С другой стороны,

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

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

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

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

Теорема 4.5.3. (задана Бюффона об игле). Среднее значение случайной переменной равно

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

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

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

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

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

Теорема 4.5.4. (Уикселл (1926)). Если имеет конечное среднее значение плотность распределения диаметров окружностей, то

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

В таком случае для совместной плотности распределения у и получаем следующее:

замена переменных на в том числе в якобиане подстановки, приводит к плотности распределения

Так как то плотность распределения имеет следующий вид:

Это интегральное уравнение Абеля, и оно может быть решено непосредственно (см., например, монографию Кануола (1971), стр. 167—170), что приводит к решению (4.5.1).

Если заменить сферы эллипсоидами, то можно получить сходные результаты (см. работу Уикселла (1926)).

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

Случай 4.5.2 (пуассоновские окна). Для заданного изображения-соответствия на X рассмотрим множество реализаций пуассоновского процесса на X с интенсивностью относительно -инвариантной меры

Пусть для определенности - группа переносов и область Лебега. Если состоит из выпуклых множеств на плоскости (см. случай 3.5.9), то деформированное изображение будет состоять из точек плоскости, причем плотность распределения этих точек будет определяться функцией Важный частный случай возникает при

так что все деформированное изображение заключено в Такое будет подробно изучаться в гл. 12 (см. приложение).

По мере увеличения X будет расти также (по вероятности) число точек и хорошо известно, что условное по распределение на I равномерно. Рассмотрим поведение множества дрейфа в этом случае.

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

удовлетворяет условию

где — диаметр в направлении Кроме того, линейный размер в направлении определяется как

и имеет функцию распределения с пределом

Доказательство, Обозначим индикаторную функцию через Множество дрейфа можно охарактеризовать с помощью точек деформированного изображения:

откуда следует, что также выпуклое.

Теперь индикаторная функция множества принимает вид

так что

Точки стохастически независимы и характеризуются плотностью распределения так что

где ядро К определяется выражением

Следовательно, оно неотрицательно и ограничено единицей, которая достигается при

Если вектор мал и ориентирован в направлении то

замена переменной, после которой следует стандартная процедура предельного перехода, позволяют получить следующее:

или в полярных координатах:

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

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

Аналогичная задача была решена для других групп преобразований подобия (см. работу Гренандера (1973)).

Родственные встречаются при изучении образов, связанных с гипотезами и индуктивным мышлением (см. разд. 3.9). В этом случае в роли X выступает булево пространство с элементами - считающая мера. Гипотеза, представленная изображением-соответствием имеет множество истинности, которое можно отождествить с где булева функция принимает значение «истина».

При увеличении к увеличивается также Действительно, если ввести размер множества разности

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

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

в множество а остальные значения характеризуют шум.

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

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

Случай 4.5.3 (выборочные деформации). Пусть - вероятностная мера на образована точками из X, полученными в результате независимо одинаково распределенной кратной выборки из

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

Введем диффузный образ изображений-мер. Пусть а — конечная мера на Определим меру на потребовав, чтобы для любого разбиения случайный вектор имел распределение Дирихле с параметрами Напомним читателю, что это означает наличие у вектора функции распределения

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

Эти безусловные распределения удовлетворяют условиям теоремы Колмогорова о совместимости и определяют вероятностную меру распределений на Доказательство этого факта, а также обсуждение соответствующих проблем, связанных с теорией меры, можно найти в работе Фергюсона (1973). Основным результатом является следующая характеристика поведения

условного распределения вероятностной меры после наблюдения

Теорема 4.5.6. (Фергюсон (1973)). При сформулированных условиях условное распределение вероятностных мер является распределением Дирихле, причем мера а заменяется мерой представляет точечную вероятностную , сосредоточенную в точке

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

Еще один тип деформаций возникает при рассмотрении изображений-соответствий в строгом смысле. Пусть сопоставленное пространство и деформированные изображения определены на X соглано (4.5.31).

Случай 4.5.4 (фильтрующие деформации). Для изображения-соответствия определим

интегрирование осуществляется на X по S - инвариантной мере ; К — заданное действительное ядро.

Разумеется, следует принять обычные предосторожности для того, чтобы интеграл (4.5.31) имел смысл, однако делаться это будет отдельно в каждом конкретном случае в части III.

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

С помощью дополнительного условия инвариантности устанавливаем, что соответствует изображению

а изображению, принимающему значения

(используется инвариантность меры Следовательно, этот механизм деформаций ковариантен.

Остановимся на трех примерах фильтрующих деформаций, известных из техники связи.

Пусть идеальные изображения принадлежат и -мера Лебега. Пусть ядро свертки, , где принадлежит . В таком случае, взяв преобразование Фурье, получаем почти всюду

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

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

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

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

где собственные элементы симметричного интегрального уравнения

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

Определим ядро К:

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

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

таким образом, чтобы математическое ожидание средней квадратичной ошибки минимизировалось (при фиксированном ):

Теорема 4.5.7. Из всех линейных аппроксимаций вида (4.5.40) минимум ошибки обеспечивает аппроксимация (4.5.38).

Доказательство. Ничто не мешает нам предполагать ортонормированность так как ее всегда можно обеспечить посредством линейного преобразования, которое может привести к меньшему числу Если это так, то наилучшие будут «коэффициентами Фурье»:

тогда

В таком случае следует выбрать таким образом, чтобы сумма во втором члене правой части (4.5.43) была максимальной

С другой стороны,

и

Так как , из неравенства Бесселя следует, что

Следовательно, экстремум обеспечивается, если в остальных случаях (напомним, что X не возрастают), откуда следует, что при и тогда

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

Если в случае 4.5.4 X — конечное множество со считающей мерой то изображения являются векторами и К можно представить в виде матрицы. Если, в частности, К не имеет обращения, так что отображается в собственное подпространство то при применении происходит потеря информации Этот тип деформаций характерен для теории систем.