3.2. Использование полиномиальных преобразований для вычисления двумерной свертки

Непосредственное выполнение двумерной нерекурсивной фильтрации массива требует вычисления числа операций, пропорционального (где — размеры апертуры свертки) и, таким образом, большой вычислительной мощности даже для относительно малых сверток. Это обстоятельство стимулировало ряд попыток найти более эффективные методы реализации двумерных нерекурсивных цифровых фильтров.

В большинстве этих методов цифровая нерекурсивная фильтрация осуществляется путем вычисления серии циклических сверток фрагментов, полученных секционированием входных последовательностей и дополнением их соответствующим числом нулей. Окончательный результат цифровой фильтрации при этом получается методом перекрытия с суммированием или перекрытия с накоплением [3.10]. При таком подходе объем вычислений определяется объемом вычислений циклических сверток, которые обычно сильно упрощаются при использовании алгоритмов быстрых преобразований Фурье (БПФ) ;[3.12], теоретикочисловых преобразований (ТЧП) [3.8, 3.9] или метода Агарвала — Кули [3.2]. По сравнению с прямым вычислением эти методы позволяют существенно снизить число операций, но, вообще говоря, для вычисления двумерных сверток

они не являются оптимальными. Вычисление с помощью БПФ связано с операциями над комплексными числами, значительными ошибками округления, требует определенных средств для вычисления тригонометрических функций и по-прежнему большого числа умножений. ТЧП могут быть вычислены без умножений и без ошибок округления при вычислении свертки. Однако эти преобразования строго ограничены по длине слова, длине преобразуемой последовательности и используют модулярную арифметику, которая обычно в универсальных ЭВМ реализуется недостаточно эффективно. Метод Агарвала — Кули, основанный на вложении нескольких коротких сверток, привлекателен для одномерных сверток, так как он не использует модулярной арифметики и не требует каких-либо манипуляций с тригонометрическими функциями. К сожалению, этот метод не очень эффективен для двумерных сверток.

Покажем, что с помощью полиномиальных преобразований [3.3, 3.5] для отображения двумерных сверток в одномерные свертки и полиномиальные произведения можно значительно упростить вычисление двумерных сверток. Полиномиальные преобразования определены на полях полиномов и обладают свойством циклической свертки. Эти преобразования вычисляются в обычной арифметике без умножений и в сочетании с эффективными алгоритмами короткой свертки и полиномиального произведения позволяют минимизировать объем вычислений двумерных сверток.