2021-10-23
49
Для поиска на изображении однопиксельных экстремумов предлагается алгоритм на основе центрально-симметричного сканирования (SSEF – SymmetricScan-based Extreme Finding). Сущность алгоритма состоит в выборе пикселей изображения в порядке строчной развертки, оценке распределения яркости в окрестностях размером 
пикселей, фиксировании центрального пикселя в качестве экстремума, если все пиксели в его окрестности имеют меньшие или большие значения. Предлагаемый алгоритм отличается от известных алгоритмов поиска однопиксельных экстремумов порядком выборки пикселей в окрестности анализируемого на экстремум пикселя, который осуществляется центрально-симметрично – поочередно с различных направлений относительно центра области анализа (рис. 4). Центральный пиксель С не является максимальным, если найден любой более значимый
или равный ему пиксель. Немаксимальный пиксел затем передается на этап поиска локальных минимумов. Если найден любой менее значимый или равный пиксель, то центральный пиксель С также не является минимальным и алгоритм переходит на следующий пиксель по порядку сканирования изображения. Процедура поиска продолжается до тех пор, пока все пиксели
не будут обработаны.
| а | б | в |
Рис. 4. Виды центрально-симметричной окрестности размером 
пикселя
Алгоритм поиска состоит из следующих шагов
1. Инициализация. На данном шаге осуществляется буферизация исходного изображения 
размером 
пикселей. Формируется матрица разметки экстремумов 
, элементы которой определяются с помощью выражений 
при 
.
Формирование вектора индексов центрально-симметричного сканирования с помощью выражения 
, элементы которого определяются следующим образом: 
при 
(рис.4 а).
2. Начало цикла поиска локальных однопиксельных экстремумов
2.1. Поиск локальных однопиксельных максимумов. Осуществляется формирование матрицы разметки значений максимумов 
с помощью выражения
(1)
при 
2.2. Поиск локальных однопиксельных минимумов. Осуществляется формирование матрицы разметки значений минимумов 
с помощью выражения
(2)
при 
2.3. Проверка условия окончания цикла: 
и 
. Если выполняется условие,
то осуществляется переход к шагу 2.1. Если это условие не выполняется, то осуществляется выход из алгоритма.
Вычислительная сложность алгоритма определяется числом вещественных операций сложения (алгоритм имеет нулевую вычислительную сложность умножения) с помощью выражения
(3)
где 
– число сравнений на пиксель (Comparisons Per Pixel), 
– размеры исходного изображения.
В результате выполнения данного алгоритма формируется матрица разметки локальных экстремумов, значение каждого элемента которой указывает на экстремум изображения (значение 1 – максимум, значение 0 – минимум), которому принадлежит пиксель разметки изображения с соответствующими координатами. Эти данные используются для последующей обработки изображений.
