स्तर समुच्चय (डेटा संरचनाएं): Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
{{Cleanup bare URLs|date=August 2022}}
{{Cleanup bare URLs|date=August 2022}}
[[कंप्यूटर विज्ञान]] में एक स्तर सेट [[डेटा संरचना]] को अलग-अलग [[नमूनाकरण (सांख्यिकी)]] गतिशील स्तर सेट कार्यों का प्रतिनिधित्व करने के लिए डिज़ाइन किया गया है।
[[कंप्यूटर विज्ञान]] में एक स्तर समुच्चय [[डेटा संरचना|आँकड़े संरचना]] को अलग-अलग [[नमूनाकरण (सांख्यिकी)|नमूने (सांख्यिकी)]] वाले गतिशील स्तर समुच्चय कार्यों का प्रतिनिधित्व करने के लिए बनाया गया है।


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


== कालानुक्रमिक घटनाक्रम ==
== कालानुक्रमिक घटनाक्रम ==
शक्तिशाली [[स्तर-सेट विधि]] [[स्टेनली ओशर]] और [[जेम्स सेथियन]] 1988 के कारण है।<ref name=Osher>Osher, S. & Sethian, J. A. 1988. "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi
शक्तिशाली [[स्तर-सेट विधि|स्तर-समुच्चय विधि]] [[स्टेनली ओशर]] और [[जेम्स सेथियन]] 1988 के कारण है।<ref name=Osher>Osher, S. & Sethian, J. A. 1988. "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi
formulations". ''Journal of Computation Physics'' 79:12–49.</ref> हालांकि, मूल्यों के घने डी-आयामी [[सरणी डेटा संरचना]] के माध्यम से सीधा कार्यान्वयन, परिणाम समय और भंडारण जटिलता दोनों में होता है <math>O(n^d)</math>, कहाँ पे <math>n</math> डोमेन के स्थानिक विस्तार का क्रॉस सेक्शनल रिज़ॉल्यूशन है और <math>d</math> डोमेन के स्थानिक आयामों की संख्या है।
formulations". ''Journal of Computation Physics'' 79:12–49.</ref> चूंकि, मूल्यों के घने डी-आयामी [[सरणी डेटा संरचना|सरणी आँकड़े संरचना]] के माध्यम से सीधा कार्यान्वयन <math>O(n^d)</math>, जहाँ  <math>n</math> समय और भंडारण जटिलता दोनों में परिणाम देता है, डोमेन के स्थानिक विस्तार का प्रतिच्छेद अनुभागीय विश्लेषण है और <math>d</math> डोमेन के स्थानिक आयामों की संख्या है।


