संघनन एल्गोरिथ्म (condensation algorithm) दृश्य अनुक्रमों और अन्य गतिशील प्रणालियों में वस्तुओं पर नज़र रखने की एक प्रायिक विधि है। यह कण फ़िल्टर (particle filters) के परिवार से संबंधित है, जो किसी प्रणाली की स्थिति के प्रायिकता वितरण को भारित यादृच्छिक नमूनों के समुच्चय द्वारा निरूपित करते हैं, जिन्हें कण (particles) कहा जाता है। 'संघनन' नाम 'कंडीशनल डेंसिटी प्रोपेगेशन' (Conditional Density Propagation) का संक्षिप्त रूप है, जो समय के साथ सशर्त प्रायिकता घनत्व के प्रसार की इसकी मूल क्रिया को दर्शाता है। यह एल्गोरिथ्म 1990 के दशक के मध्य में दृश्य ट्रैकिंग के लिए एक व्यावहारिक दृष्टिकोण के रूप में प्रस्तुत किया गया था, विशेष रूप से अव्यवस्थित वातावरण में गतिशील वस्तुओं के लिए, जहाँ पारंपरिक कलमन फ़िल्टर (Kalman filters), जो रैखिक गतिकी और गाऊसी शोर मानते हैं, अपर्याप्त होते हैं।
एल्गोरिथ्म एक पुनरावर्ती पूर्वानुमान-अद्यतन चक्र में कार्य करता है। प्रत्येक समय चरण पर, यह पिछले समुच्चय से कणों का एक नया समुच्चय खींचता है, जिसमें चयन की प्रायिकता उनके भारों के समानुपाती होती है; इस प्रक्रिया को पुनर्नमूनाकरण या चयन (resampling or selection) कहा जाता है। फिर प्रत्येक चयनित कण को एक गति मॉडल के अनुसार प्रसारित किया जाता है जो वस्तु की नई स्थिति का पूर्वानुमान करता है, और अनिश्चितता को ध्यान में रखने के लिए अक्सर यादृच्छिक शोर जोड़ा जाता है। अंत में, एल्गोरिथ्म मापता है कि प्रत्येक पूर्वानुमानित कण प्रेक्षित छवि या संवेदक डेटा से कितनी अच्छी तरह मेल खाता है, और इस संभाव्यता के आधार पर एक भार निर्दिष्ट करता है। भारित कण समुच्चय तब वस्तु की स्थिति के पश्च वितरण (posterior distribution) का अनुमान लगाता है, और अनुमानित स्थिति सामान्यतः भारित माध्य या सर्वोच्च भार वाला कण होती है।
ऐतिहासिक विकास
संघनन एल्गोरिथ्म को 1990 के दशक में माइकल आई. जॉर्डन और उनके सहयोगियों द्वारा कैलिफोर्निया विश्वविद्यालय, बर्कले में विकसित किया गया था। आधारभूत शोधपत्र, 'कंडेन्सेशन - कंडीशनल डेंसिटी प्रोपेगेशन फॉर विज़ुअल ट्रैकिंग', 1998 में माइकल इसार्ड और एंड्रयू ब्लेक द्वारा प्रकाशित किया गया था, जो उस समय क्रमशः ऑक्सफोर्ड विश्वविद्यालय और एमआईटी मीडिया लैब में थे। यह कार्य पूर्ववर्ती कण फ़िल्टरिंग विधियों पर आधारित था, जैसे कि 1993 में नील गॉर्डन, डेविड सैलमंड और एड्रियन स्मिथ द्वारा प्रस्तुत बूटस्ट्रैप फ़िल्टर, और अनुक्रमिक महत्व पुनर्नमूनाकरण तकनीक। एल्गोरिथ्म को विशेष रूप से दृश्य ट्रैकिंग में कलमन फ़िल्टर की सीमाओं को संबोधित करने के लिए डिज़ाइन किया गया था, जहाँ वस्तु की गति अत्यधिक अरैखिक हो सकती है और अवलोकन मॉडल अवरोधों या पृष्ठभूमि अव्यवस्था के कारण बहुविध (multimodal) हो सकता है।
एल्गोरिथ्मिक विवरण
संघनन एल्गोरिथ्म को चार मुख्य चरणों में वर्णित किया जा सकता है। पहला, आरंभीकरण: प्रारंभिक पूर्व वितरण (prior distribution) से N कणों का एक समुच्चय खींचा जाता है, प्रत्येक का भार समान होता है। दूसरा, चयन: वर्तमान समुच्चय से प्रतिस्थापन के साथ N कणों का एक नया समुच्चय नमूना किया जाता है, जहाँ किसी कण के चयन की प्रायिकता उसके भार के समानुपाती होती है। यह चरण कणों को उच्च संभाव्यता वाले क्षेत्रों में केंद्रित करता है। तीसरा, पूर्वानुमान: प्रत्येक चयनित कण को एक गतिशील मॉडल के माध्यम से प्रसारित किया जाता है, उदाहरण के लिए, एक यादृच्छिक चाल या स्थिर-वेग मॉडल, जिसमें प्रक्रिया अनिश्चितता को दर्शाने के लिए गाऊसी शोर जोड़ा जाता है। चौथा, माप अद्यतन: प्रत्येक पूर्वानुमानित कण की तुलना वर्तमान अवलोकन से एक संभाव्यता फलन का उपयोग करके की जाती है, और उसका भार तदनुसार अद्यतन किया जाता है। फिर यह चक्र अगले फ्रेम के लिए दोहराया जाता है।
एल्गोरिथ्म की एक प्रमुख विशेषता एक साथ कई परिकल्पनाओं को बनाए रखने की इसकी क्षमता है। चूँकि कण पश्च वितरण के विभिन्न मोडों में फैल सकते हैं, एल्गोरिथ्म अस्थायी अवरोधों या अस्पष्ट स्थितियों के माध्यम से वस्तुओं पर नज़र रख सकता है। कणों की संख्या, N, एक महत्वपूर्ण पैरामीटर है: बहुत कम कण खराब सन्निकटन की ओर ले जाते हैं, जबकि बहुत अधिक कण कम्प्यूटेशनल लागत बढ़ाते हैं। विशिष्ट कार्यान्वयन राज्य की आयामिता और अवलोकन मॉडल की जटिलता के आधार पर सैकड़ों से हजारों कणों का उपयोग करते हैं।
अनुप्रयोग
संघनन एल्गोरिथ्म को कंप्यूटर विज़न और रोबोटिक्स में व्यापक रूप से लागू किया गया है। इसका प्राथमिक उपयोग दृश्य ट्रैकिंग में है, जैसे वीडियो अनुक्रमों में किसी व्यक्ति के सिर या हाथों का अनुसरण करना, यातायात निगरानी में वाहनों पर नज़र रखना, और जोड़दार वस्तुओं की मुद्रा पर नज़र रखना। इसका उपयोग चिकित्सा इमेजिंग में भी किया गया है, उदाहरण के लिए, अल्ट्रासाउंड अनुक्रमों में हृदय की गति पर नज़र रखने के लिए, और संवर्धित वास्तविकता में कैमरा मुद्रा का अनुमान लगाने के लिए। रोबोटिक्स में, एल्गोरिथ्म मोंटे कार्लो स्थानीयकरण (Monte Carlo localization) को रेखांकित करता है, जो एक रोबोट के लिए ज्ञात मानचित्र में अपनी स्थिति का अनुमान लगाने की एक विधि है जो कण फ़िल्टर का उपयोग करती है। एल्गोरिथ्म की लचीलापन ने भाषण पहचान और ऑडियो स्रोत पृथक्करण में इसके उपयोग को भी जन्म दिया है, जहाँ राज्य स्थान ध्वनि स्रोतों की स्थिति या पहचान है।
सीमाएँ और विस्तार
अपनी शक्तियों के बावजूद, संघनन एल्गोरिथ्म की ज्ञात सीमाएँ हैं। मूल संस्करण कण अधःपतन (particle degeneracy) से ग्रस्त है, जहाँ कुछ पुनरावृत्तियों के बाद अधिकांश कणों के भार नगण्य हो जाते हैं, जिससे कम्प्यूटेशनल प्रयास बर्बाद होता है। पुनर्नमूनाकरण इसे कम करता है लेकिन नमूना दरिद्रता (sample impoverishment) का कारण बन सकता है, जहाँ कण समुच्चय विविधता खो देता है, विशेष रूप से कम-शोर परिदृश्यों में। इन मुद्दों को संबोधित करने के लिए विभिन्न विस्तार प्रस्तावित किए गए हैं, जिनमें व्यवस्थित पुनर्नमूनाकरण, सहायक कण फ़िल्टर, और अनसेंटेड कण फ़िल्टर का उपयोग शामिल है। एल्गोरिथ्म को एक सावधानीपूर्वक डिज़ाइन किए गए संभाव्यता फलन की भी आवश्यकता होती है, जो जटिल दृश्यों में चुनौतीपूर्ण हो सकता है। व्यवहार में, कणों की संख्या और गति मॉडल मापदंडों का चुनाव प्रदर्शन को महत्वपूर्ण रूप से प्रभावित करता है, और इन्हें ट्यून करना अक्सर अनुभवजन्य रूप से किया जाता है।
अन्य विधियों से संबंध
संघनन एल्गोरिथ्म कण फ़िल्टर के व्यापक वर्ग का एक विशिष्ट उदाहरण है, जिसे अनुक्रमिक मोंटे कार्लो विधियाँ (sequential Monte Carlo methods) भी कहा जाता है। यह बूटस्ट्रैप फ़िल्टर और नमूनाकरण महत्व पुनर्नमूनाकरण फ़िल्टर से निकटता से संबंधित है। मशीन लर्निंग के संदर्भ में, कण फ़िल्टर राज्य-स्थान मॉडलों में उपयोग किए जाते हैं, जैसे कि सतत राज्यों वाले छिपे हुए मार्कोव मॉडल, और नीति मूल्यांकन के लिए सुदृढीकरण सीखने में। एल्गोरिथ्म सामान्य रूप से मोंटे कार्लो विधियों से भी जुड़ा है, जो जटिल प्रायिकता वितरणों का अनुमान लगाने के लिए यादृच्छिक नमूनाकरण का उपयोग करते हैं। कलमन फ़िल्टर की तुलना में, जो रैखिक गाऊसी प्रणालियों के लिए इष्टतम अनुमान प्रदान करते हैं, संघनन एल्गोरिथ्म उप-इष्टतम है लेकिन कहीं अधिक सामान्य है, जो अरैखिक गतिकी और गैर-गाऊसी शोर को संभालता है। इस सामान्यता ने इसे कंप्यूटर विज़न समुदाय में एक मानक उपकरण बना दिया है, और यह प्रायिक रोबोटिक्स और दृश्य ट्रैकिंग में एक आधारभूत तकनीक बनी हुई है।
यह भी देखें
- कण फ़िल्टर
- कलमन फ़िल्टर
- दृश्य ट्रैकिंग
- मोंटे कार्लो विधियाँ