A Fast Algorithm for Matching Remote Scene Images

An iterative algorithm to calculate mutual correlation using hierarchical key points and the search space mark principle is proposed. An effective algorithm is designed to improve the matching speed. By hi-erarchical key point algorithm and mutual correlation coefficients of the matching images, the important points can be iteratively calculated in the images hierarchically, and the correlation coefficient can be ob-tained with satisfactory precision. Massive spots in the parameter space which are impossible to match can be removed by the search space mark principle. Two approximate continuities in the correlation image matching process, the image gray level distribution continuity and the correlation coefficient value in the parameter space continuity, are considered in the method. The experiments show that the new algorithm can greatly enhance matching speed and achieve accurate matching results.

Fast M-fold matching pursuit algorithm for image approximation

A simple and effective greedy algorithm for image approximation is proposed. Based on the matching pursuit approach, it is characterized by a reduced computational complexity benefiting from two major modifications. First, it iteratively finds an approximation by selecting M atoms instead of one at a time. Second, the inner product computations are confined within only a fraction of dictionary atoms at each iteration. The modifications are implemented very efficiently due to the spatial incoherence of the dictionary. Experimental results show that compared with full search matching pursuit, the proposed algorithm achieves a speed-up gain of 14.4-36.7 times while maintaining the approximation quality.

Fast identification of mural pigments at Mogao Grottoes using a LIBS-based spectral matching algorithm

To quickly identify the mineral pigments in the Dunhuang murals,a spectral matching algorithm(SMA)based on four methods was combined with laser-induced breakdown spectroscopy(LIBS)for the first time.The optimal range of LIBS spectrum for mineral pigments was determined using the similarity value between two different types of samples of the same pigment.A mineral pigment LIBS database was established by comparing the spectral similarities of tablets and simulated samples,and this database was successfully used to identify unknown pigments on tablet,simulated,and real mural debris samples.The results show that the SMA method coupled with the LIBS technique has great potential for identifying mineral pigments.

Parallel Quick Search Algorithm for the Exact String Matching Problem Using OpenMP

String matching is seen as one of the essential problems in computer science. A variety of computer applications provide the string matching service for their end users. The remarkable boost in the number of data that is created and kept by modern computational devices influences researchers to obtain even more powerful methods for coping with this problem. In this research, the Quick Search string matching algorithm are adopted to be implemented under the multi-core environment using OpenMP directive which can be employed to reduce the overall execution time of the program. English text, Proteins and DNA data types are utilized to examine the effect of parallelization and implementation of Quick Search string matching algorithm on multi-core based environment. Experimental outcomes reveal that the overall performance of the mentioned string matching algorithm has been improved, and the improvement in the execution time which has been obtained is considerable enough to recommend the multi-core environment as the suitable platform for parallelizing the Quick Search string matching algorithm.

A Fast Pattern Matching Algorithm Using Changing Consecutive Characters

Pattern matching is a very important algorithm used in many applications such as search engine and DNA analysis. They are aiming to find a pattern in a text. This paper proposes a Pattern Matching Algorithm Using Changing Consecutive Characters (PMCCC) to make the searching pro- cess of the algorithm faster. PMCCC enhances the shift process that determines how the pattern moves in case of the occurrence of the mismatch between the pattern and the text. It enhances the Berry Ravindran (BR) shift function by using m consecutive characters where m is the pattern length. The formal basis and the algorithms are presented. The experimental results show that PMCCC made enhancements in searching process by reducing the number of comparisons and the number of attempts. Comparing the results of PMCCC with other related algorithms has shown significant enhancements in average number of comparisons and average number of attempts.

Four Sliding Windows Pattern Matching Algorithm (FSW)

This paper presents an efficient pattern matching algorithm (FSW). FSW improves the searching process for a pattern in a text. It scans the text with the help of four sliding windows. The windows are equal to the length of the pattern, allowing multiple alignments in the searching process. The text is divided into two parts;each part is scanned from both sides simultaneously using two sliding windows. The four windows slide in parallel in both parts of the text. The comparisons done between the text and the pattern are done from both of the pattern sides in parallel. The conducted experiments show that FSW achieves the best overall results in the number of attempts and the number of character comparisons compared to the pattern matching algorithms: Two Sliding Windows (TSW), Enhanced Two Sliding Windows algorithm (ETSW) and Berry-Ravindran algorithm (BR). The best time case is calculated and found to be??while the average case time complexity is??.

Enhancing ERS-A Algorithm for Pattern Matching (EERS-A)

Pattern matching is a very important topic in computer science. It has been used in various applications such as information retrieval, virus scanning, DNA sequence analysis, data mining, machine learning, network security and pattern recognition. This paper has presented a new pattern matching algorithm—Enhanced ERS-A, which is an improvement over ERS-S algorithm. In ERS-A, two sliding windows are used to scan the text from the left and the right simultaneously. The proposed algorithm also scans the text from the left and the right simultaneously as well as making comparisons with the pattern from both sides simultaneously. The comparisons done between the text and the pattern are done from both sides in parallel. The shift technique used in the Enhanced ERS-A is the four consecutive characters in the text immediately following the pattern window. The experimental results show that the Enhanced ERS-A has enhanced the process of pattern matching by reducing the number of comparisons performed.

