计算机算法类

1、上海电机学院毕业设计（论文）开题报告课题名称基于人工免疫系统的虚实交互碰撞检测技术研究学院 电子信息学院专业计算机科学与技术班 级 BX0901学号0835姓名张广琪指导教师赵孟德定稿日期：2011年12月23日基于人工免疫系统的虚实交互碰撞检测技术研究摘要：碰撞检测问题是3D游戏、机器人、动画仿真、城市规划、医学等领域不可 回避的问题之一。在AR （增强现实）环境中，目前普遍使用AABB、OOBB算法或是 混合使用的算法来解决碰撞问题，这些算法实时性较好，但是真实性无法满足AR环境， 尤其是自然人参与的AR交互过程要求。本文将利用实时性较好的AABB包围盒算法作 为粗糙碰撞检测，再引入人工免

2、疫系统来解决AR中的精确碰撞检测问题，以满足AR 环境中的实时性和真实性要求。本文要实现的系统利用摄像机采集真实手的视频并利用 通用AR平台（ARTOOLKITPLUS）产生出虚拟图像。手运动去与虚拟物体交互，并作出 一定的碰撞响应，使虚拟物体变形。在没有力反馈的情况下，实现一定的交互效果。关键词：增强现实、人工免疫系统，碰撞检测1文献综述（1）虚拟现实（VR），是由美国VPL公司创建人拉尼尔（Jaron Lanier）在20世 纪80年代初提出的。其具体内涵是：综合利用计算机图形系统和各种现实及控制等接口 设备，在计算机上生成的、可交互的三维环境中提供沉浸感觉的技术。和其他的计算机 系统相比

3、，vR系统可提供实时交互性操作、三维视觉空间和多通道（目前主要限于视觉 和听觉，但触觉和嗅觉方面的研究也正在不断取得进展）的人机界面。作为一种新型的 人机接口VR不仅使参与者沉浸于计算机所产生的虚拟世界，而且还提供用户与虚拟世界 之间的直接通讯手段。（2）增强现实（Augmented Reality，简称AR），是在虚拟现实的基础上发展起来 的新技术，也被称之为混合现实。是通过计算机系统提供的信息增加用户对现实世界感 知的技术，将虚拟的信息应用到真实世界，并将计算机生成。它通过电脑技术，将虚拟 的信息应用到真实世界，真实的环境和虚拟的物体实时地叠加到了同一个画面或空间同 时存在。增强现实提供了

4、在一般情况下，不同于人类可以感知的信息。它不仅展现了真 实世界的信息，而且将虚拟的信息同时显示出来，两种信息相互补充、叠加。在视觉化的 增强现实中，用户利用头盔显示器，把真实世界与电脑图形多重合成在一起，便可以看 到真实的世界围绕着它。增强现实借助计算机图形技术和可视化技术产生现实环境中不 存在的虚拟对象，并通过传感技术将虚拟对象准确“放置”在真实环境中，借助显示设备 将虚拟对象与真实环境融为一体，并呈现给使用者一个感官效果真实的新环境。因此增 强现实系统具有虚实结合、实时交互、三维注册的新特点。（3）包围盒篡法是进行碰撞干涉初步检测的重要方法之一。包围盒算法是一种 求解离散点集最优包围空间的

5、方法。基本思想是用体积稍大且特性简单的几何体（称为 包围盒）来近似地代替复杂的几何对象。碰撞检测技术中所用的包围盒有两个属性：简 单性和紧密性。简单性是指包围盒间进行相交测试时需要的计算量，这不但要求几何形 状简单容易计算，而且要求相交测试算法简单快速；紧密性要求包围盒尽可能的贴近被 包围的对象，这一属性直接关系到需要进行相交测试的包围盒的数目，紧密性越好，参 与相交测试的包围盒数目就越少。最常见的包围盒算法有AABB包围盒（Axis-aligned bounding box），包围球（Sphere）， 方向包围盒 OBB （Oriented bounding box）以及固 定方向凸包 FD

6、H （Fixed directions hulls 或 k-DOP）。（4）人工免疫系统就是借鉴免疫系统机制和理论免疫学而发展的自适应系统。 从工程领域角度及其运用领域和表现形式看，人工免疫系统是借鉴自然免疫系统机制以 及免疫学理论所建立的算法、模型以及软硬件系统的总称。它是继人工神经网络、模糊 系统和进化计算之后产生的智能计算技术，是生物科学与计算机科学的完美结合。免疫系统作为一种高度复杂的生物系统，免疫系统是自然界复杂性的代表。以下针 对本文所涉及的记忆学习，识别自我非我，多样性遗传，克隆选择机理作简要介绍。记忆学习。众所周知，要是我们曾经患过流感，之后的近一段时间里要是再感染同 样病毒就

