微软专利分享如何改进计算机视觉图像的特征点识别
以向外螺旋序列从其中心朝向其边界遍历感兴趣区域中的像素来识别特征点
（映维网Nweon 2023年02月09日）特征检测和/或特征匹配是众多计算机视觉应用的重要组成。在检测特征的过程中，通常需要在图像或图像的一部分（感兴趣区域）中识别像素的特征分数。
像素的特征分数是其局部邻域中像素值的函数。它通常与像素的颜色有关。在一种情况下，特征分数是采用各种颜色的一个或多个数值，例如灰度颜色值、RGB（红、绿、蓝）颜色值。在另一种情况下，特征分数是从采用各种颜色的数值得出。
例如，可以首先处理原始图像（具有像素的原始值集）并将其转换为另一图像（具有新的像素特征分数集）。然后，可以进一步处理处理后的图像以识别特征，并且可以将识别的特征进一步细化到亚像素精度和/或用于提取它们的特征描述符。
传统上，暴力搜索方法通常遍历感兴趣区域中从一个边缘到另一个边缘的所有像素（例如从左到右和从上到下），从而检测局部特征。通常，感兴趣区域通常以特征点所在的特征候选为中心。
在名为“Spiral feature search”的专利申请中，微软介绍了一种改进的方法：通过以向外螺旋序列从其中心朝向其边界遍历感兴趣区域中的像素来识别特征点。
螺旋搜索从图像中感兴趣区域的中心开始，而这显著增加了在遍历整个区域之前找到特征的可能性。通常，特征出现的概率集中可以用正态分布来表征。值得注意的是，螺旋搜索的预期时间显著提高，而对于传统的暴力方法，无论特征出现的概率分布如何都需要相同的时间。
图2示出了特征探测器200。特征探测器200配置为以螺旋序列从感兴趣区域的中心向外到边缘遍历感兴趣区域中的像素。
在一个实施例中，特征查找器200包括候选特征查找器202、序列表204、序列生成器206和特征检查器208。候选特征查找器202被配置为识别特征点候选。在另一实施例中，候选特征发现器202同时配置为定义图像中的感兴趣区域。
例如，候选特征发现器202确定感兴趣区域的位置和尺寸，例如50×50或10×10。通常，感兴趣区域在每个宽度或高度维度中包括奇数个像素，所以感兴趣区域的中心点与中心像素重叠。
序列表204存储感兴趣区域中的多个像素的序列。序列生成器206配置为生成全螺旋序列以遍历感兴趣区域中的所有像素。特征检查器208配置为遍历感兴趣区域中的每个像素，检查其邻域中的特征分数，并确定其是否是局部特征（也称为局部特征点、特征点或特征）。对于所识别的特征点，其位置可以进一步细化到亚像素精度和/或其特征描述符可以被提取。
在一个实施例中，序列表204存储感兴趣区域中按其规范排序的多个像素点。在另一实施例中，采用欧几里德范数，即x2+y2，其中x和y分别对应于像素的x和y坐标）。在另一实施例中，采用最大范数。
图3A示出了在正方形晶格或x-y平面300中具有多个像素的感兴趣区域。每个黑点代表感兴趣区域中的一个像素。例如，（0，0）处的像素与感兴趣区域的中心点重叠（又称为中心像素）。像素旁边的每个数字表示其平方范数。对于其他示例，（0，1）处的像素具有1（＝02+12），（1，1）的像素具有2（＝12+12）、（2，1）上的像素具有5（＝22+12）等等。这样，在x-y平面300中计算每个像素的平方范数。
值得注意的是，x-y平面300的每个象限中的像素关于轴和对角线（例如，线y＝0、x＝0、y＝x和/或y＝−x）对称。在下文中，轴向像素或点是位于坐标轴上的像素点，例如x轴（即，线y＝0）或y轴（即线x＝0）；对角线像素或对角线点是位于对角线上的像素点，例如直线y=x或y=−x；内部像素或点是不位于坐标轴或对角线上的像素点。
参考图3B，对于参考pizza slice 310中的每个轴向像素，可以在剩余的三个象限中识别对称的其他三个轴向像素，并且它们的范数与参考披萨切片320中的轴向像素的范数相同。例如，参考pizza slice 310中的（3，0）处的轴向像素在剩余三个象限中的（0，3）、（−3，0，和（0，−3）处具有三个对称的轴向像素。由于（3，0）处的轴像素的平方范数是9，所以（0，3）、（−3，0，和（0，−3）处的其他对称轴像素的均方范数同样是9。
类似地，参考图3C，对于pizza slice 310中的每个对角像素，可以在剩余的三个象限中识别对称的其他三个对角像素，并且它们的范数与320中的对角像素的范数相同。例如，参考pizza slice 310中（2，2）处的对角像素与其余三个象限中（−2，2、（−2、−2）、（2，−2）处对称的其他三个对角像素。由于（2，2）处对角像素的平方范数为8，所以（−2，2，（−2），（−1，−2）和（2，−2，−3）处对称的其他对角像素的均方范数同样为8。
在一个实施例中，在感兴趣区域中按其规范排序的像素被存储在查找表中。图4A示出了完整查找表400A的示例，所述完整查找表包含在感兴趣区域中按其规范排序的像素序列。
如图所示，平方范数为0的（0，0）中心像素列为第一个像素，而平方范数为1的（1，0）、（0，1）、（−1，1）和（0，−1）的轴向像素则列为下一组像素；平方范数为2的（1，1）、（-1，1），（-1，-1）和（1，-1）的对角像素列为下一组像素，依此类推。
值得注意的是，完整查找表的大小与特征提取应用的最大感兴趣区域的大小成比例。例如，如果最大感兴趣区域是50×50以提取特征，则完整查找表只需要记录50×50边界内的像素。
作为另一个例子，最大感兴趣区域是100×100以提取特征，完整的查找表需要记录100×100边界内的像素。
一组对称像素具有相同的范数，并且它们在完整查找表400A中彼此相邻地列出。例如，平方范数为1、（1，0）、（0，1）、（−1，1）和（0，−1）的对称轴点彼此相邻。平方范数为2、（1，1）、（−1，2）、（-1，1）和（1，−1）的对称对角点彼此相邻，这是冗余的，占用了更多的存储空间。
在一个实施例中，只有pizza slice的像素记录在缩减查找表中。然后，计算系统110配置为计算剩余pizza slice中的其他对称像素。图4B示出了基于其规范仅记录参考pizza slice中的像素的简化查找表400B的示例。
如图所示，范数为0的位于（0，0）的中心像素列为第一像素，范数为1的位于（1，0）的轴向像素列作为第二像素，范数平方为2的位于（2，1）的对角线像素列第三像素，依此类推。渐进地，对于相同大小的感兴趣区域，缩减查找表400B比完整查找表400A节省了八倍的存储空间。
在一个实施例中，简化查找表同时配置为记录像素的位置。图4C示出了简化查找表400C的示例，所述简化查找表不仅如图4B所示记录参考pizza slice中的像素，而且记录每个像素是位于y＝x还是y＝0线上。
如图所示，表400C包括两个附加列“y=x”和“y=0”，每个列对应于布尔值。如果点位于直线y=x上，则其对应的布尔值为True；否则，其对应的布尔值为False。类似地，如果点位于直线y=0上，则其对应的布尔值为True；否则，其对应的布尔值为False。
值得注意的是，当“y=x”和“y=0”都为True时，像素点是中心点；当“y=x”为假且“y=0”为True时，像素点为轴点；当“y=x”为真且“y=0”为False时，像素点为对角点；当“y=x”和“y=0”都为False时，像素点是内部点。这样，像素的位置可以由两个布尔值表示。布尔值可以预先计算并存储在简化查找表400C中。
因此，计算系统110不需要每次遍历时检查像素的位置。计算系统110可以简单地检索存储在表400C中的像素的布尔值，并基于检索到的像素位置执行对称变换。
一旦生成了查找表400A、400B或400C，计算系统110配置为基于记录在查找表400B、400C中的像素序列遍历感兴趣区域中的每个像素，并确定其是否是局部特征。图5A-5E示出了在螺旋序列中遍历感兴趣区域中的每个像素的示例，其可以从完整或缩减的查找表（例如，查找表400A、400B或400C）获得。
在一个实施例中，计算系统110配置为简单地遵循完整查找表400A中的每个像素坐标（例如，（x，y）坐标），并遍历感兴趣区域中的每一个像素。在另一实施例中，对于缩减查找表400B或400C中的每个像素，计算系统110被配置为通过对称变换来识别其他对称像素，并以逆时针、顺时针、任何其他预定义序列或随机序列遍历它们。
图5A示出了首先遍历感兴趣区域500中的（0，0）处的中心像素。当遍历（0，0）处的中心像素时，计算系统110确定它是否是局部特征。例如，将像素的特征分数与其中心正方形中所示的八个相邻像素的特征得分进行比较，以确定其特征分数是否小于或大于其他特征分数。如果一个像素的特征分数小于或大于其相邻像素的特征得分，则它是作为特征点的局部最小值或最大值。
对于缩小查找表400B或400C中的偏心像素，计算系统110首先确定它是参考pizza slice中的轴向点、对角线点还是内部点。对于参考pizza slice的轴向或对角像素，通过对称变换在感兴趣区域中识别其他三个对称像素。对于参考pizza slice的内部点，通过对称变换在剩余的七个pizza slice中识别的其他七个对称像素。
图5B示出了在（1，0）、（0，−1）、（−1，1）和（0，1）处范数为1的下一组轴向点被顺时针遍历。对于缩小查找表400B或400C中的（1，0）处的轴向像素，计算系统110配置为对称地识别其他三个轴向像素。
图5C示出了在（1，1）、（−1，2）、（-1，-1）和（1，−1）处平方范数为2的下一组对角像素被顺时针遍历。对于缩小查找表400B或400C中的（1，1）处的对角像素，计算系统110配置为对称地识别其他三个对角像素。
图5D示出了在（2，0）、（0，2）、（−2，2）和（0，−2）处平方范数为4的下一组轴向像素被顺时针遍历。对于缩小查找表400B或400C中的（2，0）处的轴向像素，计算系统110配置为对称地识别其他三个轴向像素。
图5E示出了在（2，1）、（2，−1），（1，−2），（−1，−3）、（−2，−4）、（-2，−5）处的平方范数为5的一组内部像素被顺时针遍历。对于简化查找表400B或400C中的（2，1）处的内部像素，计算系统110配置为对称地识别其他七个内部像素。
重复所述过程，直到在感兴趣区域中检测到第一个局部特征。图5F示出了遍历感兴趣区域中平方范数小于23的像素的螺旋序列的示例。
如图所示，序列从（0，0）处的中心像素开始，到（2，4）处的像素结束，这看起来像一个向外的螺旋。如果在遍历（2，4）处的最后一个像素之前发现特征，则不需要额外的计算来遍历感兴趣区域500的其余部分。
微软指出，以这种螺旋序列遍历感兴趣区域中的像素是有利的，因为感兴趣区域通常包含围绕其中心的特征点。特征出现的概率集中通常可以用正态分布来表征。螺旋搜索从感兴趣区域的中心开始，这显著增加了在遍历整个感兴趣区域之前找到特征的可能性。
然而，无论特征出现的概率分布如何，暴力搜索的预期时间都是相同的。螺旋搜索的预期时间因此比传统的强力搜索显著提高。
图9示出了以螺旋序列遍历感兴趣区域中的像素以识别局部特征的示例方法900的流程图。
方法900包括识别图像中具有多个像素的感兴趣区域，每个像素对应于特征分数（动作910）。方法900还包括以预定义的顺序遍历感兴趣区域中的每个像素，以基于其邻域中的特征分数来确定其是否是局部特征（动作920）。
在一个实施例中，预定义序列是从感兴趣区域的中心向外到边缘的向外螺旋序列（动作922）。方法900同时包括，响应于基于某些像素的特征分数确定某些像素是一个或多个特征，将它们的位置细化到亚像素精度和/或在特征点处提取一个或更多个特征描述符（动作930）。
名为“Spiral feature search”的微软专利申请最初在2021年7月提交，并在日前由美国专利商标局公布。
