Пусть area
(
CC
[
p
])
— функция площади
p
-го компонента;
Пусть dist
(
CC
[
p
]
, CC
[
p
1])
— евклидово расстояние между
p
-м и
p
1
-м компонентами;
Пусть
f
(
area
(
CC
[
p
])
,
area
(
CC
[
p
1]))
— группирующая функция
p
-го и
p
1
-го компонентов;
Пусть swap
(
area
(
CC
[
p
])
,
area
(
CC
[
p
1]) )
— функция перестановки
p
-
го и
p
1
-го компонентов;
p = p1 = 0;
while (p1 меньше L)
{
p
2 =
p
1 + 1
;
while (
p
1
меньше
p
2
)
{
p
=
p
2
;
while(p меньше L)
{
if
(
dist
(
CC
[
p
]
, CC
[
p
1])
меньше
f
(
area
(
CC
[
p
])
,
area
(
CC
[
p
1])))
{
if (
p
не равно
p
2
)
swap
(
area
(
CC
[
p
])
, area
(
CC
[
p
1]) )
;
инкрементировать
p
2
;
}
инкрементировать p;
}
инкрементировать p1;
}
CC
[
p
0
, p
1) :
обнаруженная группа;
CC
[
p
1
, p
2) :
принадлежит другой группе;
p
0 =
p
1
;
}
Вычислительная сложность алгоритма составляет
O
(
n
2
)
в худшем
случае, когда каждый компонент изолирован на изображении с общим
числом компонентов
n
. Очевидно, что для реальных данных затрачи-
ваемое время будет существенно меньше. Описанная реализация га-
рантирует, что для каждой пары компонентов будет определена только
одна прямая связь в процессе группировки. Кроме того, гарантируется
независимость результата группировки от выбранного стартового ком-
понента. В итоге результаты начальной группировки объединяются по
локализации и критерию пересечения в выпуклые полигоны блоков
текста разного уровня.
Далее описаны роль параметра
k
и выбор его значения. Для группы
из
n
g
компонентов плотность
p
g
определяется как отношение суммы
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
159
1,2,3,4,5,6 8,9,10,11,12,13,14,15