Самый быстрый метод для вычисления свертки

Question

Я должен применить фильтр свертки для каждого ряда изображений. Классика - это 360 изображений размером 1024х1024 пикселей. В моем случае это 720 изображений 560х600 пикселей.

Проблема в том, что мой код намного медленнее, чем рекламируется в статьях.

Я реализовал наивную свертку, и это занимает 2 м 30 с. Затем я переключился на FFT, используя fftw. Я использовал сложный комплекс 2, фильтруя две строки в каждом преобразовании. Мне сейчас около 20 лет.

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

Численные рецепты предлагают избегать сортировки, выполненной в dft, и соответственно адаптировать функцию фильтра частотной области. Но нет примера кода, как это можно сделать.

Может быть, я теряю время на копирование данных. С реальным 2 реальным преобразованием мне не пришлось бы копировать данные в сложные значения. Но я все равно должен дополнить 0.

РЕДАКТИРОВАТЬ: см. Мой собственный ответ ниже для получения информации о прогрессе и дополнительной информации по решению этой проблемы.

Вопрос (точная переформулировка):

Я ищу алгоритм или фрагмент кода, чтобы применить очень быструю свертку к дискретной непериодической функции (от 512 до 2048 значений). По всей видимости, лучше всего использовать преобразование Фурье с дискретным временем. Однако я бы хотел избежать копирования и преобразования данных в сложные, а также избегать переупорядочения бабочек.

Answer 1

FFT - самая быстрая техника, известная для свертки сигналов, а FFTW - самая быстрая бесплатная библиотека, доступная для вычисления FFT.

Ключом к достижению максимальной производительности (вне аппаратного обеспечения ... хорошее предложение для графического процессора) будет добавление сигналов в степень двойки. При использовании FFTW используйте настройку «пациент» при создании плана, чтобы добиться максимальной производительности. Маловероятно, что вы будете выполнять более быструю реализацию, чем FFTW (забудьте о N.R.). Также убедитесь, что вы используете реальную версию 1D БПФ, а не сложную версию; и используйте только одинарную (с плавающей запятой) точность, если можете.

Если FFTW не подойдет вам, я бы посмотрел на (очень доступную) библиотеку Intel IPP. Имеются вручную настроенные БПФ для процессоров Intel, оптимизированные для изображений с различной глубиной цвета.

Пол
CenterSpace Программное обеспечение

Answer 2

Вы можете добавить обработку изображений в качестве тега.

Но эта статья может представлять интерес, особенно если предположить, что изображение является степенью или 2. Вы также можете увидеть, где они оптимизируют БПФ. Я ожидаю, что статьи, которые вы просматриваете, сделали некоторые предположения, а затем оптимизировали уравнения для них.

http://www.gamasutra.com/view/feature/3993/sponsored_feature_implementation_.php

Если вы хотите идти быстрее, вы можете использовать графический процессор для фактического выполнения работы.

Эта книга может быть полезна для вас, если вы идете с GPU: http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

Этот ответ предназначен для сбора отзывов о ходе работы по этому вопросу.

Редактировать 11 окт .:

Время выполнения, которое я измерил, не отражает эффективное время БПФ. Я заметил, что когда моя программа заканчивается, процессор все еще занят системным временем до 42% в течение 10 секунд. Когда я жду, пока ЦП вернется к 0%, перед перезапуском моей программы я получу время выполнения 15.35 с, которое зависит от обработки графическим процессором. Я получаю то же самое время, если закомментирую фильтрацию FFT.

Таким образом, FFT на самом деле быстрее, чем GPU, и ему просто мешала конкурирующая системная задача. Я еще не знаю, что это за системная задача. Я подозреваю, что это связано с выделением огромного блока кучи, куда я копирую результат обработки перед записью его на диск. Для ввода данных я использую карту памяти.

Теперь я изменю свой код, чтобы получить точное измерение времени обработки БПФ. Ускорение процесса по-прежнему актуально, поскольку есть возможность оптимизировать обработку на GPU, например, путем конвейерной передачи данных в процесс.