提出一种利用图像序列的平稳性和相关性检验的天气场景分类方法.首先,给出天气场景的定义和分类标准;其次,该方法通过分段逆序平稳性检验,提出图像均值子序列逆序总数数学期望和方差的计算方法,将天气场景分为平稳性天气场景和非平稳性天气场景；最后,提出自相关函数的分类检验方法,建立对待分类场景图像序列的激变描述,完成对其所属静态或动态场景的分类.该方法为非参数检验方法,推断分类标准时无需估计总体分布的参数,并能在线学习所得的分类标准.实验结果表明,该方法可准确完成对天气场景的动态分类.

基于像素的背景建模方法速度较快但不能很好地描述背景运动，光流能准确描述物体运动但计算量大，难以满足实时的要求.提出一种结合基于像素的背景建模方法速度快以及光流描述物体运动准确优点的背景建模和目标检测方法.具体来说，为静止背景建立传统基于像素的灰度背景模型，为运动背景建立光流背景模型，通过2种背景模型的有效结合快速准确地实现目标检测.实验结果表明，提出的方法建模速度与基于像素背景建模方法相当，同时，又有光流准确描述背景运动的优点，综合性能超越上述2种方法.

共生矩阵是描述纹理特征的一种常用方法.首先提出一种新的特征提取算法——多分辨共生矩阵.多分辨共生矩阵是通过同时在非下采样小波变换的逼近子带和细节子带上提取共生矩阵来实现的,能够有机整合传统小波的多分辨特性和频谱信息,以及空域灰度共生矩阵的纹理结构信息.其次,分析了多分辨共生矩阵、灰度共生矩阵以及小波能量特征的物理意义,并从相关性出发提出了新的特征选择方法,有效地降低了特征维数.对标准纹理库的分类实验结果表明:多分辨共生特征对纹理具有更好的描述能力,其分类正确率超过小波能量特征、空域灰度共生特征:二者融合以及灰度梯度共生特征的结果;所提出的特征选择方法在降低特征维数的同时,能够保持分类正确率.

针对高斯混合模型用于图像分割时仅利用了像素的灰度信息,而忽视空间位置信息,导致在噪声区域和边界处有误分割现象,提出一种自适应空间邻域信息高斯混合模型的图像分割法.该方法定义了一个能够有力抑制噪声点、很好保留边界特性的自适应空间邻域信息函数.在此基础上,设计了每个像素由某个类生成的邻域信息加权概率,并证明了该加权概率满足归一性和空间连续性2个准则;最后,利用EM优化算法给出模型参数E步和M步迭代求解公式.通过人工合成图像与真实图像的实验表明,该方法具有满意的分割效果.

有参混合模型需要假设模型为某种已知的参数模型,而实际数据往往很难假设出这种参数模型的分布.为此,提出一种二类切比雪夫正交多项式的非参数图像混合模型分割方法.首先,设计出一种基于二类切比雪夫正交多项式的图像非参数混合模型,每一个模型的平滑参数根据误差方法和最小的准则进行计算.然后,利用随机期望最大(SEM)算法求解正交多项式系数和每一个模型的权重.此方法不需要对模型作任何假设,可以有效克服有参混合模型与实际数据分布不一致的问题.实验表明,该方法比高斯混合模型分割效率更高,并比其他非参数正交多项式混合模型有更好的分割效果.

针对运动估计的各种实现方案难以同时满足实时计算性能和灵活性需求的问题,提出了一种支持多种标准的运动估计协处理器.该协处理器采用6流出超长指令字结构,可执行多种运动估计算法.协处理器中包含一个可二维数据重用的处理单元阵列、一个SAD加法树和一个多模编码耗费比较器.处理单元阵列和加法树可满足运动估计巨大的计算复杂度,而耗费比较器则用来支持各编码标准中不同的分块模式.一个快速全搜索算法在该协处理器上执行,用来验证其正确性和进行性能分析.实验结果显示,对1 920×1 080的视频序列执行运动估计,搜索窗口为32×32时,帧频可达到60 fps.

