Двумерный пиковый фильтр за почти линейное время

Abstract

Данная работа посвящена разработке быстрого алгоритма локальной пиковой фильтрации двумерных массивов. Продемонстрирована неоднозначность понятия локальный пик и введены дополнительные условия, ее устраняющие. Разработан корректный пиковый фильтр, учитывающий указанные условия. Для сравнительного анализа эффективности предложенного алгоритма описаны два известных алгоритма нахождения локальных максимумов. Приведены оценки вычислительной сложности алгоритмов для лучшего и худшего случаев, произведён анализ зависимости времени работы от размеров изображения и скользящего окна, а также количества локальных максимумов. Результаты экспериментальных исследований свидетельствуют о том, что корректный пиковый фильтр работает лучше своих некорректных аналогов.