局部特征量算出装置和方法以及对应点搜索装置和方法

摘要

本发明提供一种局部特征量算出装置和方法以及对应点搜索装置和方法。局部特征量算出装置(1)具备：特征点附近区域抽取部(11)，其从图像(TP)抽取特征点(p)和设置于特征点(p)附近的附近区域(NR)；方向强度计算部(12)，其分别算出附近区域(NR)内的各像素的边缘梯度方向(θ)和边缘强度(m)；主轴方向检测部(13)，其检测附近区域(NR)的主轴方向(v)；以及局部特征量算出部，其关于各像素，对旋转过的投票单元图案(CP’)的投票单元中的关注像素所属的投票单元，按照修正过的边缘梯度方向来进行该像素的边缘强度的投票，从而求出特征点(p)的局部特征量(d)。由此，能够高速地算出局部特征量。

说明书

技术领域

本发明涉及用于算出图像的局部特征量的局部特征量算出装置和局部 特征量算出方法、以及使用了局部特征量算出装置的对应点搜索装置和使 用了局部特征量算出方法的对应点搜索方法。

背景技术

以往，在图像处理领域中，多会使用对两个图像之间的对应点进行搜 索的对应点搜索处理。图22是表示两个图像之间的对应点的图。这样，通 过对多个图像之间的对应点进行搜索，能够从图像数据库中检索与输入图 像对应的图像、或者使以不同的视点拍摄到的被摄体的多个图像相关联地 还原该被摄体的三维形状。

为了搜索两个图像之间的对应点，可以使用局部特征量。局部特征量 是指使关注像素的周边区域的纹理图案(texture pattern)带有特征的量， 以D维的向量来表示。周边的纹理图案相似的像素具有类似的局部特征量。 因此，例如通过对第一图像和第二图像各自的像素求出局部特征量，并对 这些特征量进行比较，能够判断第一图像的该像素与第二图像的该像素是 否为对应的像素(对应点)。

图23是用于说明使用了局部特征量的图像检索的图。能够通过使用了 局部特征量的对应点搜索来如以下那样进行图像检索(例如，参照非专利 文献1)。图像检索的目的在于，从图像数据库中检索与输入图像对应的图 像。首先，对图像数据库中登记的多个图像分别抽取各自的特征点，求出 各特征点的局部特征量。当成为检索对象的图像(输入图像)被输入后， 也从该输入图像抽取特征点，对各特征点求出局部特征量。然后，关注输 入图像的多个特征点中的一个特征点，从图像数据库中检索与该关注特征 点所具有的局部特征量最接近的局部特征量。然后，对找出的局部特征量 所属的图像投一票。对输入图像中的全部特征点反复进行该处理，将得到 最多投票的图像作为检索结果。

另外，通过使用了局部特征量的对应点搜索，如以下那样能够由以不 同的视点拍摄到的多个图像还原三维形状(例如，参照非专利文献2)。首 先，从由多个摄像位置拍摄摄像对象而得到多个图像中选择两个图像，求 出该两个图像之间的对应点。对多个图像的全部组合进行该对应点搜索。 接着，将对应点的信息作为线索，通过捆绑调整(bundle adjustment，集 束调整)来求出各图像的摄像位置参数以及摄像对象的形状参数。

作为求出局部特征量的代表方法，已知SIFT(Scale Invariant Feature Transform：尺度不变特征转换)(例如参照非专利文献3和专利文献1)、 SURF(Speeded Up Robust Features：快速鲁棒特征)(例如参照非专利文 献4)。在SIFT和SURF中，即使图像旋转或者图像的尺度不同，也能够 计算这些变化中不变(不受影响)的局部特征量。因而，在搜索两个图像 之间的对应点时，即使图像旋转或者图像的尺度不同，也能够适当地求出 图像之间的对应点。

以下，以SIFT为例说明局部特征量的算出方法。图24是基于SIFT 的局部特征量算出处理的流程图。另外，图25～27是用于说明基于SIFT 的局部特征量算出处理的图。在局部特征量算出处理中，首先，如图25 的(a)所示，从图像TP中抽取特征点p以及以该特征点为中心设定的附 近区域NR(步骤S71)。在存在多个特征点p的情况下，对各个特征点p 设定附近区域NR。在该特征点p以及附近区域NR的抽取处理中，通过 DoG滤波器，与特征点p的位置一起输出图像的尺度信息。通过根据该尺 度信息来切出以特征点p为中心的附近区域NR，实现尺度不变性。

接着，求出主轴的方向(步骤S72)。在主轴的计算处理中，对针对各 特征点p设定的各个附近区域NR应用以下处理。首先，如图25的(c)、 (d)所示，针对附近区域NR内的各像素计算x方向和y方向的微分值， 求出边缘强度m(x，y)以及边缘梯度(斜率)方向θ(x，y)。在此， 通过以特征点p为中心的高斯窗G(x，y，σ)(参照图25的(b))对边 缘强度m(x，y)进行加权，得到加权边缘强度mhat(x，y)。由此，视 为越是附近区域NR中的中央的像素，则越具有重要的信息。

接着，生成边缘梯度方向直方图。具体而言，将各像素的边缘梯度方 向量化为36种，对符合的方向进行加权边缘强度mhat(x，y)投票。这 样，通过对附近区域NR中的所有像素进行边缘梯度方向的量化以及加权 边缘强度的投票，从而得到如图25的(e)所示的边缘梯度方向直方图。 接着，从该梯度方向直方图中检测出最大值，使用具有最大值的方向的左 右的值来拟合二次函数，将与其极大点对应的方向作为主轴的方向v。

接着，对附近区域内的纹理图案进行旋转修正(步骤S73)。在该旋转 修正中，使附近区域NR内的纹理图案旋转，以使得通过步骤S72求出的 主轴方向v与基准方向RD一致。图26示出基准方向为水平右方向的示例。 通过对周边像素进行线性插值来求出使附近区域NR旋转后的各像素的 值。对旋转后的纹理图案设定新的附近区域NR’。

接着，算出局部特征量(步骤S74)。为了算出局部特征量，首先，对 于对旋转修正后的纹理图案新设定的附近区域NR’的各像素，再次计算x 方向和y方向的微分值，如图27的(a)所示，求出边缘梯度方向和边缘 强度。在图27中，箭头的方向表示边缘梯度方向，箭头的长度表示边缘强 度。

接着，将各像素的边缘梯度方向量化为8种，并且，如图27的(b) 所示，将附近区域分割为4×4，定义16个投票单元VC。在图27的(b) 的示例中，由2×2像素形成一个投票单元VC。并且，针对各投票单元 VC求出八个方向的梯度方向直方图。通过以上运算，得到16×8＝128维 的特征向量。将该特征向量的长度标准化为1后，得到局部特征量。

如上所述，能够得到具有旋转不变性和尺度不变性的局部特征量。以 上为基于SIFT的局部特征量算出处理，SURF也基于同样的方法。

专利文献1：美国专利第6711293号公报

非专利文献1：“Improving bag-of-features for large scale image search”，International Journal of computer vision，2010

非专利文献2：“Unsupervised 3D object recognition and reconstruction in unordered datasets，”International Conference on 3-D Digital Imaging and Modeling(3DIM 2005)

非专利文献3：“Distinctive image features from scale-inva riant keypoints，”International Journal of Computer Vision，60，2(2004)

非专利文献4：“Herbert Bay，Andreas Ess，Tinne Tuytelaars，Luc Van Gool，“SURF：Speeded Up Robust Features”，Computer Vision and Image Understanding(CVIU)，Vo1.110，No.3，pp.346-359，2008

发明内容

SIFT存在局部特征量算出处理的执行速度慢的问题。另外，SURF是 改善了SIFT的计算速度的方法，但尽管如此也还是得不到如便携终端那 样使用低规格的硬件进行工作的程度的性能。认为执行速度这样慢是存在 以下两个原因。

第一个原因在于，在基于SIFT、SURF的局部特征量算出处理中，为 了求出主轴方向v，对附近区域NR的各像素进行微分计算，基于求出的 主轴方向v对纹理图案进行旋转修正，为了针对旋转修正后的新的附近区 域NR’的各像素算出局部特征量，会再次进行微分计算。即，虽然用于 求出主轴的微分计算与用于求出局部特征量的微分计算是类似的处理，但 这两个微分计算分别独立地进行。

第二个原因在于，用于对纹理图案进行旋转修正的计算量庞大。在对 纹理图案的旋转修正的计算过程中需要以子像素为单位的线性插值处理， 伴随着庞大的浮动小数点计算，因此计算量变多。

于是，本发明的目的在于提供一种能够高速地算出局部特征量的局部 特征量算出装置和方法以及利用了这些局部特征量算出装置和方法的对应 点搜索装置和方法。

