图形对照设备,图形对照方法以及图像对照程序

摘要

图形对照设备包括在特征点中的特征点对,这些特征点是表示作为要对比的图形的检验目标图形与作为参考图形的样本图形的相应特征的部分,特征点对在所述检验目标图形与所述的样本图形中互相对应,以及相似性确定部分,用于根据特征点对形成部分形成的特征点的对应性计算检验目标图形与样本图形之间的相似性,其中相似性确定部分根据任意图形与样本图形之间的特征点对的数量不少于先前由特征点对形成部分获得的检验目标图形与样本图形之间的特征点对的数量的可能性计算检验目标图形与样本图形之间的相似性。

说明书

技术领域

本发明涉及图像数据的对照。特别是，本发明涉及一种用于识别诸如指纹，掌纹以及字符之类的线条图形的图形对照设备，图形对照方法以及图形对照程序。

背景技术

作为传统的用于识别诸如指纹，掌纹或字符之类的线条图形的图形对照设备，日本专利申请特许公开(下文中称为JP-A)No.56-024675，59-000778，59-024384，60-029875，03-266187，04-033065，以及04-043470中描述了利用诸如线条的端点或者分支点之类的特征点获得相应的特征点并对它们进行对照的方法。

但是，上面提到的传统技术存在着下述缺点。

JP-A No.56-024675，59-000778，59-024384，60-029875，04-033065，以及04-043470中描述的方法是一种检测相应的特征点并基于相应特征点的数量进行识别的方法。由于这一原因，在特征点密集的地方形成特征点对是很容易的，而存在的一个问题就是如果在目标和/或模式中的特征点具有不同的密度，精确对照其结果是不可能的。

根据JP-A No.03-266187中描述的方法，那些以大量特征点与一个特定特征点相邻的那些特征点对于处理特征点的密度较高的的情况是无效的。但是，根据这种方法，如果仅存在特征点的密度较高的位置，则存在着不能对其进行识别的问题。

发明内容

本发明的一个目的就是提供一种图形对照设备，图像对照方法以及图形对照程序，能够解决上述传统技术的缺陷并且能够不依赖于输入图像的特征点的密度而准确地识别输入的图形。

根据本发明，提供了一种用于利用样本图形对照检验目标图形的图形对照设备，包括：特征点对形成装置，用于形成特征点对，每一特征点对由检验目标图形中的特征点和彼此相对应的样本图形中的特征点构成，从表示检验目标图形的特征的点中选择由每个特征点对组成的检验目标图形中的特征点，从表示样本图形的特征的点中选择由每个特征点对组成的样本图形中的特征点；可能性计算装置，用于计算任意图形与样本图形之间的特征点对的数量不小于检验目标图形与样本图形之间的特征点对的数量的可能性；相似性计算装置，用于根据可能性计算检验目标图形与样本图形之间的相似性。

图形对照设备可以进一步包括：特征量计算装置，用于计算检验目标图形与样本图形之间的特征量；以及一致性计算装置，用于根据检验目标图形与样本图形之间的特征点对的数量以及检验目标图形与样本图形之间的特征量计算检验目标图形与样本图形之间的特征点对的一致性，其中可能性计算装置计算任意图形与样本图形之间的一致性不小于检验目标图形与样本图形之间的一致性的可能性，而不计算任意图形与样本图形之间的特征点对的数量不小于检验目标图形与样本图形之间的特征点对的数量的可能性。

图形对照设备可以进一步包括：第二特征量计算装置，用于计算样本图形和与样本图形相同的图形之间的特征量；以及一致性计算装置，用于根据样本图形和与样本图形相同的图形之间的特征点对的数量以及样本目标图形和与样本图形相同的图形之间的特征量来计算模式图形和与样本图形相同的图形之间的特征点对的一致性，其中相似性计算装置用于根据任意图形与样本图形之间的一致性不少于检验目标图形与样本图形之间的一致性的可能性以及样本图形和与样本图形相同的图形之间的一致性少于检验目标图形与样本图形之间的一致性的可能性来计算检验目标图形与样本图形之间的相似性。

