过程式城市建模研究进展

朱晓强， 万旺根

1.上海大学通信与信息工程学院，上海200444

2.上海大学智慧城市研究院，上海200444

随着物联网、云计算的快速发展，数字城市已进入更高级的智慧城市阶段.数字城市以计算机技术、多媒体技术和大规模存储技术为基础，以宽带网络为纽带，运用遥感、全球定位系统、地理信息系统、遥测、仿真-虚拟等技术，对城市进行多分辨率、多尺度、多时空和多种类的三维描述，即利用信息技术手段把城市的过去、现在和未来的全部内容在网络上进行数字化虚拟实现.其中，作为数字城市最为基础的实物载体，城市三维模型是对真实城市的再现，它包括数字地形模型、建筑物、道路、植物等.

城市规划、城市策略、影视游戏、军事演习等领域[1]均以数字城市为基础，因此三维城市建模始终是一个多年的热点领域，并有了比较成熟的建模工具，如Autodesk公司的3DS MAX以及Google公司的SketchUp产品.目前，关于城市的三维建模研究有各种分类方法.按照数据源可分为基于航空影像[2]和基于点云数据[3]等方法；按建模方法可分为基于立体视觉[4-5]和基于规则的过程式建模[7-8]等；按照自动化程度可分为手工[10]、半自动、全自动等方法[4,8].不同的建模方法所得到的模型质量和效果差别很大，比如基于平面底图和地面摄影数据的手工建模[11]结果的细节非常丰富，而基于规则的过程式建模更适合于生成低复杂度的城市建筑物模型[15].

对于城市大范围的建模，用3DS MAX和SketchUp会耗费过多的人力和时间资源.从实际需求出发，研究大范围城市的自动化三维建模技术是重要趋势，并已取得了较大进展.尽管城市建模领域涉及非常广的研究内容，不仅要用成熟的二维GIS技术，也要用到基于航空影像的遥感技术，同时在基于视觉的三维重建领域不断有新的突破.然而，本文并非全面列举各种现有的技术，而是针对目前研究和应用比较广泛的过程式建模技术进行介绍和分析.

1 过程式建模概述

过程式建模是一种基于规则的建模方法，在计算机图形学领域是一项非常受欢迎的建模技术.该技术不仅实现简单，而且通过调整参数就能得到各种复杂的对象.过程式建模比较适合生成具有重复子结构和自相似特征的物体，如植物[12]、河流[13]、地形[14]等自然景物，人造物体建模方面也有了很多研究如城市路网建模、建筑物建模等[15-17].

2 正向过程式城市建模

过程式建模一般不太注重细节特征，而是根据输入的模型子结构快速生成整个物体或者整个场景，所生成的结果虽有一定的随机性，但与子结构具有相似的外观特征.正向过程式建模一般可根据参数调整的方式得到丰富的结果模型.

2.1 基于语法的城市建模

L-系统最早由Lindenmayer提出[18]，用来模拟细胞分裂过程.Prusinkiewicz[19]扩展了L-系统的概念，使之适用于图形化建模、可生长的植物建模、生态环境中的植物分布.

由于城市大规模建模的需要和城区模型的自相似性，近年来出现了基于语法的城市快速建模技术.文献[15]首次使用基于开放的L-系统生成虚拟城市的街道布局，根据各种图像、地图等数据源(如水陆分界线、人口密度等)，系统可快速生成高速公路和街道信息，从而将陆地分为不同的地块，然后在各个地块内部生成合适的建筑物几何模型，如图1所示.

图1 基于L-系统的城市建模Figur e 1 City modeling based on L-system

文献[20]介绍了交互式建筑物生成方法，利用CGA(computer generated architecture)形状语法生成具有高质量可视效果和细节的建筑物外壳.该方法首先生成建筑物的粗糙体模型，然后将模型的外表进行结构化，最后添加门、窗和其他装饰等细节内容.文献[21]使用简单的递推规则定义基于图像的建筑物建模，以建筑物的单幅正面图像为输入，结合基于形状语法的过程式建模技术和图像分析知识来生成有语义的建筑物正面细分结构，如图2所示.

图2 基于图像的建筑物正面过程式建模Figure 2 Image-based procedural modeling of facades

2.2 基于合成的建筑物生成

文献[6]借鉴二维纹理的合成，提出了一种基于样例的三维建筑物合成方法.用户只要输入一个小的样例建筑物模型，系统即可自动生成一个很复杂的建筑物群，且该建筑物群与输入样例外形相似.文献[7]对模型合成算法进行了扩展，充分考虑了模型的边界特征和连续性，使得新合成的复杂模型不仅整体上相似于输入样例模型，而且能合成相邻模型边界特征，从而得到更自然的合成模型.为了让三维模型合成算法具有更高的实用性和通用性，文献[8]介绍了基于约束的模型合成，系统将用户的输入意图转换为维度、几何或者代数约束，用来指导模型的合成过程，从而使合成的结果更加自然，如图3所示.关于建筑物三维模型的合成算法细节可以参见文献[9].

