5 / 13
Оценка сложности алгоритма рекурсивного поиска области изображения
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
37
в нем объекта. Поскольку цель настоящей статьи — сравнить сложности алгорит-
мов скользящего окна и рекурсивного разбиения изображения вне зависимости от
используемых классификаторов, применяемых к каждому окну, то примем слож-
ность конечных случаев равной
O
(1).
Число подзадач, получаемых на
i
-м шаге рекурсии, соответствует числу окон,
потенциально содержащих объект, и предназначенных, таким образом, к даль-
нейшему разбиению. Обозначим это число
k
i
.
Сложностью разбиения задачи на подзадачи можно считать сложность ана-
лиза всех подокон данного окна (для выбора потенциально содержащих искомый
объект). Поскольку сложность анализа одного окна было решено принять равной
O
(1), то сложность анализа всех окон, полученных на
i
-м шаге, считаем равной
( )
.
i
i
D O c
=
(2)
Сложность объединения результатов (параметров искомых окон) в худшем
(с вычислительной точки зрения) случае равна
( )
,
i
O r
где
r
i
— число объектов,
найденных на данном шаге.
Учитывая сказанное, определяем сложность алгоритма рекурсивного раз-
биения изображения на подобласти с отбрасыванием областей, заведомо не со-
держащих искомый объект, используя рекуррентное соотношение:
( )
( )
(
)
( )
( )
=
=
+ + +
<
1 ,
если
;
1
, если
.
i
i
i
O
i t
T i
k T i
O c O r
i t
(3)
Выбрав в качестве размера одиночной задачи на каждом шаге рекурсии
площадь
s
текущего окна, исключив при этом величину
O
(
r
i
)
из соотношения
(3), как не влияющую на сложность алгоритма при увеличении размера анали-
зируемого изображения, можно переписать это соотношение в виде
( )
( )
(
)
( )
= =
=
+
> <
1 ,
если
1,
;
/
, если 1,
,
i
O
s
i t
T s
k T s d O s
s
i t
(4)
где
1/
.
t
d pq s
= =
(5)
Коэффициенты
k
i
в выражении (4) на каждом шаге, вообще говоря, зависят,
во-первых, от числа и размеров искомых объектов на изображении, а во-вторых,
от выбора
p
,
q
, шагов
h
n
,
h
m
(см. формулу (1)). Дело в том, что при слишком боль-
шой площади перекрытия подокон друг другом возрастает вероятность попадания
одного и того же объекта в несколько подокон одновременно. Также
k
i
зависят от
способности классификатора успешно отличать окна, содержащие объект, от тех,
которые его не содержат.
Разложив рекуррентное соотношение (4) в сумму, получим
( )
− −
−
−
− −
=
=
=
= +
+
∏
∏
1
1
2
1
1
1
1
.
t j
t
t
i
i
t j
i
j
i
s
T s
k
k s
d
(6)