填充算法（共5篇）
填充算法 篇1
本文的研究目的是对深度图像绘制原理的研究, 在历史理论的基础上改进空洞填充算法, 消除视图合成过程中的空洞问题。该算法对视图差进行具体分析。首先, 基于深度图像转换对原始数据进行处理, 会产生匹配误差, 本文采用对三维图像变换后得到的目标图像中那些存在匹配误差的空洞边缘进行膨胀。其次, 为有效确定空洞的起始位置, 检测视图上空洞;随后, 区分并膨胀大空洞非空边缘处的前背景像素得以消除匹配误差。最后, 利用视差值从参考图像中拷贝像素来填充空洞。论文通过算法改进了DIBR中的空洞填充工作, 并以数据流的方式输出, 具有较强的实用性。
1 基于DIBR的视图合成
基于DIBR的视图合成技术是3D电视系统中的关键技术, 利用一幅参考图像便能生产任意视点的目标图像, 从而构成立体图像。传统的DIBR系统主要包括三部分:深度图像预处理、三维图像变换和空洞填充。
DIBR系统中的空洞填充模块通过接受目标图像、视差图、绘制顺序及外部参数, 填充目标图像中存在的空洞。本文将对该算法进行具体描述。
2 基于视图差的空洞填充
2.1 匹配误差
深度图像中的前景物体轮廓通常小于相应的参考图像中的对应物体。如图1所示, 将立背景物体的深度值设置为深度图像中前景物体的外围, 在参考图像前景物体轮廓中的A像素点对应于深度图中像素点A′。
由于深度图像中背景物体的深度值通常为深度图像中前景物体的外围, 三维图像在变换后可能出现前景物体边缘与相邻的背景像素的一些点的平移距离一致的现象, 导致深度图像中前景物体的轮廓比参考图像中前景物体的轮廓要小。为校正误差, 本文针对三维图像膨胀由于变换而产生的目标图像的匹配误差, 提出一种基于视察图的空洞填充算法。
2.2 空洞
本文基于DIBR的空洞填充技术算法的基本思想是:按行遍历输入的视差图M, 若连续len_biohole个或以上的像素点为空洞像素点, 则认为此处存在较大空洞。本算法可分为:空洞检测、扩充大空洞、处理小空洞以及填充空洞四个部分。
2.3 空洞检测
按行从左到右的顺序遍历视差图M, 检测空洞, 若视差值为-128, 则目标图像中相同位置的点为空洞像素点, 记录空洞的终点和连续空洞像素点的个数。若连续出现len_bighole个及以上的空洞像素点, 则认为此处是大空洞。
2.4 扩充大空洞
之所以要对较大的空洞进行扩充, 是因为生成的深度图像有较大误差, 为了消除这个不准确性, 就要对大空洞进行扩充。扩充大空洞包括三个步骤:像素点视差图跳变的检测、前景和背景像素的辨别、扩充大空洞。
经过研究发现, 不同视图大空洞出现的位置是不一样的, 例如, 右视图中的空洞一般出现在前景像素点的右边, 而左视图与之相反。因此, 采取对两个视图分开扩充的方法, 以使结果更加准确。
对于左视图来说: (1) 像素点视差图跳变的检测, 首先选择检测的起始位置。在这里将空洞的右边缘作为起始位置, 然后按照从左到右的顺序对左视图对应的视差图上的空洞右边缘进行检测, 记录其视察值的跳变值。 (2) 前景和背景像素的辨别, 对于左视图来说, 利用背景像素的视察值是小于前景像素点这个特性来辨别其前背景像素。如果相邻的非空洞像素点视察值由大变小或者不变, 那么就为前景像素点并将d的值设为空洞右部边缘第一个像素点视差值;相反则为背景像素点, 将d值设为较大的视差值。 (3) 膨胀空洞边缘, 首先根据空洞右边是否为背景像素点判断膨胀需求。若为背景像素点, 则需膨胀空洞两边, 若非背景像素点, 则只需膨胀其左边缘。膨胀过程为:在视差图M中将需被膨胀的像素点对应位置进行标记 (修改视差值为-128) , 如图2所示。假设Il为目标图像的左视图, 在这些像素点中共有空洞像素点有num个, 点Il (u-num, v) 作为背景像素点, 点Il (u+1, v) 作为前景的像素点。当需要膨胀空洞的左边缘时, 根据l确定需要膨胀的像素点个数, 然后对其进行标记 (-128) , 使空洞的长度发生改变, 得到长度为num+l。然而, 在实验处理过程中, 只对空洞的长度和终点进行更新。
处理右视图:在图像的右视图中, 大空洞的出现位置为前景像素点的右侧, 而非左侧, 并且其背景的视差值大于前景。对图像右视图的膨胀处理, 仅对起点位置进行扫描, 总体过程与处理左视图相似。但是, 区分前景的规则与扫描顺序与右视图不一样。
此后膨胀空洞边缘。观察前景像素点的位置, 若左边缘为前景像素点, 则只需要膨胀右侧边缘空洞进;若非前景而为背景像素点, 则需要膨胀空洞两边。
2.5 处理小空洞
小空洞分为两种:第一种是由于在目标图像平面上, 物体的投影扩张而产生;第二种是有可见性变换引起的小空洞。这两种小空洞都不需要膨胀, 直接进行填充即可。
2.6 填充空洞
填充空洞的原理主要是由上一步得到的结果, 即需要填充的空洞的视差值d以及其起、终点, 并由参考图像复制得到对应的像素点, 从而进行空洞填充, 如图2所示。设生成的新视图Ides为参考图像Iref的右视图, 假设Ides (v, u-1) (0≤v≤Hi) 为前景像素点, Ides (v, u+num) 为背景像素点, 其中有num个空洞的像素点处于这两个不属于空洞的像素点中间, 则应该根参考图像Iref, 拷贝背景像素点num个用以填充这些空洞。所描述的区域起点为Iref (v, u-d) , 终点为Iref (v, u+num-1-d) , 其中d为视差图中M (v, u-1) 的视差值, 以完成空洞填充。
摘要：近年来, 3D成像技术得到了广泛应用。其中, 基于DIBR系统的视图合成技术则是3D成像的关键技术, 它能够方便地合成任意视点的视图, 使3D图像具有更强的交互性与真实性。然而, 在生成立体图像时, 根据参考图像及其对应的深度图像进行转换, 由于视点变化导致场景中的遮挡关系发生了变化, 物体的可见性、表面积也会发生改变, 从而产生空洞。
关键词：3D成像,视图合成,空洞填充,深度图像
参考文献
[1]张兆杨, 安平, 张之江, 等.发展3DTV需解决的技术及其应用趋势[J].电视技术, 2010 (6) .
[2]鞠芹, 安平, 张倩, 等.高质量的虚拟视点图像的绘制方法[J].电视技术, 2009, 33 (9) .
[3]戴琼海, 徐秀兵.一种基于深度图的快速图像绘制方法:中国, CN200810105346.2[P].2008-04-28.
[4]骆凯, 李东晓, 冯雅美, 等.基于DIBR和图像修复的任意视点绘制[J].中国图象图形学报, 2010 (3) .
填充算法 篇2
防水套管在安装过程中要对其进行填充，填充物一般采用：沥清、麻丝、聚苯乙烯板、聚氯乙烯泡沫塑料板、密封膏、聚硫密封膏、聚胺脂密对膏等；套管穿墙处如遇非混凝土墙壁时，应局部改用混凝土墙壁，其浇注范围应比翼环直径（D5）大200，而且必须将套管一次浇固于墙内；穿管处混凝土墙厚应小于300，否则应使墙壁一边加厚或两边加厚，加厚部分的直径至少为
D5+200；套管的重量以L=300计算如墙厚大于300时，应另行计算。
防水套管的填充技术：
工程实际中常常发生防水套管堵塞的问题。所以我们必须做到以下几点： 1：现浇楼板、柱内的穿梁套管在配合土建安装完成之后，可以确保后续设备安装有良好的施工环境。防止沙浆进入套管和接线盒引起堵塞。
2：为防止室外地下水或雨水通过防水套管进入地下室，因此，地下室出外墙处防水套管除采用软性物封堵外，在防水套管预制加工时，应在套管一端端口采用钢板焊接封堵，待防水套管管道安装时再开启。
3：管道穿防水外墙，应随结构预埋刚性或柔性防水套管。
4：管道穿墙处、穿楼板处、穿屋面处应随结构预留洞，待结构施工完毕后再进行套管埋设，穿墙预留套管时两端一定要用胶布等密封好。
填充算法 篇3
关键词：计算机图形学,圆,区域填充,Bresenham算法
计算机图形学是研究如何用计算机生成、处理和显示图形的一门学科[1,2]。随着计算机图形学的不断发展, 其应用范围日趋广泛。在计算机显示器屏幕上生成的任何图形都是像素点的集合。圆内区域填充的过程实质上就是寻找最佳逼近给定圆心和半径的圆周范围内的像素点序列, 并向图形卡帧缓存器的相应单元填入颜色数据的过程。作为最低层的计算机图形、图像处理算法, 圆内区域填充算法大量应用于计算机辅助设计与制造、计算机软件用户接口、计算机动画和艺术等领域。因此, 对圆内区域填充算法进行研究, 有着非常重要的意义。
1 基于种子点的圆内区域填充的递归算法
1.1 算法的基本思想[1,2]
基于种子点的圆内区域填充的递归算法是比较经典的算法。其基本思想是:先将圆内区域的一点赋予指定的颜色, 然后将该颜色递归地扩展到整个圆内区域。该算法要求区域是四连通区域和八连通区域。即要求从区域上一点出发, 通过上下左右4个方向的移动组合或上下左右、左上、右上、左下、右下8个方向的移动组合, 在不越出区域的前提下, 能到达区域内的任意像素点。
圆内区域可用内点 (圆内区域的像素点) 表示或边界 (圆周线上的像素点) 表示。因此, 基于种子点的圆内区域填充的递归算法对当前点是否需要进行递归填充的判断标准有两种:一是当前点是旧颜色的内点, 则对它进行递归填充;二是当前点既非已填充为新颜色的内点也非边界点, 则对它进行递归填充。
基于种子点的圆内区域填充的递归算法可以分为四种:内点表示的四连通区域递归填充算法、内点表示的八连通区域递归填充算法、边界表示的四连通区域递归填充算法、边界表示的八连通区域递归填充算法。由于八连通区域的递归填充算法过程非常缓慢, 且有可能出现所填像素点出界的现象[2], 所以, 实际常用四连通区域的两种递归填充算法。
1.2 算法的函数实现
1.2.1 内点表示的四连通区域的递归填充算法
假设 (x, y) 为圆内区域内的一点, oldcolor为圆内区域填充前的颜色, 需将整个圆内区域填充为新颜色newcolor。内点表示的四连通区域的递归填充算法的实现函数如下:
1.2.2 边界表示的四连通区域的递归填充算法
假设 (x, y) 为圆内区域内部的一点, boundarycolor为原圆内区域边界的颜色, 需要将整个圆内区域填充为新的颜色newcolor, 则可以构造边界表示的四连通区域的递归填充算法的实现函数如下:
对于内点表示的八连通区域以及边界表示的八连通区域的递归填充算法的实现函数只需要将上述两段四连通区域的递归填充算法的实现函数代码中增加左上、左下、右上、右下四个方向相邻的像素点的递归调用函数即可。
1.3 算法的不足
递归算法实现时, 计算机系统自动设置和管理系统堆栈。每调用一次递归函数就“入栈”一次, 函数执行完一次, 结果就“出栈”一次。圆内区域填充的递归算法函数的递归调用次数由需要填充的像素点数目决定。所需要填充的区域越广, 所覆盖像素点越多, 函数递归调用次数就越多, 系统“入栈”和“出栈”操作越多, 所消耗的内存空间等系统资源越多, 执行时间就越长。当递归调用次数达到一定数目时, 就会耗尽系统资源, 导致应用程序无法运行。
实际应用中, 对圆内区域进行填充时, 所覆盖的像素点数目一般至少是成百上千、甚至是成千上万的。因此, 用基于种子点的圆内区域填充的递归算法填充时, 不但速度慢, 而且还有可能导致程序无法运行、填充任务无法完成的情况发生。因此, 基于种子点的圆内区域填充的递归算法的应用只局限于需要填充区域较小的情况。
2 基于改进的Bresenham圆生成算法的圆内区域填充新算法
2.1 圆的八对称性
圆心位于原点的圆有四条对称轴x=0, y=0, x=y和x=-y。如果已知圆心在 (xc, yc) 的圆弧上一点 (x, y) , 可以得到该点关于上述四条对称轴的其它7个点 (xc+x, yc+y) 、 (xc-x, yc+y) 、 (xc+x, yc-y) 、 (xc-x, yc-y) 、 (xc+y, yc+x) 、 (xc-y, yc+x) 、 (xc+y, y c-x) 、 (xc-y, yc-x) 。这种性质称为圆的八对称性。由圆的八对称性可知, 生成一个圆时, 只要扫描转换生成该圆上1/8段的圆弧, 就可以求得构成整个圆的像素点集合。
目前, 经典的圆生成算法都基于圆的八对称性。对圆心在原点 (0, 0) 、半径为r的圆, 经典的圆生成算法首先考虑以 (0, r) 为起点, 按顺时针方向生成第一向限的1/8段圆弧的情况。然后, 再根据圆的八对称性, 生成整个圆。生成圆心在 (xc, yc) 、半径为r的圆, 则只需将圆心在原点 (0, 0) 、半径为r的圆作平移就可得到。
2.2 Bresenham圆生成算法的基本思想[1,2]
在经典的Bresenham圆生成算法中, 将圆表示为:y2=r2-x2。如图1所示, 在第一向限的1/8段圆弧上取当前像素点为 (xi, yi) , 那么要取的下一个用于近似精确交点Q (xi+1, y) 的像素点是垂线x=xi+1上的点P 1 (xi+1, yi) 或P 2 (xi+1, yi-1) 。
选择P1或P2的原则是P1与P2中与Q距离最小者。由于距离为正值, 用距离的平方代替距离不影响P1或P2的选择, 所以, 为了提高运算效率, 可以避免开方运算。具体计算式为:
令距离差pi=d1-d2, 并代入d1, d2, 则有:
(1) 若pi≤0, 说明P1与Q距离近, 则应取P1为下一个近似像素点。此时, 下一步以P1 (xi+1, yi) 为当前点时, 再求下一个近似像素点的pi的递推式为:
(2) 若pi>0, 说明P2与Q距离近, 则应取P2为下一个近似像素点。此时, 下一步以P2 (xi+1, yi-1) 为当前点时, 再求下一个近似像素点的pi的递推式为:
(3) 根据起点 (0, r) , 得pi的初始值为:
2.3 Bresenham算法的函数实现
pl ot_ci rc le_po int s (xc, y c, x, y, c) ;
2.4 圆内区域填充新算法的基本思想
使用Bresenham圆生成算法生成圆心在 (xc, yc) 、半径分别由零依次增加一个像素点, 最后变为给定的半径r的多个圆的效果实际就相当对给定圆心 (xc, yc) 和半径r的圆内区域进行填充的效果。因此, 基于Bresenham算法的圆内区域填充新算法的基本设计思想很简单, 只需要设计FOR循环, 从零开始每次增加一个像素点, 直到变为指定要填充的圆半径为止。循环体中直接调用Bresenham算法生成循环控制变量为半径的圆即可。
然而, 实例运行结果显示圆内区域存在较多像素点没被填充到。经过仔细分析, 发现其原因在于:用Bresenham算法生成圆时, 得到当前像素点P (xi, yi) 后, 后继点 (xi+1, yi+1) 只考虑了取P 1 (xi+1, yi) 和P 2 (xi+1, yi-1) 的两种情况。而取P2为后继点时, 中间存在漏点现象。实际上, 在取P2之前, 点P1 (xi+1, yi) 或P3 (xi, yi-1) 也可能是圆弧上的点。如图2所示。
如果P1到圆弧的距离小于P3到圆弧的距离, 则P1为漏点, 应该补上P1;反之, 应该补上P3。现令d3为P3到圆弧距离的平方, 则有:
那么, P1到圆弧的距离平方d1与P3到圆弧的距离平方d3之差为:
当d1-d3>0时, 需要补上的漏点是P3, 否则, 需要补上P1。
2.5 改进Bresenham算法的函数实现
2.6 圆内区域填充新算法的函数实现
由以上两个函数可知, 基于改进Bresenham算法的圆内区域填充新算法只需做整数加法、整数乘2和整数乘4的运算, 并且涉及到的数据结构很简单, 所以, 算法运行速度很快, 适宜于在硬件上实现。
3 实例分析
3.1 实例及其运行结果
给定圆心在 (200, 200) 、半径为100和45的两个圆, 分别使用基于种子点的递归算法、基于Br es en ha m算法和基于改进Bresenham算法的圆内区域填充新算法将此圆内区域填充为白色。假设对应三种算法, 实例分别取名为实例1、实例2、实例3。在酷睿双核2.4G CPU、4G内存的机器上的Turbo C2.0中运行实例1、实例2、实例3。其运行结果如表1、表2所示。
3.2 运行结果比较分析
根据表1和表2对实例运行结果进行比较分析如下。
(1) 表1中实例1运行失败, 体现了基于种子点的圆内区域填充的递归算法的局限性。失败原因是因为半径为100的圆区域所覆盖像素点较多, 函数递归调用次数达到极限, 耗尽系统资源, 导致程序实例无法成功运行。表2中对半径为100的圆区域填充时, 实例1虽然运行成功, 但运行时间远比实例2和实例3多很多。说明算法运行速度显著慢于实例2和实例3。
(2) 表1和表2中实例2的运行结果表明:用基于Bresenham算法的圆内区域填充新算法进行填充时, 虽然运行时间短, 算法运行速度快, 但是随着所需要填充圆内区域的半径增大, 未被填充到的像素点 (显示为黑色的点) 逐渐增多。
(3) 表1和表2中实例3的运行结果表明:用基于改进Bresenham算法的圆内区域填充新算法进行填充时, 运行时间只稍多于实例2, 但是圆内区域能全部被填满。说明该算法不但运行速度快, 而且即使所需要填充圆半径增大, 圆内区域的所有像素点全部能被填充到。
(4) 笔者经过多次尝试发现, 圆半径大于49时, 实例1就无法成功运行, 系统就会提示“TC NTVDM CPU遇到无效的指令选择‘关闭’终止应用程序”。然而, 实例2和实例3即使圆半径取为TC中整型变量的最大值216-1=32767, 都能运行成功, 并且运行速度都很快。
综上所述, 基于改进Bresenham算法的圆内区域填充新算法相对于基于种子点的圆内区域填充的递归算法而言, 具有简单、运行速度快、占用内存空间等系统资源少的优点。
参考文献
[1]潘云鹤, 董金祥, 陈德人.计算机图形学——原理、方法及应用 (修订版) [M].北京:高等教育出版社, 2003, 12:26～37.
填充算法 篇4
协同过滤算法产生推荐具有很多优点, 与传统的基于内容的推荐方法相比, 协同过滤不但可以发现目标用户与其他用户的相似兴趣, 还可以挖掘目标用户新的兴趣, 由于综合考虑了邻居用户的兴趣与评分, 其推荐质量更高[6]。然而, 在愈发深入的研究和广泛的应用中, 协同过滤出现了一些问题, 使得它的预测推荐性能在一定范围内被限制, 比如一直以来存在的推荐结果的准确度问题、原始评分数据的稀疏性问题, 在实际应用的推荐系统中出现了冷启动、扩展性等问题。本文考虑到原始评分数据的稀疏性对协同过滤推荐结果的准确度有较大负面影响, 提出了基于项目特征值分类与预测数据填充的协同过滤推荐算法, 该算法主要将分类技术和空缺元素填充技术应用到协同过滤中, 来对协同过滤推荐模型中的项目进行分类, 一定程度上挖掘了用户对于项目类别的兴趣偏好, 提高了推荐的准确度, 并使用预测评分数据填充原始的稀疏评分矩阵, 在一定程度上缓解了评分数据的稀疏性问题。
1 传统基于协同过滤的推荐算法
传统协同过滤算法分为两类, 即基于用户的协同过滤和基于项目的协同过滤[5], 分别以用户和项目作为衡量评分行为共性的载体, 最后都会产生用户对若干项目的预测评分。基于用户的协同过滤算法是根据具有较高相似度的最近邻居的评分行为与他们共同评分情况, 为用户生成推荐项目。基于项目的协同过滤与基于用户的协同过滤产生预测推荐的原理相同, 只是比较的对象变成了项目。协同过滤产生推荐基于以下两个假设, 一是如果一些用户具有相似的评分行为, 那么他们的兴趣偏好基本相似;二是如果一些用户对某一类中的评分差距较小、比较接近, 那么他们在其他类中也会有相似的评分行为。
相似度计算是协同过滤推荐产生的核心步骤, 以基于用户的协同过滤为例, 主流的相似度计算方法有三种, 皮尔逊相关相似度, 余弦夹角相似度, 修正的余弦相似度。其中余弦相似度如下:undefined
sim (a, b) 取值落在在区间[0, 1]中, sim (a, b) 越大, 表示用户a与b之间的相似程度越高。由于余弦相似度在Movielens数据集下具有更合理的取值分布, 本文选取余弦相似度作为用户间相似性度量方法[6]。
2 基于项目特征分类与填充的协同过滤推荐技术
本文算法改进的思路是针对协同过滤中的矩阵稀疏性与推荐准确度问题, 分别引入了项目分类技术与空缺元素填充技术, 以缓解协同过滤中这两个问题对推荐结果的影响。
2.1 项目的特征分类
在协同过滤推荐模型中, 项目与用户一样自身有许多的基本特征属性, 每个基本特征属性都有若干的类别, 用户对项目属性类别的往往会有一定的偏好倾向。因此, 正确分析并预测出用户对于项目类别的偏好将对预测推荐结果有良好的改善作用。比如电影的属性特征, 电影有较多的属性特征, 其中几个主要的属性特征是电影类型、产地、年代、时长等, 用户对电影的偏好可从这几个属性特征中得到体现。
本文使用朴素贝叶斯分类器[7,8]作为对协同过滤推荐模型中项目的分类方法, 之所以选择朴素贝叶斯分类器是因为它具有很好的健壮性能, 性能相对稳定, 适用于不同特点的数据集, 同时朴素贝叶斯分类在分类的过程中对时间、空间等资源的需求较小, 逻辑结构简单容易实现。
将项目的属性特征抽象为特征向量{A1, A2, ……An}, 向量中的每一个元素表示被抽象的一个属性特征值。用{C1, C2, ……Cm}表示已知的m个类别, 先验概率表示为P (x|ci) , 它是从训练数据集中求得的, 后验概率表示为P (ci|x) , 后验概率以先验概率为依据, 通过贝叶斯公式计算得到:undefined
对象的最大后验概率通过比较得到, 对象的最大后验概率所在的类即可被判定为对象最终所属的类, 计算公式如下:C* (x) =arg max P (x|ci) P (ci)
依据朴素贝叶斯分类器的构造原理及步骤, 分类器算法设计如下:
输入:项目集合I={i1, i2, ……in}, 项目的属性特征向量{A1, A2, ……An}
输出:项目分类结果
(1) 读入训练数据集, 对属性值做格式处理。
(2) 从训练集中提取项目集I和项目的特征属性{N1, N2, ……Nb}计算项目的先验概率分布P (ai|c) 。
(3) 根据训练数据计算类别条件概率。
(4) 依据前面两算法步骤得到的先验概率与类别条件概率计算在某一类别下项目的后验概率P (
(5) 将项目在所有类别下的后验概率分布按大小进行排序, 选取最大值作为项目最终所属的类, 并将分类结果与最大后验概率值保存。其中, 在相关属性值下面计算类别的后验概率分布的公式如下:
P (C=c|A1=a1……An=an) =aPundefined
2.2 矩阵空缺元素填充
根据前面对项目的分类结果, 对项目按一定的属性类别进行归类, 分类后的项目具有这样的特性:同一类中的项目在部分属性内容上具有相似性, 目标项目与同一类中的项目相比具有较高相似度。因此, 对于基于项目的协同过滤预测评分生成中项目之间的相似度计算, 直接计算同一类中的项目相似度sim (i, j) , 从同类项目中搜索项目的最近邻。
使用余弦相似度作为计算目标项目与同类项目之间的相似性度量方法, 如下:undefined
对目标项目与同类项目之间的相似度按大小进行排序, 选出相似度较高的k个项目作为目标项目的最近邻居, 并存储到最近邻居集合J中, 然后综合最近邻居项目与项目自身的被评分数据, 计算用户u对目标项目i的预测评分:undefined
对于生成的基于项目的预测评分, 按评分矩阵中用户与项目的对应关系标记并保存, 然后将这些预测评分填充到原始评分矩阵中对应的位置。
填充后新的评分矩阵R*是后续预测推荐计算的数据依据, 对于填充技术的引入对推荐结果的改善作用将通过实验中平均绝对误差的变化来体现。
2.3 基于用户的协同过滤推荐生成
根据前面的准备工作, 改进的协同过滤算法步骤如下:
Step1, 获取填充后的评分矩阵R*, 以R*为作生成预测评分的历史评分数据;
Step2, 计算用户间的相似度, 形成用户相似度矩阵Rs;
Step3, 根据相似度矩阵得到用户的候选邻居集合B’, 然后根据实验的需要选取相似度较高的k个邻居作为最近邻居集合B;
Step4, 是基于用户的协同过滤预测评分的生成。计算公式如下:undefined
其中, Pa, i表示用户a对项目i的预测评分, Ra表示的是用户a对所有项目的平均评分, 集合B是用户最近邻集合, 最近邻居集合是预测评分产生的关键性数据。
3 实验与结果分析
3.1 实验数据集与评价标准
本文使用协同过滤通用数据集Movielens作为实验数据, 它是一个关于用户对电影的评分数据集合, 包含了943个用户对1682个电影项目10 0000条左右的评分。数据来源于Grouplens研究组工作人员开发的一个在线推荐系统。
Movielens具备了其他评分数据集的特点, 那就是评分数据的极度稀疏性。根据实际的评分数据与用户电影项目数量, 评分矩阵的稀疏度为93.7%。
本文实验中采用平均绝对误差、覆盖率、命中率三种指标作为改进型协同过滤算法性能的评价标准。三种评价指标的计算方法如下。
平均绝对误差 (Mean Absolute Error) :undefined
其中, 预测评分为p1, p2, ……pn, 历史评分矩阵中的真实评分为q1, q2, ……qn。
覆盖率 (Coverage) :undefined
其中, ku为预测评分集合p1, p2, ……pn中不为空的项目数, nu为客户要求做出的评分项目数。
命中率 (Hite Rate) :undefined
其中, Nu为预测评分集合p1, p2, ……pn中pi>=3.5及用户喜欢的项目, L原始评分数据q1, q2, ……qn中为用户真正喜欢的项目数。
3.2 实验结果
对比实验是将本文的改进算法与传统基于用户的协同过滤和传统基于项目的协同过滤实验结果进行对比。在以Movielens为研究数据集的条件下, 分别以MAE、Coverage、HitRate作为算法预测结果的评价标准, 结果如图1, 图2, 图3。
图1是三种算法在Movielens数据集下平均绝对误差 (MAE) 的比较结果。从图中可以看出, 三种算法的MAE值都随着用户最近邻居个数k的增加而呈减小的趋势, 但改进算法的MAE具有更好的表现, 表明改进算法中预测评分更加接近真实评分值, 误差更小, 一定程度上提高推荐结果的准确度;图2是预测评分中项目覆盖率的比较, 从图中可以看出, 三种算法的Coverage值随着最近邻居用户个数k的增加, 改进算法在项目的覆盖率方面有小幅的优势;图3是预测评分结果中项目命中率的对比结果, 可以看出命中率会随着最近邻居个数的增加而呈递增的趋势, 改进算法在满足用户预期的实际需求方面表现得更好。通过对命中率的衡量, 可以跟踪用户对推荐结果的满意度, 对提高推荐服务具有一定的实用价值。
4 结论
本文针对协同过滤推荐算法中存在的评分矩阵稀疏性问题和推荐准确度问题, 提出了一种基于项目特征分类与预测评分数据填充的协同过滤推荐算法。本文在充分发挥了项目分类与空缺元素技术优势的基础上, 实现了改进的协同过滤算法, 并对改进算法的性能进行多方面、多角度的对比与分析。结果表明, 基于这两种技术的协同过滤算法能有效缓解评分矩阵稀疏性对预测结果消极性影响, 提高了评分预测的准确度和推荐的质量。
摘要：网络化与信息化社会具有信息海量化和用户需求个性化的特点, 如何通过有效手段过滤掉与目标用户不相关的信息, 筛选出对用户有用、能满足用户需求的信息成为信息研究领域的重要课题。本文针对协同过滤中存在的评分数据稀疏性与推荐准确度问题, 提出了一种基于项目特征值分类与空缺元素填充的协同过滤算法。实验结果表明, 改进的协同过滤算法能有效的缓解评分数据稀疏性对推荐结果的负面影响, 在一定程度上提高了推荐的准确度。
关键词：推荐算法,协同过滤,项目分类,填充
参考文献
[1]曾春, 邢春晓, 周立柱等.个性化服务技术综述[J].软件学报, 2002, 13 (10) :1952-1961
[2]邓爱林, 朱扬勇, 施伯乐等.基于项目评分预测的协同过滤推荐算法[J].软件学报, 2003, 14 (9) :1621-1628
[3]许海玲, 吴潇, 李晓东等.互联网推荐系统比较研究[J].软件学报, 2009, 20 (2) :350-362
[4]刘芳先, 宋顺林.改进的协同过滤推荐算法[J].计算机工程与应用, 2011, 47 (8) :72-75
[5]黄裕洋, 金远平.一种综合用户和项目因素的协同过滤推荐算法[J].东南大学学报 (自然科学版) , 2010, 40 (5) :917-921
[6]嵇晓声, 刘宴兵, 罗来明等.协同过滤中基于用户兴趣度的相似性度量方法[J].计算机应用, 2010, 30 (10) :2618-2620
[7]Cheng H, Yong F, Liang L, et al.A static detection model of malicious PDF documents based on naive Bayesian classi-fier technology[C]//Wavelet Active Media Technology and Infor-mation Processing (ICWAMTIP) , 2012International Conference on.IEEE, 2012:29-32
填充算法 篇5
利用规则矩形网格和不规则三角网TIN(Triangulation Irregular Network)方法可以生成等值线,对等值线围成的区域进行颜色填充能够使等值线图更直观地反映区域的属性值范围。为了使等值线图准确反映数据分布情况,需要找到一种合理的算法生成并填充等值线。
传统的等值线生成与填充通常采用规则网格法,但很多时候需要在一个不规则空间内生成等值线,即离散数据点坐标分布没有规律性。此时,如采用规则矩形网格方式绘制等值线,首先需要采用插值法将不规则离散点集变为规则网格离散点集,但等值线的走向往往与实测有一定偏差。而采用三角网方法生成的等值线能很好地解决这一问题。
郑元满等[1]通过样本点与等值线属性值比较来填色,简化了填色过程,但是采用矩形网格追踪算法生成等值线,偏离原始数据分布情况。张登荣等基于等值线的拓扑关系实现等值线填充[2],通过拓扑树可以矢量填充等值线区域,但是没有给出颜色确定方法。韩丽娜[3]等采用双属性法来进行区域的颜色确定,通过围成区域的等值线平均值确定区域颜色,方法简单,但是颜色与区域属性值有一定偏差。李强等[4]针对温度分布等值线利用围成区域的属性值变化趋势来判断区域颜色,对于由显著趋势的等值线图可以准确填色,但是不能适应复杂趋势情况。刘冬韡等[5]通过等值线分类确定填色顺序,引入格点数据进行颜色确定,填色准确,但是对于含大量闭合区域的等值线图填充过程较慢。
为此,本文给出了一种基于不规则三角网的等值线图填充方法,采用逐点插入法生成TIN的方式绘制等值线,无需对离散数据网格化,更能精确反映离散数据分布情况。并通过两点属性值比较与深度优先搜索的方法确定填充区域颜色,填色准确,效率较高。
1 算法原理与数据结构定义
生成等值线图并填充颜色,主要是在原始离散数据的组成的空间点集上用逐点插入法建立TIN[6],采用线性插值法生成所有等值线[7,8],确定填充区域的轮廓与颜色,再进行矢量填充。
等值线图中的填充区域可以分为开区域和封闭区域两类,其中,开区域由一条或几条等值线与等值线图边界的子线段确立,闭合区域由一条封闭的等值线确立。等值线图可以既含有开区域也含有闭区域,也可以只含有开区域或者只含有闭区域,需要分情况进行填充。
这里定义一条等值线即为单等值线,则未填充颜色的等值线图G拥有n种具有不同Z值(属性值)的等值线,且每种等值线有mi(mi≥1)条单等值线。则:
其中,Contourline_Si为Z值为Zi的等值线集合,Boundary Lines为边界线集合,Single Linej为Contourlines_Si中的第j条单等值线。
算法采用C++实现,具体数据结构定义如下:
数据结构1单等值线集数据结构
其中,SINGLELINE为自定义的一个具有属性的单条等值线的数据结构:
数据结构2单等值线数据结构
其中,Cline为一个线段类。
2 填充算法
对于等值线图的填充,关键是要确定开区域或封闭区域的颜色,这需要建立一张颜色表,通过等值线属性值与颜色的对应关系来确定填充区域颜色。
2.1 颜色表的建立
具有n+1种颜色的等值线图应包含n种具有不同Z值的单等值线集。据此,可以为等值线图建立一个具有n+1个颜色值的并且按所表示Z值大小升序排列的颜色表Color Table(即一个颜色数组Color[n+1])。Color Table与按属性值升序排列分类的单等值线集数组Contourline[n]的构成及对应关系如图1所示。
具体颜色值Color[i]、Color[i+1]与属性值为Zi的单等值线集合Contourline[i]具有对应关系,可以表述为:在属性值为Zi的单条等值线两侧的区域颜色为Color[i]和Color[i+1]。通过这种关系,便可以确定由等值线围成区域的颜色。
2.2 含有开区域的等值线图填充
首先,利用线性插值法可以绘制出所有等值线。基于TIN中三角形边采用线性插值法生成等值线的公式为:
其中,(x1,y1)、(x2,y2)分别为三角网一边两个端点的坐标,z1、z2为该边两个端点的属性值,x、y为在该边上插入等值点的坐标,z为该等值点的属性值。生成的单等值线集数组为Contourlines[n]。
然后,找到TIN的边界点集,把所有单等值线端点插入到该点集中,对新点集逆时针排序,利用边界点追踪算法生成一个新的开区域轮廓[9],采用深度优先策略对开区域及其内部的封闭区域进行颜色的确定与填充。
对所有开区域及其内部的封闭区域都按上述方法进行操作,便完成了整个等值线图的填充。流程如图2所示。
2.2.1 边界点集合的生成
对TIN内的每个三角形存储三个边的邻接三角形信息。如果一个三角形的某条边没有邻接三角形,则该条边即为TIN的边界子线段。此时,TIN的边界由在原始数据点集中并且在边界子线段上的点连接而成,设该点集为ST。
由于非封闭等值线的首尾两个端点必定落在边界上,如果设集合中所有的单等值线Single Line端点集合为SL,生成等值线之后,连成边界的点集应为:
如图3所示,将该点集按空间关系逆时针排序,并存储在有序边界点列表S'中。
2.2.2 开区域的填充
1)确定开区域轮廓
利用边界点追踪填充区域的方法,确立一个由非闭合等值线和边界线段组成的开区域Ri。并设该区域轮廓点集中的第一个在S'中并且是单等值线端点的点为A。然后,找到S'中排在点A前面的一个点,设为A'(若A为S'中第一个点,则A'为S'中的最后一个点)。
2)确定开区域颜色并填充
开区域包括两种模式:
模式1由Z值为zi的等值线组中的一条单等值线和边界中的线段围成(如图4中单等值线L1和边界线段Lc1、Lc2围成的区域R1);
模式2由Z值为zi和zi±1的两个等值线组中的一条或多条单等值线和边界线段围成(如图4中单等值线L1、L2、L3和边界线段Lc3、Lc4、Lc5围成的区域R2)。
文献[10]通过围成开区域等值线属性值个数与大小确定颜色,需要知道区域轮廓所有等值线的属性值,计算量大,为此,本文通过两点比较法来确定开区域颜色。方法如下:
(1)如图5(a)所示的区域Ri,A'∈ST,即点A'不是等值线端点,而是三角网点。此时,由于A'在填充区域Ri的内部,如果设点A所在单等值线的索引比较Z(A')与Z(A)的大小,如果Z(A')>Z(A),则Color(Ri)=Color[i+1],如果Z(A')<Z(A),则Color(Ri)=Color[i],然后用颜色Color(Ri)对区域Ri进行填充。算法如下:
算法1
其中,Contourline Index(Z(A))为A点所在单等值线集在Contourline[n]中的索引,Fill(Ri,Color(Ri))为填充区域函数。
(2)如图5(a)中的Ri'所示单等值线与边界线段围成开区域情况。由式(3)、式(4)可知,单等值线两头必然落在两条不同的三角网边上,所以Ri'轮廓中,必然有一个以上的集合ST中的点。所以单等值线围成区域的颜色值可以由算法1确定。
(3)如图5(b)所示,A'∈SL,即点A'为单等值线端点。此时,A'为单等值线上的点,但是,如果在线段A A'上取一个虚拟的点A″,则A″的Z值有两种情况:一是Z(A″)>Z(A),二是Z(A″)<Z(A)。由式(3)、式(4)可知,Z(A)到Z(A″)再到Z(A')应为单调递增(或递减)的,则Z(A″)和Z(A)的大小关系与Z(A')和Z(A)的大小关系相同。由于A″在填充区域Ri内,则可以利用算法1进行区域填充。
上述方法(1)-方法(3)中,Z(A)>Z(A')或Z(A)<Z(A'),而Z(A)==Z(A')的情况不可能发生。证明过程如下:
如果如图5(a)所示,A'∈ST(即A'为原始数据点)或者如图5(b)所示,A'∈SL(即A'为等值线上的点),则A、A'必然在TIN中同一个三角形的同一条边上(如果A、A'在TIN中三角形的两条不同的边上,则A、A'之间必定有一个三角形边的顶点属于集合ST)。此时,由于采用的等值线生成算法为线性插值法,则该边上的任意两点属性值必然不等,即点A、A'的属性值必然不相等。
这样即使不知道围成开区域所有等值线的属性值也能确定开区域颜色。
2.2.3 封闭区域的填充
对于封闭区域的填充,无论是文献[3]提出的双属性算法还是文献[4]提出的趋势判断法,都无法对内部不包含子封闭区域的封闭区域的颜色进行准确判断。为此,本文给出一种利用已填充区域颜色值,逐级进行深度遍历填充子封闭区域的方法。
如图6所示,L1或L3围成的封闭区域R1、R3被区域Ri所包围,如果两个区域之间只隔着一条单等值线即为相邻区域,则区域R1、R3与Ri是相邻的,并R1、R3为Ri的一级子封闭区域。同样的,R2与Ri不相邻,与R1相邻,为R1的一级子封闭区域,且说R2为Ri的二级子封闭区域,R4与R2类似。一个开或闭区域的多级子封闭区域的定义以此类推。由于含有开区域的等值线图中的封闭区域一定是由某一个开区域包含的,所以只要对所有开区域的一到多级子封闭区域逐级填充便可以完成整个等值线图的填充。下面结合图6给出的具有代表性的示例,对一个开区域及其内部所有子封闭区域逐级填充的具体方法。
设图6中的开区域Ri为当前已填充区域R,并设Color(Ri)的颜色表索引为i,即Color(Ri)==Color[i]。由图1所示单等值线与颜色的对应关系可知,R的一级子封闭区域颜色为Color[i+1]或者Color[i-1]。如果一级子封闭区域的颜色为Color[i+1],则其轮廓为单等值线集Contourline[i].Single Lines[mi]中的一条单等值线,如果颜色为Color[i-1],则其轮廓为Contourline[i-1].Single Lines[mi-1]中的一条单等值线。找到单等值线集Contourline[i].Single Lines[mi]和Contourline[i-1].Single Lines[mi-1]中被Ri的轮廓包含且围成区域与R相邻的封闭单等值线即为R的一个一级子封闭区域轮廓。
判断Contourline[i].Single Lines[mi]或者Contourline[i-1].Single Lines[mi-1]中的一条单等值线Lt围成区域Rt与R相邻与否的具体方法为:如果Lt(图6中的L1、L3)不被其他同属性值的封闭单等值线包含,则Rt为R的一级子封闭区域(图6中的R1、R3)轮廓,对Lt围成的区域Rt进行填充;如果Lt(如图6中的L2)被其他同属性值的一条封闭单等值线(图6中的L1)包含,而且包含Lt的这条同属性值单等值线围成的区域(设为图6中的R1)没有被填充,则代表Lt围成区域Rt与R不相邻,暂不对其进行填充。
在对图6中Ri的二级子封闭区域R2、R4填充时,可以递归地将当前区域R由Ri换为R1及R3,再对R的一级子封闭区域进行填充操作即可,同样地,Ri的多级子封闭区域也采用类似方法进行填充,直到当前区域R没有相邻子封闭区为止。
2.3 不含开区域的等值线图填充
有时等值线图中只包含封闭区域,如图7所示。这种情况下,由于等值线图边界上没有等值点,需要把边界当做一个特殊的开区域RS进行填充。由于边界中必然包含一个三角网点PS,由图1可知,只需比较PS的属性值Z(PS)与单等值线集数组Contourline[n]中的Contourline[i]属性值Z(Contourline[i])大小即可确定RS的颜色。例如,如果Z(PS)>Z(Contourline[i])且Z(PS)<Z(Contourline[i+1])(i≥0,i≤n-1),则RS的颜色为Color[i+1]。再按照2.2.3节所述方法,即可完成RS内部封闭区域的填充。
2.4 复杂度分析
本文算法对开区域的填充采用两点属性值比较方法,在等值线图由t个开区域,且每个开区域由k条非封闭等值线围成的情况下,仅需进行属性值的t次比较就能确定开区域颜色,时间复杂度为O(t)。对于封闭区域的填充,算法采用深度优先搜索方式确定区域颜色与填充,填充一个封闭区域需对其在属性值上相邻的单等值线集进行遍历。如果等值线图含有n种属性等级,每种等级有m条封闭等值线,算法对封闭区域填充的时间复杂度应为O(nm2)。算法的总时间复杂度为O(t)+O(nm2)。但经过大量数据分析发现,当n线性增长时,t也呈线性增长且速率与n一致,但k、m往往保持在常量水平,故算法的实际时间复杂度为O(n)+O(n)即O(n)。
文献[10]对开区域的填充须记录所有等值线属性值,时间复杂度为O(kt),对封闭区域的填充通过三角网中线段与等值线的空间关系及属性值比较来确定区域颜色,时间复杂度为O(nm),总时间复杂度为O(kt)+O(nm),由上述分析可知,实际时间复杂度应为O(n)+O(n)亦即O(n)。但三角网生长方法效率较低[6],已经很少有人使用,本文算法采用逐点插入法生成三角网,故本文算法在实用性上更高。
3 实验
采用C++与Open CV编程实现上述算法。图8为通过对一组数据20种不同属性等级的等值线图进行本文算法实现的耗时曲线,从中可以看出算法时间复杂度为O(n)这与2.4节分析的一致。
图9为采用边界扫描算法填充的包含开区域等值线图,该算法不能对闭区域进行填充。图10为利用本文给出方法对包含开区域等值线图的填充结果。可以看出,本文方法准确地填充了封闭区域。
图11为采用文献[10]提出的基于逆生长三角网算法填充的不含开区域等值线图,可见不能对等值线图的边界围成的区域进行填充。图12为采用本文方法填充的不含开区域的等值线图。通过对比可以看出,本文方法对于包含或者不包含开区域的等值线图均能进行较好的填充。
4 结语
本文先采用逐点插入法生成TIN,再生成等值线,充分发挥了TIN方式生成等值线更忠实于原始离散数据分布情况的特点,确保了等值线图的精确性。同时,采用两点属性值比较法判断开区域颜色,采用深度优先遍历方式,根据当前等值线的属性值逐层对包含的封闭区域进行颜色判断。对于一些颜色走势不显著与走势复杂的情况也能够进行很好的填充,且能够对不含开区域的等值线图进行填充。本文实现了对基于TIN生成的等值线图的精确绘制。
通过程序实现,证明了该方法简单、可靠,为等值线图的填充算法研究提供了一个有效参考,且能在地理信息系统开发中得以较好应用。此外,本方法应用在了瞬变电磁探测数据的成图与识别系统中。
摘要：现有基于不规则三角网的等值线填充算法较少,且不能精确判断区域颜色。对此给出一种通过不规则三角网快速填充等值线图的算法,搜索出所有开区域轮廓,通过围成区域等值线属性值与不同颜色的对应关系确定区域颜色,采用深度优先的方法对开区域及其内部的多级封闭区域进行矢量填充。对不同数据源运行该算法,并与其他算法进行比较,根据对比结果可知该算法比现有算法更适合于基于三角网生成的等值线图精确填充。
关键词：等值线图,颜色填充,三角网,对应关系,深度优先
参考文献
[1]郑元满,姚长利,张晨,等.基于等值线拓扑走向的快速区域填充算法[J].石油地球物理勘探,2010,45(6):899-908.
[2]张登荣,刘绍华,毛天露,等.等值线自动建立拓扑关系算法与快速填充应用[J].中国图象图形学报,2001,6(3):264-269.
[3]韩丽娜,石昊苏,张群会.基于边界点追踪的等值线图区域填充算法[J].计算机工程与科学,2006,28(11):66-67.
[4]李强,李超,甘建红.基于三角网的等值线填充算法研究[J].计算机工程与应用,2013,49(5):185-189.
[5]刘冬韡,戴建华,林红,等.基于等值线分类的区域填充算法[J].气象科技,2009,37(5):597-600.
[6]余杰,吕品,郑昌文.Delaunay三角网构建方法比较研究[J].中国图象图形学报,2010,15(8):1158-1167.
[7]付晓东,赵俊三,马绍雄.不规则区域内基于D_TIN的等值线生成算法[J].昆明理工大学学报:理工版,2006,31(6):46-50.
[8]陈宏文,曾繁彩,王刚龙,等.改进Delaunay三角网格等值线提取方法[J].热带海洋学报,2013,32(4):92-96.
[9]康建荣.不规则区域等值线拓扑关系的建立及充填算法[J].测绘通报,2004(9):7-9.