基于局部极值快速搜索的特征点提取方法

摘要

本发明提出一种基于局部极值快速搜索的特征点提取方法，通过改变局部极值的搜索方法，在保证算法鲁棒性的同时，避免局部极值的重复搜索过程，减少计算量，可以使得平均每个元素的搜索次数小于1.5次，并且与窗口大小无关，从而提高特征点的提取速度，特别是在大窗口中局部极值的提取过程更具有优势。本发明对特征提取、匹配的结果没有影响，可提高多种特征点提取算法的实时性。

主权项

一种基于局部极值快速搜索的特征点提取方法，其特征在于包括如下步骤：A、1维2n+1窗口局部最大值搜索，n为正整数：A1、利用差分得到当前行中局部最大值，作为2n+1窗口的候选最大值；A2、取下个候选最大值元素；A3、判断窗口中心元素是否为非最大值，若是，重复步骤A2，否则进入步骤A4；A4、历遍后n个元素中的非递增的元素；A5、判断是否大于后n个元素中未历遍元素，若否，标记窗口中心元素为非最大值，并返回步骤A2，若是，则标记当前被比较元素为非最大值，并执行步骤A6；A6、历遍前n个元素中的非递增的元素；A7、判断是否大于前n个元素中未历遍元素，若否，标记窗口中心元素为非最大值，并返回步骤A2，若是，则标记窗口中心元素为2n+1窗口内最大值；A8、判断是否历遍当前行所有候选最大值，若否，返回步骤A2；若是，执行步骤A9；A9、保存输出结果；B、2维(2n+1)×(2n+1) 窗口局部最大值搜索：B1、将每行(2n+1)窗口内最大值作为2维候选最大值；B2、取下个2维候选最大值元素；B3、判断窗口中心元素是否为非最大值，若是，重复步骤B2，否则进入步骤B4；B4、与窗口内下一个候选最大值比较；B5、判断是否大于被比较元素，若否，标记窗口中心元素为非最大值，并返回步骤B2，若是，则标记当前被比较元素为非最大值，并执行步骤B6；B6、判断是否历遍窗口内1维最大值，若否，返回步骤B4；若是，执行步骤B7；B7、历遍窗口其他元素,判断是否大于所有其他元素，若否，标记窗口中心元素和被比较过的元素为非最大值，并返回步骤B2；若是，执行步骤B8；B8、标记窗口中心元素为(2n+1)×(2n+1) 窗口内最大值；B9、判断是否历遍2维候选最大值；若否，返回步骤B2；若是，执行步骤B10；B10、保存输出结果。