特征点对等系统、特征点对等方法、以及记录介质

技术领域

本发明涉及一种特征点关联系统和特征点关联方法，利用该特征 点关联系统和特征点关联方法，通过信息处理在数据分析中使分别属 于来自两个图像等等的特征点的组并且可以被视为相同特征点的特征 点彼此关联。

背景技术

当可以使两个图像中的相同特征点（地点）彼此关联时可以从图 像获得各类信息。例如，借助于下述对应特征点通过立体匹配可以从 两个图像获得对象的三维形状，该对应特征点是来自两个图像的、彼 此相对应的特征点。此外，可以通过利用对应特征点来检查对象的变 化以校正图像，使得图像的对象重叠。该校正还使得可以检验在两个 图像中所拍摄的对象是否是相同的。

获得各类信息的另一方式是预先准备要比较的特征点组中的一个 作为三维数据并且使从图像或视频所提取的一组特征点与所准备的特 征点组关联。这可以在例如使实际拍摄的卫星图像或航拍图像与地图 数据关联时使用。类似地，这可以在使车载照相机的图像与汽车导航 数据关联时使用。

该特征点关联方法的示例是在专利文献1中所述的图形形式位置 检测方法。专利文献1的方法使来自两个图像的下述特征点关联并且获 得用于使对应特征点候选者重叠的坐标整合参数的分布，该特征点在 相对于作为对应特征点候选者的给定特征点而言的邻近特征点的布置 中彼此相似。在随后处理中使用坐标整合参数所集中到的位置作为与 图像至图像转换参数相当的坐标整合量。

在专利文献2中所述的图像处理设备创建多个分辨率的图像的集 合，并且通过利用为一个图像所创建的不同分辨率图像的集合以及为 另一图像所创建的不同分辨率图像的集合来使两个图像彼此关联。因 此即使当放大或缩小图像中的一个时，要比较的图像也可以彼此关联。

在专利文献3中所述的图案交叉检验设备从对应特征点候选者之 间的关系来估计形状的变化，以便图形形式可以彼此关联而与对象的 形状变化无关。

引用列表：

专利文献1：日本专利No.3002721；

专利文献2：JP－A－2006－065399

专利文献3：JP－A－2002－298141

发明内容

要由本发明解决的技术问题

进一步发展了用于通过参考多个特征点组来使图像等等中的特定 位置彼此关联的技术，如上面作为示例所给出的技术。

描述对上面作为示例所给出的技术的一些问题。

在专利文献1中所述的技术的问题之一是当图像之间的形状变化 非常大或者图像之间的布置部分不同时，要比较的图像无法彼此关联。 这是因为该技术使邻近特征点的布置中彼此相似的特征点关联，提取 关联点作为对应特征点候选者，并且获得用于使对应特征点候选者重 叠的坐标整合量。因此当在图像之间对象的形状变化非常大或者布置 部分且局部不同时，用于使每对对应特征点候选者中的特征点重叠的 坐标整合量因地点而不同。其结果是，坐标整合参数不集中并且无法 获得正确位置。

专利文献1中所述的方法的另一问题是处理过长。专利文献1的方 法首先为来自两个图像的特征点的每成对组合确定是否通过利用邻近 特征点的布置将特征点的成对组合视为对应特征点候选者。为该确定 设定严格标准提高了对应特征点的对应精确度，这使坐标整合参数的 分布集中于正确值，并且从而便于获得正确坐标整合量。

然而，进行该确定严格地需要从邻近特征点的布置获得足够信息， 这反过来需要扩大获得邻近特征点的范围。另一方面，扩大邻近特征 点的范围增大了该确定所使用的信息并且增大了（延长了）该确定所 需的处理量（长度）。另外，对特征点的每成对组合进行对应特征点 的确定，这是非常大的数目。因此执行该确定的次数也非常大并且由 于每个确定会话所需的过长处理时间，总处理时间极其长。另一方面， 使该确定处理简单化以便使该确定加速降低了对应特征点候选者的对 应精确度，这导致检测正确对应特征点（实际上相同的特征点对；仍 包括的特征点对）失败并且在对应特征点候选者中包含许多错误的对 应特征点（实际上不相同的特征点对；要被排除的特征点对）。此后 坐标整合量具有稀疏的分布，这意味着无法获得正确坐标整合量。

专利文献1的方法的又一问题在于获得用于使每对对应特征点候 选者中的特征点重叠的坐标整合量的分布的处理也费时。坐标整合量 是用于使每对对应特征点候选者中的特征点重叠的转换的参数，并且 坐标整合量是在平行移动的情况下通过例如检查横向和纵向每一个上 的各个对的对应特征点候选者的坐标位置差的分布而获得的。该差可 能采用非常宽范围的值并且在该条件下扫描每对对应特征点候选者的 需要延长了处理时间。与确定对应特征点候选者的情况一样，为该特 征设定严格标准进一步延长了处理时间。

在专利文献2中所述的技术具有该技术不能应对形状的极大变化 或者部分不同的布置的相似问题。原因是通过图像放大或缩小无法缓 和由于形状的极大变化或者部分不同的布置所引起的在图像之间的差 别。通过创建多分辨率图像来应对图像放大或缩小的专利文献2的方法 不能应对形状变化或者部分不同的布置，因为图像放大或缩小不能消 除形状的变化或者部分不同的布置。

专利文献3中所述的技术问题在于该技术在估计图像形状变化的 过程中不能处理除弹性连续的形状变化之外的其它形状变化。原因是 根据专利文献3的方法在估计形状变化的过程中认为对象为是弹性膜。 因此该方法不能应对图像之间的布置部分地且不连续地不同的情况。

本发明提供了一种特征点关联系统，该特征点关联系统在即使在 特征点的比较组之间对象的布置部分地不同时也可以以低处理量使特 征点彼此关联。

解决问题的手段

根据本发明的一个实施例的特征点关联系统包括：集合创建单元， 用于接收要比较的多个特征点组，并且通过将就局部转换参数而言彼 此接近的特征点对一起分组成集合来创建多个特征点对集合；集合选 择单元，用于在多个特征点对集合当中选择包含元素多的特征点对集 合；以及对应特征点确定单元，用于从包含在所选择的特征点对集合 之中的特征点对当中确定将被彼此关联的特征点对作为正确对应特征 点以便输出。

