Я пытаюсь реализовать алгоритм зрения, который включает этап предварительной фильтрации с фильтром Лапласа-Гаусса 9x9. Можете ли вы указать документ, в котором кратко объясняется реализация быстрых фильтров? Я думаю, что я должен использовать БПФ для наиболее эффективной фильтрации.
Быстрый способ реализации 2D свертки в C
Ответы (3)
Вы уверены, что хотите использовать БПФ? Это будет преобразование всего массива, что будет дорого. Если вы уже выбрали сверточный фильтр 9x9, вам не нужен БПФ.
Как правило, самый дешевый способ выполнить свертку в C — настроить цикл, который перемещает указатель по массиву, суммирует свернутые значения в каждой точке и записывает данные в новый массив. Затем этот цикл можно распараллелить с помощью вашего любимого метода (векторизация компилятором, библиотеки MPI, OpenMP и т. д.).
По поводу границ:
- Если вы предполагаете, что значения равны 0 за пределами границ, добавьте 4-элементную границу 0 к вашему 2d-массиву точек. Это позволит избежать необходимости использования операторов if для обработки границ, которые являются дорогостоящими.
- Если ваши данные переносятся по границам (т. е. они периодические), используйте модуль или добавьте границу из 4 элементов, которая копирует противоположную сторону сетки (abcdefg -> fgabcdefgab для 2 точек). **Примечание: это то, что вы неявно предполагаете с любым преобразованием Фурье, включая БПФ**. Если это не так, вам нужно будет учесть это, прежде чем выполнять какое-либо БПФ.
4 точки связаны с тем, что максимальное перекрытие границ ядра 9x9 составляет 4 точки за пределами основной сетки. Таким образом, для ядра размером 2n+1 x 2n+1 требуется n точек границы.
Если вам нужно, чтобы эта свертка была действительно быстрой, и/или ваша сетка большая, подумайте о том, чтобы разбить ее на более мелкие части, которые можно хранить в кеше процессора и, таким образом, рассчитывать гораздо быстрее. Это также относится к любой разгрузке графического процессора, которую вы, возможно, захотите выполнить (они идеально подходят для этого типа вычислений с плавающей запятой).
person
Phil H
schedule
24.03.2009
Использование границы нулей предполагает, что данные довольно белые и имеют нулевое среднее. Использование фильтра размытия для ненулевых средних данных с нулевой границей может привести к нежелательным искажениям на краях.
- person Jukka Dahlbom; 24.03.2009
Достаточно верно. Вместо этого использование БПФ предполагало бы, что данные переносятся на границы, что также может быть неверным. Нули должны были удалить дорогостоящие ifs. Я добавлю кое-что о границах.
- person Phil H; 24.03.2009
Юкка граница всегда страдает. Вы должны что-то сделать, чтобы объяснить это, и Фил упоминает пару традиционных методов. Единственный способ не страдать от границы — сделать 2d-свертку, а затем обрезать на 4 пикселя со всех сторон изображения.
- person Trevor Boyd Smith; 24.03.2009
Тревор: Во-первых, часть границ — это правка после комментария Юкки. Кроме того, ваш метод обрезки по-прежнему будет вызывать проблемы, если неверно установить граничное значение, равное 0. Например, если фон изображения был синим, это не сработает.
- person Phil H; 24.03.2009
Вот теоретическая ссылка http://hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf
А вот ссылка на fftw, довольно хорошую библиотеку БПФ, которую я использовал в прошлом (проверьте лицензии, чтобы убедиться, что она подходит) http://www.fftw.org/
Все, что вы делаете, это БПФ вашего изображения и ядра (матрица 9x9). Умножить вместе, затем обратно преобразовать.
Однако с матрицей 9x9 вам все же лучше делать это в реальных координатах (просто с двойным циклом по пикселям изображения и матрице). Попробуйте оба способа!
person
Greg Reynolds
schedule
24.03.2009
На самом деле вам не нужно использовать размер БПФ, достаточно большой, чтобы вместить все изображение. Вы можете сделать много меньших перекрывающихся 2d fft. Вы можете искать «быстрая свертка», «сохранение перекрытия», «добавление перекрытия».
Однако для ядра 9x9. Вы можете не увидеть большого преимущества в скорости.
person
Mark Borgerding
schedule
13.08.2009