本发明的局部特征量算出装置是算出图像的局部特征量的装置，具有 如下结构，具备：特征点附近区域抽取部，其从所述图像抽取特征点以及 设定于所述特征点附近的附近区域；方向强度计算部，其分别算出所述附 近区域内的各像素的方向以及其方向强度；主轴方向检测部，其检测所述 附近区域的主轴方向；以及局部特征量算出部，其对于所述各像素，对使 基准投票单元图案以与所述主轴方向相应的角度旋转而得到的旋转过的投 票单元图案的投票单元中的该像素所属的投票单元，按照根据所述主轴方 向对由所述方向强度计算部算出的该像素的方向进行修正而得到的修正过 的方向，进行由所述方向强度计算部算出的该像素的方向强度的投票，由 此求出所述特征点的局部特征量。

根据该结构，为了实现旋转不变性，不是对使特征点的附近区域的纹 理图案旋转之后重新设定的投票单元图案的单元进行投票，而是使投票单 元图案旋转，对该旋转后的投票单元图案(旋转过的投票单元图案)的投 票单元进行投票，因此不需要伴随着用于使纹理图案旋转的庞大的浮动小 数点计算的、以子像素为单位的线性插值处理，能够提高算出局部特征量 的速度。特征点附近区域抽取部可以仅抽取构成图像的像素中的满足预定 条件的像素来作为特征点，也可以将图像的所有像素作为特征点。另外， 主轴方向检测部也可以根据生成图像时的摄像装置所具备的陀螺仪传感 器、地磁传感器、重力传感器等的检测值来进行检测。

另外，在上述局部特征量算出装置中，所述主轴方向检测部根据由所 述方向强度计算部算出的所述附近区域中的多个像素的方向以及其方向强 度来检测所述附近区域的主轴方向。

如上所述，本发明的局部特征量算出装置为了实现旋转不变性，不是 使纹理图案旋转，而是使投票单元图案旋转，在对各像素的方向进行了修 正之后进行投票，因此不需要对旋转后的纹理图案再次计算各像素的方向 以及其方向强度，由方向强度计算部算出的各像素的方向以及其方向强度 既能够利用于主轴方向的检测，也能够利用于局部特征量的算出。由此， 用于算出各像素的方向以及其方向强度的微分计算为一次即可，能够提高 算出局部特征量的速度。

另外，上述局部特征量算出装置还具备方向量化部，该方向量化部将 所述像素的方向量化，所述主轴方向检测部按照由所述方向量化部量化后 的像素的方向进行该像素的方向强度的投票，由此生成方向直方图，对所 述方向直方图的峰附近进行曲线近似，检测与该曲线的极大点对应的方向 来作为所述主轴方向。

根据该结构，能够按照量化后的各方向积累强度，能够检测强度的积 累值最大的方向来作为主轴方向。另外，对直方图的峰进行曲线近似而将 其极大点作为主轴方向，因此能够得到实数的主轴方向。主轴方向可以由 对像素的方向进行了量化时的量化数(整数)来表现，也可以由弧度来表 现。

另外，上述局部特征量算出装置还具备投票单元图案生成部，该投票 单元图案生成部使所述基准投票单元图案旋转与所述主轴方向相应的角 度，由此生成所述旋转过的投票单元图案。

根据该结构，能够生成与主轴方向对应地进行了旋转的旋转过的投票 单元图案。

另外，上述局部特征量算出装置还具备方向修正图案生成部，该方向 修正图案生成部生成方向修正图案，该方向修正图案用于根据所述主轴方 向对由所述方向强度计算部算出的像素的方向进行修正，所述局部特征量 算出部使用所述方向修正图案来修正各像素的方向，由此得到所述修正过 的方向。

根据该结构，与主轴方向对应地修正像素的方向，因此能够获取用于 对旋转过的投票单元图案进行投票的适当的方向。

另外，上述局部特征量算出装置还具备方向量化部，该方向量化部将 所述像素的方向量化，所述主轴方向检测部按照由所述方向量化部量化后 的像素的方向进行该像素的方向强度的投票，由此生成方向直方图，检测 所述方向直方图中具有极大值的方向来作为所述主轴方向。

根据该结构，能够按照量化后的各方向来累积其方向强度，能够检测 强度的累积值最大的方向来作为主轴方向。另外，将直方图中具有极大值 的方向作为主轴方向，因此能够得到离散化的主轴方向。主轴方向可以由 对像素的方向进行了量化时的量化数(整数)来表现，也可以由弧度来表 现。

另外，上述局部特征量算出装置还具备投票单元图案表，该投票单元 图案表存储有多个投票单元图案，所述多个投票单元图案是以分别与由所 述主轴方向检测部检测得到的多个主轴方向对应的多个角度使所述基准投 票单元图案旋转而得到的，所述局部特征量算出部使用存储在所述投票单 元图案表中的投票单元图案中的与所述主轴方向对应的投票单元图案作为 所述旋转过的投票单元图案，算出所述局部特征量。

如上所述，在作为离散化的值而得到主轴方向的情况下，能够预先准 备与各主轴方向对应的旋转过的投票单元图案而使之表格化。根据上述结 构，在使用这样的表格得到了主轴方向时，通过从表格中选择与其主轴方 向对应的旋转过的投票单元图案，从而不需要每次通过计算来求出投票单 元图案，因此能够提高处理的速度。另外，使对投票单元图案预先存储的 旋转过的投票单元图案为与附近区域相同的大小时，分别仅通过一次的存 储器访问(表格的查找)就能够得到各像素要投票的投票单元。

另外，上述局部特征量算出装置还具备：代表投票单元图案表，其存 储有以分别与由所述主轴方向检测部检测得到的多个主轴方向对应的多个 角度使所述基准投票单元图案旋转而得到的多个投票单元图案中的、图案 的形状相互不重复的多个代表投票单元图案；以及单元编号转换表，其用 于按照所述主轴方向来转换所述代表投票单元图案的单元编号，所述局部 特征量算出部参照所述单元编号转换表，按照所述主轴方向对存储在所述 投票单元图案表中的所述代表投票单元图案中的与所述主轴方向对应的代 表投票单元图案的单元编号进行转换，由此确定进行所述方向强度的投票 的投票单元。

在基准投票单元图案具有点对称的形状的情况下，当使基准投票单元 图案旋转时，图案形状相同的旋转过的投票单元图案周期地出现。在上述 结构中，利用该周期性，实现了投票单元图案表的压缩。即，对于图案形 状重复的多个旋转过的投票单元图案，仅将其中的一个作为代表投票单元 图案而预先存储到投票单元图案表中，对于图案形状与代表投票单元图案 相同、但单元的编号不同的主轴方向，对代表投票单元图案的投票单元编 号进行转换，由此能够得到该主轴方向的旋转过的单元图案。

另外，上述局部特征量算出装置还具备方向修正表，该方向修正表对 由所述主轴方向检测部检测得到的多个主轴方向各自规定了对于由所述方 向量化部量化后的方向的所述修正过的方向，所述局部特征量算出部通过 参照所述方向修正表，从而按照所述主轴方向，获取与由所述方向量化部 量化后的方向对应的所述修正过的方向。

在离散地得到主轴方向的情况下，关于像素的方向也能够预先准备表 格。根据上述结构，使用这样的表格对各像素的方向进行修正，因此对于 各像素分别仅通过一次的存储器访问(表格的查找)就能够得到的修正过 的方向，能够提高处理的速度。

另外，上述局部特征量算出装置还具备：代表方向修正表，其将由所 述主轴方向检测部检测得到的多个主轴方向中的、对于由所述方向量化部 量化后的方向的所述修正过的方向具有同一周期的主轴方向作为一组，对 各组规定了对于由所述方向量化部量化后的方向的代表修正过的方向；以 及方向转换表，其用于按照所述主轴方向对所述代表方向修正表的所述代 表修正过的方向进行转换，所述局部特征量算出部参照所述方向转换表， 按照所述主轴方向，对由所述代表方向修正表规定的所述代表修正过的方 向中的、与所述主轴方向以及由所述方向量化部量化后的方向对应的代表 修正过的方向进行转换，由此获取所述修正过的方向。

当在方向修正表中修正过的方向也具有周期性的情况下，也能够压缩 表格。根据上述结构，将修正过的方向具有同一周期的主轴方向作为一组， 对于各组中仅存储代表的修正过的方向，在实际修正方向的情况下，参照 代表修正方向表，按照主轴方向来求出代表修正方向，并且按照主轴方向 来转换所得到的代表修正方向，由此能够得到修正过的方向。

另外，在上述局部特征量算出装置中，关于所述各像素，在该像素属 于多个所述投票单元的情况下，所述局部特征量算出部根据各投票单元在 该像素中所占的比例，对该多个所述投票单元进行该像素的方向强度的投 票。

在投票单元图案中，能够设定投票单元以使得各像素仅属于任一个投 票单元，但这样一来，由于旋转过的投票单元图案的旋转角的不同，在投 票单元的边界附近会产生误差。根据上述结构，通过使一个像素属于多个 投票单元，不管旋转过的投票单元图案的旋转角如何，都能够得到正确的 投票值。

