3.5. Плоские образы

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

Правильная структура, показанная на рис. 3.5.2, представляет собой плоский кристалл.

Пусть Б — тип связи, задаваемый рис. 3.5.1. Каждая образующая имеет арность, равную 8 (двойные стрелки); показатели связей где принимает значения 1, 2, 3, 4, соответствуют направлениям а и принимает значения что соответствует или «-компоненте. В качестве отношения связи выберем «равенство». Образующая имеет признак показатели связей вычисляются при помощи соотношений

и аналогично для значений

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

Случай 3.5.1 (плоский кристалл). Рассмотрим изображение, заданное в виде решетки

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

Рис. 3.5.1.

Введем новые векторы.

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

Или, с учетом линейной независимости

и

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

где .

причем является целым числом. (3.5.8)

Рис. 3.5.2.

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

Исходя из (3.5.2), для эквивалентного базиса легко получаем

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

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

Тогда, если

то

Это упростит в дальнейшем вычисление коэффициентов ряда Фурье. Отметим, что площадь фундаментальной клетки V равна

что непосредственно следует из (3.5.11).

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

В этом случае изображение однозначно определяет преобразование подобия при заданном прототипе

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

Случай 3.5.3. Стационарный пуассоновский процесс характеризуется условиями:

1. для множества А с площадью есть пуассоновское распределение со средним

2. если непересекающиеся множества, то стохастически независимы.

Здесь мы используем обозначение для числа точечных образующих в А.

Рис. 3.5.3.

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

Случай 3.5.4. Центрально-сопутствующий процесс Неймана (1939) образуется в 2 этапа. Сначала по пуассоновскому процессу получают центры. На втором этапе, исходя из центра определяют по заданному распределению число сопутствующих ему точек и, наконец, по функции распределения получают точек.

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

В более общем случае произвольные стационарные точечные образы можно охарактеризовать по их ковариациям и спектральным плоскостям; для этого читатель может обратиться к работе Бартлетта (1964).

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

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

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

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

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

Каждая образующая будет иметь две концевые точки и

Регулярными конфигурациями будут конфигурации, удовлетворяющие данным отношениям согласования, когда концевые

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

В качестве простого примера такого типа алгебры изображений рассмотрим следующие три класса образующих:

Отношения согласования таковы:

где и заданные функции. Типичный образ такого типа показан на рис. 3.5.5.

Рис. 3.5.4.

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

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

можно отождествить ее с истинностным множеством (полуплоскостью) свойств в линейной пороговой логике (см. разд. 3.9). Используемая здесь р-мера

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

Рис. 3.5.6.

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

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

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

Рис. 3.6.6. (см. скан)

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

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

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

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

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

На рис. 3.5.6 проиллюстрирован случай 3.5.5, где

евклидово расстояние,

Выше мы полагали, что полная группа евклидовых движений, так что сеть должна иметь изотропную грубую топологию. Пусть теперь — группа параллельных переносов, так что свойство изотропности теряется, однако мы по-прежнему будем использовать термин «статистически однородная топология». В качестве иллюстрации приведем рис. 3.5.7, считая заданной соотношением (3.5.21), но, предполагая расстояние неизотропным:

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

Другой образ диффузной сети, использованный при геоморфологическом исследовании дренажных систем, использует источников при Е — «дерево». Отношение сводится к тому, что начальная точка новой дуги лежит на предыдущей дуге. Также предполагается, что звенья (сегменты либо от источника, либо узла внизу по течению до следующего узла или до выхода) соединяются лишь попарно. Внешние звенья начинаются от источников. Рис. 3.5.8 соответствует случаю и 0 — обозначает выход. Числа задают «величину» этих звеньев,

Рис. 3.5.7. (см. скан)

равную числу источников, расположенных вверх по течению, причем эти величины приписываются узлам. Их значения равны 1 на источнике и на выходе, как это показано на рисунке.

Более информативным признаком является число потоков по Хортону и Стралеру (см., например, Хортон (1945), Шрив, (1966, 1967, 1969), Уэрритти (1972), Смарт (1972)). Один из

вариантов определения этой величины по Стралеру таков:

(i) потоки, начинающиеся от источников, имеют порядок

(ii) два встречных потока порядка со создают поток порядка (3.5.24)

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

Рис. 3.5.8.

Рис. 3.5.9.

Соответствующий пример приведен на рис. 3.5.9.

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

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

Аналогичными рассуждениями получаем

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

число звеньев на 2, а число узлов на

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

так что последовательность является «почти» геометрической прогрессией. Следовательно, величины могут в какой-то мере характеризовать сеть. Хортой также установил, что обычно довольно близко к 4.

Рис. 3.5.10.

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

где средняя длина потоков в сети порядка .

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

Для заданного числа источников можно, по крайней мере в принципе, перечислить (топологически) различные сети. При

существуют 14 вариантов, показанных на рис. 3.6.11 с указанием соответствующих чисел потоков.

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

Теорема 3.5.1 (Шрив, 1966). Для системы каналов с источниками число топологически различных сетей удовлетворяет соотношению

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

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

Чтобы оценить сверху при больших , попытаемся проверить справедливость неравенства

Допустим, что оно справедливо при . Тогда

но

Рис. 3.5.11. (см. скан)

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

которая сходится для малых значений

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

Здесь выбрана та ветвь квадратного корня, при которой

Тогда коэффициентом при в ряде Тейлора для в точке при будет

Чтобы доказать (3.5.31), рассмотрим потоков порядка . Из них потока должны объединяться в пары, чтобы образовать потоков следующего, более высокого порядка. Тогда останутся потоков порядка , которые входят в звеньев по крайней мере порядка , до того как объединятся потоки меньшего порядка. Но каждый из оставшихся — потоков может объединиться со звеньями слева или справа, что приводит к появлению сомножителя

Число различных распределений объектов в ячейках (см. Феллер (1957), I) равно

Если здесь положить , то мы придем к выражению (3.5.31).

Эта теорема непосредственно связывает вероятностную меру с дискретными вероятностями

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

Случай 3.5.7 (топологические случайные сети каналов). Введем на множестве всех сетей с источниками вероятностное распределение классов образов, приписывая последним вероятности в соответствии с (3.5.38).

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

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

Теорема 3.5.2 (Шрив, 1967). Вероятность звена порядка со равна

вероятность звена, имеющего «величину» равна

Вероятность потока порядка равна

Таблица 3.5.1 (см. скан) Вероятности чисел потоков при

Доказательство. Введем совместную вероятность звена «величины» р и порядка . Тогда это соответствует внешнему звену, и известно, что внешние и внутренние звенья встречаются одинаково часто (см. (3.5.37)). Если больше единицы, то пара недопустима, так что Аналогично при

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

Мы можем также иметь соединение узла порядка со звеном порядка где Это происходит с вероятностью

при фиксированном а, и конечно, упомянутые два звеиа взаимозаменяемы, поэтому выражение в (3.5.42) следует удвоить. Комбинируя (3.5.41) и (3.5.42), получим рекуррентное соотношение

с граничными условиями, сформулированными выше. Суммируя (3.5.33) по для маргинальных вероятностей имеем:

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

С другой стороны, если просуммировать (3.5.43) по то получим

Но

так что

Отсюда

что при подстановке в (3.5.47) дает

откуда

что и утверждалось.

Наконец, чтобы получить вероятность потоков порядка достаточно заметить, что они в точности соответствуют звеньям, имеющим соединения типа Используя (3.5.50), имеем

что и завершает доказательство теоремы.

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

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

Читатель, интересующийся нетопологическими свойствами сетей каналов, т. е. метрическими свойствами, такими, как длины потоков и площадь бассейна, может обратиться к работам Шрива (1969), Смарта (1972), Уэррити (1972).

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

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

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

Случай 3.5.9. Рассмотрим алгебру изображений состоящую из замкнутых ограниченных выпуклых множеств в плоскости и из трех операций:

пересечения, умножения на скляр при

и сложения по Минковскому

