第41卷 第2期2007年2月
西 安 交 通 大 学 学 报
J OU RNAL O F XI′AN J IAO TON G UN IV ERSIT Y
Vol.41 №2
Feb.2007
一种基于混合层次包围盒的快速碰撞检测算法
刘晓东,姚兰,邵付东,王颖
(西安交通大学电子与信息工程学院,710049,西安)
摘要:提出了一种基于混合层次包围盒(BV H)的快速碰撞检测算法,它将固定方向凸包(FD H)包围盒与沿坐标轴方向的包围盒(AABB)相结合,吸收了基于图像的碰撞测算法的优点,利用了图形硬件的计算能力.算法在预处理阶段为待测物体的凸块构造FD H包围盒树,然后在逐步求精的过程中遍历该树并进行初步碰撞检测,最后通过建立AABB包围盒快速设置视域参数,在对凸块绘制的同时进行精确求交,实时得到碰撞检测的结果.实验结果表明,所提算法可以较好地解决形状复杂刚体的实时碰撞检测问题,检测速度比经典算法RA PID和RECODE分别提高了约17%和20%.
关键词:实时检测;层次包围盒;固定方向凸包;刚体碰撞
中图分类号:TP391 文献标识码:A 文章编号:0253Ο987X(2007)02Ο0141Ο04
F ast Collision Detection Algorithm B ased on Mixed BVH
Liu Xiaodong,Yao Lan,Shao Fudo ng,Wang Y ing
(School of Electronics and Information Engineering,Xi′an Jiaotong University,Xi′an710049,China)
Abstract:A fast collision detection algorit hm based on mixed hierarchical bounding volumes (BV H)is p ropo sed,which combines t he quality of co mpact ness of t he fixed direction hull(FD H) wit h t he simplicity of AABB,absorbs t he merit s of image2based collision detection algorit hm, and utilizes t he comp uting capabilities of grap hic hardware.In t he p reliminary period t he FD H t ree of t he object s is established.Then t he t ree is t raversed and t he original detection is carried out simultaneously.Subsequently,t he AABB of t he object is established to set t he view parame2 ter,and t he detection result could be obtained in real time when t he convex pieces of t he object s are drawn.The experimental result s demonst rate t hat t he p roposed algorit hm works well in t he collision detection for complexly shaped rigid2body,and t he speed of t he collision detection is im2 proved by about17%and20%compared to t he t raditional algorit hms RA PID and RECOD E.
K eyw ords:real2time detection;hierarchical bounding volumes;fixed direction hull;rigid2body collision
随着虚拟现实、分布式交互仿真等技术的兴起,碰撞检测问题开始成为研究的热点.碰撞检测算法在空间采样方式上可划分为基于物理空间和基于图像空间两大类,在前一类算法中,基于层次包围盒树的方法是研究的热点.具有代表性的包围盒有沿坐标轴方向的包围盒(AABB)[1]、方向包围盒(OBB)[2]以及固定方向凸包(FD H)[3].利用包围盒可以将碰撞检测问题简化,但是紧密性好的包围盒计算相对复杂,简单性好的包围盒精确度不够,这两类包围盒均难以同时满足速度和精确度的要求.基于图像空间的碰撞检测算法[4Ο5]能有效利用图形硬件的绘制加速功能,但是这种方法在对物体的所有凸块进行绘制时没有经过预先的筛选,在一定程度上影响了检测效率.
收稿日期:2006Ο05Ο29. 作者简介:刘晓东(1954～),男,副教授. 基金项目:国家高技术研究发展计划资助项目(2003AA209021).
本文给出了一种将FD H、AABB层次包围盒和图像空间相结合的碰撞检测算法,在不影响碰撞检测精确性的前提下,它的检测速度比以往的算法有较大的提高.
1 算法实现
整个算法分为预处理、逐步求精、精确求交3个阶段.算法的输入为三维空间中的2个物体,输出为2个物体的碰撞检测结果,即True(相交)或False (不相交).
111 预处理阶段
预处理阶段的主要工作是将物体对的每个对象分解为凸块,构造凸块的FD H层次包围盒树,并对凸块进行三角形带压缩编码,以便于提高后2个阶段的效率.工作步骤描述如下.
步骤1:对2个物体分别进行表面凸分解,得到一组凸片集合,并针对每一凸片构建与其相应的凸块.本文采用对偶图搜索方法和增量凸片算法来搜索凸片集合[6].
步骤2:采用自顶向下的策略将凸块集合组织为层次二叉树.从凸块集出发,以全集作为根结点,利用基于全集信息递归对这个结点进行划分以形成其子结点,直至到达叶结点.
步骤3:为层次树中每个凸块构建一个FD H包围盒.具体方法如下:①选定固定方向集D k,本文取D14={±(1,0,0),±(0,1,0),±(0,0,1),±(1,1,1),±(1,-1,1),±(1,1,-1),±(1, -1,-1)};②计算凸块集S中的顶点与固定方向集D14中各个方向的最大点积,得到凸块集的FD H 包围盒.
步骤4:对层次二叉树上的所有节点的凸块进行三角形带压缩编码.采用Isenburg的启发式搜索法[7],一次性地对层次二叉树中的每个结点凸块的三角形网格进行处理,得到比较理想的三角形带,并对这些三角形进行压缩编码.
112 逐步求精阶段
建立好FD H树之后,算法在逐步求精阶段会同时遍历环境对象和活动对象的层次凸块二叉树,检测凸块节点所对应的FD H包围盒是否相交. 11211 层次二叉树的遍历 遍历算法在预处理阶段已为物体对的每个对象各构造了一个层次二叉树,层次树的每个结点表示一个由FD H包围盒包围的凸块.因此,检测2个物体是否相交可通过同时递归遍历它们的层次二叉树来确定,遍历的过程主要由一个递归调用函数Traverse Tree(V E,V F)来实现.遍历算法如图1所示,其中V E为环境对象包围盒树中的当前结点,V F为活动对象包围盒树的当前结点,该过程的输入为环境对象包围盒树的根结点E和活动对象包围盒树的根结点F,S E和S F分别为结点V E和V F所对应的凸块,b(S E)和b(S F)分别为它们的包围盒
.
图1 层次二叉树的遍历算法
11212 包围盒间的相交测试 由于所有的FD H 都由同一个固定方向集合D k中的k/2个方向相反的向量对来定义,故一个FD H完全可以在k/2个方向轴的投影区间上定义.对于FD H的相交测试,可采用区间重叠测试法[3],即:如果2个包围盒在k/2个固定轴上的某个轴的投影区间不重叠,就可以判定这2个包围盒不重叠,包围盒的曲面也必定不相交;如果在所有方向上的投影区间都重叠,认为2个包围盒相交.
113 精确求交阶段
算法在逐步求精阶段检测到2个凸块包围盒相交后,需要进一步断定这2个凸块是否相交,这个过程就是精确求交.在这一阶段,算法首先基于AABB 包围盒设置视域参数,再进行凸块相交测试,得到碰撞检测结果.
11311 基于AABB的视域参数设置 为了提高精确求交阶段的效率,算法为2个凸块重新建立AABB包围盒,因为AABB简单,易于为绘制过程设定相应的视域参数,而FD H的方向轴过多,不便于设定这些参数.
AABB包围盒可用各个坐标轴上的最小、最大值所限定的区域来表示[1],即
R={(x,y,z)|l x≤x≤u x,
l y≤y≤u y,l z≤z≤u z}(5)
241西 安 交 通 大 学 学 报 第41卷
式中:l x 、l y 、l z 分别为x 、y 、z 轴上的最小值,u x 、u y 、u z 分别为x 、y 、z 轴上的最大值,这些值均为区域内点的边界.
绘制所用到的视域参数包括相机位置、视线方向、视口大小和投影矩阵,而本文的投影方式采用平行投影.设置视域参数的步骤如下.
步骤1:分别为2个凸块建立AABB 包围盒.步骤2:在3个坐标轴中,将AABB 包围盒的重叠区间最长的一个坐标轴方向确定为视线方向,剩余的2个重叠区间构成一个矩形,将这个矩形作为视口.
步骤3:依据视线方向、视口大小和AABB 包围盒的尺寸来设定相机位置.相机在视线方向的坐标值为-∞,在其他2个方向的坐标值与视口中心坐标值相同.
例如,建立2个AABB 包围盒,假定它们在z 轴上重叠区间最长,则z 方向被设定为视线方向,而x 和y 方向上的重叠区域被设定为视口,如图2所示.根据2个包围盒在x 、y 方向上的最大、最小值,可以得到视口的范围
.
图2 视域参数设置
设视口γ={(x ,y )|l vx ≤x ≤u vx ,l vy ≤y ≤u vy },
则相机位置由坐标(C 1,C 2,-∞
)来确定,其中C 1=(l vx +u vx )/2C 2=(l vy +u vy )/2
利用FD H 的相交检测结果建立AABB 包围盒,可以迅速实现视域参数的设定,从而达到加快绘制过程的目的.
11312 凸块之间的相交测试 2个凸块之间的相
交测试是在图形硬件绘制过程中实时进行的,主要用到了深度缓存和模板缓存.本文通过比较重叠像素的深度值来修改模板缓存值,再根据模板缓存值来确定凸块是否相交.
假设z 轴为视线方向,用R xy (x )表示物体在
x Oy 平面上的垂直投影区域,用I z (x )表示物体在z
轴上所占的区间.那么,2个凸块A 、B 发生碰撞时
当且仅当下式成立[5]
R xy (A )∩R xy (B )≠ ,I z (A )∩I z (B )≠ 对A 、B 而言,在某像素上的z 轴区间的重叠情况有8种.当只比较A 的正面与B 的前、后面之间的位置关系时,可进一步将8种情况归纳成为4类[8],并且可用模板缓存值0～3进行区分,如图3所示
.
图3 A 正面与B 的位置关系
凸块相交测试步骤如下.
步骤1:在已设置的视域下,采用背面剔除的方式来绘制A ,将A 在投影区域内的所有像素的模板
缓存值置1,并将其最大深度值d A
max 写入相应的像素深度缓存.绘制时,通过实时解码绘制以三角形带编码保存的凸块.
步骤2:将B 分正面和背面进行2次三角形带解码绘制.每次绘制时,检测B 的投影区域满足模板缓存值为1的像素点,并将B 上该像素点的深度值d B 与当前深度缓存中的值进行比较,若前者小于后者,则该像素的模板缓存值加1.
步骤3:查询视域中所有的像素模板缓存值,若均小于或等于1,则A 、B 不相交,返回False ;若发现至少有一个值为2,则A 、B 相交,返回True ;其他情况,执行步骤4.
步骤4:将A 和B 的角色互换,重复步骤1～步骤3,最终确定A 、B 是否相交.
2 算法复杂度分析
下面从构造FD H 包围盒树的时间开销和对存储空间的要求进行比较分析.
对于不同的包围盒类型,计算复杂度主要取决于其构造过程和相交测试的复杂度.本文算法采用的FD H 包围盒,固定方向集取D 14,所以构造凸块集合S 的FD H 的时间复杂度为O (14n )(n =|S |),而每对FD H 间的相交测试需要14次比较运算.OBB 包围盒在构造时需要计算凸块集合S 中所有
元素的协方差矩阵、特征向量以及顶点在3个特征向量上的最大值,而且2个OBB 的相交测试需要
3
41 第2期 刘晓东,等:一种基于混合层次包围盒的快速碰撞检测算法
15次比较运算、60次加减运算、81次乘法运算和24次绝对值运算[2],其时间开销大于本文所用的FD H.
FD H树对存储空间的要求比较低,对树中的每一个结点,只需存储定义FD H的表示固定方向的浮点数,这里共有14个方向(需112个字节)、存储指向子结点的2个指针(共8个字节)和指向父结点的1个指针(4个字节),而对叶结点还需保留1个指向相应的基本几何元素的指针(4个字节).一棵完全的FD H树,共有n个叶结点和n-1个内部结点,故本文算法中的FD H树所需存储空间为256n 个字节,而OBB在各结点上的包围盒方向的任意性使得它需要更多的存储空间(336n个字节)[2].
采用C++,Open G L/G LU T在PC机(PIV310 GHz,内存1G B,显卡MSI RADEON X600PRO,显存128MB)上实现了本文提出的基于混合BV H的碰撞检测算法.图4为测试场景中虚拟手的运动.
通过实验数据比较了本文算法、基于OBB包围盒的碰撞检测算法(RA PID)[2]、基于图像的碰撞检测算法(RECODE)[4],它们在不同情况下的平均碰撞检测时间见表1.从表中可以得出,在速度上本文算法比RA PID、RECODE分别提高了约17%和20%.根据对算法的描述和分析得知,速度提高的主要原因有以下几个方面
.
图4 测试场景中虚拟手的运动
(1)采用了复杂度较低、效率较高的FD H包围盒进行碰撞初判.
(2)采用了最简单的AABB包围盒来快速设置视域参数.
(3)采用的三角形条带化技术提高了绘制速度.
(4)利用图形硬件的计算能力,使得凸块相交测试能够在绘制过程中实时进行.
表1 平均碰撞检测的时间比较
算法平均碰撞检测时间/ms
RECODE71021131241816225190331544216952110601856814480123 RAPID61816121321615823196321064018750163571746710579165本文算法61120101561116917125241543217641135491366212570196三角形面片数2000400060008000100001200014000160001800020000
3 结束语
精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有着至关重要的作用,而提高速度是虚拟环境中碰撞检测的核心问题.本文主要围绕提高碰撞检测速度展开研究,并提出了一种新的基于混合BV H的快速碰撞检测算法.该算法充分利用了FD H包围盒紧密性好、AABB包围盒简单性好的特点和图形的硬件加速功能,大大地提高了碰撞检测的速度,它可应用于形状复杂的刚体精确碰撞检测,而在对碰撞检测的实时性要求较高的场合中应用效果尤其明显.
参考文献:
[1] Cohen J D,Lin M C,Manocha D,et al.I2COOL IDE:
an interactive and exact collision detection system for
large2scale environments[C]∥Proceedings of ACM
Interactive3D Graphics Conference.New Y ork:
ACM,1995:189Ο196.
[2] G ottschalk S,Lin M C,Manocha D.OBB2tree:a hi2
erarchical structure for rapid interference detection[C]
∥Computer Graphics Proceedings.New Y ork:ACM,
1996:171Ο180.
[3] 魏迎梅,吴泉源,石教英.碰撞检测中的固定方向凸包
包围盒的研究[J].软件学报,2001,12(7):1056Ο1063.
Wei Y ingmei,Wu Quanyuan,Shi Jiaoying.Research
on fixed direction hull bounding volume in collision de2
tection[J].Journal of Software,2001,12(7):1056Ο1063.
(下转第157页)
441西 安 交 通 大 学 学 报 第41卷
大数据负载下,多进程、多线程混合模型的隐藏磁盘访问延迟的能力发挥了作用,此时它的性能保持稳定,并优于Zeus和Flash.Zeus虽然在小数据负载下的性能优于Apache,但比之Flash的性能则相差甚远,而在大数据负载下,其性能下降也不如Flash 那样明显.应用ACC方法后,Flash充分发挥了AM PED的优势,无论数据负载是大是小,其性能远远超出其他服务器.
4 结 论
本文提出了应用控制缓冲方法,并以Flash为例实现并验证了ACC的有效性.实验表明,在大数据负载下的ACC能够大大提高Web服务器的性能.
虽然本文的研究集中于静态页面,但有两种途径可以解决Web服务器的动态页面问题:一是可以将一个Web站点的动态页面和静态页面分流,采用专门的服务器来处理、计算要求很高的动态页面,再利用ACC方法来加速静态页面的处理;二是通过磁盘来缓冲动态页面,将之转化为静态页面的处理.
ACC方法不单适用于AM PED模型的服务器,也适用于其他模型,即便服务器通过采用异步方式工作来消除磁盘I/O的阻塞问题,但它还可以通过更优化的磁盘缓冲替换算法来提高缓冲命中率,以获得更好的性能.
参考文献:
[1] Pai V S,Druschel P,Zwaenepoel W.Flash:an effi2
cient and portable web server[C]∥1999Annual USE2
N IX Technical Conference.Monterey,USA:USE2
N IX,1999:199Ο212.
[2] Ruan Yaoping,Pai V S.The origins of network server
latency and the myth of connection scheduling[C]∥Joint International Conference on Measurement and
Modeling of Computer Systems.New Y ork:Associa2
tion for Computing Machinery,2004:424Ο425.
[3] Cao Pei,Felten E W,Karlin A R,et al.Implementa2
tion and performance of integrated application2
controlled file caching,prefetching,and disk schedu2
ling[J].ACM Transactions on Computer Systems,
1996,14(4):311Ο343.
[4] Podlipnig S,Boszormenyi L.A survey of Web cache
replacement strategies[J].ACM Computing Surveys,
2003,35(4):374Ο398.
[5] Cao Pei,Irani S.Cost2aware WWW proxy caching al2
gorithms[C]∥Proceedings of the USEN IX Symposi2
um on Internet Technologies and Systems.Monterey,
USA:USENIX,1997:193Ο206.
[6] Aggarwal C,Wolf J L,Yu P S.Caching on the world
wide web[J].IEEE Transactions on Knowledge and
Data Engineering,1999,11(1):94Ο107.
[7] Ruan Yaoping,Cohen M S,Pai V.Finding speed
bump s:web server performance analysis and anomaly
detection via wide spectrum microbenchmarking[EB/
OL].[2005Ο12Ο15].http:∥https://www.doczj.com/doc/7511880884.html,/
～yruan/.
[8] Standard Performance Evaluation Corporation.SPEC
Web99benchmark[EB/OL].[2005Ο12Ο15].http:∥https://www.doczj.com/doc/7511880884.html,/osg/web99/.
(编辑 苗凌)
(上接第144页)
[4] Baciu G,Wong S K W,Sun H.RECODE:an image2
based collision detection algorithm[J].Journal of Vi2 sualization and Computer Animation,1999,10(4): 181Ο192.
[5] 范昭炜,万华根,高曙明.基于图像的快速碰撞检测算
法[J].计算机辅助设计与图形学学报,2002,9(14): 805Ο809.
Fan Zhaowei,Wan Huagen,G ao Shuming.A fast col2 lision detection algorithm in image space[J].Journal of Computer Aided Design&Computer Graphics, 2002,9(14):805Ο809.
[6] Ehmann S,Lin M C.Accurate and fast proximity que2
ries between polyhedra using convex surface decompo2 sition[C]∥Proceedings of the Eurographics Confer2 ence.Manchester,U K:Blackwell Publishers for Euro2 graphics Assoc.,2001:500Ο510.
[7] Isenburg M.Triangle strip compression[C]∥Pro2
ceedings of Graphics Interface Conference.Waterloo, Canada:Canadian Human2Computer Communication Society,2000:197Ο204.
[8] 霍滨焱.基于图像空间的碰撞检测算法[D].哈尔滨:
哈尔滨工程大学计算机科学与技术学院,2005.
(编辑 苗凌)
751
第2期 李卫,等:应用控制的Web服务器磁盘缓冲方法
简介 本文是阐述如何在2D动作游戏中进行精确而高效的碰撞检测。这里的碰撞是基于多边形而不是基于精灵的。这两者之间在设计上会有不同。 基于精灵的碰撞检测是通过精灵之间的重叠的像素来完成的。而多边形使用向量数学来精确计算交点，时间和碰撞方向。虽然多边形仅仅是精灵的一个近似，但是它比精灵系统要高级。 ?可以精确模拟逼真的简单物理学，例如反弹，摩擦，斜面的滑行 ?碰撞检测可以更精确的用于高速精灵系统。在基于精灵的系统中，如果物体移动过快就会在跳过另一个物体。 ?基于向量数学因此可以扩展到3D，然而精灵碰撞系统被严格限制在2D的情况下。 特性 本文使用的算法只适用于凸多边形，例如三角形，四边形，六边形，圆形。对于非凸多边形，你可以将其分解为多个凸多边形，例如三角形。 算法可以用于快速移动或慢速移动的多边形。不管物体移动多快，碰撞都不会丢失。它也可以处理重叠的问题，并促使交叠物体分离。 演示也支持分割多边形交叉。这可以用于子弹的建模。 同时提供了简单的物体系统，弹力，一些基本的摩擦和静摩擦力。用于确保物体不会从斜面上滑落。
有一个刚体系统的例子，使用了Chrsi Hecker的物理教程。 限制 有序碰撞。就是说并不是有序的进行碰撞。这对于快速移动的物体会出现一定的问题。一旦碰撞被检测到，它就被直接处理了。理想状态下你可能需要找到一个碰撞点并处理它，然后寻找更多的碰撞。但是对于2D动作游戏，这通常是不必要的。 一、分离坐标轴方法 这个方法是碰撞检测的核心。它的规则非常简单并且非常易于实现。这个方法也非常快并且非常可靠，因为计算中没有使用除法操作，下面给出一个简单的基于两个BOX的碰撞检测的例子。
德尔菲法案例分析 案例一：德尔菲法应用案列 某公司研制出一种新兴产品，现在市场上还没有相似产品出现，因此没有历史数据可以获得。公司需要对可能的销售量做出预测，以决定产量。于是该公司 成立专家小组，并聘请业务经理、市场专家和销售人员等8位专家，预测全年可 能的销售量。8位专家提出个人判断，经过三次反馈得到结果如下表所示。 专家编 号 第一次判断第二次判断第三次判断 最低销售量最可能销 售量 最高销 售量 最低销 售量 最可能销 售量 最高销 售量 最低销售量 最可能销 售量 最高销售量 1 150 750 900 600 750 900 550 750 900 2 200 450 600 300 500 650 400 500 650 3 400 600 800 500 700 800 500 700 800 4 750 900 1500 600 750 1500 500 600 1250 5 100 200 350 220 400 500 300 500 600 6 300 500 750 300 500 750 300 600 750 7 250 300 400 250 400 500 400 500 600 8 260 300 500 350 400 600 370 410 610 平均数345 500 725 390 550 775 415 570 770 ?平均值预测： 在预测时，最终一次判断是综合前几次的反馈做出的，因此在预测时一般以最后一次判断为主。则如果按照8位专家第三次判断的平均值计算，则预测这个新产品的平均销售量为： （415+570+770）/3=585 ?加权平均预测： 将最可能销售量、最低销售量和最高销售量分别按0.50、0.20和0.30的概率加权平均，则预测平均销售量为：570*0.5+415*0.2+770*0.3=599 ?中位数预测： 用中位数计算，可将第三次判断按预测值高低排列如下： 最低销售量： 300 370 400 500 550
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/7511880884.html, Journal of Software, Vol.19, Supplement, December 2008, pp.31?40 https://www.doczj.com/doc/7511880884.html, ? 2008 by of Journal of Software. All rights reserved. Tel/Fax: +86-10-62562563 ? 实体网格模型的变分层次有向包围盒构建 王锐, 华炜+, 许高峰, 彭群生, 鲍虎军 (浙江大学 CAD&CG国家重点实验室,浙江杭州 310058) Variational OBB-Tree Approximation for Solid Object WANG Rui, HUA Wei+, XU Gao-Feng, PENG Qun-Sheng, BAO Hu-Jun (State Key Laboratory of CAD&CG, Zhejiang University, Hangzhou 310058, China) + Corresponding author: E-mail: huawei@https://www.doczj.com/doc/7511880884.html, Wang R, Hua W, Xu GF, Peng QS, Bao HJ. Variational OBB-tree approximation for solid object. Journal of Software, 2008,19(Suppl.):31?40. https://www.doczj.com/doc/7511880884.html,/1000-9825/19/s31.htm Abstract: A method that approximates a solid object by object oriented bounding box tree (OBB-Tree) having minimal summed volume outside the object is proposed. First, the outside volume for a single OBB is defined and computed by a hardware-accelerated algorithm. Then, the construction of one OBB-Tree is formulated into a variational approximation. To solve such an approximation, this paper presents an algorithm that minimizes the total outside volume over all OBBs in the same level using the iterative Lloyd clustering and using a variant of iterative MultiGrid among levels. In experiments, comparing against a state-of-the-art alternative, the resulting OBB-Tree is tighter and has better performance in the test of collision detection. Key words: variational approximation; OBB-Tree; solid objects; collision detection 摘要: 层次有向包围盒(object oriented bounding box tree,简称OBB-Tree)在碰撞检测、实时绘制等诸多场合有着 广泛的应用.研究了实体网格模型的层次有向包围盒的构建问题,提出了新的优化求解方法.首先以属于层次包围盒 但不属于实体网格模型的这部分外部空间体积作为误差,并给出基于硬件加速的误差计算方法.其次,将层次包围盒 的构建问题转化为变分逼近问题,通过求解全局误差最小来最优的层次有向包围盒.在优化计算上,我们提出在同层 内采用Lloyd分簇迭代与在层次间采用类似MultiGrid的往复迭代相结合的方法.与前人的结果比较,此方法可以生 成对原实体网格模型包裹更紧密的层次有向包围盒逼近,在碰撞检测的实际应用中,使用此方法构建的结果可以减 少碰撞检测的计算时间提高检测效率. 关键词: 变分逼近;层次有向包围盒;实体网格模型;碰撞检测 层次包围体是用若干体积略大而形状简单的包围体来近似地表示复杂的几何对象.在很多对计算实时性 有要求的场合(例如:碰撞检测、实时绘制等),层次包围体被用来代替原几何对象参与计算,达到简化计算的目 的.以碰撞检测为例,在对包围体层次树进行遍历的过程中,通过包围体间的快速相交测试可及早排除明显不可 能相交的基本几何对象,从而有效地提高了碰撞检测的速度. 由于应用的广泛性,人们已经在层次包围体构建的研究上展开了许多研究.根据应用需求的不同,可选取不 ? Supported by the National Natural Science Foundation of China under Grant No.60773184 (国家自然科学基金) Received 2008-05-03; Accepted 2008-11-14
层次分析法在最优生鲜农产品流通中的应用 班级 （一）、建立递阶层次结构 目标层：最优生鲜农产品流通模式。 准则层：方案的影响因素有：1c 自然属性、2c 经济价值、3c 基础设施、5c 政府政策。 方案层：设三个方案分别为：1A 农产品产地一产地批发市场一销地批发市场一消费者、2A 农产品产地一产地批发市场一销地批发市场一农贸市场一消费者、3A 农业合作社一第三方物流企业一超市一消费者(本文假设农产品的生产地和销地不在同一个地区)。 。 目标层： 准则层： 方案层：
图3—1 递阶层次结构 （二）、构造判断(成对比较)矩阵 所谓判断矩阵昰以矩阵的形式来表述每一层次中各要素相对其上层要素的相对重要程度。为了使各因素之间进行两两比较得到量化的判断矩阵，引入1～9的标度，见表 为了构造判断矩阵，作者对6个专家进行了咨询，根据专家和作者的经验，四个准则下的两两比较矩阵分别为：
（三）、层次单排序及其一致性检验 层次单排序就是把本层所有要素针对上一层某一要素，排出评比的次序，这种次序以相对的数值大小来表示。 对应于判断矩阵最大特征根λmax 的特征向量，经归一化(使向量中各元素之和等于1)后记为W 。 W 的元素为同一层次因素对于上一层次因素某因素相对重要性的排序权值，这一过程称为层次单排序。 能否确认层次单排序，需要进行一致性检验，所谓一致性检验是指对A 确定不一致的允许范围。 由于λ 连续的依赖于ij a ，则λ 比n 大的越多，A 的不一致性越严重。用最大特征值对应的特征向量作为被比较因素对上层某因素影响程度的权向量，其不一致程度越大，引起的判断误差越大。因而可以用 λ―n 数值的大小来衡量 A 的不一致程度。 用一致性指标进行检验：max 1 n CI n λ-= -。其中max λ是比较矩阵的最大特征值，n 是比较矩 阵的阶数。CI 的值越小，判断矩阵越接近于完全一致。反之，判断矩阵偏离完全一致的程度越大。 （四）、层次总排序及其一致性检验 )0(273.0104.0056.0567.0092.1418.0224.0266.2222.0316.0353.0201 .0074.0105.0118.0121 .0037.0053.0059.0075 .0667.0526.0470.0603 .0136131121121113581 W A =??? ?? ?? ??????????→??? ? ? ?? ? ???????????→?????????????? ???????→?????????????? ?=归一化按行求和列向量归一化
层次分析法在人力资源管理方面的应用 作者：周红燕 入库时间：2005年7月1日 摘要：本文旨在应用层次分析法（AHP）对人力资源中的经常碰到的问题：岗位工资等级、绩效评估进行一个量化的分析，从而定义一个合理的薪酬水平，对员工做出公正的绩效评估，使员工觉得公平，使公司得到效率。 关键词：层次分析法、薪酬分析、决策变量、评判标准 1、什么是层次分析法 层次分析法(The analytic hierarchy process)简称AHP，是由Thomas L.Staaty 最先发明的用于解决包含多项标准时的复杂问题，在这个过程中，决策者需要判断各项评判标准的重要性、决策变量相对于评判标准的优先极。应用层次分析法可以给出各个标准的权重，各个决策变量相对于每项标准的优先级，量化决策变量，从而为决策提供依据。 层次分析法广泛地应用于设施规划、选址、决策等，笔者曾将之用于人力资源管理中的岗位薪酬分析，用这种方法对一个工厂的众多岗位的薪酬标准进行分析，从而定义出岗位工资，这对于薪酬分配的公平性具有很重要的意义。 层次分析法中有几个很重要的定义 决策变量（Decision variate）：要进行判断进行取舍的参量 评判标准（Criteria）：用以做为比较指标的参量 优先级(Preference)：重要性 权重（weight）：指定给某数字反映其重要性的系数 2、案例： 在一个工厂里，有一百多个岗位，这些岗位复杂程度各不相同，工作的环境各不一样，一个合理的岗位工资分配制度对于提高员工满意度、体现人力资源的公平性具有非常重要的作用，而该工厂所处的行业比较特殊，没有可以借鉴的经验，必须由该工厂对自已的岗位工资水平进行合理地定义。 现已知社会的平均工资水平，该公司决定比社会平均工资水平高10%做为公司总的基数，如何对工厂内部各个岗位的工资基数进行分配，这是该文章要解决的问题。
一种基于OBB包围盒算法的改进 耿朝阳;刘敏;徐江涛 【期刊名称】《西安工业大学学报》 【年(卷),期】2012(032)007 【摘要】The direction cylindrical bounding box testing method was put forward to improve the efficiency of collision detection. Based on the characteristics of different types of bounding box, their algorithms were analyzed and then the algorithm for collision detection of bounding box was optimized. The experiment result shows that the improved algorithm can increase the efficiency of collision detection and enchance the real-time of the system.%为了提高碰撞检测的速度,对虚拟环境中的物体进行了假设,提出了方向圆柱包围盒检测方法,并结合各类包围盒的特点,分析了不同类型包围盒之间算法,实现了层次包围盒碰撞检测算法的优化,提高了碰撞检测的速度,增强了系统的实时性. 【总页数】4页(550-553) 【关键词】碰撞检测;虚拟环境;检测算法;方向圆柱包围盒 【作者】耿朝阳;刘敏;徐江涛 【作者单位】西安工业大学计算机科学与工程学院,西安710032;西安工业大学计算机科学与工程学院,西安 710032;西安工业大学计算机科学与工程学院,西安710032 【正文语种】中文 【中图分类】TP301.5
旅游业发展水平评价问题 摘要 为了研究比较两个旅游城市Q、Y的旅游业发展水平，建立层次分析法]3[数学模型，对两个旅游城市Q、Y的旅游业发展水平进行了评价. 首先，通过对题目中的图1、表1进行了分析与讨论，根据层次分析法，建立了目标层A、准则层B和子准则层C、方案层D四个层次，通过同一层目标之 间的重要性的两两比较，得出判断矩阵,利用]1[ MATLAB编程对每个判断矩阵进行求解. 其次,用MATLAB软件算出决策组合向量，再比较决策组合向量的大小，由“决策组合向量最大”为目标,得出城市Y的决策组合向量为0.4325，城市Q组合向量为0.5675. 最后，通过城市Q旅游业发展水平与旅游城市Y旅游业发展水平的决策组合向量比较，得出城市Q的旅游业发展水平较高. 关键词层次分析法MATLAB旅游业发展水平决策组合向量
1.问题重述 本文要求分析Q Y,两个旅游城市旅游业发展水平,并且给出了两个城市各方面因素的对比，如城市规模与密度，经济条件，交通条件，生态环境条件，宣传与监督，旅游规格，空气质量，城市规模，人口密度，人均GDP，人均住房面积，第三产业增加值占GDP比重，税收GDP，外贸依存度，市内外交通，人均拥有绿地面积，污水集中处理率，环境噪音，国内外旅游人数，理赔金额，立案数量，A级景点数量，旅行社数量，星级饭店数量.建立数学模型进行求解. 2.问题分析 本文要求分析Q Y,两个城市的分析Y,两个旅游城市旅游业发展水平，在对Q 中，发现需要考虑因素较多，第一、城市规模与密度，包括城市规模与人口密度.第二、经济条件，包括外贸依存度，人均GDP，人均住房面积，第三产业增加值占GDP比重，税收GDP.第三、交通条件，包括市内外交通.第四，生态环境条件包括空气质量，人均绿地面积，污水处理能力，环境噪音.第五、宣传与监督，包括国内外旅游人数，游客投诉立案件数.第六、旅游规格，包括A级景点个数，旅行社个数，星级饭店个数，这就涉及到层次分析法来估算各个指标的权重，评出最优方案.具体内容如下： （1）本文选择了对Q Y,两个旅游城市旅游业发展水平有影响的19个指标作为评价要素,指标规定如下： 城市规模：城市的人口数量. 人口密度：单位面积土地上居住的人口数.是反映某一地区范围内人口疏密程度的指标.人口影响城市规模.人口密度越大城市规模也就越大. 人均GDP：即人均国内生产总值. 人均城建资金：即用于城市建设的资金总投入. 第三产业增加值：增加值率指在一定时期内单位产值的增加值.即第三产业增加值越高越能带动城市经济的发展. 税收GDP：税收是国家为实现其职能，凭借政治权力，按照法律规定，通过税收工具强制地、无偿地征收参与国民收入和社会产品的分配和再分配取得财政收入的一种形式. 外贸依存度：即城市对于外贸交易的依赖程度. 市内交通：即城市市区交通情况. 市外交通：即城市郊区交通情况.市内交通与市外交通对于城市交通条件具有同等的重要性. 空气质量：即城市总体空气质量情况.空气质量越好对于城市生态环境就越好. 人均绿地面积：即反应城市绿化面积以及人口密度的比值关系. 污水处理能力：城市污水处理水平. 环境噪音：城市环境噪音情况. 国内外旅客人数：国内外来旅客一年总人数.人数越多说明宣传与监督就越好.
德尔菲法探讨物流企业效益度量指标体系 汪思远2009710083 统计二班 【摘要】目前，企业运作的不规范已经成为制约我国物流业健康发展的瓶颈，为此，有必要从效益度量的层面针对物流企业的运营管理提出指导性的规范要求，促进物流企业的规范发展，促进我国物流产业的有序发展。文中将德尔菲法和层次分析法两种度量方法进行融合，根据两者的特点取其长、避其短，构建了一套全新的财务与非财务指标相结合的物流企业效益指标度量体系，试图对企业效益做出更加科学客观的度量。 【关键词】物流企业；效益；度量指标；德尔菲法；层次分析法 1引言 物流理论的不断发展和物流实践的不断深入，客观上要求建立与之相适应的物流企业效益度量指标体系，并确定合理的度量方法，以此来科学、客观地反映物流企业的运营情况。目前，物流企业作为新兴的行业，其经营方法还处于探索阶段，效益度量指标体系就更不完善。基于这一背景对物流企业的效益度量指标进行综合分析，除要建立科学、合理的度量指标体外，还要研究科学的度量模型。 2德尔菲法在物流企业效益度量指标体系中的应用可行性物流企业效益度量指标度量系统作为物流企业管理控制系统中一个相对独立的子系统，由以下几个基本要素构成：度量目标、度量对象、度量指标、度量标准、分析报告。 德尔菲法作为一种主观、定性的方法，可以广泛应用于各种度量指标体系的建立和具体指标的确定过程。当德尔菲法下的决策系统中很多因素之间的比较往往无法用定量的方式描述，此时需要将半定性、半定量的问题转化为定量计算问题。层次分析法是解决这类问题的行之有效的方法。层次分析法将复杂的决策系统层次化，通过逐层比较各种关联因素的重要性来为分析、决策提供定量的依据。由此可见，结合层次分析法的德尔菲法是一种相对权威的企业效益度量指标度量指标体系建模方法，它考虑了专家们的真实意见，统一了各项指标的权重，克服了传统效益度量体系中或重财务或重服务的弱点，能够比较准确地反映企业在一定时期内为创造的价值，不仅适用于物流行业，还适合物流企业的成本与服务效益度量指标评估。
层次分析法应用实例 问题描述：通讯交流在当今社会显得尤其重要，手机便是一个例子，现在每个人手里都有至少一部手机。但如今生产手机的厂家越来越多，品种五花八门，如何选购一款适合自己的手机这个问题困扰了许多人。 目标：选购一款合适的手机 准则：选择手机的标准大体可以分成四个：实用性，功能性，外观，价格。 方案：由于手机厂家有几十家，我们不妨可以将其归类：○1欧美（iphone）；○2亚洲（索爱）；○3国产（华为）. 解决步骤： 1.建立递阶层次结构模型 图1 选购手机层次结构图 2.设置标度 人们定性区分事物的能力习惯用5个属性来表示，即同样重要、稍微重要、较强重要、强烈重要、绝对重要，当需要较高精度时，可以取两个相邻属性之间的值，这样就得到9个数值，即9个标度。
为了便于将比较判断定量化，引入1～9比率标度方法，规定用1、3、5、7、9分别表示根据经验判断，要素i与要素j相比：同样重要、稍微重要、较强重要、强烈重要、绝对重要，而2、4、6、8表示上述两判断级之间的折衷值。 注：aij表示要素i与要素j相对重要度之比，且有下述关系： aij=1/aji ；aii=1；i，j=1，2，…，n 显然，比值越大，则要素i的重要度就越高。 3.构造判断矩阵 A B1 B2 B3 B4 B1 1 3 5 1 B2 1/3 1 3 1/3 B3 1/5 1/3 1 1/5 B4 1 3 5 1 表1 判断矩阵A—B B1 C1 C2 C3 C1 1 1/3 1/5 C2 3 1 1/3 C3 5 3 1 表2 判断矩阵B1—C
B2 C1 C2 C3 C1 1 3 3 C2 1/3 1 1 C3 1/3 1 1 表3 判断矩阵B2—C B3 C1 C2 C3 C1 1 3 6 C2 1/3 1 4 C3 1/6 1/4 1 表4 判断矩阵B3—C B4 C1 C2 C3 C1 1 1/4 1/6 C2 4 1 1/3 C3 6 3 1 表5 判断矩阵B4—C 4.计算各判断矩阵的特征值，特征向量和一致性检验 用求和发计算特征值： ○1将判断矩阵A 按列归一化（即列元素之和为1）：bij= aij /Σaij ； ○2将归一化的矩阵按行求和：ci=Σbij （i=1，2，3….n ）； ○3将ci 归一化：得到特征向量W=（w1，w2，…wn ）T ，wi=ci /Σci ， W 即为A 的特征向量的近似值； ○4求特征向量W 对应的最大特征值： 1).1 5 3 1 51131513131311531 = A ，按列归一化后为 38 1514 522 938 1538314122138338514322338539151452293815 2).按行求和并归一化后得()T 389 .0069 .0153 .0389.0=W
层次分析法的一个应用 摘要 关键词： Abstract Keywords: 前言 1层次分析法理论概述 1.2层次分析法的概念 层次分析法是由美国运筹学家匹兹堡大学的 T.L.saaty教授于20世纪70年代提出的一种决策方法。它是将评价对象或问题视为一个系统，根据问题的性质和想要达到的总目标将问题分解成不同的组成要素，并按照要素间的相互关联度及隶属关系将要素按不同层次聚集组合，从而形成一个多层次的分析结构系统，把问题条理化、层次化。 层次分析法的结构符合人们思维的基本特征分解、判断、综合，把复杂的问题分解为各组成要素，再将这些要素按支配关系分组，从而形成有序的递阶层次结构，通过两两比较判断的方式确定每一层次中要素的相对重要性，然后在递阶层次结构内进行合成得到相对于目标的重要程度的总排序。因此，层次分析法从出现开始就受到了理论界广泛的支持和认可，并得到了不断的改进和完善。
1.3 AHP法下优点 （1）AHP对于解决多层次、多指标的递阶结构问题行之有效。保险公司绩效评价各指标之间相互作用，相互制约，且绩效受到多种因素的影响，可以分解成不同的子指标，例如我们从财务维度可将保险公司的绩效分解为增加盈利能力、偿付能力和发展能力三个层面，而各个层面又可以从多个角度来衡量，从而构成关联保险公司绩效评价指标体系的递阶结构体系。这样，我国上市保险公司绩效评价指标体系的递阶结构为层次分析法提供了“结构”基础。 （2）把定性分析和定量分析有机地结合起来，避免了单纯定性分析的主观臆断性和单纯利用定量分析时对数据资料的严格要求。 （3）层次分析法思路简单明了，将人们的思维数字化、系统化，便于接受并容易计算；同时，层次分析法是一种相对比较成熟的理论，有大量的是实践经验可以借鉴，这就避免了在保险公司绩效评价指标权重的确定过程中由于缺乏经验而产生的不足。 当然层次分析法也存在着缺陷：首先，其结论是建立在判断矩阵是一致性矩阵的基础上的，而在实际应用中所建立的判断矩阵，由于各方面的原因，往往不能一次性得到具有一致性的判断矩阵，而需要对其一致性进行检验，并进行多次的修改。因此，判断矩阵的建立过程比较复杂，且存在较大的主观性；其次是特征值的计算量较大；再次，许多专家认为层次分析法中采用的1-9标度法不能准确地反映专家和决策者的真实感觉和判断。采用层次分析法来确定两个指标的相对重要性时，当人们认为A1比A2重要(记为a)，B1比B2明显重要(记为b)，C1比C2强烈重要(记为c)时，则(c-b)比(b-a)要大得多，因而标度不应该的线性的，而是随着重要程度的增加差距越来越大。而1-9标度是等距的，所以Saaty 提出的线性评判标度与人们头脑中的实际标度并非一致。因此，这些问题都需要进行改进，但整体上不影响本文采用层次分析法确定评价指标权重。 1.4 AHP的基本步骤 用层次分析法作系统分析，首先需要把问题层次化，根据问题的性质和总目标把问题分解成为不同的因素，并且根据这些因素间的相互影响及隶属关系将因素按不同层次聚集组合，形成一个多层次的分析结构模型，并最终系统分析归结为最底层(供决策的方案、措施等)相对于最高层(总目标)的相对重要性权重的确
。数 学 建 模 作 业 班级：高分子材料与工程 姓名：林志许、朱金波、任宇龙
。 学号：1211020115、1211020126、1211020134 层次分析法 某物流企业需要采购一台设备，在采购设备时需要从功能、价格与可维护性三个角度进行评价，考虑应用层次分析法对3个不同品牌的设备进行综合分析评价和排序，从中选出能实现物流规划总目标的最优设备，其层次结构如下图所示。以A 表示系统的总目标，判断层中1B 表示功能，2B 表示价格，3B 表示可维护性。1C ，2C ，3C 表示备选的3种品牌的设备。 解题步骤： 1、标度及描述 人们定性区分事物的能力习惯用5个属性来表示，即同样重要、稍微重要、较强重要、强烈重要、绝对重要，当需要较高精度时，可以取两个相邻属性之间的值，这样就得到9个数值，即9个标度。 为了便于将比较判断定量化，引入1～9比率标度方法，规定用1、3、5、7、9分别表示根据经验判断，要素i 与要素j 相比：同样重要、稍微重要、较强重要、强烈重要、绝对重要，而2、4、6、8表示上述两判断级之间的折衷值。 目标层 判断层 方案层 图 设备采购层次结构图
注：a ij 表示要素i与要素j相对重要度之比，且有下述关系： a ij =1/a ji ； a ii =1； i，j=1，2，…，n 显然，比值越大，则要素i的重要度就越高。 2、构建判断矩阵A 判断矩阵是层次分析法的基本信息，也是进行权重计算的重要依据。根据结构模型，将图中各因素两两进行判断与比较，构造判断矩阵： ●判断矩阵B A-(即相对于物流系统总目标，判断层各因素相对重要性比较)如表1所示； ●判断矩阵C B- 1(相对功能，各方案的相对重要性比较)如表2所示； ●判断矩阵C B- 2(相对价格，各方案的相对重要性比较)如表3所示； ●判断矩阵C B- 3(相对可维护性，各方案的相对重要性比较)如表4所示。 B A- C B- 1 C B- 3 3、计算各判断矩阵的特征值、特征向量及一致性检验指标 一般来讲，在AHP法中计算判断矩阵的最大特征值与特征向量，必不需
基于层次分析法的个人信用评估体系 李立兵，曾志伟 河海大学，南京（210098） E-mail：libing_li2004@https://www.doczj.com/doc/7511880884.html, 摘要：本文在层次分析法的基础上建立个人信用的评价指标体系对个人信用进行评估。关键词：层次分析法，评估指标体系，个人信用评估 从古到今，信用都不是孤立的概念，它必须依附于当时的经济、政治和文化背景，个人信用，是自然人个人的信用，是个人的无形资产，信用资产质量好，拥有良好的信用记录，则意味着更多的发展机会，更高的发展效率。个人信用问题已经是我国经济体制改革和发展中不可回避的重要问题。但是我国的个人信用体系还不完善，基本上属于空白。目前我国居民个人信用资料缺乏，他们能提供的信用证明文件只有身份证和户籍证明、所在单位的工作证明；在个人储蓄实名制实施以后，又增加了个人存单和实物资产。国内虽然已有相关机构对个人的信用进行评估，但是由于在评估定位、评估要素的选取以及评估手段方面的不足，使得个人信用评估结果的可信度大大降低。如何建立科学的个人信用评估方法、如何建立一个规范化并和国际接轨的个人信用评估制度体系已成为一个亟待解决的重要课题。本文选取个人资质评价指标情况、个人资产评价指标、家庭评价指标及个人的信用历史等一系列的指标，利用层次分析法来建立个人信用评估体系，对个人信用进行评估。 1. 层次分析法概述⑴、⑵、⑶ 层次分析法（Analytical Hierarchy Process，ＡＨＰ）是美国匹兹堡人学教授A. L. Saaty 于20世纪70年代提出的一种系统分析方法。它是一种能将定性分析与定量分析相结合的系统分析方法。其解决问题的基本思路和基本原理是：首先，把要解决的问题分层系列化，即根据问题的性质和要达到的目标，将问题分解为不同的组成因素，按照因素之间的相互影响和隶属关系将其分层聚类组合，形成一个递阶的、有序的层次模型。然后，对模型中每一层次因素的相对重要性，依据人们对客观现实判断给予定量表述，再利用数学方法确定每一层次全部因素相对重要性次序的权值。最后，通过综合训算各因素相对重要性的权值，得到最低层(方案层)相对最高层(总日标)相对重要性次序的组合权值，以此作为评价和选择方案的依据。 层次分析法处理问题的基木步骤简述如下：①确定评价目标，再明确方案评价的准则。根据评价目标、评价准则构造递阶层次结构模型。递阶层次结构模型一般分为3层：目标层、准则层和方案层；②应用两两比较法构造所有的判断矩阵。具体如下： 1.1 建立判断矩阵 对本级的要素进行两两比较来确定判断矩阵A的儿素，a ij是要素a i对a j的相对重要性其值是由专家根据资料数据以及自己的经验和价值观用判断尺度来确定判断尺度表示要素要素a i对a j相对重要性的数量尺度。采用的判断尺度见表１。
实时视频图像的清晰度检测算法研究 2010-12-18 17:11:42 来源:微型机与应用 关键字：实时视频图像背景提取Sobel算子清晰度检测 实时视频图像的质量分析已成为众多应用领域性能好坏的关键因素之一，因此实时视频图像的清晰度检测变得尤为重要。目前针对实时视频图像清晰度检测的研究较少，图像清晰度检测算法的研究对象主要针对静止的图像。现有的图像清晰度检测算法大致分为空域和频域两类。在空域中多采用基于梯度的算法，如拉普拉斯(Laplace)算法、差分平方和(SPSMD)算法、Sobel算子等。此类算法计算简洁、快速、抗噪性能好、可靠性较高。在频域中多采用图像的FFT变换(或其他变换)，如功率谱(Power-spectra)算法等[1-2]。此类算法的检测效果好，但计算复杂度高、计算时间长，不适合应用在基于软件实现的实时检测系统中。 当前对实时视频图像的一种重要应用是对运动目标的检测，常用的目标检测方法有帧差法、背景减法、光流法及运动能量法[3]，其中最简单而又快捷的方法是背景差法。其基本思想是通过对输入图像与背景图像进行比较来分割运动目标，关键环节是背景图像的提取。目前常用的背景提取方法有多帧图像平均法、灰度统计法、中值滤波法、基于帧差的选择方法、单高斯建模等。参考文献[4]中对以上算法做了充分的研究。 本文是针对实时视频图像的清晰度检测，基于实时视频图像背景基本保持不变的环境。通过比较上述算法，针对实时视频图像的特点，提出一种基于背景提取与Sobel算子相结合的实时视频图像的清晰度检测算法。 1 实时视频图像的清晰度检测算法原理 当视频播放画面超过24帧/s时，根据视觉暂留原理，人眼无法辨别每幅单独的静态画面，看上去是平滑连续的视觉效果。视频中的事物通常分为静止和运动两类，连续多帧画面中保持静止的物体可视为静止的背景，连续多帧画面中位置变化的物体可视为运动的前景。因此，实时视频图像中的每帧图像都可以划分为静止的背景和运动的前景两类区域。由于视频序列图像中运动的前景区域随机变化，引起图像像素点梯度值的随机改变，使得实时视频图像的清晰度检测较难实现。因此，本文的算法是利用实时视频图像中静止的背景区域检测视频序列图像的清晰度，即由背景提取和清晰度检测两部分组成。 1.1 实时视频图像的背景提取
实验目的： 熟悉有关层次分析法模型的建立与计算，熟悉Matlab 的相关命令。 实验准备： 1. 在开始本实验之前，请回顾教科书的相关内容； 2. 需要一台准备安装Windows XP Professional 操作系统和装有Matlab 的计算机。 实验内容及要求 试用层次分析法解决一个实际问题。问题可参考教材P296第4大题。 实验过程： 某物流企业需要采购一台设备，在采购设备时需要从功能、价格与可维护性三个角度进行评价，考虑应用层次分析法对3个不同品牌的设备进行综合分析评价和排序，从中选出能实现物流规划总目标的最优设备，其层次结构如下图所示。以A 表示系统的总目标，判断层中1B 表示功能，2B 表示价格，3B 表示可维护性。1C ，2C ，3C 表示备选的3种品牌的设备。 解题步骤： 1、标度及描述 人们定性区分事物的能力习惯用5个属性来表示，即同样重要、稍微重要、较强重要、强烈重要、绝对重要，当需要较高精度时，可以取两个相邻属性之间的值，这样就得到9个数值，即9个标度。 为了便于将比较判断定量化，引入1～9比率标度方法，规定用1、3、5、7、9分别表示根据经验判断，要素i 与要素j 相比：同样重要、稍微重要、较强重要、强烈重要、绝对重要，而2、4、6、8表示上述两判断级之间的折衷值。 标度 定义（比较因素i 与j ） 1 因素i 与j 同样重要 3 因素i 与j 稍微重要 5 因素i 与j 较强重要 7 因素i 与j 强烈重要 9 因素i 与j 绝对重要 2、4、6、8 两个相邻判断因素的中间值 倒数 因素i 与j 比较得判断矩阵a ij ，则因素j 与i 相比的判断为a ji =1/a ij 设备采购层次结构图
层次分析法实例讲解学习 生活实际例题： 旅游实例，有三个旅游地点供游客们选择，连云港，常州，徐州。影响游客们决策的因素主要有以下五项：景色、费用、居住、饮食、旅途。请根据个人偏好选择最佳旅游地点。 分析：旅游点是方案层，将它们分别用B,B2,B3表示，影响旅游决策的因素为准 则层AAAAA；目标层为选择旅游地，即可以建立以下模型: 建立判断矩阵： 准则层判断矩阵（即各种因素在旅客偏好选择中所占有的不同比重） 1 1/ 2 4 3 3 2 1 7 5 5 A 1/4 1/7 1 1/2 1/3 1/3 1/5 2 1 1 1/3 1/5 3 1 1 方案层判断矩阵建立（针对每一个影响因素来对方案层建立） 1 2 5 1 1/3 1/8 1 1 3 B 1/2 1 2 B1 3 1 1/3 B1 1 1 3 1/5 1/2 1 8 3 1 1/3 1/3 1 1 3 4 1 1 1/4 B1 1/3 1 1 B1 1 1 1/4 1/4 1 1 4 4 1 求准则层判断矩阵A的特征值： Matlab 运行程序：[a,b]=eig（A）
'矩阵的对角线为准则层判断矩阵 A 的特征值: 5.073 0 0 0 0 0.031 0 0 0 b 0 0 0.031 0 0 0 0 0 0.005 0 0.005 即 1 5.073, 2 0.031, 3 0.031, 4 0.005, 5 0.005 选出最大特征值： max ( 1, 2, 3, 4, 5 ) 1 最大特征值的特征向量即为准则层的影响因素所占的权重， 为： 所对应的特征向量 w 1 -0.4658 -0.8409 -0.0951 -0.1733 -0.1920 归一化(最简 matlab 程序为 w=w1./sum(w1)) w 0.2636 0.4759 0.0538 0.0981 0.1087 一致性指标的检验： 由max 是否等于5来检验判断矩阵A 是否为一致矩阵。由于特征根连续地依 赖于矩阵A 中的值，故max 比5大得越多，A 的非一致性程度也就越严重， max 对应的标准化特征向量也就越不能真实地反映出对因素 A i (i 1, ,5)的影 响中所占的比重。 计算一致性指标CI : 此题的一致性指标为 5.073-5 0.018 5-1 平均随机一致性指标RI 相对固定，如下表： RI 随机一致性指标 3456789 10 11 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51 计算一致性比例CR : CR q RI 当CR 时，认为判断矩阵的一致性是可以接受的，否则应对判断矩阵作适当修正。 本题： CR ? 皿 0.016 0.1 RI 1.12 可行。 按照如上方式处理矩阵B, B 2, B 3, B 4, B 5得: CI max n n 1 max n n 1 CI n 1 2 RI 0
某物流企业需要采购一台设备，在采购设备时需要从功能、价格与可维护性三个角度进行评价，考虑应用层次分析法对3个不同品牌的设备进行综合分析评价和排序，从中选出能实现物流规划总目标的最优设备，其层次结构如下图所示。以A 表示系统的总目标，判断层中1B 表示功能，2B 表示价格，3B 表示可维护性。 C ，C ，3C 表示备选的3种品牌的设备。 解题步骤： 1、标度及描述 人们定性区分事物的能力习惯用5个属性来表示，即同样重要、稍微重要、较强重要、强烈重要、绝对重要，当需要较高精度时，可以取两个相邻属性之间的值，这样就得到9个数值，即9个标度。 为了便于将比较判断定量化，引入1～9比率标度方法，规定用1、3、5、7、9分别表示根据经验判断，要素i 与要素j 相比：同样重要、稍微重要、较强重要、强烈重要、绝对重要，而2、4、6、8表示上述两判断级之间的折衷值。 注：a ij 表示要素i 与要素j 相对重要度之比，且有下述关系： a ij =1/a ji ；a ii =1； i ，j=1，2，…，n 显然，比值越大，则要素i 的重要度就越高。 目标层 判断层 方案层 图 设备采购层次结构图
2、构建判断矩阵A 判断矩阵是层次分析法的基本信息，也是进行权重计算的重要依据。 根据结构模型，将图中各因素两两进行判断与比较，构造判断矩阵： ●判断矩阵B A -(即相对于物流系统总目标，判断层各因素相对重要性比较)如表1所示； ●判断矩阵C B -1(相对功能，各方案的相对重要性比较)如表2所示； ●判断矩阵C B -2(相对价格，各方案的相对重要性比较)如表3所示； ●判断矩阵C B -3(相对可维护性，各方案的相对重要性比较)如表4所 示。 1B A - C B -1 4C B -3 3、计算各判断矩阵的特征值、特征向量及一致性检验指标 一般来讲，在AHP 法中计算判断矩阵的最大特征值与特征向量，必不需要较高的精度，用求和法或求根法可以计算特征值的近似值。 ●求和法 1）将判断矩阵A 按列归一化（即列元素之和为1）：b ij = a ij /Σa ij ； 2）将归一化的矩阵按行求和：c i =Σb ij （i=1，2，3….n ）； 3）将c i 归一化：得到特征向量W =（w 1，w 2，…w n ）T ，w i =c i /Σc i ， W 即为A 的特征向量的近似值；
层次分析法实例与步骤 结合一个具体例子，说明层次分析法的基本步骤和要点。 【案例分析】合理购买电脑决策：层次分析法问题提出 很多的电脑小白需要对购买哪个品牌的电脑进行决策，可选择的方案是购买戴尔公司生产的笔记本（简称购买戴尔）或购买联想公司生产的笔记本（简称购买联想）。除了考虑主板来源外，还要考虑CPU 性能、显卡方式等因素，即是多准则决策问题，考虑运用层次分析法解决。 1. 建立递阶层次结构 【案例分析】合理购买电脑决策：建立递阶层次结构 在购买哪个品牌的电脑决策问题中，很多电脑小白希望通过选择不同的电脑品牌使性价比最高，即决策目标是“合理购买电脑使性价比最高”。 为了实现这一目标，需要考虑的主要准则有三个，即主板来源，CPU 性能，显卡方式。但问题绝不这么简单。通过深入思考，还认为还必须考虑本工厂自产、代工厂提供、主频的大小、核心数、独立式显卡、集成式显卡等因素（准则），从相互关系上分析，这些因素隶属于主要准则，因此放在下一层次考虑，并且分属于不同准则。 假设本问题只考虑这些准则，接下来需要明确为了实现决策目标、在上述准则下可以有哪些方案。根据题中所述，本问题有两个解决方案，即购买戴尔或购买联想，这两个因素作为措施层元素放在递阶层次结构的最下层。很明显，这两个方案于所有准则都相关。 将各个层次的因素按其上下关系摆放好位置，并将它们之间的关系用连线连接起来。同时，为了方便后面的定量表示，一般从上到下用A 、B 、C 、D 。。。代表不同层次，同一层次从左到右用1、2、3、4。。。代表不同因素。这样构成的递阶层次结构如下图。 目标层A 准则层B 准则层C 措施层D 图1 递阶层次结构示意图 2. 构造判断矩阵并赋值