正在进行安全检测...
发布时间：1714715450 来源：文档文库
小
中
大
字号：
第２７卷第７期 计算机辅助设计与图形学学报 Ｖ０１．２７ＮＯ．７ ２０１５年７月 Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ－Ａｉｄｅｄ Ｄｅｓｉｇｎ＆Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｊｕ１．２Ｏｌ５ 基于增强ＰｙｒＬＫ光流法的三维树木骨架重建方法 张德嘉，梁 爽，张晨，贾金原木 （同济大学软件学院上海２０１８０４） （ｊＹＪｉａ＠ｔｏｎｇｊｉ．ｅｄｕ．ｃｎ） 摘 要：针对树木骨架重建要求手工交互多、不精确的问题，提出了用增强ＰｙｒＬＫ光流法对树木骨架进行重建，且 可以基于多幅图像完全自动化地进行树木建模．首先在传统ＰｙｒＬＫ光流法的基础上加入了特征点的仿射变换和迭代 追踪，提出增强ＰｙｒＬＫ光流法，解决了传统ＰｙｒＬＫ光流法不支持特征点旋转和双向匹配验证的问题；其次利用邻域 的泛洪和局部点云的拟合进行高速、准确的树木骨架抽取，提出了三维体素泛洪和最小二乘拟合的方法．实验结果表 明，文中方法能够快速重建出极具真实感的三维树木骨架模型． 关键词：树木建模；增强ＰｙｒＬＫ光流法；三维重建；三维体素泛洪 中图法分类号：ＴＰ３９１ ３Ｄ Ｔｒｅｅ Ｓｋｅｌｅｔｏｎ Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ Ｂａｓｅｄ ｏｎ Ｅｎｈａｎｃｅｄ ＰｙｒＬＫ Ｏｐｔｉｃａｌ Ｆｌｏｗ Ａｌｇｏｒｉｔｈｍ Ｚｈａｎｇ Ｄｅｊｉａ，Ｌｉａｎｇ Ｓｈｕａｎｇ，Ｚｈａｎｇ Ｃｈｅｎ，ａｎｄ Ｊｉａ Ｊｉｎｙｕａｎ （ＳｃｈｏｏｌｏｆＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，Ｔｏｎｇｊｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０１８０４） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｔｒｅｅ ｓｋｅｌｅｔｏｎ ｓｕｆｆｅｒｓ ｆｒｏｍ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｌＯＷ ａｃｃｕｒａｃｙ ａｎｄ ｈｅａｖｙ ｕｓｅｒ ｉｎ－ ｔｅｒａｃｔｉｏｎ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐｒｏｐｏｓｅ ａ ｎｅｗ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ａｎ ｅｎｈａｎｃｅｄ ＰｙｒＬＫ ｏｐｔｉｃａｌ ｆｌｏｗ ａｌｇｏｒｉｔｈｍ ｔｏ ａｌｌｅｖｉａｔｅ ｓｕｃｈ ｐｒｏｂｌｅｍｓ．Ｆｉｒｓｔ，ａｆｆｉｎｅ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ ａｎｄ ｉｎｔｅｒａｃｔｉｖｅ ｔｒａｃｋｉｎｇ ａｒｅ ｉｎｃｏｒｐｏｒａｔｅｄ ｉｎｔｏ ｔｒａｄｉｔｉｏｎａｌ ＰｙｒＬＫ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｆｅａｔｕｒｅ ｍａｔｃｈｉｎｇ．Ｓｅｃｏｎｄ，ｗｅ ａｌｓｏ ｐｒｏ－ ｐｏｓｅ ｔｏ ｕｓｅ ３Ｄ ｖｏｘｅｌ・－ｂａｓｅｄ ｆｌｏｏｄｉｎｇ ａｎｄ ｌｅａｓｔ ｓｑｕａｒｅ ｔｏ ｅｘｔｒａｃｔ ｔｈｅ ｔｒｅｅ ｓｋｅｌｅｔｏｎ ａｆｔｅｒ ｐｏｉｎｔ ｃｌｏｕｄ ｒｅｃｏｎ・－ ｓｔｒｕｃｔｉｏｎ ｗｉｔｈ ｈｉｇｈｅｒ ｅｆｉｆｃｉｅｎｃｙ ａｎｄ ａｃｃｕｒａｃｙ．Ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｏｕｒ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｍｅｔｈｏｄ ｉｓ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｅｆｉｆｃｉｅｎｔ ｉｎ ３Ｄ ｔｒｅｅ ｓｋｅｌｅｔｏｎｓ． Ｋｅｙ ｗｏｒｄｓ：ｔｒｅｅ ｍｏｄｅｌｉｎｇ；ｅｎｈａｎｃｅｄ ＰｙｒＬＫ ｏｐｔｉｃａｌ ｆｌｏｗ；３Ｄ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ；３Ｄ ｖｏｘｅｌ ｆｌｏｏｄｉｎｇ 树木建模在虚拟场景中的应用十分广泛，是场 费高，因此不适宜进行一般用途的建模．为了克服 景漫游、三维游戏、虚拟现实等研究领域不可或缺 这些缺陷，不少学者对树木的自动化建模进行了 的一部分．主流的手工建模方法虽然能够得到精 研究．但是，自然界中的树木形态多样，结构复杂， 确的树木模型，但是需要专业人员，并且耗时长、耗 使得树木建模在计算机图形领域成为了极具挑战 收稿日期：２０１４—０４—１３；修回日期：２０１４—０９・２７．基金项目：国家自然科学基金面上项目（６１２７２２７６）；国家自然科学基金青年项 目（６１３０５０９１）；国家“十二五”计划重大科技支撑项目（２０１２ＢＡＣ１１Ｂ００—０４．Ｏ３）；高等学校博士学科点专项科研基金项目（博导类） （２Ｏ１３ｏ０７２ｌ１ＯＯ３５）；吉林省重点科技攻关课题（２Ｏ１４Ｏ２Ｏ４Ｏ８８Ｇｘ）；上海市浦江人才计划（１３ＰＪ１４０８２００）；长春高新区“长白慧谷”英才 计划（３—２０１３００６）；中央高校基本科研业务费专项资金（２１００２１９０３８）．张德嘉（１９９１一），男，硕士研究生，主要研究方向为计算机图形 学、轻量化建模；梁爽（１９８３—），女，博士，讲师，主要研究方向为计算机图形学、模式识别；张展（１９８７—＇，男，硕士研究生，主 要研究方向为计算机图形学、图像处理；贾金原（１９６３一），男，博士，博士生导师，论文通讯作者，主要研究方向为计算机图形学、虚拟 现实．
计算机辅助设计与图形学学报 第２７卷 的研究课题． 泛洪（３Ｄ ｖｏｘｅ１．ｂａｓｅｄ ｌｆｏｏｄｉｎｇ）的算法，它能够根据 树木形态自底向上的生长规律进行空间泛洪，并 且在同一级的节点上，该方法采用了并发泛洪，从 早期的基于规则的树木建模建立在Ｌ．Ｓｙｓｔｅｍ【１］ 的基础上，并利用树木生长规则对模型进行递归 式的生成［２。】，但是少量的规则无法还原出真实感较 强的树木模型．而基于三维扫描仪的树木重建＿４ 】 而提高了算法的效率． 虽然能够得到较稠密的点云数据，但由于设备昂 贵，也不是一种适用度广的方法．温维亮等【６Ｊ用隐 １技术路线概述 本文提出了一套完整的基于多幅图像树木骨 架重建的解决方法，它主要分为特征点匹配、三维 重建和骨架抽取３个阶段．该方法首先以树木图像 序列作为输入，提出了增强ＰｙｒＬＫ光流法来进行特 征点匹配，以准确和稳定的匹配结果进行后续的 式曲面来构造三维树木枝条模型，以达到比较光 滑拼接的效果，但是这种方法的数据量比较大． 基于图像的树木建模由于其输入简单，并且 图像信息丰富，受到许多研究人员的关注．Ｎｅｕｂｅｒｔ 等【７】根据树木在图像中的像素密度近似生成空间 体素，并进一步以三维粒子流和方向场等方法模 拟生成了树木骨架．但是对于树木轮廓内没有背 三维重建步骤，得到稳定的树木点云模型．在此基 础上，再通过三维体素泛洪和局部几何信息的拟 合，得到精确的树木骨架模型．图１所示为本文方法 的总体路线图．其中，本文方法的创新点如下： ｌ１用增强ＰｙｒＬＫ光流法进行树木图像间的特 征点匹配．该方法突破了传统ＰｙｒＬＫ光流法不支 持特征点仿射变换的局限，并且用迭代追踪的方 法解决了传统ＰｙｒＬＫ光流法未进行双向匹配而导 致过多错误匹配的问题，增强了匹配的鲁棒性．实 验表明，该方法的实验结果远远优于主流的ＳＩＦＴ 景像素的情况，该方法需要完全靠用户勾画骨架， 工作量大．Ｔａｎ等［８】提出了依靠树木生长引擎来恢 复树木枝干，然后将其与叶片结合进行重建．该方 法由于使用单幅图像，信息不足，再加上可见枝干 较少，因此枝干的重建更多地带有猜测的成分． Ｔａｎ等【 】和Ｑｕａｎ等【】ｏｊ还用Ｓｔｒｕｃｔｕｒｅ Ｆｒｏｍ Ｍｏｔｉｏｎ 的方法恢复树木的三维点云数据，从而进行重建． 但是由于树木的复杂性，使得主流的ＳＩＦＴ特征匹 配正确率很低，导致后续的三维重建步骤无法得 到准确的模型．对于从点云中抽取骨架，Ｌｉｎｖｙ等 ［¨］使用了迭代的方法来逐步优化骨架，并提出了 一特征点匹配方法和传统的ＰｙｒＬＫ光流法． ２）用三维体素泛洪的方法确定点云邻域范围， 并基于邻域内的点云分布拟合出树木的局部几何 种ＢＳＧ的数据结构．Ｓｈｅ等［１ ］使用了三维细化的 信息．其中三维体素泛洪方法不仅将泛洪时体素 问的相互影响降至最低，而且采用并发的方法来 加速泛洪．区别于主流的三维细化等方法，该方法 结合了树木自底向上的形态规律，能够更高速和 准确地获取树木骨架． 方法来从点云获取骨架，但是由于三维细化是一 种通用的骨架抽取算法，其并没有针对树木形态 进行特殊的优化，因此效率较低． 由于ＳＩＦＴ方法在树木匹配时出现过多错误， 因此本文提出了增强ＰｙｒＬＫ光流法．该方法将特 征点的仿射变换和迭代追踪加入到传统ＰｙｒＬＫ光 流法［１ ］中，能够非常精确和鲁棒地进行特征点的 匹配；将其匹配结果导人到后续三维重建步骤，可 以得到高精度的点云．在骨架抽取步骤，为了克服 ２增强ＰｙｒＬＫ光流法 不同于简单物体的重建，由于树木结构复杂、 过多遮挡和光照分布不均匀等因素，导致主流的 ＳＩＦＴ特征匹配算法的实际效果很不理想．本文 厂 、 三维细化效率不高的局限，本文提出了三维体素 厂 、 ＩＩ基于仿射变ｌ ￣ＰｙｒＬＫ Ｉ 三维体素泛洪 木骨架模型 输入图 ｌ 迭代追踪 Ｉ 三维重建 几何参数拟合 ＼ ／ 图１ 基于图像树木骨架重建总体路线图
第７期 张德嘉，等：基于增强ＰｙｒＬＫ光流法的三维树木骨架重建方法 引进了ＰｙｒＬＫ光流法来进行多幅图像间的特征点 匹配，较ＳＩＦＴ算法，ＰｙｒＬＫ光流法更能捕捉树木图 像中特征点的对应关系． 光流法将图像上的像素值作为一个三元的函 数Ｉ（ｘ，Ｙ， ，其中Ｘ和Ｙ为像素点的坐标，ｔ表示时 间．该方法用函数 的变化来刻画光流的变化，以 达到运动追踪的目的．而ＰｙｒＬＫ光流法则采用 Ｌｕｃａｓ—Ｋａｎａｄｅ的实现，并且用图像金字塔的方法 加以扩展，使得光流法有了很大的改进． 但是，传统的ＰｙｒＬＫ光流法有比较大的局限 性，主要表现在２个方面：不支持特征点旋转，即 传统的ＰｙｒＬＫ光流法只支持特征点的平移变换， 不能捕捉特征点的旋转变换；缺乏验证机制，即没 有给出一个对于匹配点是否合格的验证机制，导 致匹配对的可信度下降． 为了打破ＰｙｒＬＫ光流法的局限性，本文将特 征点的仿射变换和迭代追踪加入到传统ＰｙｒＬＫ光 流法中，提出了增强ＰｙｒＬＫ光流法．该方法首先将 传统ＰｙｒＬＫ光流法扩展为基于特征点仿射变换的 ＡｆｆｉｎｅＰｙｒＬＫ光流法，引入了待定的仿射变换矩阵， 并改造了传统的光流方程，从而增强了ＰｙｒＬＫ光 流法的适用性．然后又对特征点的匹配进行迭代 的追踪，只有在迭代过程中表现稳定的特征点才 作为真正匹配的特征点，从而大大降低了匹配错 误率，提高了匹配算法的鲁棒性． ２．１ 基于ＡｆｆｉｎｅＰｙｒＬＫ光流法的特征点匹配 对于传统的ＰｙｒＬＫ光流法，只能解决平移特 征点的匹配；然而，这并不足以解决树木图像的匹 配问题．因为相邻２帧图像要求在空间形成一定的 夹角进行拍摄，这样在２帧图像上，也一定会产生 在空间旋转投影下的平面旋转；而特征点的这种 变换在传统ＰｙｒＬＫ光流法里是无法捕捉的．所以， 有必要对ＰｙｒＬＫ光流法进行由平移变换到仿射变 换的扩展．本文将待定的仿射变换矩阵加入到传 统的ＰｙｒＬＫ光流法中，用图像中局部小窗口内的 像素数据来拟合待定矩阵，从而支持特征点的仿 射变换．具体方法如下： 设２个特征点的匹配满足仿射矩阵 ，即前１ 帧图像上的特征点通过仿射变换 匹配到后１帧 的点．那么有 ｆ ｒ１ ｆ ａｌ１ ａ１２ ａ１３ １ ｆ Ａｘ １ 