点模式匹配

摘要： Objective Fingerprint identification is an important and efficient technique used for biometric recognition.Fingerprints have become the most widely used biometric feature in recent years given their uniqueness and immutability.Fingerprint matching is a core research content of automatic fingerprint recognition systems.Matching algorithms directly influence the functions of a recognition system.Most point pattern-matching algorithms depend on the orientation field or directed graph of fingerprint images.That is,the matching of points is transformed into the matching of vectors,which are composed of two feature points.The fingerprint orientation field or the directed graph from the same finger frequently varies at different collection times because the input fingerprint images exhibit translation,rotation,and scale change.Consequently,the calculation of most point pattern-matching algorithms is extremely difficult.Point pattern-matching algorithms are also sensitive to the translation,rotation,and scale change of fingerprint images,particularly rotation.Certain parts of point pattern-matching algorithms cannot deal with fingerprint images with rotation.Therefore,a triangle-matching algorithm that is irrelevant to orientation is proposed and a detailed presentation of composing the congruent triangle is introduced in this study to improve the precision of calculation.Method A triangle exhibits stability,invariance,and uniqueness.The position structure is stable for any point and a certain triangle on a plane.The proposed triangle-matching algorithm is designed based on this theory.This algorithm efficiently avoids the orientation field or directed graph and significantly reduces calculation.The proposed algorithm,which is independent of orientation field or directed graph,also has preferable stability and robustness performance at different rotation angles.Fingerprint identification can be generally divided into three main periods:preprocessing of fingerprint images,feature extraction,and feature matching.On the basis of this framework,the proposed algorithm mainly contains three periods as follows.First,two benchmark triangles are constituted in identifying a fingerprint and a template fingerprint system.Second,the ordered arrays are composed of the distances from every feature point to three vertices of a benchmark triangle.Third,fingerprint image matching is decided based on the similarity degree of ordered arrays.Result The overall performance comparison experiments,such as complete fingerprint-matching process,equal error rate,false match rate,false acceptance rate,receiver operating curve,and match time,are completed using the FVC2004 fingerprint database,which is an international standard test library.Experimental results show that compared with other fingerprint-matching algorithms,the proposed algorithm successfully improves accuracy by 27.97％ to 33.81％,reduces matching time by 3％ to 5％,and decreases the average error in matching by approximately 86.63％.The proposed algorithm also outperforms the compared algorithms in terms of adaptive capacity,accuracy,and robustness for fingerprint images with noise,translation,rotation,and deformation.Conclusion The proposed algorithm is a global model-matching algorithm,which is unconstrained by the fingerprint orientation field and the locations of fingerprint images.Calculation is significandy reduced compared with other point pattern fingerprint-matching algorithms.The process and implementation of the proposed algorithm are simply based on elementary mathematics.The experimental results indicate that the proposed algorithm demonstrates preferable adaptive performance for fingerprint images with noise,translation,rotation,and deformation.Furthermore,the proposed algorithm exhibits good robustness and can handle different types of images.%目的 指纹匹配是自动指纹识别系统研究的核心内容之一,匹配算法的好坏直接影响识别系统的效能.目前,大多数点模式匹配算法都依赖于指纹方向场的求取,由于输入的指纹图像存在平移、旋转和尺度变化,因此同一个手指在不同时间获得的指纹图像的方向场是不同的,这不仅增加了计算量,也影响了指纹识别的精度.针对上述问题,提出了无方向的三角形匹配算法.方法 提出的三角形匹配算法是以平面中任意点与一个确定的三角形之间的位置结构稳定性为理论基础的.首先,分别在待识指纹图像和模板指纹图像中确定基准三角形;其次,将各个特征点与基准三角形三个顶点的距离组成有序三数组;最后,利用数组的相等程度对指纹相似度进行匹配判断.结果 采用国际标准测试库FVC2004进行综合性能比对实验,实验结果表明,与其他几种匹配算法相比,本文方法在识别精度上提高了27.97％～33.81％,在比对时间上降低了3％～5％,在不同旋转角度下误匹配率平均降低了约86.63％,对噪声、平移、旋转和形变有足够的适应能力,具有较高的容错能力和鲁棒性.结论 无方向的三角形匹配算法是一种全局模式的算法,该算法不受指纹图像方向及其位置的影响,实现过程简单,识别精度高,平均比对时间少,适用于处理不同类型的图像数据.