图形对照设备可以进一步包括：特征量计算装置，用于计算检验目标图形与样本图形之间的特征点对的特征量的差；用于将检验目标图形与样本图形之间的特征点对的数量减少到数量差少于预定值的特征点对的数量的装置；用于通过去除数量差不小于预定值的特征点对来减少任意图形与样本图形之间的特征点对的数量的装置，其中可能性计算装置计算任意图形与样本图形之间的特征点对的减少数量不少于检验目标图形与样本图形之间的特征点对的减少数量的可能性，而不计算任意图形与样本图形之间的特征点对的数量不少于检验目标图形与样本图形之间的特征点对的数量的可能性。

在图形对照装置中，数量差可以是构成特征点对的特征点之间的距离。

在图形对照装置中，至少可用指纹和掌纹中的一种作为检验目标图形和样本图形。

根据本发明，利用被假定输入的任意图形与样本图形之间的特征点对是一致的可能性来计算检验目标图形与样本图形之间的相似性。就是说，如果在检验目标图形与样本图形之间存在着许多相对应的特征点对，并且当用任意图形作为目标时这种对应发生的可能性非常低，则确定检验目标图形与样本图形相同的可能性非常大。因此，根据特定的标准能够正确地识别检验目标图形和样本图形，而不受检验目标图形与样本图形的特征点对的密度的影响。

附图说明

图1是表示根据本发明的第一实施例的图形对照设备的结构的方框图；

图2是用于说明根据第一实施例进行图形对照过程的流程图；

图3是用于说明根据第一实施例进行相似性确定过程的一个实施例的流程图；

图4是表示根据本发明的第二实施例的图形对照设备的结构方框图；

图5是用于说明在第二实施例中进行图形对照过程的流程图；

图6是用于说明根据第二实施例进行相似性确定过程的一个实施例的流程图；

图7是表示根据本发明第三实施例的图形对照设备的结构方框图；

图8是用于说明根据第三实施例进行图形对照过程的流程图；

图9是用于说明根据第三实施例进行相似性确定过程的一个实施例的流程图；和

图10是表示配备有记录根据本发明的图形对照程序的记录媒体的一个实施例的结构方框图。

具体实施方式

下面将参照附图详细描述本发明的实施例。

图1是表示根据本发明第一实施例的图形对照设备的结构方框图。

参照图1，在本实施例中的图形对照设备包括一个检验目标图形输入部分20，其输入有关检验目标图形的数据，它是将被对照的图形，一个样本图形输入部分30，其输入有关样本图形数据，它是一个参考图形，一个数据处理部分10，计算检验目标图形与样本图形之间的相似性，以及输出处理结果的输出部分40。

数据处理部分10包括将检验目标图形的特征点与样本图形的对应特征点配对在一起的特征点对形成部分11，以及根据特征点对计算检验目标图形与样本图形之间的相似性的相似性确定部分12。下面描述数据处理部分10的相应组成部件的操作要点。

特征点对形成部分11对照从检验目标图形输入部分20输入的检验目标图形的特征点与从样本图形输入部分30输入的样本图形的特征点，并且找出对应的特征点。两个图形中的一对对应的特征点将被称为特征点对。

相似性确定部分12根据任意图形与样本图形之间的特征点对的数量不少于先前通过特征点对形成部分11获得的检验目标图形与样本图形之间的特征点对的数量的可能性来计算检验目标图形与样本图形之间的相似性。就是说，相似确定装置12计算从假定要输入的所有图形中任意选择的任意图形的特征点数量不少于检验目标图形与样本图形之间的特征点对的数量的可能性，这些假定要输入的图形在特征点对形成部分11基于其确定成对数的阈值内与样本图形的特征点相一致。基于这一点来计算相似性。

