टोपोलॉजिकल कंकाल

एक आकृति और उसका कंकाल, जिसकी गणना टोपोलॉजी-प्रिजर्विंग थिनिंग एल्गोरिथम के साथ की जाती है।

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

तकनीकी साहित्य में स्केलेटन की कई अलग-अलग गणितीय परिभाषाएँ हैं, और उनकी गणना के लिए कई अलग-अलग एल्गोरिदम हैं। कंकाल के विभिन्न प्रकार भी पाए जा सकते हैं, जिनमें सीधे कंकाल, रूपात्मक कंकाल आदि शामिल हैं।

तकनीकी साहित्य में, कुछ लेखकों द्वारा कंकाल और औसत दर्जे की धुरी की अवधारणाओं का परस्पर उपयोग किया जाता है, जबकि कुछ अन्य लेखक उन्हें संबंधित मानें, लेकिन समान नहीं। इसी तरह, कंकालकरण और पतलापन (आकृति विज्ञान) की अवधारणाओं को भी कुछ लोगों द्वारा समान माना जाता है,और दूसरों के द्वारा नहीं।

कंप्यूटर दृष्टि, छवि विश्लेषण, पैटर्न पहचान और ऑप्टिकल चरित्र पहचान, फिंगरप्रिंट पहचान, दृश्य निरीक्षण या छवि संपीड़न जैसे उद्देश्यों के लिए स्केलेटन का व्यापक रूप से उपयोग किया जाता है। जीवन विज्ञान के भीतर प्रोटीन की तह की विशेषता के लिए कंकालों का व्यापक उपयोग पाया गया और विभिन्न जैविक पैमानों पर पादप आकृति विज्ञान।

गणितीय परिभाषाएँ

तकनीकी साहित्य में कंकालों की कई अलग-अलग गणितीय परिभाषाएँ हैं; उनमें से अधिकांश कॉन्टिनम (टोपोलॉजी) में समान परिणाम देते हैं, लेकिन आमतौर पर असतत स्थानों में अलग-अलग परिणाम देते हैं।

अग्नि प्रसार मॉडल के शमन बिंदु

Main article: Grassfire transform

अपने सेमिनल पेपर में, हैरी ब्लम (वैज्ञानिक) बेडफ़ोर्ड, मैसाचुसेट्स में हंसकॉम एयर फोर्स बेस में वायु सेना कैम्ब्रिज अनुसंधान प्रयोगशालाओं के एक घास के मैदान पर अग्नि प्रसार के एक सहज मॉडल का उपयोग करते हुए, एक आकृति के कंकाल की गणना के लिए एक औसत दर्जे का अक्ष परिभाषित किया गया है, जहां क्षेत्र का रूप है आकार दिया। यदि कोई उस घास के मैदान की सीमा पर सभी बिंदुओं पर एक साथ आग लगाता है, तो कंकाल विकट: शमन बिंदुओं का समूह होता है, यानी वे बिंदु जहां दो या दो से अधिक तरंगाग्र मिलते हैं। यह सहज वर्णन कई अधिक सटीक परिभाषाओं के लिए प्रारंभिक बिंदु है।

अधिकतम डिस्क (या गेंदों) के केंद्र

एक डिस्क (गणित) (या गेंद (गणित)) B को समुच्चय A में अधिकतम कहा जाता है यदि

• $B\subseteq A$, और
• यदि अन्य डिस्क D में B है, तो $D\not \subseteq A$.

आकार ए के कंकाल को परिभाषित करने का एक तरीका ए में सभी अधिकतम डिस्क के केंद्रों के सेट के रूप में है।

द्वि-स्पर्शी वृत्तों के केंद्र

आकृति A के कंकाल को डिस्क के केंद्रों के सेट के रूप में भी परिभाषित किया जा सकता है जो A की सीमा को दो या दो से अधिक स्थानों पर स्पर्श करता है।यह परिभाषा आश्वस्त करती है कि कंकाल बिंदु आकृति सीमा से समान दूरी पर हैं और गणितीय रूप से ब्लम के औसत दर्जे के अक्ष परिवर्तन के समतुल्य हैं।