摘要： 点模式匹配是目标识别、图像配准与匹配、姿态估计等计算机视觉与模式识别应用方向的基础问题之一.提出了一种新的利用点特征进行匹配的算法,该算法根据点集的分布与点位置信息,构建了点的特征属性图,通过极坐标变换得到对数极坐标的特征图,并利用几何不变矩方法对特征图进行描述.由特征描述向量的比较,获得粗匹配结果,然后通过几何约束迭代的方法获取最终的点集匹配结果.本文贡献如下:一,构建了一种点的极坐标变换特征,并运用不变矩进行描述,使所提特征具有旋转与平移的不变性;二,提出了利用点特征与整体点集几何约束结合的匹配算法,能有效克服出格点与噪声带来的不利影响.最终实验说明了算法的有效性和鲁棒性.

摘要： 点模式匹配涉及诸多研究应用领域，是一个重要而基础的问题，对点模式匹配问题研究的技术方法也多种多样。利用特征点的空间信息，研究基于Laplace谱的点模式匹配方法，首先对特征点构建的图进行Laplace矩阵构建，通过对L aplace矩阵进行的奇异值分解获取匹配矩阵，实现图像匹配。实验研究表明，该匹配算法能够减轻计算负担，缓解传统的基于图像局部灰度信息匹配速度慢、效果不理想的问题，具有很好的匹配效果。%Point pattern matching is a basic and important problem involving many applied research fields . The methods which focus on the problem of point pattern matching remain various .This paper uses the spatial information of feature points , and studies the point pattern match method based on Laplace spectrum .First ,it constructs the Laplace matrix of the figure constructed by feature points ,then ,does the singular value decomposition of Laplace matrix to obtain the matching matrix ,and achieves the image matching .The experiment results show , the matching method not only can reduce the computational burden ,but alleviate the problems of slow speed and the ineffective image matching based on local gray level information ,w hich has good matching effect .

摘要： Aiming to improve the point pattern matching accuracy with graphical models, an improved point pattern matching algorithm is proposed using dynamic generating graphical model. First, mixed Gaussian distribution is applied in similarity measure of dynamic generating graphical model to improve the multi-feature ability of model,which make the matching results more robust to noise. Second, a dummy point is introduced in the target point set and the similarity measure including the dummy point is provided. A point in the template would match the dummy point when the similarity measure of a template point with a target point is less than that of the template point and the dummy point, which can reduce the mismatching rate caused by outliers. Experimental results with simulated and real images show that the proposed algorithm is more robust to noise and outlier, and compared with the traditional methods, matching accuracy is improved.%　　为了提高概率图模型点模式匹配的精度，本文提出了改进的动态图模型点模式匹配算法。首先，在动态图模型点模式匹配的相似性度量中应用混合高斯分布，以提高模型利用多特征的能力，使匹配方法对噪声更加稳健。其次，在目标点集中引入了虚拟的哑点并给出了包含哑点的相似性度量。当模板中的点和哑点相匹配的相似性度量更大时模板点将和哑点匹配，以减少由异常点所导致的误配。实验结果表明所提出的匹配方法对噪声和异常点更加稳健，匹配的精度也优于传统方法。

