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