另外，在上述局部特征量算出装置中，所述方向为像素的边缘梯度方 向，所述方向的强度为像素的边缘强度。

根据该结构，通过对像素进行微分能够得到方向及其强度。

另外，在上述局部特征量算出装置中，所述局部特征量算出部根据进 行所述方向强度的投票的投票单元的大小对所述方向强度进行加权而进行 投票。

如上所述，在投票单元图案中，能够设定投票单元以使得各像素仅属 于任一个投票单元，但这样一来，相同的投票单元的面积会由于旋转过的 投票单元图案的旋转角不同而产生不同。根据上述结构，根据投票单元的 大小对要投票的强度进行加权，因此如上所述由于旋转过的投票单元图案 的旋转角不同引起的向同一投票单元进行的投票的累计值的误差能够得到 缓和。

另外，在上述局部特征量算出装置中，所述方向强度计算部进行越是 接近所述特征点的像素、越增加权重的加权来算出所述方向强度。

根据该结构，在附近区域中，视为越接近特征点的像素越是重要的像 素。

本发明的其它方式是一种对应点搜索装置，用于对多个图像之间的对 应点进行搜索，具有以下结构，具备：上述任一项所述的局部特征量算出 装置；以及对应点搜索部，其通过对使用所述局部特征量算出装置算出的 所述多个图像各自的局部特征量相互进行比较来对所述多个图像之间的对 应点进行搜索。

根据该结构，能够为了对多个图像之间的对应点进行搜索而高速地算 出局部特征量。

本发明的另一个方式是一种局部特征量算出方法，用于算出图像的局 部特征量，具有以下构成，包括：特征点抽取步骤，从所述图像抽取特征 点；附近区域设定步骤，在所述特征点附近设定附近区域；方向算出步骤， 算出所述附近区域内的各像素的方向；强度算出步骤，算出所述附近区域 内的各像素的方向强度；主轴方向检测步骤，根据所述附近区域内的多个 像素的所述方向以及所述方向强度，检测该附近区域的主轴方向；投票单 元图案旋转步骤，使基准投票单元图案以与所述主轴方向相应的角度进行 旋转来获取旋转过的投票单元图案；方向修正步骤，根据所述主轴方向来 修正各像素的所述方向而获取修正过的方向；以及局部特征量算出步骤， 关于所述附近区域内的各像素，对所述旋转过的投票单元图案的投票单元 中的该像素所属的投票单元，按照所述修正过的方向，进行该像素的所述 方向强度的投票，由此求出所述特征点的局部特征量。

根据该构成，为了实现旋转不变性，也不是对使特征点的附近区域的 纹理图案旋转之后重新设定的投票单元图案的单元进行投票，而是使投票 单元图案旋转，对该旋转后的投票单元图案(旋转过的投票单元图案)的 投票单元进行投票，因此不需要伴随着用于使纹理图案旋转的庞大的浮动 小数点计算的、以子像素为单位的线性插值处理，能够提高算出局部特征 量的速度。上述各步骤可以不一定按照记载的顺序来执行。上述步骤的一 部分可以并行地执行，或者上述步骤的一部分也可以按照与记载的顺序不 同的顺序来执行。

本发明的另一个方式是一种局部特征量算出方法，用于算出图像的局 部特征量，具有以下构成，包括：特征点抽取步骤，从所述图像抽取特征 点；附近区域设定步骤，在所述特征点附近设定附近区域；方向算出步骤， 算出所述附近区域内的各像素的方向；方向量化步骤，将所述附近区域内 的各像素的所述方向量化；强度算出步骤，算出所述附近区域内的各像素 的方向强度；主轴方向检测步骤，按照通过所述方向量化步骤量化后的像 素的方向进行该像素的方向强度的投票，由此生成方向直方图，检测所述 方向直方图中具有极大值的方向来作为所述附近区域的主轴方向；投票单 元确定步骤，对于所述附近区域内的各像素，参照投票单元图案表，确定 与所述主轴方向对应的投票单元图案中的、该像素所属的投票单元，所述 投票单元图案表存储有以分别与通过所述主轴方向检测步骤检测得到的多 个主轴方向对应的多个角度使基准投票单元图案旋转而得到的多个投票单 元图案；方向修正步骤，关于所述附近区域内的各像素，参照方向修正表 来获取与所述主轴方向以及通过所述方向量化步骤量化后的方向对应的修 正过的方向，所述方向修正表对于通过所述主轴方向检测步骤检测得到的 多个主轴方向各自规定了对于通过所述方向量化步骤量化后的方向的修正 过的方向；以及局部特征量算出步骤，关于所述附近区域内的各像素，对 通过所述投票单元确定步骤确定的投票单元，按照所述修正过的方向，进 行该像素的所述方向强度的投票，由此求出所述特征点的局部特征量。

根据该构成，为了实现旋转不变性，也不是对使特征点的附近区域的 纹理图案旋转之后重新设定的投票单元图案的单元进行投票，而是使投票 单元图案旋转，对该旋转后的投票单元图案(旋转过的投票单元图案)的 投票单元进行投票，因此不需要伴随着用于使纹理图案旋转的庞大的浮动 小数点计算的、以子像素为单位的线性插值处理，能够提高算出局部特征 量的速度。另外，作为离散的值而得到主轴方向，因此通过利用表格能够 获取旋转过的投票单元图案，另外，还能够使用表格对各像素的方向进行 修正，因此能够进一步提高算出局部特征量的速度。投票单元图案表和方 向修正表可以是压缩的表格与转换表格的组合。另外，上述各步骤可以不 一定按照记载的顺序来执行。上述步骤的一部分可以并行地执行，或者上 述步骤的一部分也可以按照与记载的顺序不同的顺序来执行。

本发明的另一个方式是一种对应点搜索方法，用于对多个图像之间的 对应点进行搜索，具有以下构成，包括：局部特征量算出步骤，按照上述 的局部特征量算出方法来算出所述多个图像各自的局部特征量；以及对应 点搜索步骤，对通过所述局部特征量算出步骤算出的所述多个图像各自的 局部特征量相互进行比较，由此搜索所述多个图像之间的对应点。

根据该构成，能够为了对多个图像之间的对应点进行搜索而高速地算 出局部特征量。上述各步骤可以不一定按照记载的顺序来执行。上述步骤 的一部分可以并行地执行，或者上述步骤的一部分也可以按照与记载的顺 序不同的顺序来执行。

本发明的另一个方式是一种程序，用于使运算处理装置执行上述任一 个方法。

根据本发明，为了实现旋转不变性，不是对使特征点的附近区域的纹 理图案旋转之后重新设定的投票单元图案的单元进行投票，而是使投票单 元图案旋转，对该旋转后的投票单元图案的投票单元进行投票，因此不需 要伴随着用于使纹理图案旋转的庞大的浮动小数点计算的、以子像素为单 位的线性插值处理，能够提高算出局部特征量的速度。

附图说明

图1是表示本发明第一实施方式的局部特征量算出装置的结构的框 图。

图2是表示本发明第一实施方式的输入图像中的特征点和附近区域的 图。

图3是表示本发明第一实施方式的将输入图像缩小多级而得到的金字 塔图像的图。

图4是说明本发明第一实施方式的边缘梯度方向的量化的图表。

图5是表示本发明第一实施方式的边缘梯度方向的直方图的图表。

图6A是表示本发明第一实施方式的投票单元图案(主轴方向0度) 的图。

图6B是表示本发明第一实施方式的投票单元图案(主轴方向22.5度) 的图。

图7是表示本发明第一实施方式的使投票单元图案与输入图像重叠的 状况的图。

图8是用于说明本发明第一实施方式的表示局部特征量的向量的图。

图9是本发明第一实施方式的局部特征量算出方法的流程图。

图10是表示本发明第二实施方式的局部特征量算出装置的结构的框 图。

图11是表示本发明第二实施方式的与主轴的各方向对应的各投票单 元图案的图。

图12是表示本发明第二实施方式的投票单元图案表的图。

图13是表示本发明第二实施方式的压缩了的投票单元图案表的图。

图14是表示本发明第二实施方式的用于确定投票单元图案的压缩用 转换表的图。

图15是表示本发明第二实施方式的方向修正表的图。

图16是表示本发明第二实施方式的压缩了的方向修正表的图。

图17是表示本发明第二实施方式的用于进行方向修正的压缩用转换 表的图。

图18是表示本发明第二实施方式的局部特征量算出方法的流程图。

图19是说明本发明第二实施方式的关于一个像素在多个投票单元进 行投票的处理的图。

图20是表示本发明第三实施方式的对应点搜索装置的结构的框图。

图21是本发明第三实施方式的对应点搜索方法的流程图。

图22是表示两个图像之间的对应点的图。

图23是用于说明使用了局部特征量的图像检索的图。

图24是基于SIFT的局部特征量算出处理的流程图。

图25是用于说明基于SIFT的局部特征量算出处理的图。