दूरी समारोह की लकीरें

स्केलेटन की कई परिभाषाएँ दूरी फलन की अवधारणा का उपयोग करती हैं, जो एक ऐसा फलन है जो आकृति A के भीतर प्रत्येक बिंदु x के लिए A की सीमा पर निकटतम बिंदु तक की दूरी लौटाता है। दूरी फलन का उपयोग करना बहुत आकर्षक है क्योंकि इसकी गणना है अपेक्षाकृत तेज़।

दूरी समारोह का उपयोग कर कंकाल की परिभाषाओं में से एक दूरी समारोह की चोटी के रूप में है।साहित्य में एक आम गलत बयान है कि कंकाल में ऐसे बिंदु होते हैं जो दूरी परिवर्तन में स्थानीय रूप से अधिकतम होते हैं। यह केवल मामला नहीं है, क्योंकि दूरी परिवर्तन और परिणामी कंकाल की सरसरी तुलना भी दिखाई देगी। रिज की ऊंचाई अलग-अलग हो सकती है, इसलिए रिज पर एक बिंदु रिज पर उसके निकटतम पड़ोसी से कम हो सकता है। इस प्रकार यह एक स्थानीय अधिकतम नहीं है, भले ही यह रिज से संबंधित हो। हालाँकि, इसकी जमीनी दूरी की तुलना में यह लंबवत रूप से कम दूर है। अन्यथा यह ढलान का हिस्सा होगा।

अन्य परिभाषाएं

• डिस्टेंस फंक्शन में बिना अपस्ट्रीम सेगमेंट वाले पॉइंट। एक बिंदु x का अपस्ट्रीम x से शुरू होने वाला खंड है जो अधिकतम ढाल पथ का अनुसरण करता है।
• बिंदु जहां दूरी समारोह की ढाल 1 से भिन्न होती है (या, समकक्ष, अच्छी तरह से परिभाषित नहीं)
• लाइनों का सबसे छोटा संभव सेट जो टोपोलॉजी को संरक्षित करता है और सीमाओं के समतुल्य है

कंकालकरण एल्गोरिदम

डिजिटल छवियों में आकृतियों के साथ-साथ निरंतर कार्य (सेट सिद्धांत) के लिए कंकाल की गणना के लिए कई अलग-अलग एल्गोरिदम हैं।

• गणितीय आकृति विज्ञान का उपयोग करना # मूल संचालक (रूपात्मक कंकाल देखें)
• आकार आधारित छंटाई (आकृति विज्ञान) के साथ रूपात्मक संचालकों का पूरक
• सीमा खंडों से दूरियों के चौराहों का उपयोग करना
• वक्र विकास का उपयोग करना
• स्तर सेट का उपयोग करना* दूरी समारोह पर रिज अंक ढूँढना* अभिसरण तक, टोपोलॉजी को बदले बिना, आकार को छीलना
• झांग-सुएन थिनिंग एल्गोरिथम

स्केलेटनाइजेशन एल्गोरिदम कभी-कभी आउटपुट कंकाल पर अवांछित शाखाएं बना सकते हैं। इन शाखाओं को हटाने के लिए अक्सर प्रूनिंग (आकृति विज्ञान) का उपयोग किया जाता है।

यह भी देखें

• मध्य अक्ष
• सीधा कंकाल
• बीटा कंकाल|β-कंकाल
• घास का रूपांतरण
• कंप्यूटर फ़ॉन्ट#स्ट्रोक-आधारित फ़ॉन्ट|स्ट्रोक-आधारित फ़ॉन्ट

संदर्भ

