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

Question

Мне нужно применить фильтр свертки к каждой строке множества изображений.Классика — 360 изображений размером 1024х1024 пикселей.В моем случае это 720 изображений размером 560x600 пикселей.

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

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

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

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

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

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

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

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

Answer 1

БПФ — это самый быстрый метод, известный для свертки сигналов, а FFTW — самая быстрая бесплатная библиотека, доступная для вычисления БПФ.

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

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

Павел
ЦентрКосмос Программное обеспечение

Answer 2

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

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

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

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

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

Answer 3

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

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

Измеренное мною время выполнения не отражает эффективное время БПФ.Я заметил, что когда моя программа завершается, процессор по-прежнему занят в системное время до 42% в течение 10 с.Когда я жду, пока процессор вернется к 0%, перед перезапуском программы я получаю время выполнения 15,35 с, которое получается из-за обработки графического процессора.Я получу то же время, если закомментирую фильтрацию БПФ.

Таким образом, БПФ на самом деле в настоящее время быстрее, чем графический процессор, и ему просто мешает конкурирующая системная задача.Я пока не знаю, что это за системная задача.Я подозреваю, что это происходит из-за выделения огромного блока кучи, куда я копирую результат обработки перед записью его на диск.Для входных данных я использую карту памяти.

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