===संकीर्ण बैंड===
===संकीर्ण बैंड===
नैरो बैंड लेवल सेट विधि, 1995 में एडालस्टीनसन और सेथियन द्वारा शुरू की गई,<ref name="Adalsteinsson">Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." ''[[Journal of Computational Physics]]''. 118(2)269–277.</ref> अधिकांश संगणनाओं को इंटरफ़ेस के आसपास के सक्रिय स्वरों के एक पतले बैंड तक सीमित कर दिया, इस प्रकार तीन आयामों में समय की जटिलता को कम कर दिया <math>O(n^2)</math> अधिकांश ऑपरेशनों के लिए। सक्रिय स्वरों की सूची को फिर से बनाने के लिए नैरोबैंड संरचना के आवधिक अद्यतन की आवश्यकता थी, जिसके लिए एक आवश्यक था <math>O(n^3)</math> ऑपरेशन जिसमें पूरे वॉल्यूम पर वोक्सल्स एक्सेस किए गए थे। इस नैरोबैंड योजना के लिए भंडारण जटिलता अभी भी थी <math>O(n^3).</math> संकीर्ण बैंड डोमेन एज पर डिफरेंशियल कंस्ट्रक्शन को समाधान को स्थिर करने के लिए सावधानीपूर्वक प्रक्षेप और डोमेन परिवर्तन योजनाओं की आवश्यकता होती है।<ref>{{cite journal|title=इंटरफेस के प्रचार के लिए एक तेज़ स्तर सेट विधि|author1=Adalsteinsson, D  |author2=Sethian, J|journal=Journal of Computational Physics |volume=118 |issue=2 |pages=269 |year=1994|citeseerx=10.1.1.46.1716 |bibcode=1995JCoPh.118..269A |doi=10.1006/jcph.1995.1098 }}</ref>
1995 में एडालस्टीनसन और सेथियन द्वारा संकीर्ण बैंड स्तर समुच्चय विधि की शुरूआत की थी<ref name="Adalsteinsson">Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." ''[[Journal of Computational Physics]]''. 118(2)269–277.</ref> अधिकांश संगणनाओं को इंटरफ़ेस के आसपास के सक्रिय स्वरों के एक पतले बैंड तक सीमित कर दिया, इस प्रकार तीन आयामों में समय की जटिलता को <math>O(n^2)</math> तक कम कर दिया जाता है। सक्रिय स्वरों की सूची को फिर से बनाने के लिए नैरोबैंड संरचना के आवधिक अद्यतन की आवश्यकता थी, जिसके लिए एक <math>O(n^3)</math> ऑपरेशन की आवश्यक थी  जिसमें पूरे वॉल्यूम पर वोक्सल्स एक्सेस किए गए थे। इस नैरोबैंड योजना के लिए भंडारण जटिलता अभी <math>O(n^3).</math> भी थीसंकीर्ण बैंड डोमेन एज पर डिफरेंशियल कंस्ट्रक्शन को समाधान को स्थिर करने के लिए सावधानीपूर्वक प्रक्षेप और डोमेन परिवर्तन योजनाओं की आवश्यकता होती है।<ref>{{cite journal|title=इंटरफेस के प्रचार के लिए एक तेज़ स्तर सेट विधि|author1=Adalsteinsson, D  |author2=Sethian, J|journal=Journal of Computational Physics |volume=118 |issue=2 |pages=269 |year=1994|citeseerx=10.1.1.46.1716 |bibcode=1995JCoPh.118..269A |doi=10.1006/jcph.1995.1098 }}</ref>




=== विरल क्षेत्र ===
=== विरल क्षेत्र ===
इस <math>O(n^3)</math> 1998 में व्हिटेकर द्वारा शुरू की गई अनुमानित विरल क्षेत्र स्तर सेट पद्धति में समय की जटिलता को समाप्त कर दिया गया था।<ref name=Whitaker>Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." ''[[International Journal of Computer Vision]].'' 29(3)203–231.</ref> इंटरफ़ेस के चारों ओर सक्रिय स्वरों को ट्रैक करने के लिए विरल फ़ील्ड स्तर सेट विधि लिंक्ड सूचियों के एक सेट को नियोजित करती है। यह किसी भी महत्वपूर्ण ओवरहेड के बिना आवश्यकतानुसार सक्रिय क्षेत्र के वृद्धिशील विस्तार की अनुमति देता है। जबकि लगातार <math>O(n^2)</math> समय में कुशल, <math>O(n^3)</math> भंडारण स्थान अभी भी विरल क्षेत्र स्तर सेट विधि द्वारा आवश्यक है। देखना<ref name=Lankton>S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/></ref> कार्यान्वयन विवरण के लिए।
यह <math>O(n^3)</math> समय की जटिलता को 1998 में व्हिटेकर द्वारा पेश किए गए अनुमानित "स्पार्स फील्ड" लेवल सेट पद्धति में समाप्त कर दिया गया था।<ref name=Whitaker>Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." ''[[International Journal of Computer Vision]].'' 29(3)203–231.</ref> इंटरफ़ेस के चारों ओर सक्रिय स्वरों को ट्रैक करने के लिए विरल फ़ील्ड स्तर समुच्चय विधि लिंक्ड सूचियों के एक समुच्चय को नियोजित करती है। यह किसी भी महत्वपूर्ण ओवरहेड के बिना आवश्यकतानुसार सक्रिय क्षेत्र के वृद्धिशील विस्तार की अनुमति देता है। जबकि लगातार <math>O(n^2)</math> समय में कुशल, <math>O(n^3)</math> भंडारण स्थान अभी भी विरल क्षेत्र स्तर समुच्चय विधि द्वारा आवश्यक है।<ref name=Lankton>S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/></ref> कार्यान्वयन के लिए विवरण देखे।


