政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/139557
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文笔数/总笔数 : 113303/144284 (79%)
造访人次 : 50832303      在线人数 : 877
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 查询小技巧:
  • 您可在西文检索词汇前后加上"双引号",以获取较精准的检索结果
  • 若欲以作者姓名搜寻,建议至进阶搜寻限定作者字段,可获得较完整数据
  • 进阶搜寻
    政大機構典藏 > 資訊學院 > 資訊科學系 > 學位論文 >  Item 140.119/139557


    请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/139557


    题名: 以圖神經網路將二維樂高建構映射至平鋪問題之方法
    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
    上传时间: 2022-04-01 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
    DOI: 10.6814/NCCU202200365
    显示于类别:[資訊科學系] 學位論文

    文件中的档案:

    档案 描述 大小格式浏览次数
    311801.pdf4497KbAdobe PDF297检视/开启


    在政大典藏中所有的数据项都受到原著作权保护.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,惟仍請適度,合理使用本網站之內容,以尊重著作權人之權益。商業上之利用,則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作,已盡力防止侵害著作權人之權益,如仍發現本網站之數位內容有侵害著作權人權益情事者,請權利人通知本網站維護人員(nccur@nccu.edu.tw),維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回馈