Быстрый алгоритм вычисления преобразования Хафа для изображений произвольного размера с переиспользованием выделенной памяти

In-place алгоритмы эффективно используют память, уже выделенную для входных данных, ограничиваясь лишь незначительным дополнительным объемом памяти для промежуточных вычислений. Для изображений ширины, равной степени двойки, известен in-place алгоритм, являющийся вариацией стандартного алгоритма Брейди – Ёна для вычисления преобразования Хафа. Однако этот алгоритм неприменим к изображениям с произвольной шириной, наиболее часто встречающимся на практике. Напротив, out-of-place алгоритм $\mathit{FHT}2\mathit{DS}$ может обрабатывать изображения различных размеров. В настоящей статье представлен in-place вариант алгоритма $\mathit{FHT}2\mathit{DS}$, названный $\mathit{FHT}2\mathit{IDS}$. Мы показываем, что алгоритм $\mathit{FHT}2\mathit{IDS}$ дает такие же результаты, как и алгоритм $\mathit{FHT}2\mathit{DS}$, но использует значительно меньше памяти на каждом шаге рекурсии. В частности, на каждом шаге рекурсии алгоритм $\mathit{FHT}2\mathit{IDS}$ требует массива размера не более $w+h$ (где $w$ и $h$ – ширина и высота изображения), в то время как алгоритм $\mathit{FHT}2\mathit{DS}$ требует массива размера $wh$. Экспериментальные результаты показывают, что алгоритм $\mathit{FHT}2\mathit{IDS}$, реализованный на C/C++, работает на 26% быстрее своего out-of-place аналога, алгоритма $\mathit{FHT}2\mathit{DS}$. Алгоритм $\mathit{FHT}2\mathit{IDS}$ также доступен на Python через открытый исходный код библиотеки adrt.