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

ТРАНСПОНИРОВАНИЕ СУММИРУЮЩИХ АЛГОРИТМОВ С СОХРАНЕНИЕМ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ПРИ ПОМОЩИ ГРАФОВОГО ПРЕДСТАВЛЕНИЯ ВЫЧИСЛЕНИЙ

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

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

13 0

БЫСТРЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ХАФА ДЛЯ ИЗОБРАЖЕНИЙ ПРОИЗВОЛЬНОГО РАЗМЕРА С ПЕРЕИСПОЛЬЗОВАНИЕМ ВЫДЕЛЕННОЙ ПАМЯТИ

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

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

13 0