Декомпозиционный метод построения образов изображений 1

Павловский Ю.Н.
Вычислительный центр РАН, Москва

Аннотация:

"Изображением" считается некоторое подмножество $U$ множества $X$, наделенного структурой $\sigma$ (в смысле Н.Бурбаки  [1]) рода $\Sigma$ . В излагаемом подходе к обсуждаемой проблеме "образом" изображения считается некоторая совокупность таких свойств множества $U$ и таких ассоциированных с ним характеристик, которые "сохраняются", когда объект объект $(X,\sigma)$ подвергается изоморфизмам. Средства геометрической теории декомпозиции  [6] дают возможность развивать методы построения образов изображений в определенной мере независимо от того, каков род структуры $\Sigma$: декомпозиционнная структура множества $U$ над объектом $(X,\sigma)$ и ее свойства по их определению сохраняются при изоморфизмах этого объекта. Общие построения иллюстрируются на примере подмножеств аффинного двумерного пространства.

Let $X$ is a set supplied by structure  [1] $\sigma$ of kind $\Sigma$. A subset $U$ of the $X$ is treated as a `picture'. Image of the picture $U$ is assumed some assemble of such properties of the $U$ which is preserved by action of isomorphisms of $\Sigma$-object $(X,\sigma)$. The means of geometric theory of decomposition  [6] permit to develop methods of creation of images of pictures in some extend independently from structure kind $\Sigma$: preservation of decomposition structure of $U$ over $(X,\sigma)$ by isomorphisms of $\Sigma$-object is a simple consequence of definition. The images of the subsets of two-dimensional affine space is used as example.

1. Геометрическая теория декомпозиции


1. Предлагаемый подход к проблеме построения образов изображений основывается на геометрической теории декомпозиции (ГТД)  [6]. В настоящем разделе дается представление об этой теории. На самом общем уровне ГТД можно охарактризовать как языковую среду, связанную с подходом к проблеме декомпозиции математических объектов, состоящим в следующем. Изучаемый объект погружается в класс, где определено понятие об изоморфизме объектов. Среди объектов, изоморфных изучаемому, отыскивается такой, который является "представлением" исходного объекта с помощью семейства более простых в некотором смысле объектов. Практически, "более простыми" объектами в этом семействе являются подобъекты и/или фактор-объекты исходного объекта, а "представлением" является ситуация, когда по данному семейству можно однозначно восстановить исходный объект (например, с помощью операций декартова произведения или дизъюнктивной суммы).

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

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

2. В качестве основного инструментального средства при развитии ГТД использовалась бурбаковская система , в качестве вспомогательного -- теория категорий  [3]. Под бурбаковской системой здесь понимается излагаемая в  [1], именуемая там "Теорией множеств" (ТМ) формальная система, претендующая на "полную формализацию" математических рассуждений (с позиций этой формальной системы "обычная" математика трактуется как "наивная"), а также естественным образом возникающие в этой системе языковые средства  [1, стр. 242-297], с помощью которых удобно (наряду с теорией категорий) изучать свойства математических объектов, сохраняющиеся при изоморфизмах. Система Н. Бурбаки и теория категория в большой мере взаимосвязаны, но это разные языковые системы. В теории категорий от математических объектов "ничего не остается", кроме множеств связывающих их морфизмов. В бурбаковской же системе мы знаем, что математический объект -- это снабженное бурбаковской структурой множество. Теория категорий тривиальным образом доступна из бурбаковской системы; в то же время интерпретация ряда понятий и фактов бурбаковской системы средствами теории категорий вызывает определенные трудности  [2].

Для того, чтобы воспользоваться средствами ГТД, необходимо прежде всего дать трактовку исследуемому объекту как базисному множеству $X$ , снабженному бурбаковской структурой $\sigma$ рода $\Sigma$ в бурбаковской формальной системе В, более сильной (содержащей больше аксиом), чем ТМ. Дальнейшее изложение в связи с этим будет иметь "синтаксический аспект". В частности, буква, за которой в ломаных скобках $\langle\;\rangle$ фигурирует список букв, будет обозначать некоторый терм или соотношение формальной системы, в котором присутствуют буквы, перечисленные в данном списке. Род структуры $\Sigma$ есть текст (т.е. список термов и соотношений формальной системы) $(X;\sigma;A;\sigma\subset S\langle X,A\rangle ;R\langle X,\sigma\rangle ) $ в системе В. В этом тексте $X$ -- базисное множество (их может быть несколько), т.е. обозначение для множества, которое снабжается структурой, $\sigma$ -- родовая константа, т.е. обозначение для этой самой структуры (их также может быть несколько), $A$ -- так называемое вспомогательное множества (их может быть несколько или не быть ни одного); соотношение $\sigma \subset S\langle X,A\rangle $ называется соотношением типизации, где $S\langle X,A\rangle $ -- множество, полученное из $X,A$ операциями прямого произведения и образования множества частей, причем $S$ -- схема образования этого множества, указывающая с какими множествами и в какой последовательности выполняются эти операции  [6]; $R\langle X,\sigma\rangle $ -- аксиома рода структуры $\Sigma$, т.е. соотношение (оно может отсутствовать), которое должно быть $\Sigma_0$ - сохраняемым (инвариантным) в В  [5] (см. п. 3), где $\Sigma_{0} = (X;\sigma;A;\sigma\subset S\langle X,A\rangle ) $ -- типизация рода структуры $\Sigma$ (по терминологии  [1] $R\langle X,\sigma\rangle $ должно быть биективно переносимо в В). Это означает, что из $\sigma \subset S\langle X,A\rangle $ и " $f:X \rightarrow X'$ -- биекция" в В должно следовать $R\langle X,\sigma\rangle \Leftrightarrow R\langle X',\sigma'\rangle $, где $\sigma'=S\langle f,id_{A}\rangle (\sigma)$, а $S\langle f,id_{A}\rangle $ -- распространение отображения $f$ и тождественных отображений множеств $A$ по схеме $S$ до отображения из множества $S\langle X,A\rangle $ в множество $S\langle X',A\rangle $  [1].

В качестве примера выполним погружение в ТМ конечномерного линейного векторного пространства $V$ над полем $R$ действительных чисел (это поле является термом ТМ; оно будет вспомогательным множеством в определяемом роде структуры), а также аффинного пространства $A$ над $V$. Род структуры LVS конечномерного линейного векторного пространства над $R$ есть текст

\begin{displaymath} LVS = (V;\;\sigma, \omega;\; R;\; \sigma \subset \sigma \sub... ...t R\times V\times V;\; ALVS\langle V,R,\sigma,\omega\rangle ). \end{displaymath}

Здесь структура $\sigma$ определяет абелеву группу, т.е. сложение в LVS (записанное на классическом языке соотношение $x+y=z$ эквивалентно соотношению $(x,y,z)\in \sigma$ на формальном языке), аналогично, структура $\omega$ определет умножение векторов из $X$ на скаляры из $R$,

\begin{displaymath} ALVS\langle V,R,\sigma,\omega\rangle \end{displaymath}

есть запись аксиомы LVS как формального соотношения в бурбаковской системе. LVS$_{0}$ - инвариантность этой аксиомы очевидна.

Род структуры $AS$ аффинного пространства $A$ над $V$ есть текст

\begin{displaymath} AS = (A,V;\;\sigma,\omega,\rho;R;\;\sigma \subset V\times V\times V, \end{displaymath}


\begin{displaymath} \omega\subset R\times V\times V,\rho \subset V\times V\times... ...\sigma \rangle \wedge AAS\langle A,V,R,\sigma,\omega\rangle) . \end{displaymath}

Здесь структура $\rho$ определяет разность элементов $a,b$ из AS, равную элементу $u$ пространства $LV$: $a-b=u \Leftrightarrow (a,b,u) \in \rho $ , аксиома $AAS$ предъяляет к этой разности необходимые требования.

Через В$\Sigma$ обозначается теория рода структуры $\Sigma$, т.е. бурбаковская система, получающаяся из В прибавлением к ее явным аксиомам соотношений $\sigma \subset S\langle X,A\rangle $ и $R\langle X,\sigma\rangle $. В системе В', более сильной, чем B, совокупность $(E,\tau)$ называется $\Sigma$-объектом, если в ней верно $\tau \subset S\langle E,A\rangle $ и $R\langle E,\tau\rangle $ . $\Sigma$ - изоморфизмом $\Sigma$-объекта $(E,\tau)$ в $\Sigma$-объект $(E',\tau')$ называется биекция " $f:E \rightarrow E'$, такая, что $\tau'=S\langle f,id_{A}\rangle (\tau)$. Таким образом, в любой системе B' более сильной, чем В (в частности, в самой В ) возникает класс $\Sigma$-объектов снабженный понятием об изоморфизме.

3. Введем понятия о сохраняемых ($\Sigma$ - инвариантных) при $\Sigma$ - изоморфизмах термах и соотношениях  [1, стр.281-297],  [5], о которых шла речь выше. Рассуждения будут вестись в системе В, в которой определен род структуры $\Sigma$, а также в системе В$\Sigma$. Напомним, что в последнем случае понятия и факты будут основаны на выполнении соотношений $\sigma \subset S\langle X,A\rangle $ и $R\langle X,\sigma\rangle $. т.е. на том, что $(X,\sigma)$ является $\Sigma$ - объектом. Пусть $V\langle X,\sigma\rangle $ -- терм системы В$\Sigma$. Говорят, что этот терм имеет в В$\Sigma$ тип $S_{V}\langle X,A\rangle $, если $V\langle X,\sigma\rangle \in S_{V}\langle X,A\rangle $ -- теорема в В$\Sigma$. Пусть теперь терм $V\langle X,\sigma,U\rangle $ имеет в В$\Sigma$ тип $S_{V}\langle X,A\rangle $. Говорят, что этот терм сохраняется при $\Sigma$ - изоморфизмах ($\Sigma$-инвариантен (в В)) если из " $f:X \rightarrow X'$ -- биекция" в В$\Sigma$ следует соотношение $V\langle X',\sigma'\rangle =S_{V}\langle f,id_{A}\rangle (V\langle X,\sigma\rangle )$, где $\sigma'=S\langle f,id_{A}\rangle (\sigma)$. Далее, если тип терма очевиден, он не будет указываться.

Пусть $I\langle X,\sigma\rangle $ -- соотношение в В$\Sigma$. Говорят, что это соотношение сохраняется при $\Sigma$ - изоморфизмах ($\Sigma$-инвариантно (в В)), если из " $f:X \rightarrow X'$ -- биекция" в В$\Sigma$ следует $I\langle X,\sigma\rangle \Leftrightarrow I\langle X',\sigma'\rangle $. Инвариантность аксиомы $R\langle X,\sigma\rangle $ рода структуры $\Sigma$ относительно типизации этого рода структуры (см. п. 2) является в некотором смысле "базовой" инвариантностью, на которой основана сохраняемость при изоморфизмах объектов, участвующих в построениях ГТД, о которых говорится ниже.

Далее, для того, чтобы воспользоваться средствами ГТД необходимо сопоставить с каждыми двумя $\Sigma$-объектами $(X,\sigma)$ и $(X',\sigma')$ множество $M\langle X,\sigma,X',\sigma'\rangle $ отображений из $(X,\sigma)$ в $(X',\sigma')$, называемых (бурбаковскими  [1, стр.255]) морфизмами, так, чтобы суперпозиция морфизмов была морфизмом и биекция $f:X \rightarrow X'$ тогда и только тогда была изоморфизмом, когда она сама и обратная к ней биекция -- морфизмы. Множество (графиков) морфизмов $M\langle X,\sigma,X',\sigma'\rangle $ имеет тип $\beta(\beta(X\times X'))$ ($\beta(X)$ -- булеан $X$) и является $2\Sigma$-инвариантным объектом, где род структуры $2\Sigma$ есть $(X,X';\sigma,\sigma';A;\sigma\subset S\langle X,A\rangle \wedge\sigma\subset S\langle X',A\rangle ;R\langle X,\sigma\rangle \wedge R\langle X',\sigma'\rangle )$. Класс $\Sigma$ - объектов (в B'), снабженный морфизмами удовлетворяет аксимам теории категорий. Далее, однако, понятия и факты теории категорий не будут использоваться, поскольку в этом не будет никакой нужды.

4. В основе ГТД лежат лишь два понятия, которые двойственны друг другу.

О п р е д е л е н и е 1. Пусть $(X_{i},\sigma _{i}) _{i \in I}$ -- семейство $\Sigma$-объектов, ($X,\sigma$) - $\Sigma$-объект, $f_{i}: X_{i} \rightarrow X $ $(f_{i} = X \rightarrow X_{i})$ - морфизмы. Если для любого $\Sigma$-объекта ($X',\sigma') $ и любого отображения $g:X \rightarrow X'$ $( g:X' \rightarrow X)$, соотношение "для любого $i \in I$ суперпозиция $g\circ f_{i}$ есть морфизм $(f_{i}\circ g \;$ есть $\Sigma$-морфизм$ )$" влечет соотношение ''$g$ есть морфизм'', то говорят, что семейство (( $X_{i},\sigma _{i}$),$f_{i}$)$_{i\in I}$ является $P$-декомпозицией $( F-декомпозицией )$ $\Sigma$-объекта ($X,\sigma$) (или что семейство (( $X_{i},\sigma _{i}$))$_{i\in I}$ является декомпозицией реализуемой посредством морфизмов $f_{i}$. Мощность множества $I$ называется мощностью декомпозиции. Декомпозиция называется тривиальной, если существует такое $i \in I$, что $f_{i}$ есть $\Sigma$-изоморфизм.

Из определения сразу следует, что объект ($X,\sigma$) восстанавливается по своей декомпозиции (P- или F-) единственным образом.

Следующая схема иллюстрирует сформулированное определение

($X'$,$\sigma' $) $\stackrel{g}\rightarrow $ ($X$,$\sigma$) $\stackrel{f_{i}}\rightarrow $ ($X_{i}$,$\sigma _{i}$) $\vert$ ($X_{i}$,$\sigma _{i}$) $\stackrel{f_{i}}\rightarrow $ ($X$,$\sigma$) $\stackrel{g}\rightarrow $ ($X'$,$\sigma' $)

Понятия о P- и -F объектах являются частными случаями, соответственно, F- и P-декомпозиций: пусть $(\widetilde{X},\widetilde{\sigma})$, ($X,\sigma$) -- $\Sigma$-объекты, $\widetilde{X}\subset X$. Объект $(\widetilde{X},\widetilde{\sigma})$ называется P-объектом объекта $(X,\sigma)$, если $(X,\sigma)$ является F-декомпозицией для $(\widetilde{X},\widetilde{\sigma})$, реализуемой посредством канонической инъекции $\omega: \widetilde{X} \rightarrow X$. Двойственно определяется фактор-объект $(X_{Q},\sigma _{Q})$ объекта $(X,\sigma)$ ($Q$ -- отношение эквивалентности на $X$, $X_{Q}$ -- фактор-множество по этому отношению). Следующая схема иллюстрирует определения P- и F-объектов ($\pi$ -- каноническая проекция).

$ (X',\sigma ')\stackrel{g}\rightarrow ( \tilde{X},\tilde{\sigma }) \stackrel{\o... ...el{\pi }\rightarrow (X_{Q},\sigma _{Q})\stackrel{g}\rightarrow (X', \sigma ') $

Аналогично, декартово произведение и дизъюнктивная сумма являются частными случаями P- и F-декомпозиций: объект $(\prod\nolimits^{d}_{i\in I}X_{i},\sigma ^{d})$ (через $(\prod\nolimits^{d}_{i\in I}X_{i})$ обозначается декартово произведение семейства $(X_{i})_{i\in I}$, через $\sum\nolimits^{c}_{i\in I}X_{i}$ -- его дизъюнктивная сумма), является декартовым произведением семейства $\Sigma$-объектов $(X_{i},\sigma _{i}) _{i \in I}$, если это семейство является для него P-декомпозицией, реализуемой с помощью соответствующих канонических проекций $pr_{i}$. Двойственным образом определяется дизъюнктивная сумма семейства $\Sigma$-объектов. Следующая схема иллюстрирует определение декартова произведения и дизъюнктивной суммы семейства объектов ($j_{i}$ -- канонические инъекции).

$ (X',\sigma')\stackrel{g}\rightarrow (\prod\nolimits^{d}_{i\in I}X_{i},\sigma ^{d})\stackrel{pr_{i}}\rightarrow (X_{i},\sigma _{i})$ $\mid$ $(X_{i},\sigma _{i})\stackrel{j_{i}}\rightarrow (\sum\nolimits^{c}_{i\in I}X_{i},\sigma ^{c})\stackrel{g}\rightarrow (X',\sigma') $

Объект $(X,\sigma)$, изоморфный декартову произведению (дизъюнктивной сумме) некоторого семейства объектов называется допускающим декомпозицию на декартово произведение (дизъюнктивную сумму).

5. Имеется канонический способ определить морфизмы для данного рода структуры $\Sigma = (X;\sigma;A;\sigma\subset S\langle X,A\rangle ;R\langle X,\sigma\rangle ) $. Пусть $(X,\sigma)$, $(X',\sigma')$ - $\Sigma$-объекты. Отображение $f:X \rightarrow X'$ называется естественным каноническим морфизмом (ЕКМ), если $\sigma' \subset S\langle f,id_{A}\rangle (\sigma)$. Примерами ЕКМ являются гомоморфизмы групп, колец, полей, линейные отображения линейных векторных пространств, аффинные отображения аффинных пространств, непрерывные, открытые, замкнутые отображения топологических пространств -- в зависимости от того, какой системой аксиом задается топология, гладкие отображения дифференцируемых многообразий. Для дифференциальных уравнений ЕКМ -- это отображения, переводящие решения в решения. Все, что в "обычной" ("наивной" по Н. Бурбаки) математике получило название "подобъект" ("фактор-объект") является в ГТД P-объектом (F-объектам) относительно ЕКМ.

С каноническим разложением $f=\omega\circ b\circ \pi $ ЕКМ $f:(X,\sigma)\rightarrow (X',\sigma')$ на проекцию, биекцию и инъекцию ассоциируется F-объект $(X_{Q},\sigma _{Q})$ объекта $(X,\sigma)$, P-объект $(\widetilde{X}',\widetilde{\sigma}')$ объекта $(X',\sigma')$. Этот факт не доказан, но исключения из него автору неизвестны. Благодаря этому обстоятельству всякая P-декомпозиция (F-декомпозиция) объекта $(X,\sigma)$ порождает "более близкую" к нему P-декомпозицию (F-декомпозицию), образованную семейством его P-объектов (F-объектов), реализуемую с помощью соответствующих канонических инъекций (проекций) и, таким образом, изучение декомпозиций $\Sigma$ - объекта $(X,\sigma)$ сводится к изучению множеств $P\langle X,\sigma\rangle $ и $F\langle X,\sigma\rangle $ его P- и F-объектов. Эти множества не пусты, поскольку $(X,\sigma)$ является для $\Sigma$ - объекта $(X,\sigma)$ одновременно (тривиальным) P-объектом и F-объектом. Если у объекта кроме тривиального нет более P-объектов (F-объектов), то он называется P-простым (F-простым). Отношение "более близкая" между двумя декомпозициями объекта $(X,\sigma)$ является отношением предпорядка на классе декомпозиций этого объекта. Примером еще одного отношения на классе декомпозиций объекта $(X,\sigma)$ является отношение "более простая": например, Р-декомпозиция $(\widetilde{X}_{i},\widetilde{\sigma}_{i})_{i\in I}$ для $(X,\sigma)$, составленная из его Р-объектов называется более простой, чем Р-декомпозиция $(\widetilde{X}_{j}',\widetilde{\sigma}_{j}')_{j\in J}$, если каждый элемент первого семейства является элементом второго. Система таких отношений и их свойства будут именоваться "декомпозиционной структурой" объекта $(X,\sigma)$. Рамки статьи не позволяют ввести это понятие на формальном уровне. Собственно говоря, содержанием ГТД является изучение декомпозиционных структур математических объектов (моделей).

6. Для иллюстрации ГТД переведем на ее язык некоторые известные читателям понятия и факты. Все декомпозиции, о которых будет идти речь, выполняются относительно ЕКМ.

а) Классическое понятие "простая группа" на языке ГТД является F-простым объектом, а "простое поле" -- P-простым объектом (любое поле является F-простым объектом). Транзитивная группа преобразований на языке ГТД -- это P-простой объект, примитивная группа преобразований -- это F-простой объект.

б) Жорданова форма системы дифференциальных уравнений

\begin{displaymath} \frac{dx^{i}}{dt} = a^{i}_{j}x^{j}, i, j=1, 2, ..., n, \eqno (1) \end{displaymath}

с действительными коэффициентами $a^{i}_{j}$ является максимальной декомпозицией этого объекта на декартово произведение своих DP - простых (т.е. не допускающих нетривиальных декомпозиций на декартово произведение) подобъектов), если (1) вложена в класс систем с комплексными коэффициентами, а изоморфизмами считаются невырожденные преобразования

\begin{displaymath} z^{i}=b^{i}_{j}x^{j}, i, j=1, 2, ..., n \eqno(2) \end{displaymath}

с комплексными коэффициентами $b^{i}_{j}$.

Внутри жордановой клетки также имеет место декомпозиция, которую поясним на более общем уровне. Именно, декомпозиционное представление

$ dz^{k}/dt = \phi ^{k}(z^{1}, ..., z^{m}), k = 1, ..., m,$
$dx^{l}/dt = \psi ^{l}(z^{1},...,z^{m},x^{1},...,x^{n-m}), l = 1,...,n-m$

системы

$ dy^{i}/dt=f^{i}(y^{1}, ..., y^{n}), i=1, 2, ..., n, $

полученное с помощью диффеоморфизма $ y=g(z,x)$ трактуется как дизъюнктивная сумма подобъектов этой системы.

Если же считать (1) представителем класса систем с коэффициентами, являющимися действительными функциями $t$, а изоморфизмами -- невырожденные преобразования (2), где $b^{i}_{j}$ также действительные функции $t$, то максимальная декомпозиция объекта (1) на декартово произведение имеет вид $ dz^{i}/dt=0, i=1, 2, ..., n.$

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

г) Инвариантные решения системы дифференциальных уравнений  [4] соответствуют случаям (нетривиальной) факторизации некоторых подобъектов множества решений данной системы.

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

е) Свойства слабой управляемости, наблюдаемости, инвариантности управляемых динамических систем являются свойствами декомпозиционнной структуры этого объекта  [3],  [7] .

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




2. Построение образов изображений



1. Пусть $(X,\sigma)$ -- $\Sigma$-объект в В$\Sigma$, $U \subset X$. Образуем род структуры $\Sigma'$, присоединив к $\Sigma$ родовую константу $U$ и типизацию $U \subset X$. $\Sigma'$-объекты в В$\Sigma'$ имеют вид $(X,\sigma,U)$. Пусть $I\langle X,\sigma,U\rangle$ -- $\Sigma'$-инвариантное соотношение, $f:X \rightarrow X'$ -- биекция и $\sigma'=S\langle f,id_{A}\rangle (\sigma)$. Поскольку соотношение $R\langle X,\sigma\rangle $ является $\Sigma_0$-инвариантным в В, то $\Sigma$-объект $(X,\sigma)$ изоморфен объекту $\Sigma$-объекту $(X',\sigma')$. Таким образом, $\Sigma'$-инвариантное при изоморфизмах соотношение $I\langle X,\sigma,U\rangle$ есть свойство подмножества $U$ множества $X$ , которое "сохраняется", при $\Sigma$ - изоморфизмах (в частности, при автоморфизмах) $\Sigma$ - объекта $(X,\sigma)$. Поэтому $\Sigma'$-инвариантные соотношения будут называться $\Sigma$-образами подмножества $U$ первого уровня или простыми $\Sigma$-образами. Одним из способов формирования как простых так и иерархических (см. далее) $\Sigma$-образов является изучение декомпозиций $\Sigma'$-объекта $(X,\sigma,U)$ над объектом $\Sigma$-объектом $(X,\sigma)$. Конкретизируем общие понятия о такой декомпозиции [6, раздел 2.6.5, стр. 103] для рассматриваемого случая.

Пусть род структуры $\Sigma$ в В снабжен морфизмами, которые будут называться $\Sigma$-морфизмами. Снабдим род структуры $\Sigma'$-морфизмами следующим образом: $f:X \rightarrow X'$ есть $\Sigma'$-морфизм объекта $(X,\sigma,U)$ в объект $(X',\sigma',U')$ тогда и только тогда, когда $f$ есть $\Sigma$-морфизм и $f(U)\subset U'$.

О п р е д е л е н и е 2. Пусть $(X_{i},\sigma _{i},U_{i}) _{i \in I}$ -- семейство $\Sigma'$-объектов, ($X,\sigma,U$) - $\Sigma'$-объект, $f_{i}: X_{i} \rightarrow X $ $\Bigl(f_{i} = X \rightarrow X_{i}\Bigr)$ для всякого $i$ из $I$ -- $\Sigma'$-морфизмы. Если для любого $\Sigma'$-объекта ( $X',\sigma',U') $ и любого $\Sigma$-морфизма $g:X \rightarrow X'$ $\Bigl( g:X' \rightarrow X \Bigr)$ соотношение "для любого $i \in I$ суперпозиция $g\circ f_{i}$ есть $\Sigma'$-морфизм $\Bigl (f_{i}\circ g \;$ есть $\Sigma'$-морфизм$ \Bigr )$" влечет соотношение ''$g$ есть $\Sigma'$-морфизм'', то будем говорить, что семейство (( $X_{i},\sigma _{i},U_{i}$),$f_{i}$)$_{i\in I}$ является $P$-декомпозицией $\Bigl ( F-декомпозицией \Bigr)$ $\Sigma'$-объекта ($X,\sigma,U$) над $\Sigma$-объектом ($X,\sigma$). $Card(I)$ называется мощностью декомпозиции. Декомпозиция называется тривиальной, если существует такое $i \in I$, что $f_{i}$ есть $\Sigma'$-изоморфизм.

Для сокращения речи вместо словосочетания P-декомпозиция $\Sigma'$-объекта ($X,\sigma,U$) над $\Sigma$-объектом ($X,\sigma$) будет употребляться словосочетание P - декомпозиция для ($X,\sigma,U$), если это не может вызвать недоразумений (аналогично для F - декомпозиций).

Пусть (( $X_{i},\sigma _{i},U_{i}$),$f_{i}$)$_{i\in I}$ -- декомпозиция (P- или F-) для ($X,\sigma,U$). Совокупность (( $X_{i},\sigma _{i},U_{i}$),$f_{i}$) для некоторого фиксированного $i$ из $I$ называется элементом этой декомпозиции. Две декомпозиции для ($X,\sigma,U$), множества элементов которых совпадают, не будут далее различаться.

Следующие утверждения тривиальным образом вытекают из определений.

П р е д л о ж е н и е 1. Существует не более одного множества $U \subset X$, такого, что семейство $((X_{i},\sigma _{i},U_{i}),f_{i}) _{i \in I}$ является P-декомпозицией (F-декомпозицией) для $(X,\sigma,U)$.

П р е д л о ж е н и е 2. Для того, чтобы семейство $((X_{i},\sigma _{i},U_{i}),f_{i}) _{i \in I}$ $\Sigma'$-объектов и $\Sigma'$-морфизмов $f_{i}: X_{i} \rightarrow X $( $f_{i}:X\rightarrow X_{i}$) было P-декомпозицией (F-декомпозицией) для $(X,\sigma,U)$ необходимо и достаточно, чтобы выполнялось условие

\begin{displaymath}\bigcup_{i\in I}f_{i}(U_{i})=U\;\; ( \bigcap_{i\in I}f_{i}^{-1}(U_{i})=U).\end{displaymath}

П р е д л о ж е н и е 3. Всякое семейство $((\widetilde{X}_{i},\widetilde{\sigma}_{i}, \widetilde{U}_{i}),\omega_{i})_{i\in I }$, такое, что для любого $i$ канонические инъекции $\omega_{i}:\widetilde{X}_{i} \rightarrow X$ -- $\Sigma$-морфизмы и $\bigcup_{i\in I}\widetilde{X}_{i}=U$, является P-декомпозицией для $(X,\sigma,U)$ (двойственно -- для F-декомпозиции).

Обратим внимание на то, что $\Sigma$-объекты $(\widetilde{X}_{i},\widetilde{\sigma}_{i})$, участвующие в Р-декомпозиции $((\widetilde{X}_{i},\widetilde{\sigma}_{i},\widetilde{U}_{i}))_{i\in I }$ объекта $(X,\sigma,U)$ над $(X,\sigma)$ могут не быть его бурбаковскими подобъектами (двойственно -- для F-декомпозиций)  [2].

2. Пусть $I\langle X,\sigma,U\rangle$ -- простой $\Sigma$ - образ подмножества $U$, являющийся утверждением о существовании и единственности некоторой декомпозиции $V\langle X,\sigma,U\rangle $ для $(X,\sigma,U)$. Образуем из $\Sigma'$ последовательность $\Sigma''$, присоединив к аксиоме $R\langle X,\sigma\rangle $ последовательности $\Sigma'$ в качестве явной аксиомы соотношение $I\langle X,\sigma,U\rangle$. Образуем бурбаковскую формальную систему B$\Sigma''$  [5]. В системе B$\Sigma''$ становится доступным $\Sigma'$ - инвариантный объект $V\langle X,\sigma,U\rangle $ и, возможно, некоторые $\Sigma'$ - инвариантные объекты $P$, которые можно построить, имея объект $V\langle X,\sigma,U\rangle $, обладающий свойствами, определяемыми соотношением $I\langle X,\sigma,U\rangle$. Некоторое $\Sigma''$ - инвариантное соотношение $I'\langle X,\sigma,U,V,P\rangle $ в системе В$\Sigma''$ вместе с $\Sigma'$ - инвариантным соотношением $I\langle X,\sigma,U\rangle$ образуют двухуровневый иерархический образ подмножества $U$. Аналогично строятся более высокие уровни образа множества $U$. Следующий пример в некоторой мере конкретизирует изложенную схему.

3. Пусть система В есть бурбаковская теория множеств,

\begin{displaymath} AS_{0} = (A,V;\;\sigma,\omega,\rho;R;\;\sigma \subset V\time... ...omega\subset R\times V\times V,\rho \subset V\times V\times A) \end{displaymath}

$AS$ получается из $AS_{0}$ присоединением явной аксиомы $ALVS\langle V,R,\sigma \rangle \wedge AAS\langle A,V,R,\sigma,\omega\rangle)$, утверждающей, что $(V,\sigma,\omega)$ является линейным векторным пространством размерности 2 над полем $R$, а $(A,V,\sigma,\omega,rho)$ -- аффинным пространством над $(V,\sigma,\omega)$ (см. пример в разделе 1.2), $AS'$ получается из $AS$ присоединением к $AS$ родовой константы $U$ и типизации $U \subset A$, а также условия непустоты $U$. $AS$-морфизмами будем считать аффинные гомоморфизмы. Далее для краткости обозначено $\eta=(\sigma,\omega,\rho)$.

Обозначим через $I_{1}\langle A,V,\eta,U\rangle $ следующее $AS'$-инвариантное соотношение:


существует и единственна (см. замечание 2) Р-декомпозиция $\widetilde{A}_{i},\widetilde{V}_{i},\widetilde{\eta}_{i},\widetilde{U}_{i}), )_{i\in I }$ мощности 3 для $(A,V,\eta,U)$ такая, что для любого $i$ множества $\widetilde{U}_{i}$ не пусты, $AS$-объекты $(\widetilde{A}_{i},\widetilde{V}_{i},\widetilde{\eta}_{i})$ являются одномерными подобъектами объекта $(A,V,\eta)$ и каждая пара $(\widetilde{A}_{i},\widetilde{V}_{i}),( \widetilde{A}_{j},\widetilde{\widetilde{V}_{j}})$ имеет единственный общий нуль-мерный подобъект $P_{ij}$ объекта $(A,V,\eta)$, причем при $\{i,j\}\neq\{i',j'\}$ имеет место $P_{ij}\neq P_{i'j'}$.


Выполним перевод соотношения $I_{1}\langle A,V,\eta,U\rangle $ с языка ГТД на "аффинный язык":


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


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

Обозначим через $\Sigma''$ последовательность термов и соотношений, которая получается из $\Sigma'$ присоединением к ней в качестве явной аксиомы соотношения $I_{1}\langle A,V,\eta,U\rangle $. В системе B$\Sigma''$ можно оперировать объектами $\widetilde{A}_{i},\widetilde{V}_{i},\widetilde{\eta}_{i},\widetilde{U}_{i} $, $ $$i=1,2,3$, $P_{12},P_{13},P_{23}$, существование которых утверждается аксиомой $I_{1}\langle A,V,\eta,U\rangle $.

Пусть $(\widetilde{A},\widetilde{V},\widetilde{\eta})$ -- одномерный подобъект (т.е. прямая) аффиного пространства $(A,V,\eta)$. Множество $\widetilde{A}$ нульмерных подобъектов объекта $(A,V,\eta)$ (всякая точка множества $A$ является нульмерным подобъектом объекта $(A,V,\eta)$ ) естественным образом снабжается структурой тернарного отношения $Q \subset \widetilde{A}\times \widetilde{A}\times \widetilde{A}$, определенного соотношением $(x,y,z)\in Q \Leftrightarrow ((x \leq y \wedge y \leq z) \vee(z \leq y \wedge y \leq x)$, которое на "аффинном" языке можно охарактеризовать словосочетанием "$y$ лежит между $x$ и $z$". Это тернарное соотношение будет называться индуцированным. Терм $Q$ является аффинно-инвариантным. Обозначим через $\widetilde{Q}_{1},\widetilde{Q}_{2},\widetilde{Q}_{3}$ индуцированные тернарные отношения на $\widetilde{A}_{1},\widetilde{A}_{2},\widetilde{A}_{3}$, соответственно. Соотношение $(\forall u)(u \in U \Rightarrow ((P_{12},u,P_{13})\in\widetilde{Q}_{1}\vee(P_{12},u,P_{23}) \in\widetilde{Q}_{2}\vee(P_{13},u,P_{23})\in\widetilde{Q}_{3}))$, которое обозначим через $I_{2}\langle A,V,\eta,U,P\rangle$ (здесь $P=\{P_{12},P_{13},P_{23}\}$) является $\Sigma''$-инвариантным. Двухуровневый иерархический образ $I_{1}\langle A,V,\eta,U\rangle $, $I_{2}\langle A,V,\eta,U,P\rangle$ множества $U$ естественно обозначить словосочетанием образ множества $U$ является прописной греческой буквой дельта.

Алгоритм, который "узнает", что образ предъявленного множества $U$ является прописной греческой буквой дельта, имеет иерархический характер. На первом уровне иерархии алгоритм должен уметь вычислять логическое значение соотношения $I_{1}\langle A,V,\eta,U\rangle $. Если оно оказалось верным, то включается второй уровень иерархии, на котором вычислятся логическое значение соотношения $I_{2}\langle A,V,\eta,U,P\rangle$. Если мощность множества $U$ конечна, то эти задачи алгоритмически тривиальны. Поэтому при практической реализации алгоритма необходимо, конечно, использовать метрику: во-первых, для того, чтобы трасформировать предъявленное множество в конечное (т.е. "оцифровывать" это множество с некоторым шагом $h$) ,во-вторых, практический алгоритм должен оперировать не прямыми, в полосами некоторой ширины $\varepsilon$. Распознающий алгоритм должен перебирать в некоторых пределах пары значений $h$ и $\varepsilon$, пытаясь отыскать такие, при которых истины оба соотношения $I_{1}\langle A,V,\eta,U\rangle $ и $I_{2}\langle A,V,\eta,U,P\rangle$. Повидимому, наиболее естественно начинать работу с больших значений $h$ и $\varepsilon$, переходя затем к меньшим их значениях. Аналогичным образом строятся иерархические образы других букв и фигур на плоскости и алгоритмы их распознавания.

Выполним теперь "обратный" перевод изложенного метода построения образов изображений в двумерном аффинном пространстве на язык ГТД: выясняется минимальное количество подобъектов объекта $(X,\sigma)$, которым принадлежат все элементы изображения $U$, и "взаимоотношения" между этими подобъектами, порождаемым самим изображением $U$ и структурой $\sigma$ на $X$. Языковая среда теории декомпозиции  [6] представляется перспективным инструментом для решения задачи автоматической генерации, накопления и распознавания образов подмножеств снабженных структурой множеств.

Литература

1
Бурбаки Н. Теория множеств. М.: Мир. 1965.

2
Данилов Н.Ю. О взаимосвязи декомпозиционных свойств исчисления родов структур и теории категорий. В кн. Моделирование, оптимизация и декомпозиция сложных динамических процессов. М. :ВЦ РАН, 1996, cтр.49-62.

3
Елкин В.И. Редукция нелинейных управляемых систем. М.:Наука, 1997.

4
Овсянников Л.В. Групповой анализ дифференциальных уравнений. М.: Наука. 1978.

5
Павловский Ю.Н. О шкалах родов структур// ДAН, 1998, Т.363, №2, c.163-165.

6
Павловский Ю.Н., Смирнова Т.Г. Проблема декомпозиции в математическом моделировании. М.: Фазис. 1998.

7
Яковенко Г.Н. Групповые свойства динамических систем. М.:МФТИ. 1994. 138 с.

1
Работа поддержана Российским фондом фундаментальных исследований, грант 99-01-00018 и Программой государственной поддержки ведущих научных школ, грант 00-15-96137.
Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Sunday, 09-Sep-2001 14:49:52 NOVST