摘要： In order to improve the robustness of spectral correspondence algorithm for noise and outlier,a structural descriptor based on spectral graph theory is proposed,and the matching objective function combined with geometric consistency is given as well as its solving algorithm.Firstly,a structural descriptor is proposed by utilizing the statistic of graph spectra and spectral gap,consequently the attribute representation of feature point with fixed length is obtained.Secondly,an objective function is defined by combining geometric consistency represented by neighborhood relationship,and then the matching problem is formulated as an optimization problem with one-to-one correspondence constraints.Finally,the solution to the defined objective function is given by using probabilistic relaxation.Comparative experiments applied to both synthetic data and real-world images validate that our method can achieve higher matching accuracy.%为了提高谱匹配算法对噪声和出格点的鲁棒性,提出一种基于谱图理论的结构描述子,并在此基础上结合几何相容性给出了匹配目标函数的定义及相应求解算法.首先给出一种利用特征谱与谱隙序列的统计量构造的结构描述子,以获得定长的特征点属性表示；然后结合邻近关系表示的几何相容性定义了求解匹配问题的目标函数,将匹配问题转化为一对一约束下的优化问题；最后介绍了利用概率松弛对匹配目标函数的求解方法.在模拟数据与真实图像上的比较实验结果均表明该算法具有相对较高的准确性.

摘要： 针对复杂背景下多运动目标的跟踪方法不能有效解决遮挡和高速运动等问题，提出一种Kalman预测与点模式匹配相结合的多目标跟踪方法。利用Kalman滤波预测目标在下一帧图像中的位置，以此位置为中心确定目标搜索区域，然后以点模式匹配进行搜索区域和目标模板进行匹配，有效地解决目标的旋转和轻微的遮挡问题。为了提高匹配速度和实时性，在点模式匹配中利用Kalman滤波对目标旋转角度的预测与修正；同时为了保证跟踪的鲁棒性、连续性及准确性，对目标模板的更新采用置信度二级判决门限。实验表明该方法具有较好的实时性，并能够有效地解决遮挡等问题。%Since the muti⁃object tracking method can not effectively overcome the target covering and high⁃speed movement in complex background,a new multi⁃object tracking algorithm based on point matching algorithm and Kalman filtering predic⁃tion is proposed. The possible position of a moving object in the next frame image is predicted by Kalman filtering. The position is regarded as the search center to determine the object seach region. The matching of the object template and the candidate re⁃gions is carried out with point matching algorithm to solve the problems of rotation and slight covering of the target. In order to improve the matching speed and real⁃time performance,the rotation angle of the target is predicted and corrected in the process of point matching by using Kalman filtering. The secondary judgment threshold of confidence is adopted for object template up⁃date to ensure the tracking robustness,continuity,stability and accuracy. The experimental results show that this approach has better real⁃time performance and can solve the covering problem effectively.

摘要： Graphical models have good performance in point pattern matching. However, the method has high computation complexity and attends to be affected by outliers in separators. In order to match the point pattern accurately and efficiently, this paper proposes a coarse-to-fine matching algorithm. A coarse matching process is completed using normal cross-correlation algorithm with windows including feature points, which reduces the number of outliers and improves the matching efficiency. A novel graphical model is proposed. The model can make use of positional information of feature points and gray information of the windows including the feature points. A stepwise matching method is applied to the point pairs matched by normal cross-correlation method and the fine matching result is obtained. The matching experiment results show the proposed method can reduce significantly the running time and improve the matching accuracy.%点模式匹配的概率图模型具有很好的匹配精度，但是计算复杂度较高，当隔离子中包含异常点（outlier）时匹配精度会受到较大的影响。为了提高匹配的速度和精度，提出了一种由粗到精的图模型点模式匹配算法。利用包含特征点的窗口，用标准化互相关方法对特征点进行粗匹配，以减少异常点的数量，提高后续匹配方法的速度和精度。提出了一种新的点模式匹配的概率图模型，这种图模型能综合利用特征点的位置信息和包含特征点的邻域的灰度信息。利用提出的概率图匹配方法对粗匹配所得到的点对进行分段匹配，得到精确的匹配结果。对光学图像和遥感图像的匹配实验显示该方法能显著减少点模式匹配时间，提高匹配的精度。