图3 基于合成的建筑物生成Figure 3 Synthesis-based building generation

3 逆向过程式城市建模

逆向过程式建模是近年来兴起的新研究领域，不仅可以高效生成大规模的新三维模型，而且可以重建已有的建筑物.

3.1 逆向过程式建模参数求解

逆向过程式建模始终是个难题，需要解决的问题是求解一套语法规则和对应的语法参数值，使得该套语法和参数在前向过程式建模中生成用于预定义的目标模型.该规则和参数的求解过程可以理解为把预订的三维模型压缩到一个紧致的参数空间里.文献[22]给出了一种算法，可从任意的二维矢量图推算出紧致的语法规则，通常生成一个参数化的上下文无关的L-系统来表示输入的二维形状.其中，L-系统的规则用于对规整化的结构进行编码，参数的大小代表结构变形相关的属性，但该算法主要针对二维模型.文献[23]利用输入三维模型的局部对称性进行辅助逆向过程式建模，将物体在对称区域内沿对称线切分碎片，然后创建形状操作算子，从而生成可保持对称性的新模型.文献[24]给出了一种基于优化的方法，从生成的模型空间中找到与预设配置最相近的一个，其核心是将建模过程形式化为语法生成空间的概率推断问题.对于给定模型的高层次配置参数，首先定义一个用于衡量目标模型与配置参数之间相似度的目标函数，然后根据优化算法进行求解.

3.2 建筑物生成

将逆向过程式建模技术用于城市建筑物重建也有各种特定的方法，较多的是假定规则为已知量，参数为未知量.文献[25]利用语法驱动的算法从航拍影像中自动提取建筑物，该算法建立在模型遵照Manhattan-World假定的基础上，即场景中需要建立3个相互垂直的坐标轴.通过语法将建筑物的重建过程转化为对初始粗糙的建筑物逐步细化的操作序列，并根据几何和影像匹配需求对细化过程进行优化，最终可以较鲁棒地生成完整、一致并且贴有纹理的三维模型，如图4所示.

图4 基于航空影像的逆向过程式建筑物重建Figure 4 Inverse procedural building reconstruction based on aerial images

3.3 城区生成

除了对单个建筑物的逆向重建之外，文献[26]研究了逆向过程式建模和整个城区大场景设计.给出了一种设计城区的机制，借助于蒙特卡罗马尔科夫链和BP算法实现了城区设计的抽象化和可交互性.系统支持复杂的通用指示器标识，从而允许用户从较高的语义层次控制全局目标形状，如图5所示.系统具体实现可以看作是一个黑盒子，同时支持上下文无关和上下文敏感的随机语法.

图5 基于逆向过程式建模的城区设计Figure 5 Urban design based on inverse procedural modeling

3.4 逆向过程式建模展望

尽管逆向过程式可以生成指定形状的目标物体，但过程式高效建模主要针对大场景海量模型生成，因此如何快速获取大量目标物体形状是一个很重要的问题.航空影像虽然是很好的数据源，但遮挡问题使获取的大多为局部视角下的信息.随着激光扫描技术的不断进步，LiDAR数据的获取也变得越来越容易.根据点云的获取方式，三维重建可以分为基于地面[3]、车载[27]和机载[28-29]LiDAR点云.这3种数据源各有优缺点，其中地面和车载的LiDAR数据不能获取到屋顶的信息，机载LiDAR能够获取建筑物的位置、顶部以及色彩信息，但采集机载LiDAR数据的代价较大[1].因此，针对不同的过程式建模需求，可分别采用对应点云获取方式生成目标形状数据，并作为逆向过程式建模的形状约束.

4 结语

尽管城市建模涵盖很多分支，并有很多的文献可供参考，但本文从过程式建模最新研究进展进行了简要介绍.过程式建模通过定义语法规则可以充分复用定义的规则，从而高效率生成单个建筑物甚至超大范围的城区场景.为了解决过程式建模的可控性问题，学者们给出了一些逆向过程式建模，但仍有很广泛的研究空间.LiDAR点云数据能够直接得到物体的三维信息，扫描生成的点云数据也有助于数据驱动的逆向过程式建模技术.

[1]王丽英.城市环境的过程式建模技术研究[D].杭州：浙江大学，2009.

[2]桂德竹，林宗坚，张成成.倾斜航空影像的城市建筑物三维模型构建研究[J].测绘科学，2012,178(4):144-146.

GUI Dezhu,LIN Zongjian,ZHANG Chengcheng,Research on construction of 3D building based on oblique images from UAV[J].Science of Surveying and Mapping,2012,178(4):144-146.(in Chinese)

[3]张志超.融合机载与地面LIDAR数据的建筑物三维重建研究[D].武汉：武汉大学，2010.

[4]SNAVELY K N.Scene reconstruction and visualization from Internet photo collections[D].Washington:University of Washington,2009.

