서로 다른 차원의 두 이미지의 스펙트럼을 어떻게 곱합니까?

Question

이것은 "프로그래밍"질문이 아닙니다. 그러나 나는 이것이이 공동체에서 널리 알려지고 이해되는 어떤 것이라 확신합니다.

필자는 이미지 x와 훨씬 더 작은 이미지 y를 가지고 있으며, 나는 FFT를 곱하여 두 가지를 컨버팅해야합니다. 그러나 그들은 같은 크기가 아니기 때문에 나는 주파수 영역 곱셈을하는 법을 모른다.

x (4096 x 4096 크기의 정수 행렬) 인 x의 (2 차원) FFT를 사용하면 주파수 도메인 표현 인 X (복소수 행렬 임)를 얻을 수 있다고 생각합니다. 2048 x 2048).

유사하게, (차원 64 x 64의 정수 행렬 인) y의 2 차원 FFT를 취하여 주파수 도메인 표현 Y를 얻습니다. (또한 복소수의 행렬이기도합니다. 그것의 차원은 32 x 32이다.)

나는 Numerical Recipes에서 fourn 함수를 사용하기 때문에 입력 행렬 x와 y는 이산 푸리에 변환 X로 대체되는 1 차원 배열로 축소되어야한다. 요점은 이것이 이미지에 2 차원 문제가 있음에도 불구하고 1 차원 배열로 작업하고 있다는 것입니다.

정확히 동일한 크기의 두 이미지 x와 y를 컨볼 루션하려했다면 말입니다. 그것 모두 매우 직관적입니다 :

X = FFT(x) 

Y = FFT(y) 

Z = X * Y (term by term multiplication) 

Convolution of x and y = IFFT(Z) 

그러나 X와 Y가 다른 길이 인 경우 어떻게 곱셈을 수행합니까?

하나의 가능성은 x와 동일한 치수를 갖기 위해 y를 패딩하는 것입니다. 그러나 이것은 끔찍하게 비효율적 인 것처럼 보인다. 또 다른 가능성은 X와 동일한 차원을 갖도록 Y를 패딩하는 것입니다. 그러나 주파수 공간에서 이것이 무엇을 의미하는지 모르겠습니다.

이 질문을하는 또 다른 방법은 다음과 같습니다. FFT를 사용하여 매우 다른 차원의 두 이미지를 컨버전하여 스펙트럼 (주파수 도메인 표현)을 곱할 수 있다면 어떻게 그 곱셈을 수행합니까?

감사합니다.

~ 마이클.

Answer 1

입력 이미지 크기 (행렬 x)와 일치하도록 더 작은 배열 (귀하의 경우에는 컨볼 루션 커널, y)을 0으로 채우는 것이 표준 방식입니다. 은이 공간 도메인에서 컨볼 루션을 수행하는 경우 엄청나게 비효율적 일 수 있지만 FFT를 곱하면 필요한 것이므로 패딩 된 배열의 FFT를 계산하는 데 드는 비용이 그리 나쁘지 않습니다.

Answer 2

두 주파수 간격이 동일해야한다고 생각하는 것이 맞습니다. (I는 매트랩 구문을 사용하고) 1 차원 예를 보자

N = 4096; 
M = 64; 

x = randn(N, 1); 
y = hann(M, 'symmetric'); 

zLinear = conv(x,y); 
zCircular = ifft(fft(x) .* fft(y,N)); 

disp(max(abs(zLinear(65:4096) - zCircular(65:4096)))); 

두 방법의 차이는 14 ~ 2E-때문에 반올림 오차이다. 선형 및 순환 컨볼 루션의 차이로 인해 처음 64 개 샘플을 건너 뛰어야합니다.

zCircular의 계산에서 fft를 계산하기 전에 y 신호를 N까지 0으로 채우기위한 Matlab 구문을 기록합니다.이것은 메모리 사용을 비효율적으로 간주하지만, 속도 비교 될 수있다 :

가

선형 컨벌루션 : 4,096 곱하기/64 각 = 262,144 승산 추가를 추가/

원형 콘볼 루션 : 2의 4096 + 1 복소 곱의 2 개의 FFT * 4096 개 원소 + 1 역 FFT
= *의 LOG2 (4096) + 4096 * 4096 3 * 6 = 172,032는 FFT의

기본적 NlogN 속도가 필요하더라도 (복소 곱셈 6 개 동작을 가정) 그 중 3 개는 M이 매우 짧은 경우를 제외하고는 N * M 컨볼 루션 연산보다 우수합니다. 2D의 경우

그것은 2D 데이터에 대한 속도의 장점은 확대되어 추가 가치에 대한

편집 추가 속도 추정. 2D FFT는 N * N * log2 (N * N) 연산을 취하므로 N = 4096에 대한 3 개의 FFT + 복소 N^2 배열 곱셈은 1.3e10 연산입니다. 그러나 직접 컨볼 루션은 N^2 * M^2 = 6.9e10 작업이며 약 50 배 느립니다.