7、不会患病。这种记忆作用是又记忆T细胞和记忆B细胞所承担的。这是因为在 一次免疫响应后，如果同类抗原再刺激时，在短时间内，免疫系统会产生比上一次较多 的抗体，同时与该抗原的亲和力也提高了。识别自我非我。这里的自我对应于机体自身的组织，非我对应于外来有害病原或者 体内病变组织。免疫识别是通过淋巴细胞上的康源识别受体与抗原的结合实现的，结合 的强度就称为亲和度。成熟的T细胞产生过程中首先要经历一个审查环节，只有那些不 能与自我（即机体本身组织）发生应答的T细胞才可以离开胸腺，执行免疫应答的任务， 这样可以防止免疫细胞对机体组织造成错误攻击。多样性遗传机理。免疫系统的抗体库具有多样性，能及时有效地消除

8、不同入侵抗原。 根据免疫学知识，免疫系统大约含有106种不同的蛋白质，但外部潜在的抗原或是待识别 的模式有10之多。要实现对数量级远远大于本身的抗原进行识别，需要有效的多样性 个体产生机制。该机制就是遗传变异机制，也即是多样性遗传机理。克隆选择机理。由于遗传和免疫细胞在增殖中的基因突变，形成了免疫细胞的多样 性，这些细胞的不断增殖形式形成无性繁殖系，即为克隆。有机体内免疫细胞的多样性 能达到这种程度，以至于每一种抗原侵入机体都能在机体内选择出识别和消灭相应抗原 的免疫细胞克隆，使之激活、分化和增殖，进行免疫应答以最终消除抗原，这就是克隆 选择。（5）随着计算机图形学、仿真技术和硬件技术的发展，

9、用高质量的计算机动画 来对现实世进行模拟与饵创造已成为可能.很多专家和学者都研究了在动画演示与模 拟中的一个根重要的问题一一碰撞检测（物体之间的干涉和碰撞），并在理论和实际方 面提出了许多有重要价值的研究结果.图形移动时的碰撞检测问题在计算机图形学、CAD /CAM、动态系统模拟、机器人学以及实时干涉布局等问题中都有着广泛的应用.碰撞 问题牵涉到碰撞检测和碰撞响应两部分。碰撞问题的具体应用很广泛，例如，虚拟环境 应用中的飞行员和宇航员的培养与训练、机器人的路径规划和学习、交互式动画系统、服装CAD中 衣物与人体躯干的配舍等.碰撞检测问题按运动物体所处的空间可分为二维平面碰撞检 测和三维空间碰撞

10、检测.由于平面物体的构造都可用多边形来表示，故其检测算法相对 要简单一些 而三维物体的掏造比较复杂，所以，其碰撞检测算法也比较困难.2选题背景及其意义AR不仅继承了VR的优点，同时又具有虚实结合的特点。与VR技术相比，AR技术把 计算机带人到用户的“世界”中。而不是把用户沉浸到计算机的世界中。它允许用户在 与实际对象交互的过程中，从计算机接收到关于这些对象的各种辅助信息。AR技术能够将计算机生成的虚拟物体合成到真实环境当中。在虚实交互的基础上 如何去实现人机交互是这一领域新的研究发展方向。碰撞检测技术能够确定虚拟场景当 中多个物体之间是否发生接触或者穿透现象并且返回相应的碰撞信息，为虚拟物体之

11、间 的交互提供了理论依据在AR环境中用3D重构的方法重构真实对象，再用VR的碰撞检测算法来实现碰撞检 测，由于重构带来的时差、误差、VR碰撞检测的精度与实时性等综合放大的误差是无法 接受的。因此在VR中普遍使用的包围盒算法精度和效果不能满足AR环境，尤其是有自然 人参与的AR交互过程。AR碰撞检测技术要求实时处理，对碰撞响应更要求有较快的实时渲染算法。由于 人工免疫算法具有分类精确，对原始数据维数与其它要求不敏感等特点，因此，本文打 算对碰撞检测中的快速高维数据处理的难题，创新地引入启发式的人工免疫算法AIS， 很好地解决7AR应用中虚拟与实际物体交互中的碰撞检测发生的检测问题。3研究内容(1

12、)碰撞检测算法总体流程设计本文所使用的碰撞算法总体流程如图1-1所示:图1-11、分割手部图像，识别手部姿态首先通过摄像头获取图像中RGB各分量，再经过变换将RGB模型转换为YCbCr模型。用高斯 模型对皮肤颜色建模，高斯模型为：M =馈，h c , h c)取一定数量的皮肤样本，用我们的高斯模型逼近皮肤颜色，训练好皮肤颜色的高斯模型后，对 于待判断的像素，可以得到其属于皮肤的概率如下：P(C ,C)= exp(-0.5(C -hc ,C -hc)(C -hc ,C -hc ) .!)b rr r b b r r b b这样，对于一幅待测图像中的，每一个像素，可以得到相应的属于皮肤的概率值，类