[5]POLLEFEYS M,NISTER D,FRAHM J M,AKBARZADEHA,MORDOHAIP,CLIPPB,ENGELSC,GALLUP D,KIM SJ,MERRELL P,SALMIC,SINHA S,TALTON B,WANG L,YANG Q,STEw ENIUS H,YANG R,WELCHG,TOw LESH.Detailed real-time urban 3D reconstruction from video[J].International Journal of Computer Vision,2007,78(2/3):143-167.

[6]MERRELL P.Example-based model synthesis[C]//Proceeding of the 2007 Symposium on Interactive 3D Graphics and Games,2007:105-112.

[7]MERRELLP,MANOCHAD.Continuous model synthesis[J].ACM Transactions on Graphics,2008,27(5):158:1-158:7.

[8]MERRELLP,PALOA,MANOCHAD.Model synthesis:a general procedural modeling algorithm[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(6):715-728.

[9]MERRELL P.Model synthesis[D].North Carolina:University of North Carolina at Chapel Hill,2009.

[10]YINX,WONKA P,RAZDANA.Generating 3D building models from architectural drawings:a survey[J].IEEE Computer Graphics and Applications,2009,29(1):20-30.

[11]龚俊，朱庆，眭海刚，宋成芳.从CAD模型到数码城市GIS模型的若干问题[J].武汉大学学报：工学版，2003,36(2):64-68.

GONG Jun,ZHU Qing,SUI Haigang,SONG Chengfang.Key issues for data transformation from CAD to GIS[J].Engineering Journal of Wuhan University,2003,36(2):64-68.(in Chinese)

[12]LONGAY S,RUNIONSA,BOUDONF,PRUSINKIEw ICZ P.TreeSketch:interactive procedural modeling of trees on a tablet[C]//Proceedings of the International Symposium on Sketch-Based Interfaces and Modeling,2012:107-120.

[13]DERZAPFE,GANSTERB,GUTHEM,KLEINR.River networks for instant procedural planets[J].Computer Graphics Forum,2011,30(7):2031-2040.

[14]GENEVAUX J D,GALIN E,GUERIN E,PEYTAVIE A,BENESB.Terrain generation using procedural models based on hydrology[J].ACM Transactions of Graphics,2013,32(4):143:1-143:13.

[15]PARISH Y I H,MULLER P.Procedural modeling of cities[C]//Proceedings of ACM SIGGRAPH,2001:301-308.

[16]MUSIALSKI P,WONKA P,A sc liaga D G,WIMMER M,GOOL L,PURGATHOFER W.A survey of urban reconstruction[J].Computer Graphics Forum,2013,32(6):146-177.

[17]VANEGASC A,ALIAGA D G,WONKA P,MULLERP,WADDELLP A,WATSONB.Modeling theappearance and behavior of urban spaces[J].Computer Graphics Forum,2010,29(1):25-42.

[18]LINDENMAYER A.Mathematical models for cellular interaction in development[J].Journal of Theoretical Biology Parts I and II,1968(18):280-315.

[19]PRUSINKIEw ICZ P.Graphical applications of Lsystems[C]//Proceedings on Graphical Interface,1986:247-253.

[20]MULLERP,WONKAP,HAEGLERS,ULMERA,GOOL L V.Procedural modeling of buildings[J].ACM Transactions on Graphics,2006,26(2):614-623.

[21]MULLER P,ZENG G,WONKA P,GOOL L V.Imagebased procedural modeling of facades[J].ACM Transactions on Graphics,2007,26(3):85:1-85:9.

[22]ST'AVA O,BenešB,MECHR,ALIAGA D G,KRIŠTOF P.Inverse procedural modeling by automatic generation of L-systems[J].Computer Graphics Forum,2010,29(2):665-674.

[23]BOKELOH M,WAND M,SEIDEL H P.A connection between partial symmetry and inverse procedural modeling[J].ACM Transactions on Graphics,2010,29(4):104:1-104:10.

[24]TALTON J O,LOU Y,LESSER S,DUKE J,MECH R,KOLTUN V.Metropolis procedural modeling[J].ACM Transactions on Graphics,2011,30(2):11:1-11:14.

[25]VANEGAS C A,ALIAGA D G,BENES B.Building reconstruction using Manhattan-world grammars[C]//IEEE Conference on Computer Vision and Pattern Recognition,2010:358-365.

[26]VANEGAS C A,GARCIA-DORADO I,ALIAGA D G,BENESB,WADDELL P.Inverse design of urban procedural models[J].ACM Transactions on Graphics,2012,31(6):168:1-168:11.

[27]LIN H,GAO J,ZHOU Y,LU G,YE M,LIU L,YANG R.Semantic decomposition and reconstruction of residential scenes from LiDAR data[J].ACM Transactions on Graphics,2013,32(4):66:1-66:10.

[28]朱晓强.基于LiDAR点云和航空影像的城市三维重建[D].合肥：合肥工业大学，2009.

[29]姚春静.机载LiDAR点云数据与遥感影像配准的方法研究[D].武汉：武汉大学，2010.