Matching Pursuits方法综述

Matching Pursuits(匹配逼近)算法是在一个确定的函数集合中自适应地选择一些函数来表示一个信号的计算过程,函数集合中的每个函数都称为原子.多样化的信号特征决定了可以精确刻画信号特征的原子的类型,而重复迭代逼近的贪婪算法又确定了运算效率是MP算法的存在和发展的问题核心.本文围绕MP算法中原子库的生成,原子参数的搜索索引方式和迭代逼近过程中的快速算法等方面,阐述了MP算法发展变化过程.

一种基于FAsT-Match算法的多靶位定位方法

FAsT-Match(Fast Affine Template Matching)算法很好地实现了二维仿射变换情况下的模板在连续图像中的快速、精准定位。该算法对光照变化不敏感,具有较强的鲁棒性,但是对于有多个目标的图像,只能定位到一个近似全局最优解。因此,首先对FAsT-Match算法进行改进,将通过对得到的仿射变换矩阵进行模糊c均值聚类而得到的目标区域作为新的目标图像,然后采用原始的FAsT-Match算法进行定位,最后将新目标位置返回到原始目标图像中。该方法弥补了FAsT-Match算法只能定位单目标的不足,应用到无线激光模拟射击系统中能够降低硬件成本,快速、精确地定位靶位目标。实验结果表明,该方法是有效的,可以在满足定位多个目标的需求的基础上实现多靶位定位,具有一定的实用价值。

基于改进FAsT-Match算法的特定建筑区锁定跟踪

机载遥感视频背景复杂,且指定建筑目标面积小、分布离散,传统区域提取算法难以准确锁定并跟踪这类目标。提出了一种基于改进FAsT-Match算法的特定建筑区锁定跟踪方法。该方法首先以模板图为基准对目标图像进行直方图规定划,以适应不同的光照变化;然后构建仿射变换参数网络,并根据上一帧得到的最佳仿射变换参数限制当前帧图像的仿射变换参数范围,以提升匹配效率;最后将与仿射变换匹配的平行四边形图像数据经过逆仿射变换成矩形图像作为下一帧模板,从而解决旋转、尺度、形变等变化对目标跟踪准确性的影响。由实验分析可知,该算法AUC指标可达0.820,较NCC算法准确率提升40.5%,且跟踪效果好、效率高、对各种场景的适应性好,可在特定建筑区域准确、实时、高效地锁定跟踪。

基于Contig的单面基因组框架填充2-近似算法

随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。

结合FAST-SURF和改进k-d树最近邻查找的图像配准

针对两图像之间存在平移和旋转变化的图像匹配,提出了一种结合FAST-SURF和改进k-d树最近邻查找的图像配准算法。该算法首先用FAST(加速分割检测特征)检测器进行特征点提取,然后根据特征点周围邻域的信息生成SURF(快速鲁棒特征)描述子,采用一种改进的k-d树最近邻查找算法BBF(最优节点优先)寻找特征点的最近邻点及次近邻点,接着进行双向匹配得到初匹配点对,最后利用RANSAC(随机抽样一致性)算法消除误匹配点,findHomography函数寻找单应性变化矩阵,从而计算出图像间的相对平移量和旋转量。实验结果表明,该算法平移参数的最大误差为0.022个像素,旋转参数的最大误差为0.045度,优于传统的SURF图像匹配算法,实现了图像的快速、高精度配准。

一种二级分段PMF-FFT卫星信号捕获算法

针对在小点数快速傅里叶变换(Fast Fourier Transform,FFT)中,经典分段匹配滤波(Partial Matched Filtering,PMF)与FFT相结合的PMF-FFT卫星信号捕获算法存在增益损失,导致捕获灵敏度低、频率覆盖范围小和搜索速度慢的问题,提出了一种改进的二级分段PMF-FFT卫星信号捕获算法。截取部分FFT频率分量,缩短算法有效频率覆盖范围,以改善分段求和带来的包络增益衰减;采用在FFT频率分量中间位置追加搜索的方法,以改善FFT带来的扇贝损失;使用从粗略搜索到高精度搜索的策略,以减少搜索次数,提高搜索速度。仿真结果表明,相比经典PMF-FFT算法,在FFT点数不大于64点的情况下,改进算法能有效提高搜索增益和搜索速度,在8点FFT、125 Hz频率精度条件下,平均增益提升了22.19%,搜索次数减少了7.69%。

一种基于编辑距离的中文字符串近似匹配算法