摘要： One of the important pre-condition of identification fusion based on remote sensing images is target association, which is to determine if the information from two or more images are related to the same target A novel and robust point pattern matching method was presented for group target association in low-resolution remote sensing images. A new point set based invariant feature,Relative Shape Context (RSC), was proposed. We used the test statistic of relative shape context descriptor's matching scores as the foundation of mathematics model of group target association. For resolving the model,we firstly constructed the new compatibility measurement and used it to initialize the association probability matrix. Then the association probability matrix can be updated by relaxation labeling. The one-to-one matching can be achieved by dual-normalization of rows and columns in the end. Experiments on both synthetic point-sets and on real world data show that the group association algorithm is effective and robust.%目标关联是遥感影像融合处理的重要步骤,本质上是目标配对问题.针对低分辨率遥感影像中阵群目标的特点,提出了一种基于点模式匹配的阵群目标关联算法.首先提出一种新的基于点集的不变特征——相对形状上下文特征,然后建立了以相对形状上下文特征的统计检验匹配测度为基础的阵群目标关联数学模型.为了求解该模型,在构造新的相容性度量函数来初始化关联概率矩阵后,利用松弛标记法通过迭代逐步更新关联概率矩阵,同时通过行列双向正则化最终得到满足一对一约束的最优关联匹配结果.通过仿真和实际数据实验验证了新算法的有效性和鲁棒性.

摘要： A watermarking algorithm for vector map based on point pattern matching is presented. The algorithm embeds the gray image to feature vertex of the vector map, while embedding, the invisibility of the watermarking is guaranteed by controlling the tolerance of error. The point pattern matching algorithm is used in watermarking extraction process, the key vertices of the vector map being detected and the vector map with watermark are matched, through this way the registration function between them are obtained. At last, by comparing it with original vector map, the watermarking information image embedded can be derived from calculation. Experiments prove that the algorithm has good resistance against the attacks such as translation, rotation, scaling, etc. , and has relatively high security.%提出一种基于点模式匹配的矢量地图水印算法.该算法将灰度图像嵌入到矢量地图的特征顶点中,嵌入时通过控制误差容限,保证水印的不可见性.水印的提取过程采用点模式匹配算法,通过匹配被检测的矢量地图与含水印的矢量地图的关键顶点得到它们之间的配准函数,最后与原矢量地图比较可以计算得到嵌入的水印信息图像.实验证明该算法对平移、旋转、缩放等攻击都能起到很好地抵抗,具有较高的安全性.

摘要： 针对谱匹配方法对噪声和出格点的鲁棒性较差的问题,提出了一种基于拟Laplacian谱和点对拓扑特征的点模式匹配算法.首先,用赋权图的最小生成树构造无符号Laplacian矩阵,通过对矩阵谱分解得到的特征值和特征向量表示点的特征,进而计算点的初始匹配概率；其次,利用点对拓扑特征的相似性测度来定义点对间的局部相容性,然后借助概率松弛的方法更新由拟Laplacian谱得到的匹配概率,得出匹配结果.对比实验结果表明,该方法在处理存在噪声和出格点的点集匹配上具有较高的鲁棒性.

摘要： 针对大部分点模式匹配算法对噪声和出格点稳健性较差的问题,对提出的基于马氏距离的点模式匹配方法进行了理论分析,然后针对马氏距离及加权图转换匹配方法的不足,将马氏距离融入到加权图转换匹配算法中,提出基于马氏距离加权图转换的点模式匹配算法.该算法利用中值和角度距离约束不断剔除出格点,获得了更加精确的匹配结果.实验对比结果表明该方法的可行性和鲁棒性.

摘要： 本文提出了一种新的点模式匹配算法。算法能对不同大小点集间的匹配和非刚性的变换关系同时进行估计。算法用空域滤波的方法对点集间的匹配概率进行计算,通过软指派(soft assign)方法来获得一致的匹配结果。为提高算法鲁棒性,文章在迭代框架下使用上述方法,并用高斯径向基函数模型来对点集间形变进行估计。理沦分析和实验结果充分证明了算法的有效性和鲁棒性,并统一了目前数种点模式匹配算法。

