Размытие по Гауссу с БПФ Вопросы

Question

У меня есть текущая реализация Gaussian Blur с использованием регулярной свертки. Он достаточно эффективен для небольших ядер, но как только размер ядра становится немного больше, производительность падает. Итак, я думаю реализовать свертку с использованием БПФ. У меня никогда не было опыта обработки изображений, связанных с БПФ, поэтому у меня есть несколько вопросов.

1. Разделяется ли свертка на основе 2D БПФ также на две одномерные свертки?

   • Если это правда, будет ли это выглядеть так: 1D FFT в каждой строке, а затем 1D FFT в каждом столбце, затем умножить на двумерное ядро, а затем обратное преобразование каждого столбца и обратное преобразование каждой строки? Или мне нужно умножать с 1D ядром после каждого 1D FFT Transform?

2. Теперь я понимаю, что размер ядра должен соответствовать размеру изображения (строка в случае 1D). Но как это повлияет на края? Нужно ли дополнять края изображения нулями? Если так, то размер ядра должен быть равен размеру изображения до или после заполнения?

Кроме того, это проект C++, и я планирую использовать kissFFT, так как это коммерческий проект. Вы можете предложить любые лучшие альтернативы. Спасибо.

РЕДАКТИРОВАТЬ: Спасибо за ответы, но у меня есть еще несколько вопросов.

1. Я вижу, что мнимая часть входного изображения будет иметь все нули. Но будет ли на выходе мнимая часть также иметь нули? Нужно ли умножать ядро ​​Гаусса на действительные и мнимые части?

2. У меня есть экземпляры одного и того же изображения, которые будут размыты в разных масштабах, то есть одно и то же изображение масштабируется до разных размеров и размыто при разных размерах ядра. Нужно ли выполнять FFT каждый раз, когда я масштабирую изображение, или я могу использовать одно и то же FFT?

3. Наконец, если я хотел визуализировать БПФ, я понимаю, что к БПФ должен применяться фильтр журнала. Но я действительно заблудился, какую часть следует использовать для визуализации БПФ? Реальная часть или мнимая часть.

4. Также для изображения размером 512x512, что будет размером с реальной и мнимой частями. Будут ли они одинаковой длины?

Еще раз спасибо за ваши подробные ответы.

Answer 1

1. Двумерное БПФ является разделяемым, и вы правы в том, как его выполнять, за исключением того, что вы должны умножить на двумерное БПФ двумерного ядра. Если вы используете kissfft, более простой способ выполнить 2-D FFT - просто использовать kiss_fftnd в каталоге инструментов пакета kissfft. Это будет делать многомерное БПФ.

2. Размер ядра не должен быть каким-либо конкретным размером. Если ядро ​​меньше, чем изображение, вам нужно просто обнулить его до размера изображения перед выполнением 2-D FFT. Вы также должны обнулить края изображения нулями, поскольку конволюция, выполняемая умножением в частотной области, фактически является круговой сверткой, и результаты обертываются по краям.

Итак, подведем итог (учитывая, что размер изображения составляет M x N):

1. придумать двумерное ядро ​​любого размера (U x V)
2. обнуление ядра до (M+U-1) x (N+V-1)
3. возьмите 2-D FFT ядра
4. обнуление изображения до (M+U-1) x (N+V-1)
5. возьмите 2-D FFT изображения
6. умножить FFT ядра на FFT изображения
7. принять обратное 2-D БПФ результата
8. обрезать мусор по краям

Если вы выполняете один и тот же фильтр несколько раз на разных изображениях, вам не нужно выполнять 1-3 каждый раз.

Примечание: размер ядра должен быть достаточно большим, чтобы это было быстрее, чем прямое вычисление свертки. Кроме того, реализовали ли вы свою прямую свертку, воспользовавшись тем, что двумерный гауссов фильтр является отделимым ( см. Несколько абзацев в разделе "Механика")? То есть вы можете выполнить 2-D свертку как 1-D свертки в строках, а затем в столбцах. Я обнаружил, что это быстрее, чем большинство подходов, основанных на FFT, если ядра не очень большие.

Ответ на редактирование

1. Если вход является реальным, вывод все еще будет сложным, за исключением редких случаев. БПФ вашего гауссова ядра также будет сложным, поэтому умножение должно быть сложным умножением. Когда вы выполняете обратное БПФ, вывод должен быть реальным, поскольку ваше входное изображение и ядро ​​реальны. Вывод будет возвращен в виде сложного массива, но мнимые компоненты должны быть нулевыми или очень маленькими (ошибка с плавающей запятой) и могут быть отброшены.

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

3. Для визуализации следует использовать величину комплексного вывода. Логарифмическая шкала просто помогает визуализировать меньшие компоненты вывода, когда более крупные компоненты заглушают их в линейном масштабе. Шкала децибел часто используется и задается 20*log10(abs(x)) или же 10*log10(x*x') которые эквивалентны. (x это сложный выход БПФ и x' комплексное сопряжение x).

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

Answer 2

Помните, что свертка в пространстве эквивалентна умножению в частотной области. Это означает, что после того, как вы выполните FFT как изображения, так и маски (ядра), вам нужно будет только выполнить умножение на точку, а затем выполнить IFFT результата. Сказав это, вот несколько слов предостережения.

Вы, наверное, знаете, что при цифровой обработке сигналов мы часто используем круговую свертку, а не линейную свертку. Это происходит из-за любопытной периодичности. Проще говоря, это означает, что DFT (и FFT, который является его вычислительно эффективным вариантом) предполагает, что ваш сигнал является периодическим, а когда вы фильтруете свой сигнал таким образом - предположим, что ваше изображение имеет размер N x M пикселей - что требуется пиксель в (1,m) соседу или пиксель в (N, m) для некоторого m< M. Вы сигнализируете виртуально вокруг себя. Это означает, что ваша гауссова маска будет усреднять пиксели в дальнем правом углу, а пиксели - в дальнем левом, и то же самое относится к верху и низу. Это может быть или не быть желательным, но в общем случае все равно приходится иметь дело с краями артефактов. Однако гораздо проще забыть об этой проблеме при работе с умножением БПФ, потому что проблема перестает быть очевидной. Есть много способов решить эту проблему. Лучший способ - просто добавить изображение в нули и удалить лишние пиксели позже.

При использовании фильтра Гаусса в частотной области очень удобно то, что вам никогда не придется брать его БПФ. Хорошо известен тот факт, что преобразование Фурье гауссиана является гауссовым (некоторые технические подробности здесь). Все, что вам нужно было бы сделать, это дополнить изображение нолями (сверху и снизу), сгенерировать гауссиан в частотной области, умножить их вместе и взять IFFT. Тогда все готово.

Надеюсь это поможет.