การสืบค้นวัตถุสามมิติแบบบางส่วนโดยใช้เรปกราฟ

Abstract

ปัจจุบันวัตถุสามมิติได้มีการใช้อย่างแพร่หลายและมีจำนวนเพิ่มขึ้นอย่างต่อเนื่องในคลังข้อมูลดิจิตอล จึงมีงานวิจัยเป็นจำนวนมากที่ให้ความสนใจในการเพิ่มความเร็วและประสิทธิผลในการสืบค้นวัตถุสามมิติ อย่างไรก็ตามงานส่วนใหญ่ที่ผ่านยังไม่สามารถเทียบได้กับการสืบค้นเอกสารซึ่งเป็นที่นิยมในปัจจุบัน ในแง่ของความสะดวกและความหลากหลายในการสืบค้น ปัญหาดังกล่าวเกิดขึ้นเนื่องจากงานส่วนใหญ่ที่ผ่านมาไม่รองรับการหาความเหมือนแบบบางส่วน ซึ่งคือความเหมือนกันของส่วนย่อยของวัตถุ จากเหตุนี้ทำให้ไม่รองรับการสืบค้นด้วยบางส่วนของวัตถุ และไม่สามารถแยกแยะวัตถุออกเป็นประเภทย่อยได้ ซึ่งคุณลักษณะเหล่านี้เป็นคุณลักษณะเด่นในการสืบค้นเอกสารในปัจจุบัน วิทยานิพนธ์นี้ได้ออกแบบอัลกอริทึ่มสำหรับการสืบค้นแบบบางส่วน สำหรับวัตถุสามมิติประเภทเมช ซึ่งรองรับการเปลี่ยนแปลงแบบวัตถุแข็งเกร็ง และทนต่อการเปลี่ยนแปลงท่าทางของวัตถุ โดยใช้คุณสมบัติทางโครงสร้าง และคุณสมบัติทางพื้นผิวในการอธิบายรูปร่างของวัตถุ ในงานนี้จะใช้เรปกราฟตามระยะทางจีออเดสิกเฉลี่ยในการแสดงคุณสมบัติทางโครงสร้าง และใช้ในการแบ่งส่วนวัตถุออกเป็นส่วนย่อยที่มีความหมายในเชิงทอพอโลยี และเพื่อเพิ่มความความแม่นยำในการเปรียบเทียบจะอธิบายแต่ละส่วนย่อยด้วยคุณสมบัติทางพื้นผิว การเปรียบเทียบระหว่างวัตถุจะถูกคำนวณผ่านการหากราฟย่อยสามัญที่ใหญ่ที่สุด เพื่อจับคู่ส่วนย่อยที่เข้าคู่กันและยังคงรักษาข้อมูลทางทอพอโลยีไว้ การทดสอบอัลกอริทึ่มจะทดสอบบนวัตถุหลากหลายประเภทที่มีการเปลี่ยนแปลงแบบวัตถุแข็งเกร็ง และการเปลี่ยนแปลงท่าทางที่แตกต่างกัน จากผลการทดสอบอัลกอริทึ่มที่นำเสนอสามารถสืบค้นวัตถุที่มีการเปลี่ยนแปลงท่าทางและมีความซับซ้อนได้ดี และมีความเร็วในระดับที่ผู้ใช้ยอมรับได้ อย่างไรก็ตามอัลกอริทึ่มนี้ไม่เหมาะสมกับวัตถุที่มีลักษณะเว้า และวัตถุที่มีลักษณะเป็นก้อน อัลกอริทึ่มที่นำเสนอมีประสิทธิภาพเชิงเวลาเป็น O(n log n) ในการสร้างตัวแทนข้อมูลวัตถุสามมิติเมื่อ n คือจำนวนจุดยอดของเมช และมีประสิทธิภาพเชิงเวลาเป็น O(m⁴) ในการเปรียบเทียบแต่ละครั้งโดย m คือจำนวนจุดยอดของเรปกราฟ การสืบค้นโดยเฉลี่ยแล้วจะมีค่าเฉลี่ยความแม่นเฉลี่ยเป็น 0.348