输出部分40输出计算的相似性。

参照附图详细描述该实施例的操作。

图2是用于说明根据第一实施例的图形对照过程的流程图。

首先，将有关检验目标图形的特征点信息输入到检验目标图形输入部分20，并且将作为要对照的图形的样本图形的特征点信息输入到样本图形输入部分30(步骤201)。

为了输入相应的图形，可以使用例如有关输入表明相应图形的特征并被预先提取的特征点的信息的方法，或者输入有关相应图形的图像数据，在检验目标图形输入部分20以及样本图形输入部分30中提取有关特征点的信息，并且将其发送到数据处理部分10的方法。

如果将其应用到例如字符识别，可以利用将有关将被检验以便识别字符的图像数据输入到检验目标图形输入单元20并且将寄存在字典中的字符数据输入到样本图形输入部分30的方法。

如果将其应当到例如指纹识别，掌纹识别，可以将有关将被检验以便识别指纹或者掌纹的主人的指纹或掌纹的图像数据输入到检验目标图形输入部分20并且寄存在指纹数据库或指纹数据库中的指纹数据或掌纹数据输入到样本图形输入部分30。

可以看到，检验目标图形输入部分20可以输入有关预先提取的检验目标图形的特征点信息或者可以输入检验目标图形本身并且在检验目标图形输入部分20提取特征点信息。同样，样本图形输入部分30可以输入有关预先提取的样本图形的特征点信息，或者可以输入样本图形本身并且在样本图形输入部分20提取特征点信息。

在此，检验目标图形和样本图形的特征点可以是线段断开的点(端点)，分支点(branch points)，交叉点(crossings)或者类似的点。此外，作为表示相应特征点的特征度的数据的特征量，可以使用诸如特征点的位置，切线的方向等之类的数据。另外，可以将有关连接线与邻近线的曲率值的信息，邻近特征点的排列，邻近特征点之间交叉线的数量等信息加到特征量中。

特征点对形成部分11对照从检验目标图形输入部分20输入的检验目标图形的特征点信息与从样本图形输入部分30输入的样本图形的特征点信息，选择将被认为是相同的特征点，并且形成特征点对数据(步骤202)。

通过在检验目标图形重叠在样本图形上时计算特征点之间的位置差，判断相应特征点之间的特征量的差是否在预定阈值内，使用有关位置差或相应特征量的差的数据作为预定函数的变量计算用于估计特征点的相似度的值，特征点对形成部分11可以执行关于其是否是相同特征点的判断处理。

相似性判断装置12根据任意图形与样本图形之间的特征点对的数量不少于先前由特征点对形成部分11获得的检验目标图形与样本图形之间的特征点对的数量的可能性来计算检验目标图形与样本图形之间的相似性(步骤203)。图3是用于说明在步骤203执行的本实施例中的相似性判断过程的一个实施例的流程图。参照图3，查阅有关检验目标图形的特征点的数量(步骤203-1)。接下来，计算相对于任意图形(假定是要输入的任意图形)的特征点对的数量不少于相对于检验目标图形的特征点对的数量的可能性(步骤203-2)。根据该可能性计算相似性(步骤203-3)。在此，在步骤203-2中计算出来的可能性，即，与在确定它们成对的阈值内的样本图形的特征点一致的特征点的数量不少于在特征点形成部分11中形成的特征点对的数量的可能性可以用下面的方式计算。

在该例子中，只使用特征点中的位置差被用作形成特征点对的标准。作为例子，描述当检验目标图形叠加在样本图形上并且它们之间的位置差不大于预定长度E时确定特征点对的方法。此外，假定样本图形的区域是S，检验目标图形具有N₁个特征点，样本图形具有N₂个特征点并且它们之中的M个特征点形成了特征点对。现将其中任意排列N₁个特征点的整个图形被看作是假定要输入的整个检验目标图形。

