Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การแสดงกราฟสำหรับการจับคู่แผนผังห้องโดยใช้การฝังตัวเชิงสเปกตรัม
Year (A.D.)
2019
Document Type
Thesis
First Advisor
Nagul Cooharojananone
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2019.19
Abstract
Graph matching is efficient to search similar layout when the architectural floor plan data size is increasing. Because the computational time of floor plan matching using spectral embedding is only in seconds, so it is one of the popular methods. However, the isomorphism of each floor plan leads to low accuracy in the matching process and it becomes the weakness of this method. Therefore, we propose a graph representation for room layout matching using spectral embedding. Normally, graph representations of the floor plan define nodes as rooms and edges as connections between rooms. Besides, the graph spectral embedding is to find the feature vector of each floor plan by ignoring the semantic of rooms. Our proposed method also considers both room semantic which is the connection between the area outside and inside the room, and the structure of each layout. Furthermore, we show that by adding an extra node, our method can handle the isomorphism of a graph based on a mathematical idea called eigenvalue testing. There are three main processes in the proposed method: floor plan extracting, appended topology graph and floor plan matching. The performance from our experiment shows that our proposed method improve the matched accuracy from the conventional method by about 27.81 percent.
Other Abstract (Other language abstract of ETD)
การจับคู่กราฟมีประสิทธิภาพในการค้นหาแบบแปลนที่มีลักษณะคล้ายกันเมื่อข้อมูลแผนผังทางสถาปัตยกรรมมีขนาดเพิ่มมากขึ้น เนื่องจากการคำนวณเพื่อค้นหาการจับคู่แบบแปลนโดยใช้การฝังตัวเชิงสเปกตรัมนั้นใช้เวลาในเพียงแค่ไม่กี่วินาที ดังนั้นวิธีนี้จึงเป็นวิธีที่ได้รับความนิยม อย่างไรก็ตามการสมสัณฐานของแบบแปลนแต่ละแบบทำให้ความถูกต้องแม่นยำในกระบวนการจับคู่ลดลงและกลายเป็นจุดอ่อนของวิธีนี้ ดังนั้นเราจึงเสนอการแสดงกราฟสำหรับการจับคู่แบบแปลนห้องโดยใช้การฝังตัวเชิงสเปกตรัม โดยปกติแล้วการแสดงกราฟของแบบแปลนจะกำหนดโหนดแทนห้องและเส้นเชื่อมแทนการเชื่อมต่อระหว่างห้อง นอกจากนี้การฝังตัวเชิงสเปกตรัมมีวัตถุประสงค์เพื่อค้นหาเวกเตอร์แสดงคุณสมบัติของแต่ละแบบแปลนโดยไม่สนใจความหมายของห้องแต่วิธีที่นำเสนอนี้จัดการกับทั้งความหมายของห้องซึ่งคือการเชื่อมต่อระหว่างพื้นที่ภายนอกและภายในห้องและโครงสร้างของแต่ละแบบแปลนด้วย และเรายังแสดงให้เห็นว่าการเพิ่มโหนดใหม่ขึ้นมานั้นสามารถจัดการกับการสมสัณฐานของกราฟบนแนวคิดทางคณิตศาสตร์ที่เรียกว่าการทดสอบค่าเฉพาะได้ วิธีการที่นำเสนอประกอบด้วย 3 ขั้นตอน ได้แก่ การสกัดแบบแปลน การขยายกราฟทอพอโลยี และการจับคู่แบบแปลน ประสิทธิภาพจากการทดสอบวิธีการของเราแสดงให้เห็นว่าวิธีการที่เรานำเสนอสามารถปรับปรุงความแม่นยำในการจับคู่เพิ่มขึ้นจากวิธีการทั่วไปประมาณร้อยละ 27.81
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Sa-ngawong, Thamonwan, "Graph representation for room layout matching using spectral embedding" (2019). Chulalongkorn University Theses and Dissertations (Chula ETD). 8395.
https://digital.car.chula.ac.th/chulaetd/8395