8 / 13
К.А. Кивва, И.В. Рудаков
40
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
По-прежнему считаем, что сдвиг окон относительно друг друга равен одно-
му пикселю по вертикали и/или по горизонтали. С другой стороны, число всех
окон, рассматриваемых рекурсивно при произвольном выборе на
i
-м шаге ре-
курсии
k
i
подокон для рассмотрения на (
i
+ 1)-м шаге (см. формулу (3)) равно
(
) (
)
1
1
1
1
1
1
1
.
t
t
t
t
t
i
i
p p
q q
k
−
−
−
=
+ − + − + +
Таким образом, условие, при котором рекурсивный алгоритм будет эффек-
тивнее алгоритма скользящего окна, можно записать (учитывая, что
M = p
t
,
N = q
t
) в виде
(
) (
)
1
2
1
0
1
1 .
t
t
t
i
t
i
i
i
i
k
p p
q q
−
−
=
=
<
− + − +
(11)
Хотя нахождение точного решения данного неравенства — задача крайне
сложная из-за большого числа переменных, однако, во-первых, решения суще-
ствуют (например, очевидно, к области решения относится
k
i
= 1 для любого
k
i
,
как было показано ранее), во-вторых, можно найти решения в некоторых част-
ных случаях. Например, пусть в каждом окне на каждом шаге выбирается для
дальнейшего рассмотрения одинаковое число подокон (т. е.
k
1
= k
,
k
2
= k
2
и т. д.,
поскольку
k
i
, как указано, это суммарное число всех выбранных на
i
-м шаге
подокон всех выбранных на предыдущем шаге окон). Тогда выражение (11), с
учетом суммы геометрической прогрессии, принимает вид
(
)
(
)
(
) (
)
1
2
0
1
1
1 .
1
t
t
t
i
t
i
i
k k
p p
q q
k
−
−
=
−
<
− + − +
−
(12)
Для иллюстрации данного условия приведен график (рис. 3), отражающий
преимущество рекурсивного подхода перед скользящим окном для некоторых
значений
k
при различных
t
в данном случае (т. е. при
k
i
= k
i
).
Видно, если в каждом рассматриваемом во время рекурсии окне выбирать
одинаковое число
k
подокон, то существуют целые
k
, относящиеся к области реше-
ния неравенства (12), т. е. такие, при которых использование рекурсивного алго-
ритма позволит обработать меньше окон, чем в случае использования алгоритма
скользящего окна. Как следует из приведенного графика, в некоторых случаях ис-
пользование рекурсивного алгоритма вместо скользящего окна способно дать зна-
чительный прирост в скорости обработки изображения. Данное преимущество по-
степенно теряется при увеличении числа
t
шагов изменения размеров рассматрива-
емых окон. Это объясняется экспоненциальным ростом числа рассматриваемых
рекурсивно окон при увеличении
t
, как следует из неравенства (12). В самом деле,
каждое выбранное окно на начальных этапах рекурсии создает отдельную ветвь
рекурсии, умножая число окон, выбираемых на последующих этапах.
Таким образом, очевидно, что выгоднее на более ранних этапах рекурсии
исключать из рассмотрения как можно больше окон, не содержащих искомый
объект.