本发明的效果

根据本发明的一个实施例，可以提供即使当在特征点的比较组之 间对象的布置部分地不同时也可以以低处理量使特征点彼此关联的特 征点关联系统。

附图说明

图1是用于对根据本发明的第一实施例的配置进行说明的方框图。

图2是用于对根据本发明的第一实施例的操作示例进行说明的流 程图。

图3是用于对根据本发明的第二实施例的配置进行说明的方框图。

图4是用于对根据本发明的第二实施例的操作示例进行说明的流 程图。

图5是用于对根据本发明的示例1的处理目标图像的示例进行说明 的示意图。

图6是用于对图5的特征点之间的位置关系进行说明的说明图。

图7是用于对图6的特征点之间的局部转换参数进行说明的说明 图。

图8是用于对创建特征点对的集合的处理的示例进行说明的说明 图。

图9是用于对特征点对的集合的示例进行说明的说明图。

图10是用于对根据本发明的示例2的要比较的处理目标图像中的 一个进行说明的示意图。

图11是用于对根据本发明的示例2的要比较的其它处理目标图像 进行说明的示意图。

图12是用于对图10的处理目标图像的特征点进行说明的说明图。

图13是用于对图11的处理目标图像的特征点进行说明的说明图。

图14是用于对图12的特征点与图13的特征点之间的位置关系进行 说明的说明图。

图15是用于对根据本发明的示例2的特征点之间的相对位置关系 的示例进行说明的说明图。

图16是用于对根据本发明的示例2的特征点之间的相对位置关系 的另一示例进行说明的说明图。

图17是用于对具体体现本发明的示例进行说明的配置示意图。

具体实施方式

接下来参考附图对本发明的实施例进行详细地说明。

参考图1，本发明的第一实施例的特征点关联系统包括集合创建单 元110、集合选择单元120、以及对应特征点确定单元130。

集合创建单元110接收要比较的多个特征点组并且设定多个特征 点对集合，这多个特征点对集合的每一个是将就局部转换参数而言彼 此接近的特征点对分组在一起的集合。特征点对是由来自要比较的特 征点组之一的一个特征点与来自另一个特征点组的一个特征点所构成 的对。局部转换参数(local conversion parameter)是在构成了特征点对的 特征点之间进行各个转换所需的指示诸如变量的值、函数、代数式等 等这样的图形的参数。换句话说，局部转换参数是用于将成对的两个 特征点中的一个转换成另一特征点的参数。

集合选择单元120从多个创建的集合当中选择包含元素多的集合。

对应特征点确定单元130确定包含在所选择的集合之中的元素当 中的特征点彼此关联的特征点对作为正确对应特征点（分别从要比较 的特征点组取出的并且被认为是相同的对应特征点）。对所确定的特 征点对进行分组以便输出并且适当地使用。

利用该配置，通过分别从例如两个图像收集特征点来为比较而创 建的特征点组被接收，并且来自特征点组之一的特征点与来自另一特 征点组的、被认为是相同的特征点被彼此关联并且被确定为对应特征 点。

所获得的对应特征点被视为用于在各种类型的随后期望处理中指 示两个图像中的相同地点的特征点。

接下来参考图2的流程图和图1对该实施例中的整个处理的示例进 行详细地描述。以下描述采用两个图像的特征点作为示例。

集合创建单元110检查来自两个图像的特征点组的特征点的成对 组合，并且顺序地创建特征点对的集合，使得就局部转换参数而言彼 此接近的特征点对属于同一集合。其处理包括从来自两个图像的特征 点的许多成对组合（特征点对）选择一个成对组合（步骤S101），并 且获得所选择的特征点对的局部转换参数（步骤S102）。确定所获得 的局部转换参数是否接近已创建的特征点对集合中的一个的局部转换 参数（步骤S103），并且当找到这种特征点对集合时，将所选择的特 征点对添加到该特征点对集合（步骤S104）。当不存在符合该标准的 特征点对集合时，创建仅具有所选择的特征点对作为其元素的新特征 点对集合（步骤S105）。重复这些操作步骤，同时检验是否已对给定 范围的特征点对组合完成了该处理（步骤S106）。

集合选择单元120从多个创建的集合当中选择包含元素多的集合 （步骤S107）。

对应特征点确定单元130从所选择的集合的元素当中确定将被视 为来自两个图像的、彼此相对应的特征点的对应特征点（步骤S108）。

因而通过采用用于从下述特征点对集合当中选择对应特征点的例 程可以降低处理量，该特征点对集合将参数彼此接近的特征点对分组 在一起。

接下来参考附图对本发明的第二实施例进行详细地描述。

如在图3和4中所说明的，第二实施例与第一实施例的不同之处在 于集合创建单元的操作。简化或省略对第二实施例的与第一实施例相 似的点的描述。

集合创建单元210从要比较的特征点组中选择特征点的一个成对 组合作为焦点特征点对（图4的步骤S201）。对于所选择的焦点特征点 对获得局部转换参数（步骤S202）。此后，创建下述特征点对集合（步 骤S203），该特征点对集合仅具有已获得了局部转换参数的焦点特征 点对作为其元素。接下来，从要比较的特征点组中的每一个中选择在 当前焦点特征点对附近的特征点，并且创建下述邻近特征点对（步骤 S204），该邻近特征点对是就相对于构成了焦点特征点对的相应特征 点而言的布置来说彼此接近的特征点对。对于所创建的邻近特征点对 获得局部转换参数（步骤S205）。确定邻近特征点对的局部转换参数 是否接近焦点特征点对的局部转换参数（步骤S206），并且当参数彼 此接近时，将邻近特征点对添加到包含焦点特征点对的集合（步骤 S207）。执行这些操作步骤，直至对焦点特征点的邻近特征点的每一 成对组合进行了处理（步骤S208）。

接下来确定包含焦点特征点对的特征点对集合是否具有仍未被选 择作为焦点特征点对的特征点对（步骤S209）。当存在符合该标准的 特征点对时，从未被选择作为焦点特征点对的特征点对当中选择一个 特征点对（步骤S210），并且利用所选择的对作为新焦点特征点对来 执行相同处理（S202至S208）。