图26是用于说明基于SIFT的局部特征量算出处理的图。

图27是用于说明基于SIFT的局部特征量算出处理的图。

标号说明

1：局部特征量算出装置；11：特征点附近区域抽取部；12：方向强度 计算部；13：主轴方向检测部；14：投票单元图案生成部；15：方向修正 图案生成部；16：局部特征量算出部；2：局部特征量算出装置；21：特征 点附近区域抽取部；22：方向强度计算部；23：主轴方向检测部；24：投 票单元确定部；241：代表投票单元图案表；242：单元编号转换表；25： 方向修正部；251：代表方向修正部；252：方向转换表；26：局部特征量 算出部；3：对应点搜索装置；100：局部特征量算出装置；31：对应点搜 索部。

具体实施方式

以下，参照附图详细说明本发明的实施方式。以下说明的实施方式仅 是例示，并不限定本发明。

(第一实施方式)

图1是表示本发明第一实施方式的局部特征量算出装置1的结构的框 图。局部特征量算出装置1具备特征点附近区域抽取部11、方向强度计算 部12、主轴方向检测部13、投票单元图案生成部14、方向修正图案生成 部15以及局部特征量算出部16。局部特征量算出装置1可以作为硬件而 实现图1示出的结构，也可以通过对运算处理装置载入软件(计算机程序) 来实现图1示出的结构。局部特征量算出装置1输入图像而输出该图像中 的局部特征量。

对特征点附近区域抽取部11输入图像TP。特征点附近区域抽取部11 从构成对象图像的像素中抽取满足预定条件的像素来作为特征点p。用于 抽取特征点的条件被确定为能进行再现性高的抽取。例如，可以使用抽取 拐角点(角)的算法(角检测器)来抽取特征点。

这样，通过仅抽取构成输入图像的多个像素中的一部分像素来作为特 征点，从而仅针对输入图像中的一部分像素求出局部特征量，因此在使用 局部特征量的对应点搜索中，能够高速地搜索对应点。另一方面，也可以 抽取输入图像的所有像素来作为特征点。在该情况下，能够期望得到图像 之间的密切对应。

特征点附近区域抽取部11将抽取出的特征点p附近的预定区域设定为 附近区域NR而抽取该区域。在本实施方式中，将以特征点为中心的W× W像素的正方形的区域作为附近区域NR。图2是表示由特征点附近区域 抽取部11抽取出的特征点p1～p6以及特征点p1的附近区域NR1的图。 附近区域的形状不限于正方形，也可以是圆形、长方形等其它形状。

如图3所示，特征点附近区域抽取部11可以求出将图像TP缩小多级 而得到的金字塔图像，在同一条件下对于各比例尺的图像分别独立地抽取 特征点而定义附近区域。图3示出将比例尺设为s分之一而缩小多级得到 的金字塔图像。由此，能够求出具有尺度不变性且不会受到尺寸差异的影 响的局部特征量。另外，特征点附近区域抽取部11也可以通过DoG滤波 器与特征点一起获取尺度信息，根据该尺度信息来切出附近区域。由此， 也能够求出具有尺度不变性的局部特征量。

如上所述，特征点附近区域抽取部11通常从一个输入图像抽取多个特 征点p1～pN，对各特征点设定附近区域NR。并且，局部特征量算出装置 1对各特征点分别算出局部特征量。以下，对方向强度计算部12、主轴方 向检测部13、投票单元图案生成部14、方向修正图案生成部15以及局部 特征量算出部16进行说明。在由特征点附近区域抽取部11抽取出特征点 p1～pN的情况下，上述各部12～16对多个特征点p1～pN各自进行以下 说明的处理。在以下说明中，针对一个特征点说明用于求出其局部特征量 的处理。

方向强度计算部12算出附近区域NR内的各像素的方向以及其方向强 度。在此，在本发明中，像素的“方向”表示包含该像素的周边的小区域 中的像素值的分布偏移。另外，“方向强度”表示其偏移的程度、即“方向” 的可靠度。典型地，可以通过对像素的像素值进行微分来求出该像素的边 缘信息，根据该边缘信息来求出“方向”以及“方向强度”。即，通过将像 素在x方向和y方向上进行微分，能够求出边缘梯度方向和边缘强度来作 为边缘信息，能够将该边缘梯度方向作为该像素的“方向”，将该边缘强度 作为该像素的“方向强度”。在本实施方式中，作为像素的“方向”以及“方 向强度”分别采用边缘梯度方向和边缘强度。具体而言为如下所述。以下， (x，y)T表示图像上的坐标。

首先，分别通过式(1)和式(2)来求出坐标(x，y)的像素的x方 向微分fx(x，y)以及y方向微分fy(x，y)。

[式1]

f_x(x，y)＝f(x+1，y)-f(x-1，y)...(1)

[式2]

f_y(x，y)＝f(x，y+1)-f(x，y-1)...(2)

然后，使用这些x方向微分fx(x，y)以及y方向微分fy(x，y)， 分别通过式(3)和式(4)来求出边缘梯度方向θ(x，y)以及边缘强度 m(x，y)。

$\theta (x,y)={\tan }^{-1}\left(\frac{f_y(x,y)}{f_x(x,y)}\right)...\left(3\right)$

$m(x,y)=\sqrt{f_x{(x,y)}^2+f_y{(x,y)}^2}...\left(4\right)$

但是，根据式(3)，对于边缘梯度方向，无法区别第一象限与第三象 限、以及第二象限与第四象限。因而，通过参照x方向微分fx(x，y)以 及y方向微分fy(x，y)的符号来适当地进行修正，从而求出0～2π的方 向来作为边缘梯度方向。以下，为了简化记载，设为反正切均输出0～2π 的值。

方向强度计算部12使用由式(4)求出的边缘强度，通过式(5)来求 出加权边缘强度mhat(x，y)。p＝(px，py)T为特征点的位置。另外， “hat”表示式中的“^”。

$\hat{m}(x,y)=w(x-p_x,y-p_y)m(x,y)...\left(5\right)$

在此，函数w(x，y)为权重，例如，可以使用将平均设为(0，0) T、将协方差矩阵设为式(6)的二维高斯分布。由此，视为越是中心的像 素则越重要。

$\left(\begin{array}{cc}{\sigma }^2& 0\\ 0& {\sigma }^2\end{array}\right)...\left(6\right)$

由方向强度计算部12求出的加权边缘强度mhat(x，y)分别被使用 于后级的主轴方向检测部13和局部特征量算出部16中，但也可以在主轴 方向检测用和局部特征量算出用中，分别使用不同的权重w(x，y)来分 别分开地求出主轴方向检测用的加权边缘强度和局部特征量算出用的加权 边缘强度。另外，当然也可以直接使用没有进行加权的边缘强度m(x，y) 来检测主轴方向、算出局部特征量。

如上所述，方向强度计算部12针对附近区域NR的各像素算出边缘梯 度方向θ(x，y)以及加权边缘强度mhat(x，y)，将这些输出到主轴方 向检测部13和局部特征量算出部16。

主轴方向检测部13检测主轴方向。因此，主轴方向检测部13首先通 过式(6)来将边缘梯度方向θ(x，y)量化。

$\hat{\theta }(x,y)=\mathrm{quantize}(\theta (x,y),N)...\left(6\right)$

在此，式(6)的右边为将边缘梯度方向θ(x，y)标量量化0～N-1 的函数，例如可以采用式(7)。

例如在N＝4的情况下将该式(7)表示于图表，则为如图4所示。根 据实验结果可知，优选N＝40左右。

当使附近区域NR内的各像素的边缘梯度方向θ(x，y)量化后，主 轴方向检测部13使用该量化后的边缘梯度方向θhat(x，y)以及由方向 强度计算部12得到的加权边缘强度mhat(x，y)，按照式(8)来求出边 缘梯度方向的直方图h(k)。

$h\left(k\right)=\underset{{(x,y)}^T\in S_k}{\Sigma }\hat{m}(x,y)...\left(8\right)$

在式(8)中，由式(9)提供Sk。

Sk＝{(x，y)^T|(x，y)^T存在于特征点p的附近区域内，

并且，$\hat{\theta }(x,y)=k$}…(9)

如式(8)所示，对边缘梯度方向直方图的投票值使用加权边缘强度 hat(x，y)。图5是表示通过式(8)得到的边缘梯度方向直方图的示例的 图表。

主轴方向检测部13从该边缘梯度方向直方图h(k)求出主轴。在本 实施方式中，主轴方向检测部13对直方图h(k)的峰附近进行抛物线近 似，将以弧度表示出该抛物线的峰的部位作为主轴v。主轴v为实数，因 而将该主轴标记为vreal。如后所述，在其它实施方式中，将直方图的峰直 接作为主轴v。在该情况下，主轴v为离散的值、即0～N-1的整数值或者 将其转换为弧度而得到的值，因此将该主轴标记为vinteger，与vreal相区 别。

