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

Глава 3. Изображения

3.1. Алгебра изображений

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

Определение 3.1.1. Отношение между конфигурациями из называется правилом идентификации, если:

(i) R является отношением эквивалентности,

(ii) если с то имеют одни и те же внешние и внутренние показатели связей,

(iii) если то для любого

(iv) если регулярны и то имеем

Классы эквивалентности называются изображениями и в общем случае обозначаются через а множество всех изображений — через

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

На множестве задается алгебраическая структура.

Теорема 3.1.1. На могут быть однозначно заданы преобразования подобия и однозначно определены комбинации

для изображений если связи в а соответствуют их внешним связям. Тогда

если внешние связи реализуются посредством а.

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

Доказательство. Явное определение однозначно, так как если то (см. пункт (iii) определения 3.1.1). Аналогично явное определение при условиях, что и внешние связи реализуются посредством а, также однозначно. Это следует из пункта определения 3.1.1. Чтобы доказать пункт теоремы, достаточно заметить, что если имеют внешние связи, соединяемые посредством , то справедливо аналогичное утверждение относительно (см. разд. 2.2), так что правая часть имеет смысл. Тогда обе части доказываемого соотношения должны быть равными, поскольку мы имеем эквивалентность по модулю между двумя выражениями, полученными заменой соответственно двумя его конфигурациями (см. теорему 1.2.1). Утверждение доказывается аналогичным образом.

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

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

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

Вероятностная мера Р на индуцирует вероятностную меру на при помощи соотношения

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

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

Тривиальное правило задается при помощи равенства между конфигурациями, а именно, тогда и только тогда, когда с Конечно, в этом случае имеем

Другое правило появляется тогда, когда все регулярные конфигурации имеют нулевую арность, и мы полагаем тогда и только тогда, когда состав равен составу (с): идентификация по составу.

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

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

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

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

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

Рассмотрим алгебру изображений с моноатомным типом соединения (см. разд. 2.2). Тогда для любых двух образующих соответствующие конфигурации

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

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

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

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

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

Комбинируя это с пунктом определения 3.1.1, получаем что и утверждалось.

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

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

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

Рис. 3.1.1.

Теорема 3.1.3. Пусть Н — гомоморфизм определяем посредством тогда и только тогда, когда

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

Доказательство Очевидно, что рефлексивно, симметрично и транзитивно, следовательно, оно является отношением эквивалентности и условие определения 3.1.1 выполнено. Если так что то отсюда следует, что следовательно, условие выполнено.

Пусть снова имеем Тогда

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

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

Доказательство Свойство определения 3.1.2 выполнено, поскольку, если так что содержатся в общем -изображении, то Также, если то для любого с мы должны иметь поэтому М переводит в соответствии со свойством Наконец, если соответствует по и

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

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

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

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

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

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

Тогда нормальная подгруппа Действительно, для любого и некоторого имеем

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

Основываясь на определении алгебры изображения, мы формализуем понятие образа в соответствии с обсуждением, проведенным в гл. 2.

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

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

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

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

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

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

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

Аналогично, некоторое изображение может быть выведено из двух (или большего числа) изображений где Интересным является случай, когда трактовка операции «X» более сложная, чем какой-либо обычной бинарной операции на скажем, интерферирует с в некотором смысле. Муаровые образы, рассматриваемые в разд. 3.5, вы водятся из пар изображений.

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