碰撞检测技术

碰撞检测技术

碰撞检测技术2011-05-06 23：00

技术--引擎2008-09-05 19：50：55阅读251 10.3碰撞检测技术

到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体，墙壁、树木对玩家(视点)好像是虚设，可以任意从其中穿越。为了使场景人物更加完善，还需要使用碰撞检测技术。

10.3.1碰撞检测技术简介

无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。

好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率过大则会把人物挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。

在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。

做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中的常识。如果出现Bug，很容易被人发现，例如人物无缘无故被卡住不能前进或者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法，算法复杂，容易出错。

对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游戏上使用的碰撞检测不可能使用太精确的检测，而且对于3D碰撞检测问题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和精确性。

目前成功商业3D游戏普遍采用的碰撞检测是BSP树及AABB(axially aligned bounding box)包装盒(球)方式。简单地讲，AABB检测法就是采用一

个描述用的立方体或者球形体包裹住3D物体对象的整体(或者是主要部分)，之后根据包装盒的距离、位置等信息来计算是否发生碰撞，如图10-24所示。

除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和方

便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一些特殊场

合使用。BSP树是用来控制检测顺序和方向的数据描述。

在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相

对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重

要的时间。

如果使用单步碰撞检测，需要注意当时间步长较大时会发生两个物体完全

穿透而算法却未检测出来的问题，如图10-25所示。其解决方案是产生一个4D

空间，在物体运动的开始和结束时间之间产生一个4D超多面体，用于穿透测试。

图10-24 AABB包装盒图10-25碰撞检测的单步失控和4D测试

读者在程序开发初期有必要对碰撞检测有一个初步的估计，以免最后把大

量精力消耗在碰撞检测问题上，从而降低了在基础的图形编程之上的注意力。

10.3.2球体碰撞检测

真实的物理模拟系统需要非常精确的碰撞检测算法，但是游戏中常常只需

要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而不用知道

模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影成较规则的物体

进行碰撞检测。

球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知道

两个球体的球心和半径就能进行检测。

那么球体碰撞是如何工作的?主要过程如下。

n计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较。

n如果距离大于半径和，则没有发生碰撞。

n否则，如果距离小于半径和，则发生了物体碰撞。

考虑由球心c1、c2和半径r1、r2定义的两个球，如图10-26所示。设d

为球心间的距离。很明显，当d

d2<(r1+r2)2，可以避免包括计算d在内的平方根运算。

对两个运动的球进行碰撞检测要麻烦一些，假设两个球的运动向量为d1和

d2，球与位移向量是一一对应的，它们描述了所讨论时间段中的运动方式。

事实上，物体的运动是相对的，例如两列在两条平行轨道上相向行驶的火车，在其中一列中观察，对方的速度是两车速度之和。同样，也可以从第一个

球的角度来简化问题，假设第一个球是"静止"的，另一个是"运动"的，那么该

运动向量等于原向量d1和d2之差，如图10-27所示。

图10-27动态球的检测过程

球体碰撞的优点是非常适用于需要快速检测的游戏，因为它不需要精确的

碰撞检测算法。执行速度相对较快，不会给CPU带来过大的计算负担。

球体碰撞的另一个劣势是只适用于近似球形物体，如果物体非常窄或者非

常宽，该碰撞检测算法将会失效，因为会在物体实际发生碰撞之前，碰撞检测

系统就发出碰撞信号，如图10-28所示是球体碰撞检测中可能出现的坏情况，

其解决方法是缩小检测半径，或者使用其他检测模型，如图10-29所示。

图10-28球体碰撞的坏情况图10-29缩小检测半径

为了解决包容球精确度不高的问题，人们又提出了球体树的方法。

球体树实际上是一种表达3D物体的层次结构。对一个形状复杂的3D物体，先用一个大球体包容整个物体，然后对物体的各个主要部分用小一点的球体来

表示，然后对更小的细节用更小的包容球体，这些球体和它们之间的层次关系

就形成了一个球体树。

举例来说，对一个游戏中的人物角色，可以用一个大球来表示整个人，然

后用中等大小的球体来表示四肢和躯干，然后用更小的球体来表示手脚等。这

样在对两个物体进行碰撞检测时，先比较两个最大的球体。

如果有重叠，则沿树结构向下遍历，对小一点的球体进行比较，直到没有

任何球体重叠，或者到了最小的球体，这个最小的球体所包含的部分就是碰撞

的部分，如图10-30所示。

10.3.3 AABB立方体边界框检测

用球体去近似地代表物体运算量很小，但在游戏中的大多数物体是方的或

者长条形的，应该用方盒来代表物体。另一种常见的检测模型是立方体边界框，如图10-31展示了一个AABB检测盒和它里面的物体。

坐标轴平行(Axially-aligned)不仅指盒体与世界坐标轴平行，同时也指盒体的每个面都和一条坐标轴垂直，这样一个基本信息就能减少转换盒体时操作

的次数。AABB技术在当今的许多游戏中都得到了应用，开发者经常用它们作为

模型的检测模型，再次指出，提高精度的同时也会降低速度。

因为AABB总是与坐标轴平行，不能在旋转物体时简单地旋转AABB，而是

应该在每一帧都重新计算。如果知道每个对象的内容，这个计算就不算困难，

也不会降低游戏的速度。然而，还面临着精度的问题。

假如有一个3D的细长刚性直棒，并且要在每一帧动画中都重建它的AABB。可以看到每一帧中的包装盒都不一样而且精度也会随之改变，如图10-32所示。

图10-31 3D模型与AABB检测盒图10-32不同方向的AABB

可以注意到AABB对物体的方向很敏感，同一物体的不同方向，AABB也可

能不同(由于球体只有一个自由度，所以检测球对物体方向不敏感)。

当物体在场景中移动时，它的AABB也需要随之移动，当物体发生旋转时，有两种选择：用变换后的物体来重新计算AABB，或者对AABB做和物体同样的

变换。

如果物体没有发生扭曲，可以通过"变换后的AABB"重新计算，因为该方法要比通过"变换后的物体"计算快得多，因为AABB只有8个顶点。变换AABB得出新的AABB要比变换物体的运算量小，但是也会带来一定的误差，如图10-33所示。

比较图中原AABB(灰色部分)和新AABB(右边比较大的方框)，它是通过旋转后的AABB计算得到的，新AABB几乎是原来AABB的两倍，注意，如果从旋转后的物体而不是旋转后的AABB来计算新AABB，它的大小将和原来的AABB相同。

先介绍AABB的表达方法，AABB内的点满足以下条件：

xmin≤x≤xmax ymin≤y≤ymax zmin≤z≤zmax

因此只需要知道两个特别重要的顶点(xmin，ymin，zmin)、(xmax，ymax，zmax)，记作：

float min=new float{0.0f,0.0f,0.0f}；

float max=new float{0.0f,0.0f,0.0f}；

中心点是两个顶点的中点，代表了包装盒的质点。

float center=new float{0.0f,0.0f,0.0f}；

中心点的计算方法如下：