从特征点任意排列的图形中任意选择的图形的特定特征点的位置等于当它们任意排列时的位置。由于这一原因，就通过下面的等式1获得在样本图形中任意排列的特定特征点相对于样本图形的特征点中的特定特征点具有不大于误差E的可能性P₀ $>>>P>0>>=>>>\pi >>E>2>>>S>>->->->>(>1>)>>>s>$

因此，当样本图形中的特征点足够疏，并且与样本图形中的每个特征点具有不大于距离E的重叠区域小到可以忽略的时候，可以通过下面的等式2获得特定特征点相对于样本图形的N₂个特征点之一具有不大于误差E的可能性。 $>>>P>1>>=>>N>2>>·>>>\pi >>E>2>>>S>>->->->>(>2>)>>>s>$

此外，当N₁足够小并且不少于两个任意排列的特征点与样本图形的相同特征点具有不大于距离E的距离的可能性小的可以忽略的时候，可以通过下面的等式3获得在样本图形中任意排列的N₁个特征点中的M₁个特征点与样本图形的特征点具有不大于距离E的可能性P₂(M₁)。 $>>>P>2>>>(>>M>1>>)>>>=>>N>1>>>>C>>M>1>>>·sup>>P>1>>M>1>sup>>·>>>(>1>->>P>1>>·>>N>1>>)>>>(>>N>1>>->>M>1>>)>>>->->->>(>3>)>>>s>$

因此，如果我们提供表示当N₁个特征点在样本图形中任意排列时不少于M个特征点与样本图形的特征点不大于距离E的可能性，即当检验目标图形的N₁个特征点在样本图形中任意排列时，在检验目标图形与样本图形之间存在不少于M个特征点对的可能性的P(M)，值则可以通过下面的等式4获得P(M)。 $>>P>>(>M>)>>=>>\Sigma >>i>=>M>>>N>1>>>>P>2>>>(>i>)>>->->->>(>4>)>>>s>$

相似性判断部分12可以使用1-P(M)作为检验目标图形与样本图形之间的相似性的值，或者使用值P(M)的值作为表示相似性的预定等式的变量。此外，可以执行当样本图形侧被任意排列时使用与检验目标图形一致性的可能性的方法，或者使用利用一个值和P(M)作为预定等式的变量获得的值的方法。

此外，通过相似性确定部分12计算的相似性不局限于由上述实施例中描述的方法计算的值。如果存在另一个值可用于相似性的计算，利用P(M)获得一个值并且将所获得的值作为预定等式的变量。

当由于样本图形中的特征点足够疏或者N₁非常小而不能建立用于得到获得P(M)的等式的每个假设时，则可根据该条件修改等式。此外，当使用除了位置以外的特征量，并且从一个可能的值中任意选择每个特征量时，能够将作为落入预定范围内的可能性的特征量加到样本中。

作为例子，考虑除样本之外采用特征点的方向作为特征量的实施例。在这种情况下，每一个方向都是从0到2π(弧度)任意选择的。当其差在“A(弧度)”内时，则确定其成对。就是说，当检验目标图形的特征点与样本图形的特征点的方向在±A(弧度)的范围内时，则确定其成对。因此，如果用于获得可能性P₁的等式2和等式3被修改成下面的等式5，并且将等式5带入等式4，则可以类似地计算当检验目标图形与样本图形之间的特征点对不少于M时的可能性。 $>>>P>1>>=>>N>2>>·>>>\pi >>E>2>>>S>>·>>>2>A>>>2>\pi >>>->->->>(>5>)>>>s>$

另外，从输出部分40输出相似性确定部分12计算的相似性(步骤204)。

如上所述，根据本实施例，能够不依赖于输入图形的特征点的密度准确地识别图形。

下面参照附图详细描述本发明的第二实施例。

图4是表示根据第二实施例的图形对照设备的结构方框图。图5是用于说明根据该本实施例的图形对照过程的流程图；