在集合不再包含未构成焦点特征点对的特征点的情况下，对特征 点的每一成对组合执行相同处理（S201至S211）。该处理包括选择下 一集合，并且当已创建的集合中的一个包含未被选择作为焦点特征点 对的特征点对时，利用该特征点对作为焦点特征点对来执行相同处理。 在没有集合包含未被选择作为焦点特征点对的特征点对并且存在未选 择的特征点对的情况下，利用该特征点对作为焦点特征点对来执行相 同处理。重复该处理，直至没有留下未被选的特征点对。

此后，集合选择单元220和对应特征点确定单元230从多个创建的 集合当中选择包含元素多的集合（步骤S212），并且从所选择的集合 的元素当中确定对应特征点（步骤S213）。

因而通过采用用于选择一个特征点对作为代表的例程、将参数上 接近所选择的特征点对的特征点对分组在一起、并且从分组的特征点 对的集合中选择对应特征点，借助于特征点与其邻近特征点的相对关 系可以降低处理量并且提高处理精确度。

[示例]

接下来借助于具体示例对实施例的操作进行描述。

对与本发明的第一实施例相对应的本发明的示例进行描述。该示 例是本发明应用于使用两个卫星图像或者航拍图像以创建3D地图的3D 地图创建系统中的特征点关联系统。

该示例讨论了关联下述特征点，该关联特征点是具有不同图像拾 取角度的两个卫星图像或航拍图像中的建筑物等等的拐角，并且由此 创建包括建筑物等等的高度的3D地图。该特征点可以是通过各种通常 已知的方法来提取的，并且在这里已被提取作为特征点组。通过三角 测量的原理，基于特征点之间的关联性来创建3D地图也是众所周知的 技术，并且在这里仅描述了通过特征点的关联的处理，同时省略了对 在该处理之前和之后的处理的描述。

参考用于对特征点组进行说明的示意图给出以下描述。

图5的左半边是从正上方拍摄两个建筑物的图像的示意图。图5的 右半边是从一定角度拍摄两个建筑物的示意图。从每个建筑物提取建 筑物的边沿所交汇的四个角作为特征点，由A至H以及a至h来表示。诸 如“A”和“a”或者“B”和“b”这样的相同字母的大写字母和小写字是在左 边图像和右边图像中同一特征点（同一地点：彼此关联的特征点）。

图6说明了图5的每个特征点的坐标位置。相同特征点具有不同坐 标值，因为建筑物不是从完全相同的位置拍摄的。因此必需获得用于 使两个特征点重叠的平行移动和/或旋转的参数。

此外，由于拍摄建筑物的不同方向，ABCD与EFGH之间的位置关 系以及abcd与efgh之间的位置关系在左边图像和右边图像中不同。换句 话说，无论哪个建筑物用作参考，其它拍摄的建筑物的布置在图像之 间不同，并且对象布置在图像之间部分地不同。因此特征点通过两个 图像的旋转和/或平行移动没有彼此重叠。因此，通过专利文献1的方法 没有实现这两个图像之间的局部关联并且特征点无法适当地彼此关 联。

通过将两个图像之间的旋转视为不必要并且仅对就每个特征点对 的坐标整合量（局部转换参数值）而言的平行移动进行描述可以使这 里所给出的描述简单化。该描述还仅使用附图中的相应建筑物的上部 特征点（ABEF和abef）。

图7说明了用于对来自两个图像的特征点的成对组合的坐标进行 整合的局部转换参数（平行移动量）。在该描述中执行通过将两个图 像的特征点组标绘在同一坐标系统上来获得参数值的处理。替代地， 可以通过对特征点组进行处理使得特征点组重叠，来确定参数值。其 它方法也可以用于确定值。

集合创建单元110检查来自两个图像的特征点的成对组合，并且通 过对特征点对进行分组来创建特征点对的多个分组集合，使得就局部 转换参数而言彼此接近的特征点对属于同一集合。

首先，从来自两个图像的特征点的成对组合当中选择诸如（A，a） 的一个特征点对。接下来对于所选择的特征点对获得局部转换参数。 在（A，a）的情况下，当“A”通过平行移动向右位移12并且向上位移2 时，“A”和“a”重叠。因此（A，a）的局部转换参数是（12，2）。

当所获得的局部转换参数接近已被创建的特征点对集合中的一个 的局部转换参数时，将所选择的特征点对添加到该特征点对集合。在 所获得的参数不接近任何现有集合中的参数的情况下，创建仅包含所 选择的特征点对作为其元素的新特征点对集合。

因为（A，a）是首先选择的特征点对，因此尚未创建特征点对集 合。因此集合创建单元110执行如图8中所说明的、创建具有局部转换 参数（12，2）的集合1作为新特征点对集合，并且关联特征点对（A， a作为集合1的元素）的处理。该处理与经过步骤S105的、从图2的步骤 S101至步骤S106的处理例程相对应。

在处理了一个特征点对之后，选择下一特征点对以重复相同处理。

例如，接下来选择（A，b）。该特征点对的局部转换参数是（15， 2）。在该示例中，用于确定局部转换参数是否彼此接近的标准是局部 转换参数是否完全匹配以便使该描述简单化。因此，因为刚获得的局 部转换参数（15，2）与已创建的集合1的局部转换参数不匹配，因此 集合创建单元110创建具有局部转换参数（15，2）的集合2作为新特征 点对集合，并且将特征点对（A，b）置为集合2的元素。

当接下来选择了（B，b）时，该特征点对的局部转换参数是（12， 2）并且与集合1的局部转换参数相匹配。因此集合创建单元110将（B， b）添加到集合1。该处理与经过步骤S104的、从图2的步骤S101至S106 的处理例程相对应。

类似地，当选择了（E，e）时，该特征点对的局部转换参数是（10， 0）并且与已创建的特征点对集合的集合1和集合2的局部转换参数不 同。因此创建具有局部转换参数（10，0）的集合3作为新特征点对集 合，并且将特征点对（E，e）置为集合3的元素。

类似地，当选择了（F，f）时，该特征点对的局部转换参数是（10， 0）并且与集合3的局部转换参数相匹配。因此将该特征点对（F，f）添 加到集合3。

类似地，当选择了（E，b）时，该特征点对的局部转换参数是（15， 5）并且与已创建的特征点对集合的局部转换参数不同。因此创建具有 局部转换参数（15，5）的集合4作为新特征点对集合，并且将特征点 对（E，b）置为集合4的元素。

