3 / 13
Оценка сложности алгоритма рекурсивного поиска области изображения
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
35
Рис. 1.
Локализация объекта рекурсивным разбиением изображения на области
Таким образом, алгоритм найдет те подобласти изображения (если они
есть), которые содержат искомый объект (или несколько объектов).
В случае, если определить факт наличия искомого объекта в произвольном
месте некоей подобласти возможно лишь с некоторой вероятностью (способ
определения вероятности зависит от реализации классификатора), то такое раз-
биение изображения может быть представлено в виде дерева принятия реше-
ний [15], как показано на рис. 2.
Оценка вычислительной сложности алгоритма рекурсивного поиска об-
ласти изображения, содержащей объект.
Примем исходные размеры окна,
равными размерам самого изображения
M
×
N
пикселей и, уменьшая на каждом
из
t
шагов ширину и высоту окна в
p
и
q
раз, закончим рассмотрение (в худшем
случае) окнами размерами 1 × 1 пиксель. Следовательно, число шагов измене-
ния размера окна
t
= log
p
M
= log
q
N
.
В худшем случае, во-первых, имеем шаги смещения подокна в окне по
горизонтали и вертикали (обозначим их
h
m
и
h
n
) равные 1 пиксель, а во-вторых,
как нетрудно заметить, если на последнем шаге размеры окон будут равны 1 × 1
пиксель, то на предпоследнем —
p
×
q
пикселей, на шаге перед ним —
p
2
×
q
2
и т. д. Число положений окна (
i
+1)-го размера в окне размера
i
-го равно
(
) (
)
1
1
1
1 ,
t i
t i
t i
t i
i
c p p
q q
− +
−
− + −
=
− +
− +
(1)
где
, ,1
i
t
=
при
i
= 1 имеем число подокон, рассматриваемых на первом шаге
алгоритма. Полагаем, что
i
= 0 соответствует одному окну размером со всю об-
ласть изображения, которое не относится к данной формуле, поскольку такое
окно не содержится ни в каком большем окне и, следовательно, говорить о ко-
личестве его положений в окне более крупного размера некорректно.