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

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

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

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

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

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

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

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

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

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)