ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
33
УДК 004.021
DOI: 10.18698/0236-3933-2017-2-33-45
ОЦЕНКА СЛОЖНОСТИ АЛГОРИТМА РЕКУРСИВНОГО ПОИСКА
ОБЛАСТИ ИЗОБРАЖЕНИЯ
К.А. Кивва
k.kivva@gmail.comИ.В. Рудаков
irudakov@yandex.ruМГТУ им. Н.Э. Баумана, Москва, Российская Федерация
Аннотация
Ключевые слова
Приведены описание алгоритма рекурсивного поиска
области изображения и оценка его вычислительной
сложности, а также сравнение вычислительной сложно-
сти данного алгоритма с вычислительной сложностью
алгоритма скользящего окна. Предложен критерий
определения эффективности использования алгоритма
рекурсивного поиска вместо алгоритма скользящего
окна. Согласно предложенному критерию, обоснована
эффективность использования рекурсивного алгоритма
Обработка изображения, компью-
терное зрение, скользящее окно,
локализация объекта
Поступила в редакцию 09.06.2016
©МГТУ им. Н.Э. Баумана, 2017
Введение.
Компьютерное зрение — это быстро развивающаяся область искус-
ственного интеллекта, находящая применение в различных сферах человече-
ской деятельности: от картографии [1] и контроля качества [2, 3] до создания
беспилотных систем [4, 5] и дополненной реальности [6]. Одной из задач ком-
пьютерного зрения является задача локализация объекта на изображении. Не-
смотря на множество разработанных подходов к ее решению, большинство из
них не универсальны и требуют значительных вычислительных затрат.
Одна из подзадач локализации объекта — разбиение изображения на обла-
сти, потенциально содержащие искомый объект. Используемый во многих ра-
ботах механизм локализации основан на алгоритме скользящего окна [7]. Дан-
ный алгоритм осуществляет полный перебор множества возможных областей
изображения. Можно предположить, что рекурсивный подход к разбиению
изображения на подобласти с исключением из рассмотрения части подокон на
каждом шаге рекурсии позволит сократить число рассматриваемых областей и,
соответственно, уменьшить вычислительную сложность локализации объекта.
Данный алгоритм разбиения с точки зрения оценки вычислительной сложности
фактически построен по принципу «разделяй и властвуй» [8], заключающемуся
в разбиении исходной задачи на подзадачи меньшего размера с последующим
объединением результатов.
Анализ сложности рекурсивных алгоритмов — одна из наиболее сложных и
до конца не решенных проблем метрической теории алгоритмов [9]. Основны-
ми современными инструментами исследования сложности рекурсивных алго-
ритмов являются метод рекуррентных соотношений и теоретико-графовый ме-
тод исследования дерева рекурсии [9].