Dup-Pack:基于CRIS的FPGA装箱方法

设计了一种电路改写指令系统,并在CSPack算法的基础上提出了一种新的FPGA装箱方法Dup-Pack。Dup-Pack只需要改动指令流描述文件,就能实现对不同FPGA芯片的装箱。该方法采用将用户电路网表中的衍生逻辑单元替换为标准逻辑单元,再对标准逻辑单元进行装箱的方式,在实现高级逻辑功能装箱的情况下减少了样本电路总数。实验结果表明Dup-Pack的装箱结果相比较于T-VPack可减少11.26%的面积,在完成相同逻辑功能的情况下,较传统CSPack装箱速度提升2.77倍。     

迭代的图变换匹配算法

目的：图像的精确匹配在图像处理与识别中起着重要的作用。为了提高图像的匹配效果,本文提出了一种迭代的图变换匹配算法来实现误匹配关系的去除从而提高图像的匹配精度。方法：该算法首先利用传统的图变换匹配(GTM)算法从初始匹配关系集合中获得较为精确的匹配关系子集,然后,利用已经获得的正确匹配点集与初始匹配点集之间的几何关系对初始匹配进行修正。最后,利用GTM对修正后的匹配关系进一步优化,从而得到更多的精确匹配关系。结果：实验结果显示在不同的图像变换场景下,相比于传统GTM算法,该算法具有较高的查全率。结论：所提算法能够克服传统GTM算法所得正确匹配关系少的缺陷。     

求解矩形条带装箱问题的动态匹配启发式算法

矩形条带装箱问(RSPP)是指将一组矩形装入在一个宽度固定高度不限的矩形容器中,以期获得最小装箱高度.RSPP理论上属于NP难问题,在新闻组版、布料下料以及金属切割等工业领域中有着广泛的应用.为解决该问题,采用了一种混合算法,即将一种新的启发式算法--动态匹配算法--与遗传算法结合起来.混合算法中,动态匹配算法能根据4类启发式规则动态选择与装填区域相匹配的下一个待装矩形,同时将装箱后所需容器高度用遗传算法的进化策略进行优化.时2组标准测试问题的计算结果表明,相对于文献中的已有算法,提出的算法更加有效.     

多部图的匹配算法研究

本文给出了一个多部图的商匹配问题的定义,提出了求解多部图商匹配问题的一个算法。该算法使用圈与割集中偶图的交相结合的方法,利用求二部图的最大匹配算法,求解多部图的最大商匹配问题。     

计算机视觉中图匹配研究进展: 从二图匹配迈向多图匹配

图匹配试图求解二图或多图之间节点的对应关系.在图像图形领域,图匹配是一个历久弥新的基础性问题.从优化的角度来看,图匹配问题是一个组合优化问题,且在一般情形下具有非确定性多项式复杂程度(non-deter-ministic polynomial, NP)难度的性质.在过去数十年间,出现了大量求解二图匹配的近似算法,并在各个领域得到了较为广泛的应用.然而,受限于优化问题本身的理论困难和实际应用中数据质量的种种限制,各二图匹配算法在匹配精度上的性能日益趋近饱和.相比之下,由于引入了更多信息且往往更符合实际问题的设定,多图的协同匹配则逐渐成为了一个新兴且重要的研究方向.本文首先介绍了经典的二图匹配方法,随后着重介绍近年来多图匹配方法的最新进展和相关工作.最后,本文讨论了图匹配未来的发展.     

基于邻居信息聚合的子图同构匹配算法

图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题（CSP）模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。     

基于深度优先搜索的一般图匹配算法

对于一般图的匹配问题,Edmonds算法以Berge定理为基础,采用广度优先搜索增广路,图中可能存在“花”。遇到这种情况,要对它进行缩减“花”处理,再进行搜索。当找到增广路时,要将缩减图恢复,算法显得复杂。Gabow等算法使用先给固的顶点和边编号,并使用了不同数组和虚拟顶点,避免了处理花。算法的复杂性为O（n^3）,但增加了空间复杂性。本文提出的基于深度优先搜索算法,在搜索增广路时不会出现“花”的情况,算法相对简单;同时,算法时间效率为O（n＊degree（n））,degree（n）为顶顶点的平均度数。另外,当图的边动态增减时,使用该算法可以很快调整最大匹配,并且该算法空间复杂性在同一数量级也可以推广到广度优先搜索。     

采用二元CSP引擎求解RTL数据通路的可满足性

针对寄存器传输级(RTL)验证和测试过程中非常重要的数据通路可满足性求解问题,提出一种基于二元约束满足问题(CSP)的求解方法,包括数据通路提取、二元CSP建模和搜索求解3个步骤.数据通路提取通过对接口布尔变量和某些字变量赋值,为各个数据通路器件建立环境;二元CSP建模则根据该环境和各个数据通路器件的功能,将数据通路的可满足性问题转化为二元CSP描述;该二元CSP问题的描述被送入到二元CSP引擎,并采用冲突引导的回跳搜索策略进行求解,获得有解的例证或无解的判定.实验结果表明,即使在没有采取很多优化策略的条件下,该方法仍有较好的性能,并优于基于线性规划(LP)的求解方法.     

求解入库堆垛问题的改进约束满足算法

入库堆垛问题普遍存在于堆场作业管理中,是在货物数目和出库顺序已知的前提下,要求较长（重）的货物置于较短（轻）的货物下方,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的A形装箱问题,并建立了约束满足模型,设计了嵌入经典装箱启发式的约束满足求解算法。实验表明,该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。     