目标在复杂环境下运动,特征会受到光照、摄像机角度等因素影响,并且目标可能会被自身其他部分或者场景物体遮挡,为此,提出一种多窗口概念的视频目标跟踪算法,基本思想就是将目标用多个不同的窗口表示,每一个窗口对应一个跟踪器.这些窗口之间可以存在重叠,也可以包含被跟踪目标上下文信息,如在人脸跟踪中,有些跟踪窗口可以包含颈部信息、上衣颜色信息.然后利用这些窗口之间的位置关系以及在后继跟踪过程中的相似度来估计目标的真实位置.通过实验可以看出,提出的多窗口均值移动跟踪算法可以提高系统在遮挡、光照变化等复杂条件下的跟踪性能.

乐观并发控制允许操作并发执行,由此将产生对象引用发生时刻与对象引用使用时刻的几何模型的不一致,结果将导致命名机制的失效而不能保证对象引用的正确性.将引用对象分为可替代与不可替代2种类型,对于可替代对象引用,通过构建对象引用发生时刻的临时几何模型保证该类对象引用的正确性;对于不可替代对象引用,通过恢复对象引用发生时刻的几何模型,然后完成引用该类对象的操作,最后Redo模型恢复过程中被Undo的并发操作来保证该类对象引用的正确性.在原型系统中对提出的方法进行了验证.

定性空间推理是人工智能领域中非常重要的研究内容.空间信息包含拓扑关系、大小关系、形状、距离等很多方面.以往多侧重于单一方面的研究,如何将孤立的各方面信息进行统一表示和推理是当前定性空间推理中的一个重要问题.提出利用结合操作来融合不同空间信息表示的新方法.利用结合操作,可以由原先完备互斥关系集合得到新关系,同时利用原有的复合表自动生成新关系的粗复合表.基于结合操作,给出2个理论模型：结合拓扑关系与大小关系模型、结合拓扑关系与远近关系模型.并提出了邻域划分图的概念,说明了邻域划分图与概念邻域图的关系.利用邻域划分图回答了Galton提出的问题:“为什么LOS(视觉光线演算)的概念邻域图不同于标准的空间或时间关系的概念邻域图,这些关系的复合表中关系总是来自于概念邻域图”.

联盟形成是多agent系统中的一个关键问题,找到最优的联盟结构是NP-完全的.Sandholm和Larson等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能完全解决的问题.在任务分配等实际问题中,不同联盟存在同势同值的特征,或同势的2个联盟的值相差不大.研究了最优势结构生成问题,分析了基于势结构的分组思想,并提出一个以势结构为搜索单位的新的任一时间联盟结构生成算法.算法在最小搜索之后给出进一步降低限界至2的搜索,也讨论了限界从2降到1的过程中由底向上的补充搜索.从搜索的势结构数和联盟结构数以及达到的限界上明显优于由Sandholm和Dang等人给出的算法,是基于势结构的联盟生成问题的一个重要进展.

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2\+m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland (DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393\+m).

在基于扩展规则的知识编译算法的基础上提出了2种启发式策略:MCN策略和MO策略.MCN策略和MO策略利用子句集的信息分别选择相应子句和变量,减少扩展规则的使用次数,进而降低知识编译后目标子句集的规模.在此基础上,设计并实现了MCN_KCER,MO_KCER和MCN_MO_KCER算法.实验结果表明:2种启发式策略都可以大幅度减小编译后的子句集规模,同时使用它们的效果更为明显,经过编译后得到的子句集规模是原算法的1/3～1/39,从而大幅度提高之后的在线推理阶段的效率.

移动数据的研究逐渐成为了数据挖掘研究领域的热点.已有的移动对象离群轨迹检测算法部分参数敏感且需人工调节,导致算法不稳定,可扩展性不理想;同时,已有算法完全根据自己主观定义的度量来探测离群轨迹,没有充分利用已知轨迹反映的信息.因此,提出一种基于半监督技术的移动对象离群轨迹检测算法,利用半监督技术,根据已知的信息确定敏感参数,克服算法不稳定的缺点,并从整体与局部相结合的角度设计新的度量,以发现有意义的移动对象离群轨迹.实验表明该算法可以发现更有意义的移动对象离群轨迹并减少参数的人工调节.

