संयुक्त संगतता शाखा और बाउंड (JCBB) एक डेटा सहयोग एल्गोरिथ्म है जिसका उपयोग एक साथ स्थानीयकरण और मानचित्रण (SLAM) और कंप्यूटर विज़न में देखी गई विशेषताओं को ज्ञात मानचित्र या मॉडल के साथ मिलाने के लिए किया जाता है। इसे 2001 में José Neira और Juan D. Tardós ने अपने पेपर "डेटा एसोसिएशन इन स्टोकेस्टिक मैपिंग यूज़िंग जॉइंट कम्पैटिबिलिटी" में प्रस्तुत किया था। यह एल्गोरिथ्म यह निर्धारित करने की समस्या को संबोधित करता है कि कौन से सेंसर माप किस लैंडमार्क या मानचित्र विशेषता के अनुरूप हैं, जो मोबाइल रोबोटिक्स में सटीक स्थिति अनुमान के लिए एक महत्वपूर्ण कदम है।
सरल निकटतम-पड़ोसी दृष्टिकोणों के विपरीत, जो व्यक्तिगत विशेषता मिलानों का स्वतंत्र रूप से मूल्यांकन करते हैं, JCBB सेट में सभी विशेषताओं के बीच सांख्यिकीय सहसंबंधों पर विचार करके मिलानों के एक सेट की संयुक्त संगतता का मूल्यांकन करता है। यह संयुक्त परीक्षण झूठे मिलानों के प्रति अधिक मजबूत है, विशेष रूप से दोहराव या अस्पष्ट विशेषताओं वाले वातावरण में। यह एल्गोरिथ्म संभावित मिलान सेटों के स्थान को शाखा और बाउंड रणनीति का उपयोग करके खोजता है, जो उन शाखाओं को व्यवस्थित रूप से काट देता है जो बेहतर समाधान की ओर नहीं ले जा सकती हैं, यह सुनिश्चित करते हुए कि पाया गया सेट सबसे बड़ा सेट है जो संयुक्त रूप से संगत है।
एल्गोरिथ्म अवलोकन
JCBB पूर्वानुमानित विशेषताओं (वर्तमान मानचित्र से) और देखी गई विशेषताओं (सेंसर डेटा से) के सेट पर काम करता है। प्रत्येक अवलोकन को अधिकतम एक पूर्वानुमानित विशेषता को सौंपा जा सकता है, और प्रत्येक पूर्वानुमानित विशेषता को अधिकतम एक अवलोकन से मिलान किया जा सकता है। लक्ष्य मिलानों का अधिकतम कार्डिनैलिटी सेट खोजना है जैसे कि संयुक्त नवाचार वेक्टर (देखे गए और पूर्वानुमानित मापों के बीच का अंतर) पूर्ण सहप्रसरण मैट्रिक्स को ध्यान में रखते हुए, ची-स्क्वायर थ्रेशोल्ड के भीतर हो।
शाखा और बाउंड खोज एक पेड़ का निर्माण करती है जहां प्रत्येक नोड अवलोकनों का विशेषताओं को आंशिक असाइनमेंट दर्शाता है। प्रत्येक चरण में, एल्गोरिथ्म अगले अनअसाइन किए गए अवलोकन पर विचार करके नोड का विस्तार करता है और प्रत्येक शेष विशेषता के साथ उसकी संगतता का परीक्षण करता है, दोनों व्यक्तिगत रूप से और पहले से असाइन किए गए मिलानों के साथ संयुक्त रूप से। यदि संयुक्त संगतता परीक्षण विफल हो जाता है, तो उस शाखा को काट दिया जाता है। खोज तब तक जारी रहती है जब तक सभी नोड्स का अन्वेषण नहीं हो जाता, और सबसे अच्छा (सबसे बड़ा) सेट लौटाया जाता है। दक्षता बढ़ाने के लिए, एल्गोरिथ्म अवलोकनों की एक ह्यूरिस्टिक ऑर्डरिंग का उपयोग करता है, आमतौर पर उनकी व्यक्तिगत संगतता के आधार पर, शुरुआती अच्छे समाधान खोजने और अधिक आक्रामक रूप से छंटाई करने के लिए।
संयुक्त संगतता परीक्षण
JCBB का मूल संयुक्त संगतता परीक्षण है। मिलानों के एक सेट को देखते हुए, परीक्षण संयुक्त नवाचार वेक्टर और उसके सहप्रसरण मैट्रिक्स की गणना करता है। इस वेक्टर की महालनोबिस दूरी की तुलना ची-स्क्वायर थ्रेशोल्ड से की जाती है, जिसमें स्वतंत्रता की डिग्री नवाचार वेक्टर के आयाम के बराबर होती है। यदि दूरी थ्रेशोल्ड से नीचे है, तो सेट को संयुक्त रूप से संगत माना जाता है। यह परीक्षण व्यक्तिगत परीक्षणों से अधिक शक्तिशाली है क्योंकि यह विशेषताओं के बीच सहसंबंधों को पकड़ता है, जो रोबोट की स्थिति अनिश्चितता और मानचित्र के सहप्रसरण से उत्पन्न होते हैं। उदाहरण के लिए, दो विशेषताएं जो व्यक्तिगत रूप से विभिन्न मानचित्र बिंदुओं के साथ संगत हो सकती हैं, संयुक्त रूप से असंगत हो सकती हैं यदि उनके बीच की सापेक्ष ज्यामिति मानचित्र से मेल नहीं खाती है।
अनुप्रयोग और विस्तार
JCBB व्यापक रूप से SLAM प्रणालियों में लागू किया गया है, विशेष रूप से इनडोर और आउटडोर मोबाइल रोबोटिक्स में। यह अक्सर अनुकूलन या फ़िल्टरिंग से पहले फ्रंट-एंड डेटा सहयोग मॉड्यूल के रूप में उपयोग किया जाता है। एल्गोरिथ्म को विज़ुअल SLAM में भी अनुकूलित किया गया है, जहां विशेषताएं कैमरा छवियों में पता लगाए गए कीपॉइंट होती हैं, और 3D पॉइंट क्लाउड पंजीकरण में। विस्तारों में प्रारंभिक स्थिति अनुमान के लिए JCBB को रैंडम सैंपल कंसेंसस (RANSAC) के साथ संयोजित करना, और बड़े मानचित्रों को संभालने के लिए एक पदानुक्रमित ढांचे में इसका उपयोग करना शामिल है। व्यवहार में, JCBB बड़ी संख्या में विशेषताओं के लिए कम्प्यूटेशनल रूप से महंगा हो सकता है, इसलिए खोज स्थान को कम करने के लिए वेरिएंट प्रस्तावित किए गए हैं, जैसे संगतता ग्राफ और अधिकतम क्लिक एल्गोरिथ्म का उपयोग करना, जो समाधान के संदर्भ में JCBB के बराबर हैं लेकिन तेज़ हो सकते हैं।
अन्य विधियों से संबंध
JCBB की तुलना अक्सर अन्य डेटा सहयोग तकनीकों से की जाती है जैसे व्यक्तिगत संगतता निकटतम पड़ोसी (ICNN), जो तेज़ है लेकिन झूठे मिलानों से ग्रस्त है, और ग्राफ-आधारित विधियों से जो अधिकतम क्लिक समस्या को हल करते हैं। शाखा और बाउंड दृष्टिकोण संयुक्त संगतता मानदंड के तहत वैश्विक रूप से इष्टतम समाधान खोजने की गारंटी देता है, जबकि ह्यूरिस्टिक विधियाँ उप-इष्टतम सेटों पर समझौता कर सकती हैं। हालाँकि, इष्टतमता उच्च कम्प्यूटेशनल जटिलता की कीमत पर आती है, जिससे JCBB ऑफ़लाइन प्रसंस्करण या मध्यम संख्या में विशेषताओं वाले वातावरण के लिए उपयुक्त है। आधुनिक SLAM प्रणालियों में, JCBB को कभी-कभी Machine learning या Deep learning पर आधारित सीखी गई विधियों द्वारा प्रतिस्थापित किया जाता है, लेकिन यह क्षेत्र में एक मौलिक एल्गोरिथ्म बना हुआ है।
यह भी देखें
संदर्भ
- Neira, J., & Tardós, J. D. (2001). डेटा एसोसिएशन इन स्टोकेस्टिक मैपिंग यूज़िंग जॉइंट कम्पैटिबिलिटी. IEEE Transactions on Robotics and Automation, 17(6), 890-897.