摘要： 谱方法是点模式匹配中一种重要的方法,但该方法对于点模式中噪声与出格点较为敏感,为克服了传统谱匹配方法存在问题,提出了一种运用谱方法和松弛标记的非刚性点模式匹配算法。该方法首先提取点模式中点的KL特征获取点与点的匹配概率,然后运用松弛标记法得到点集间明确的匹配关系；同时,为保证算法的鲁棒性,给松弛标记法定义一个匹配的目标函数,在函数的优化框架下迭代的计算匹配的最优解。本文主要从三方面对传统谱方法进行了改进:首先运用基于KL的匹配概率计算方法提高了原谱图方法抗噪方面的性能,进而在松弛标记方法框架中运用谱方法进行匹配,使算法对出格点具有更好的鲁棒性,最后融合的运用了点的谱图特征和空间分布特征,使算法在较大形变情况下仍能实现有效匹配。文章实验验证了算法的有效性。

摘要： 对指纹匹配算法的研究是自动指纹识别中一个非常重要的研究内容.针对指纹的点模式匹配方法中如何确定两枚指纹的比对基准参考点问题,基于小范围搜索与三角形方法相结合的方法,提出了一种新的不依赖图像中心区域的指纹匹配算法。该算法在保留了点模式匹配方法优点的同时有效地提高了匹配速度,且具有旋转平移不变性及对部分特征点丢失或错误时的抗干扰能力.实验结果表明了所提出算法的有效性。

摘要： 本发明公开了一种基于FPGA平台的压缩流量模式匹配引擎及模式匹配方法，设计高效的基于FPGA平台的实现方案，实现加速匹配压缩流量的效果。一种基于FPGA平台的压缩流量模式匹配引擎包含输入队列、输出队列、环存储区和结果记录四个数据存储功能模块，以及匹配模块和数据搬运和读写模块。本发明的技术方案不仅能够提升引擎处理压缩流量时的吞吐率，还有效降低了处理时延。

摘要： 本发明实施例提供了一种模式匹配的方法和模式匹配装置。该方法应用于模式匹配装置中，该模式匹配装置包括定时管理器和状态机引擎，该方法包括：该状态机引擎在接收到事件源发送的至少两个事件中的第一事件时，向该定时管理器注册定时器，该至少两个事件中的每个事件携带各自的发生时刻；该定时管理器通过该定时器从该第一事件的发生时刻开始计时，直到预设的时间阈值；该状态机引擎根据接收到的发生时刻在预设的时间段内的事件的模式，确定是否与预设模式匹配，该预设的时间段为该第一事件的发生时刻与该预设的时间阈值之间的时刻范围。本发明能够根据事件的发生时刻进行模式匹配，提高了模式匹配的准确率。

摘要： 本发明公开了一种用于安全字符串模式匹配的数据结构构造及匹配方法，包括数据结构S2PAStree的构造方法和基于该数据结构进行字符串模式匹配的方法，该数据结构包括一组关键词，使得应用该数据结构的程序能够快速响应支持隐私保护的字符串模式匹配查询需求，减少服务提供商与授权用户的内存资源开销。基于该构造方法方法，针对云计算以及数据外包的情景，服务提供商能够在保护原始数据、查询条件以及查询结果的隐私安全的前提下，快速响应授权客户端对于安全字符串模式匹配查询的需求。基于该匹配方法，相比于普通的字符串模式匹配查询方法，具有更快的查询速度，更少的通信开销，提升了服务提供商的查询处理效率和服务质量。

摘要： 提供了能够生成针对高效执行模式匹配判定而言最优的事件模式匹配树的模式匹配装置。该模式匹配装置具有：事件模式表保持部，保持包括部分事件模式的事件模式，所述部分事件模式包括第一属性名称和属性值；第一匹配率测量部，基于包括属性的事件和所述事件模式，测量与第一属性名称相对应的匹配率，其中所述属性包括第二属性名称和属性值；以及事件模式匹配树生成部，基于所述事件模式以及匹配率，生成事件模式匹配树，其中将包括相应匹配率较低的第一属性名称在内的属性值匹配判定实例排列在相对较高级别。

