7 / 13
Оценка сложности алгоритма рекурсивного поиска области изображения
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
39
(
)
(
)
2
1/3 1
,
t
O S
−
(10)
т. е. является суперполиномиальной.
Сравнение вычислительных сложностей рекурсивного алгоритма и алго-
ритма скользящего окна.
Нетрудно показать, что алгоритм скользящих окон име-
ет в худшем случае линейно-логарифмическую вычислительную сложность по-
рядка
O
(
S
log
S
) от площади изображения
S
.
Очевидно, что порядок вычислительной сложности (10) алгоритма рекурсив-
ного поиска разбиением изображения на подобласти в худшем случае значительно
выше порядка вычислительной сложности алгоритма скользящего окна.
Однако сложность рекурсивного алгоритма соответствует сложности, опре-
деленной в предыдущем разделе, в случае, если на каждом шаге рекурсии для
дальнейшего рассмотрения выбирать все подокна. Кроме того, при оценке вычи-
слительной сложности рекурсивного алгоритма в худшем случае было допущено,
что окна значительно перекрывают друг друга, поскольку смещения окон было
решено считать равными одному пикселю по горизонтали и одному пикселю по
вертикали. Эти условия ведут к многократному повторному рассмотрению
подокон, полученных на разных ветвях рекурсии.
Часто в задачах локализации объекта на изображении дело обстоит иначе.
Сложность алгоритма скользящего окна можно уменьшить, лишь увеличивая
смещения окна за один шаг и/или уменьшая число размеров рассматриваемых
окон, что ведет к повышению вероятности пропуска окном искомого объекта.
Алгоритм рекурсивного разбиения изображения помимо тех же возможностей
уменьшения вычислительной сложности, применимых для скользящего окна,
позволяет значительно сократить время вычисления на каждом шаге рекурсии
(и всех последующих) за счет уменьшения числа выбираемых для дальнейшего
рассмотрения подокон данного окна.
Использовать алгоритм предполагалось совместно с классификатором,
способным давать ответ «Да» или «Нет» на вопрос, есть ли в данном подокне
искомый объект, или оценить вероятность присутствия объекта в том или ином
окне. Такой подход (при условии построения соответствующего классификато-
ра) позволит на каждом шаге рекурсии отбросить большинство окон и значи-
тельно сократить вычислительные затраты для всех последующих шагов.
Очевидно, что рекурсивное разбиение изображения на подокна будет эф-
фективно тогда, когда при прочих равных условиях (одинаковых
p
,
q, t, s
) и ре-
курсивном обходе будет в сумме рассмотрено (за счет отбрасывания заведомо
не содержащих объект окон) меньше окон, чем существует позиций окон всех
t
+ 1
размеров (включая исходное изображение) в алгоритме скользящего окна.
Число всех положений скользящего окна для всех
t
+ 1 размеров в изображении
M
×
N
может быть найдено по формуле
(
) (
)
0
1
1 .
t
i
i
i
M p
N q
=
− + − +