=== विरल ब्लॉक ग्रिड ===
=== विरल ब्लॉक ग्रिड ===
स्पार्स ब्लॉक ग्रिड विधि, 2003 में ब्रिडसन द्वारा शुरू की गई,<ref name=Bridson>Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." [[Stanford University]], Stanford, California.</ref> आकार के पूरे [[बाउंडिंग वॉल्यूम]] को विभाजित करता है <math>n^3</math> के छोटे घन ब्लॉकों में <math>m^3</math> स्वर प्रत्येक। आकार का एक मोटा ग्रिड <math>(n/m
2003 में ब्रिडसन द्वारा स्पार्स ब्लॉक ग्रिड विधि की शुरुआत की गई थी,<ref name=Bridson>Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." [[Stanford University]], Stanford, California.</ref> <math>n^3</math> आकार के पूरे [[बाउंडिंग वॉल्यूम]] को <math>m^3</math> स्वर के छोटे घन ब्लॉकों में विभाजित करता है। आकार का एक मोटा ग्रिड <math>(n/m
)^3</math> फिर पॉइंटर्स को केवल उन ब्लॉकों में संग्रहीत करता है जो स्तर सेट के संकीर्ण बैंड को पार करते हैं। ब्लॉक आवंटन और डीलोकेशन घटित होते हैं क्योंकि सतह विकृतियों को समायोजित करने के लिए फैलती है। इस पद्धति में एक उप-इष्टतम भंडारण जटिलता है <math>O\left((nm)3 + m^3n^2\right)</math>, लेकिन सघन ग्रिडों में निहित निरंतर समय पहुंच को बरकरार रखता है।
)^3</math> फिर पॉइंटर्स को केवल उन ब्लॉकों में संग्रहीत करता है जो स्तर समुच्चय के संकीर्ण बैंड को पार करते हैं। ब्लॉक आवंटन और डीलोकेशन घटित होते हैं क्योंकि सतह विकृतियों को समायोजित करने के लिए फैलती है। इस पद्धति में <math>O\left((nm)3 + m^3n^2\right)</math> एक उप-इष्टतम भंडारण जटिलता है , लेकिन सघन ग्रिडों में निहित निरंतर समय पहुंच को बरकरार रखता है।


=== [[अष्टक]] ===
=== [[अष्टक]] ===
1999 में स्ट्रेन द्वारा शुरू की गई ऑक्ट्री लेवल सेट विधि<ref name=Strain>Strain, J. 1999. "Tree methods for moving interfaces." ''[[Journal of Computational Physics]]''. 151(2)616–648.</ref> और लोसासो, गिबू और फेडकीव द्वारा परिष्कृत,<ref name=Losasso>Losasso, F., Gibou, F., & Fedkiw, R. 2004. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.459.1489&rep=rep1&type=pdf Simulating water and smoke with an octree data structure]. [[ACM Transactions on Graphics]]. 23(3)457–462.</ref> और हाल ही में मिन और गिबू द्वारा<ref name=MinGibou>Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. [[Journal of Computational Physics]]. 225(1)300–321.</ref> नेस्टेड क्यूब्स के पेड़ का उपयोग करता है जिसमें पत्ती नोड्स में हस्ताक्षरित दूरी मान होते हैं। पर्याप्त सटीकता प्राप्त करने के लिए वर्तमान में ऑक्ट्री स्तर के सेट को इंटरफ़ेस (यानी संकीर्ण बैंड) के साथ एक समान शोधन की आवश्यकता होती है। भंडारण के मामले में यह प्रतिनिधित्व कुशल है, <math>O(n^2),</math> और एक्सेस प्रश्नों के मामले में अपेक्षाकृत कुशल, <math>O(\log\, n).</math> ऑक्ट्री डेटा संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई आंशिक अंतर समीकरणों को हल कर सकता है जो विशिष्ट मुक्त सीमा समस्याओं से जुड़ा होता है जो स्तर सेट पद्धति का उपयोग करते हैं। CASL अनुसंधान समूह<ref name=CASL>http://www1.engr.ucsb.edu/~fgibou/Research.html</ref> कम्प्यूटेशनल सामग्री, कम्प्यूटेशनल द्रव गतिकी, इलेक्ट्रोकाइनेटिक्स, छवि निर्देशित सर्जरी और नियंत्रण में काम की इस पंक्ति को विकसित किया है।
1999 में स्ट्रेन द्वारा शुरू की गई ऑक्ट्री लेवल समुच्चय विधि<ref name=Strain>Strain, J. 1999. "Tree methods for moving interfaces." ''[[Journal of Computational Physics]]''. 151(2)616–648.</ref> और लोसासो, गिबू और फेडकीव द्वारा परिष्कृत,<ref name=Losasso>Losasso, F., Gibou, F., & Fedkiw, R. 2004. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.459.1489&rep=rep1&type=pdf Simulating water and smoke with an octree data structure]. [[ACM Transactions on Graphics]]. 23(3)457–462.</ref> और हाल ही में मिन और गिबू द्वारा<ref name=MinGibou>Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. [[Journal of Computational Physics]]. 225(1)300–321.</ref> नेस्टेड क्यूब्स के पेड़ का उपयोग करता है जिसमें पत्ती नोड्स में हस्ताक्षरित दूरी मान होते हैं। पर्याप्त उपर्युक्त प्राप्त करने के लिए वर्तमान में ऑक्ट्री स्तर के समुच्चय को इंटरफ़ेस (यानी संकीर्ण बैंड) के साथ एक समान शोधन की आवश्यकता होती है। भंडारण के मामले में यह प्रतिनिधित्व कुशल है, <math>O(n^2),</math> और एक्सेस प्रश्नों के मामले में अपेक्षाकृत कुशल, <math>O(\log\, n).</math> ऑक्ट्री आँकड़े संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई आंशिक अंतर समीकरणों को हल कर सकता है जो विशिष्ट मुक्त सीमा समस्याओं से जुड़ा होता है जो स्तर समुच्चय पद्धति का उपयोग करते हैं। CASL अनुसंधान समूह<ref name=CASL>http://www1.engr.ucsb.edu/~fgibou/Research.html</ref> कम्प्यूटेशनल सामग्री, कम्प्यूटेशनल द्रव गतिकी, इलेक्ट्रोकाइनेटिक्स, छवि निर्देशित सर्जरी और नियंत्रण में काम की इस पंक्ति को विकसित किया है।