大规模并行计算机互连网络的设计对并行应用程序的执行效率有重要影响,k-元n-立方体是广泛使用的拓扑结构．局部通信是并行应用的主要通信模式之一,研究局部通信模式下互连网络的性能有重要意义,已有分析模型缺乏对这方面的充分研究．引入局部通信率和局部通信区域半径组成的二元参数,刻画k-元n-立方体网络节点间通信的空间局部性．利用排队论对网络建模,研究延迟和吞吐量随负载的变化规律,比较局部性参数对网络性能的影响强度,针对长、短消息情况分别进行详细讨论．最后采用改进的网络模拟器,验证分析模型具有较高的准确性．为具有局部通信性质的大规模并行应用,提供了一种有效预测延迟和吞吐量的方法.

在基于特权服务操作系统的虚拟机架构下客户操作系统需要借助特权服务操作系统来访问真实硬件,目前虚拟机调度算法的优化主要是侧重于I/O密集型虚拟机的研究,而忽视了CPU密集型虚拟机,更忽视了特权服务操作系统的I/O处理能力对虚拟机整体性能的影响.针对这些问题,提出了一种基于Credit算法的自适应调整虚拟机权重参数的优化调度方法,将特权服务操作系统的I/O处理能力作为虚拟机参数调整的一个重要参数,同时兼顾I/O密集型虚拟机和CPU密集型虚拟机对资源的需求.实验结果表明该方法能够及时根据当前的I/O请求数量和特权服务操作系统的处理能力合理调整虚拟机的权重参数,从而大大提高了客户操作系统CPU处理性能和硬件设备的访问性能.

近年来,专用指令集处理器(application specific instruction set processor, ASIP)在嵌入式系统中得到了越来越广泛的应用.这些ASIP提供了面向某个领域定制硬件计算加速器的功能.通过利用加速器提供的扩展指令,可以大幅提升ASIP面向领域的处理能力.然而,这些计算加速器只能加速那些在编译时加入了扩展指令的应用程序.对于在编译时没有加入扩展指令的应用而言,得不到任何性能提升.利用软件动态二进制翻译来解决这一问题,即将计算加速器虚拟化.与传统的静态编译方法所不同的是,以动态虚拟化方式利用计算加速器面临许多新的问题.针对这些问题,提出了一系列解决方法,并用实验加以验证.

符号执行能够对软件的路径分支信息进行收集和形式化表示,然后通过路径可达性推理得到软件行为同用户输入、网络输入等外部执行环境间的依赖关系.这些依赖关系已被广泛地应用到漏洞发掘、代码复用、协议分析等领域.该逆向分析技术也可被黑客用于软件破解、篡改和盗版等,对软件知识产权的保护带来了新的威胁.提出了一种新的基于路径模糊的软件保护方法以抵抗基于符号执行的逆向分析:利用条件异常代码替换条件跳转指令来隐藏程序的路径分支信息,使用不透明谓词技术引入伪造的路径分支来弥补程序在统计属性上的差异,并对路径模糊技术的强度、弹性和开销进行了分析.实验结果表明路径模糊技术能保护各类路径分支条件,有效减少路径分支信息的泄露,抵抗基于符号执行的逆向分析.

针对可信服务计算需要对系统行为和可信特征进行建模和分析的要求，结合具有描述多个维度可信特征能力的Q代数对Pi演算进行扩展，提出一种可用于对系统行为及可信特征进行建模的进程代数，称之为QPi.QPi将可信特征附加于进程动作，在描述系统行为的同时体现出其可信特征.进一步引入互相似距离的概念以考察2个进程在多大程度上是能够互相模拟的，并研究了QPi与之相关的若干性质.具体的实例描述说明了该代数方法的有效性.

