Разделимая свертка с использованием одномерного БПФ и двухмерного БПФ

Я пытаюсь использовать MATLAB для свертки изображения с помощью фильтра Гаусса, используя два метода: разделяемую свертку с использованием 1D FFT и неотделяемую свертку с использованием 2D FFT. Я ожидаю, что отделимая свертка будет быстрее. Однако это не для маленьких изображений, а для больших, где 2D быстрее. Я не уверен, проблема ли это в моей реализации или потому, что у меня нет правильной концепции.

Вот мой код:

img1 = randi([1,256],128,128);    

% Create a Gaassian filter
rf1 = fspecial('gaussian', [1 128], 1.0);
cf1 = transpose(rf1);
gf1 = cf1 * rf1;    

rc1 = round(conv2(img1, gf1, 'same'));
rc1 = fft2dconv(img1, gf1);
rc2 = fft1dconv(img1, rf1, cf1);


function o = fft1dconv(img, rowf, colf)

% Zero-Pad
imgsize = size(img);
rsize = size(rowf);
csize = size(colf);

img = padarray(img, [imgsize(1)/2, imgsize(2)/2]);
rowf = padarray(rowf, [2*imgsize(1)-rsize(1), 2*imgsize(2)-rsize(2)], 'post');
colf = padarray(colf, [2*imgsize(1)-csize(1), 2*imgsize(2)-csize(2)], 'post');


% Seperable convolution using 1D FFT
tic;
result = fft(transpose(fft(img))) .* fft(transpose(fft(colf)));
result = result .* fft(transpose(fft(rowf)));
o = transpose(round(real(ifft2(result))));
toc;


% Remove Pad
o = o(imgsize(1)+1:2*imgsize(1),imgsize(2)+1:2*imgsize(2));

end


function o = fft2dconv(img, filter)

%zero-pad
imgsize = size(img);
fsize = size(filter);

img = padarray(img, [imgsize(1)/2, imgsize(2)/2]);
filter = padarray(filter, [2*imgsize(1)-fsize(1), 2*imgsize(2)-fsize(2)], 'post');

% Non-Seperable convolution using 2D FFT
tic;
o = round(real(ifft2(fft2(img) .* fft2(filter))));
toc;

% Remove Pad
o = o(imgsize(1)+1:2*imgsize(1),imgsize(2)+1:2*imgsize(2));

end

И временные результаты, которые:

Elapsed time is 0.003315 seconds.
Elapsed time is 0.004369 seconds.

Для изображения 4 x 4 метод разделения выполняется намного быстрее, но для изображений большего размера. Это не тот случай, и я не уверен, почему. Любая помощь могла бы быть полезна.


person user115188    schedule 06.04.2014    source источник
comment
Просто догадки. (Я не знаю достаточно, чтобы проверить какое-либо из этих утверждений.) MATLAB fft2 также выполняет проверку разделимости (и фактически, приближение низкого ранга SVD). Внутри fft2 используется либо ATLAS, либо FFTW, оба из которых считаются самыми быстрыми реализациями FFT, доступными на рынке. (В некоторых более старых версиях использовался IPP.) Наконец, реализации C, используемой внутри MATLAB (при взаимодействии с ATLAS и FFTW), не нужно беспокоиться о выполнении транспонирования - она ​​просто сообщает базовой библиотеке, чтобы она считывала массив транспонированным способом.   -  person rwong    schedule 07.04.2014


Ответы (1)


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

Войдите в MATLAB и введите profile viewer. Как только вы это сделаете, запустите свою команду в этом окне и дайте ей закончиться. Как только он завершится, он определит интенсивные части вашего кода, и вы сможете понять, как его оптимизировать оттуда. Вы правы, говоря, что отделяемые фильтры быстрее.

person rayryeng    schedule 07.04.2014
comment
@ user115188 Ого! Призрак из прошлого! Вы в конце концов выяснили, почему не вовремя? - person rayryeng; 11.06.2014