Поиск локальных экстремумов полутоновых изображений на основе центрально-симметричного сканирования

ПОИСК ЛОКАЛЬНЫХ ЭКСТРЕМУМОВ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЦЕНТРАЛЬНО-СИММЕТРИЧНОГО СКАНИРОВАНИЯ

Кодирование и цифровая обработка сигналов в инфокоммуникациях

УДК 621.391

ПОИСК ЛОКАЛЬНЫХ ЭКСТРЕМУМОВ ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЦЕНТРАЛЬНО-СИММЕТРИЧНОГО СКАНИРОВАНИЯ

А.Т. НГУЕН, В.Ю. ЦВЕТКОВ

Белорусский государственный университет информатики и радиоэлектроники, Республика Беларусь

Поступила в редакцию 18 ноября 2018

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

Ключевые слова: поиск локальных экстремумов, центрально-симметричное сканирование.

Введение

Поиск локальных экстремумов является базовой операцией для множества задач обработки изображений. Известен алгоритм NMS (Non-maximum Suppression – подавление немаксимальных значений), который первоначально использовался для уменьшения длительности откликов при детектировании тонких линий [1]. Алгоритм NMS является одномерным (1-D) и работает перпендикулярно к краям. В работе [2] предложен способ модификации алгоритма NMS для определения ключевых точек (реперов) изображения
в двухмерном пространстве пикселей изображения (2-D). Ключевые точки выбираются
как локальные максимумы изображения над некоторой окрестностью. Этот подход
к обнаружению углов был принят многими детекторами ключевых точек [3–5].
При исследовании эффективности поиска локальных экстремумов берется ориентир
на алгоритмы, требующие минимального использования памяти.

Известные алгоритмы NMS требуют фиксированного количества сравнений на пиксель независимо от размера окрестности исключения. Одномерный максимальный фильтр, например, требует трех сравнений на пиксель [6–8]. При последовательной реализации двухмерный максимальный фильтр использует шесть сравнений на пиксель. В работе [9], опубликованной
в 2006 году, предложен алгоритм разбиения блоков, который уменьшает количество сравнений до 2,39 на пиксель. Однако, 20-ю годами ранее, в работе [10] предложен алгоритм, имеющий аналогичную вычислительную сложность. В любом случае для большинства известных алгоритмов поиска локальных экстремумов необходимо выполнять более двух сравнений
на пиксель. В работе [1] модифицированы алгоритмы, предложенные в [9, 10] с целью уменьшения количества сравнений на пиксель до значения менее двух.