集合创建单元110在给定范围的特征点的成对组合之内重复这些 操作步骤。在这里，对特征点的每一成对组合重复该操作步骤。替代 地，可以在首先对每个特征点获得了局部转换参数之后将就局部转换 参数而言彼此接近的特征点对分组中到集合中。

在专利文献1的方法中，信息处理设备对特征点的每一成对组合执 行用于确定就布置而言其邻近特征点是否彼此类似的处理。当一个特 征点的邻近特征点的平均计数例如是十时，需要执行10×10次对邻近特 征点的搜索和比较。对特征点的每一成对组合执行该处理意味着计算 量与特征点的计数成比例地按指数规律增大。另一方面，在该示例中， 仅对特征点的一个成对组合执行一个局部转换参数的计算。仅获得平 行移动量的两个参数的该示例只需计算两次。因而在该示例中对特征 点的每个成对组合所执行的处理非常简单，并且因此实现了高速处理。

一旦创建了特征点对集合，则集合选择单元120从多个创建的集合 当中选择包含元素多的集合。图9说明了所创建的特征点对集合中的一 些。在这里选择集合1和集合3，集合1和集合3是具有元素计数为2或更 大的集合。

当对于特征点的每一成对组合获得了局部转换参数时，形状相似 变化或者相似部分布置不同的特征点的成对组合具有相同参数值，并 且大量单元聚集在正确成对组合的集合中。另一方面，输出各种值作 为不是表示同一地点的特征点的成对组合的局部转换参数。具有该局 部转换参数的集合的元素计数是1或更小。因此通过所包含的元素的计 数是高还是低可以确定集合是否包含相同特征点的成对组合，即正确 特征点对。

利用专利文献1的方法，必需对转换参数可以采用的所有值进行检 查以便获得坐标整合量的分布。在图像大小例如是100像素*100像素的 情况下，平行移动量可以采用的值的一般范围在横向上约是200（从-100 至+100）并且在纵向上约是200（从-100至+100），其整个总计达约 40000。需要从约40000个值找到该分布所集中的位置。通过将某个范 围设定为获得平行移动量的分布的单位可以使搜索范围变窄。例如， 将移动量分成以10为单位并且将+1至+10视为相同值，则将搜索的范围 降低到长20*宽20，总共400。然而，在这种情况下所获得的坐标整合 量的精确度为以10个像素为单位，这相当低。

该示例仅需检查与所创建的特征点对集合的计数一样多的值。特 征点的计数通常低于可能的局部转换参数类型的计数，并且因此该示 例中的选择比专利文献1中的方法更快地完成。

在提取了具有高元素计数的集合之后，对应特征点确定单元130 从所选择的集合的元素当中确定对应特征点。在这里，将包含在所选 择的集合之中的所有特征点对确定为对应特征点对。

该处理后面是借助于所确定的对应特征点对组、基于两个图像的 特征点之间的关联性来创建3D地图的处理。

虽然该示例已经描述了本发明应用于下述3D地图创建系统中的特 征点关联系统，该3D地图创建系统在创建3D地图时使用两个卫星图像 或航拍图像作为要比较的输入图像，但是本发明适用于使用来自两个 图像的特征点的关联性的任何系统。

虽然该示例已经讨论了在获得局部转换参数的值时，图像不需旋 转并且仅考虑平行移动的情况，但是本发明通过在局部转换参数当中 包括旋转而能够应对图像的旋转。类似地，本发明通过添加其它参数 元素（放大/缩小、图案变化等等）作为要在被配对为特征点对的特征 点之间进行转换所需的实数值、函数、矢量等等。利用这种参数，还 可以将屋顶上的广告气球、铁路道口上的横木等等有效地确定为正确 特征点对。本发明中的处理量仍小于相似现有方法，即使当按照这种 方式增加了所使用的参数元素。

用于确定局部转换参数彼此接近的标准在该示例中是完全匹配， 以便使该描述简单化。然而，通常由于错误等等，很少见的是使局部 转换参数完全匹配。通过将该标准设定为“差别在给定范围之内”可以应 对这一点。这种情况下的集合的局部转换参数可以被固定到首先选择 的特征点对的局部转换参数，或者可以是每当将新元素添加到集合时 所计算的、在集合之内的元素的局部转换参数的平均值或者重心。

该示例中的要搜索的特征点的成对组合的范围是特征点的每一成 对组合。当例如预先已知图像的平行移动量的上限时，通过在上限范 围之内搜索，该搜索范围可以变窄。按照这种方式使搜索范围变窄可 以降低处理量。

该示例中的集合选择单元120选择集合的标准是元素计数是2或更 大。在该示例中集合选择单元120可以选择具有给定元素计数或更大的 集合，或者可以使用其它选择标准。例如，集合选择单元120可以按照 元素计数的递减顺序选择给定值的集合，或者可以选择其元素计数等 于或大于所有集合的最高元素计数的给定比例的集合。类似地，可以 选择具有较高元素计数的集合，直至包含在所选择的集合之中的元素 的计数达到与所有集合的元素的总计数的给定比值。替代地，可以用 作选择标准的元素计数可以是基于输入图像的大小或像素计数、在创 建特征点对的集合时所需的计算量等等来确定的。

集合选择单元120还可以将其局部转换参数彼此接近的特征点对 集合组合成一个集合，从而防止多个集合当中的正确对应特征点的分 散以及每个集合中得到的元素计数低。在这种情况下集合选择单元120 可以操作以执行对对应特征点分组的处理，通过该处理，利用现有图 案识别技术通过个体识别来绘制对象。

在该示例中对应特征点确定单元130将包含在所选择的集合之中 的所有特征点对确定为对应特征点对。在用于确定局部转换参数彼此 接近的标准是局部转换参数在给定范围之内彼此具有差别以代替完全 匹配的情况下，所选择的集合中的个别元素的局部转换参数具有各种 值。可以执行使用局部转换参数的这些差别以降低错误对应特征点的 精确度提高处理。例如，可以通过获得集合的平均值并且除去极大地 偏离平均值的特征点对来降低错误对应。在确定要排除的特征点对时 也可以使用集合的重心。

接下来对本发明的示例2进行描述。该示例与本发明的第二实施例 相对应。

