學術產出-Theses
Article View/Open
Publication Export
-
題名 以圖神經網路將二維樂高建構映射至平鋪問題之方法
Mapping 2D Lego Construction into Tiling Problem with Graph Neural Network作者 王祥宇
Wang, Hsiang-Yu貢獻者 紀明德
Chi, Ming-Te
王祥宇
Wang, Hsiang-Yu關鍵詞 樂高
圖神經網路
平鋪
LEGO
Graph neural network
Tiling日期 2022 上傳時間 1-Apr-2022 15:04:40 (UTC+8) 摘要 樂高積木因積木種類的多樣性而被人們喜愛，且常被創作者們用在模型的設計上。近年來，出現許多樂高研究去探討如何以電腦計算建構出二維或三維的樂高模型，然而這些研究主要以長方體狀的基本磚來建構模型，使得外觀上雖然相似，但仍保有基本磚的稜角。此外，隨著用於建構的樂高磚種類和所要建構的模型大小增加，其搜索空間及運算時間也會大幅增加。為了克服以上問題，本研究首先嘗試將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.參考文獻 [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/ 描述 碩士
國立政治大學
資訊科學系
108753118資料來源 http://thesis.lib.nccu.edu.tw/record/#G0108753118 資料類型 thesis dc.contributor.advisor 紀明德 zh_TW dc.contributor.advisor Chi, Ming-Te en_US dc.contributor.author (Authors) 王祥宇 zh_TW dc.contributor.author (Authors) Wang, Hsiang-Yu en_US dc.creator (作者) 王祥宇 zh_TW dc.creator (作者) Wang, Hsiang-Yu en_US dc.date (日期) 2022 en_US dc.date.accessioned 1-Apr-2022 15:04:40 (UTC+8) - dc.date.available 1-Apr-2022 15:04:40 (UTC+8) - dc.date.issued (上傳時間) 1-Apr-2022 15:04:40 (UTC+8) - dc.identifier (Other Identifiers) G0108753118 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/139557 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 108753118 zh_TW dc.description.abstract (摘要) 樂高積木因積木種類的多樣性而被人們喜愛，且常被創作者們用在模型的設計上。近年來，出現許多樂高研究去探討如何以電腦計算建構出二維或三維的樂高模型，然而這些研究主要以長方體狀的基本磚來建構模型，使得外觀上雖然相似，但仍保有基本磚的稜角。此外，隨著用於建構的樂高磚種類和所要建構的模型大小增加，其搜索空間及運算時間也會大幅增加。為了克服以上問題，本研究首先嘗試將GNN與二維樂高建構做結合。以樂高磚中的基本磚和斜磚作為輸入，並透過給定樂高損失函數，將現有的圖神經網路研究，從平鋪問題擴展至樂高組合問題。同時，我們也針對輸入圖形進行變形和使用分治法，來提升組裝結果的覆蓋率和相似度。綜上所述，我們提出一套系統流程，在使用者給定輸入圖形後，訓練完成的GNN模型便能輸出符合樂高建構的平鋪結果，再經過量化分析、合併和顏色抓取等操作，便能產生所要的樂高組裝結果。 zh_TW dc.description.abstract (摘要) 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. en_US dc.description.tableofcontents 第一章 緒論 11.1 研究動機 11.2 問題描述 21.3 論文貢獻 31.4 論文章節架構 3第二章 相關研究 42.1 樂高積木建構 42.2 組合問題 62.3 圖神經網路 8第三章 研究方法 113.1 系統流程 113.2 資料前處理 123.3 樂高組合的可能性 133.4 GNN模型訓練 173.4.1 神經網路和損失函數 173.4.2 結果預測 193.5 樂高輸出 203.5.1 圖形位移 213.5.2 量化分析 223.5.3 合併與顏色限制 243.6 最佳化 263.6.1 變形 263.6.2 分治法 30第四章 結果與限制 324.1 研究細節 324.2 實驗數據比較 344.2.1 輸入集合差異 344.2.2 組裝結果大小 374.2.3 組裝時間 394.2.4 變形程度 404.3 案例分析 424.4 結果 434.5 環境 474.6 限制 47第五章 結論與未來展望 485.1 結論 485.2 未來展望 49參考文獻 50 zh_TW dc.format.extent 4605515 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0108753118 en_US dc.subject (關鍵詞) 樂高 zh_TW dc.subject (關鍵詞) 圖神經網路 zh_TW dc.subject (關鍵詞) 平鋪 zh_TW dc.subject (關鍵詞) LEGO en_US dc.subject (關鍵詞) Graph neural network en_US dc.subject (關鍵詞) Tiling en_US dc.title (題名) 以圖神經網路將二維樂高建構映射至平鋪問題之方法 zh_TW dc.title (題名) Mapping 2D Lego Construction into Tiling Problem with Graph Neural Network en_US dc.type (資料類型) thesis en_US dc.relation.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/ zh_TW dc.identifier.doi (DOI) 10.6814/NCCU202200365 en_US
