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

Reeb graph based partial shape retrieval for 3D object

Name: วราวิทย์ อารีวิจิตร

ThaSH: การสร้างภาพสามมิติ

ThaSH: ระบบการจัดเก็บและค้นข้อสนเทศ

ThaSH: คอมพิวเตอร์วิทัศน์

LCSH: Three-dimensional imaging

LCSH: Information storage and retrieval systems

LCSH: Computer vision

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

Abstract: Nowadays, there are many 3D objects in digital libraries. Many approaches have been proposed in order to improve the speed and effectiveness of the retrieval. However, these approaches are not sufficient compared to the text-based retrieval. Because most of the existing 3D retrieval solutions are not support the similarity between part of object, that is partial similarity. Therefore, it is unable to query by the part of object and also cannot diagnose the element of object as text based retrieval. In this thesis, we present an algorithm for partial shape retrieval on a collection of 3D polygonal meshes. The proposed algorithm is invariant against rigid transformations and robust against different pose by using structure properties and geometric properties to represent shapes. Structure property is represented by a Reeb graph which uses an integral geodesic distance as a Morse function, whereas geometric property is represented by a Pose invariant Shape Signature. The main idea is to use Reeb graph for decomposing shape into many meaningful sub parts. Then describe each sub part with geometric property. The similarity is computed based on the Approximate Maximum Common Sub graph for matching each subpart between query shape and other while preserving topology. We evaluate our algorithm on various different model classes and deformation. The experimental results indicate better accuracy compared to the previous method in the case of deformable object. We have conclude that our approach is fast and sufficient for practical use. However, our algorithm is not suitable for concave objects and convex hull objects. The computational cost of the algorithm is O(n log n) for describing a shape and O(m⁴) for each matching with n is the number of vertices in mesh and m is the number of node in Reeb graph. The Mean Average Precision of this algorithm is about 0.348.

จุฬาลงกรณ์มหาวิทยาลัย. สำนักงานวิทยทรัพยากร

Address: กรุงเทพมหานคร

Email: cuir@car.chula.ac.th

Name: พิษณุ คนองชัยยศ

Role: ที่ปรึกษา

Email : Pizzanu.K@Chula.ac.th

Created: 2554

Modified: 2559-10-06

Issued: 2559-10-06

วิทยานิพนธ์/Thesis

application/pdf

URL: http://cuir.car.chula.ac.th/handle/123456789/35802

tha

DegreeName: วิศวกรรมศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: จุฬาลงกรณ์มหาวิทยาลัย

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	warawit_ar.pdf	3.41 MB	6	2020-03-10 23:46:12

ใช้เวลา

0.018291 วินาที