स्तर समुच्चय (डेटा संरचनाएं): Difference between revisions
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Cleanup bare URLs|date=August 2022}} | {{Cleanup bare URLs|date=August 2022}} | ||
[[कंप्यूटर विज्ञान]] में एक स्तर समुच्चय [[डेटा संरचना|आँकड़े संरचना]] को अलग-अलग [[नमूनाकरण (सांख्यिकी)|नमूने (सांख्यिकी)]] वाले गतिशील स्तर समुच्चय कार्यों का प्रतिनिधित्व करने के लिए बनाया गया है। | [[कंप्यूटर विज्ञान|संगणक विज्ञान]] में एक स्तर समुच्चय [[डेटा संरचना|आँकड़े संरचना]] को अलग-अलग [[नमूनाकरण (सांख्यिकी)|नमूने (सांख्यिकी)]] वाले गतिशील स्तर समुच्चय कार्यों का प्रतिनिधित्व करने के लिए बनाया गया है। | ||
आँकड़े संरचना के इस रूप का एक सामान्य प्रयोग कुशल छवि प्रतिपादन ( | आँकड़े संरचना के इस रूप का एक सामान्य प्रयोग कुशल छवि प्रतिपादन (संगणक ग्राफिक्स) में है। आधारभूत विधि एक [[दूरी परिवर्तन]] का निर्माण करती है जो सीमा से फैली हुई है, और इस क्षेत्र में सीमा की गति को हल करने के लिए प्रयोग किया जा सकता है। | ||
== कालानुक्रमिक घटनाक्रम == | == कालानुक्रमिक घटनाक्रम == | ||
1988 में [[स्टेनली ओशर]] और [[जेम्स सेथियन]] ने शक्तिशाली [[स्तर-सेट विधि|स्तर-समुच्चय विधि]] | 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> डोमेन के स्थानिक आयामों की संख्या है। | ||
| Line 20: | Line 20: | ||
=== [[अष्टक]] === | === [[अष्टक]] === | ||
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> ऑक्ट्री आँकड़े संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई आंशिक अंतर समीकरणों को हल कर सकता | 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> ऑक्ट्री आँकड़े संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई विशिष्ट मुक्त सीमा समस्याओं से जुड़े आंशिक अंतर समीकरणों को हल कर सकता है जो स्तर सेट विधि का उपयोग करते हैं । सीएएसएल अनुसंधान समूह<ref name=CASL>http://www1.engr.ucsb.edu/~fgibou/Research.html</ref> संगणनात्मक सामग्री, संगणनात्मक द्रव गतिकी, विद्युत् बलगति विज्ञान, छवि निर्देशित सर्जरी और नियंत्रण में काम की इस पंक्ति को विकसित किया है। | ||
=== रन-लम्बाई एन्कोडेड === | === रन-लम्बाई एन्कोडेड === | ||
| Line 40: | Line 40: | ||
*स्तर सेट | *स्तर सेट | ||
*प्रतिपादन ( | *प्रतिपादन (संगणक ग्राफिक्स) | ||
*वॉक्सेल | *वॉक्सेल | ||
*रन-लेंथ एन्कोडिंग | *रन-लेंथ एन्कोडिंग | ||
| Line 47: | Line 47: | ||
<references /> | <references /> | ||
{{DEFAULTSORT:Level Set (Data Structures)}} | {{DEFAULTSORT:Level Set (Data Structures)}} | ||
[[Category:All articles covered by WikiProject Wikify|Level Set (Data Structures)]] | |||
[[Category: | [[Category:All articles to be expanded|Level Set (Data Structures)]] | ||
[[Category:Created On 24/11/2022]] | [[Category:All articles with bare URLs for citations|Level Set (Data Structures)]] | ||
[[Category:Articles covered by WikiProject Wikify from August 2022|Level Set (Data Structures)]] | |||
[[Category:Articles needing cleanup from August 2022|Level Set (Data Structures)]] | |||
[[Category:Articles to be expanded from December 2009|Level Set (Data Structures)]] | |||
[[Category:Articles using small message boxes|Level Set (Data Structures)]] | |||
[[Category:Articles with bare URLs for citations from August 2022|Level Set (Data Structures)]] | |||
[[Category:Articles with invalid date parameter in template|Level Set (Data Structures)]] | |||
[[Category:Created On 24/11/2022|Level Set (Data Structures)]] | |||
[[Category:Machine Translated Page|Level Set (Data Structures)]] | |||
[[Category:इमेज प्रोसेसिंग|Level Set (Data Structures)]] | |||
[[Category:कंप्यूटर ग्राफिक्स डेटा संरचनाएं|Level Set (Data Structures)]] | |||
[[Category:संख्यात्मक विश्लेषण|Level Set (Data Structures)]] | |||
Latest revision as of 09:37, 13 December 2022
 | This article uses bare URLs, which are uninformative and vulnerable to link rot. (August 2022) (Learn how and when to remove this template message) |
संगणक विज्ञान में एक स्तर समुच्चय आँकड़े संरचना को अलग-अलग नमूने (सांख्यिकी) वाले गतिशील स्तर समुच्चय कार्यों का प्रतिनिधित्व करने के लिए बनाया गया है।
आँकड़े संरचना के इस रूप का एक सामान्य प्रयोग कुशल छवि प्रतिपादन (संगणक ग्राफिक्स) में है। आधारभूत विधि एक दूरी परिवर्तन का निर्माण करती है जो सीमा से फैली हुई है, और इस क्षेत्र में सीमा की गति को हल करने के लिए प्रयोग किया जा सकता है।
कालानुक्रमिक घटनाक्रम
1988 में स्टेनली ओशर और जेम्स सेथियन ने शक्तिशाली स्तर-समुच्चय विधि प्रारंभ की थी।[1] चूंकि, मानों के घने डी-आयामी सरणी आँकड़े संरचना के माध्यम से सीधा कार्यान्वयन , जहाँ समय और भंडारण जटिलता दोनों में परिणाम देता है, डोमेन के स्थानिक विस्तार का प्रतिच्छेद अनुभागीय विश्लेषण है और डोमेन के स्थानिक आयामों की संख्या है।
संकीर्ण बैंड
1995 में एडालस्टीनसन और सेथियन द्वारा संकीर्ण बैंड स्तर समुच्चय विधि की प्रारंभ की थी[2] अधिकांश संगणनाओं को इंटरफ़ेस के नजदीक के सक्रिय स्वरों के एक पतले बैंड तक सीमित कर दिया, इस प्रकार तीन आयामों में समय की जटिलता को तक कम कर दिया जाता है। सक्रिय स्वरों की सूची को फिर से बनाने के लिए संकीर्ण बैंड संरचना के आवधिक अद्यतन की आवश्यकता थी, जिसके लिए एक ऑपरेशन की आवश्यक थी जो पूरी मात्रा में स्वरों तक पहुँचा गया था इस संकीर्ण बैंड योजना के लिए संग्रहण जटिलता अभी भी थी संकीर्ण बैंड डोमेन पर किनारा पर वैशिष्ट्य निर्माण के लिये समाधान को स्थिर करने के लिए सावधानीपूर्वक प्रक्षेप और डोमेन परिवर्तन योजनाओं की आवश्यकता होती है।[3]
विरल क्षेत्र
यह समय की जटिलता को 1998 में व्हिटेकर द्वारा प्रस्तुत किए गए अनुमानित "विरल क्षेत्र" स्तर सेट पद्धति में समाप्त कर दिया गया था।[4] इंटरफ़ेस के चारों ओर सक्रिय स्वरों को ट्रैक करने के लिए विरल क्षेत्र स्तर समुच्चय विधि लिंक्ड सूचियों के एक समुच्चय को नियोजित करती है। यह किसी भी महत्वपूर्ण ओवरहेड के बिना आवश्यकतानुसार सक्रिय क्षेत्र के वृद्धिशील विस्तार की अनुमति देता है। जबकि लगातार समय में कुशल, भंडारण स्थान अभी भी विरल क्षेत्र स्तर समुच्चय विधि द्वारा आवश्यक है।[5] कार्यान्वयन के लिए विवरण देखे।
विरल खंड जाली
2003 में ब्रिडसन द्वारा विरल खंड जाली विधि की प्रारंभ की गई थी,[6] आकार के पूरे बाउंडिंग ध्वनि को स्वर के छोटे घन खंडों में विभाजित करता है। आकार का एक मोटी जाली फिर पॉइंटर्स को केवल उन खंडो में संग्रहीत करता है जो स्तर समुच्चय के संकीर्ण बैंड को पार करते हैं। खंड आवंटन और डीलोकेशन घटित होते हैं क्योंकि सतह विकृतियों को समायोजित करने के लिए फैलती है। इस पद्धति में एक उप-इष्टतम भंडारण जटिलता है , लेकिन सघन जालियो में निहित निरंतर समय पहुंच को बरकरार रखता है।
अष्टक
1999 में स्ट्रेन द्वारा प्रारंभ की गई ऑक्ट्री स्तर समुच्चय विधि[7] और लोसासो, गिबू और फेडकीव द्वारा परिष्कृत,[8] और हाल ही में मिन और गिबू द्वारा[9] स्थिर घनक्षेत्र के पेड़ का प्रयोग करता है जिसमें पत्ती नोड्स में हस्ताक्षरित दूरी मान होते हैं। पर्याप्त उपर्युक्त प्राप्त करने के लिए वर्तमान में ऑक्ट्री स्तर के समुच्चय को इंटरफ़ेस (अर्थात् संकीर्ण बैंड) के साथ एक समान शोधन की आवश्यकता होती है। भंडारण के स्थितियो में यह प्रतिनिधित्व कुशल है, और सक्रिय प्रश्नों के स्थितियो में अपेक्षाकृत कुशल, ऑक्ट्री आँकड़े संरचनाओं पर स्तर विधि का एक लाभ यह है कि कोई विशिष्ट मुक्त सीमा समस्याओं से जुड़े आंशिक अंतर समीकरणों को हल कर सकता है जो स्तर सेट विधि का उपयोग करते हैं । सीएएसएल अनुसंधान समूह[10] संगणनात्मक सामग्री, संगणनात्मक द्रव गतिकी, विद्युत् बलगति विज्ञान, छवि निर्देशित सर्जरी और नियंत्रण में काम की इस पंक्ति को विकसित किया है।
रन-लम्बाई एन्कोडेड
रन-लम्बाई एन्कोडिंग (आरएलई) स्तर समुच्चय विधि, 2004 में प्रस्तुत की गई,[11] संकरे बैंड को पूर्ण सटीकता के साथ संग्रहीत करते समय संकीर्ण बैंड से दूर क्षेत्रों को केवल उनके संकेत प्रतिनिधित्व के लिए संपीड़ित करने के लिए RLE योजना लागू करता है। संकीर्ण बैंड का अनुक्रमिक ट्रैवर्सल इष्टतम है और ऑक्ट्री स्तर समुच्चय पर भंडारण दक्षता में और सुधार हुआ है। एक त्वरण लुकअप तालिका का जोड़ तेजी से रैंडम सक्रिय की अनुमति देता है, जहां r प्रति क्रॉस सेक्शन रन की संख्या है। आरएलई योजना को एक आयामी पुनरावर्ती फैशन में लागू करके अतिरिक्त दक्षता प्राप्त की जाती है,नीलसन एंड मुसेथ के समान डीटी-ग्रिड द्वारा प्रारंभ की गई एक तकनीक है।[12]
हैश तालिका स्थानीय स्तर समुच्चय
हैश तालिका स्थानीय स्तर सेट विधि, 2011 में आईयुरेक्ली और ब्रीन द्वारा पेश किया गया [13] और 2012 में ब्रून, गुइटेट और गिबू द्वारा विस्तारित किया गया,[14] इंटरफ़ेस के चारों ओर एक बैंड में केवल स्तर सेट डेटा की गणना करता है, जैसा कि बैंड लेवल-सेट विधि में है, लेकिन डेटा को केवल उसी बैंड में संग्रहीत करता है। एक हैश तालिका डेटा संरचना का उपयोग किया जाता है, जो अकड़े पहुंच तक प्रदान करता है। चूंकि, ब्रून एट अल निष्कर्ष निकालते हैं कि उनकी विधि, लागू करने में आसान होने के बावजूद, क्वाडट्री कार्यान्वयन से भी बदतर प्रदर्शन करती है।
जैसा कि है, [...] एक चतुर्भुज डेटा संरचना स्तर-सेट कलन विधि के लिए हैश तालिका डेटा संरचना से अधिक अनुकूलित लगती है।
खराब दक्षता के तीन मुख्य कारण सूचीबद्ध हैं:
- सटीक परिणाम प्राप्त करने के लिए, इंटरफ़ेस के करीब एक बड़े बैंड की आवश्यकता होती है, जो इंटरफ़ेस से दूर ग्रिड नोड्स की अनुपस्थिति का प्रतिकार करता है;
- प्रदर्शन स्थानीय ग्रिड के बाहरी किनारों पर एक्सट्रपलेशन प्रक्रियाओं द्वारा बिगड़ जाते हैं
- बैंड की चौड़ाई समय कदम को सीमित करती है और विधि को धीमा कर देती है।
बिंदु आधारित
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | This section needs expansion. You can help by adding to it. (December 2009) |
2005 में कॉर्बेट [15] पॉइंट-बेस्ड स्तर समुच्चय मेथड प्रस्तुत किया। स्तर समुच्चय के एक समान नमूने का प्रयोग करने के अतिरिक्त, निरंतर स्तर समुच्चय फ़ंक्शन को असंगठित बिंदु नमूनों के समुच्चय से कम से कम वर्गों के माध्यम से पुनर्निर्माण किया जाता है।
इस पेज में लापता आंतरिक लिंक की सूची
- स्तर सेट
- प्रतिपादन (संगणक ग्राफिक्स)
- वॉक्सेल
- रन-लेंथ एन्कोडिंग
- कम से कम वर्ग चल रहा है
संदर्भ
- ↑ 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.
- ↑ Adalsteinsson, D. & Sethian, J. A. 1995. "A fast level set method for propagating interfaces." Journal of Computational Physics. 118(2)269–277.
- ↑ 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.
- ↑ Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." International Journal of Computer Vision. 29(3)203–231.
- ↑ S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/>
- ↑ Bridson, R. 2003. "Computational aspects of dynamic surfaces (dissertation)." Stanford University, Stanford, California.
- ↑ Strain, J. 1999. "Tree methods for moving interfaces." Journal of Computational Physics. 151(2)616–648.
- ↑ Losasso, F., Gibou, F., & Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. ACM Transactions on Graphics. 23(3)457–462.
- ↑ 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.
- ↑ http://www1.engr.ucsb.edu/~fgibou/Research.html
- ↑ 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).
- ↑ 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.
- ↑ Eyiyurekli, M. & Breen, D. 2011. "Data structures for interactive high resolution level-set surface editing," Proc. Graphics Interface. pp. 95-102.
- ↑ 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.
- ↑ Corbett, R. 2005. "Point–Based Level Sets and Progress Towards Unorganised Particle Level Sets (thesis)." University of British Columbia, Canada.
