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

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

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

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

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

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

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

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

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

Main article: घास की आग को रूपांतरित करना

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

अधिकतम डिस्क (या बॉल) के केंद्र

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

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

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

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

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

दूरी फलन की लकीरें

कंकाल की कई परिभाषाएँ दूरी फलन की अवधारणा का उपयोग करती हैं, जो एक ऐसा फलन है जो प्रत्येक बिंदु x के लिए आकृति A के अंदर 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)