В частности, если Ко состоит из одной точки то сложение Ко с К означает перенос К на вектор Если Ко — отрезок прямой как на рис. 3.5.12, а, то сложение с Ко означает растяжение в направлении этого отрезка: отрезок прямой складывается с эллипсом. Сложение с где единичный круг . означает образование параллельного множества на расстоянии с вне (см. рис. 3.5.12,б, где круг складывается с квадратом).

Топология в вводится при помощи метрики Хаусдорфа:

Вышеупомянутые операции непрерывны в этой топологии.

Удобно охарактеризовать выпуклые плоские множества опорной функцией :

Ее геометрический смысл иллюстрируется на рис. 3.5.13. Функция непрерывна и периодична с периодом

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

Рис. 3.6.12.

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

Следующий результат дает полезное представление опорной функции.

Теорема 3.5.3 (Р. Вайтал, 1974). Для того чтобы была опорной функцией множества в необходимо и достаточно, чтобы она могла быть представлена в виде

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

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

и положим Далее находим, что

Рис. 3.6.13.

Для любой выпуклой комбинации

имеем

У нас есть, однако, интегральное неравенство

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

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

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

С другой стороны, если К — произвольный выпуклый компактный многоугольник, его всегда можно аппроксимировать в метрике Хаусдорфа. Для такого многоугольника опорная функция может быть записана в виде

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

Если К имеет непрерывный радиус кривизны то дважды дифференцируема и

так что в данном случае радиус кривизны просто равен Далее интегрируя (3.5.68), получим

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

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

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

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

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

Эту алгебру изображений можно описать в терминах границы.

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

Доказательство. Пусть так что оно может быть представлено виде (3.5.70). Если конечное множество, то состоит из конечного числа дуг из , и неравенство (3.5.71) сводится к равенству, выполняемому всюду, за исключением углов . С другой стороны, если бесконечно, то можно аппроксимировать Е при помощи множества , где Е имеет конечное представление и оно как угодно близко к Е. Пусть два угла, такие, что соответствующие точки на не являются угловыми. Аналогично обозначим через точки на Е, соответствующие тем же углам (см. рис. 3.5.14) и отмеченные крестиками. Рассмотрим дугу, соединяющую два угла из и дугу из Б, соответствующую тем же значениям

Первая дуга имеет по крайней мере такую же длину, как и вторая дуга. Суммируя, получим

где обозначает длину дуги, соединяющей а и Второе неравенство выполняется потому, что имеет скачки в угловых точках Перейдя к пределу в (3.5.72), мы получим неравенство

откуда следует (3.5.71).

Рис. 3.6.14.

Рис. 3.6.16.

Обратно, пусть для замкнутого множества Е выполнено не равенство (3.5.71). Рассмотрим точку на Е, не являющуюся угловой (см. рис. 3.5.15). Радиус-вектор пересекает в точке Здесь Е обозначает перенос который переводит точку из с углом в точку Р.

Обозначая через единичный вектор в направлении а, имеем (здесь ds - элемент дуги )

и аналогично

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

Пусть и — единичный вектор в точке перпендикулярный к опорной прямой (см. рис. 3.5.15), — образует скалярное произведение

и аналогично

Тогда из неравенства (3.5.71) получим

если только в подынтегральной части неотрицателен. Следовательно, . Учитывая геометрический смысл имеем, что опорная прямая в направлении для Е простирается дальше, чем для Е. Это обстоятельство, вместе с аналогичными утверждениями для остальных значений приводит к условию . Теперь мы формируем пересечение всех подмножеств, аналогичных Е для всех начальных точек Р на границе Е. Отсюда следует, что это пересечение, имеющее вид (3.5.70), содержит Е. Однако оно должно совпасть с Е, так как любая точка может быть отделена от Е при помощи «опорной кривой», проходящей через некоторую точку Р на Принимая во внимание построение (см. рис. 3.5.15), получаем, что исключается из Е. Этим завершается доказательство теоремы.

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

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

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

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

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

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

Множество является выпуклым конусом в

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

Во-первых, если при всех то Во-вторых, если обе функции непрерывны в точке то из следует, что Это вытекает из того, что

В-третьих, если то

