Рис. 2. Формирование метаграфа (алгоритм
f
) для трех доменов (
а
), разряжен-
ных векторов (
б
) и разностного вектора для домена
D
1
(
в
), частный случай для
K
= 2
(заштрихованные вершины формально отсутствуют в метаграфе (=
;
),
в векторе они присутствуют как пустые элементы для сохранения структу-
ры графа; каждый тип фигуры означает отдельный домен
D
q
, толщина ребра
ассоциирована с его весовым значением; стрелкой показано направление вы-
числения разности)
и других свойств применяется преобразование набора вершин V в
разряженный вектор-столбец
g
iD
q
= [
g
1
, . . . , g
n
]
т
2
D
n
q
, а набора ребер
(весов) E в разряженный вектор-столбец
w
iD
q
= [0
, w
1
, . . . , w
n
]
т
2
R
n
,
где
m
(
j, k
) =
j
−
1
X
i
=0
K
i
+
k, m
2 {
1
, . . . , n
}
— индекс вершины
v
jkD
q
и
ребра
w
jkD
q
в векторах
g
iD
q
и
w
iD
q
соответственно. Такое представле-
ние является обратимым, т.е. возможно восстановить граф
G
i
=
f
(I
i
)
(см. рис. 2). Размерность векторов
n
=
h
X
i
=0
K
i
, где
h
= log
c
max(
a, b
)
—
высота дерева, которая будет идентична для всех изображений раз-
мером
ab
в независимости от домена;
c >
1
— отношение размеров
блоков верхнего уровня к нижним (обычно равно 2). При этом число
нулей будет отличаться в зависимости от содержания изображения и
домена и будет больше у менее информативных изображений. Осо-
бенностью является то, что, применяя разряженные типы хранения
данных, в которых для хранения нулевых значений не выделяется па-
мять, можно решить проблему хранения вектора такой размерности.
Отметим, что, если вектор весов известен для всех
j
и
k
, то значе-
ния вершин являются функцией значений весов и вершин уровня
h
:
4
g
i
D
q
=
ϕ
(
4
w
i
D
q
)
. Таким образом, последовательность изображений
переходит в матрицу разряженных метаграфов:
40 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2014. № 4