• Abeysinghe, Sasakthi; Baker, Matthew; Chiu, Wah; Ju, Tao (2008), "Segmentation-free skeletonization of grayscale volumes for shape understanding", IEEE Int. Conf. Shape Modeling and Applications (SMI 2008) (PDF), pp. 63–71, doi:10.1109/SMI.2008.4547951, ISBN 978-1-4244-2260-9, S2CID 15148296.
• Abeysinghe, Sasakthi; Ju, Tao; Baker, Matthew; Chiu, Wah (2008), "Shape modeling and matching in identifying 3D protein structures" (PDF), Computer-Aided Design, Elsevier, 40 (6): 708–720, doi:10.1016/j.cad.2008.01.013
• Bai, Xiang; Longin, Latecki; Wenyu, Liu (2007), "Skeleton pruning by contour partitioning with discrete curve evolution" (PDF), IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (3): 449–462, doi:10.1109/TPAMI.2007.59, PMID 17224615, S2CID 14965041.
• Blum, Harry (1967), "A Transformation for Extracting New Descriptors of Shape", in Wathen-Dunn, W. (ed.), Models for the Perception of Speech and Visual Form (PDF), Cambridge, Massachusetts: MIT Press, pp. 362–380.
• Bucksch, Alexander (2014), "A practical introduction to skeletons for the plant sciences", Applications in Plant Sciences, 2 (8): 1400005, doi:10.3732/apps.1400005, PMC 4141713, PMID 25202647.
• Cychosz, Joseph (1994), Graphics gems IV, San Diego, CA, USA: Academic Press Professional, Inc., pp. 465–473, ISBN 0-12-336155-9.
• Dougherty, Edward R. (1992), An Introduction to Morphological Image Processing, ISBN 0-8194-0845-X.
• Golland, Polina; Grimson, W. Eric L. (2000), "Fixed topology skeletons" (PDF), 2000 Conference on Computer Vision and Pattern Recognition (CVPR 2000), 13-15 June 2000, Hilton Head, SC, USA, IEEE Computer Society, pp. 1010–1017, doi:10.1109/CVPR.2000.855792, S2CID 9916140
• Gonzales, Rafael C.; Woods, Richard E. (2001), Digital Image Processing, ISBN 0-201-18075-8.
• Jain, Anil K. (1989), Fundamentals of Digital Image Processing, Bibcode:1989fdip.book.....J, ISBN 0-13-336165-9.
• Jain, Ramesh; Kasturi, Rangachar; Schunck, Brian G. (1995), Machine Vision, ISBN 0-07-032018-7.
• Kimmel, Ron; Shaked, Doron; Kiryati, Nahum; Bruckstein, Alfred M. (1995), "Skeletonization via distance maps and level sets" (PDF), Computer Vision and Image Understanding, 62 (3): 382–391, doi:10.1006/cviu.1995.1062
• Ogniewicz, R. L. (1995), "Automatic Medial Axis Pruning Based on Characteristics of the Skeleton-Space", in Dori, D.; Bruckstein, A. (eds.), Shape, Structure and Pattern Recognition, ISBN 981-02-2239-4.
• Petrou, Maria; García Sevilla, Pedro (2006), Image Processing Dealing with Texture, ISBN 978-0-470-02628-1.
• Serra, Jean (1982), Image Analysis and Mathematical Morphology, ISBN 0-12-637240-3.
• Sethian, J. A. (1999), Level Set Methods and Fast Marching Methods, ISBN 0-521-64557-3.
• Tannenbaum, Allen (1996), "Three snippets of curve evolution theory in computer vision", Mathematical and Computer Modelling, 24 (5): 103–118, doi:10.1016/0895-7177(96)00117-3.

ओपन सोर्स सॉफ्टवेयर

• ITK (सी++)
• Skeletonize3D (जावा)
• ग्राफिक्स रत्न चतुर्थ (सी)
• EVG-Thin (C++)
• न्यूरॉनस्टूडियो

बाहरी संबंध

• Skeletonization/Medial Axis Transform
• Skeletons of a region
• Skeletons in Digital image processing (pdf)
• Comparison of 15 line thinning algorithms
• Skeletonization using Level Set Methods
• Curve Skeletons
• Skeletons from laser scanned point clouds (Homepage)