在边缘梯度方向直方图h(k)中存在多个峰的情况下，主轴方向检测 部13也可以检测出多个主轴方向。在该情况下，与主轴方向的数量相应地 提供局部特征量，在使用了局部特征量的对应点搜索中，搜索性能提高。 主轴方向检测部13将检测出的主轴方向vreal输出到投票单元图案生成部 14和方向修正图案生成部15。

投票单元图案生成部14以与主轴方向vreal相应的角度使基准单元图 案CP旋转。换言之，投票单元图案生成部14使投票单元图案CP旋转以 使得基准投票单元图案CP的基准方向ED与主轴方向vreal的方向一致。 将旋转后的投票单元图案称为旋转过的投票单元图案。作为投票单元图案， 与在上述背景技术中说明过的SIFT的情况同样地，可以采用由在4×4网 格上划分出的投票单元形成的投票单元图案，但在本实施方式中，如图6A 以及图6B所示，采用以下投票单元图案，即将圆沿着圆周划分为三个区 域，进而将这样完成的两个环状区域在半径方向上八等分地进行划分来形 成了投票单元。对投票单元图案CP的各投票单元VC依次付与投票单元 编号。

基准投票单元图案被设定为其中心为特征点的位置，将基准投票单元 图案的中心作为视点来旋转基准投票单元图案，由此得到旋转过的投票单 元图案。对中心的单元付与投票单元编号“0”，在其外侧的环状区域中， 从基准投票单元图案右侧的投票单元起绕逆时针方向依次付与“1”～“8” 的投票单元编号，在最外侧的环状区域中，从基准投票单元图案右侧的投 票单元起绕逆时针方向依次付与“9”～“16”的投票单元编号。换言之， 外侧的环状区域内，投票单元编号从右侧的投票单元起绕逆时针方向依次 为“1”～“8”，最外侧的环状区域内，投票单元编号从基准投票单元图案 右侧的投票单元起绕逆时针方向依次为“9”～“16”，该投票单元图案为 本实施方式的基准投票单元图案，使该基准投票单元图案旋转而得到的投 票单元图案为旋转过的投票单元图案。基准投票单元图案的基准方向RD 被取为通过投票单元0、投票单元1以及投票单元9的中心的方向。

图6A是在主轴方向vreal为水平右方向的情况下使得基准方向RD与 主轴方向vreal重叠的旋转过的投票单元图案CP’(即，没有从基准投票 单元图案旋转)，图6B是在主轴方向vreal为22.5度时旋转成该主轴方向 vreal与基准方向RD一致的旋转过的投票单元图案CP’。

图7是表示将旋转过的投票单元图案CP’重叠到图像TP上的状况的 图。在图7的示例中，主轴方向vreal为20度，旋转过的投票单元图案 CP’被旋转为其基准方向RD与主轴vreal的方向一致。在对各像素进行 投票的情况下，对该像素所属的投票单元进行投票。

在由弧度表示主轴方向vreal的情况下，通过式(10)来表示旋转为 基准投票单元图案CP的基准方向RD与主轴方向vreal的方向一致的旋转 过的投票单元图案CP’。即，投票单元图案生成部14通过将主轴vreal代 入到式(10)，从而生成按照主轴vreal旋转了的投票单元图案CP’。(px， py)T为特征点p的位置。

$\mathrm{voting}\_\mathrm{cell}\_\mathrm{patter}{n}_{v_{\mathrm{real}}}(x,y)=$

$\left(\begin{array}{ccc}0& \mathrm{if}& \sqrt{{(x-p_x)}^2+{(y-p_y)}^2}<r_1\\ 1+\mathrm{quantize}(v_{\mathrm{real}}+{\tan }^{-1}\left(\frac{y-p_y}{x-p_x}\right),8)& \mathrm{if}& r_1\le \sqrt{{(x-p_x)}^2+{(y-p_y)}^2}<r_2\\ 9+\mathrm{quantize}(v_{\mathrm{real}}+{\tan }^{-1}\left(\frac{y-p_y}{x-p_x}\right),8)& \mathrm{if}& r_2\le \sqrt{{(x-p_x)}^2+{(y-p_y)}^2}<r_3\end{array}\right)···\left(10\right)$

通过将像素的坐标(x，y)代入到该式(10)，从而确定该像素应该投 票的投票单元。在式(10)中，r1、r2、r3分别为图6A以及图6B示出的 投票单元图案中的投票单元0的半径、投票单元1～8的外周的半径(投票 单元9～16的内周的半径)、投票单元9～16的外周的半径。例如，在附近 区域NR的尺寸为25×25的尺寸时，选择r1＝3、r2＝8、r3＝12等即可。投 票单元图案生成部14将所生成的旋转过的投票单元图案CP’输出到局部 特征量算出部16。

方向修正图案生成部15根据主轴方向vreal，生成用于修正边缘梯度 方向θ(x，y)的方向修正图案。由式(11)表示方向修正图案。

$\mathrm{direction}\_{\mathrm{offset}}_{v_{\mathrm{real}}}\left(\theta \right)=\left(\begin{array}{cc}\theta -v_{\mathrm{real}}& \theta >v_{\mathrm{real}}\\ \theta -v_{\mathrm{real}}+2\pi & \theta \le v_{\mathrm{real}}\end{array}\right)...\left(11\right)$

根据式(11)可知，方向修正图案是用于修正边缘梯度方向θ(x，y) 以使得抵消主轴方向vreal相对于基准方向RD的倾斜的修正图案。方向 修正图案生成部15将所生成的方向修正图案输出到局部特征量算出部16。

局部特征量算出部16输入由方向强度计算部12算出的附近区域内的 各像素的边缘梯度方向θ(x，y)和加权边缘强度mhat(x，y)、由投票 单元图案生成部14生成的旋转过的投票单元图案CP’以及由方向修正图 案生成部15生成的方向修正图案，使用这些边缘梯度方向θ(x，y)和加 权边缘强度mhat(x，y)、旋转过投票单元图案CP’以及方向修正图案 来求出局部特征量d。具体而言，局部特征量算出部16用方向修正图案对 附近区域NR内的各像素的边缘梯度方向θ(x，y)进行修正而得到修正 过的边缘梯度方向。并且，按照修正过的边缘梯度方向，对旋转过的投票 单元图案CP’进行加权边缘强度mhat(x，y)的投票，由此求出局部特 征量d。

在投票时，局部特征量算出部16首先用方向修正图案对各像素的边缘 梯度方向θ(x，y)进行修正而得到修正过的边缘梯度方向，并将其量化 为8种。如图6A以及图6B所示，本实施方式的旋转过的投票单元图案 CP’具有合计17个投票单元。由此，在各投票单元中生成8个方向的直 方图，当连结这些直方图来作为局部特征量d时，局部特征量成为17× 8＝136维。在生成直方图的过程中进行投票的是各像素的加权边缘强度 mhat(x，y)。

当以d＝(d0，d1，…，d135)T这一向量标记来记载局部特征量时， 通过式(12)求出di。

$d_i=\underset{{(x,y)}^T\in S_i}{\Sigma }\hat{m}(x,y)...\left(12\right)$

通过式(13)提供该Si。

另外，通过式(14)求出式(13)的index(x，y)。

$\mathrm{index}(x,y)=8\times \mathrm{votiong}\_\mathrm{cell}\_\mathrm{patter}{n}_{v_{\mathrm{real}}}(x,y)+\mathrm{quantize}(\mathrm{direction}\_{{\mathrm{offset}}_v}_{\mathrm{real}}(\theta ,\left(x,y\right)),8)...\left(14\right)$

式(14)的voting_cell_pattern_vreal(x，y)是由式(10)表示的。另 外，式(14)的direction_offset_vreal(θ(x，y))是由式(11)表示的， 对函数quantize(θ，8)采用式(7)。

根据式(14)，在局部特征量d＝(d0，d1，…，d135)中，(d0，d1，…， d7)为对投票单元0进行了投票的8个方向各自的投票累计值，(d8，d9，…， d15)为对投票单元1进行了投票的8个方向各自的投票累计值，(d16， d17，…，d23)为对投票单元2进行了投票的8个方向各自的投票累计值， 以下是同样的。用附图对其说明时，则为如图8所示。

接着，说明由局部特征量算出装置1执行的局部特征量算出方法。局 部特征量算出方法可以是由硬件构成的局部特征量算出装置1执行的方 法，也可以是载入到运算处理装置而构成局部特征量算出装置1的软件(计 算机程序)执行的方法。图9是本实施方式的局部特征量算出方法的流程 图，本实施方式的局部特征量算出方法根据所输入的图像来算出局部特征 量。