Теорема 3.5.5. Для того чтобы множество с непрерывным радиусом кривизны принадлежало алгебре изображений определенной как в случае 3.5.11, необходимо и достаточно, чтобы для каждого а существовал хотя бы один индекс такой, что мажорируется по косинусу посредством .

Доказательство. Чтобы доказать достаточность, допустим, что а — произвольный угол. Сопоставим ему некоторый индекс и множество перенесенное в точку из соответствующую а Используя такие же рассуждения, как при доказательстве теоремы 3.5.4, получаем, что содержит Е. Поэтому их пересечение совпадает с Е, так что

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

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

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

Если ослабить ограничение, наложенное на прототип, например, считать дополнением клина с углом 90° (см. рис. 3.5.16, а) множествомвсех евклидовых движений, то мы получим многоугольные изображения Заметим, что в терминах простых признаков линейной пороговой логики прототип может быть записан в виде

(см. разд. 5.9), где

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

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

Рис. 3.5.16. (см. скан)

Случай 3.5.13. Построим алгебру изображений, состоящую из всех изображений вида

где задается по (3.5.82) и состоит из всех параллельных переносов и вращении на углы, кратные

Знак конъюнкции в (3.5.84) можно объяснить тем, что определенные открытые квадранты должны быть исключены. Здесь некоторая точка в плоскости, причем является угловой точкой квадранта соответствует обычной нумерации квадрантов.

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

Заметим, что могут быть образованы самое большее четыре фигуры (одна на рис. 3.5.17), необязательно связано и угловые точки могут разделять компоненту на 2 части.

Рис. 3.5.17.

Лемма 3.5.1. Рассмотрим произвольное изображение из и пересечем его горизонтальной прямой Результирующее множество

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

Доказательство. Используя представление (3.5.84), легко получим, что

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

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

Пусть I имеет конечную численную сложность (по определению оно имеет структурную сложность, равную 2). Будем рассматривать лишь ограниченные, связные изображения. Граница состоит из вертикальных и горизонтальных отрезков прямых, образующих внутренние и внешние углы. Роль «щупалец» довольно очевидна, и можно предположить, что они отсутствуют без существенного ограничения общности. Более подробно обсудим это ниже. Можно записать, что

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

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

Теорема 3.5.6. Пусть I — изображение без «щупалец», ограниченное, связное и имеющее конечную численную сложность. Тогда состоит самое большее из четырех дуг, каждая из которых в свою очередь состоит из чередующихся вертикальных и горизонтальных отрезков прямых, как в (3.5.82), и из внутренних углов, чередующихся с внешними углами Дуги соединяются в вершинах внешних углов. Обратно, если I — замкнутое, связное, ограниченное, множество с границей обладающей описанными выше свойствами, то его можно представить в виде (3.5.87) с конечным множеством признаков.

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

Чтобы рассмотреть вопрос о «щупальцах», достаточно отметить, что в данное изображение без «щупалец» на любом из четырех (самое большее) экстремальных интервалов, где х или у

соответственно достигаю! своих минимумов или максимумов, можно ввести «щупальца». Обратно, любое «щупальце» должно максимизировать или минимизировать или у.

Можно также рассмотреть случай, когда численная сложность бесконечна. Пусть, например, ограничено, связно и имеет границу с непрерывной касательной. Теперь в соответствии с построением получим 4 дуги с касательными. Переход от дуги к дуге происходит так же, как в (3.5.88).

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

Теорема 3.5.7. Ограниченное, связное изображение I со структурной сложностью, равной 2, и непрерывной касательной имеет границу, которую можно разбить на четыре дуги, такие, что направление касательной к а, - лежит в квадранте (сложение по модулю 4). Обратно, замкнутое, ограниченное, связное множество I с непрерывной касательнойг. удовлетворяющей указанному условию, в данной алгебре изображений имеет структурную сложность, равную 2.

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

Ни один из исключенных квадрантов в (3.5.89) не пересекает I ввиду ограничения на направление касательных к Следовательно, . С другой стороны, и доказательство теоремы легко завершается.

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

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

Принимая в качестве отношения связей

н считая, что тип соединения Е — «полный», будем считать две конфигурации идентичными, когда результирующие объединения образующих совпадают:

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

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

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

