Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/139557
|
| Title: | 以圖神經網路將二維樂高建構映射至平鋪問題之方法
Mapping 2D Lego Construction into Tiling Problem with Graph Neural Network |
| Authors: | 王祥宇
Wang, Hsiang-Yu |
| Contributors: | 紀明德
Chi, Ming-Te
王祥宇
Wang, Hsiang-Yu |
| Keywords: | 樂高
圖神經網路
平鋪
LEGO
Graph neural network
Tiling |
| Date: | 2022 |
| Issue Date: | 2022-04-01 15:04:40 (UTC+8) |
| Abstract: | 樂高積木因積木種類的多樣性而被人們喜愛，且常被創作者們用在模型的設計上。近年來，出現許多樂高研究去探討如何以電腦計算建構出二維或三維的樂高模型，然而這些研究主要以長方體狀的基本磚來建構模型，使得外觀上雖然相似，但仍保有基本磚的稜角。此外，隨著用於建構的樂高磚種類和所要建構的模型大小增加，其搜索空間及運算時間也會大幅增加。
為了克服以上問題，本研究首先嘗試將GNN與二維樂高建構做結合。以樂高磚中的基本磚和斜磚作為輸入，並透過給定樂高損失函數，將現有的圖神經網路研究，從平鋪問題擴展至樂高組合問題。同時，我們也針對輸入圖形進行變形和使用分治法，來提升組裝結果的覆蓋率和相似度。綜上所述，我們提出一套系統流程，在使用者給定輸入圖形後，訓練完成的GNN模型便能輸出符合樂高建構的平鋪結果，再經過量化分析、合併和顏色抓取等操作，便能產生所要的樂高組裝結果。
Lego bricks are loved by people because of the variety of building blocks, and are often used by creators in the design of models. Recently, there have been many LEGO researches to explore how to construct 2D or 3D LEGO models by computer. However, these researches mainly build models with normal bricks. Although the appearance is similar, it still retains the edges and corners of normal bricks. Furthermore, as the types of Lego bricks used for construction and the size of the model to be constructed increase, the search space and computation time will also increase significantly.
In order to overcome the above problems, our research first attempts to combine the graph neural network with the 2D Lego construction problem. Taking normal bricks and slope bricks in LEGO bricks as input, and by giving the Lego loss function, the existing graph neural network research is extended from the tiling problem to the Lego combinatorial problem. At the same time, we also deform the input shapes and use the divide-and-conquer method to improve the coverage and similarity of the assembly results. To sum up, we propose a Lego system building. The trained GNN model can output tiling results that conform to the LEGO construction after the user gives the input shapes. Then, through quantitative analysis, merging and color mapping, the desired LEGO brick sculptures can be generated. |
| Reference: | [1]Xu, H., Hui, K. H., Fu, C. W., & Zhang, H. (2020). TilinGNN - Learning to Tile with Self-Supervised Graph Neural Network. ACM Transactions on Graphics (SIGGRAPH), 39(4), Article 129.
[2]Gower, R., Heydtmann, A. & Petersen, H. (1998). LEGO: Automated Model Construction. Jens Gravesen and Poul Hjorth, pp. 81-94.
[3]Testuz, R., Schwartzburg, Y., & Pauly, M. (2013). Automatic Generation of Constructable Brick Sculptures. In Eurographics (Short Papers) (pp. 81-84).
[4]Silva, L.F.M.S., Pamplona, V.F., & Comba, J.L.D. (2009) Legolizer: A real-time system for modeling and rendering LEGO® representations of boundary models Proceedings of SIBGRAPI 2009 - 22nd Brazilian Symposium on Computer Graphics and Image Processing, art. no. 5395263, pp. 17-23.
[5]Ono, S., Alexis, A., & Chang, Y. (2013). Automatic generation of LEGO from the polygonal data. In International workshop on advanced image technology (pp. 262-267).
[6]Kim, J.-W., Kang, K.-K., & Lee, J.-H. (2014). Survey on automated LEGO assembly construction. In Proc. WSCG 2014, pp. 89–96.
[7]Stephenson, B. (2016). A multi-phase search approach to the LEGO construction problem. In Ninth Annual Symposium on Combinatorial Search.
[8]Luo, S. J., Yue, Y., Huang, C. K., Chung, Y. H., Imai, S., Nishita, T., & Chen, B. Y. (2015). Legolization: optimizing lego designs. ACM Transactions on Graphics (TOG), 34(6), 222.
[9]Zhang, M., Igarashi, Y., Kanamori, Y., & Mitani, J. (2015). Designing mini block artwork from colored mesh. Smart Graphics (pp. 3-15). Springer, Cham.
[10]Yun, G., Park, C., Yang, H., & Min, K. 2017. Legorization with multi-height bricks from silhouette-fitted voxelization. Computer Graphics International Conference, Article 40, pp. 1-6.
[11]Kuo, M. H., Lin, Y. E., Chu, H. K., Lee, R. R., & Yang, Y. L. (2015). Pixel2brick: Constructing brick sculptures from pixel art. In Computer Graphics Forum, 34(7), pp. 339-348).
[12]Zhou, J., Chen, X., & Xu, Y. (2019). Automatic Generation of Vivid LEGO Architectural Sculptures. Computer Graphics Forum, 38(6), pp. 31-42.
[13]Xu, H., Hui, K. H., Fu, C. W., & Zhang, H. (2019). Computational LEGO® Technic Design. ACM Transactions on Graphics (SIGGRAPH ASIA), 38(6), Article 196.
[14]Lennon, K., Fransen, K., O`Brien, A., Cao, Y., Beveridge, M., Arefeen, Y., Singh, N. & Drori, I. (2021). Image2Lego - Customized LEGO® Set Generation from Images. arXiv preprint arXiv:2108.08477.
[15]Kim, J., & Pellacini, F. (2002). Jigsaw image mosaics. ACM Transactions on Graphics (SIGGRAPH), 21(3), pp. 657–664.
[16]Kwan, K. C., Sinn, L. T., Han, C., Wong, T. T., & Fu, C. W. (2016). Pyramid of Arclength Descriptor for Generating Collage of Shapes. ACM Transactions on Graphics (SIGGRAPH Asia), 35(6), Article 229.
[17]Gal, R., Sorkne, O., Popa, T., Sheffer, A., & Cohenor, D. (2007). 3D collage: expressive non-realistic modeling. In Proceedings of the 5th international symposium on Nonphotorealistic animation and rendering, NPAR ’07, 7–14.
[18]Chen, W., Ma, Y., Lefebvre, S., Xin, S., Martínez, J. & Wang. W. (2017) Fabricable Tile Decors. ACM Transactions on Graphics (SIGGRAPH Asia), 36(6), Article 175.
[19]Cohen, M. F., Shade, J., Hiller, S., & Deussen, O. (2003). Wang Tiles for Image and Texture Generation. ACM Transactions on Graphics (SIGGRAPH), 22(3), pp. 287–294.
[20]Peng, C.-H., Yang, Y.-L., & Wonka, P. (2014). Computing Layouts with Deformable Templates. ACM Transactions on Graphics (SIGGRAPH), 33(4), Article 99.
[21]Chen, X., Li, H., Fu, C.-W., Zhang, H., Cohen-Or, D., & Chen, B. (2018). 3D Fabrication with Universal Building Blocks and Pyramidal Shells. ACM Transactions on Graphics (SIGGRAPH Asia), 37(6), Article 189.
[22]Li, S., Mahdavi-Amiri, A., Hu, R., Liu, H., Zou, C., Kaick, O. V., Liu, X., Huang, H., & Zhang, H. (2018). Construction and Fabrication of Reversible Shape Transforms. ACM Transactions on Graphics (SIGGRAPH Asia), 37(6), Article 190.
[23]Tang, K., Song, P., Wang, X., Deng, B., Fu, C.-W., & Liu, L. (2019). Computational Design of Steady 3D Dissection Puzzles. Computer Graphics Forum, 38(2), pp. 291-303.
[24]Araújo, C., Cabiddu, D., Attene, M., Livesu, M., Vining, N., & Sheffer, A. (2019). Surface2Volume: surface segmentation conforming assemblable volumetric partition. ACM Transactions on Graphics (SIGGRAPH), 38(4), Article 80.
[25]Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940.
[26]Dai, H., Khalil, E. B., Zhang, Y., Dilkina, B., & Song, L. (2017). Learning combinatorial optimization algorithms over graphs. International Conference Neural Information Processing Systems. pp. 6351–6361.
[27]Hu, R., Xu, J., Chen, B., Gong, M., Zhang, H., & Huang, H. (2020). TAP-Net Transport-and-Pack using Reinforcement Learning. ACM Transactions on Graphics (SIGGRAPH Asia), 39(6), Article 232.
[28]Hu, Z., Dong, Y., Wang, K., Chang, K.-W., & Sun, Y. (2020). GPT-GNN: Generative Pre-Training of Graph Neural Networks. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 1857-1867.
[29]Jia, Z., Lin, S., Ying, R., You, J., Leskovec, J., & Aiken, A. (2020). Redundancy-Free Computation for Graph Neural Networks. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 997-1005.
[30]Yuan, H., Tang, J., Hu, X., & Ji, S. (2020). XGNN - Towards Model-Level Explanations of Graph. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 430-438.
[31]Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems ( Volume: 32, Issue: 1, Jan. 2021)
[32]Mo, K., Guerrero, P., Yi, L., Su, H., Wonka, P., Mitra, N., & Guibas, LJ. (2019). StructureNet: Hierarchical Graph Networks for 3D Shape Generation. ACM Transactions on Graphics (SIGGRAPH Asia), 38(6), Article 242.
[33]Li, Z., Chen, Q., & Koltun, V. (2018). Combinatorial optimization with graph convolutional networks and guided tree search. International Conference on Neural Information Processing Systems. pp. 537-546.
[34]Hu, R., Huang, Z., Tang, Y., Kaick, O. V., Zhang, H., & Huang, H. (2020). Graph2Plan: Learning Floorplan Generation from Layout Graphs. ACM Transactions on Graphics (SIGGRAPH), 39(4), Article 118.
[35]Yang, L., Zhuang, J., Fu, H., Wei, X., Zhou, K., & Zheng, Y. (2021). SketchGNN: Semantic Sketch Segmentation with Graph Neural Networks. ACM Transactions on Graphics (TOG), 37(4), Article 111.
[36]Lego Bricks: https://brickhub.org
[37]Veltkamp, R. C. (2001). Shape matching: similarity measures and algorithms. Proceedings International Conference on Shape Modeling and Applications. pp. 188–197.
[38]Eiter T, & Mannila H. (1994). Computing discrete Fréchet distance. Tech. Report CD-TR 94/64, Information Systems Department, Technical University of Vienna.
[39]https://www.thebrickfan.com/lego-2016-color-palette/ |
| Description: | 碩士
國立政治大學
資訊科學系
108753118 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0108753118 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202200365 |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 311801.pdf | | 4497Kb | Adobe PDF2 | 95 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