首先，特征点附近区域抽取部11从图像TP抽取特征点p(步骤S11)。 接着，特征点附近区域抽取部11在特征点p附近设定附近区域NR(步骤 S12)。然后，特征点附近区域抽取部11将特征点p和附近区域NR输出到 方向强度计算部12。方向强度计算部12通过在x方向和y方向上分别对 附近区域NR内的各像素进行微分，由此对于附近区域NR内的各像素算 出边缘梯度方向θ(x，y)(步骤S13)，并算出加权边缘强度mhat(x，y) (步骤S14)。关于步骤S13和步骤S14，哪一个先进行都可以，两者也可 以并行进行。

接着，主轴方向检测部13将边缘梯度方向θ(x，y)量化(步骤S15)。 然后，主轴方向检测部13对附近区域NR内的像素的量化后的边缘梯度方 向θhat(x，y)进行加权边缘强度mhat(x，y)的投票，由此生成边缘 梯度方向直方图(步骤S16)。主轴方向检测部13在该梯度方向直方图的 峰附近进行曲线拟合，检测与该曲线的极大点对应的方向(实数)来作为 附近区域NR的主轴方向vreal(步骤S17)。

投票单元图案生成部14从主轴方向检测部13获取主轴方向vreal，以 与主轴方向vreal相应的角度使基准投票单元图案PC旋转，生成旋转过的 投票单元图案PC(步骤S18)。另外，方向修正图案生成部15生成与主轴 方向vreal相应的方向修正图案(步骤S19)。关于步骤S18和步骤S19， 哪一个先进行都可以，两者也可以并行进行。

从方向强度计算部12对局部特征量算出部16输入边缘梯度方向θhat (x，y)和加权边缘强度mhat(x，y)，从投票单元图案生成部14对局部 特征量算出部16输入旋转过的投票单元图案PC’，从方向修正图案生成 部15对局部特征量算出部16输入方向修正图案。局部特征量算出部16 针对附近区域NR内的各像素，按照方向修正图案对边缘梯度方向θhat (x，y)进行修正，获取修正过的边缘梯度方向(步骤S20)。局部特征量 算出部16针对附近区域NR内的各像素，按照修正过的边缘梯度方向对旋 转过的投票单元图案PC’的投票单元中的该像素所属的投票单元进行该 像素的加权边缘强度mhat(x，y)的投票(步骤S21)。由此，求得特征 点p的局部特征量d。

如上所述，在本实施方式中，为了实现旋转不变性，不是如现有技术 那样对使特征点p的附近区域NR的纹理图案旋转之后重新设定的投票单 元图案的单元进行投票，而是使基准投票单元图案CP旋转，对该旋转后 的投票单元图案(旋转过的投票单元图案CP’)的投票单元进行投票，因 此不需要伴随着用于使纹理图案旋转的庞大的浮动小数点计算的、以子像 素为单位的线性插值处理，能够提高算出局部特征量的速度。

另外，如上所述，为了实现旋转不变性，不是使纹理图案旋转，而是 使基准投票单元图案旋转，并且修正各像素的方向之后进行投票，因此不 需要如现有技术那样针对旋转后的纹理图案再次计算各像素的方向以及其 方向强度，由方向强度计算部12算出的各像素的边缘梯度方向和边缘强度 既能够利用于主轴方向vreal的检测，也能够利用于局部特征量的算出。 由此，用于算出各像素的边缘梯度方向和边缘强度的微分计算为一次即可， 能够提高算出局部特征量的速度。

(第二实施方式)

图10是表示本发明第二实施方式的局部特征量算出装置的结构的框 图。本实施方式的局部特征量算出装置2具备特征点附近区域抽取部21、 方向强度计算部22、主轴方向检测部23以及局部特征量算出部26。局部 特征量算出装置2可以作为硬件实现图10示出的结构，也可以通过对运算 处理装置载入软件来实现图10示出的结构。

特征点附近区域抽取部21与第一实施方式的特征点附近区域抽取部 11同样地，从所输入的图像TP抽取特征点p，对各特征点p设定附近区 域NR。方向强度计算部22也与第一实施方式的方向强度计算部12同样 地，对附近区域NR内的各像素在x方向和y方向进行微分，由此算出边 缘梯度方向θ(x，y)和边缘强度m(x，y)来作为“方向”以及“方向 强度”。

在第一实施方式中，主轴方向检测部13通过式(6)对由方向强度计 算部22求出的、附近区域NR内的像素的边缘梯度方向θ(x，y)进行了 量化，但在本实施方式中，方向强度计算部22进行该量化，方向强度计算 部22将量化后的边缘梯度方向θhat(x，y)输出到主轴方向检测部23和 局部特征量算出部26。方向强度计算部22与第一实施方式的方向强度计 算部12同样地，对边缘强度求出加权边缘强度mhat(x，y)，并将其输出 到主轴方向检测部23和局部特征量算出部26。

主轴方向检测部23从方向强度计算部22获取量化后的边缘梯度方向 θhat(x，y)和加权边缘强度mhat(x，y)，通过式(8)、(9)求出边缘 梯度方向的直方图h(k)。并且，将直方图h(k)的峰作为主轴方向vinteger (参照图5)。该主轴方向vinteger为0～N-1中的任一个整数值、即离散 的值。主轴方向检测部23也可以将该整数值转换为弧度。在该情况下，作 为主轴vinteger的弧度也取离散的值。主轴方向检测部23将作为离散的值 的主轴vinteger输出到局部特征量算出部26。

与第一实施方式的局部特征量算出装置1相比，本实施方式的局部特 征量算出装置2不具备第一实施方式的投票单元图案生成部14和方向修正 图案生成部15。这是由于，在本实施方式中，由主轴方向检测部23作为 离散的值而检测出主轴方向，因此能够使旋转了的投票单元图案、方向修 正图案表格化，不需要如第一实施方式那样每次根据检测出的主轴方向生 成(计算)旋转过的投票单元图案、方向修正图案。本实施方式的局部特 征量算出部26在其中具备投票单元确定部24和方向修正部25。

首先，说明投票单元确定部24。投票单元确定部24按照从主轴方向 检测部23得到的主轴vinteger来确定投票单元图案，参照确定出的投票单 元图案，获取与关注像素的位置对应的投票单元编号。

图11示出基准投票单元图案PC以及与各主轴方向vinteger对应的旋 转过的投票单元图案PC’。投票单元图案的形状与图6A以及图6B示出的 投票单元图案相同，投票单元为0～16的17个。单元编号的标记方式也与 图6A以及图6B相同。

如上所述，主轴方向vinteger被离散化为0～N-1，其种类是有限的 (0～N-1)，因此与此对应的旋转过的投票单元图案的种类也是有限的 (0～N-1)。由此，若预先使这些有限的旋转过的投票单元图案表格化， 则在提供了主轴方向vinteger后，通过从表格读出投票单元图案，能够获 取以与该主轴方向vinteger对应的角度旋转了的旋转过的投票单元图案。

图12是表示投票单元图案表的示例的图。图12示出N＝40、W＝25的 情况。各旋转过的投票单元图案PC’的大小与附近区域NR的大小W× W(＝25×25)相同。即，对W×W内的各像素付与该像素所属的投票单 元的编号。对圆的外侧付与单元编号“-1”，不被投票。在图12的示例中， 对一个像素分配一个投票单元。

通过在投票单元确定部24中保存图12示出的投票单元图案表，当从 主轴方向检测部23提供主轴方向vinteger后，投票单元确定部24选择与 该主轴方向vinteger对应的旋转过的投票单元图案，按照各像素的坐标来 确定投票单元。

在基准投票单元图案具有点对称的形状的情况下，当以预定的步长使 该基准投票单元图案旋转时，图案形状相同的旋转过的投票单元图案周期 地出现。因而，在该情况下，通过使用单元编号转换表，能够压缩投票单 元图案表。

在本实施方式中，投票单元图案为点对称，步数为N＝40，因此图案 形状相同的旋转过的投票单元图案分别按45度(每五步)周期地出现。由 此，能够压缩投票单元图案表。即，主轴vinteger＝5～39的投票单元图案 能够使用主轴vinteger＝0～4的投票单元图案来表现，由此，能够将投票 单元图案的表格压缩为八分之一。例如，主轴vinteger＝5～9的投票单元 图案能够使用主轴vinteger＝0～4的投票单元图案来用式(15)表现。

$\mathrm{voting}\_\mathrm{cell}\_{\mathrm{pattern}}_{v_{\mathrm{int>}}+5}(x,y)={\mathrm{compress}}_A(\mathrm{voting}\_\mathrm{cell}\_{{\mathrm{pattern}}_v}_{\mathrm{integer}}(x,y))...\left(15\right)$

因此，在本实施方式中，如图10所示，实际上在投票单元确定部24 设置代表投票单元图案表241，如图13所示，作为代表投票单元图案而仅 存储图11的主轴vinteger＝0～4的投票单元图案。换言之，在代表单元图 案表241中仅存储有图案形状相互不重叠的多个代表投票单元图案。在本 实施方式中，与主轴方向vinteger＝0、1、2、3、4对应的五种旋转过的投 票单元图案成为代表投票单元图案。并且，在投票单元确定部24中还保存 有图14示出的单元编号转换表(comprssA)242。

