लुकास-कनाडा विधि द्वारा ऑप्टिकल फ्लक्स गणना। सिद्धांत

कंप्यूटर विज़न और इमेज प्रोसेसिंग सिस्टम में, कार्य अक्सर ऑप्टिकल सेंसर, यानी वीडियो कैमरा का उपयोग करके त्रि-आयामी अंतरिक्ष में वस्तुओं के आंदोलनों को निर्धारित करने के लिए होता है। इनपुट पर फ़्रेम का अनुक्रम होने के बाद, उन पर अंकित तीन आयामी स्थान और समय के साथ होने वाले परिवर्तनों को फिर से बनाना आवश्यक है। यह जटिल लगता है, लेकिन व्यवहार में यह अक्सर फ्रेम के विमान में वस्तुओं के दो-आयामी अनुमानों के ऑफसेट को खोजने के लिए पर्याप्त होता है।

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

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

इस दृष्टिकोण को अक्सर अंतर कहा जाता है, क्योंकि यह छवि के क्षैतिज और ऊर्ध्वाधर दिशाओं में आंशिक डेरिवेटिव की गणना पर आधारित है। जैसा कि हम बाद में देखेंगे, विस्थापन को निर्धारित करने के लिए केवल डेरिवेटिव ही पर्याप्त नहीं हैं। इसीलिए, एक सरल विचार के आधार पर, एक महान कई विधियाँ सामने आई हैं, जिनमें से प्रत्येक लक्ष्य को प्राप्त करने के लिए किसी न किसी प्रकार के गणितीय नृत्य का उपयोग करती है। हम ब्रूस लुकास और टेको कनाडा द्वारा 81 में प्रस्तावित लुकास-कनाडे पद्धति पर ध्यान केंद्रित करते हैं।

लुकास-कनाडा विधि

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

गणितीय भाषा में, इस धारणा को इस प्रकार लिखा जा सकता है: । जहां मैं फ्रेम और समय पर स्थिति से पिक्सेल की चमक का एक कार्य है। दूसरे शब्दों में, x और y फ्रेम प्लेन में पिक्सेल के निर्देशांक हैं, और ऑफसेट है, और टी अनुक्रम में फ्रेम नंबर है। मान लेते हैं कि दो आसन्न फ़्रेमों के बीच एक एकल समय बीतता है।

एक आयामी मामला

पहले, एक-आयामी मामले पर विचार करें। दो एक आयामी फ्रेम की कल्पना करें 1 पिक्सेल उच्च और 20 पिक्सेल चौड़ा (दाईं ओर आंकड़ा)। दूसरे फ्रेम में, छवि को दाईं ओर थोड़ा स्थानांतरित किया गया है। यह वह पूर्वाग्रह है जिसे हम खोजना चाहते हैं। ऐसा करने के लिए, फ़ंक्शंस के रूप में एक ही फ्रेम की कल्पना करें (बाईं ओर आंकड़ा)। इनपुट पर, आउटपुट पर पिक्सेल की स्थिति, इसकी तीव्रता। इस तरह के प्रतिनिधित्व में वांछित विस्थापन (डी) को और भी स्पष्ट रूप से देखा जा सकता है। हमारी धारणा के अनुसार, यह सिर्फ पक्षपातपूर्ण है , वह है, हम कह सकते हैं कि ।

कृपया ध्यान दें और यदि वांछित है, तो आप सामान्य रूप में लिख सकते हैं: ; जहाँ y और t निश्चित और शून्य के बराबर हैं।

प्रत्येक समन्वय के लिए, हम मूल्यों को जानते हैं और इस बिंदु पर, इसके अतिरिक्त, हम उनके डेरिवेटिव की गणना कर सकते हैं। हम ज्ञात मूल्यों को ऑफसेट d के साथ जोड़ते हैं। ऐसा करने के लिए, हम एक टेलर श्रृंखला में विस्तार के लिए लिखते हैं :



हम दूसरी महत्वपूर्ण धारणा बनाते हैं: मान लीजिए कि पहली व्युत्पन्न काफी अच्छी तरह से अनुमान लगाता है । इस धारणा को बनाते हुए, हम पहले व्युत्पन्न के बाद सब कुछ त्याग देते हैं:



यह कितना सही है? सामान्य तौर पर, वास्तव में नहीं, यहां हम सटीकता में खो जाते हैं, जब तक कि हमारे कार्य / छवि सख्ती से रैखिक नहीं होती है, जैसा कि हमारे कृत्रिम उदाहरण में है। लेकिन यह विधि को बहुत सरल करता है, और आवश्यक सटीकता प्राप्त करने के लिए, एक अनुक्रमिक सन्निकटन बनाया जा सकता है, जिसे हम बाद में विचार करेंगे।

हम लगभग वहीं हैं। ऑफसेट d हमारा वांछित मूल्य है, इसलिए आपको कुछ करने की जरूरत है । जैसा कि हम पहले सहमत थे, , तो बस फिर से लिखना:



वह है:

दो आयामी मामला

अब हम एक आयामी मामले से दो आयामी एक से गुजरते हैं। हम के लिए एक टेलर श्रृंखला में विस्तार से लिखते हैं और तुरंत सभी उच्च डेरिवेटिव को त्याग दें। पहले व्युत्पन्न के बजाय, एक ढाल दिखाई देती है:



जहाँ विस्थापन वेक्टर है।
धारणा के अनुसार । ध्यान दें कि यह अभिव्यक्ति के बराबर है । यह वही है जो हमें चाहिए। हम फिर से लिखते हैं:





चूंकि एक इकाई समय अंतराल दो फ़्रेमों के बीच गुजरता है, हम कह सकते हैं कि समय व्युत्पन्न के अलावा कुछ भी नहीं है।
हम फिर से लिखते हैं:



हम इसे फिर से लिखते हैं, ग्रेडिएंट का खुलासा करते हुए:



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

हम तीसरी धारणा बनाते हैं: मान लीजिए कि पड़ोसी पिक्सेल समान दूरी से स्थानांतरित हो गए हैं । छवि का एक टुकड़ा लें, 5 बाय 5 पिक्सेल कहें और प्रत्येक 25 पिक्सेल के लिए सहमत हों और बराबर हैं। तब एक समीकरण के बजाय, हमें एक ही बार में २५ समीकरण मिलते हैं! जाहिर है, सामान्य मामले में, सिस्टम के पास कोई समाधान नहीं है, इसलिए, हम इस तरह की तलाश करेंगे और उस त्रुटि को कम करें:



यहाँ g एक फ़ंक्शन है जो पिक्सेल के लिए वज़न निर्धारित करता है। सबसे आम विकल्प एक दो-आयामी गाऊसी है, जो केंद्रीय पिक्सेल को सबसे बड़ा वजन देता है और केंद्र से दूर जाने के दौरान कम और कम होता है।

न्यूनतम खोजने के लिए हम कम से कम वर्गों की विधि का उपयोग करते हैं, इसके आंशिक अंश को सम्मान के साथ पाते हैं और :





हम एक और अधिक कॉम्पैक्ट रूप में फिर से लिखते हैं और शून्य के बराबर होते हैं:





हम मैट्रिक्स रूप में इन दो समीकरणों को फिर से लिखते हैं:



जहाँ







यदि मैट्रिक्स M उल्टा है (रैंक 2 है), तो हम गणना कर सकते हैं और उस त्रुटि को कम से कम E:



बस इतना ही। हम दो आसन्न फ्रेम के बीच अनुमानित पिक्सेल ऑफसेट जानते हैं।

चूंकि पड़ोसी पिक्सेल प्रत्येक पिक्सेल के विस्थापन को खोजने में भी शामिल होते हैं, इस पद्धति को लागू करते समय, फ्रेम के क्षैतिज और ऊर्ध्वाधर व्युत्पन्न की गणना करना उचित होता है।

विधि का नुकसान

