4 / 13
К.А. Кивва, И.В. Рудаков
36
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
Предположим, что в худшем случае на каждом шаге рекурсивного разбие-
ния искомый объект обнаруживается алгоритмом не в одном окне, а в несколь-
ких, и/или изображение содержит несколько искомых объектов. Тогда после
каждого шага разбиения (кроме последнего) для дальнейшего рассмотрения
выбираются несколько подокон. Объект будет считаться найденным, если его
присутствие обнаружено в данном окне и выполняется одно из двух условий.
1. Окно, содержащее объект, имеет минимально допустимый размер. Для
оценки сложности в худшем случае минимально допустимым размером окна вы-
бран 1 × 1 пиксель, что произойдет при
i = t
(1). В реальных задачах этот размер в
основном будет больше, поскольку один пиксель малоинформативен для анализа.
2. Размер данного окна больше минимально допустимого, но ни одно из его
подокон не содержит искомый объект.
Таким образом, любая ветвь рекурсии остановится либо когда найдет объект
в соответствии с приведенным критерием, либо когда ни одно подокно, предна-
значенное для рассмотрения на следующем этапе рекурсии, не будет содержать
искомый объект.
Определим следующие величины [8]: вычислительные сложности случаев, в
которых рекурсия останавливается (назовем такие случаи конечными); число под-
задач, получаемых при разбиении задачи на каждом шаге; вычислительную слож-
ность разбиения задачи на подзадачи; вычислительную сложность объединения
результатов.
Вычислительная сложность конечных случаев полностью определяется
сложностью анализа одного окна классификатором в целях определения наличия
Рис. 2.
Локализация объекта рекурсивным разбиением изображения с учетом
вероятностей нахождения объекта в окне