Например, если является заданной функцией от то мы получаем изображения на средней линии, как на рис. 3.5.18 (см. Блам (1967)). Изображение линии называется скелетом фигуры, а функцией затухания.

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

Для изучения метрического аспекта изображений рассмотрим полуплоскости, выбираемые случайно и, как прежде, удовлетворяющие отношению связей «не следует». С некоторой потерей общности предположим, что полуплоскости задаются неравенствами

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

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

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

Пусть и

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

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

Рис. 3.5.18.

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

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

Введем следующие функции:

будем считать, что

Тогда, согласно теории экстремумов, получим

Но при так что при нормировке где

Иными словами, нами получена

Теорема 3.5.8. Если изображение нормируется посредством деления на и выполнено (3.5.90), то предельная мера задается соотношением

В частности, одномерное маргинальное распределение задается при помощи

а двумерное маргинальное распределение при — равенством

где — корень уравнения

Рассмотрим случай Тогда (3.5.103) сводится к экспоненциальному распределению со средним значением Ковариационную функцию можно получить из (3.5.104) интегрированием по частям; скажем, при

Следует отметить, что здесь зависит от Ковариационная функция в (3.5.105) непрерывна по что легко установить, возвращаясь к представлению в (3.5.102). Подынтегральная функция также дифференцируема, и ее производная ограничена интегрируемой функцией, так что дифференцируема, причем Однако она не является дважды дифференцируемой. Граница изображения такова, что, если ее. выразить в полярных координатах, она окажется непрерывной (но не дифференцируемой) по среднему значению. В иллюстративных целях мы построили имитационную модель для изученной выше алгебры и показали пять реализаций на рис. 3.5.19. Значения для случаев соответственно таковы: —8/9, 0, 1, 9, 19. Число образующих равно 100.

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

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

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

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

или в действительной форме

Здесь А — амплитуда, фазовый угол, -частотный вектор.

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

Рис. 3.5.19. (см. скан)

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

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

Если градиент обращается в нуль,

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

Рис. 3.5.20. (см. скан)

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

В разд. 3.6 обсудим понятия холмов, оврагов, проходов и т. д., с помощью которых можно дать топологическую характеристику сопоставленного изображения, когда значение соответствует высоте. Другая характеристика изображения дается в терминах текстуры; например, шероховатость является мерилом отклонения от линейности. Абсолютная шероховатость на множестве Е задается при помощи выражения

а относительная шероховатость — посредством

где обозначает норму изображения в

Случай 3.5.14 (плоские изображения Фурье). Пусть образующие задаются как в (3.5.106), причем индекс образующей параллельные переносы. Тип соединения 2 — «полный». Пусть показатели связей, равные а, имеют бесконечную арность, и отношение связей «различие». Две регулярные конфигурации считаются идентичными, если при всех

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

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

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

должен быть квадратным корнем -меры прямоугольника соответственно со сторонами

Чтобы была регулярной, надо допустить, что частоты могут быть различными, и считать, что и I принимают все значения от до Тем самым на определяется Р-мера. Интересно отметить, что при вероятностная мера сходится к вероятности стационарного гауссова стохастического

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

так что просто является спектральной мерой процесса.

Это представление может быть использовано при вычислении различных параметров изображения. Например, ожидаемая абсолютная шероховатость (см. (3.5.109)) задается в виде

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

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

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

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

Случай 3.5.15 (прямые топографические изображения). Если задано полный и различие, то мы получаем пространство конфигураций, в котором конфигурации будут идентифицироваться точно так же, как в (3.5.106).

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

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

Таблица 3.5.2 (см. скан)

Рис. 3.5.21. (см. скан)

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

где причем Переменные являются независимыми случайными

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

Теперь перейдем к образам кривых. Рассмотрим два изображения, :

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

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

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

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

Если то мы скажем, что получается (малым) сдвигом Тогда для Н получим приближенное равенство

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

Пусть - архимедова спираль:

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

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

Рис. 3.5.22.

Пусть , тогда

Если а мало, данное соотношение приближение заменяется

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