摘要： 本发明公开了一种模式匹配方法和模式匹配系统。变异图像生成装置生成相对于正规化图像具有不同姿态、面部位置和尺寸的多幅变异图像。特征提取装置从多幅变异图像中提取出频率特征。鉴别空间投影装置将频率特征投影在通过线性鉴别分析获得的具有高鉴别能力的鉴别空间上。参照个人比较装置执行参照个人比较以提取出高度鉴别性的特征。利用特征提取装置和鉴别空间投影装置提取出匹配图像的鉴别特征。分数计算装置使用从注册图像获得的鉴别轴和从匹配图像获得的鉴别特征来输出匹配分数。匹配判决装置通过将匹配分数与阈值相比较来确定该个人是否是相同个人。

摘要： 本发明实施例提供了一种模式匹配方法、装置和用于模式匹配的装置。其中的方法具体包括：对待匹配的模式串进行分词，得到所述模式串对应的第一分词集合；对所述第一分词集合中的各分词进行编码，得到编码后的模式串；分配所述编码后的模式串对应的位向量表，所述位向量表中的位用于表示相应分词在所述模式串中是否出现；根据所述位向量表，基于位并行算法对所述模式串与待匹配的文本串进行匹配。本发明实施例可以提高B表的利用率，以及提高模式匹配的效率。

摘要： 本发明公开了一种基于FPGA平台的压缩流量模式匹配引擎及模式匹配方法，设计高效的基于FPGA平台的实现方案，实现加速匹配压缩流量的效果。一种基于FPGA平台的压缩流量模式匹配引擎包含输入队列、输出队列、环存储区和结果记录四个数据存储功能模块，以及匹配模块和数据搬运和读写模块。本发明的技术方案不仅能够提升引擎处理压缩流量时的吞吐率，还有效降低了处理时延。

摘要： 本发明实施例提供了一种模式匹配的方法和模式匹配装置。该方法应用于模式匹配装置中，该模式匹配装置包括定时管理器和状态机引擎，该方法包括：该状态机引擎在接收到事件源发送的至少两个事件中的第一事件时，向该定时管理器注册定时器，该至少两个事件中的每个事件携带各自的发生时刻；该定时管理器通过该定时器从该第一事件的发生时刻开始计时，直到预设的时间阈值；该状态机引擎根据接收到的发生时刻在预设的时间段内的事件的模式，确定是否与预设模式匹配，该预设的时间段为该第一事件的发生时刻与该预设的时间阈值之间的时刻范围。本发明能够根据事件的发生时刻进行模式匹配，提高了模式匹配的准确率。

摘要： 本发明公开了一种用于安全字符串模式匹配的数据结构构造及匹配方法，包括数据结构S2PAStree的构造方法和基于该数据结构进行字符串模式匹配的方法，该数据结构包括一组关键词，使得应用该数据结构的程序能够快速响应支持隐私保护的字符串模式匹配查询需求，减少服务提供商与授权用户的内存资源开销。基于该构造方法方法，针对云计算以及数据外包的情景，服务提供商能够在保护原始数据、查询条件以及查询结果的隐私安全的前提下，快速响应授权客户端对于安全字符串模式匹配查询的需求。基于该匹配方法，相比于普通的字符串模式匹配查询方法，具有更快的查询速度，更少的通信开销，提升了服务提供商的查询处理效率和服务质量。

摘要： 本发明公开了一种基于模式匹配和实体匹配的数据融合方法，通过利用给定的初始连接的记录对进行实体匹配，然后再利用当前实体匹配的结果进行模式匹配，然后再根据模式匹配的结果进行实体匹配，以此类推，每一轮匹配均以上一轮的匹配结果作为输入数据，在前一轮的成功匹配的记录对的基础上再次进行匹配，可以使我们能够修正前一轮中可能的错误匹配或没有找到记录组，不断地去修正模式匹配的结果。直到模式和实体匹配的结果都趋于稳定。该方法可以提高数据融合的准确率，提升数据价值。本发明还公开了一种基于模式匹配和实体匹配的数据融合装置、系统及一种可读存储介质，具有上述有益效果。