当被提供主轴方向vinteger时，投票单元确定部24首先参照图13的 代表投票单元图案表241，选择五种代表投票单元图案中的与该主轴方向 vinteger相符的代表投票单元图案。然后，在该代表投票单元图案中得到 关注像素的坐标所属的投票单元的单元编号。接着，参照图13的压缩用转 换表242，对得到的投票单元的单元编号进行转换。

例如，在主轴方向vinteger＝18的附近区域，对于以特征点为中心的 坐标为(-4，2)的关注像素，主轴方向vinteger为“18”，因此选择从图 13的左侧起第四个代表投票单元图案，关注像素的坐标为(-4，2)，因此 得到单元编号“4”。通过参照图14示出的单元编号转换表242的第4行第 5列，将该单元编号“4”转换为“1”。由此，将该关注像素的投票单元确 定为投票单元1。

进一步，在投票单元图案的第一象限、第二象限、第三象限以及第四 象限为相似形的情况下，着眼于此，能够进一步将图12示出的投票单元图 案表压缩为四分之一。

接着，说明方向修正部25。方向修正部25使用从方向强度计算部22 得到的针对附近区域内的各像素的量化后的边缘梯度方向θhat(x，y)、 以及从主轴方向检测部23得到的主轴方向vinteger，修正其边缘梯度方向。

如上所述，在本实施方式中，主轴方向vinteger被离散化为0～N-1， 其种类是有限的(0～N-1)，另外，边缘梯度方向θhat(x，y)也是离散 的值，因此能够使与主轴方向vinteger和边缘梯度方向θhat(x，y)的组 合对应的修正过的边缘梯度方向表格化。通过准备这样的表格，在被提供 主轴方向vinteger后，从表格读出边缘梯度方向，由此能够根据该主轴方 向vinteger来获取修正后的修正过的边缘梯度方向。

图15是表示方向修正表的示例的图。图15示出N＝40的情况。在方 向修正部25中保存图15示出的方向修正表，由此当被提供主轴方向 vinteger和量化后的边缘梯度方向θhat(x，y)后，方向修正部25能够 通过参照图15的方向修正表，求出0～7的8个方向的任一个方向来作为 修正过的边缘梯度方向。

根据图15可知，在方向修正表中，修正过的边缘梯度方向相对于边缘 梯度方向θhat(x，y)的变化具有周期性。因而，能够利用该周期性来压 缩表格。在本实施方式中，N＝40，因此通过使用压缩用转换表，能够将图 15的方向修正表压缩为八分之一。即，能够从主轴方向vinteger＝0～4的 部分的表格中求出主轴方向vinteger＝5～40的情况下的边缘梯度方向(0～ 7)。例如，在主轴方向vinteger＝5～9的情况下，可以使用主轴vinteger＝0～ 4的部分的方向修正表来以式(16)表现。

$\mathrm{direction}\_{\mathrm{offset}}_{v_{\mathrm{int>}}+5}\left(\hat{\theta }\right)={\mathrm{compress}}_B(\mathrm{direction}\_{{\mathrm{offset}}_v}_{\mathrm{integer}}\left(\hat{\theta }\right))...\left(16\right)$

因此，在本实施方式中，如图10所示，实际上在方向修正部25设置 代表方向修正表251，如图16所示，在该代表方向修正表251中，仅图15 的表格中的vinteger＝0～4的部分被规定为代表修正过的边缘梯度方向。 换言之，在代表方向修正表251中，以相对于边缘梯度方向θhat(x，y) 的修正过的边缘梯度方向具有相同的周期的主轴方向(例如，主轴方向 vinteger＝0、5、10、15、20、25、30、35)为一组，对各组仅规定一行的 代表修正过边的缘梯度方向。在本实施方式中，在代表方向修正表251中 规定与主轴方向vinteger＝0、1、2、3、4对应的修正过的边缘梯度方向(图 15的第1行～第5行)来作为代表修正过的边缘梯度方向。并且，在方向 修正部25中还保存有图17示出的方向转换表(compressB)252。

当被提供主轴vinteger和量化后的边缘梯度方向θhat(x，y)后，方 向修正部25通过参照图16示出的代表方向修正表251来获取0～8中的任 一个方向，接着，通过用图17示出的方向转换表252对该方向进行转换， 由此获取修正过的边缘梯度方向。例如，关于主轴vinteger＝18、边缘梯度 方向θhat(x，y)＝10的关注像素，从图16的代表方向修正表251的第4 行第11列得到“1”，接着从图16的方向转换表252的第4行第2列得到 “6”来作为修正过的边缘梯度方向。如上所述，方向修正部25针对附近 区域NR的各像素，获取0～7中的任一个方向来作为修正过的边缘梯度方 向。

当由投票单元确定部24确定投票单元而由方向修正部25得到修正过 的边缘梯度方向后，局部特征量算出部26对其像素的边缘强度进行投票。 通过对附近区域NR的所有像素进行这样的投票处理，局部特征量算出部 26得到局部特征量d＝(d0，d1，…，d135)T。局部特征量di用算式表 示为式(17)。

$d_i=\underset{{(x,y)}^T\in S_i}{\Sigma }\hat{m}(x,y)...\left(17\right)$

在此，由式(18)提供式(17)的Si。

另外，由式(19)提供式(18)的index(x，y)。

$\mathrm{index}(x,y)=8\times \mathrm{voting}\_\mathrm{cell}\_{{\mathrm{pattern}}_v}_{\mathrm{integer}}(x,y)+\mathrm{direction}\_{{\mathrm{offset}}_v}_{\mathrm{integer}}\left(\hat{\theta }(x,y)\right)...\left(19\right)$

接着，说明本实施方式的局部特征量算出方法。本实施方式的局部特 征量算出方法中，从所输入的图像算出局部特征量。局部特征量算出方法 可以是由硬件构成的局部特征量算出装置2执行的方法，也可以载入到运 算处理装置而构成局部特征量算出装置2的软件(计算机程序)执行的方 法。图18是本实施方式的局部特征量算出方法的流程图。

特征点附近区域抽取部21从图像TP抽取特征点p(步骤S31)。接着， 特征点附近区域抽取部21在特征点p附近设定附近区域NR(步骤S32)。 然后，特征点附近区域抽取部21将特征点p和附近区域NR输出到方向强 度计算部22。方向强度计算部22在x方向和y方向上分别对附近区域NR 内的各像素进行微分，由此针对附近区域NR内的各像素算出边缘梯度方 向θ(x，y)(步骤S33)，对该边缘梯度方向θ(x，y)进行量化，求出 量化后的边缘梯度方向θhat(x，y)(步骤S34)。另外，方向强度计算部 22针对附近区域NR内的各像素算出加权边缘强度mhat(x，y)(步骤S35)。 关于步骤S33和该步骤S33的后续步骤S34、以及步骤S35，哪一方先进 行都可以，两者也可以并行进行。

接着，主轴方向检测部23通过对附近区域NR内的像素的量化后的边 缘梯度方向θhat(x，y)进行加权边缘强度mhat(x，y)的投票，从而 生成边缘梯度方向直方图(步骤S36)。主轴方向检测部23检测在其梯度 方向直方图中具有极大值的边缘梯度方向(离散化后的值)来作为附近区 域NR的主轴方向vinteger，将其输出到局部特征量算出部26(步骤S37)。

从方向强度计算部22对局部特征量算出部26输入量化后的边缘梯度 方向θhat(x，y)和加权边缘强度mhat(x，y)，从主轴方向检测部23 对局部特征量算出部26输入主轴方向vinteger。局部特征量算出部26参 照投票单元图案表，对附近区域NR内的各像素确定与主轴方向vinteger 对应的投票单元图案中的、关注像素所属的投票单元(步骤S38)。

在局部特征量算出部26中，在投票单元确定部24中存储有图12示出 的投票单元图案表的情况下，在步骤S38中，参照该投票单元图案表来确 定投票单元。另一方面，在投票单元确定部24中存储有图13示出的代表 投票单元图案表241以及图14示出的单元编号转换表242的情况下(图 10的情况下)，在步骤S38中，作为投票单元图案表，参照代表单元图案 表241和单元编号转换表242来确定投票单元。

局部特征量算出部26参照方向修正表，针对附近区域NR内的各像素 获取与主轴方向vinteger和量化后的边缘梯度方向θhat(x，y)对应的修 正过的边缘梯度方向(步骤S39)。

在局部特征量算出部26中，在方向修正部25中存储有图15示出的方 向修正表的情况下，在步骤S39中，参照该方向修正表，获取修正过的边 缘梯度方向。另一方面，在方向修正部25中存储有图16示出的代表方向 修正表251以及图17示出的方向转换表252的情况下(图10的情况下)， 在步骤S39中，参照代表方向修正表251和方向转换表252，获取修正过 的边缘梯度方向。关于步骤S38和步骤S39，哪一个先进行都可以，两者 也可以并行进行。

