Статьи автора

БЫСТРОЕ И ВЫСОКОТОЧНОЕ ПРЕОБРАЗОВАНИЕ ХАФА С ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТЬЮ Θ( log ) ДЛЯ ОБРАБОТКИ ПРЯМОУГОЛЬНЫХ ИЗОБРАЖЕНИЙ ПРОИЗВОЛЬНОГО РАЗМЕРА

Номер выпуска 4 от 01.04.2025

Преобразование Хафа (ПХ) является ключевым инструментом цифровой обработки изображений, применяемым в широком спектре научных задач – от распознавания документов до компьютерной томографии. Алгоритмические реализации ПХ традиционно оцениваются по двум параметрам: вычислительной сложности и точности, которая определяется как ошибка аппроксимации непрерывных прямых дискретными, формируемыми в ходе выполнения алгоритма. Быстрые алгоритмы ПХ (БПХ) с оптимальной линейно-логарифмической вычислительной сложностью хорошо изучены – примером является классический алгоритм Брейди – Ёна, применимый исключительно к изображениям с линейными размерами, равными степеням двойки. Его обобщения, такие как алгоритм , позволяют обрабатывать прямоугольные изображения произвольного размера, но точность реализуемого ими ПХ низкая, причем она уменьшается при увеличении размера обрабатываемого изображения. Существуют также алгоритмы ПХ, сохраняющие ограниченную сверху ошибку аппроксимации для изображений любого размера. Они обеспечивают более высокую точность, но их вычислительная сложность приближается к кубической, что делает их малопригодными при обработке больших изображений. В настоящей статье предложен алгоритм , сочетающий скорость, близкую к оптимальной, с высокой точностью. Алгоритм характеризуется вычислительной сложностью вида Θ( log ) при обработке изображений размера × . При этом предложенный алгоритм гарантирует ортотропную ошибку аппроксимации непрерывных прямых не более λ + 1/2, независимо от размера изображения и регулируемую управляющим метапараметром λ ∈ (0; 1]. В статье представлена сводная таблица экспериментальных результатов, которая может служить практическим ориентиром для выбора значения метапараметра λ с целью обеспечения баланса между точностью и вычислительной сложностью.

1 0