представляет собой специальный случай метаграфов, рассмотренных
в работе [17]. Однако здесь для формирования метаграфа заданы зна-
чения его вершин в нескольких доменах
Dq
:
v
jk
=
S
q
v
jkD
q
. Кроме
того, к домену предъявляют еще три требования.
Требование II.
Декомпозиция существует хотя бы для одного уров-
ня
j
и число вариантов таких декомпозиций для одной и той же вер-
шины больше или равно единице.
Требование III.
Существует пустое значение
v
jkD
q
=
;
, которое объ-
является как недекомпозируемое и для которого не определена опера-
ция умножения на скаляр.
Требование IV.
Определена мера расстояния между непустыми вер-
шинами:
ρ
j
1
k
1
j
2
k
2
D
q
= (
v
j
1
k
1
D
q
v
j
2
k
2
D
q
)
2
R
.
Примером домена, удовлетворяющего перечисленным требовани-
ям
I
−
IV
, могут стать пространственные позиции вершины (напри-
мер, ее центроид):
D
q
=
S
. Значения в таком домене, принадлежа-
щем пространству
2
R
, следовательно:
v
jkS
=
X
m
w
(
j
+1)
mS
v
(
j
+1)
mS
=
= w
(
j
+1)
S
т
v
(
j
+1)
S
, где
w
(
j
+1)
S
,
v
(
j
+1)
S
2
R
K
, число вариантов деком-
позиций больше 1 для
K
≥
2
. В качестве пустого элемента может
использоваться
∞
, меры расстояния — разность.
Примерами доменов могут быть: текстурное описание с помощью
набора двумерных вейвлет-фильтров с ориентациями
θ
и масштабами
σ
[15]; распределения в цветовых каналах [4]; ссылка на концепт из
модели знаний. Доказательство требований
I
−
IV
для этих и других
доменов будет рассмотрено в последующих работах.
Предложенный метаграф можно представить как набор отдельных
графов (см. рис. 2):
G
i
=
f
(I
i
) =
{
G
iD
1
, . . . ,
G
iD
Q
}
.
Формирование разряженного вектора метаграфа.
Вычислитель-
ные системы обычно работают с векторами и матрицами, поэтому, как
было отмечено ранее, во многих приложениях [8, 10, 11] изображе-
ния
I
i
2
R
a
×
b
преобразовываются в некоторые вектор-дескрипторы
x
i
2
R
n
фиксированной размерности
n
. Это позволяет работать с по-
следовательностью изображений
[I
1
, . . . ,
I
N
]
2
R
a
×
b
×
N
как с матрицей
X = [x
1
, . . . ,
x
N
]
2
R
n
×
N
.
В таких случаях графы обычно представляются в виде инци-
дентных и смежных матриц. Однако в иерархическом графе связи
присутствуют только на соседних уровнях, поэтому элементы на
определенных индексах всегда будут нулевыми, что неэффективно. В
настоящей работе структура, а следовательно, и размерность, фор-
мируемого метаграфа для каждого изображения зависит от самого
изображения. В связи с этим для приведения метаграфа к одной
размерности, а также сохранения его пространственной структуры
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 4 39
