मीन शिफ्ट: Difference between revisions

From Vigyanwiki
Line 2: Line 2:
{{Machine learning|Clustering}}
{{Machine learning|Clustering}}


मीन शिफ्ट एक  [[गैर पैरामीट्रिक]] [[सुविधा स्थान]] गणितीय विश्लेषण तकनीक है जो एक घनत्व फलन के मैक्सिमा का पता लगाने के लिए एक आधारशील एल्गोरिदम है, जिसे [[मोड (सांख्यिकी)|मोड]]  संवेदना खोजी एल्गोरिदम कहा जाता है।<ref name="PAMI95">{{cite journal
मीन शिफ्ट एक  [[गैर पैरामीट्रिक]] [[सुविधा स्थान]] गणितीय विश्लेषण तकनीक है जो एक घनत्व फलन के मैक्सिमा का पता लगाने के लिए एक आधारशील अभिकलन\ है, जिसे [[मोड (सांख्यिकी)|मोड]]  संवेदना खोजी अभिकलन\ कहा जाता है।<ref name="PAMI95">{{cite journal
   | last = Cheng
   | last = Cheng
   | first = Yizong
   | first = Yizong
Line 42: Line 42:




मीन शिफ्ट एक प्रक्रिया है जिसका उपयोग एक गुणवत्ता फलन के मूल्यकों के मॉड्स की खोज के लिए किया जाता है, जो उस फलन से प्रारूप डेटा के आधार पर लिया गया होता है।<ref name="PAMI95" />यह एक पुनरावृत्तिक विधि है, और हम एक प्रारंभिक अनुमान <math> x </math> के साथ प्रारंभ करते हैं। एक [[कर्नेल (सांख्यिकी)|कर्नल फ़ंक्शन]] <math> K(x_i - x) </math> दिया गया हो। सामान्यतः, उपस्थित अनुमान तक दूरी पर [[रेडियल आधार फ़ंक्शन कर्नेल|गॉसियन कर्नल]] का प्रयोग किया जाता है,
मीन शिफ्ट एक प्रक्रिया है जिसका उपयोग एक गुणवत्ता फलन के मूल्यकों के मॉड्स की खोज के लिए किया जाता है, जो उस फलन से प्रारूप डेटा के आधार पर लिया गया होता है।<ref name="PAMI95" />यह एक पुनरावृत्तिक विधि है, और हम एक प्रारंभिक अनुमान <math> x </math> के साथ प्रारंभ करते हैं। एक [[कर्नेल (सांख्यिकी)|कर्नल फलन]] <math> K(x_i - x) </math> दिया गया हो। सामान्यतः, उपस्थित अनुमान तक दूरी पर [[रेडियल आधार फ़ंक्शन कर्नेल|गॉसियन कर्नल]] का प्रयोग किया जाता है,


<math> K(x_i - x) = e^{-c||x_i - x||^2} </math>. <math> K </math> द्वारा निर्धारित खिड़की में घनत्व का भारी औसत होता है। यह फलन अर्थात' की समीपी बिंदुओं के लिए वजन तय करता है, अर्थात के नए अनुमान के लिए पुनर्मूल्यांकन के लिए प्रयोग किए जाते हैं।
<math> K(x_i - x) = e^{-c||x_i - x||^2} </math>. <math> K </math> द्वारा निर्धारित खिड़की में घनत्व का भारी औसत होता है। यह फलन अर्थात' की समीपी बिंदुओं के लिए वजन तय करता है, अर्थात के नए अनुमान के लिए पुनर्मूल्यांकन के लिए प्रयोग किए जाते हैं।
Line 51: Line 51:
यहां, <math> N(x) </math> के पड़ोसी <math> x </math> है, जो कुछ बिंदुओं का सेट होता है जिनके लिए <math> K(x_i - x) \neq 0 </math> होता है।
यहां, <math> N(x) </math> के पड़ोसी <math> x </math> है, जो कुछ बिंदुओं का सेट होता है जिनके लिए <math> K(x_i - x) \neq 0 </math> होता है।


फुकुनागा और होस्टेट्लर में, अंतर <math>m(x) - x</math> को मीन शिफ्ट कहा जाता है।<ref name="Fukunaga" /> अब मीन-शिफ्ट एल्गोरिदम <math> x </math> को <math> x \leftarrow m(x) </math> से सेट करता है और अनुमानन को<math> m(x) </math>का संघटन होने तक दोहराता है।
फुकुनागा और होस्टेट्लर में, अंतर <math>m(x) - x</math> को मीन शिफ्ट कहा जाता है।<ref name="Fukunaga" /> अब मीन-शिफ्ट अभिकलन\ <math> x </math> को <math> x \leftarrow m(x) </math> से सेट करता है और अनुमानन को<math> m(x) </math>का संघटन होने तक दोहराता है।


यद्यपि मीन शिफ्ट एल्गोरिदम का विस्तृत उपयोग कई एप्लिकेशनों में किया जा चुका है, परंतु एक उच्च आयामी अंतरिक्ष में एक सामान्य कर्नल का उपयोग करके एल्गोरिदम के संघटन के लिए एक कठिनता-मुक्त प्रमाण  अभी तक नहीं प्रस्तुत किया गया है।<ref name=":0">{{Cite journal|title = गॉसियन कर्नेल के साथ माध्य शिफ्ट एल्गोरिदम के अभिसरण के लिए एक पर्याप्त शर्त|journal = Journal of Multivariate Analysis|date = 2015-03-01|pages = 1–10|volume = 135|doi = 10.1016/j.jmva.2014.11.009|first = Youness|last = Aliyari Ghassabeh|doi-access = free}}</ref>अलियारी घसाबेह ने दिखाया कि एक आयाम में मीन शिफ्ट एल्गोरिदम का संघटन प्रमाणित किया जा सकता है जब उसमें एक अलगावशेषी, घुमावशील और सख्त रूप से घटनेवाली प्रोफ़ाइल फ़ंक्शन हो।<ref>{{Cite journal|title = एक-आयामी अंतरिक्ष में माध्य बदलाव एल्गोरिथ्म के अभिसरण पर|journal = Pattern Recognition Letters|date = 2013-09-01|pages = 1423–1427|volume = 34|issue = 12|doi = 10.1016/j.patrec.2013.05.004|first = Youness|last = Aliyari Ghassabeh|arxiv = 1407.2961|s2cid = 10233475}}</ref> यद्यपि, एक-आयामी परिस्थिति में सीमित वास्तविक विश्व अनुप्रयोग होते हैं। इसके अलावा, एक निर्देशांक (या अलग) बिंदुओं की एक सीमित संख्या के साथ उच्च आयामों में एल्गोरिदम के संघटन को प्रमाणित किया गया है।<ref name=":0" /><ref>{{Cite journal|title = माध्य बदलाव के अभिसरण पर एक नोट|journal = Pattern Recognition|date = 2007-06-01|pages = 1756–1762|volume = 40|issue = 6|doi = 10.1016/j.patcog.2006.10.016|first1 = Xiangru|last1 = Li|first2 = Zhanyi|last2 = Hu|first3 = Fuchao|last3 = Wu}}</ref> यद्यपि, किसी भी सामान्य कर्नल फ़ंक्शन के लिए सीमित निर्देशांक बिंदुओं के लिए पर्याप्त स्थितियाँ प्रदान नहीं की गई हैं।
यद्यपि मीन शिफ्ट अभिकलन\ का विस्तृत उपयोग कई एप्लिकेशनों में किया जा चुका है, परंतु एक उच्च आयामी अंतरिक्ष में एक सामान्य कर्नल का उपयोग करके अभिकलन\ के संघटन के लिए एक कठिनता-मुक्त प्रमाण  अभी तक नहीं प्रस्तुत किया गया है।<ref name=":0">{{Cite journal|title = गॉसियन कर्नेल के साथ माध्य शिफ्ट एल्गोरिदम के अभिसरण के लिए एक पर्याप्त शर्त|journal = Journal of Multivariate Analysis|date = 2015-03-01|pages = 1–10|volume = 135|doi = 10.1016/j.jmva.2014.11.009|first = Youness|last = Aliyari Ghassabeh|doi-access = free}}</ref>अलियारी घसाबेह ने दिखाया कि एक आयाम में मीन शिफ्ट अभिकलन\ का संघटन प्रमाणित किया जा सकता है जब उसमें एक अलगावशेषी, घुमावशील और सख्त रूप से घटनेवाली प्रोफ़ाइल फलन हो।<ref>{{Cite journal|title = एक-आयामी अंतरिक्ष में माध्य बदलाव एल्गोरिथ्म के अभिसरण पर|journal = Pattern Recognition Letters|date = 2013-09-01|pages = 1423–1427|volume = 34|issue = 12|doi = 10.1016/j.patrec.2013.05.004|first = Youness|last = Aliyari Ghassabeh|arxiv = 1407.2961|s2cid = 10233475}}</ref> यद्यपि, एक-आयामी परिस्थिति में सीमित वास्तविक विश्व अनुप्रयोग होते हैं। इसके अलावा, एक निर्देशांक (या अलग) बिंदुओं की एक सीमित संख्या के साथ उच्च आयामों में अभिकलन\ के संघटन को प्रमाणित किया गया है।<ref name=":0" /><ref>{{Cite journal|title = माध्य बदलाव के अभिसरण पर एक नोट|journal = Pattern Recognition|date = 2007-06-01|pages = 1756–1762|volume = 40|issue = 6|doi = 10.1016/j.patcog.2006.10.016|first1 = Xiangru|last1 = Li|first2 = Zhanyi|last2 = Hu|first3 = Fuchao|last3 = Wu}}</ref> यद्यपि, किसी भी सामान्य कर्नल फलन के लिए सीमित निर्देशांक बिंदुओं के लिए पर्याप्त स्थितियाँ प्रदान नहीं की गई हैं।


गॉसियन मीन-शिफ्ट एक अपेक्षासंग्रह एवं अधिकतमीकरण एल्गोरिदम है।<ref>{{Cite journal|last=Carreira-Perpinan|first=Miguel A.|date=May 2007|title=गॉसियन मीन-शिफ्ट एक ईएम एल्गोरिथम है|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=29|issue=5|pages=767–776|doi=10.1109/tpami.2007.1057|pmid=17356198|s2cid=6694308|issn=0162-8828}}</ref>
गॉसियन मीन-शिफ्ट एक अपेक्षासंग्रह एवं अधिकतमीकरण अभिकलन\ है।<ref>{{Cite journal|last=Carreira-Perpinan|first=Miguel A.|date=May 2007|title=गॉसियन मीन-शिफ्ट एक ईएम एल्गोरिथम है|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=29|issue=5|pages=767–776|doi=10.1109/tpami.2007.1057|pmid=17356198|s2cid=6694308|issn=0162-8828}}</ref>




==विवरण==
==विवरण==


डेटा एक समाप्त सेट <math>S</math> है जो <math>n</math>-आयामी यूक्लिडियन स्पेस <math>X</math> में एम्बेड है।<math>K</math> एक फ्लैट कर्नल है जो <math>X</math> में <math>\lambda</math>-बॉल  के विशेषता फ़ंक्शन है।
डेटा एक समाप्त सेट <math>S</math> है जो <math>n</math>-आयामी यूक्लिडियन स्पेस <math>X</math> में एम्बेड है।<math>K</math> एक फ्लैट कर्नल है जो <math>X</math> में <math>\lambda</math>-बॉल  के विशेषता फलन है।
<div शैली= टेक्स्ट-संरेखण: केंद्र; >
<div शैली= टेक्स्ट-संरेखण: केंद्र; >
<math>  
<math>  
Line 72: Line 72:
एल्गोरिथ्म के प्रत्येक पुनरावृत्ति में, <math>s \leftarrow m(s)</math> सभी के लिए किया जाता है <math>s \in S</math> इसके साथ ही।
एल्गोरिथ्म के प्रत्येक पुनरावृत्ति में, <math>s \leftarrow m(s)</math> सभी के लिए किया जाता है <math>s \in S</math> इसके साथ ही।


प्रत्येक एल्गोरिदम के प्रत्यावर्तन में, सभी S के प्रत्येक p के लिए m(s) समवर्ती रूप से किया जाता है।  
प्रत्येक अभिकलन के प्रत्यावर्तन में, सभी S के प्रत्येक p के लिए m(s) समवर्ती रूप से किया जाता है।  


पहला प्रश्न है, तो विकिरणीय सेट के दिए गए नमूनों के आधार पर घनत्व फ़ंक्शन का आकलन कैसे करें। सबसे सरल दृष्टिकोन है डेटा को स्मूथ करना, उदाहरण के लिए, एक निश्चित चौड़ाई <math>h</math> के निश्चित कर्नल के साथ उसे गहन करने से हैं।
पहला प्रश्न है, तो विकिरणीय सेट के दिए गए प्रारूपों के आधार पर घनत्व फलन का आकलन कैसे करें। सबसे सरल दृष्टिकोन है डेटा को स्मूथ करना, उदाहरण के लिए, एक निश्चित चौड़ाई <math>h</math> के निश्चित कर्नल के साथ उसे गहन करने से हैं।


<div शैली="टेक्स्ट-संरेखण:" केंद्र;>
<div शैली="टेक्स्ट-संरेखण:" केंद्र;>
Line 81: Line 81:
</math>
</math>
</div>
</div>
'''जहाँ <math>x_i</math> इनपुट प्रारूप हैं और <math>k(r)</math> कर्नेल फलन (या पार्ज़ेन विंडो) है। <math>h</math> एल्गोरिथम में एकमात्र पैरामीटर है और इसे बैंडविड्थ कहा जाता है। इस दृष्टिकोण को कर्नेल घनत्व अनुमान या पार्ज़ेन विंडो तकनीक के रूप में जाना जाता है। एक बार हमने गणना कर ली <math>f(x)</math> उपरोक्त समीकरण से, हम ग्रेडिएंट एसेंट या किसी अन्य अनुकूलन तकनीक का उपयोग करके इसकी स्थानीय मैक्सिमा पा सकते हैं। इस क्रूर बल दृष्टिकोण के साथ समस्या यह है कि, उच्च आयामों के लिए, इसका मूल्यांकन करना कम्प्यूटेशनल रूप से निषेधात्मक हो जाता है <math>f(x)</math> संपूर्ण खोज स्थान पर. इसके बजाय, मीन शिफ्ट एक प्रकार का उपयोग करता है जिसे अनुकूलन साहित्य में मल्टीपल रीस्टार्ट ग्रेडिएंट डिसेंट के रूप में जाना जाता है। स्थानीय अधिकतम के लिए कुछ अनुमान से प्रारंभ करते हुए, <math>y_k</math>, जो एक यादृच्छिक इनपुट डेटा बिंदु हो सकता है <math>x_1</math>, माध्य शिफ्ट घनत्व अनुमान के ग्रेडिएंट की गणना करता है <math>f(x)</math> पर <math>y_k</math> और उस दिशा में एक कठिन कदम उठाता है।<ref>Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011</ref>'''
जहाँ <math>x_i</math> इनपुट प्रारूप हैं और <math>k(r)</math> कर्नेल फलन (या पार्ज़ेन विंडो) है। <math>h</math> एल्गोरिथम में एकमात्र पैरामीटर है और इसे बैंडविड्थ कहा जाता है। इस दृष्टिकोण को कर्नेल घनत्व अनुमान या पार्ज़ेन विंडो तकनीक के रूप में जाना जाता है। एक बार हमने गणना कर ली <math>f(x)</math> उपरोक्त समीकरण से, हम ग्रेडिएंट एसेंट या किसी अन्य अनुकूलन तकनीक का उपयोग करके इसकी स्थानीय मैक्सिमा पा सकते हैं। इस क्रूर बल दृष्टिकोण के साथ समस्या यह है कि, उच्च आयामों के लिए, इसका मूल्यांकन करना कम्प्यूटेशनल रूप से <math>f(x)</math> निषेधात्मक हो जाता है  संपूर्ण खोज स्थान पर. इसके अतिरिक्त, मीन शिफ्ट एक प्रकार का उपयोग करता है जिसे अनुकूलन साहित्य में मल्टीपल रीस्टार्ट ग्रेडिएंट डिसेंट के रूप में जाना जाता है। स्थानीय अधिकतम <math>y_k</math> के लिए कुछ अनुमान से प्रारंभ करते हुए, जो एक यादृच्छिक इनपुट डेटा बिंदु <math>x_1</math> हो सकता है , मीन शिफ्ट घनत्व अनुमान के प्रवणता  <math>f(x)</math> पर <math>y_k</math> की गणना करता है, और उस दिशा में एक कठिन कदम उठाता है।<ref>Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011</ref>






== गुठली के प्रकार ==
 
कर्नेल परिभाषा: चलो <math>X</math> हो <math>n</math>-आयामी यूक्लिडियन अंतरिक्ष, <math> \mathbb{R}^n </math>. का आदर्श <math>x</math> एक गैर-ऋणात्मक संख्या है, <math>  \|x\|^2=x^{\top}x \geq 0 </math>. एक समारोह <math> K: X\rightarrow \mathbb{R} </math> यदि कोई प्रोफ़ाइल मौजूद है तो उसे कर्नेल कहा जाता है, <math> k: [0, \infty]\rightarrow \mathbb{R} </math> , ऐसा है कि
== कर्नेल के प्रकार ==
कर्नेल परिभाषा: मान लीजिये <math>X</math> <math>n</math>-आयामी यूक्लिडियन अंतरिक्ष, <math> \mathbb{R}^n </math>. का आदर्श <math>x</math> एक गैर-ऋणात्मक <math>  \|x\|^2=x^{\top}x \geq 0 </math> संख्या है, . एक फलन <math> K: X\rightarrow \mathbb{R} </math> यदि कोई प्रोफ़ाइल <math> k: [0, \infty]\rightarrow \mathbb{R} </math> उपस्थित है तो उसे कर्नेल कहा जाता है, ऐसा है कि


<math>
<math>
K(x) = k(\|x\|^2)
K(x) = k(\|x\|^2)
</math>
</math> और
और
* k गैर-नकारात्मक है।
* k गैर-नकारात्मक है।
* k गैर-बढ़ती है: <math> k(a)\ge k(b) </math> अगर <math> a < b </math>.
* k गैर-बढ़ती   <math> k(a)\ge k(b) </math> और <math> a < b </math>. है:
* k टुकड़े-टुकड़े निरंतर है और <math> \int_0^\infty k(r)\,dr < \infty\ </math>
* k खंड निरंतर और <math> \int_0^\infty k(r)\,dr < \infty\ </math> है 
माध्य बदलाव के लिए दो सबसे अधिक उपयोग की जाने वाली कर्नेल प्रोफ़ाइल हैं:
मीन शिफ्ट के लिए दो सबसे अधिक उपयोग की जाने वाली कर्नेल प्रोफ़ाइल हैं:


;फ्लैट कर्नेल
;फ्लैट कर्नेल
Line 116: Line 116:
</math>
</math>
</div>
</div>
जहां मानक विचलन पैरामीटर <math>\sigma</math> बैंडविड्थ पैरामीटर के रूप में कार्य करता है, <math> h </math>.
जहां मानक विचलन पैरामीटर <math>\sigma</math> बैंडविड्थ मापदंड <math> h </math> के रूप में कार्य करता है ।.


==अनुप्रयोग==
==अनुप्रयोग==


=== क्लस्टरिंग ===
=== क्लस्टरिंग ===
दो-आयामी अंतरिक्ष में कुछ बिंदुओं का एक सेट पर विचार करें। एक वृत्ताकार खिड़की को कर्नल के रूप में समझें, जो बिंदु <math>C</math> पर केंद्रित है और रेडियस <math>r</math> रखता है। मीन-शिफ्ट एक हिल क्लाइमिंग एल्गोरिदम है जिसमें यह कर्नल घनत्व के उच्चतर क्षेत्र की ओर पुनर्स्थान संघटन तक किया जाता है।प्रत्येक शिफ्ट को माध्य शिफ्ट वेक्टर द्वारा परिभाषित किया जाता है। मीन शिफ्ट वेक्टर हमेशा घनत्व में अधिकतम वृद्धि के दिशा की ओर संकेत करता है। प्रत्येक प्रतियांत्रण में, कर्नल को उसके अंदर बिंदुओं की औसत या मीन के लिए परिस्थान किया जाता है। इस मीन की गणना का विधि कर्नल के चयन पर निर्भर करता है। इस परीस्थिति में, यदि एक फ्लैट कर्नल के अतिरिक्त एक गॉसियन कर्नल का चयन किया जाता है, तो हर बिंदु को पहले एक भार आवंटित किया जाएगा जो कर्नल के केंद्र से दूरी के साथ घटता है। संघटन पर, एक ऐसी दिशा नहीं होगी जिसमें एक शिफ्ट में अधिक से अधिक बिंदु एक कर्नल के अंदर समायोजित कर सके।
दो-आयामी अंतरिक्ष में कुछ बिंदुओं का एक सेट पर विचार करें। एक वृत्ताकार खिड़की को कर्नल के रूप में समझें, जो बिंदु <math>C</math> पर केंद्रित है और रेडियस <math>r</math> रखता है। मीन-शिफ्ट एक हिल क्लाइमिंग अभिकलन\ है जिसमें यह कर्नल घनत्व के उच्चतर क्षेत्र की ओर पुनर्स्थान संघटन तक किया जाता है।प्रत्येक शिफ्ट को मीन शिफ्ट सदिश द्वारा परिभाषित किया जाता है। मीन शिफ्ट सदिश हमेशा घनत्व में अधिकतम वृद्धि के दिशा की ओर संकेत करता है। प्रत्येक प्रतियांत्रण में, कर्नल को उसके अंदर बिंदुओं की औसत या मीन के लिए परिस्थान किया जाता है। इस मीन की गणना का विधि कर्नल के चयन पर निर्भर करता है। इस परीस्थिति में, यदि एक फ्लैट कर्नल के अतिरिक्त एक गॉसियन कर्नल का चयन किया जाता है, तो हर बिंदु को पहले एक भार आवंटित किया जाएगा जो कर्नल के केंद्र से दूरी के साथ घटता है। संघटन पर, एक ऐसी दिशा नहीं होगी जिसमें एक शिफ्ट में अधिक से अधिक बिंदु एक कर्नल के अंदर समायोजित कर सके।


=== ट्रैकिंग ===
=== ट्रैकिंग ===
दृश्य ट्रैकिंग के लिए माध्य शिफ्ट एल्गोरिदम का उपयोग किया जा सकता है। इस तरह का सबसे सरल एल्गोरिदम पिछली छवि में ऑब्जेक्ट के रंग हिस्टोग्राम के आधार पर नई छवि में एक आत्मविश्वास मानचित्र तैयार करेगा, और ऑब्जेक्ट की पुरानी स्थिति के पास आत्मविश्वास मानचित्र के शिखर को खोजने के लिए माध्य बदलाव का उपयोग करेगा। कॉन्फिडेंस मैप नई छवि पर एक संभाव्यता घनत्व फलन है, जो नई छवि के प्रत्येक पिक्सेल को एक संभावना निर्दिष्ट करता है, जो पिछली छवि में ऑब्जेक्ट में होने वाले पिक्सेल रंग की संभावना है। कुछ एल्गोरिदम, जैसे कर्नेल-आधारित ऑब्जेक्ट ट्रैकिंग,<ref name="PAMI03">{{cite journal
मीन शिफ्ट अभिकलन\ विजुअल ट्रैकिंग के लिए उपयोग किया जा सकता है। सबसे सरल ऐसा अभिकलन\ एक विश्वास दिलाने वाली नवीन छवि में एक वस्तु के रंग हिस्टोग्राम पर आधारित एक विश्वास्यता मानचित्र बनाएगा, और मीन शिफ्ट का उपयोग करके वस्तु के पुराने स्थान के नजदीकी एक विश्वास्यता मानचित्र के चरम का पता लगाने में सछम हैं। विश्वास्यता मानचित्र एक प्राकृतिकता घनत्व फलन है जो नई छवि पर प्रत्येक पिक्सेल को एक प्राकृतिकता, यानी पिक्सेल रंग का पिछली छवि में वस्तु में होने की प्राकृतिकता का प्राकृतिकता, का आकलन करता है। कुछ अभिकलन\, जैसे कर्नल-आधारित वस्तु ट्रैकिंग,<ref name="PAMI03">{{cite journal
   | last = Comaniciu
   | last = Comaniciu
   | first = Dorin
   | first = Dorin
Line 137: Line 137:
   | doi = 10.1109/tpami.2003.1195991
   | doi = 10.1109/tpami.2003.1195991
   | citeseerx = 10.1.1.8.7474
   | citeseerx = 10.1.1.8.7474
   }}</ref> समूह ट्रैकिंग,<ref name="avidan2001">{{cite book
   }}</ref> एंसेंबल ट्रैकिंग<ref name="avidan2001">{{cite book
   | last = Avidan
   | last = Avidan
   | first = Shai
   | first = Shai
Line 152: Line 152:
   | isbn = 978-0-7695-2372-9
   | isbn = 978-0-7695-2372-9
   | s2cid = 1638397
   | s2cid = 1638397
  }}</ref> कैमशिफ्ट <ref>[[Gary Bradski]] (1998) [http://download.intel.com/technology/itj/q21998/pdf/camshift.pdf Computer Vision Face Tracking For Use in a Perceptual User Interface] {{webarchive|url=https://web.archive.org/web/20120417121810/http://download.intel.com/technology/itj/q21998/pdf/camshift.pdf |date=2012-04-17 }}, Intel Technology Journal, No. Q2.</ref><ref name="Emami2001">{{cite book
  }}</ref>कैमशिफ्ट <ref>[[Gary Bradski]] (1998) [http://download.intel.com/technology/itj/q21998/pdf/camshift.pdf Computer Vision Face Tracking For Use in a Perceptual User Interface] {{webarchive|url=https://web.archive.org/web/20120417121810/http://download.intel.com/technology/itj/q21998/pdf/camshift.pdf |date=2012-04-17 }}, Intel Technology Journal, No. Q2.</ref><ref name="Emami2001">{{cite book
   | last = Emami
   | last = Emami
   | first = Ebrahim
   | first = Ebrahim
Line 165: Line 165:
   | isbn = 978-1-4673-6184-2
   | isbn = 978-1-4673-6184-2
   | s2cid = 15864761
   | s2cid = 15864761
  }}</ref> इस विचार का विस्तार करें.
  }}</ref> इस विचार पर विस्तार करते हैं।


=== चौरसाई ===
=== चौरसाई ===
होने देना <math>x_i</math> और <math>z_i, i = 1,...,n,</math> हो <math>d</math>-संयुक्त स्थानिक-श्रेणी डोमेन में आयामी इनपुट और फ़िल्टर किए गए छवि पिक्सेल। प्रत्येक पिक्सेल के लिए,
मान लीजिये <math>x_i</math> और <math>z_i, i = 1,...,n,</math> हो <math>d</math>-संयुक्त स्थानिक-श्रेणी डोमेन में आयामी इनपुट और फ़िल्टर किए गए छवि पिक्सेल। प्रत्येक पिक्सेल के लिए,


* आरंभ करें <math>j = 1</math> और <math>y_{i,1} = x_i</math>
* <math>j = 1</math> और <math>y_{i,1} = x_i</math> आरंभ करें।
*गणना करें <math>y_{i,j+1}</math> के अनुसार <math>m(\cdot)</math> अभिसरण तक, <math>y = y_{i,c}</math>.
*<math>y_{i,j+1}</math> के अनुसार <math>m(\cdot)</math> अभिसरण तक, <math>y = y_{i,c}</math>. गणना करें।
* सौंपना <math>z_i =(x_i^s,y_{i,c}^r)</math>. सुपरस्क्रिप्ट s और r क्रमशः एक वेक्टर के स्थानिक और श्रेणी घटकों को दर्शाते हैं। असाइनमेंट निर्दिष्ट करता है कि स्थानिक स्थान अक्ष पर फ़िल्टर किए गए डेटा में अभिसरण बिंदु का रेंज घटक होगा <math>y_{i,c}^r</math>.
* निर्धारित  <math>z_i =(x_i^s,y_{i,c}^r)</math>. करते हैं, सुपरस्क्रिप्ट s और r क्रमशः एक सदिश के स्थानिक और श्रेणी घटकों को दर्शाते हैं। असाइनमेंट निर्दिष्ट करता है कि स्थानिक स्थान अक्ष पर फ़िल्टर किए गए डेटा में <math>y_{i,c}^r</math> अभिसरण बिंदु का रेंज घटक होगा .


==ताकतें==
==ताकतें==


# मीन शिफ्ट वास्तविक डेटा विश्लेषण के लिए उपयुक्त एक एप्लिकेशन-स्वतंत्र उपकरण है।
# मीन शिफ्ट वास्तविक डेटा विश्लेषण के लिए उपयुक्त एक एप्लिकेशन-स्वतंत्र उपकरण है।
# डेटा क्लस्टर पर कोई पूर्वनिर्धारित आकार नहीं लेता है।
# इसमें डेटा क्लस्टर्स पर किसी भी पूर्वनिर्धारित आकृति का अनुमान नहीं लगाया जाता है।
# यह मनमाने फीचर स्पेस को संभालने में सक्षम है।
# यह विभिन्न फ़ीचर स्पेस को संभालने की क्षमता रखता है।
# प्रक्रिया एकल पैरामीटर की पसंद पर निर्भर करती है: बैंडविड्थ।
# इस प्रक्रिया को एकल पैरामीटर: बैंडविड्थ के चयन पर निर्भर करती है।
# बैंडविड्थ/विंडो आकार 'एच' का एक भौतिक अर्थ है, के-मीन्स|के-मीन्स के विपरीत।
# बैंडविड्थ/विंडो का आकार 'h' भौतिक अर्थ रखता है, जो k-मीन्स के विपरीत है।


==कमजोरियाँ==
==कमजोरियाँ==


# विंडो आकार का चयन कोई मामूली बात नहीं है.
# विंडो का आकार का चयन सरल नहीं होता है।
# अनुपयुक्त विंडो आकार के कारण मोड मर्ज हो सकते हैं, या अतिरिक्त "उथले" मोड उत्पन्न हो सकते हैं।
# अनुपयुक्त विंडो का आकार मोड को मिलाने के कारण बन सकता है, या अतिरिक्त "अल्प" मोड उत्पन्न कर सकता है।
# अक्सर अनुकूली विंडो आकार का उपयोग करने की आवश्यकता होती है।
# प्रायः संवेदनशील विंडो का उपयोग करने की आवश्यकता होती है।


==उपलब्धता==
==उपलब्धता==


एल्गोरिदम के वेरिएंट मशीन लर्निंग और [[ इमेजेज ]] प्रोसेसिंग पैकेज में पाए जा सकते हैं:
अभिकलन\ के विभिन्न रूप डेटा विश्लेषण और [[ इमेजेज |छवि]] प्रसंस्करण पैकेजों में देखे जा सकते हैं:


* [[ मूर्तियों ]]कई क्लस्टरिंग एल्गोरिदम के साथ जावा डेटा माइनिंग टूल।
* [[ मूर्तियों |एल्की]] जावा डेटा खनन उपकरण जिसमें कई क्लस्टरिंग अभिकलन\ होते हैं।
* छवि जे. माध्य शिफ्ट फ़िल्टर का उपयोग करके छवि फ़िल्टरिंग।
*छवि जे. मीन शिफ्ट फिल्टर का उपयोग करके छवि फ़िल्टरिंग की जाती हैं।
*[[ mlpack ]]. कुशल दोहरे वृक्ष एल्गोरिदम-आधारित कार्यान्वयन।
*[[ mlpack |एमएलपैक]]. कुशल द्विपेड़ आधारित अनुमानन विधि पर आधारित कार्यान्वयन होता हैं।
* [[OpenCV]] में cvMeanShift विधि के माध्यम से माध्य-शिफ्ट कार्यान्वयन सम्मिलित है
* [[OpenCV|ओपनसीवी]] में सीवीमीनशिफ्ट विधि के मीनम से मीन-शिफ्ट कार्यान्वयन सम्मिलित है।.
* [[ऑर्फियो टूलबॉक्स]]एक C++ कार्यान्वयन.
* [[ऑर्फियो टूलबॉक्स]] एक C++ कार्यान्वयन करता हैं।.
* [[स्किकिट-लर्न]] नम्पी/पायथन कार्यान्वयन कुशल पड़ोसी बिंदुओं के लुकअप के लिए बॉल ट्री का उपयोग करता है
* [[स्किकिट-लर्न]] नम्पी/पायथन कार्यान्वयन कुशल पड़ोसी बिंदुओं के लुकअप के लिए बॉल ट्री का उपयोग करता है।.


== यह भी देखें ==
== यह भी देखें ==

Revision as of 23:20, 27 July 2023

मीन शिफ्ट एक गैर पैरामीट्रिक सुविधा स्थान गणितीय विश्लेषण तकनीक है जो एक घनत्व फलन के मैक्सिमा का पता लगाने के लिए एक आधारशील अभिकलन\ है, जिसे मोड संवेदना खोजी अभिकलन\ कहा जाता है।[1] इसके अनुप्रयोग डिजिटल दृष्टि में क्लस्टर विश्लेषण और छवि प्रसंस्करण में किया जाता है।[2]

इतिहास

मीन शिफ्ट प्रक्रिया को सामान्यतः 1975 में फुकुनागा और होस्टेटलर के कार्य का श्रेय दिया जाता है।[3] यद्यपि, यह 1964 में श्नेल द्वारा किए गए पहले कार्य को याद दिलाता है।[4]

सिंहावलोकन

मीन शिफ्ट एक प्रक्रिया है जिसका उपयोग एक गुणवत्ता फलन के मूल्यकों के मॉड्स की खोज के लिए किया जाता है, जो उस फलन से प्रारूप डेटा के आधार पर लिया गया होता है।[1]यह एक पुनरावृत्तिक विधि है, और हम एक प्रारंभिक अनुमान के साथ प्रारंभ करते हैं। एक कर्नल फलन दिया गया हो। सामान्यतः, उपस्थित अनुमान तक दूरी पर गॉसियन कर्नल का प्रयोग किया जाता है,

. द्वारा निर्धारित खिड़की में घनत्व का भारी औसत होता है। यह फलन अर्थात' की समीपी बिंदुओं के लिए वजन तय करता है, अर्थात के नए अनुमान के लिए पुनर्मूल्यांकन के लिए प्रयोग किए जाते हैं।

.

यहां, के पड़ोसी है, जो कुछ बिंदुओं का सेट होता है जिनके लिए होता है।

फुकुनागा और होस्टेट्लर में, अंतर को मीन शिफ्ट कहा जाता है।[3] अब मीन-शिफ्ट अभिकलन\ को से सेट करता है और अनुमानन कोका संघटन होने तक दोहराता है।

यद्यपि मीन शिफ्ट अभिकलन\ का विस्तृत उपयोग कई एप्लिकेशनों में किया जा चुका है, परंतु एक उच्च आयामी अंतरिक्ष में एक सामान्य कर्नल का उपयोग करके अभिकलन\ के संघटन के लिए एक कठिनता-मुक्त प्रमाण अभी तक नहीं प्रस्तुत किया गया है।[5]अलियारी घसाबेह ने दिखाया कि एक आयाम में मीन शिफ्ट अभिकलन\ का संघटन प्रमाणित किया जा सकता है जब उसमें एक अलगावशेषी, घुमावशील और सख्त रूप से घटनेवाली प्रोफ़ाइल फलन हो।[6] यद्यपि, एक-आयामी परिस्थिति में सीमित वास्तविक विश्व अनुप्रयोग होते हैं। इसके अलावा, एक निर्देशांक (या अलग) बिंदुओं की एक सीमित संख्या के साथ उच्च आयामों में अभिकलन\ के संघटन को प्रमाणित किया गया है।[5][7] यद्यपि, किसी भी सामान्य कर्नल फलन के लिए सीमित निर्देशांक बिंदुओं के लिए पर्याप्त स्थितियाँ प्रदान नहीं की गई हैं।

गॉसियन मीन-शिफ्ट एक अपेक्षासंग्रह एवं अधिकतमीकरण अभिकलन\ है।[8]


विवरण

डेटा एक समाप्त सेट है जो -आयामी यूक्लिडियन स्पेस में एम्बेड है। एक फ्लैट कर्नल है जो में -बॉल के विशेषता फलन है।

एल्गोरिथ्म के प्रत्येक पुनरावृत्ति में, सभी के लिए किया जाता है इसके साथ ही।

प्रत्येक अभिकलन के प्रत्यावर्तन में, सभी S के प्रत्येक p के लिए m(s) समवर्ती रूप से किया जाता है।

पहला प्रश्न है, तो विकिरणीय सेट के दिए गए प्रारूपों के आधार पर घनत्व फलन का आकलन कैसे करें। सबसे सरल दृष्टिकोन है डेटा को स्मूथ करना, उदाहरण के लिए, एक निश्चित चौड़ाई के निश्चित कर्नल के साथ उसे गहन करने से हैं।

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



कर्नेल के प्रकार

कर्नेल परिभाषा: मान लीजिये -आयामी यूक्लिडियन अंतरिक्ष, . का आदर्श एक गैर-ऋणात्मक संख्या है, . एक फलन यदि कोई प्रोफ़ाइल उपस्थित है तो उसे कर्नेल कहा जाता है, ऐसा है कि

और

  • k गैर-नकारात्मक है।
  • k गैर-बढ़ती और . है:
  • k खंड निरंतर और है

मीन शिफ्ट के लिए दो सबसे अधिक उपयोग की जाने वाली कर्नेल प्रोफ़ाइल हैं:

फ्लैट कर्नेल

गाऊसी कर्नेल

जहां मानक विचलन पैरामीटर बैंडविड्थ मापदंड के रूप में कार्य करता है ।.

अनुप्रयोग

क्लस्टरिंग

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

ट्रैकिंग

मीन शिफ्ट अभिकलन\ विजुअल ट्रैकिंग के लिए उपयोग किया जा सकता है। सबसे सरल ऐसा अभिकलन\ एक विश्वास दिलाने वाली नवीन छवि में एक वस्तु के रंग हिस्टोग्राम पर आधारित एक विश्वास्यता मानचित्र बनाएगा, और मीन शिफ्ट का उपयोग करके वस्तु के पुराने स्थान के नजदीकी एक विश्वास्यता मानचित्र के चरम का पता लगाने में सछम हैं। विश्वास्यता मानचित्र एक प्राकृतिकता घनत्व फलन है जो नई छवि पर प्रत्येक पिक्सेल को एक प्राकृतिकता, यानी पिक्सेल रंग का पिछली छवि में वस्तु में होने की प्राकृतिकता का प्राकृतिकता, का आकलन करता है। कुछ अभिकलन\, जैसे कर्नल-आधारित वस्तु ट्रैकिंग,[10] एंसेंबल ट्रैकिंग[11]कैमशिफ्ट [12][13] इस विचार पर विस्तार करते हैं।

चौरसाई

मान लीजिये और हो -संयुक्त स्थानिक-श्रेणी डोमेन में आयामी इनपुट और फ़िल्टर किए गए छवि पिक्सेल। प्रत्येक पिक्सेल के लिए,

  • और आरंभ करें।
  • के अनुसार अभिसरण तक, . गणना करें।
  • निर्धारित . करते हैं, सुपरस्क्रिप्ट s और r क्रमशः एक सदिश के स्थानिक और श्रेणी घटकों को दर्शाते हैं। असाइनमेंट निर्दिष्ट करता है कि स्थानिक स्थान अक्ष पर फ़िल्टर किए गए डेटा में अभिसरण बिंदु का रेंज घटक होगा .।

ताकतें

  1. मीन शिफ्ट वास्तविक डेटा विश्लेषण के लिए उपयुक्त एक एप्लिकेशन-स्वतंत्र उपकरण है।
  2. इसमें डेटा क्लस्टर्स पर किसी भी पूर्वनिर्धारित आकृति का अनुमान नहीं लगाया जाता है।
  3. यह विभिन्न फ़ीचर स्पेस को संभालने की क्षमता रखता है।
  4. इस प्रक्रिया को एकल पैरामीटर: बैंडविड्थ के चयन पर निर्भर करती है।
  5. बैंडविड्थ/विंडो का आकार 'h' भौतिक अर्थ रखता है, जो k-मीन्स के विपरीत है।

कमजोरियाँ

  1. विंडो का आकार का चयन सरल नहीं होता है।
  2. अनुपयुक्त विंडो का आकार मोड को मिलाने के कारण बन सकता है, या अतिरिक्त "अल्प" मोड उत्पन्न कर सकता है।
  3. प्रायः संवेदनशील विंडो का उपयोग करने की आवश्यकता होती है।

उपलब्धता

अभिकलन\ के विभिन्न रूप डेटा विश्लेषण और छवि प्रसंस्करण पैकेजों में देखे जा सकते हैं:

  • एल्की जावा डेटा खनन उपकरण जिसमें कई क्लस्टरिंग अभिकलन\ होते हैं।
  • छवि जे. मीन शिफ्ट फिल्टर का उपयोग करके छवि फ़िल्टरिंग की जाती हैं।
  • एमएलपैक. कुशल द्विपेड़ आधारित अनुमानन विधि पर आधारित कार्यान्वयन होता हैं।
  • ओपनसीवी में सीवीमीनशिफ्ट विधि के मीनम से मीन-शिफ्ट कार्यान्वयन सम्मिलित है।.
  • ऑर्फियो टूलबॉक्स एक C++ कार्यान्वयन करता हैं।.
  • स्किकिट-लर्न नम्पी/पायथन कार्यान्वयन कुशल पड़ोसी बिंदुओं के लुकअप के लिए बॉल ट्री का उपयोग करता है।.

यह भी देखें

संदर्भ

  1. 1.0 1.1 Cheng, Yizong (August 1995). "Mean Shift, Mode Seeking, and Clustering". IEEE Transactions on Pattern Analysis and Machine Intelligence. 17 (8): 790–799. CiteSeerX 10.1.1.510.1222. doi:10.1109/34.400568.
  2. Comaniciu, Dorin; Peter Meer (May 2002). "Mean Shift: A Robust Approach Toward Feature Space Analysis". IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (5): 603–619. CiteSeerX 10.1.1.160.3832. doi:10.1109/34.1000236.
  3. 3.0 3.1 Fukunaga, Keinosuke; Larry D. Hostetler (January 1975). "The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition". IEEE Transactions on Information Theory. 21 (1): 32–40. doi:10.1109/TIT.1975.1055330.
  4. Schnell, P. (1964). "समूहों को खोजने की एक विधि". Biometrische Zeitschrift (in Deutsch). 6 (1): 47–48. doi:10.1002/bimj.19640060105.
  5. 5.0 5.1 Aliyari Ghassabeh, Youness (2015-03-01). "गॉसियन कर्नेल के साथ माध्य शिफ्ट एल्गोरिदम के अभिसरण के लिए एक पर्याप्त शर्त". Journal of Multivariate Analysis. 135: 1–10. doi:10.1016/j.jmva.2014.11.009.
  6. Aliyari Ghassabeh, Youness (2013-09-01). "एक-आयामी अंतरिक्ष में माध्य बदलाव एल्गोरिथ्म के अभिसरण पर". Pattern Recognition Letters. 34 (12): 1423–1427. arXiv:1407.2961. doi:10.1016/j.patrec.2013.05.004. S2CID 10233475.
  7. Li, Xiangru; Hu, Zhanyi; Wu, Fuchao (2007-06-01). "माध्य बदलाव के अभिसरण पर एक नोट". Pattern Recognition. 40 (6): 1756–1762. doi:10.1016/j.patcog.2006.10.016.
  8. Carreira-Perpinan, Miguel A. (May 2007). "गॉसियन मीन-शिफ्ट एक ईएम एल्गोरिथम है". IEEE Transactions on Pattern Analysis and Machine Intelligence. 29 (5): 767–776. doi:10.1109/tpami.2007.1057. ISSN 0162-8828. PMID 17356198. S2CID 6694308.
  9. Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011
  10. Comaniciu, Dorin; Visvanathan Ramesh; Peter Meer (May 2003). "Kernel-based Object Tracking". IEEE Transactions on Pattern Analysis and Machine Intelligence. 25 (5): 564–575. CiteSeerX 10.1.1.8.7474. doi:10.1109/tpami.2003.1195991.
  11. Avidan, Shai (2005). Ensemble tracking. pp. 494–501. doi:10.1109/CVPR.2005.144. ISBN 978-0-7695-2372-9. PMID 17170479. S2CID 1638397. {{cite book}}: |journal= ignored (help)
  12. Gary Bradski (1998) Computer Vision Face Tracking For Use in a Perceptual User Interface Archived 2012-04-17 at the Wayback Machine, Intel Technology Journal, No. Q2.
  13. Emami, Ebrahim (2013). "Online failure detection and correction for CAMShift tracking algorithm". 2013 8th Iranian Conference on Machine Vision and Image Processing (MVIP). pp. 180–183. doi:10.1109/IranianMVIP.2013.6779974. ISBN 978-1-4673-6184-2. S2CID 15864761. {{cite book}}: |journal= ignored (help)