该示例是本发明应用于对水果执行个体识别的系统中的特征点关 联系统。

在这里所讨论的系统是对甜瓜的个体识别系统，其目的在于确保 可追溯性以便解决水果生产区域的伪造及其它问题。对培育者所注册 的甜瓜的图案与所出售的甜瓜的图案进行比较，并且当图案匹配时， 确定甜瓜为同一个体。因此通过从甜瓜的图案提取特征点并且使特征 点关联以交叉检验来实现甜瓜的个体识别，并且可以发现生产区域的 伪造等等。在这里已经提取了通过各种通常已知的方法可以被提取的 甜瓜图案的特征点。用于根据特征点之间的关联性来确定对象是否相 同的特征点交叉检验的技术也广为人知，并且在这里仅描述通过特征 点的关联的处理，同时省略对在该处理之前和之后的处理的描述。

图10和11每一个是用于对甜瓜的图案进行说明的示意图。在如图 12和13中所说明的示例中将以线状图案的断点当作特征点。特征点的 特征量不但包括坐标位置而且还包括与特征点相接触的线的方向作为 元素。特征量还可以包括与环境亮度等等的差别作为元素。

对图12和图13执行比较处理，图12说明了图10的甜瓜的特征点， 图13说明了图11的甜瓜的特征点。图14是两个特征点布置图案与作为 中心的甜瓜的茎相重叠的示意图。图10中的甜瓜和图12中的甜瓜位于 不同地点，这导致特征点布置有差别。甜瓜位置的差别例如使“I”与“K” 的相对位置关系之间以及i与k的相对位置关系之间极大地差别，而与 “I”与“i”、“J”与“j”、“K”与“k”每一个是相同特征点这样的事实无关。通 过获得正确特征点对来确定下述两个图像的同一性，在该两个图像之 间图案特征点的布置部分地且局部地不同。

通过利用这两个图像的示例对示例2进行了描述。

集合创建单元210选择来自两个图像的特征点的一个成对组合作 为焦点特征点对（与图4的S201相对应）。在这里，将（I，i）选择作 为焦点特征点对。

接下来对于所选择的焦点特征点对获得局部转换参数，并且创建 仅包括焦点特征点对作为其元素的特征点对集合（与S202和S203相对 应）。在这里，创建具有（I，i）作为元素的集合10。

接下来执行对焦点特征点对的邻近特征点对的处理（与S204至 S208相对应）。首先通过从焦点特征点对的附近单独地选择特征点来 创建邻近特征点对。在这里，“I”的邻近特征点是“J”和“K”，“i”的邻近 特征点“j”和“k”，并且考虑四个邻近特征点对（J，j），（J，k），（K， j），（K，k）。此后，对于所选择的邻近特征点对获得局部转换参数， 并基于所获得的局部转换参数对焦点特征点对的局部转换参数的接近 性，将所获得的局部转换参数添加到包含焦点特征点对作为元素的特 征点对集合。

图15说明了邻近特征点相对于焦点特征点对（I，i）的相对位置关 系。在邻近特征点对（J，j），（J，k），（K，j），（K，k）当中， （J，j）具有接近的相对位置关系，并且在这里将其添加到集合10。

接下来，在包含焦点特征点对的集合包含仍未被选择作为焦点特 征点对的特征点对的情况下，将未被选择作为焦点特征点对的特征点 对中的一个选择作为新焦点特征点对，并且执行对邻近特征点对的处 理。

例如，包含焦点特征点对（I，i）的集合10包含未被选择作为焦点 特征点对的（J，j），并且利用（J，j)作为焦点特征点对来执行对邻近 特征点对的处理。

在这里，“J”的邻近特征点是“I”和“K”，并且“j”的邻近特征点是“i” 和“k”。虽然（J，j）具有四个邻近特征点对：（I，i），（I，k），（K， i）和（K，k），但是（I，i）已经属于集合10，并且因此考虑仍未属 于任何集合的（I，k），（K，i）和（K，k）。

图16说明了相对于焦点特征点对（J，j）而言邻近特征点的相对位 置关系。在所搜索的邻近特征点对，即（I，k），（K，i）和（K，k） 当中，（K，k）具有接近的相对位置关系并且将其添加到集合10。

接下来选择属于集合10但是仍未被选择作为焦点特征点对的特征 点对（K，k）作为焦点特征点对，以执行对邻近特征点对的处理。集 合创建单元210按照这种方式重复该操作，直至集合10不再包含未被选 择作为焦点特征点对的特征点对。

当焦点集合不再包含未被选择作为焦点特征点对的特征点对时， 选择下一集合。

按照这种方式，当存在仍未选择的特征点对时，利用该特征点对 作为新焦点特征点来执行相同处理。重复上述处理以直至对每个特征 点对进行了处理。

集合选择单元220和对应特征点确定单元230的随后操作与示例1 中相同，并且省略其描述。

该示例中的特征点的特征量使用除了位置之外的方向作为参数元 素。即使在目标特征点不具有方向的情况下，例如当柑子或梨的点图 案被用作特征点时，通过将诸如朝着最接近所讨论的特征点的特征点 的方向用作所讨论的特征点所具有的方向的方法，或者通过确定诸如 柑子或梨的茎的参考点并且使用朝着参考点的方向的方法的任意方 法，来对特征点给出方向特征量。

该示例通过采用甜瓜作为示例描述了本发明应用于个体识别系统 中的特征点关联系统。然而，本发明还适合于鲜鱼等等的个体识别系 统，该个体识别系统是针对诸如鱼的、其轮廓和图案方向性可以被使 用的对象并且相对于轮廓而言的图案方向性用作特征点的特征量。本 发明还可应用于将脊纹中断或分叉关联作为交叉检验的特征点的指纹 或掌纹认证系统、通过利用字符的端点和高曲率点来识别字符的字符 识别系统、以及需要使来自两个图像的特征点彼此关联的任何其它系 统。

可展开的手指和手掌部分地伸展/收缩。因此当本发明应用于指纹 或掌纹认证系统时，能够应对局部转换参数部分不同的情况的本发明 的特征很有效。

