อ่าน 4 นาที
โครงกระดูกเชิงทอพอโลยี
ในการวิเคราะห์รูปทรงโครงร่าง (หรือโครงร่างเชิงโทโพโลยี ) ของรูปทรงคือโครงร่างบางๆ ของรูปทรงนั้นที่อยู่ห่างจากขอบเขตของรูปทรงเท่ากัน...
โครงกระดูกเชิงทอพอโลยี

ในการวิเคราะห์รูปทรงโครงร่าง (หรือโครงร่างเชิงโทโพโลยี ) ของรูปทรงคือโครงร่างบางๆ ของรูปทรงนั้นที่อยู่ห่างจากขอบเขตของรูปทรงเท่ากัน โครงร่างมักเน้นคุณสมบัติทางเรขาคณิตและเชิงโทโพโลยีของรูปทรง เช่นการเชื่อมต่อโทโพโลยีความยาว ทิศทางและความกว้างเมื่อรวมกับระยะห่างของจุดต่างๆ บนโครงร่างจากขอบเขตของรูปทรง โครงร่างยังสามารถใช้เป็นตัวแทนของรูปทรงได้ (เนื่องจากมีข้อมูลทั้งหมดที่จำเป็นในการสร้างรูปทรงขึ้นใหม่)
ในเอกสารทางเทคนิค โครงกระดูกมีนิยามทางคณิตศาสตร์ที่แตกต่างกันหลายแบบ และมีอัลกอริธึมมากมายสำหรับการคำนวณ นอกจากนี้ยังสามารถพบโครงกระดูกรูปแบบต่างๆ ได้หลายแบบ เช่นโครงกระดูกแบบตรงโครงกระดูกแบบสัณฐานวิทยาเป็นต้น
ในเอกสารทางเทคนิค แนวคิดของโครงกระดูกและแกนกลางถูกใช้สลับกันโดยผู้เขียนบางคน[ 1 ] [ 2 ]ในขณะที่ผู้เขียนคนอื่นๆ[ 3 ] [ 4 ] [ 5 ]ถือว่าทั้งสองอย่างมีความเกี่ยวข้องกัน แต่ไม่เหมือนกัน ในทำนองเดียวกัน แนวคิดของการสร้างโครงกระดูกและการทำให้บางลงก็ถูกมองว่าเหมือนกันโดยบางคน[ 2 ]และไม่ใช่โดยคนอื่นๆ[ 3 ]
โครงกระดูกถูกนำมาใช้กันอย่างแพร่หลายในด้านคอมพิวเตอร์วิชั่นการวิเคราะห์ภาพการจดจำรูปแบบและการประมวลผลภาพดิจิทัล เพื่อวัตถุประสงค์ ต่างๆเช่นการจดจำตัวอักษรด้วยแสงการจดจำลายนิ้วมือการตรวจสอบด้วย สายตา หรือ การ บีบอัดในสาขาวิทยาศาสตร์ชีวภาพ โครงกระดูกถูกนำมาใช้อย่างกว้างขวางเพื่อจำแนกลักษณะการพับของโปรตีน[ 6 ]และสัณฐานวิทยาของพืชในระดับชีวภาพต่างๆ[ 7 ]
นิยามทางคณิตศาสตร์
ในเอกสารทางเทคนิค โครงร่างมีนิยามทางคณิตศาสตร์ที่แตกต่างกันหลายแบบ ซึ่งส่วนใหญ่นำไปสู่ผลลัพธ์ที่คล้ายคลึงกันในปริภูมิต่อเนื่องแต่โดยทั่วไปแล้วจะให้ผลลัพธ์ที่แตกต่างกันในปริภูมิไม่ต่อเนื่อง
จุดดับไฟของแบบจำลองการลุกลามของไฟ
ในบทความสำคัญของเขาHarry Blum [ 8 ]จากห้องปฏิบัติการวิจัยเคมบริดจ์ของกองทัพอากาศที่ฐานทัพอากาศแฮนส์คอมในเบดฟอร์ด รัฐแมสซาชูเซตส์ได้กำหนดแกนกลางสำหรับการคำนวณโครงร่างของรูปร่าง โดยใช้แบบจำลองเชิงสัญชาตญาณของการแพร่กระจายของไฟบนสนามหญ้า ซึ่งสนามมีรูปร่างตามที่กำหนด หาก "จุดไฟ" ที่ทุกจุดบนขอบของสนามหญ้านั้นพร้อมกัน โครงร่างจะเป็นชุดของ จุด ดับไฟ กล่าวคือ จุดที่หน้าคลื่นสองหน้าหรือมากกว่านั้นมาบรรจบกัน คำอธิบายเชิงสัญชาตญาณนี้เป็นจุดเริ่มต้นสำหรับคำจำกัดความที่แม่นยำยิ่งขึ้นหลายประการ
จุดศูนย์กลางของแผ่นดิสก์ (หรือลูกบอล) ที่ใหญ่ที่สุด
กล่าวได้ว่าแผ่นดิสก์ (หรือลูกบอล ) B เป็น ค่าสูงสุดในเซตAถ้า
- , และ
- ถ้าแผ่นดิสก์อีกแผ่นหนึ่งDบรรจุB ไว้ ด้วยแล้ว...
วิธีหนึ่งในการกำหนดโครงร่างของรูปร่างAคือเป็นเซตของศูนย์กลางของดิสก์สูงสุดทั้งหมดใน A [ 9 ]
จุดศูนย์กลางของวงกลมสัมผัสสองเส้น
โครงร่างของรูปร่างAยังสามารถกำหนดได้ว่าเป็นเซตของจุดศูนย์กลางของแผ่นดิสก์ที่สัมผัสกับขอบเขตของAในสองตำแหน่งขึ้นไป[ 10 ]คำจำกัดความนี้รับประกันว่าจุดโครงร่างอยู่ห่างจากขอบเขตของรูปร่างเท่ากันและเทียบเท่าทางคณิตศาสตร์กับการแปลงแกนกลางของ Blum
สันของฟังก์ชันระยะทาง
คำจำกัดความของโครงร่างจำนวนมากใช้แนวคิดของฟังก์ชันระยะทางซึ่งเป็นฟังก์ชันที่ส่งคืนระยะทางของแต่ละจุดxภายในรูปร่างAไปยังจุดที่ใกล้ที่สุดบนขอบของAการใช้ฟังก์ชันระยะทางนั้นน่าสนใจมากเพราะการคำนวณค่อนข้างรวดเร็ว
หนึ่งในคำจำกัดความของโครงกระดูกโดยใช้ฟังก์ชันระยะทางคือสันของฟังก์ชันระยะทาง[ 3 ]มีข้อความผิดพลาดทั่วไปในเอกสารว่าโครงกระดูกประกอบด้วยจุดซึ่งเป็น "จุดสูงสุดเฉพาะที่" ในการแปลงระยะทาง นี่ไม่ใช่กรณีดังกล่าวเลย ดังที่การเปรียบเทียบอย่างคร่าวๆ ระหว่างการแปลงระยะทางและโครงกระดูกที่ได้จะแสดงให้เห็น สันเขาอาจมีความสูงที่แตกต่างกัน ดังนั้นจุดบนสันอาจต่ำกว่าจุดข้างเคียงที่อยู่ติดกันบนสัน ดังนั้นจึงไม่ใช่จุดสูงสุดเฉพาะที่ แม้ว่าจะเป็นส่วนหนึ่งของสันก็ตาม อย่างไรก็ตาม มันอยู่ห่างออกไปในแนวดิ่งน้อยกว่าระยะทางบนพื้นดินที่ควรจะเป็น มิฉะนั้นมันจะเป็นส่วนหนึ่งของความลาดชัน
คำจำกัดความอื่นๆ
- จุดที่ไม่มีส่วนของเส้นตรงต้นน้ำในฟังก์ชันระยะทาง ส่วนของ เส้นตรงต้นน้ำของจุดxคือส่วนของเส้นตรงที่เริ่มต้นที่xซึ่งตามเส้นทางที่มีความชันสูงสุด
- จุดที่ค่าความชันของฟังก์ชันระยะทางแตกต่างจาก 1 (หรือกล่าวอีกนัยหนึ่งคือ ไม่สามารถนิยามได้อย่างชัดเจน)
- ชุดเส้นที่เล็กที่สุดเท่าที่จะเป็นไปได้ซึ่งยังคงรักษารูปทรงเดิมไว้และมีระยะห่างจากขอบเขตเท่ากัน
อัลกอริทึมการสร้างโครงร่าง
มีอัลกอริธึมมากมายหลายแบบสำหรับการคำนวณโครงร่างของรูปร่างในภาพดิจิทัลรวมถึงเซตต่อเนื่องด้วย
- การใช้ตัวดำเนินการทางสัณฐานวิทยา (ดูโครงร่างทางสัณฐานวิทยา[ 10 ] )
- การเสริมตัวดำเนินการทางสัณฐานวิทยาด้วย การตัดแต่งตามรูปร่าง[ 11 ]
- การใช้จุดตัดของระยะทางจากส่วนขอบเขต[ 12 ]
- การใช้วิวัฒนาการของเส้นโค้ง[ 13 ] [ 14 ]
- การใช้ชุดระดับ[ 5 ]
- การค้นหาจุดสันบนฟังก์ชันระยะทาง[ 3 ]
- การ "ลอก" รูปทรงโดยไม่เปลี่ยนแปลงโทโพโลยี จนกว่าจะบรรจบกัน[ 15 ]
- อัลกอริธึมการทำให้ผอมบางของ Zhang-Suen [ 16 ]
บางครั้งอัลกอริธึมการสร้างโครงร่างอาจสร้างกิ่งที่ไม่ต้องการบนโครงร่างที่ได้อัลกอริธึมการตัดแต่งกิ่งมักถูกใช้เพื่อกำจัดกิ่งเหล่านี้
ดูเพิ่มเติม
หมายเหตุ
- ↑ Jain, Kasturi & Schunck (1995) , มาตรา 2.5.10, หน้า. 55;โกลแลนด์ แอนด์ กริมสัน (2000) ;โดเฮอร์ตี้ (1992) ;อ็อกเนียวิคซ์ (1995 )
- ^ a b Gonzales & Woods (2001) , ส่วนที่ 11.1.5, หน้า 650
- ^ a b c d A. K. Jain ( 1989 ), ส่วนที่ 9.9, หน้า 382.
- ^เซอร์รา (1982 )
- ^ a b Sethian (1999) , ส่วนที่ 17.5.2, หน้า 234.
- ^ Abeysinghe et al. (2008)
- ^บัคช์ (2014)
- ^แฮร์รี่ บลัม ( 1967 )
- ↑เอเค เจน ( 1989 ), มาตรา 9.9, หน้า. 387.
- ^ a b Gonzales & Woods (2001) , ส่วนที่ 9.5.7, หน้า 543.
- ^ Abeysinghe et al. (2008) .
- ^คิมเมลและคณะ (1995 )
- ^แทนเนนบอม (1996)
- ↑ไป๋, หลงจิน และเหวินหยู่ (2550 )
- ↑เอเค เจน ( 1989 ), มาตรา 9.9, หน้า. 389.
- ^ Zhang, TY; Suen, CY (1984-03-01). "อัลกอริทึมแบบขนานที่รวดเร็วสำหรับการลดความหนาของรูปแบบดิจิทัล" Communications of the ACM . 27 (3): 236– 239. doi : 10.1145/357994.358023 . ISSN 0001-0782 . S2CID 39713481 .
ซอฟต์แวร์โอเพนซอร์ส
- ITK (C++)
- Skeletonize3D (Java)
- กราฟิกเจมส์ IV (C)
- อีวีจี-ทิน (ซี++)
- นิวรอนสตูดิโอ
ลิงก์ภายนอก
- การสร้างโครงร่าง/การแปลงแกนกลาง
- โครงกระดูกของภูมิภาค
- โครงกระดูกในการประมวลผลภาพดิจิทัล (pdf)
- การเปรียบเทียบอัลกอริทึมลดความหนาเส้น 15 แบบ
- การสร้างโครงร่างโดยใช้วิธี Level Set
- โครงกระดูกโค้ง
- โครงกระดูกจากกลุ่มจุดข้อมูลที่ได้จากการสแกนด้วยเลเซอร์ (หน้าหลัก)
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ โครงกระดูกเชิงทอพอโลยี
ในการวิเคราะห์รูปทรงโครงร่าง (หรือโครงร่างเชิงโทโพโลยี ) ของรูปทรงคือโครงร่างบางๆ ของรูปทรงนั้นที่อยู่ห่างจากขอบเขตของรูปทรงเท่ากัน...
นิยามทางคณิตศาสตร์
ในเอกสารทางเทคนิค โครงร่างมีนิยามทางคณิตศาสตร์ที่แตกต่างกันหลายแบบ ซึ่งส่วนใหญ่นำไปสู่ผลลัพธ์ที่คล้ายคลึงกันใน ปริภูมิต่อเนื่อง แต่โดยทั่วไปแล้วจะให้ผลลัพธ์ที่แตกต่างกันใน ปริภูมิไม่ต่อ เนื่อง
จุดดับไฟของแบบจำลองการลุกลามของไฟ
ในบทความสำคัญของเขา Harry Blum [ 8 ] จากห้องปฏิบัติการวิจัยเคมบริดจ์ของกองทัพอากาศที่ ฐานทัพอากาศแฮนส์คอม ใน เบดฟอร์ด รัฐแมสซาชูเซตส์ ได้กำหนด แกนกลาง สำหรับการคำนวณโครงร่างของรูปร่าง โดยใช้แบบจำลองเชิงสัญชาตญาณของการแพร่กระจายของไฟบนสนามหญ้า...
จุดศูนย์กลางของแผ่นดิสก์ (หรือลูกบอล) ที่ใหญ่ที่สุด
กล่าวได้ว่าแผ่น ดิสก์ (หรือ ลูกบอล ) B เป็น ค่าสูงสุด ในเซต A ถ้า