मैं विभिन्न आयामों की दो छवियों के स्पेक्ट्रा को कैसे गुणा कर सकता हूं?

Question

यह एक "प्रोग्रामिंग" प्रश्न नहीं है। लेकिन मुझे यकीन है कि यह ऐसा कुछ है जो इस समुदाय में व्यापक रूप से ज्ञात और समझा जाता है।

मेरे पास एक छवि, एक्स, और एक बहुत छोटी छवि है, वाई, और मुझे अपने एफएफटी गुणा करके दोनों को मजबूत करने की आवश्यकता है। लेकिन चूंकि वे एक ही आकार के नहीं हैं, इसलिए मुझे नहीं पता कि आवृत्ति डोमेन गुणा कैसे करें।

मैं एक्स (दो आयामी) एफएफटी एक्स (जो आयामों का पूर्णांक मैट्रिक्स 4096 x 4096) लेता है, जो मुझे आवृत्ति डोमेन प्रतिनिधित्व देता है, एक्स (जो जटिल संख्याओं का एक मैट्रिक्स है और मुझे लगता है कि यह आयाम है 2048 x 2048 है)।

इसी तरह, मैं (दो आयामी एफएफटी वाई (जो आयाम 64 x 64 का एक पूर्णांक मैट्रिक्स है) लेता है, जो मुझे आवृत्ति डोमेन प्रतिनिधित्व देता है, वाई (जो जटिल संख्याओं का मैट्रिक्स भी है और मुझे लगता है यह आयाम 32 x 32 है)

मैं संख्यात्मक व्यंजनों में चार कार्य का उपयोग कर रहा हूं, इसलिए मेरे इनपुट मैट्रिस, एक्स और वाई को एक-आयामी सरणी में ध्वस्त किया जाना चाहिए, जो उनके अलग फूरियर ट्रांसफॉर्म, एक्स द्वारा प्रतिस्थापित किया जाता है और वाई। बिंदु यह है कि भले ही यह छवियों के साथ एक द्वि-आयामी समस्या है, मैं एक-आयामी सरणी के साथ काम कर रहा हूं।

यदि मैं सटीक समान आयामों, एक्स और वाई की दो छवियों को संकलित करने की कोशिश कर रहा था। यह सभी बहुत सरल होंगे:

X = FFT(x) 

Y = FFT(y) 

Z = X * Y (term by term multiplication) 

Convolution of x and y = IFFT(Z) 

लेकिन यदि एक्स और वाई अलग-अलग लंबाई हैं, तो मैं गुणा कैसे करूं?

एक संभावना है कि एक्स को समान आयामों के लिए y को पैड करना है। लेकिन यह बहुत अक्षम है। एक अन्य संभावना है कि वाई को एक्स के समान आयाम प्राप्त करने के लिए पैड आउट करना है। लेकिन मुझे नहीं पता कि आवृत्ति स्थान में इसका क्या अर्थ है।

यहां इस प्रश्न पूछने का एक और तरीका है: यदि मैं एफएफटी का उपयोग करके बहुत अलग आयामों की दो छवियों को संकुचित करना चाहता हूं तो मैं उनके स्पेक्ट्रा (आवृत्ति डोमेन प्रतिनिधित्व) का गुणा कर सकता हूं, मैं उस गुणा को कैसे कर सकता हूं?

धन्यवाद,

~ माइकल।

Answer 1

इनपुट छवि आकार (आपके मैट्रिक्स एक्स) से मेल खाने के लिए शून्य के साथ छोटी सरणी (आपके मामले में रूपांतरण कर्नेल, वाई) में पैडिंग मानक दृष्टिकोण है। बहुत ही अक्षम हो सकता है यदि आप स्थानिक डोमेन में रूपांतरण कर रहे थे, लेकिन यदि आप एफएफटी गुणा कर रहे हैं, तो यह आवश्यक है, और गद्देदार सरणी के एफएफटी की गणना करने की लागत बहुत खराब नहीं है।

Answer 2

आप सोचने में सही हैं कि दो आवृत्ति स्पैसिंग समान होने की आवश्यकता है। एक -1 डी उदाहरण लें (मैं 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)))); 

दो तकनीकों के बीच का अंतर ~ 2 ई -14, इसलिए roundoff त्रुटि है। ध्यान दें कि आपको रैखिक और परिपत्र संकल्प के बीच अंतर के कारण पहले 64 नमूने छोड़ना होगा।

zCircular की गणना में, एफएफटी (वाई, एन) नोट करें, जो एफएफटी की गणना करने से पहले शून्य तक शून्य के साथ वाई सिग्नल को पैडिंग के लिए मैटलैब सिंटैक्स है।यह स्मृति के उपयोग में अक्षम माना जा सकता है, लेकिन गति की तुलना:

रैखिक घुमाव: 4096 गुणा/64 प्रत्येक = 262,144 गुणा की कहते हैं/कहते हैं

परिपत्र घुमाव: 4096 + 1 2 की जटिल गुणा के 2 FFTs * 4096 तत्वों +1 व्युत्क्रम FFT
= 3 * 4096 * log2 (4096) + 4096 * 6 = 172032

असल में, FFT के NlogN गति, तब भी जब आप की जरूरत (जटिल गुणा के लिए 6 संचालन कल्पना करते हुए) उनमें से तीन, एन * एम कन्वोल्यूशन ऑपरेशन को धड़कता है जब तक कि एम बहुत छोटा न हो। 2 डी मामले

यह भी कहा कि 2 डी डेटा के लिए गति लाभ बढ़ाया है लायक है के लिए

संपादित जोड़ें गति अनुमान। एक 2 डी एफएफटी एन * एन * लॉग 2 (एन * एन) संचालन लेता है, इसलिए एन = 40 9 6 के लिए 3 एफएफटी + जटिल एन^2 सरणी गुणा 1.3e10 संचालन है। लेकिन प्रत्यक्ष संकल्प एन^2 * एम^2 = 6.9e10 संचालन है, कुछ 50 गुना धीमा है।