类似地，果实及其它易腐品的颜色和图案随时间而变。因此当本 发明应用于下述个体识别系统时，能够应对局部转换参数部分不同的 情况的本发明的特征很有效，该个体识别系统吸收了由于随识别目标 的时间的变化所造成的从一个地点到另一地点的变化量的差。在这种 情况下，基于图像获得的日期/时间、识别目标的传送信息等等，可调 节特征点对集合的提取中参数之间的接近/远离。

此外在字符识别中，字符之间的间隔或者一个汉字内的左手偏旁 部首与右手偏旁部首之间的间隔有时变化，并且因此当本发明应用于 字符识别系统时能够应对局部转换参数部分不同的情况的本发明的特 征很有效。

接下来对示例2的效果进行描述。示例1在确定特征点对属于哪个 集合时使用局部转换参数的绝对差。因此示例1无法应对诸如在该示例 中给定为示例的甜瓜的球状物上的特征点随着球状物的转动而逐渐变 化的情况。例如，利用示例1的方法,几乎不能将图14中的其间的绝对距 离相当大的特征点K和特征点k识别为属于与特征点对（I，i）相同集合 的特征点对。在该示例中，如在图15和16中所说明的使用相对于相邻 特征点对而言的相对位置关系的情况下，通过确定相对于比（I，i）更 靠近（K，k）的（J，j）而言的相对位置关系，可以将（K，k）放置 在与（J，j）相同的集合10中，即与（I，j）相同的集合10。

因而示例2还能够应对图像之内的位置关系等等部分地且逐渐地 变化这样的情况。

可以通过硬件和软件的组合实现特征点关联系统的部件。在硬件 和软件相结合的模式中，在RAM上开发特征点关联程序，并且部件通 过基于该程序对控制单元（CPU）等等的硬件进行操作而起各种装置的 作用。还可以将该程序固定地记录到要分发的记录介质上。经由电缆、 无线连接、或者记录介质本身将记录在记录介质上的程序读取到存储 器上，并且运行控制单元等等。记录介质的示例包括光盘、磁盘、半 导体存储器设备、以及硬盘。

如在图17中所例示的，特征点关联系统可以建立在单个计算机或 服务器上，并且还可以被建立为云系统。

为了改述该实施例，基于在RAM上开发的特征点关联程序，通过 使控制单元作为集合创建装置、集合选择装置、以及对应特征点确定 装置进行操作，可以实现作为特征点关联系统进行操作的信息处理设 备。

在建立下述个体识别系统的过程中可以使用该特征点关联系统， 在该个体识别系统中，单独地从两个输入图像提取特征点作为特征点 组，使包含在所提取的特征点组中的一个之中的特征点与包含在另一 个提取的特征点组之中的特征点彼此成对以被识别为是特征点对，获 得要在构成了所识别的特征点对的特征点之间进行转换所需的参数作 为局部转换参数，对在给定规则之下被认为就所获得的局部转换参数 而言彼此接近的特征点对进行分组以创建多个特征点对集合，从所创 建的多个特征点对集合当中选择在给定规则之下被认为包含元素多的 特征点对集合，从包含在所选择的特征点对集合中的特征点对当中选 择具有在给定规则之下被认为仍包括特征点对的局部转换参数的特征 点对作为正确对应特征点，借助于所选择的对应特征点对执行特征点 交叉检验处理，并且确定包括在输入两个图像之中的个体的同一性。 在建立执行3D地图创建处理以创建包括在两个输入图像之中的对象的 3D地图的3D地图创建系统中也可以使用该特征点关联系统。

除了图像之间的关联性之外，在使图像与特征点组的数据关联的 过程中可以使用特征点关联系统。特征点组的数据在这里是通过使特 定空间中的特征点之间的位置关系变成信息所获得的数据。

通过按照这种方式对图像与特征点组的数据进行比较，可以以小 处理量使实际拍摄的卫星图像、航拍图像等等与现有地图数据关联。 例如，将该特征点关联系统并入到拍摄位置识别系统中可以使识别系 统从输入图像提取图像的对象的位置和名称、对象的有关数据、3D数 据等等。

当使图像与视频、视频与另一视频、视频与特征点组的数据等等 实时关联时，也可以使用该特征点关联系统。

通过按照这种方式使来自不同特征点组的特征点实时关联，可以 以小处理量使利用照相机等等所拍摄的视频与地图数据等等关联。这 些可以在例如汽车导航系统和增强现实（AR）系统中使用。从而以小 处理量实现了诸如在照相机所拍摄的视频上重叠写入并且输出注解的 处理。在视频－视频比较的情况下，在识别版权拥有者等等的过程中 可以使用该系统。在诸如汽车导航系统或AR系统中的实时处理的情况 下，通过执行下述处理可以降低整个处理量，该处理涉及从照相机拍 摄的视频新提取特征点、使所提取的特征点与包含在要比较的数据（特 征点组）之中的特征点成对、将成对的特征点识别为特征点对、对于 特征点对获得局部转换参数、找到接近特征点对的局部转换参数的特 征点对集合的已获得的局部转换参数中的一个、并且将该特征点对添 加到具有接近的局部转换参数的特征点对集合。可以基于与在新提取 的特征点附近的特征点对的关系来限制该情况下的提取范围。

汽车导航系统或AR系统可以对于实时处理图像的每个帧，使来自 不同特征点组的特征点关联，或者可以使在帧变稀疏的同时执行该处 理。本发明还可以用于与分离给定间隔的一个帧和另一帧关联地并且 利用特定的变化量使来自不同特征点组的特征点关联，并且介于帧之 间的帧的特征点与较接近在关联中所使用的帧中的一个的特征点关 联。在执行帧间预测的MPEG或其它视频形式的情况下，不执行帧间预 测的I帧或其它帧可以用于将来自不同特征点组的就局部转换参数而言 彼此接近的特征点对分组到一起并且对分组的特征点对进行处理，而 在对执行帧间预测的帧的帧间预测中所计算的值可以用于校正对从不 执行帧间预测的帧所获得的对应特征点的预测。

用这种方式，可以以小处理量获得诸如对象的位置以及对象的变 化（例如靠边驾驶的车辆）。在吸收从视频所提取的实时处理的识别 目标的特征点之间的由于天气、光源等等所引起的差别方面，能够应 对如在实施例中所述的局部转换参数部分不同的情况的本发明的特征 也是有效的。可以通过集合创建装置来执行所述的变疏及其它类型的 处理。可以通过对应特征点确定单元来处理比较帧之间的帧关联性。