如图4和5所示，第二实施例与第一实施例的差别在于在数据处理部分10a中的相似性确定部分12a的功能。除了根据本实施例的步骤403中的相似性计算之外，图形对照处理的过程与前面第一实施例中的相同，这里将不再描述。

在前面第一实施例的相似性计算(步骤203)中，根据任意图形与样本图形之间的特征点对的数量不少于先前由特征点对形成部分11获得的检验目标图形与样本图形之间的特征点对的数量的可能性来计算检验目标图形与样本图形之间的相似性。

相反，在根据第二实施例在步骤403中的相似性计算过程中，不仅参考特征点对的数量，而且参考有关作为表示每个特征点对的特征度的值的特征量的数据计算相似性。就是说，根据在包括任意图形与样本图形之间的特征点对的数量和有关其特征量的数据时计算的一致性的值不小于根据先前由特征点对形成部分11获得的检验目标图形与样本图形之间的特征点对的数量以及其特征量计算的一致性的值的可能性来计算相似性。

图6是说明该实施例的步骤403中相似性确定处理的一个实施例的流程图。参照图6，首先，查阅相对于检验目标图形的特征点对的数量和特征点对之间的特征量的差(步骤403-1)。接下来，根据特征点对的数量计算相对于任意图形(假定要输入的任意图形)和相应特征点对之间的特征量的差的一致性不少于相对于检验目标图形的一致性的可能性(步骤403-2)。根据该可能性计算相似性(步骤403-3)。

下面给出了计算根据任意图形与样本图形之间的特征点对的数量以及其特征量计算的一致性的值不少于根据检验目标图形与样本图形之间的特征点对的数量以及其特征量计算的一致性的值的可能性的方法的实例。

在该实例中，仅用特征点的位置差作为形成特征点对的标准。作为例子，下面将描述当检验目标图形叠加在样本图形上并且它们的特征点之间的位置差不大于预定长度E时确定特征点对的方法。此外，假设样本图形的区域为S，检验目标图形具有N₁个特征点，样本图形具有N₂个特征点，并且它们之中的M个特征点形成了特征点对。现在，将其中N₁个特征点任意排列的所有图形看作是假定要输入的所有检验目标图形。此外，假定M个特征点对之间的位置差表示为E_i(i＝1，…，M)。

在具有区域S的样本图形中任意排列的特定点被排列在与检验目标图形的特征点之一的距离不大于位置差D的位置的可能性P₂(D)可以通过下面的等式6而获得。 $>>>P>2>>>(>D>)>>=>>>\pi >>D>2>>>S>>->->->>(>6>)>>>s>$

另外，通过下面的等式7可以获得这样排列的特定点与样本图形的任意特征点的没有不大于E的位置差的可能性P₃。 $>>>P>3>>=>1>->>>\pi >>E>2>>>S>>·>>N>2>>->->->>(>7>)>>>s>$

通过下面的等式8可以获得当N₁个特征点在样本图形中任意排列时，彼此不同的M₂个特征点对中的每一个具有不大于位置差Ei的可能性P₄(M₂)。 $>>>P>4>>>(>>M>2>>)>>>=>>N>2>>>>P>>M>2>>>>·>>N>1>>>>P>>M>2>>>·sup>>P>3>>(>>N>1>>->>M>2>>)>sup>>·>>\Pi >>i>=>1>>>M>2>>>>P>2>>>(>>E>i>>)>>->->->>(>8>)>>>s>$

在等式8中，假定当i不大于M时，E_i(其中i＝1，…，M)的值是由特征点对形成装置形成的特征点对之间的位置差，并且如果i的值大于M，它是该位置的可允许的误差“E”。通过这样的定义，可以通过下面的等式9获得与样本图形的N₂个特征点的一部分相一致的任意排列的N₁个特征点对中的特征点的数量不少于由特征点对形成装置形成的M对的可能性P₅。 $>>>P>5>>=>>\Sigma >>i>=>M>>>N>1>>>>P>4>>>(>i>)>>->->->>(>9>)>>>s>$