13、似于一个 灰度图。通过取适当的阈值，就可以将皮肤区域分割出来。通过手势分割之后，可能会得到多个属 于皮肤的区域，我们利用手势通常比脸部低这一生理事实，取较低区域为手势区域，然后采用基于 SAD的光流跟踪方法，对手势进行定位和跟踪。2、转换坐标系，使虚实物体处于同一坐标系系统有坐标系：全局坐标系W，摄像头坐标系C，人手坐标系H，虚拟坐标系O。坐标系的转 换过程如式(1.3)所示：O=(W+WT)*(C+CT)*H3、粗糙的碰撞检测算法首先利用AABB包围盒方法划分对象，对虚实物体进行粗糙的的碰撞检测。具体AABB包 围盒可用各个坐标轴上的最小、最大限定的区域表示，即V = Kx ,y ,z )|

14、l x h , l y H , l Z H 其中，l ,l ,l 分别表示 x,y,z 轴上的最 xx yy zzx y z小值，H x, H y , H z分别表示各轴的最大值。4、精确碰撞检测5、利用碰撞检测结果集，生成反应动画利用免疫算法得到的抗体集合RC，和距离集DC，调用事先生成的分类动画，模型库，渲染 响应动画，完成碰撞检测响应。(2)碰撞免疫算法设计本文所使用的免疫算法是基于文献所描述的基于克隆算法网络结构聚类算法。具体算法如下:图1-21、抗原识别，待求解问题的数据输入系统完成坐标转换，先把虚拟物体的圆柱包围体定点集合C分成三个部分T, B, R；姿态矢量为CA。调整后的矩阵为

15、CT。CT= （T，B，R）*CA。把手部分为P1，F1-F5；姿态角矢量为HA。2、初始化网络抗体A），激活记忆细胞产生初始抗体从CT（T，B，R）中利用最小距离选择T/B/R作为输入。3、选择克隆操作利用式（2）分别计算每个抗原%与所有网络抗体的亲和度。选择亲和度最高饨个抗体作为 抗体，按照亲和度越高，抗体克隆规模越大的原则进行克隆，克隆总数为Nci一 pril（2.1）4、高频变异操作利用式（2.2）通过减小个克隆抗体与抗原之间的距离，来增加其抗依抗原亲和度。C（W,P） = Y （Jr + Cc）（2.2）i =15、重新选择操作利用式（2.1）计算改良的抗体与抗原间的亲和度，并将亲和

16、度最高的e %个抗体作为网络 记忆细胞存储于M 中；6、克隆死亡操作对于每一个抗体，分别计算其与所有网络抗体间的亲和度。若与该抗体亲和度小于门限7 ,的 抗体个数小于。f，则将该抗体排除。将（抗体-抗体）亲和度小于 ,和（抗体-抗原）亲和度小 于刁抗体死亡。7、条件设定抗原数目设定为，迭代次数设定为在上述算法中，是网络压缩门限，它通过调整网络中抗体细胞的特异性水平，来控制网络的可塑性以及聚类精度，一般可以先取一个比较小的值（比如 1），然后不断增大其值，并分析获得的结果，以便最终确定一个合适的网络参数；是克隆 死亡率，通过调整的值，可以适当简化网络结构，从而达到网络压缩的目的；而是禁忌克隆门限

17、， 当与某抗体亲和度小于门限的抗体数小于时，将相应的抗体处于抑制状态，进而禁忌克隆运算， 可使网络产生免疫耐受性。4工作特色及其难点，拟采取的解决措施AR碰撞检测技术要求实时处理，对碰撞响应更要求有较快的实时渲染算法。由于人工 免疫算法具有分类精确，对原始数据维数与其它要求不敏感等特点,免疫算法设计是本文 的关键。5论文工作量及预期进度1、文献翻译与开题报告2012年12月5日一2012年12月23日2、软件开发与论文初稿3、软件与论文完善2012年12月24日一2013年04月15日 2013年04月16日一2013年05月22日4、 软件提交验收与答辩准备2013年05月23日一2013年

18、05月25日5、 毕业答辩2013年05月26日一2013年06月05日参考文献:焦李成，杜海峰，刘芳，公茂果.免疫优化计算、学习与识别.科学出版社. 2006陈明.增强现实虚实交互的若干关键问题的研究.：肖人彬，曹鹏彬，刘勇.工程免疫计算.科学出版社.2007刘韬.人工免疫系统及其数据挖掘应用研究.中国矿业大学出版社.2010.王志强洪嘉振杨辉碰撞检测问题研究综述上海交通大学建筑工程与力学学院19996郭天太王引童；虚拟现实技市与增强现实技市文章编号：1000-4998(2003)06-0007-037于复胜李少华冷怡山宋晓旭；碰撞检测算法研究 软件导刊2012年02期8陈雷;伊明;陈二雷;基于包围盒的碰撞检测算法研究J；电脑知识与技术(学术交流)；2007年14期9范昭炜，万华根，高曙明;基于图像的快速碰撞检测算法J;计算机辅助设计与图形学学报；2002年09 期10董向阳;张佐刚;基于层次包围盒的碰撞检测算法研究A;2006系统仿真技术及其应用学术交流 会