如已描述的，本发明所应用于的特征点关联系统对于布置部分不 同的两个图像等等也能够以小处理量使特征点关联。

也就是说，根据本发明的一个实施例，可以提供即使当诸如两个 图像的特征点的比较组之间的对象的布置部分不同，也能够以低处理 量使特征点彼此关联的特征点关联系统。

本发明的具体配置不局限于上述实施例和示例，并且不脱离本发 明的精神的修改包含在本发明中。本发明还包括部件的适当划分和组 合。

上述实施例的一些或全部还可以如下表达。以下说明决不是对本 发明做出限制。

[补充说明1]

一种特征点关联系统，包括：

集合创建单元，用于接收要比较的多个特征点组，并且通过将就 局部转换参数而言彼此接近的特征点对一起分组到集合中来创建多个 特征点对集合；

集合选择单元，用于从所述多个特征点对集合当中选择包含元素 多的特征点对集合；以及

对应特征点确定单元，用于从包含在所选择的特征点对集合中的 特征点对当中确定要被彼此关联的特征点对作为正确对应特征点，以 便输入。

[补充说明2]

根据先前说明的特征点关联系统，其中，所述集合创建单元参考 给定特征点对的局部转换参数以及在所述给定特征点对附近的邻近特 征点对的局部转换参数，以由此创建将就局部转换参数而言彼此接近 的特征点对分组在一起的特征点对集合。

[补充说明3]

根据先前说明的特征点关联系统，其中，当创建集合时，为了确 定是否将特定特征点对添加到已创建的集合，所述集合创建单元通过 基于相对于包含在现有集合之中的特征点对而言的相对位置关系，选 择属于搜索范围的特征点作为邻近特征点，来创建所述特定特征点对 的邻近特征点对。

[补充说明4]

根据先前说明中的任何一个的特征点关联系统，其中，所述集合 创建单元使用在被配对为特征点对的特征点之间的转换所需的值作为 所述局部转换参数，来创建用于将就参数而言彼此接近的特征点对分 组在一起的特征点对集合。

[补充说明5]

根据先前说明的特征点关联系统，其中，所述局部转换参数包括 局部转换所需的多个参数元素，并且所述集合创建单元基于所述多个 参数元素的每一个的近似性来创建用于将特征点对分组在一起的特征 点对集合。

[补充说明6]

根据先前说明中的任何一个的特征点关联系统，其中，所述集合 创建单元通过将用于确定局部转换参数接近已创建集合的局部转换参 数的标准设定为“局部转换参数完全匹配”或者“局部转换参数之间的差 在给定范围之内”来执行将特征点对分组的处理，并且所述标准使用首 先选择的元素的参数、在包含在集合中的元素当中取平均值的参数、 以及包含在集合中的元素的重心的参数。

[补充说明7]

根据先前说明中的任何一个的特征点关联系统，其中，在当将特 征点对分组时使用除了“完全匹配”之外的标准作为将局部转换参数认 为彼此接近的范围的集合中，所述对应特征点确定单元对照首先选择 的元素的参数、在包含在集合中的元素当中取平均值的参数、以及包 含在集合之中的元素的重心的参数中的任何一个，对作为元素包含在 由所述集合选择单元所选择的特征点对集合中的每个特征点对的局部 转换参数进行比较，并且作为错误对应特征点从关联排除局部转换参 数极大地偏离的特征点对。

[补充说明8]

一种个体识别系统，所述个体识别系统配置成：

从两个输入图像分别提取特征点作为特征点组；

使包含在所提取的特征点组中的一个之中的特征点与包含在所提 取的特征点组的另一个之中的特征点彼此成对，并且将成对的特征点 识别为特征点对，获得在构成所识别的特征点对的特征点之间进行转 换所需的参数作为局部转换参数，并且通过将在给定规则之下就所获 得的局部转换参数而言被认为彼此接近的特征点分组在一起来创建多 个特征点对集合；

从所创建的所述多个特征点对集合当中选择在给定规则之下被认 为包含高元素计数的特征点对集合；

从包含在所选择的特征点对集合中的特征点对当中选择具有在给 定规则之下被认为仍被包括的特征点对的局部转换参数的特征点对作 为正确对应特征点；并且

通过借助于所选择的对应特征点对执行特征点交叉检验处理来确 定包括在两个输入图像之中的个体的同一性。

[补充说明9]

一种特征点关联方法，包括：

集合创建步骤，用于接收要比较的多个特征点组，并且通过将就 局部转换参数而言彼此接近的特征点对一起分组到集合中来创建多个 特征点对集合；

集合选择步骤，用于从所述多个特征点对集合当中选择包含元素 多的特征点对集合；以及

对应特征点确定步骤，用于从包含在所选择的特征点对集合中的 特征点对当中确定要被彼此关联的特征点对作为正确对应特征点，以 便输出。

[补充说明10]

根据先前说明的特征点关联方法，其中，所述集合创建步骤包括 参考给定特征点对的局部转换参数以及在所述给定特征点对附近的邻 近特征点对的局部转换参数，以由此创建将就局部转换参数而言彼此 接近的特征点对分组在一起的特征点对集合。

[补充说明11]

根据先前说明的特征点关联方法，其中，所述集合创建步骤包括， 当创建集合时，为了确定是否将特定特征点对添加到已创建的集合， 通过基于相对于包含在现有集合之中的特征点对而言的相对位置关 系，选择属于搜索范围的特征点作为邻近特征点，来创建所述特定特 征点对的邻近特征点对。

[补充说明12]

根据先前说明中的任何一个的特征点关联方法，其中，所述集合 创建步骤包括使用在被配对为特征点对的特征点之间的转换所需的值 作为所述局部转换参数，来创建用于将就参数而言彼此接近的特征点 对分组在一起的特征点对集合。

[补充说明13]

根据先前说明的特征点关联方法，其中，所述局部转换参数包括 局部转换所需的多个参数元素，并且所述集合创建步骤包括基于所述 多个参数元素的每一个的近似性来创建用于将特征点对分组在一起的 特征点对集合。

[补充说明14]