=== रन-लम्बाई एन्कोडेड ===
=== रन-लम्बाई एन्कोडेड ===
रन-लम्बाई एन्कोडिंग (आरएलई) स्तर सेट विधि, 2004 में पेश की गई,<ref name=Houston2004>Houston, B., Nielsen, M., Batty, C., Nilsson, O. & K. Museth. 2006. "Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation." ''[[ACM Transactions on Graphics]]''. 25(1).</ref> संकरे बैंड को पूर्ण सटीकता के साथ संग्रहीत करते समय संकीर्ण बैंड से दूर क्षेत्रों को केवल उनके संकेत प्रतिनिधित्व के लिए संपीड़ित करने के लिए RLE योजना लागू करता है। संकीर्ण बैंड का अनुक्रमिक ट्रैवर्सल इष्टतम है और ऑक्ट्री स्तर सेट पर भंडारण दक्षता में और सुधार हुआ है। एक त्वरण लुकअप तालिका के अतिरिक्त तेजी के लिए अनुमति देता है <math>O(\log r)</math> रैंडम एक्सेस, जहां आर प्रति क्रॉस सेक्शन रन की संख्या है। आरएलई योजना को एक आयामी पुनरावर्ती फैशन में लागू करके अतिरिक्त दक्षता प्राप्त की जाती है, नीलसन और मुसेथ के समान डीटी-ग्रिड द्वारा पेश की गई एक तकनीक।<ref name=Nielsen>Nielsen, M. B. & Museth K. 2006. "Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets." ''[[Journal of Scientific Computing]]''. 26(1) 1–39.</ref>
रन-लम्बाई एन्कोडिंग (आरएलई) स्तर समुच्चय विधि, 2004 में पेश की गई,<ref name=Houston2004>Houston, B., Nielsen, M., Batty, C., Nilsson, O. & K. Museth. 2006. "Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation." ''[[ACM Transactions on Graphics]]''. 25(1).</ref> संकरे बैंड को पूर्ण सटीकता के साथ संग्रहीत करते समय संकीर्ण बैंड से दूर क्षेत्रों को केवल उनके संकेत प्रतिनिधित्व के लिए संपीड़ित करने के लिए RLE योजना लागू करता है। संकीर्ण बैंड का अनुक्रमिक ट्रैवर्सल इष्टतम है और ऑक्ट्री स्तर समुच्चय पर भंडारण दक्षता में और सुधार हुआ है। एक त्वरण लुकअप तालिका का जोड़ तेजी से <math>O(\log r)</math> रैंडम एक्सेस की अनुमति देता है, जहां r प्रति क्रॉस सेक्शन रन की संख्या है। आरएलई योजना को एक आयामी पुनरावर्ती फैशन में लागू करके अतिरिक्त दक्षता प्राप्त की जाती है,नीलसन एंड मुसेथ के समान डीटी-ग्रिड द्वारा शुरू की गई एक तकनीक है।<ref name=Nielsen>Nielsen, M. B. & Museth K. 2006. "Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets." ''[[Journal of Scientific Computing]]''. 26(1) 1–39.</ref>