在使用除位置以外的特征量时，可以将它们加到样本中作为当从可能的值中任意选择时每一个特征量在预定范围内的可能性。

上面描述的第二实施例除了第一实施例的效果以外，不仅可以利用特征点对的数量，而且可以利用关于特征点对之间的特征量的差的信息更严格地识别。

下面参考附图详细描述本发明的第三实施例。

图7是表示根据第三实施例的图形对照设备的结构方框图。附图8是说明根据该实施例的图形对照过程的流程图。

如图7和8所示，第三实施例与前面每一个实施例的差别在于数据处理部分10b中的相似性确定部分12b的功能。由于除了本实施例的步骤604中的相似性计算外的图形对照处理过程与前面第一实施例中的相似性计算过程相同，在此不再对其进行说明。

图9是说明本实施例的步骤603中相似性确定处理的一个实施例的流程图。参考图9，首先，参考相对于检验目标图形的特征点对的数量和特征点对之间的特征量的差(步骤603-1)。接下来，在参考预先获得的可能性分布时获得特征点的特征量一致，不少于相对于检验目标图形的特征点对的可能性(步骤603-2)。根据该可能性计算相似性(步骤603-3)。下面更详细地描述在该实施例的步骤603-2中计算可能性的过程。

在步骤603的相似性计算过程中，执行与第一和第二实施例中的每一个中的相似性计算过程(步骤203以及步骤403)相同的过程。

此后，获得任意图形与样本图形是一致的，且不少于由特征点对形成部分11预先获得的检验目标图形与样本图形之间的特征点对的数量的可能性。另外，当检验目标图形和样本图形是相同图形时，获得对应的特征点之间特征量的差的分布。利用该分布获得当检验目标图形与样本图形是相同图形时，检验目标图形仅与不多于由特征点对形成部分11形成的特征点对的那些特征点一致的可能性P_a。

利用作为预定等式的变量的P_n和P_a获得的值被用作检验目标图形与样本图形之间的相似性。仅当考虑用特征点之间的位置差作为形成特征点对的标准，对应的特征点之间的位置差不小于F，检验目标图形具有N₁个特征点，和样本图形具有N₂个特征点，它们中的M对形成特征点对，并且相应特征点对之间的位置差表示为E_i(其中i＝1，…，M)的可能性P₆(F)时，例如，可由下面的等式10获得与不比由特征点对形成部分11形成的特征点多的特征点一致的可能性P_a。 $>>>P>a>>=>>\Pi >>i>=>1>>M>>>P>6>>>(>>E>i>>)>>->->->>(>10>)>>>s>$

如前面所述，根据第三实施例，除了前述的第一实施例的效果以外，当预先知道相同图形的特征点的特征量分布时，使用用于识别的分布能够准确地进行识别。

另外，也可以执行第二实施例与第三实施例中相似性计算处理的组合。

图10是表示设置有记录根据本发明的图形对照程序的记录介质的结构的一个实施例的示意图。

该图形对照程序被存储在诸如磁盘或半导体存储器之类的记录介质90中。将图形对照程序从存储介质加载到作为计算机处理装置的数据处理部分10c中，并通过控制数据处理部分10c的操作来实现且上述的相应功能。结果是，数据处理部分10c在图形对照程序的控制下执行由第一，第二和第三实施例中的数据处理部分10，10a和10b中执行的处理。

虽然至此已参考包括优选实施例在内的实施例描述了本发明。然而，本发明并不局限于这些实施例，而是能够在本发明的技术范围内以各种改进的方式执行。

如上所述，根据本发明的图形对照设备，可以不依赖于特征点的密度而使用估算标准，即要对比的检验目标图形当其是从假定要输入的所有图形任意选择的检验目标图形时偶然一致的可能性来获得相似性。因此，即使在输入图形的特征点的密度存在差别时也能准确地识别图形。