根据先前说明中的任何一个的特征点关联方法，其中，所述集合 创建步骤包括通过将用于确定局部转换参数接近已创建集合的局部转 换参数的标准设定为“局部转换参数完全匹配”或者“局部转换参数之间 的差在给定范围之内”来执行将特征点对分组的处理，并且所述标准使 用首先选择的元素的参数、在包含在集合中的元素当中取平均值的参 数、以及包含在集合中的元素的重心的参数。

[补充说明15]

根据先前说明中的任何一个的特征点关联方法，其中，所述对应 特征点确定步骤包括，在当将特征点对分组时使用除了“完全匹配”之外 的标准作为将局部转换参数认为彼此接近的范围的集合中，对照首先 选择的元素的参数、在包含在集合中的元素当中取平均值的参数、以 及包含在集合之中的元素的重心的参数中的任何一个，对作为元素包 含在所述集合选择步骤中选择的特征点对集合中的每个特征点对的局 部转换参数进行比较，并且作为错误对应特征点从关联排除局部转换 参数极大地偏离的特征点对。

[补充说明16]

一种特征点关联程序，所述特征点关联程序用于控制信息处理设 备的控制单元，以便所述控制单元操作为：

集合创建单元，用于通过将就局部转换参数而言彼此接近的特征 点对分组在一起来创建多个特征点对集合；

集合选择单元，用于从所述多个特征点对集合当中选择包含元素 多的特征点对集合；以及

对应特征点确定单元，用于从包含在所选择的特征点对集合中的 特征点对当中确定要被彼此关联的特征点对作为正确对应特征点，以 便输出。

[补充说明17]

根据先前说明的特征点关联程序，其中，所述集合创建单元被所 述特征点关联程序控制，以便参考给定特征点对的局部转换参数以及 在所述给定特征点对附近的邻近特征点对的局部转换参数，以由此创 建将就局部转换参数而言彼此接近的特征点对分组在一起的特征点对 集合。

[补充说明18]

根据先前说明的特征点关联程序，其中，所述集合创建单元被所 述特征点关联程序控制，以便当创建集合时，为了确定是否将特定特 征点对添加到已创建的集合，通过基于相对于包含在现有集合之中的 特征点对而言的相对位置关系，选择属于搜索范围的特征点作为邻近 特征点，来创建所述特定特征点对的邻近特征点对。

[补充说明19]

根据先前说明中的任何一个的特征点关联程序，其中，所述集合 创建单元被所述特征点关联程序控制，以便使用在被配对为特征点对 的特征点之间的转换所需的值作为局部转换参数，来创建用于将就参 数而言彼此接近的特征点对分组在一起的特征点对集合。

[补充说明20]

根据先前说明的特征点关联程序，其中，所述局部转换参数包括 局部转换所需的多个参数元素，并且所述集合创建单元被所述特征点 关联程序控制，以便基于所述多个参数元素的每一个的近似性来创建 用于将特征点对分组在一起的特征点对集合。

[补充说明21]

根据先前说明中的任何一个的特征点关联程序，其中，所述集合 创建单元被所述特征点关联程序控制，以便通过将用于确定局部转换 参数接近已创建集合的局部转换参数的标准设定为“局部转换参数完 全匹配”或者“局部转换参数之间的差在给定范围之内”来执行将特征点 对分组的处理，并且所述标准使用首先选择的元素的参数、在包含在 集合中的元素当中取平均值的参数、以及包含在集合中的元素的重心 的参数。

[补充说明22]

根据先前说明的任何一个的特征点关联程序，其中，所述对应特 征点确定单元被所述特征点关联程序控制，以便在当将特征点对分组 时使用除了“完全匹配”之外的标准作为将局部转换参数认为彼此接近 的范围的集合中，对照首先选择的元素的参数、在包含在集合中的元 素当中取平均值的参数、以及包含在集合之中的元素的重心的参数中 的任何一个，对作为元素包含在由所述集合选择单元所选择的特征点 对集合中的每个特征点对的局部转换参数进行比较，并且作为错误对 应特征点从关联排除局部转换参数极大地偏离的特征点对。

[补充说明23]

根据先前说明中的一个的特征点关联程序，其中，所述集合创建 单元被所述特征点关联程序控制，以便：

接收从照相机实时获得的视频或图像的帧所提取的一组特征点， 使包括在所提取的帧特征点的组中的特征点与包含在准备的特征点组 中的特征点成对，将成对的特征点识别为特征点对，获得在构成所识 别的特征点对的特征点之间的转换所需的参数作为局部转换参数，将 在给定规则之下就所获得的局部转换参数而言被认为彼此接近的特征 点对分组在一起，并且由所分组的特征点对创建多个特征点对集合； 并且

基于所接收到的帧特征点组，执行特征点交叉检验处理以输出在 来自照相机的视频上覆盖写入的注释。

[补充说明24]

根据先前说明中的一个的特征点关联程序，其中，所述集合创建 单元被所述特征点关联程序控制，以便使帧特征点组稀疏。

[补充说明25]

根据先前说明中的一个的特征点关联程序，其中，所述集合创建 单元被所述特征点关联程序控制，以便通过与给定间隔的每个帧和/或 每个特定量的变化关联地，将就局部转换参数而言彼此接近的特征点 对分组在一起，来创建多个特征点。

[补充说明26]

根据先前说明中的一个的特征点关联程序，其中，所述集合创建 单元被所述特征点关联程序控制，以便使在特征点集合的产生过程中 未使用的帧的特征点与更接近在关联中所使用的帧中的一个的特征点 关联。

[补充说明27]

根据先前说明中的一个的特征点关联程序，其中，所述集合创建 单元被所述特征点关联程序控制，以便基于所讨论的帧与在关联中所 使用的帧之间的关系，以及在关联中所使用的帧的特征点对，来对于 在特征点集合的产生过程中未使用的帧的特征点计算要比较的特征点 组中的、与所讨论的帧的特征点相对应的对应特征点或对应位置。

[补充说明28]

一种在其上记录有先前说明中的一个的特征点关联程序的记录介 质。

本发明可已应用于需要使来自两个图像等等的特征点彼此关联的 任何系统。

该申请要求于2011年8月16日提交的日本专利申请No.2011－ 178029的优先权，将其整个公开并入到这里。

参考符号列表

110，210集合创建单元（集合创建装置）

120，220集合选择单元（集合选择装置）

130，230对应特征点确定单元（对应特征点确定装置）