float center(){

center[0]=(min[0]+max[0])*0.5f；

center[1]=(min[1]+max[1])*0.5f；

center[2]=(min[2]+max[2])*0.5f；

return center；

通过这两个顶点可以知道以下属性。

float xSize(){return(max[0]-min[0])；}

float ySize(){return(max[1]-min[1])；}

float zSize(){return(max[2]-min[2])；}

float size(){return(max[0]-min[0])*(max[1]-min[1])*(max[2]-min[2])；}

当添加一个顶点到包装盒时，需要先与这两个顶点进行比较。

void add(float p){

if(p[0]min[0])min[0]=p[0]；

if(p[0]max[0])max[0]=p[0]；

if(p[1]min[1])min[1]=p[1]；

if(p[1]max[1])max[1]=p[1]；

if(p[2]min[2])min[2]=p[2]；

if(p[2]max[2])max[2]=p[2]；

检测包装盒是否为空，可以将这两个顶点进行比较。

boolean isEmpty(){

return(min[0]max[0])||(min[1]max[1])||(min[2]max[2])；

检测某个点是否属于AABB范围之内的代码如下：

boolean contains(float p){

return

(p[0]=min[0])&&(p[0]=max[0])&&

(p[1]=min[1])&&(p[1]=max[1])&&

(p[2]=min[2])&&(p[2]=max[2])；

AABB的静态检测比较简单，检测两个静止包装盒是否相交，它是一种布尔测试，测试结果只有相交或者不相交。这里我们还提供了获取相交范围信息的方法，一般来说，这种测试的目的是为了返回一个布尔值。碰撞的示意如图10-34所示。

图10-34包装盒的碰撞

检测静态AABB碰撞的方法如下：

boolean intersectAABBs(AABB box2,AABB boxIntersect)

float box2_min=box2.getMin()；

float box2_max=box2.getMax()；

if(min[0]box2_max[0])return false；

if(max[0]box2_min[0])return false；

if(min[1]box2_max[1])return false；

if(max[1]box2_min[1])return false；

if(min[2]box2_max[2])return false；

if(max[2]box2_min[2])return false；

if(boxIntersect！=null){

float box_intersect_min=new float[3]；

float box_intersect_max=new float[3]；

box_intersect_min[0]=Math.max(min[0],box2_min[0])；

box_intersect_max[0]=Math.min(max[0],box2_max[0])；

box_intersect_min[1]=Math.max(min[1],box2_min[1])；

box_intersect_max[1]=Math.min(max[1],box2_max[1])；

box_intersect_min[2]=Math.max(min[2],box2_min[2])；

box_intersect_max[2]=Math.min(max[2],box2_max[2])；

return true；

可以利用AABB的结构来加快新的AABB的计算速度，而不用变换8个顶点，再从这8个顶点中计算新AABB。下面简单地回顾4×4矩阵变换一个3D点的过程。

通过原边界框(xmin，ymin，zmin，xmax，ymax，zmax)计算新边界框(，，，，，)，现在的任务是计算的速度。换句话说，希望找到

m11x+m12y+m13z+m14的最小值。其中[x，y，z]是原8个顶点中的任意一个。

变换的目的是找出这些点经过变换后哪一个的x坐标最小。看第一个乘积

m11x，为了最小化乘积，必须决定是用xmin还是xmax来替换其中的x。显然，如果m11>0，用xmin能得到最小化的乘积；如果m11<0，则用xmax能得到最小化乘积。

比较方便的是，不管xmin还是xmax中哪一个被用来计算，都可以用另外

一个来计算。可以对矩阵中的9个元素中的每一个都应用这个计算过程(其他元素不影响大小)。

根据变换矩阵和原有的AABB包装盒计算新的AABB包装盒的代码如下：

void setToTransformedBox(Transform t)

if(isEmpty()){//判断包装盒是否为空

return；

float m=new float[16]；

t.get(m)；//将变换矩阵存入数组

float minx=0,miny=0,minz=0；

float maxx=0,maxy=0,maxz=0；

minx+=m[3]；//x方向上平移

maxx+=m[3]；//x方向上平移

miny+=m[7]；//y方向上平移

maxy+=m[7]；//y方向上平移

minz+=m[11]；//z方向上平移

maxz+=m[11]；//z方向上平移

if(m[0]0.0f){

minx+=m[0]*min[0]；maxx+=m[0]*max[0]；}else{

minx+=m[0]*max[0]；maxx+=m[0]*min[0]；if(m[1]0.0f){

minx+=m[1]*min[1]；maxx+=m[1]*max[1]；}else{

minx+=m[1]*max[1]；maxx+=m[1]*min[1]；if(m[2]0.0f){

minx+=m[2]*min[2]；maxx+=m[2]*max[2]；}else{

minx+=m[2]*max[2]；maxx+=m[2]*min[2]；if(m[4]0.0f){

miny+=m[4]*min[0]；maxy+=m[4]*max[0]；}else{

miny+=m[4]*max[0]；maxy+=m[4]*min[0]；if(m[5]0.0f){

miny+=m[5]*min[1]；maxy+=m[5]*max[1]；}else{

miny+=m[5]*max[1]；maxy+=m[5]*min[1]；if(m[6]0.0f){

miny+=m[6]*min[2]；maxy+=m[6]*max[2]；}else{

miny+=m[6]*max[2]；maxy+=m[6]*min[2]；if(m[8]0.0f){

minz+=m[8]*min[0]；maxz+=m[8]*max[0]；}else{

minz+=m[8]*max[0]；maxz+=m[8]*min[0]；

if(m[9]0.0f){

minz+=m[9]*min[1]；maxz+=m[9]*max[1]；

}else{

minz+=m[9]*max[1]；maxz+=m[9]*min[1]；

if(m[10]0.0f){

minz+=m[10]*min[2]；maxz+=m[10]*max[2]；

}else{

minz+=m[10]*max[2]；maxz+=m[10]*min[2]；

min[0]=minx；min[1]=miny；min[2]=minz；//用新的AABB坐标替换原有坐标

max[0]=maxx；max[1]=maxy；max[2]=maxz；//用新的AABB坐标替换原有坐标

为了使用AABB包装盒进行碰撞检测，将这些方法和属性封装为AABB类，代码如下：

import https://www.sodocs.net/doc/b010470300.html,ng.Math；

import javax.microedition.m3g.Transform；

class AABB{

public AABB(){}

float getMin(){return min；}

float getMax(){return max；}

void setMin(float x,float y,float z){min[0]=x；min[1]=y；

min[2]=z；}

void setMax(float x,float y,float z){max[0]=x；max[1]=y；

max[2]=z；}

void reset(){

for(int i=0；i 3；i++)

min[i]=0；

max[i]=0；

//其他方法同上

为了检验碰撞检测的使用构造了两个立方体，并各自绑定了一个包装盒。

/*立方体1*/

mesh1=createCube()；//创建立方体1

mesh1.setTranslation(1.0f,0.0f,0.0f)；//平移

mesh1.setOrientation(90,0.0f,1.0f,0.0f)；//旋转

mesh1.setScale(0.5f,0.5f,0.5f)；//缩放

box1=new AABB()；//包装盒

box1.setMin(-1.0f,-1.0f,-1.0f)；//设置包装盒1的最小顶点

box1.setMax(1.0f,1.0f,1.0f)；//设置包装盒1的最大顶点

mesh1.getCompositeTransform(cubeTransform)；//获取立方体1的混合矩阵

box1.setToTransformedBox(cubeTransform)；//将变换矩阵应用到包装盒中

world.addChild(mesh1)；//将立方体1添加到场景中

/*立方体2*/

mesh2=createCube()；//创建立方体2 mesh2.setTranslation(-

0.5f,0.0f,0.0f)；//平移

mesh2.setScale(0.5f,0.5f,0.5f)；//缩放

box2=new AABB()；//包装盒

box2.setMin(-1.0f,-1.0f,-1.0f)；//设置包装盒2的最小顶点

box2.setMax(1.0f,1.0f,1.0f)；//设置包装盒2的最大顶点

mesh2.getCompositeTransform(cubeTransform)；//获取立方体2的混合矩阵

box2.setToTransformedBox(cubeTransform)；//将变换矩阵应用到包装盒2中

world.addChild(mesh2)；//将立方体2添加到场景中

检测包装盒1和包装盒2是否碰撞的代码如下：

isCollided=box1.intersectAABBs(box2,null)；//检测两个AABB包装盒是否碰撞

编译运行程序，设置两个立方体不同的位置和角度，可以比较精确地检测出它们的碰撞情况，如图10-35所示。

检测两个静止AABB的碰撞情况比较简单，只需要在每一维上单独检查它们的重合程度即可。如果在所有维上都没有重合，那么这两个AABB就不会相交。

AABB间的动态检测稍微复杂一些，考虑一个由顶点smin和smax指定的静

态包装盒和一个由顶点mmin和mmax指定的动态包装盒(如果两个都是动态的，可以根据相对运动视作如此)。运动的速度由向量s给出，运动时间t假定为

0~1。

图10-35静态物体碰撞检测示意

移动检测的目标是计算运动AABB碰撞到静态AABB的时刻，因此需要计算

出两个AABB在所有维上的第一个点。为了简化起见，可以把上述问题先归结到某一维，然后再将三维结合到一起。假设把问题投影到x轴，如图10-36所示。

图10-36 AABB的动态检测

黑色矩形代表沿坐标轴滑动的AABB，t=0时，运动AABB完全位于静止

AABB的左边。当t=1时，运动AABB完全位于静止AABB的右边。当t=tenter 时，两个AABB刚刚相交，当t=tleave时，两个AABB脱离碰撞。

对照上图，可以推导出两个AABB接触和离开的时间：

AABB的动态检测有3个要点。

n如果速度为0，两个包装盒要么一直相交，要么一直分离。

n不管物体从哪个方向运动，碰撞过程中，肯定是先入后出，所以有

tenter

n如果tenter和tleave超出运动时间范围，那么在此范围内它们是不相

交的。

检测出某一维的碰撞还不够，还需要进行其他两维的检测，然后取结果的

交集。如果交集为空，那么两AABB包装盒没有相交，如果区间范围在时间段[0，1]之外，那么在此区间也不相交。对AABB进行动态检测的方法定义如下：

float intersectMovingAABB(AABB stationaryBox,AABB movingBox,float s)

float NoIntersection=1e30f；//没有碰撞则返回大数

float tEnter=0.0f；//初始化碰撞时间

float tLeave=1.0f；//初始化离开时间

float Swap=0.0f；//交换操作中间变量

float sBoxmin=stationaryBox.getMin()；//静止包装盒的最小值顶点float sBoxmax=stationaryBox.getMax()；//静止包装盒的最大值顶点float mBoxmin=movingBox.getMin()；//运动包装盒的最小值顶点

float mBoxmax=movingBox.getMax()；//运动包装盒的最大值顶点

if(s[0]==0.0f){//如果x方向速度为0

if((sBoxmin[0]=mBoxmax[0])||(sBoxmax[0]=mBoxmin[0])){ return NoIntersection；//进行静态检测

}else{

float xEnter=(sBoxmin[0]-mBoxmax[0])/s[0]；//计算碰撞时间

float xLeave=(sBoxmax[0]-mBoxmin[0])/s[0]；//计算离开时间

if(xEnter xLeave){//检查顺序

Swap=xEnter；

xEnter=xLeave；

xLeave=Swap；

if(xEnter tEnter)tEnter=xEnter；//更新区间

if(xLeave tLeave)tLeave=xLeave；

if(tEnter tLeave){//是否导致空重叠区

return NoIntersection；//没有碰撞

if(s[1]==0.0f){//y轴速度为0

if((sBoxmin[1]=mBoxmax[1])||(sBoxmax[1]=mBoxmin[1])){ return NoIntersection；//没有相交

}else{

float yEnter=(sBoxmin[1]-mBoxmax[1])/s[1]；

float yLeave=(sBoxmax[1]-mBoxmin[1])/s[1]；

if(yEnter yLeave){

Swap=yEnter；

yEnter=yLeave；

yLeave=Swap；

if(yEnter tEnter)tEnter=yEnter；//更新区间

if(yLeave tLeave)tLeave=yLeave；

if(tEnter tLeave){

return NoIntersection；

if(s[2]==0.0f){//z方向速度为0

if((sBoxmin[2]=mBoxmax[2])||(sBoxmax[2]=mBoxmin[2])){ return NoIntersection；

}else{

float oneOverD=1.0f/s[2]；

float zEnter=(sBoxmin[2]-mBoxmax[2])/s[2]；

float zLeave=(sBoxmax[2]-mBoxmin[2])/s[2]；

if(zEnter zLeave){

Swap=zEnter；

zEnter=zLeave；

zLeave=Swap；

if(zEnter tEnter)tEnter=zEnter；//更新区间

if(zLeave tLeave)tLeave=zLeave；

if(tEnter tLeave){

return NoIntersection；

return tEnter；//返回碰撞时间

为了对移动AABB进行检测，创建两个AABB如图10-37所示。两个包装盒距离0.5，速度为3。

图10-37移动AABB检测

检测代码如下：

float speed=new float{3.0f,0.0f,0.0f}；

float tEnter=intersectMovingAABB(box1,box2,speed)；

输出结果为0.16667，完全符合预期的猜测。

10.3.4 OBB树碰撞检测

前面提到了长条物体在旋转时AABB盒的变化，那么是否有能够在任意方向都更为精确的检测方式，答案是肯定的，这是一种基于OBB即定向包容盒子(Oriented Bounding Box,OBB)的技术，它已经广泛用于光线追踪和碰撞检测中。

OBB这种方法是根据物体本身的几何形状来决定盒子的大小和方向，盒子

无须和坐标轴垂直。这样就可以选择最合适的最紧凑的包容盒子。OBB盒子的

生成比较复杂。一般是考虑物体所有的顶点在空间的分布，通过一定的算法找

到最好的方向(OBB盒子的几个轴)。

一个2D示意图如图10-38所示。

这种技术比AABB技术更精确而且更健壮，但OBB实现起来比较困难，执行速度慢，并且不太适合动态的或柔性的物体。特别注意的是，当把一个物体分

得越来越小的时候，事实上是在创建一棵有层次的树，如图10-39所示。

图10-39 OBB树的生成(曲折线为物体)

为任意的网格模型创建OBB树可能是算法里最难的一个部分，而且它还要

调整以适合特定的引擎或游戏类型。从图中可以看出，不得不找出包围给定模

型的最近似的包装盒(或者其他3D体)。

现在得到了所有的包装盒，下一步将构造一棵树。

从最初的AABB包装盒开始从上至下地反复分割它。另外，还可以用从下至上的方式，逐步地合并小包装盒从而得到最大的包装盒。把大的包装盒分割成

小的包装盒，应该遵守以下几条原则。

(1)用一个面(这个面垂直于包装盒中的一条坐标轴)来分割包装盒上最长的轴，然后根据多边形处在分割轴的哪一边把多边形分离开来(如图10-38所示)。

(2)如果不能沿着最长的轴进行分割，那就沿第二长的边分割。持续地分割直到包装盒不能再分割为止。

(3)依据需要的精度(比如，是否真的要判断单个三角形的碰撞)，可以按选择的方式(是按树的深度或是按包装盒中多边形的数目)以任意的条件停止分割。

正如读者所看到的，创建阶段相当复杂，其中包括了大量的运算，很明显

不能实时地创建树，只能是事先创建。事先创建可以免去实时改变多边形的可能。另一个缺点是OBB要求进行大量的矩阵运算，不得不把它们定位在适当的

地方，并且每棵子树必须与矩阵相乘。

现在假设已经有了OBB或者AABB树。那么该怎么进行碰撞检测呢?首先检

测最大的包装盒是否相交(AABB级别)，如果相交了，它们可能(注意，只是可能)发生了碰撞，接下来将进一步地递归处理它们(OBB级别，不断地递归用下

一级进行处理)。

如果沿着下一级，发现子树并没有发生相交，这时就可以停止，并得出结

论没有发生碰撞。如果发现子树相交，那么要进一步处理它的子树直到到达叶

子节点，并最终得出结论。

碰撞检测最直观的想法是把一个OBB盒子的每个边都和另一个盒子的所有

面来比较，如果这个边穿过了另一个OBB盒子的一个面，则两个OBB盒子发生

了碰撞。显然这种方法的计算量是比较大的，因为要进行12×6×2=144次边和面的比较。

但是，在考察两个没有碰撞的OBB盒子时，人们发现一些规律来简化比较。

(1)如果两个OBB盒子不互相接触，则应该可以找到一个盒子上的一个面，这个面所在的平面可以把3D空间分为两部分，两个OBB盒子各在两边。

(2)如果没有这样的表面存在，则一定可以在两个OBB盒子上各找出一条边，这两条边所在的平面可以把两个OBB盒子分在两边。有了这个平面，就可以找

到垂直于它的分割轴(separating axis)，如图10-40所示。

(3)进行相交测试时，可以把包装盒投影到分割轴上，并检查它们是否线性相交。两个OBB盒子在这个分割轴上的投影将是分离的。

如上所述，要判断两个OBB盒子是否碰撞，只需要看两个OBB盒子之间是

否有这样的平面和分割轴存在。如果存在，则没有碰撞。如果不存在，则碰撞。对第一种情况，每个盒子有6个表面(其中每两个平行)，可以决定3个分割轴。两个OBB盒子一共有6个可能的分割轴需要考虑。对第二种情况，两个OBB盒

子之间的边的组合可以有3×3=9种情况，也就是有9个可能的分割轴。这样对任意两个OBB盒子，只需要考察15个分割轴就可以了。如果在任一分割轴上的阴影不重合，则OBB盒子之间没有碰撞。

选择AABB还是选择OBB应该根据所需的精确程度而定。对一个需要快速反应的3D射击游戏来说，可能用AABB来进行碰撞检测更好些--可以牺牲一些精度来换取速度和实现的简单化，因此总能在游戏中看到一些小疏漏。当然随着硬件能力的提高，OBB处理会逐渐被重视起来。

在做碰撞检测时应当遵循以下的优化理论，这样可以改善检测速度。

n分两步检验，距离远时看作质点，距离近时采用包装盒。

n距离很远的物体不会在短时间内相撞(可以采用BSP树分割空间)。

n一个物体不能隔着第二个物体和第三个物体相撞。

n一旦一个物体检测到和另一物体碰撞，另一物体对这个物体不再检测。

n静止的物体不主动与其他物体碰撞。

10.3.5碰撞反应

碰撞以后需要做一些反应，比如说产生反冲力反弹出去，或者停下来，或者让阻挡物体飞出去，或者穿墙，而碰撞最讨厌的就是穿越，因为这通常不合逻辑。

首先看看弹性碰撞。弹性碰撞就是初中物理中说的动量守恒。物体在碰撞前后的动量守恒，没有任何能量损失。这样的碰撞用于打砖块的游戏中。引入质量的概念，有的物体会具有一定的质量，这些物体通常来说需要在碰撞以后进行另外一个方向的运动，另外一些物体设定为质量无限大，这些物体通常是碰撞墙壁。

当物体碰到质量非常大的物体，默认为碰到了一个弹性物体，其速度会改变，但是能量不会受到损失。一般在代码上的做法就是在速度向量上加上一个负号。

图像识别技术的研究现状论文

图像识别技术研究现状综述 简介： 图像识别是指图形刺激作用于感觉器官，人们辨认出它是经验过的某一图形的过程,也叫图像再认。在图像识别中,既要有当时进入感官的信息,也要有记忆中存储的信息。只有通过存储的信息与当前的信息进行比较的加工过程，才能实现对图像的再认。图像识别技术是以图像的主要特征为基础的，在图像识别过程中，知觉机制必须排除输入的多余信息,抽出关键的信息。在人类图像识别系统中，对复杂图像的识别往往要通过不同层次的信息加工才能实现。对于熟悉的图形,由于掌握了它的主要特征，就会把它当作一个单元来识别，而不再注意它的细节了。这种由孤立的单元材料组成的整体单位叫做组块，每一个组块是同时被感知的。图像在人类的感知中扮演着非常重要的角色，人类随时随处都要接触图像。随着数字图像技术的发展和实际应用的需要，出现了另一类问题，就是不要求其结果输出是一幅完整的图像，而是将经过图像处理后的图像，再经过分割和描述提取有效的特征，进而加以判决分类，这就是近20年来发展起来的一门新兴技术科学一图像识别。它以研究某些对象或过程的分类与描述为主要内容，以研制能够自动处理某些信息的机器视觉系统，代替传统的人工完成分类和辨识的任务为目的。 图像识别的发展大致经历了三个阶段：文字识别、图像处理和识别及物体识别：文字识别的研究是从1950年开始的，一般是识别字母、数字和符号，并从印刷文字识别到手写文字识别，应用非常广泛，并且已经研制了许多专用设备。图像处理和识别的研究，是从1965年开始的。过去人们主要是对照相技术、光学技术的研究，而现在则是利用计算技术、通过计算机来完成。计算机图像处理不但可以消除图像的失真、噪声，同时还可以进行图像的增强与复原，然后进行图像的判读、解析与识别，如航空照片的解析、遥感图像的处理与识别等，其用途之广，不胜枚举。物体识别也就是对三维世界的认识，它是和机器人研究有着密切关系的一个领域，在图像处理上没有特殊的难点，但必须知道距离信息，并且必须将环境模型化。在自动化技术已从体力劳动向部分智力劳动自动化发展的今天，尽管机器人的研究非常盛行，还只限于视觉能够观察到的场景。进入80年代，随着计算机和信息科学的发展，计算机视觉、人工智能的研究已成为新的动向 图像识别与图像处理的关系： 在研究图像时，首先要对获得的图像信息进行预处理（前处理）以滤去干扰、噪声，作几何、彩色校正等，以提供一个满足要求的图像。图像处理包括图像编码，图像增强、图像压缩、图像复原、图像分割等。对于图像处理来说，输入是图像，输出（即经过处理后的结果）也是图像。图像处理主要用来解决两个问题：一是判断图像中有无需要的信息；二是确定这些信息是什么。图像识别是指对上述处理后的图像进行分类，确定类别名称，它可以在分割的基础上选择需要提取的特征，并对某些参数进行测量，再提取这些特征，然后根据测量结果做出分类。为了更好地识别图像，还要对整个图像做结构上的分析，对图像进行描述，以便对图像的主要信息做一个好的解释，并通过许多对象相互间的结构关系对图像加深理解，以便更好帮助和识别。故图像识别是在上述分割后的每个部分中，找出它的形状及纹理特征，以便对图像进行分类，并对整个图像做结构上的分析。因而对图像识别环节来说，输入是图像（经过上述处理后的图像），输出是类别和图像的结构分析，而结构分析的结果则

碰撞检测

二维碰撞检测算法 碰撞检测（Collision Detection,CD）也称为干涉检测或者接触检测，用来检测不同对象之间是否发生了碰撞，它是计算机动画、系统仿真、计算机图形学、计算几何、机器人学、CAD\ CAM等研究领域的经典问题。 碰撞物体可以分为两类：面模型和体模型。面模型是采用边界来表示物体，而体模型则是使用体元表示物体。面模型又可根据碰撞后物体是否发生形变分为刚体和软体，刚体本身又可根据生成方式的不同分为曲面模型和非曲面模型。目前对于碰撞的研究多集中于面模型的研究，因为体模型是一种三维描述方式，对它进行碰撞检测代价较高。而在面模型的研究中，对刚体的研究技术更为成熟。 下面列举几种常用的碰撞检测技术： 1：包围盒（bounding box）是由Clark提出的，基本思想是使用简单的几何形体包围虚拟场景中复杂的几何物体，当对两个物体进行碰撞检测时，首先检查两个物体最外层的包围盒是否相交，若不相交，则说明两个物体没有发生碰撞，否则再对两个物体进行检测。基于这个原理，包围盒适合对远距离物体的碰撞检测，若距离很近，其物体之间的包围盒很容易相交，会产生大量的二次检测，这样就增大了计算量。 包围盒的类型主要有AABB(Aligned Axis Bounding Box)沿坐标轴的包围盒、包围球、OBB(Oriented Bounding Box)方向包围盒和k-DOP(k Discrete Orientation Polytopes)离散方向多面体等。 AABB是包含几何对象且各边平行于坐标轴的最小六面体，两个AABB包围盒相交当且仅当它们三个坐标轴上的投影均重叠，只要存在一个方向上的投影不重叠，那么它们就不相交。AABB间的相交测试和包围体的更新速度比其他算法

关于人脸识别技术的发展研究

人脸识别技术优势 863计划、国家科技支撑计划、自然科学基金都拨出专款资助人脸识别的相关研究。国家“十一五”科技发展规划中也将人脸识别技术的研究与发展列入其中[4]，明确指出：“要在生物特征识别技术领域缩小与世界先进水平的差距，开展生物特征识别应用技术研究，人脸识别具有高安全性、低误报率的出入口控制新产品。”在这种环境下，国内一些科研院所和院校在人脸识别技术方面取得了很大进展。如中科院自动化所，清华大学，中科院计算所自主开发的人脸识别技术已经达到了国际先进的水平。人脸识别作为一种新兴的生物特征识别技术(Biometrics)，与虹膜识别、指纹扫描、掌形扫描等技术相比，人脸识别技术在应用方面具有独到的优势： 1.人脸识别使用方便，用户接受度高。人脸识别技术使用通用的摄像机作为识别信息获取装置，以非接触的方式在识别对象未察觉的情况下完成识别过程。 2.直观性突出。人脸识别技术所使用的依据是人的面部图像，而人脸无疑是肉眼能够判别的最直观的信息源，方便人工确认、审计，“以貌取人”符合人的认知规律。 3.识别精确度高，速度快。与其它生物识别技术相比，人脸识别技术的识别精度处于较高的水平，误识率、拒认率较低。 4.不易仿冒。在安全性要求高的应用场合，人脸识别技术要求识别对象必须亲临识别现场，他人难以仿冒。人脸识别技术所独具的活性判别能力保证了他人无法以非活性的照片、木偶、蜡像来欺骗识别系统。这是指纹等生物特征识别技术所很难做到的。举例来说，用合法用户的断指即可仿冒合法用户的身份而使识别系统无从觉察。 5.使用通用性设备。人脸识别技术所使用的设备为一般的PC、摄像机等常规设备，由于目前计算机、闭路电视监控系统等已经得到了广泛的应用，因此对于多数用户而言使用人脸识别技术无需添置大量专用设备，从而既保护了用户的原有投资又扩展了用户已有设备的功能，满足了用户安全防范的需求。 6.基础资料易于获得。人脸识别技术所采用的依据是人脸照片或实时摄取的人脸图像，因而无疑是最容易获得的。 7.成本较低，易于推广使用。由于人脸识别技术所使用的是常规通用设备，价格均在一般用户可接受的范围之内，与其它生物识别技术相比，人脸识别产品具有很高的性能价格比。 概括地说，人脸识别技术是一种高精度、易于使用、稳定性高、难仿冒、性价比高的生物特征识别技术，具有极其广阔的市场应用前景。 我将人脸识别的一些应用列举出来，希望抛转引玉，大家不断完善，开拓更多的应用领域。 1）监控布控

虚拟手术中实时碰撞检测技术

虚拟手术中实时碰撞检测技术研究 彭 磊 张裕飞 王秀娟 （泰山医学院 信息工程学院 山东 泰安 271016） 摘 要： 碰撞检测是虚拟手术的关键技术，为提高检测速度，满足系统实时性的要求，提出空间剖分和层次包围盒相结合的方法。使用八叉树表示法对虚拟场景进行空间剖分，在叶节点构建层次包围盒。进行碰撞检测时属于不同八叉树节点的几何元素不会相交，否则使用层次包围盒算法继续进行检测，对于有可能相交的几何元素再进行精确相交检测。 关键词： 虚拟手术；碰撞检测；空间剖分；层次包围盒 中图分类号：TP391.9 文献标识码：A 文章编号：1671－7597（2012）1120029－02 进行碰撞检测时从八叉树的根节点开始，计算两几何元素0 引言 是否属于同一节点，如果不属于同一节点则不相交，如果属于虚拟手术是集医学、生物力学、材料学、计算机图形学、同一节点，递归的到下一级节点进行检查，直到发现两几何元虚拟现实等诸多学科为一体的交叉研究领域。虚拟手术在医学素属于同一叶节点，则需要进一步使用层次包围盒进行检查。 中的应用主要包括：手术计划与过程模拟、术中导航与监护、 2 层次包围盒 手术教学与训练等。碰撞检测是虚拟手术系统中的关键技术，贯穿于虚拟手术的整个过程。 对于八叉树的每个叶节点包含的几何元素，建立层次包围虚拟手术系统中的对象根据材质可分为刚体组织和软件组盒（Bounding Volume Hierarchy ，BVH ）。相对于单纯的层次织。骨骼、手术器械等属于刚体组织，而人体的许多器官如肌包围盒技术，使用空间剖分与层次包围盒相结合的方法进行碰肉、血管、肝脏等属于软体组织。以往大部分碰撞检测的研究撞检测，构建的层次树规模更小，计算量更少。层次包围工作都是针对刚体对象的。与刚体相比较，软体组织由于其特殊的物理性质，在外力或某些操作的作用下会发生几何形状、位置甚至数量上的变化，因此基于软体组织的碰撞检测需要更详细的信息和更多的处理。 最简单的碰撞检测方法是对场景中的几何元素进行两两相2交测试，其时间复杂度为O(n )，虽然这种方法可以得到正确的结果，但是当场景中的几何模型稍微增多些，其实时性便无法满足实际的需求。为了尽可能地减少参与相交测试的几何元素的数量，提高系统的实时性，目前碰撞检测技术使用的主要算法有：层次包围盒法，空间分割法，基于网格剖分的方法[1]。但是这些经典的算法也都存在着构造难度大、紧密性差、相交测试复杂、效率低等缺点。 本文采用空间剖分和层次包围盒相结合的方法，简化了几何信息的表示，进行碰撞检测时可排除明显不相交的几何元素，无法排除的再进行精确相交检测，从而减少计算量，加速碰撞检测速度，提高系统实时性。 1 空间剖分技术 整个虚拟手术的场景空间递归的剖分成若干个网格单元，每一个几何元素都属于某个网格单元，处于同一网格单元内的几何元素才有相交的可能，不在同一网格单元的几何元素一定不会相交。采用八叉树的表示方法进行空间剖分。即包含整个场景的立方体作为八叉树的根节点，立方体的3条棱边分别与x ，y ，z 轴平行。递归的将立方体剖分为8个小块，如图1（a ）所示，生成8个子节点，直到达到指定的剖分层次为止，如图1（b ）所示，每个叶节点包含有限个几何元素。 图1 八叉树表示法 盒包括包围盒和层次树两种数据结构。 2.1 包围盒 包围盒技术是减少相交检测次数，降低碰撞检测复杂度的一种有效的方法。其基本思想是用几何形状相对简单的封闭表面将一复杂几何元素包裹起来，首先进行包围盒之间的相交测试，排除明显不相交的几何元素，无法排除的几何元素，再进一步进行精确的相交测试，从而达到减少相交测试计算量的目的。常见的包围盒类型有：包围球（Bounding Sphere ）、沿坐标轴的包围盒（Axis Aligned Bounding Box ，AABB ）、方向包围盒（Oriented Bounding Box ，OBB ）。离散方向包围盒（k-Discrete Orientation Polytopes ，k-DOPs ）等[2]，如图2所示。 图2 包围盒 由于虚拟手术对实时性要求较高，本文选择AABB 型包围盒，AABB 是平行于坐标轴的，包含几何元素的最小正立方体。其优点是：1）易于构建，只需要计算所包含几何元素的顶点的x ，y ，z 坐标的最大值和最小值，存储6个浮点数即可；2）相交测试计算量小，相交测试时只需对两个包围盒在三个坐标轴上的投影分别进行比较，最多6次比较运算即可。 2.2 包围盒层次树 包围盒层次树即包围盒的层次结构，层次树的根节点包含某个八叉树叶节点几何元素的全集，向下逐层分裂，直到每个叶节点表示一个基本几何元素。常用的构建策略有自顶向下和自底向上两种。 自顶向下的方法首先建立根结点，利用基于全集的信息递归地将每个节点分裂为两个或多个子集，直至生成只包含一个 基本图元的叶结点为止，从而建立一棵自顶向下的包围盒层次 （ ）八叉树结构 （ ）节点的剖分

基于matlab的图像预处理技术研究文献综述

毕业设计文献综述 题目：基于matlab的图像预处理技术研究 专业：电子信息工程 1前言部分 众所周知，MATLAB在数值计算、数据处理、自动控制、图像、信号处理、神经网络、优化计算、模糊逻辑、小波分析等众多领域有着广泛的用途，特别是MATLAB的图像处理和分析工具箱支持索引图像、RGB 图像、灰度图像、二进制图像，并能操作*.bmp、*.jpg、*.tif等多种图像格式文件如。果能灵活地运用MATLAB提供的图像处理分析函数及工具箱，会大大简化具体的编程工作，充分体现在图像处理和分析中的优越性。 图像就是用各种观测系统观测客观世界获得的且可以直接或间接作用与人眼而产生视觉的实体。视觉是人类从大自然中获取信息的最主要的手段。拒统计，在人类获取的信息中，视觉信息约占60%，听觉信息约占20%，其他方式加起来才约占20%。由此可见，视觉信息对人类非常重要。同时，图像又是人类获取视觉信息的主要途径，是人类能体验的最重要、最丰富、信息量最大的信息源。通常，客观事物在空间上都是三维的(3D)的，但是从客观景物获得的图像却是属于二维(2D)平面的。 图像存在方式多种多样，可以是可视的或者非可视的，抽象的或者实际的，适于计算机处理的和不适于计算机处理的。 图像处理它是指将图像信号转换成数字信号并利用计算机对其进行处理的过程。图像处理最早出现于20世纪50年代，当时的电子计算机已经发展到一定水平，人们开始利用计算机来处理图形和图像信息。图像处理作为一门学科大约形成于20世纪60年代初期。早期的图像处理的目的是改善图像的质量，它以人为对象，以改善人的视觉效果为目的。图像处理中，输入的是质量低的图像，输出的是改善质量后的图像，常用的图像处理方法有图像增强、复原、编码、压缩等。首次获得实际成功应用的是美国喷气推进实验室（JPL）。他们对航天探测器徘徊者7号在 1964 年发回的几千张月球照片使用了图像处理技术，如几何校正、灰度变换、去除噪声等方法进行处理，并考虑了太阳位置和月球环境的影响，由计算机成功地绘制出月球表面地图，获得了巨大的成功。随后又对探测飞船发回的近十万张照片进行更为复杂的图像处理，以致获得了月球的地形图、彩色图及全景镶嵌图，获得了非凡的成果，为人类登月创举奠定了坚实的基础，也推动

浅析人工智能中的图像识别技术

浅析人工智能中的图像识别技术 本文从网络收集而来，上传到平台为了帮到更多的人，如果您需要使用本文档，请点击下载按钮下载本文档（有偿下载），另外祝您生活愉快，工作顺利，万事如意！ 图像识别技术是信息时代的一门重要的技术，其产生目的是为了让计算机代替人类去处理大量的物理信息。随着计算机技术的发展，人类对图像识别技术的认识越来越深刻。图像识别技术的过程分为信息的获取、预处理、特征抽取和选择、分类器设计和分类决策。文章简单分析了图像识别技术的引入、其技术原理以及模式识别等，之后介绍了神经网络的图像识别技术和非线性降维的图像识别技术及图像识别技术的应用。从中可以总结出图像处理技术的应用广泛，人类的生活将无法离开图像识别技术，研究图像识别技术具有重大意义。 1 图像识别技术的引入 图像识别是人工智能科技的一个重要领域。图像识别的发展经历了三个阶段：文字识别、数字图像处理与识别、物体识别。图像识别，顾名思义，就是对图像做出各种处理、分析，最终识别我们所要研究的

目标。今天所指的图像识别并不仅仅是用人类的肉眼，而是借助计算机技术进行识别。虽然人类的识别能力很强大，但是对于高速发展的社会，人类自身识别能力已经满足不了我们的需求，于是就产生了基于计算机的图像识别技术。这就像人类研究生物细胞，完全靠肉眼观察细胞是不现实的，这样自然就产生了显微镜等用于精确观测的仪器。通常一个领域有固有技术无法解决的需求时，就会产生相应的新技术。图像识别技术也是如此，此技术的产生就是为了让计算机代替人类去处理大量的物理信息，解决人类无法识别或者识别率特别低的信息。 图像识别技术原理 其实，图像识别技术背后的原理并不是很难，只是其要处理的信息比较繁琐。计算机的任何处理技术都不是凭空产生的，它都是学者们从生活实践中得到启发而利用程序将其模拟实现的。计算机的图像识别技术和人类的图像识别在原理上并没有本质的区别，只是机器缺少人类在感觉与视觉差上的影响罢了。人类的图像识别也不单单是凭借整个图像存储在脑海中的记忆来识别的，我们识别图像都是依靠图像所具有

图像处理技术的研究现状和发展趋势

图像处理技术的研究现状和发展趋势 庄振帅 数字图像处理又称为计算机图像处理，它是指将图像信号转换成数字信号并利用计算机对其进行处理的过程。数字图像处理最早出现于20世纪50年代，当时的电子计算机已经发展到一定水平，人们开始利用计算机来处理图形和图像信息。数字图像处理作为一门学科大约形成于20世纪60年代初期。早期的图像处理的目的是改善图像的质量，它以人为对象，以改善人的视觉效果为目的。图像处理中，输入的是质量低的图像，输出的是改善质量后的图像，常用的图像处理方法有图像增强、复原、编码、压缩等。首次获得实际成功应用的是美国喷气推进实验室（JPL）。他们对航天探测器徘徊者7号在1964年发回的几千张月球照片使用了图像处理技术，如几何校正、灰度变换、去除噪声等方法进行处理，并考虑了太阳位置和月球环境的影响，由计算机成功地绘制出月球表面地图，获得了巨大的成功。随后又对探测飞船发回的近十万张照片进行更为复杂的图像处理，以致获得了月球的地形图、彩色图及全景镶嵌图，获得了非凡的成果，为人类登月创举奠定了坚实的基础，也推动了数字图像处理这门学科的诞生。在以后的宇航空间技术，如对火星、土星等星球的探测研究中，数字图像处理都发挥了巨大的作用。数字图像处理取得的另一个巨大成就是在医学上获得的成果。1972年英国EMI公司工程师Housfield发明了用于头颅诊断的X射线计算机断层摄影装置，也就是我们通常所说的CT（Computer Tomograph）。CT的基本方法是根据人的头部截面的投影，经计算机处理来重建截面图像，称为图像重建。1975年EMI公司又成功研制出全身用的CT 装置，获得了人体各个部位鲜明清晰的断层图像。1979年，这项无损伤诊断技术获得了诺贝尔奖，说明它对人类作出了划时代的贡献。与此同时，图像处理技术在许多应用领域受到广泛重视并取得了重大的开拓性成就，属于这些领域的有航空航天、生物医学过程、工业检测、机器人视觉、公安司法、军事制导、文化艺术等，使图像处理成为一门引人注目、前景远大的新型学科。随着图像处理技术的深入发展，从70年代中期开始，随着计算机技术和人工智能、思维科学研究的迅速发展，数字图像处理向

图像识别技术发展状况及前景

医学图像配准技术 罗述谦综述 首都医科大学生物医学工程系(100054) 吕维雪审 浙江大学生物医学工程研究所(310027) 摘要医学图像配准是医学图像分析的基本课题,具有重要理论研究和临床应用价 值。本文较全面地介绍了医学图像配准的概念、分类、配准原理、主要的配准技术及评 估方法。 关键词医学图像配准多模 1 医学图像配准的概念 在做医学图像分析时,经常要将同一患者的几幅图像放在一起分析,从而得到该患者的多方面的综合信息,提高医学诊断和治疗的水平。对几幅不同的图像作定量分析,首先要解决这几幅图像的严格对齐问题,这就是我们所说的图像的配准。 医学图像配准是指对于一幅医学图像寻求一种(或一系列)空间变换,使它与另一幅医学图像上的对应点达到空间上的一致。这种一致是指人体上的同一解剖点在两张匹配图像上有相的空间位置。配准的结果应使两幅图像上所有的解剖点,或至少是所有具有诊断意义的点及手术感兴趣的点都达到匹配。 医学图像配准技术是90年代才发展起来的医学图像处理的一个重要分支。涉及“配准”的技术名词除registration外,mapping、matching、co-registration、integration、align-ment和fusion 等说法也经常使用。从多数文章的内容看,mapping偏重于空间映射;fu-sion指图像融合,即不仅包括配准,而且包括数据集成后的图像显示。虽然在成像过程之前也可以采取一些措施减小由身体移动等因素引起的空间位置误差,提高配准精度(称作数据获取前的配准preacquisition),但医学图像配准技术主要讨论的是数据获取后的(post-acquisition)配准,也称作回顾式配准(retrospective registration)。当前,国际上关于医学图像配准的研究集中在断层扫描图像( tomographic images,例如CT、MRI、SPECT、PET等)及时序图像(time seriesimages,例如fMRI及4D心动图像)的配准问题。 2 医学图像基本变换 对于在不同时间或/和不同条件下获取的两幅图像I1(x1,y1,z1)和I2(x2,y2,z2)配准,就是寻找一个映射关系P:(x1,y1,z1) (x2,y2,z2),使I1的每一个点在I2上都有唯一的点与之相对应。并且这两点应对应同一解剖位置。映射关系P表现为一组连续的空间变换。常用的空间几何变换有刚体变换(Rigid body transformation)、仿射变换(Affine transformation)、投影变换(Projec-tive transformation)和非线性变换(Nonlin-ear transformation)。 (1)刚体变换: 所谓刚体,是指物体内部任意两点间的距离保持不变。例如,可将人脑看作是一个刚体。 处理人脑图像,对不同方向成像的图像配准常使用刚体变换。刚体变换可以分解为旋转和平移:P(x)=Ax+b(1) x=(x,y,z)是像素的空间位置;A是3×3的旋转矩阵,b是3×1的平移向量。

图像识别与人工智能研究所发展规划报告

图像所学科建设与发展规划 根据学校建设世界知名高水平大学的发展目标，特制定图像所相应的学科建设与发展规划，以推动本学科的跨越式发展。 一、学科建设总体目标 （一）学科基础 图像识别与人工智能研究所（简称图像所）将继续以跻身于我国的国防科技的发展为切入点，从事发展巡航导弹中制导、末制导关键技术，承担相关预先研究和攻关科研任务为学科建设的主攻方向。 （1）目前本学科点共有五个研究方向： “计算机视觉与应用”、 “成像自动目标识别与精确制导技术”、 “多谱成像与遥感图像处理”、 “人工智能与思维科学” “面向模式识别的专用处理机与IC芯片设计”。 （2）本学科点现有科研人员26人，其中教授（含博士生导师）7人，副教授7人。科研教学梯队层次高，年龄、专业结构合理。现有教学科研用房4000 平方米。实验设备固定资产5000余万元，已初步形成先进、配套的教学、科研、开发环境和雄厚的技术储备。 （3）学科特点 模式识别与智能系统是信息科学技术领域中发展最迅速的前沿领域之一。

来自不同成像传感器的不同谱段的图像信号能全面揭示客观世界的各种特性，智能控制是人工智能与自动控制相结合的现代控制理论和技术，图像模式处理、识别与智能控制的结合构成了智能信息系统和智能自动化系统发展的基础，不仅科学意义深远而且有十分广阔的应用前景。本学科点的主要特色是紧密结合航天、航空和信息技术领域的国家目标，进行应用基础和应用技术的研究和开发，重点研究多谱段图像模式信息的获取、表示、处理、分析与智能系统领域的基础理论与关键技术，同时培养和造就本领域高层次、高质量的科技人才。本学科点具有特色和优势的研究方向是： ·计算机视觉与应用 在基于信息融合的信号处理、基于视觉、力觉和超声波接近觉的多传感器机器人系统和飞行器三维航迹规划技术方面具有特色，承担了国家重大型号XY-20末制导航迹规划攻关项目并进入型号研制。 ·成像自动目标识别与精确制导技术 开展面向复杂背景和随机环境下成像自动目标检测、识别、跟踪的新理论、新方法、新算法和新系统的研究，其特色是瞄准有关国家安全的国家目标,紧密结合航天航空高技术发展,在基于图象和图象序列的自动目标识别,景象匹配定位等精确制导领域开展应用基础和高技术的研究,并将一系列高水平成果应用于国防高技术武器系统中。 ·多谱成像与遥感图像处理 研究微波辐射特性及成像技术、激光雷达成像信号处理和遥感图像处理与

数字图像处理技术的现状及其发展方向(笔记)

数字图像处理技术的现状及其发展方向 一、数字图像处理历史发展 数字图像处理(Digital Image Processing)将图像信号转换成数字信号并利用计算机对其进行处理。 1.起源于20世纪20年代。 2.数字图像处理作为一门学科形成于20世纪60年代初期，美国喷气推进实验室(JPL)推动了数字图像处理这门学科的诞生。 3.1972年英国EMI公司工程师Housfield发明了用于头颅诊断的X射线计算机断层摄影装置即CT(Computer Tomograph)，1975年EMI公司又成功研制出全身用的CT装置,获得了人体各个部位鲜明清晰的断层图像。 4.从70年代中期开始,随着计算机技术和人工智能、思维科学研究的迅速发展,数字图像处理向更高、更深层次发展，人们已开始研究如何用计算机系统解释图像,实现类似人类视觉系统理解外部世界，其中代表性的成果是70年代末MIT的Marr提出的视觉计算理论。 二、数字图像处理的主要特点 1．目前数字图像处理的信息大多是二维信息,处理信息量很大,对计算机的计算速度、存储容量等要求较高。 2.数字图像处理占用的频带较宽,在成像、传输、存储、处理、显示等各个环节的实现上,技术难度较大,成本也高,这就对频带压缩技术提出了更高的要求。 3.数字图像中各个像素是不独立的,其相关性大。因此,图像处理中信息压缩的潜力很大。 4.由于图像是三维景物的二维投影,一幅图像本身不具备复现三维景物的全部几何信息的能力,要分析和理解三维景物必须作合适的假定或附加新的测量。在理解三维景物时需要知识导引,这也是人工智能中正在致力解决的知识工程问题。 5．一方面，数字图像处理后的图像一般是给人观察和评价的,因此受人的因素影响较大，作为图像质量的评价还有待进一步深入的研究；另一方面，计算机视觉是模仿人的视觉,人的感知机理必然影响着计算机视觉的研究,这些都是心理学和神经心理学正在着力研究的课题。 三、数字图像处理的优点 1.再现性好；图像的存储、传输或复制等一系列变换操作不会导致图像质量的退化。 2.处理精度高；可将一幅模拟图像数字化为任意大小的二维数组,现代扫描仪可以把每个像素的灰度等级量化为16位甚至更高。 3.适用面宽；图像可以来自多种信息源，图像只要被变换为数字编码形式后,均是用二维数组表示的灰度图像组合而成,因而均可用计算机来处理。 4.灵活性高；数字图像处理不仅能完成线性运算,而且能实现非线性处理,即凡是可以用数学公式或逻辑关系来表达的一切运算均可用数字图像处理实现。 四、数字图像处理过程及其主要进展 常见的数字图像处理有:图像的采集、数字化、编码、增强、恢复、变换、

实验四：基于BSP技术的室内场景渲染和碰撞检测

实验四：基于BSP???碰撞检测 姓名：班级：学号： 一、实验目 掌握BSP?原理； 熟悉Ogr?e中基于S P??法。 二、实验仪器 pc、visua?l studi?o 2010 、实验原理 ?过程 //网上检索B?S P相关 //利 Ogr?e实现基于B SP? 程?实现 ???A PI进行详细说明1、BSP相关? （1）BSP? BSP Trees??B i nar?y Space? Parti?o ning?trees? 二 ? 二 ?。 ： ?； 中?光照运算；BSP?预 。 （2）BSP原理? 顺 判定 BSP：二 ?。 ?????? 。 ??定过 ??? 一 ?B S P。 ?上 于 ?件Z Buf?f er?后向前画。

?于?Z B uff?e r?前向后 ? 于后画 ??遮挡而 Z?B uffe?r CUT 而 ?高。 筛选优化 ?进行顺 判?定? 中 ?上?? 过?筛选。 PVS ?减外BSP?过?进行进一 ?筛选优化?。 理?解Po?r tal： ??。Porta?l?于 一? 进行 ? 算 算 ?； 二 法??集合PV?S?候 同 ??? 关 候 ??PVS? 关 ? 。 前 ?D 候?BC?过PVS?测试 A一 ??C U T。

（3）BSP? BSP?流程： 1） ???PVS?信息； 2） ?； 3）??判 ????理； ? 中 判 上级 ?。 4） ????? 理（ ） 后 ?理 ； ? 理 ? 后 理? ； 5） ? 判 PVS??中? 进?行。 2、程 实现 ??相API? 详细?说明 多边 A 一 顶 位于多边 组 一 说多边 A位于多边 “前 ”参考左图。 想象一 一 盒 6 组 朝向盒说盒 一“凸多边 ”朝向盒 盒 “凸多边”。 图1.2 让 一 何确定一 图元集合 否一 “凸多边 ” 伪算法 ： （1） - 参 : o n –确定一 D 中 相 位置 参考多边 。 –待确定 D 中 。 返 值: 位于多边 哪一边。 功 : 确定一 位于 多边定义 哪一边。

数字图像处理技术的研究现状与发展方向

数字图像处理技术的研究现状与发展方向 孔大力崔洋 （山东水利职业学院，山东日照276826） 摘要：随着计算机技术的不断发展，数字图像处理技术的应用领域越来越广泛。本文主要对数字图像处理技术的方法、优点、数字图像处理的传统领域及热门领域及其未来的发展等进行相关的讨论。 关键词：数字图像处理；特征提取；分割；检索 引言 图像是指物体的描述信息，数字图像是一个物体的数字表示，图像处理则是对图像信息进行加工以满足人的视觉心理和应用需求的行为。数字图像处理是指利用计算机或其他数字设备对图像信息进行各种加工和处理，它是一门新兴的应用学科，其发展速度异常迅速，应用领域极为广泛。 数字图像处理的早期应用是对宇宙飞船发回的图像所进行的各种处理。到了70年代，图像处理技术的应用迅速从宇航领域扩展到生物医学、信息科学、资源环境科学、天文学、物理学、工业、农业、国防、教育、艺术等各个领域与行业，对经济、军事、文化及人们的日常生活产生重大的影响。 数字图像处理技术发展速度快、应用范围广的主要原因有两个。最初由于数字图像处理的数据量非常庞大，而计算机运行处理速度相对较慢，这就限制了数字图像处理的发展。现在计算机的计算能力迅速提高，运行速度大大提高，价格迅速下降，图像处理设备从中、小型计算机迅速过渡到个人计算机，为图像处理在各个领域的应用准备了条件。第二个原因是由于视觉是人类感知外部世界最重要的手段。据统计，在人类获取的信息中，视觉信息占60％，而图像正是人类获取信息的主要途径，因此，和视觉紧密相关的数字图像处理技术的潜在应用范围自然十分广阔。 1数字图像处理的目的 一般而言，对图像进行加工和分析主要有以下三方面的目的[1]： (1)提高图像的视感质量，以达到赏心悦目的目的。如去除图像中的噪声，改变图像中的亮度和颜色，增强图像中的某些成分与抑制某些成分，对图像进行几何变换等，从而改善图像的质量，以达到或真实的、或清晰的、或色彩丰富的、或意想不到的艺术效果。 (2)提取图像中所包含的某些特征或特殊信息，以便于计算机进行分析，例如，常用做模式识别和计算机视觉的预处理等。这些特征包含很多方面，如频域特性、灰度/颜色特性、边界/区域特性、纹理特性、形状/拓扑特性以及关系结构等。 (3)对图像数据进行变换、编码和压缩，以便于图像的存储和传输。 2数字图像处理的方法 数字图像处理按处理方法分，主要有以下三类，即图像到图像的处理、图像到数据的处理和数据到图像的处理[2]。 （1）图像到图像。图像到图像的处理，其输入和输出均为图像。这种处理技术主要有图像增强、图像复原和图像编码。 首先，各类图像系统中图像的传送和转换中，总要造成图像的某些降质。第一类解决方法不考虑图像降质的原因，只将图像中感兴趣的特征有选择地突出，衰减次要信息，提高图像的可读性，增强图像中某些特征，使处理后的图像更适合人眼观察和机器分析。这类方法就是图像增强。例如，对图像的灰度值进行修正，可以增强图像的对比度；对图像进行平滑，可以抑制混入图像的噪声；利用锐化技

实时视频图像的清晰度检测算法研究教案

实时视频图像的清晰度检测算法研究 2010-12-18 17:11:42 来源:微型机与应用 关键字：实时视频图像背景提取Sobel算子清晰度检测 实时视频图像的质量分析已成为众多应用领域性能好坏的关键因素之一，因此实时视频图像的清晰度检测变得尤为重要。目前针对实时视频图像清晰度检测的研究较少，图像清晰度检测算法的研究对象主要针对静止的图像。现有的图像清晰度检测算法大致分为空域和频域两类。在空域中多采用基于梯度的算法，如拉普拉斯(Laplace)算法、差分平方和(SPSMD)算法、Sobel算子等。此类算法计算简洁、快速、抗噪性能好、可靠性较高。在频域中多采用图像的FFT变换(或其他变换)，如功率谱(Power-spectra)算法等[1-2]。此类算法的检测效果好，但计算复杂度高、计算时间长，不适合应用在基于软件实现的实时检测系统中。 当前对实时视频图像的一种重要应用是对运动目标的检测，常用的目标检测方法有帧差法、背景减法、光流法及运动能量法[3]，其中最简单而又快捷的方法是背景差法。其基本思想是通过对输入图像与背景图像进行比较来分割运动目标，关键环节是背景图像的提取。目前常用的背景提取方法有多帧图像平均法、灰度统计法、中值滤波法、基于帧差的选择方法、单高斯建模等。参考文献[4]中对以上算法做了充分的研究。 本文是针对实时视频图像的清晰度检测，基于实时视频图像背景基本保持不变的环境。通过比较上述算法，针对实时视频图像的特点，提出一种基于背景提取与Sobel算子相结合的实时视频图像的清晰度检测算法。 1 实时视频图像的清晰度检测算法原理 当视频播放画面超过24帧/s时，根据视觉暂留原理，人眼无法辨别每幅单独的静态画面，看上去是平滑连续的视觉效果。视频中的事物通常分为静止和运动两类，连续多帧画面中保持静止的物体可视为静止的背景，连续多帧画面中位置变化的物体可视为运动的前景。因此，实时视频图像中的每帧图像都可以划分为静止的背景和运动的前景两类区域。由于视频序列图像中运动的前景区域随机变化，引起图像像素点梯度值的随机改变，使得实时视频图像的清晰度检测较难实现。因此，本文的算法是利用实时视频图像中静止的背景区域检测视频序列图像的清晰度，即由背景提取和清晰度检测两部分组成。 1.1 实时视频图像的背景提取

图像识别匹配技术原理

第1章绪论 1.1研究背景及意义 数字图像，又称数码图像或数位图像，是二维图像用有限数字数值像素的表示。通常，像素在计算机中保存为二维整数数组的光栅图像，这些值经常用压缩格式进行传输和储存。数字图像可以由许多不同的输入设备和技术生成，例如数码相机、扫描仪、坐标测量机等，也可以从任意的非图像数据合成得到，例如数学函数或者三维几何模型，三维几何模型是计算机图形学的一个主要分支。数字图像处理领域就是研究它们的变换算法。 数字图像处理(Digital Image Processing)是通过计算机对图像进行去除噪声、增强、复原、分割、提取特征等处理的方法和技术。数字图像处理的产生和迅速发展主要受三个因素的影响:一是计算机的发展;二是数学的发展(特别是离散数学理论的创立和完善);三是广泛的农牧业、林业、环境、军事、工业和医学等方面的应用需求的增长。 图像配准(Image registration)就是将不同时间、不同传感器(成像设备)或不同条件下(天候、照度、摄像位置和角度等)获取的两幅或多幅图像进行匹配、叠加的过程，它已经被广泛地应用于遥感数据分析、计算机视觉、图像处理等领域。 图像配准的方法迄今为止，在国内外的图像处理研究领域，已经报道了相当多的图像配准研究工作，产生了不少图像配准方法。总的来说，各种方法都是面向一定范围的应用领域，也具有各自的特点。比如计算机视觉中的景物匹配和飞行器定位系统中的地图匹配，依据其完成的主要功能而被称为目标检测与定位，根据其所采用的算法称之为图像相关等等。 基于灰度信息的图像配准方法一般不需要对图像进行复杂的预先处理，而是利用图像本身具有灰度的一些统计信息来度量图像的相似程度。主要特点是实现简单，但应用范围较窄，不能直接用于校正图像的非线性形变，在最优变换的搜索过程中往往需要巨大的运算量。经过几十年的发展，人们提出了许多基于灰度信息的图像配准方法，大致可以分为三类：互相关法（也称模板匹配法）、序贯相似度检测匹配法、交互信息法。 目前主要图像配准方法有基于互信息的配准方法，基于相关性的配准方法和基于梯度的配准方法。其中基于梯度的方法基本很少单独使用，而作为一个辅助

碰撞检测技术

碰撞检测技术 碰撞检测技术2011-05-06 23：00 技术--引擎2008-09-05 19：50：55阅读251 10.3碰撞检测技术 到目前为止，构造的各种对象都是相互独立的，在场景中漫游各种物体，墙壁、树木对玩家(视点)好像是虚设，可以任意从其中穿越。为了使场景人物更加完善，还需要使用碰撞检测技术。 10.3.1碰撞检测技术简介 无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。 好的碰撞检测要求人物在场景中可以平滑移动，遇到一定高度的台阶可以自动上去，而过高的台阶则把人物挡住，遇到斜率较小的斜坡可以上去，斜率过大则会把人物挡住，在各种前进方向被挡住的情况下都要尽可能地让人物沿合理的方向滑动而不是被迫停下。 在满足这些要求的同时还要做到足够精确和稳定，防止人物在特殊情况下穿墙而掉出场景。 做碰撞检测时，该技术的重要性容易被人忽视，因为这符合日常生活中的常识。如果出现Bug，很容易被人发现，例如人物无缘无故被卡住不能前进或者人物穿越了障碍。所以，碰撞检测是让很多程序员头疼的算法，算法复杂，容易出错。 对于移动终端有限的运算能力，几乎不可能检测每个物体的多边形和顶点的穿透，那样的运算量对手机等设备来讲是不可完成的，所以移动游戏上使用的碰撞检测不可能使用太精确的检测，而且对于3D碰撞检测问题，还没有几乎完美的解决方案。目前只能根据需要来取舍运算速度和精确性。

目前成功商业3D游戏普遍采用的碰撞检测是BSP树及AABB(axially aligned bounding box)包装盒(球)方式。简单地讲，AABB检测法就是采用一 个描述用的立方体或者球形体包裹住3D物体对象的整体(或者是主要部分)，之后根据包装盒的距离、位置等信息来计算是否发生碰撞，如图10-24所示。 除了球体和正方体以外，其他形状也可以作包装盒，但是相比计算量和方 便性来讲还是立方体和球体更方便些，所以其他形状的包装只用在一些特殊场 合使用。BSP树是用来控制检测顺序和方向的数据描述。 在一个游戏场景中可能存在很多物体，它们之间大多属于较远位置或者相 对无关的状态，一个物体的碰撞运算没必要遍历这些物体，同时还可以节省重 要的时间。 如果使用单步碰撞检测，需要注意当时间步长较大时会发生两个物体完全 穿透而算法却未检测出来的问题，如图10-25所示。其解决方案是产生一个4D 空间，在物体运动的开始和结束时间之间产生一个4D超多面体，用于穿透测试。 图10-24 AABB包装盒图10-25碰撞检测的单步失控和4D测试 读者在程序开发初期有必要对碰撞检测有一个初步的估计，以免最后把大 量精力消耗在碰撞检测问题上，从而降低了在基础的图形编程之上的注意力。 10.3.2球体碰撞检测 真实的物理模拟系统需要非常精确的碰撞检测算法，但是游戏中常常只需 要较为简单的碰撞检测，因为只需要知道物体什么时候发生碰撞，而不用知道 模型的哪个多边形发生了碰撞，因此可以将不规则的物体投影成较规则的物体 进行碰撞检测。 球体只有一个自由度，其碰撞检测是最简单的数学模型，我们只需要知道 两个球体的球心和半径就能进行检测。 那么球体碰撞是如何工作的?主要过程如下。 n计算两个物体中心之间的距离，并且将其与两个球体的半径和进行比较。

基于GJK的凸体快速连续碰撞检测研究

龙源期刊网 https://www.sodocs.net/doc/b010470300.html, 基于GJK的凸体快速连续碰撞检测研究 作者：刘丽等 来源：《河北科技大学学报》2014年第05期 摘要：针对一段时间内的多个运动物体之间的碰撞检测，提出一种基于距离算法（GilbertJohnsonKeerthialgorithm，GJK算法）的凸体快速连续碰撞检测算法，该算法主要通过判断一段时间内两物体之间的最小距离是否为零来检测碰撞发生情况。首先利用GJK算法在有限步骤内计算得到最小距离，检测两物体是否发生碰撞；若两物体发生碰撞，进而利用raycasting算法确定发生碰撞的精确位置，根据环境要求做出相应响应，调整运动物体位置。仿真结果表明，对多个运动物体间的连续碰撞检测，该算法有较高的实时性和准确性。 关键词：连续碰撞；GJK算法；运动物体；碰撞检测；凸体 中图分类号：TP391.9文献标志码：A Abstract：This paper presents a fast continuous collision detection algorithm to dealing with moving multiple convex objects within a period of time， which is based on the GilbertJohnsonKeerthi algorithm. The algorithm is determined by whether the minimum distance between the two objects within a period of time is zero to detect the occurrence of a collision. First，the algorithm utilizes GJK algorithm to calculate the minimum distance between the two objects and to detect the collision in finite steps. If two objects collide， then， determine the precise collision position of two objects based on the raycasting algorithm， and respond according to the environmental requirements， adjust two objects' location. The simulation results show that this algorithm has high realtime and accurate characteristics for continuous collision detection between multiple moving objects. Key words：continuous collision； GilbertJohnsonKeerthi（GJK） algorithm； moving objects； collision detection； convex objects 碰撞检测在计算机图形学、CAD/CAM、虚拟现实、虚拟制造、三维游戏等诸多领域都有广泛的应用，是提高虚拟场景物理真实感的关键问题之一[14]。按照场景模式不同，碰撞检测主要分为静态检测和动态检测。动态检测针对场景中至少存在一个运动物体的情况；根据碰撞检测方式的不同，动态检测分为离散检测和连续检测[5]。离散碰撞检测算法是对运动物体进 行取样检测，因此容易造成漏检测，进而产生穿透现象[6]。针对两物体间的穿透现象，连续 碰撞检测算法通过对一段连续时间内物体的运动过程进行建模，判断两物体之间的碰撞情况，可以很好地解决漏检测问题[6]，但计算量相对较大。目前，虚拟环境的场景复杂度越来越 高，对碰撞检测的实时性及准确性的要求也越来越高。因此，提高检测实时性及准确性是连续碰撞检测要解决的关键问题。