Eight-point algorithm
आठ-बिंदु एल्गोरिथ्म एक एल्गोरिथ्म है जिसका उपयोग कंप्यूटर दृष्टि में आवश्यक मैट्रिक्स या संबंधित छवि बिंदुओं के एक सेट से एक स्टीरियो कैमरा जोड़ी से संबंधित मौलिक मैट्रिक्स का अनुमान लगाने के लिए किया जाता है। इसे क्रिस्टोफर लोंगुएट-हिगिंस द्वारा 1981 में आवश्यक मैट्रिक्स के मामले में पेश किया गया था। सिद्धांत रूप में, इस एल्गोरिथ्म का उपयोग मौलिक मैट्रिक्स के लिए भी किया जा सकता है, लेकिन व्यवहार में सामान्यीकृत आठ-बिंदु एल्गोरिथ्म, जिसे 1997 में रिचर्ड हार्टले द्वारा वर्णित किया गया था, इस मामले के लिए बेहतर है। एल्गोरिथम का नाम इस तथ्य से निकला है कि यह आठ (या अधिक) संबंधित छवि बिंदुओं के एक सेट से आवश्यक मैट्रिक्स या मौलिक मैट्रिक्स का अनुमान लगाता है। हालांकि, एल्गोरिथ्म की विविधताओं का उपयोग आठ से कम बिंदुओं के लिए किया जा सकता है। कोपलानरिटी बाधा एक बीजगणितीय समीकरण के साथ दो कैमरों की एपिपोलर ज्यामिति और अंतरिक्ष में एक बिंदु को व्यक्त कर सकते हैं। ध्यान दें कि, कोई फर्क नहीं पड़ता कि बिंदु अंतरिक्ष में कहाँ है, वैक्टर, और एक ही तल से संबंधित हैं। बाईं आंख के संदर्भ फ्रेम में बिंदु के निर्देशांक को कॉल करें और दाहिनी आंख के संदर्भ फ्रेम में के निर्देशांक को कॉल करें और दो संदर्भ फ्रेम के बीच घूर्णन और अनुवाद को कॉल करें। यह दो संदर्भ फ्रेमों के निर्देशांकों के बीच का संबंध है। निम्नलिखित समीकरण हमेशा लागू होता है क्योंकि उत्पन्न वेक्टर दोनों के लिए ऑर्थोगोनल है औरः क्योंकि, हम प्राप्त करते हैं। के साथ प्रतिस्थापित करते हुए, हम अवलोकन प्राप्त करते हैं जिसे एक मैट्रिक्स के रूप में सोचा जा सकता है; लोंगुएट-हिगिंस ने इसे दर्शाने के लिए प्रतीक का उपयोग किया। उत्पाद को अक्सर आवश्यक मैट्रिक्स कहा जाता है और इसके साथ दर्शाया जाता है। वैक्टर वैक्टरों के समानांतर होते हैं और इसलिए यदि हम इन वैक्टरों को प्रतिस्थापित करते हैं तो सह-ग्रहता बाधा बनी रहती है। यदि हम बाएँ और दाएँ छवि विमानों के प्रक्षेपणों के निर्देशांक कहते हैं, तो सह-ग्रहता बाधा को मूल एल्गोरिथ्म के रूप में लिखा जा सकता है मूल आठ-बिंदु एल्गोरिथ्म यहाँ आवश्यक मैट्रिक्स का अनुमान लगाने के मामले में वर्णित है। इसमें तीन चरण होते हैं। सबसे पहले, यह एक सजातीय रैखिक समीकरण तैयार करता है, जहां समाधान सीधे संबंधित होता है, और फिर समीकरण को हल करता है, इस बात को ध्यान में रखते हुए कि इसका कोई सटीक समाधान नहीं हो सकता है। अंत में, परिणामी मैट्रिक्स की आंतरिक बाधाओं को प्रबंधित किया जाता है। पहले चरण का वर्णन लोंगुएट-हिगिंस के शोध पत्र में किया गया है, दूसरा और तीसरा चरण आकलन सिद्धांत में मानक दृष्टिकोण हैं। आवश्यक मैट्रिक्स द्वारा परिभाषित बाधा सामान्यीकृत छवि निर्देशांक में दर्शाए गए संबंधित छवि बिंदुओं के लिए है। एल्गोरिथ्म जिस समस्या को हल करता है वह मेल खाने वाले छवि बिंदुओं के एक सेट के लिए निर्धारित करना है। व्यवहार में, छवि बिंदुओं के छवि निर्देशांक शोर से प्रभावित होते हैं और समाधान भी अति-निर्धारित किया जा सकता है जिसका अर्थ है कि यह खोजना संभव नहीं हो सकता है कि सभी बिंदुओं के लिए उपरोक्त बाधा को कौन संतुष्ट करता है। इस मुद्दे को एल्गोरिथ्म के दूसरे चरण में संबोधित किया गया है। चरण 1: और और बाधा के साथ एक सजातीय रैखिक समीकरण तैयार करना, 9-आयामी वेक्टर के रूप में आवश्यक मैट्रिक्स का प्रतिनिधित्व करता है और यह वेक्टर वेक्टर के लिए ऑर्थोगोनल होना चाहिए जिसे मैट्रिक्स के वेक्टर प्रतिनिधित्व के रूप में देखा जा सकता है। संबंधित छवि बिंदुओं की प्रत्येक जोड़ी एक सदिश उत्पन्न करती है। 3डी बिंदुओं के एक समूह को देखते हुए यह वैक्टरों के एक समूह से मेल खाता है और उन सभी को वेक्टर के लिए संतुष्ट होना चाहिए। पर्याप्त रूप से कई (कम से कम आठ) रैखिक रूप से स्वतंत्र वैक्टरों को देखते हुए सीधे तरीके से निर्धारित करना संभव है। सभी वैक्टरों को एक मैट्रिक्स के कॉलम के रूप में इकट्ठा करें और फिर यह मामला होना चाहिए कि इसका मतलब है कि यह एक सजातीय रैखिक समीकरण का समाधान है। चरण 2: समीकरण को हल करना इस समीकरण को हल करने के लिए एक मानक दृष्टिकोण का तात्पर्य है कि यह एक एकवचन मूल्य के अनुरूप एक सही एकवचन सदिश है जो शून्य के बराबर है। बशर्ते कि इसके निर्माण के लिए कम से कम आठ रैखिक रूप से स्वतंत्र सदिशों का उपयोग किया जाता है, यह इस प्रकार है कि यह एकवचन सदिश अद्वितीय है (अदिश गुणन को नजरअंदाज करते हुए) और इसके परिणामस्वरूप, और फिर निर्धारित किया जा सकता है। यदि निर्माण के लिए आठ से अधिक संबंधित बिंदुओं का उपयोग किया जाता है, तो यह संभव है कि इसका शून्य के बराबर कोई एकल मूल्य न हो। यह मामला व्यवहार में तब होता है जब छवि निर्देशांक विभिन्न प्रकार के शोर से प्रभावित होते हैं। इस स्थिति से निपटने के लिए एक सामान्य दृष्टिकोण यह है कि इसे कुल न्यूनतम वर्ग समस्या के रूप में वर्णित किया जाए; पता करें कि कौन सी समस्या कब कम होती है। इसका समाधान सबसे छोटे एकवचन मूल्य के अनुरूप बाएं एकवचन सदिश के रूप में चुनना है। इसे एक मैट्रिक्स में फिर से व्यवस्थित करने से इस चरण का परिणाम मिलता है, जिसे यहाँ के रूप में संदर्भित किया गया है। चरण 3: आंतरिक बाधा को लागू करना शोर-शराबे वाली छवि निर्देशांकों से निपटने का एक और परिणाम यह है कि परिणामी मैट्रिक्स आवश्यक मैट्रिक्स की आंतरिक बाधा को पूरा नहीं कर सकता है, यानी इसके दो एकवचन मान समान और गैर-शून्य हैं और दूसरा शून्य है। अनुप्रयोग के आधार पर, आंतरिक बाधा से छोटे या बड़े विचलन एक समस्या हो सकती है या नहीं भी हो सकती है। यदि यह महत्वपूर्ण है कि अनुमानित मैट्रिक्स आंतरिक बाधाओं को संतुष्ट करता है, तो इसे रैंक 2 के मैट्रिक्स को ढूंढकर पूरा किया जा सकता है जो चरण 2 से परिणामी मैट्रिक्स को कम करता है और फ्रोबेनियस मैट्रिक्स मानक का उपयोग किया जाता है। समस्या का समाधान पहले एकवचन मान अपघटन की गणना करके दिया जाता हैः जहाँ ऑर्थोगोनल मैट्रिक्स हैं और एक विकर्ण मैट्रिक्स है जिसमें के एकवचन मान होते हैं। आदर्श मामले में, के विकर्ण तत्वों में से एक शून्य होना चाहिए, या अन्य दो की तुलना में कम से कम छोटा होना चाहिए जो बराबर होना चाहिए। किसी भी मामले में, निर्धारित करें कि क्रमशः सबसे बड़े और दूसरे सबसे बड़े एकवचन मान कहाँ हैं। अंत में, मैट्रिक्स एल्गोरिथ्म द्वारा प्रदान किए गए आवश्यक मैट्रिक्स का परिणामी अनुमान है। सामान्यीकृत एल्गोरिथ्म मूल आठ-बिंदु एल्गोरिथ्म का उपयोग सिद्धांत रूप में मौलिक मैट्रिक्स का अनुमान लगाने के लिए भी किया जा सकता है। के लिए परिभाषित बाधा यह है कि संबंधित छवि निर्देशांक के सजातीय प्रतिनिधित्व कहाँ हैं (आवश्यक सामान्यीकृत नहीं)। इसका मतलब है कि आवश्यक मैट्रिक्स की तरह ही एक मैट्रिक्स बनाना और उस समीकरण को हल करना संभव है जिसके लिए इसका एक नया रूप दिया गया है। ऊपर उल्लिखित प्रक्रिया का पालन करके, आठ मिलान अंकों के एक सेट से निर्धारित करना संभव है। व्यवहार में, हालांकि, परिणामी मौलिक मैट्रिक्स एपिपोलर बाधाओं को निर्धारित करने के लिए उपयोगी नहीं हो सकता है। कठिनाई समस्या यह है कि इसके परिणामस्वरूप अक्सर खराब स्थिति होती है। सिद्धांत रूप में, एक एकल मान शून्य के बराबर होना चाहिए और बाकी गैर-शून्य हैं। व्यवहार में, हालांकि, कुछ गैर-शून्य एकवचन मान बड़े के सापेक्ष छोटे हो सकते हैं। यदि निर्माण के लिए आठ से अधिक संबंधित बिंदुओं का उपयोग किया जाता है, जहां निर्देशांक केवल लगभग सही होते हैं, तो एक अच्छी तरह से परिभाषित एकवचन मान नहीं हो सकता है जिसे लगभग शून्य के रूप में पहचाना जा सकता है। नतीजतन, समीकरणों की सजातीय रैखिक प्रणाली का समाधान उपयोगी होने के लिए पर्याप्त रूप से सटीक नहीं हो सकता है। कारण हार्टले ने अपने 1997 के लेख में इस आकलन समस्या को संबोधित किया। समस्या के उनके विश्लेषण से पता चलता है कि समस्या उनके स्थान में सजातीय छवि निर्देशांक के खराब वितरण के कारण होती है। 2डी छवि निर्देशांक का एक विशिष्ट सजातीय प्रतिनिधित्व वह है जहाँ दोनों एक आधुनिक डिजिटल कैमरे के लिए 0 से 1000-2000 की सीमा में स्थित हैं। इसका मतलब है कि पहले दो निर्देशांक तीसरे निर्देशांक की तुलना में बहुत बड़ी सीमा में भिन्न होते हैं। इसके अलावा, यदि छवि के निर्माण के लिए उपयोग किए जाने वाले छवि बिंदु छवि के अपेक्षाकृत छोटे क्षेत्र में स्थित हैं, उदाहरण के लिए, फिर से वेक्टर सभी बिंदुओं के लिए कमोबेश एक ही दिशा में इंगित करता है। नतीजतन, एक बड़ा एकल मूल्य होगा और शेष छोटे होंगे। समाधान इस समस्या के समाधान के रूप में, हार्टले ने प्रस्ताव दिया कि दोनों छवियों में से प्रत्येक की समन्वय प्रणाली को स्वतंत्र रूप से, निम्नलिखित सिद्धांत के अनुसार एक नई समन्वय प्रणाली में परिवर्तित किया जाना चाहिए। नई निर्देशांक प्रणाली की उत्पत्ति छवि बिंदुओं के केंद्रक (गुरुत्वाकर्षण के केंद्र) पर केंद्रित (इसकी उत्पत्ति) होनी चाहिए। यह मूल मूल का नए में अनुवाद करके पूरा किया जाता है। अनुवाद के बाद निर्देशांकों को समान रूप से मापा जाता है ताकि मूल से बिंदुओं तक की दूरी का औसत बराबर हो। इस सिद्धांत के परिणामस्वरूप, आम तौर पर, दोनों छवियों में से प्रत्येक के लिए एक अलग समन्वय परिवर्तन होता है। नतीजतन, नए सजातीय छवि निर्देशांक दिए जाते हैं जहां पुराने से नए सामान्यीकृत छवि निर्देशांक में परिवर्तन (अनुवाद और स्केलिंग) होते हैं। यह सामान्यीकरण केवल छवि बिंदुओं पर निर्भर करता है जो एक छवि में उपयोग किए जाते हैं और सामान्य रूप से, एक सामान्यीकृत कैमरे द्वारा उत्पादित सामान्यीकृत छवि निर्देशांक से अलग होते हैं। मौलिक मैट्रिक्स पर आधारित एपिपोलर बाधा को अब कहाँ के रूप में फिर से लिखा जा सकता है। इसका मतलब है कि ऊपर वर्णित बुनियादी आठ-बिंदु एल्गोरिदम का उपयोग करके परिवर्तित मौलिक मैट्रिक्स का अनुमान लगाने के लिए सामान्यीकृत सजातीय छवि निर्देशांक का उपयोग करना संभव है। सामान्यीकरण परिवर्तनों का उद्देश्य यह है कि सामान्यीकृत छवि निर्देशांक से निर्मित मैट्रिक्स की स्थिति संख्या सामान्य रूप से बेहतर होती है। इसका मतलब है कि समाधान समरूप समीकरण के समाधान के रूप में सापेक्ष की तुलना में अधिक अच्छी तरह से परिभाषित है। एक बार जब निर्धारित किया जाता है और बाद वाले में पुनः आकार दिया जाता है, तो सामान्य रूप से, मौलिक मैट्रिक्स का यह अनुमान गैर-सामान्यीकृत निर्देशांक से अनुमान लगाकर प्राप्त किए जाने की तुलना में बेहतर होता है। आठ से कम अंकों का उपयोग करते हुए प्रत्येक बिंदु जोड़ी तत्व पर एक अवरोधक समीकरण के साथ योगदान करती है। चूँकि इसमें पाँच डिग्री ऑफ़ फ्रीडम है, इसलिए यह निर्धारित करने के लिए केवल पाँच बिंदु जोड़े के साथ पर्याप्त होना चाहिए। डेविड निस्टर ने पाँच युग्मित बिंदुओं के सेट से आवश्यक मैट्रिक्स का अनुमान लगाने के लिए एक कुशल समाधान का प्रस्ताव रखा, जिसे पाँच-बिंदु एल्गोरिथ्म के रूप में जाना जाता है। हार्टले एट। अल। बाद में उन्होंने सिस्टर के एल्गोरिदम के आधार पर एक संशोधित और अधिक स्थिर पाँच-बिंदु एल्गोरिदम का प्रस्ताव रखा। एसेंशियल मैट्रिक्स फंडामेंटल मैट्रिक्स ट्राइफोकल टेंसर संदर्भ भी देखें।