Я работаю с двумерной корреляцией для методов обработки изображений (распознавание образов и т. Д.). Мне было интересно, есть ли теоретический подход к тому, как определить, когда использовать умножение в частотном пространстве над корреляцией во временном пространстве. Для размеров 2 x частотное пространство, очевидно, быстрее, но как насчет небольших, простых размеров, например, 11?
Я предполагаю, что это делается на обычном процессоре, одном ядре, выполняющем один простой поток, без сложного оборудования. Если происходит нечто большее, это, вероятно, может быть объяснено корректировкой рассуждений для более простой системы. Нельзя сказать намного больше без конкретной системы для обсуждения, без целого учебника или исследовательской работы, чтобы охватить целый ряд возможностей.
Я бы не беспокоился о размерах степени двух. Это не важно Алгоритмы БПФ с бабочками и всем, что существует для факторов 3 или любого небольшого числа, а не только 2. Существуют и умные алгоритмы для рядов простых данных. Я не люблю цитировать Википедию по этому поводу из-за ее непостоянства, но в любом случае:
существуют БПФ со сложностью O (N log N) для всех N, даже для простых N
Реализации FFT для произвольного N можно найти в библиотеке FFTW GPL .
Единственный надежный способ с точки зрения серьезного проектирования - это строить и измерять, но мы, безусловно, можем получить представление из теории, чтобы увидеть взаимосвязи между переменными. Нам нужны оценки того, сколько арифметических операций задействовано для каждого метода.
Умножение по-прежнему медленнее, чем сложение на большинстве процессоров, даже если за последние годы разница значительно сократилась, поэтому давайте просто посчитаем умножения. Учет также сложения требует немного больше обдумывания и отслеживания вещей.
Простая свертка, фактически умножение и сложение с использованием ядра свертки, повторяющегося для каждого выходного пикселя, требует умножения W² · K², где W - количество пикселей вдоль одной стороны изображения (для простоты предполагается квадрат), а K - размер ядра свертки, в виде пикселей вдоль одной стороны. Для вычисления одного выходного пикселя требуется умножение K² с использованием ядра и части входного изображения того же размера. Повторите эти действия для всех выходных пикселей, число которых совпадает с номером входного изображения.
(N мульт ) прямой = W² · K²
Чтобы выполнить работу в пространстве Фурье, мы должны преобразовать изображение Фурье. Это делается путем применения БПФ к каждому столбцу отдельно, а затем к каждой строке. БПФ для N точек данных занимает около 2N · log (N) умножений; мы хотим, чтобы N было W, длина одного столбца или строки. Все логарифмы здесь являются основанием два.
Есть W строк и W столбцов, поэтому после того, как все FFT сделаны, мы сделали 2W · (2W · log (W)) умножения. Удвойте это, потому что после того, как мы умножим на преобразование Фурье ядра, мы должны инвертировать Фурье данные, чтобы вернуться к разумному изображению. Это 8W² · log (W). Конечно, нужно умножить на преобразование Фурье ядра, еще одно умножение W2. (Делается один раз, а не один раз для выходного пикселя, для строки или чего-либо еще.) Это сложные умножения, так что это реальные умножения 4W².
Так что, если я не обманул (и я, вероятно, сделал), у нас есть
(N мульт ) Фурье = 4 Вт² · (2 · log (Вт) + 1)
Когда мы хотим делать вещи прямым путем? Когда K достаточно мало, чтобы W2 · K2 было меньше 4W2 · (2 · log (W) + 1). Общий фактор W² легко вычленяется. Вероятно, мы можем опустить «+1», поскольку имеем дело с идеализированными оценками. +1, вероятно, теряется в ошибках по сравнению с фактическими реализациями, не считая сложений, накладных расходов цикла и так далее. Это оставляет:
K² < 8·log(W)
Это приблизительное условие для выбора прямого подхода по сравнению с частотным пространственным подходом.
Обратите внимание, что корреляция двух изображений одинакового размера точно так же, как свертка с ядром размером K = W. Фурье-пространство всегда способ сделать это.
Это может быть уточнено и аргументировано для учета накладных расходов, конвейерной обработки кодов операций, операций с плавающей запятой и фиксированной запятой, а также выброса окна с GPGPU и специализированным оборудованием.