=== हैश टेबल स्थानीय स्तर सेट ===
=== हैश तालिका स्थानीय स्तर समुच्चय ===
हैश टेबल लोकल लेवल सेट मेथड, 2011 में आईयुरेक्ली और ब्रीन द्वारा पेश किया गया <ref name=Eyiyurekli>Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.</ref> और 2012 में ब्रून, गुइटेट और गिबू द्वारा विस्तारित किया गया,<ref name=BrunGuittetGibou>Brun, E., Guittet, A. & Gibou, F. 2012. "A local level-set method using a hash table data structure." ''[[Journal of Computational Physics]]''. 231(6)2528-2536.</ref> इंटरफ़ेस के चारों ओर एक बैंड में केवल स्तर सेट डेटा की गणना करता है, जैसा कि नैरो बैंड लेवल-सेट विधि में है, लेकिन डेटा को केवल उसी बैंड में संग्रहीत करता है। एक हैश तालिका डेटा संरचना का उपयोग किया जाता है, जो प्रदान करता है <math>O(1)</math> डेटा तक पहुंच। हालांकि, ब्रून एट अल। निष्कर्ष निकालते हैं कि उनकी विधि, लागू करने में आसान होने के बावजूद, क्वाडट्री कार्यान्वयन से भी बदतर प्रदर्शन करती है। वे पाते हैं {{blockquote|as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms.}} खराब दक्षता के तीन मुख्य कारण सूचीबद्ध हैं:
हैश तालिका स्थानीय स्तर सेट विधि, 2011 में आईयुरेक्ली और ब्रीन द्वारा पेश किया गया <ref name=Eyiyurekli>Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.</ref> और 2012 में ब्रून, गुइटेट और गिबू द्वारा विस्तारित किया गया,<ref name=BrunGuittetGibou>Brun, E., Guittet, A. & Gibou, F. 2012. "A local level-set method using a hash table data structure." ''[[Journal of Computational Physics]]''. 231(6)2528-2536.</ref> इंटरफ़ेस के चारों ओर एक बैंड में केवल स्तर सेट डेटा की गणना करता है, जैसा कि बैंड लेवल-सेट विधि में है, लेकिन डेटा को केवल उसी बैंड में संग्रहीत करता है। एक हैश तालिका डेटा संरचना का उपयोग किया जाता है, जो अकड़े  <math>O(1)</math> पहुंच तक प्रदान करता है। चूंकि, ब्रून एट अल निष्कर्ष निकालते हैं कि उनकी विधि, लागू करने में आसान होने के बावजूद, क्वाडट्री कार्यान्वयन से भी बदतर प्रदर्शन करती है। {{blockquote|as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms.}} खराब दक्षता के तीन मुख्य कारण सूचीबद्ध हैं:
# सटीक परिणाम प्राप्त करने के लिए, इंटरफ़ेस के करीब एक बड़े बैंड की आवश्यकता होती है, जो इंटरफ़ेस से दूर ग्रिड नोड्स की अनुपस्थिति का प्रतिकार करता है;
# सटीक परिणाम प्राप्त करने के लिए, इंटरफ़ेस के करीब एक बड़े बैंड की आवश्यकता होती है, जो इंटरफ़ेस से दूर ग्रिड नोड्स की अनुपस्थिति का प्रतिकार करता है;
# स्थानीय ग्रिड के बाहरी किनारों पर एक्सट्रपलेशन प्रक्रियाओं से प्रदर्शन बिगड़ जाता है और
# प्रदर्शन स्थानीय ग्रिड के बाहरी किनारों पर एक्सट्रपलेशन प्रक्रियाओं द्वारा बिगड़ जाते हैं
# बैंड की चौड़ाई समय कदम को सीमित करती है और विधि को धीमा कर देती है।
# बैंड की चौड़ाई समय कदम को सीमित करती है और विधि को धीमा कर देती है।


