Làm cách nào để nhân phổ phổ của hai hình ảnh có kích thước khác nhau?

Question

Đây không phải là câu hỏi "lập trình". Nhưng tôi chắc chắn đó là một thứ được nhiều người biết đến và hiểu rõ trong cộng đồng này.

Tôi có hình ảnh, x và hình ảnh nhỏ hơn nhiều, y và tôi cần phải xoay chuyển cả hai bằng cách nhân các FFT của chúng. Nhưng vì chúng không có cùng kích thước nên tôi không biết cách thực hiện phép nhân miền tần số.

Tôi lấy FFT (hai chiều) FFT của x (là ma trận số nguyên của kích thước 4096 x 4096), cung cấp cho tôi đại diện miền tần số, X (là ma trận số phức và tôi nghĩ rằng đó là thứ nguyên là 2048 x 2048).

Tương tự, tôi lấy (FFT hai chiều của y (là ma trận số nguyên của kích thước 64 x 64), cung cấp cho tôi đại diện miền tần số, Y (cũng là ma trận số phức Tôi đang sử dụng hàm bốn trong Bí quyết số, vì vậy ma trận đầu vào của tôi, x và y phải được thu gọn thành mảng một chiều, được thay thế bằng các biến đổi Fourier rời rạc của chúng, X và Y. Vấn đề là mặc dù đây là vấn đề hai chiều với các hình ảnh, tôi đang làm việc với các mảng một chiều

Nếu tôi cố gắng ghép hai hình ảnh có cùng kích thước, x và y. Nó tất cả sẽ rất đơn giản:

X = FFT(x) 

Y = FFT(y) 

Z = X * Y (term by term multiplication) 

Convolution of x and y = IFFT(Z) 

Nhưng nếu X và Y có độ dài khác nhau, làm cách nào để thực hiện phép nhân?

Một khả năng là đưa ra y để có cùng kích thước với x. Nhưng điều này có vẻ không hiệu quả khủng khiếp. Một khả năng khác là đưa ra Y để có cùng kích thước với X. Nhưng tôi không biết điều này có nghĩa là gì trong không gian tần số. Đây là một cách khác để đặt câu hỏi này: Nếu tôi muốn kết hợp hai hình ảnh với các kích thước rất khác nhau bằng cách sử dụng FFT để tôi có thể nhân phép phổ của chúng (đại diện miền tần số), làm cách nào để thực hiện phép nhân đó?

Xin cảm ơn,

~ Michael.

Answer 1

Đệm mảng nhỏ hơn (hạt nhân chập, y trong trường hợp của bạn) với số không phù hợp với kích thước hình ảnh đầu vào (ma trận x) của bạn là phương pháp chuẩn. sẽ không hiệu quả khủng khiếp nếu bạn đang thực hiện chuyển đổi trong miền không gian, nhưng nếu bạn nhân các FFT, cần thiết và chi phí tính toán FFT của mảng đệm không quá tệ.

Answer 2

Bạn đúng khi nghĩ rằng hai khoảng cách tần số cần phải giống nhau. Lấy ví dụ 1D (Tôi đang sử dụng cú pháp Matlab):

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)))); 

Sự khác biệt giữa hai kỹ thuật là ~ 2e-14, do đó lỗi vòng tròn. Lưu ý rằng bạn phải bỏ qua 64 mẫu đầu tiên do sự khác biệt giữa phép hồi quy tuyến tính và vòng tròn.

Trong phép tính zCircular, chú ý fft (y, N), là cú pháp Matlab để đệm ra tín hiệu y với số không lên đến N trước khi tính toán fft.Điều này có thể được coi là không hiệu quả trong việc sử dụng bộ nhớ, nhưng so sánh tốc độ:

chập tuyến tính: 4096 nhân/thêm 64 mỗi = 262.144 nhân/thêm

chập tròn: 2 FFTs của 4096 + 1 nhân phức tạp của 2 * 4096 yếu tố + 1 nghịch đảo FFT
= 3 * 4096 * log2 (4096) + 4096 * 6 = 172032 (giả sử 6 hoạt động cho nhân phức tạp)

về cơ bản, tốc độ NlogN của FFT, ngay cả khi bạn cần ba trong số đó, đánh bại hoạt động chập N * M trừ khi M rất ngắn.

EDIT Add ước tính tốc độ đối với trường hợp 2D

Nó có giá trị thêm rằng cho dữ liệu 2D lợi thế tốc độ phóng đại. Một FFT 2D có N * N * log2 (N * N) hoạt động, do đó, 3 FFT + phức tạp N^2 mảng nhân cho N = 4096 là 1.3e10 hoạt động. Nhưng sự chập chững trực tiếp là N^2 * M^2 = 6,9e10 hoạt động, chậm hơn 50 lần.