一种基于图分割的动态回溯算法

动态回溯算法在进行回溯时保留所有已赋值变量的值,从而可能与后面赋值的变量产生冲突,其在解决不具有明显子问题结构的约束满足问题时效率较低。为此,将图分割技术应用于动态回溯,通过图分割将变量分为若干集合,当发生回溯时,不保留全部变量的值,舍弃那些与引起冲突的变量在同一集合变量中的值。实验结果表明,该算法在求解没有明显子问题结构的约束满足问题时具有较高的效率。     

基于图匹配的分层布局算法

针对节点数目较大并且度数比较平均的无向图,根据分层扩展的思想,提出一种基于图匹配的分层布局算法（Graph Matching Hierarchy,GMH）。基于图匹配思想对大图进行递归化简,然后应用FR算法对最粗化图进行布局,最后利用质心布局算法对图进行扩展。实验结果表明,GMH算法能够提高可视化效率,改善布局效果,且分层布局的结果更易于理解。      

一个基于DFS编码的图形匹配算法

快速有效的图形查询是图形数据库成功应用的关键。文章利用图的词典顺序，用唯一的最小DFS（深度优先搜索）编码表示每个图。根据两个图同构当且仅当它们的最小DFS编码相同这一性质，将图形匹配转化为图的最小DFS编码的比较：在判断两个标记图形是否同构时，可以先求出图的最小DFS编码，再用有效的匹配算法进行比较。     

一种基于图的异常入侵检测新算法

根据主机系统异常入侵过程中Windows native API序列的瞬时高频性,提出一种基于图的异常入侵检测算法。该算法首先将每个Native API映射成为图中的一个点,并以其为起点的子序列作为该点的路径、Native API的前后调用关系为边;其次,对图中每个点记录各自的路径,在这些点的路径中找到若干个圈,圈定义为因对同一个Native API重复调用而在图中出现的回路;然后,对组成圈的所有边权值根据一定规则更新;最后利用图的边与其邻边权值差计算出异常指数,判断该序列是否异常。实验结果表明该算法在Windows平台下能实时有效地检测出异常入侵和病毒的Native API序列。     

一种基于图割的改进立体匹配算法

针对基于图割法的立体匹配算法耗时太长的问题,提出了一种基于简化网格图的立体匹配算法．算法 通过区域匹配算法得到每个像素的初始视差值,然后只保留完整网格图的部分可能的视差值,去除其余大部分的节 点和边缘,建立简化的网格图．该方法大大缩减了网格图的容量,缩短匹配所用时间,并且能够选用更大的视差范 围．实验证明,该算法能够得到比较理想的视差图,而且大大缩短立体匹配所用时间．     

基于自适应权值的图割立体匹配算法

针对传统自适应权重存在计算复杂度高和传统图割匹配精度低的问题,提出一种改进的基于自适应权值和图割的立体匹配算法。首先根据灰度相似性和空间相近性重新定义能量函数的数据项,利用图像的梯度信息作为能量函数的平滑项;然后运用图割理论和 α 扩展算法进行模型求解;最后对视差图运用左右一致性检验和加权中值滤波进行视差精化。算法采用了Middlebury 网站提供的四幅国际标准立体图像对进行测试,实验表明所提算法能够得到较准确的视差图。     

基于图匹配的人脸识别算法研究

文中介绍了一种通过提取特征点信息进行人脸识别的方法。在利用特征点定位的基础上,根据五官颜色检测特征点,然后构造特征点的具体数据及之间的关系数据,并与样本库中的人脸图片相比计算其最小匹配代价,依据最小匹配度完成识别。实践证明该方法对人脸正面图具有准确的识别率,且具有强抗干扰能力。最后展望了人脸识别技术的今后的研究方向。     

基于二分图完善匹配的布尔匹配算法

提出了一种改进的基于二分图完善匹配的布尔匹配算法。该算法通过把布尔变量之间的匹配问题转换为二分图的完善匹配问题,避免了原算法中因乘积项过多而导致计算时间过长的缺点。对MCNC标准测试电路的实验结果表明;与原算法相比,改进后的算法可以减少21％左右的计算时间。同时,文中提出了布尔变量强匹配的概念,它是对传统布尔匹配概念的引申。     

一种立体匹配的新算法

提出了一种基于遗传算法进行立体匹配,并获得高密度视差图的方法。遗传算法比其它优化方法具有更强的搜索能力,因此非常适用于求解全局优化问题。利用这一特点,该文将每一幅视差图看作是一个个体,将视差值编码形成染色体,这样每个个体中都有许多染色体。然后,引入匹配约束条件,形成目标函数,利用遗传算法搜索全局最优解。另外,还采用了由粗到精的层次策略来减少匹配模糊性和搜索时间。最后,分别用合成图像和真实图像对这种方法进行了验证。     

基于仿射参数估计的迭代点匹配算法

本文提出了一种新的迭代点匹配算法。算法建立点集间仿射映射关系,把匹配问题转化为函数优化问题,通过点集间匹配对应关系和仿射变换参数的反复迭代最终求出问题的解。文中提出了构造虚拟点对和最小方差两种仿射参数估计方法,并利用改进最近点原则求解点集匹配关系,且证明了算法的收敛性。本文算法较好地解决了由仿射带来的非刚性形变点集匹配问题,且有很好的抗噪声和点性能。实验证明了算法的有效性和鲁棒性。