=== बिंदु आधारित ===
=== बिंदु आधारित ===
{{Expand section|date=December 2009}}
{{Expand section|date=December 2009}}
2005 में कॉर्बेट <ref name=Corbett>Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." [[University of British Columbia]], [[Canada]].</ref> पॉइंट-बेस्ड लेवल सेट मेथड पेश किया। स्तर सेट के एक समान नमूने का उपयोग करने के बजाय, निरंतर स्तर सेट फ़ंक्शन को असंगठित बिंदु नमूनों के सेट से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।
2005 में कॉर्बेट <ref name=Corbett>Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." [[University of British Columbia]], [[Canada]].</ref> पॉइंट-बेस्ड लेवल समुच्चय मेथड पेश किया। स्तर समुच्चय के एक समान नमूने का उपयोग करने के बजाय, निरंतर स्तर समुच्चय फ़ंक्शन को असंगठित बिंदु नमूनों के समुच्चय से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।




Revision as of 21:17, 2 December 2022

कंप्यूटर विज्ञान में एक स्तर समुच्चय आँकड़े संरचना को अलग-अलग नमूने (सांख्यिकी) वाले गतिशील स्तर समुच्चय कार्यों का प्रतिनिधित्व करने के लिए बनाया गया है।

आँकड़े संरचना के इस रूप का एक सामान्य उपयोग कुशल इमेज रेंडरिंग (कंप्यूटर ग्राफिक्स) में है। अंतर्निहित विधि एक दूरी परिवर्तन का निर्माण करती है जो सीमा से फैली हुई है, और इस क्षेत्र में सीमा की गति को हल करने के लिए प्रयोग किया जा सकता है।

कालानुक्रमिक घटनाक्रम

शक्तिशाली स्तर-समुच्चय विधि स्टेनली ओशर और जेम्स सेथियन 1988 के कारण है।[1] चूंकि, मूल्यों के घने डी-आयामी सरणी आँकड़े संरचना के माध्यम से सीधा कार्यान्वयन , जहाँ समय और भंडारण जटिलता दोनों में परिणाम देता है, डोमेन के स्थानिक विस्तार का प्रतिच्छेद अनुभागीय विश्लेषण है और डोमेन के स्थानिक आयामों की संख्या है।

संकीर्ण बैंड

1995 में एडालस्टीनसन और सेथियन द्वारा संकीर्ण बैंड स्तर समुच्चय विधि की शुरूआत की थी[2] अधिकांश संगणनाओं को इंटरफ़ेस के आसपास के सक्रिय स्वरों के एक पतले बैंड तक सीमित कर दिया, इस प्रकार तीन आयामों में समय की जटिलता को तक कम कर दिया जाता है। सक्रिय स्वरों की सूची को फिर से बनाने के लिए नैरोबैंड संरचना के आवधिक अद्यतन की आवश्यकता थी, जिसके लिए एक ऑपरेशन की आवश्यक थी जिसमें पूरे वॉल्यूम पर वोक्सल्स एक्सेस किए गए थे। इस नैरोबैंड योजना के लिए भंडारण जटिलता अभी भी थीसंकीर्ण बैंड डोमेन एज पर डिफरेंशियल कंस्ट्रक्शन को समाधान को स्थिर करने के लिए सावधानीपूर्वक प्रक्षेप और डोमेन परिवर्तन योजनाओं की आवश्यकता होती है।[3]


विरल क्षेत्र

यह समय की जटिलता को 1998 में व्हिटेकर द्वारा पेश किए गए अनुमानित "स्पार्स फील्ड" लेवल सेट पद्धति में समाप्त कर दिया गया था।[4] इंटरफ़ेस के चारों ओर सक्रिय स्वरों को ट्रैक करने के लिए विरल फ़ील्ड स्तर समुच्चय विधि लिंक्ड सूचियों के एक समुच्चय को नियोजित करती है। यह किसी भी महत्वपूर्ण ओवरहेड के बिना आवश्यकतानुसार सक्रिय क्षेत्र के वृद्धिशील विस्तार की अनुमति देता है। जबकि लगातार समय में कुशल, भंडारण स्थान अभी भी विरल क्षेत्र स्तर समुच्चय विधि द्वारा आवश्यक है।[5] कार्यान्वयन के लिए विवरण देखे।