ऊपर वर्णित विधि तीन महत्वपूर्ण मान्यताओं पर आधारित है, जो एक तरफ हमें ऑप्टिकल प्रवाह को निर्धारित करने का मौलिक अवसर देती है, लेकिन दूसरी ओर एक त्रुटि का परिचय देती है। पूर्णतावादियों के लिए अच्छी खबर यह है कि हमें विधि को सरल बनाने के लिए केवल एक धारणा की आवश्यकता है, और हम इसके परिणामों से लड़ सकते हैं। हमने मान लिया कि पूर्वाग्रह के बारे में अनुमान लगाने के लिए पहला व्युत्पन्न हमारे लिए पर्याप्त होगा। सामान्य मामले में, निश्चित रूप से, ऐसा नहीं है (बाईं ओर आंकड़ा)। आवश्यक सटीकता प्राप्त करने के लिए, प्रत्येक जोड़ी फ्रेम के लिए ऑफसेट (चलो उन्हें कॉल करें और ) की गणना की जा सकती है। साहित्य में, इसे वारपिंग कहा जाता है। व्यवहार में, इसका अर्थ है कि पहले पुनरावृत्ति में ऑफसेट की गणना करके, हम फ्रेम के प्रत्येक पिक्सेल को स्थानांतरित करते हैं विपरीत दिशा में ताकि इस ऑफसेट को मुआवजा दिया जाए। मूल फ्रेम के बजाय अगले पुनरावृत्ति पर हम इसके विकृत संस्करण का उपयोग करेंगे । और इसलिए, अगले पुनरावृत्ति तक, सभी प्राप्त ऑफसेट निर्दिष्ट सीमा मूल्य से कम हैं। प्रत्येक विशिष्ट पिक्सेल के लिए अंतिम ऑफसेट हमें सभी पुनरावृत्तियों पर इसके विस्थापन के योग के रूप में मिलता है।

इसकी प्रकृति से, यह विधि स्थानीय है, अर्थात्, जब एक विशिष्ट पिक्सेल की ऑफसेट का निर्धारण किया जाता है, तो केवल इस पिक्सेल के आसपास के क्षेत्र को ध्यान में रखा जाता है - स्थानीय पड़ोस। नतीजतन, फ्रेम के समान रूप से रंगीन वर्गों (स्थानीय पड़ोस से बड़ा) के अंदर विस्थापन को निर्धारित करना असंभव है। सौभाग्य से, इस तरह के खंड अक्सर वास्तविक शॉट्स में नहीं मिलते हैं, लेकिन यह सुविधा फिर भी सच्चे पूर्वाग्रह से एक अतिरिक्त विचलन का परिचय देती है।

एक और समस्या यह है कि छवि में कुछ बनावट एक अध: पतन मैट्रिक्स M देती है, जिसके लिए उलटा मैट्रिक्स नहीं पाया जा सकता है। तदनुसार, ऐसे बनावट के लिए हम ऑफसेट का निर्धारण नहीं कर सकते हैं। यही है, एक आंदोलन लगता है, लेकिन यह स्पष्ट नहीं है कि कौन सा तरीका है। सामान्य तौर पर, न केवल माना विधि इस समस्या से ग्रस्त है। यहां तक ​​कि मानव आंख भी मानती है कि यह आंदोलन अद्वितीय नहीं है ( नाई ध्रुव )।

निष्कर्ष

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

हालाँकि ऑप्टिकल फ्लक्स को खोजने की समस्या का कई दशकों से अध्ययन किया जा रहा है, फिर भी तरीकों में सुधार किया जा रहा है। इस तथ्य को देखते हुए काम जारी है कि करीबी परीक्षा में, समस्या बहुत मुश्किल हो जाती है, और कई अन्य एल्गोरिदम की स्थिरता और दक्षता वीडियो और छवियों के प्रसंस्करण में ऑफसेट का निर्धारण करने की गुणवत्ता पर निर्भर करती है।

इस पाथोस नोट पर, मुझे राउंड आउट करना और स्रोतों और उपयोगी लिंक पर जाना है।

स्रोत और लिंक

1. ऑप्टिकल फ्लो अनुमान। डेविड जे फ्लीट, येयर वीस। - एक व्यापक लेख जिसमें न केवल लुकास-कनाडा पद्धति का विस्तृत विवरण है, बल्कि अन्य अंतर विधियां भी हैं।
2. मल्टीमीडिया इंजीनियरिंग के लिए छवि और वीडियो संपीड़न: बुनियादी बातों, एल्गोरिदम और मानक। यूं क्यू शी, हुइफांग सन - वीडियो और छवि संपीड़न पर ट्यूटोरियल, लेकिन इस मुद्दे के इतिहास का एक अच्छा अवलोकन भी शामिल है।
3. इमेज प्रोसेसिंग ऑन लाइन - बड़ी संख्या में प्रासंगिक इमेज प्रोसेसिंग एल्गोरिदम। सभी के लिए, एल्गोरिदम एक ऑनलाइन डेमो से लैस हैं।