字符串近似匹配是模式匹配领域中的一个重要研究方向。在中文字符串近似匹配中,基于字符操作的编辑距离不能准确衡量由复制、剪贴等操作导致的相似关系。基于此,在传统编辑距离的基础上引入了字符串的平移和复制操作,给出了一种在贪心算法基础上进行动态规划搜索的计算方法,能有效计算改进的编辑距离,在真实数据集上的实验结果和分析显示了对文本检索的有效性。

改进FAST和对立颜色特征的向量场一致性匹配

针对目前传统图像匹配算法在复杂环境下存在误匹配点对过多、稳健性较差等问题,本文提出一种基于改进FAST的特征点提取,结合对立颜色特征的图像匹配算法。首先,利用改进FAST算法提取的角点作为特征点,结合改进的Opponent SIFT算法对特征点进行描述;然后,使用基于字符定位算法对提取的特征点对进行粗匹配,降低整体匹配过程中特征点对误匹配的风险。最后,为了规避因RANSAC算法易陷入局部最优解而导致正确点对被误剔除的问题,运用向量场一致性替代RANSAC进行提纯,降低误匹配率。通过对比试验表明,改进算法匹配准确率均大于91%,且对差异变化具有较好的稳健性、适应性。

基于FAST和SURF的特征点快速匹配算法

为解决传统印刷电路板(PCB)图像配准过程中匹配耗时和错配率较高的问题,提出一种基于FAST-SURF的特征点匹配优化算法。利用FAST算法快速提取特征点,利用SURF的64维描述子进行准确的特征描述,在匹配阶段使用K-Means算法优化匹配结果,通过RANSAC算法进行一致性检查,消除误匹配点。实验结果表明,与传统的SURFRANSAC算法相比,该算法提高了匹配正确率,减少了匹配时间,实现了PCB图像特征的快速匹配。

基于多尺度FAST-9的图像快速匹配算法

FAST-9检测子不具备尺度不变性,为此,提出一种基于多尺度FAST-9的图像快速匹配算法。对图像建立高斯尺度空间,在各图层上应用FAST-9检测子分别提取特征点,在其周围建立圆形区域并分配主方向,同时建立方形区域构造SURF描述子,利用基于最近邻匹配方法进行匹配。实验结果表明,与SURF、SIFT算法相比,该算法具有较高的匹配速度。

An optimization model of parameter matching for aircraft catapult launch

To efficiently and fully utilize aircraft carrier resources,an optimization model is presented to deal with parameter matching between aircraft and carrier in the process of aircraft catapult launch.Based on carrier aircraft longitudinal dynamic equations and theorem of kinetic energy in catapult launch course,the work characteristics of different forces are learned and a theory model of parameter matching is deduced.In view of the uncertainty of the model parameters of the theory model and the low matching accuracy of the approximate model,an optimization model of parameter matching is introduced in line with the structure of theory model and the approximate model and is generated by the proposed immune genetic algorithm.Compared with the original genetic algorithm and immune algorithm,the proposed algorithm has better calculation accuracy and convergence.The calculation results show that the optimization model occupies certain application value of engineering estimation from the comparison with the relevant literature data and has higher precision than the approximate models.The validity of the proposed approach is verified with numerical case study on a carrier based aircraft.

改进FAST-SURF算法在卷烟包件识别定位中的应用

在智能卷烟包件码垛系统中抓取目标物体前需要快速而准确地对其进行识别与定位。而传统的SURF方法在进行特征点检测时时间较长。因此,提出一种基于改进的FAST-SURF算法的双目目标匹配定位方法。将FAST算法检测特征点的检测像素个数由16个降为12个,利用FLANN算法搜索待匹配特征点,缩短搜索匹配时间,然后用改进RANSAC算法剔除误匹配对,根据图像匹配的结果与标定得到的内外参以及匹配特征点近似均匀分布的规律,将所有特征点的三维坐标进行平均运算,得到近似形心坐标。实验中,确定了合适的阈值,证明了该方法在卷烟包件识别定位的速度和正确率上都有一定提高且具有更好的鲁棒性。

基于FAST算子与多特征匹配的图像伪造检测算法

当前图像伪造检测算法大多采用最近邻与次近邻比值法进行特征匹配来完成图像伪造检测,存在较多的错误检测以及漏检测现象,基于此提出了一种基于FAST算子与多特征匹配的图像伪造检测算法.首先,基于FAST算法与Bresenham方法,构造以像素点为中心的圆形区域,提取图像特征;然后,通过梯度直方图统计法判定特征点的主方向,以特征点为中心建立两级同心圆,并通过求取同心圆在指定方向上的梯度特征,生成特征向量和特征描述子;最后,提取特征点的HSI颜色分量,将HSI颜色分量以及特征点的特征向量作为双重特征,设计了双重特征匹配法则,实现特征匹配.引入Hough变换,对匹配特征点进行聚类,定位伪造内容.实验结果显示,与当前图像匹配算法相比,所提算法具有更高的检测正确度与鲁棒性能.