विरल ब्लॉक ग्रिड

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

अष्टक

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

रन-लम्बाई एन्कोडेड

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


हैश तालिका स्थानीय स्तर समुच्चय

हैश तालिका स्थानीय स्तर सेट विधि, 2011 में आईयुरेक्ली और ब्रीन द्वारा पेश किया गया [13] और 2012 में ब्रून, गुइटेट और गिबू द्वारा विस्तारित किया गया,[14] इंटरफ़ेस के चारों ओर एक बैंड में केवल स्तर सेट डेटा की गणना करता है, जैसा कि बैंड लेवल-सेट विधि में है, लेकिन डेटा को केवल उसी बैंड में संग्रहीत करता है। एक हैश तालिका डेटा संरचना का उपयोग किया जाता है, जो अकड़े पहुंच तक प्रदान करता है। चूंकि, ब्रून एट अल निष्कर्ष निकालते हैं कि उनकी विधि, लागू करने में आसान होने के बावजूद, क्वाडट्री कार्यान्वयन से भी बदतर प्रदर्शन करती है।

as it is, [...] a quadtree data structure seems more adapted than the hash table data structure for level-set algorithms.

खराब दक्षता के तीन मुख्य कारण सूचीबद्ध हैं:

  1. सटीक परिणाम प्राप्त करने के लिए, इंटरफ़ेस के करीब एक बड़े बैंड की आवश्यकता होती है, जो इंटरफ़ेस से दूर ग्रिड नोड्स की अनुपस्थिति का प्रतिकार करता है;
  2. प्रदर्शन स्थानीय ग्रिड के बाहरी किनारों पर एक्सट्रपलेशन प्रक्रियाओं द्वारा बिगड़ जाते हैं
  3. बैंड की चौड़ाई समय कदम को सीमित करती है और विधि को धीमा कर देती है।

बिंदु आधारित

2005 में कॉर्बेट [15] पॉइंट-बेस्ड लेवल समुच्चय मेथड पेश किया। स्तर समुच्चय के एक समान नमूने का उपयोग करने के बजाय, निरंतर स्तर समुच्चय फ़ंक्शन को असंगठित बिंदु नमूनों के समुच्चय से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।


इस पेज में लापता आंतरिक लिंक की सूची

  • लेवल सेट
  • प्रतिपादन (कंप्यूटर ग्राफिक्स)
  • वॉक्सेल
  • रन-लेंथ एन्कोडिंग
  • कम से कम वर्ग चल रहा है

संदर्भ

  1. ↑ Osher, S. & Sethian, J. A. 1988. "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations". Journal of Computation Physics 79:12–49.
  2. ↑ Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." Journal of Computational Physics. 118(2)269–277.
  3. ↑ Adalsteinsson, D; Sethian, J (1994). "इंटरफेस के प्रचार के लिए एक तेज़ स्तर सेट विधि". Journal of Computational Physics. 118 (2): 269. Bibcode:1995JCoPh.118..269A. CiteSeerX 10.1.1.46.1716. doi:10.1006/jcph.1995.1098.
  4. ↑ Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." International Journal of Computer Vision. 29(3)203–231.
  5. ↑ S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/>
  6. ↑ Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." Stanford University, Stanford, California.
  7. ↑ Strain, J. 1999. "Tree methods for moving interfaces." Journal of Computational Physics. 151(2)616–648.
  8. ↑ Losasso, F., Gibou, F., & Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Transactions on Graphics. 23(3)457–462.
  9. ↑ Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. Journal of Computational Physics. 225(1)300–321.
  10. ↑ http://www1.engr.ucsb.edu/~fgibou/Research.html
  11. ↑ Houston, B., Nielsen, M., Batty, C., Nilsson, O. & K. Museth. 2006. "Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation." ACM Transactions on Graphics. 25(1).
  12. ↑ Nielsen, M. B. & Museth K. 2006. "Dynamic Tubular Grid: An efficient data structure and algorithms for high resolution level sets." Journal of Scientific Computing. 26(1) 1–39.
  13. ↑ Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.
  14. ↑ Brun, E., Guittet, A. & Gibou, F. 2012. "A local level-set method using a hash table data structure." Journal of Computational Physics. 231(6)2528-2536.
  15. ↑ Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." University of British Columbia, Canada.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्तर_समुच्चय_(डेटा_संरचनाएं)&oldid=41440’