接着，局部特征量算出部26针对附近区域NR内的各像素，对通过步 骤S38确定的投票单元，按照通过步骤S39得到的修正过的边缘梯度方向， 进行关注像素的加权边缘强度mhat(x，y)的投票(步骤S40)，由此求 得特征点p的局部特征量d。

如上所述，在本实施方式中，为了实现旋转不变性，也不是如现有技 术那样对使特征点p的附近区域NR的纹理图案旋转之后重新设定的投票 单元图案的单元进行投票，而是对根据主轴方向旋转了的旋转过的投票单 元图案CP’的投票单元进行投票，因此不需要伴随着用于使纹理图案旋 转的庞大的浮动小数点计算的、以子像素为单位的线性插值处理，能够提 高算出局部特征量的速度。

另外，如上所述，为了实现旋转不变性，不是使纹理图案旋转，而是 对旋转过的基准投票单元图案修正各像素的方向之后进行投票，因此不需 要如现有技术那样对旋转后的纹理图案再次计算各像素的方向以及该方向 强度，由方向强度计算部22算出的各像素的边缘梯度方向和边缘强度既能 够利用于主轴方向vinteger的检测，也能够利用于局部特征量的算出。由 此，用于算出各像素的边缘梯度方向和边缘强度的微分计算为一次即可， 能够提高算出局部特征量的速度。

另外，在本实施方式中，作为离散化后的值而得到主轴方向vinteger， 因此能够预先准备与各主轴方向对应的旋转过的投票单元图案而使其表格 化，在使用这样的表格得到了主轴方向vinteger时，通过从表格选择与该 主轴方向vinteger对应的旋转过的投票单元图案，不需要每次通过计算来 求出投票单元图案，因此能够提高处理的速度。

进一步，在本实施方式中，基准投票单元图案具有点对称的形状，因 此能够利用其周期性来压缩投票单元图案表，能够减小所需的存储容量。 在为本实施方式所示的程度的表格时，能够放入到CPU的闪存中，能够 进一步提高处理的速度。

另外，在本实施方式中，还可以对像素的边缘梯度方向也准备表格， 使用这样的表格来修正各像素的边缘梯度方向，因此能够提高处理的速度。

进一步，在本实施方式中，修正过的边缘梯度方向具有周期性，因此 还能够压缩方向修正表，能够减小所需的存储容量。在为本实施方式所示 的程度的表格时，能够放入到CPU的闪存中，能够进一步提高处理的速 度。

在上述第二实施方式的投票单元图案中，设定投票单元以使得各像素 仅属于任一个投票单元，因此相同的投票单元的面积会由于旋转过的投票 单元图案的旋转角不同而产生不同。例如，参照图12，主轴方向vinteger＝0 时的投票单元1的面积为21个像素，但主轴方向vinteger＝1时的投票单 元1的面积为20个像素，尽管是相同的投票单元，但两个面积由于旋转过 的投票单元图案的旋转角不同而稍微不同。这样一来，即使是相同的图像， 由于主轴方向不同，在同一单元进行边缘强度的投票的像素数量也会是一 方多而另一方少，因此该投票单元的累计值也会产生误差。

考虑这一点，局部特征量算出部26也可以根据投票单元的大小来对加 权边缘强度进一步加权而进行投票。例如，可以将面积的倒数作为该权重。 由此，能够求出不会受到由旋转角不同引起的投票单元的面积不同的影响 的局部特征量。

另外，作为上述第二实施方式的投票单元图案，设定投票单元以使得 各像素仅属于任一个投票单元，因此由于旋转过的投票单元图案的旋转角 不同，在投票单元的边界附近会产生误差。

考虑这一点，如图19的(c)所示，对于位于投票单元的边界的像素， 局部特征量算出部26也可以对投票单元图案划实现，对于带有该实线的像 素，根据由实线分开的面积，在多个投票单元进行投票。图19的(a)是 图12示出的主轴方向vinteger＝0的旋转过的投票单元图案，图19的(b) 和(c)是放大其一部分(投票单元15与投票单元16的边界部分)而得到 的图。图19的(b)是不考虑误差的示例，图19的(c)是缓和误差的示 例的图。

在图19的(c)中，例如对于左上角的像素，其60％属于投票单元15， 其40％属于投票单元16。由此，对于该单元，在投票单元15进行加权边 缘强度mhat(x，y)的60％的投票，在投票单元16进行其40％的投票。 这样，通过使一个像素属于多个投票单元，不论旋转过的投票单元图案的 旋转角如何都能够得到正确的投票值。

(第三实施方式)

接着，作为第三实施方式说明采用了上述第一实施方式或者第二实施 方式的局部特征量算出装置的对应点搜索装置。图20是表示第三实施方式 的对应点搜索装置3的结构的框图。如图20所示，对应点搜索装置3具备 局部特征量算出装置100和对应点搜索部31。点搜索装置3可以作为硬件 实现图20示出的结构，也可以通过在运算处理装置载入软件来实现图20 示出的结构。

作为局部特征量算出装置100，采用第一实施方式的局部特征量算出 装置1或者第二实施方式的局部特征量算出装置2中的任一方。对局部特 征量算出装置100输入第一图像和第二图像，算出各自的局部特征量，将 其输出到对应点搜索部31。对应点搜索部31将第一图像的局部特征量与 第二图像的局部特征量进行比较来搜索特征点。

在检索图像的系统中，对应点搜索装置3能够作为对输入图像与保存 在图像数据库中的图像之间的对应点进行搜索的装置来应用，另外，在从 以不同视点拍摄得到的第一图像和第二图像还原三维形状的系统中，对应 点搜索装置3也能够作为对第一图像与第二图像之间的对应点进行搜索的 装置来应用，进而也能够应用于其它系统。

图21是本实施方式的对应点搜索方法的流程图。对应点搜索方法可以 是由硬件构成的对应点搜索装置3执行的方法，也可以是载入到运算处理 装置而构成对应点搜索装置3的软件(计算机程序)执行的方法。

在对应点的搜索中，首先，局部特征量算出装置100算出第一图像的 局部特征量(步骤S51)，接着，算出第二图像的局部特征量(步骤S52)。 在步骤S51和步骤S52中，能够采用第一实施方式的局部特征量算出方法 或者第二实施方式的局部特征量算出方法中的任一方。接着，对应点搜索 部31将第一图像的局部特征量与第二图像的局部特征量进行比较来搜索 对应点(步骤S53)。

如上所述，根据第一实施方式～第三实施方式，在局部特征量的算出 中，为了实现旋转不变性，不是对使特征点的附近区域的纹理图案旋转之 后重新设定的投票单元图案的单元进行投票，而是使投票单元图案旋转， 对该旋转了的投票单元图案(旋转过的投票单元图案)的投票单元进行投 票，因此不需要伴随着用于使纹理图案旋转的庞大的浮动小数点计算的、 以子像素为单位的线性插值处理，能够提高处理的速度，其结果，也能够 提高对应点搜索处理的速度。

根据第一实施方式～第三实施方式，算法也比作为以往的局部特征量 算出方法的SIFT、SURF简单，因此在使局部特征量算出装置硬件化时， 能够缩小电路规模，能够削减成本。另外，即使在作为软件进行装载的情 况下，也能够缩小执行二进制大小，因此具有易于装入各种应用程序 (application)的优点。因此，在使上述实施方式的局部特征量算出装置 硬件化的情况下以及进行软件装载的情况下，都能够适当地安装到移动设 备、低端设备中。

在上述实施方式中，像素的“方向”和“方向强度”不限于是根据边 缘信息得到的。“方向”和“方向强度”也可以通过小波变换、伽柏变换来 求出。另外，针对大量的图像，通过使边缘梯度方向、边缘强度数据库化 来加以学习，在输入了新的图像的情况下，也可以使用该数据库来求出边 缘梯度方向、边缘强度。

另外，在上述实施方式中，关于求出加权边缘强度mhat(x，y)时的 权重，也可以取为w(x，y)＝1来预先对多个图像求出局部特征量，根据 由此得到的统计量，重新确定权重w(x，y)。例如在存在较强的值向特定 的投票单元集中的趋势的情况下，通过减小该部分的权重，能够调整各投 票单元的贡献率。

另外，在上述实施方式中，主轴方向是根据图像信息(边缘梯度方向 和边缘强度图像)检测出的，但主轴方向不限于此，也可以根据生成时的 摄像装置所具备的陀螺仪传感器、地磁传感器或者重力传感器的检测值来 检测主轴方向，另外，也可以通过针对大量的图像使主轴方向数据库化来 加以学习，在输入了新的图像的情况下，使用该数据库来检测主轴方向。

产业上的可利用性

本发明具有能够提高算出局部特征量的速度的效果，作为算出图像的 局部特征量的局部特征量算出装置和局部特征量算出方法、以及使用了局 部特征量算出装置的对应点搜索装置和使用了局部特征量算出方法的对应 点搜索方法等是有用的。