为了降低恶意评价对信任模型造成的影响,提出了一种适用于开放分布式网络环境下的基于信任领域和评价可信度量的信任模型(trust model based on the trust area and evaluation credibility, TMEC),并给出了模型流程及相关定义.TMEC模型中将节点的信誉值区分为节点的全局信誉值和反馈信誉值,并基于信任领域进行模型的构建;提出了基于节点评分行为相似性的共谋团体识别算法;提出了基于评价支持度和评价一致性因子确定节点反馈权重的方法,从而使所构建的信任模型更加可信和可靠.仿真实验表明,该模型能够有效地检测和抵制夸大、诋毁和共谋等恶意评价行为,具有良好的抗攻击性.

针对视频点播系统,研究其软件老化模式.对系统资源和视频点播服务器的实时参数,采用Mann-Kendall方法来检测老化趋势以判断系统是否存在软件老化现象,并采用Sen的斜率估计方法来估计老化衰退速率;提出了基于径向基网络的软件老化预测模型,对老化趋势进行预测,并采用主成分分析方法来减少径向基网络的复杂度以提高效率.实验结果表明:视频点播系统中存在软件老化现象;基于径向基网络的软件老化预测模型预测效果优于时间序列模型.基于提出方法以及对视频点播系统的老化分析,可为进一步研究相应的软件再生策略提供理论依据.

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2\+m)减少到O(1.618\+m)，将DNA计算机在试管内可求解的最大匹配问题的规模从60(2\+{60}≈10\+{18})提高到86(1.618\+{86}≈10\+{18}).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.

量子线路模型是使用最广泛的量子计算模型,它对于量子算法的构造和量子计算机的物理实现提供了一个基本框架.利用测量演算和分布式量子计算的基本思想,提出了测量量子线路模型(measurement quantum circuits model).测量量子线路主要考虑测量结果对酉运算的影响,测量结果和酉运算之间的关系以及测量基量子线路的在纯态和混合态上的作用.讨论了2个基元运算的并运算,以及连接运算,它们都是封闭的. 基于此,定义测量量子线路的基本运算元,并证明任何一个测量量子线路是一个量子运算 并举例得以说明.

随着XML技术的不断应用和推广,XML结构聚类技术在XML管理与挖掘中扮演着重要角色.针对目前XML结构聚类算法聚类不准确、效率低、对数据输入次序敏感的不足,提出簇核心的概念,并指出在动态环境下,对簇核心加以正确维护可以支持增量式聚类.在此基础上设计了一套有效的XML结构聚类算法COXClustering,该算法涵盖静态聚类和增量式聚类,静态聚类提取子树作为特征合理反映XML结构之间的相似性,并利用簇核心快速分类的特点提高聚类效率,利用簇核心正交的特点降低对数据输入次序的敏感性;增量式聚类根据当前增加的XML文档动态调整簇核心,从而自适应地指导增量式聚类.理论分析和实验表明该算法静态聚类效率高、聚类质量好、能够有效屏蔽输入次序的敏感性,增量式聚类将聚类速度大幅度提升,聚类质量接近静态聚类质量.

目前B+树仍是在商业数据库中应用最广泛的基本索引结构,为在现有数据库平台上对时态数据进行有效操作,有必要研究基于B+树的时态索引技术.研究了一种以B+树为基本存储结构、基于结构摘要的时态索引方法CMap-tree. 首先,引入基于内存的结构摘要,通过存储结点必要的结构摘要信息,有效地降低了时态操作过程中对无效结点的访问;其次,提出了时态矩阵的概念,并以时态矩阵为参考详细分析了各时态关系对应的结果集;然后,在结构摘要的基础上,详细讨论了CMap-tree的时态插入、查询和更新算法.最后,通过仿真实验,对CMap-tree的空间利用率、查询效率和更新效率等基本性能与现有时态索引方法进行了比较和分析.实验结果表明,CMap-tree具有明显优势.