CN108665409A - 指纹图像的合并方法与电子装置 - Google Patents

Abstract

本发明提出一种指纹图像的合并方法，包括：建立层次结构，其中层次结构包括多个层级，这些层级的数目大于2，当中的最低层级中的每一个片段是通过指纹传感器所产生的单一指纹图像，第二层级中的片段包含了最多M张在第一层级中的片段，第二层级高于第一层级一个层级，M为大于1的正整数；取得新指纹图像，将新指纹图像加入至最低层级中，并更新层次结构；以及根据层级中的最高层级中的片段输出注册用指纹图像。

Description

指纹图像的合并方法与电子装置

技术领域

本发明涉及一种指纹图像的合并方法，且特别涉及一种利用层级结构来合并指纹图像的合并方法。

背景技术

人类的指纹具有细节多、几乎是独特、不容易更改、而且在个人的生命中是耐用的(durable)等特性，这使得指纹很适合长期用来作为人类身分的识别。指纹的应用至少有两个阶段，第一个阶段为注册(enroll)，第二个阶段为辨识两人指纹或身分验证。在注册阶段，使用者必须在将手指按压在指纹传感器上以取得足够的指纹特征。然而，在一些应用中，由于成本等因素的考虑使得指纹传感器的面积不会太大，因此在注册阶段时使用者必须在指纹传感器上按压多次，进而需要一个算法来合并多张指纹图像。一种现有的算法是先取得第一张指纹图像，而后续产生的指纹图像都会合并至第一张指纹图像，但这样的作法的缺点是当第一张指纹图像不清晰时，所合并出来的指纹图像会有许多错误，甚至有错误传递(error propagation)的问题。因此，如何提出一个更好的指纹图像合并方法，为此领域技术人员所关心的议题。

发明内容

本发明的实施例提出一种指纹图像的合并方法，适用于电子装置。此合并方法包括：建立层次结构，其中层次结构包括多个层级，这些层级的数目大于2，当中的最低层级中的每一个片段是通过指纹传感器所产生的单一指纹图像，第二层级中的片段包含了最多M张在第一层级中的片段，第二层级高于第一层级一个层级，M为大于1的正整数；取得新指纹图像，将新指纹图像加入至最低层级中，并更新层次结构；以及根据层级中的最高层级中的片段输出注册用指纹图像。

在一些实施例中，上述的合并方法还包括：设定在最低层级中的每一个片段都为完整；以及若在第i个层级中的一片段包括了在第i-1个层级中的M张完整片段，设定在第i个层级中的该片段为完整，其中i为大于1的正整数。

在一些实施例中，上述更新层次结构的步骤包括：设定第L个层级为最低层级，将新指纹图像设定为一传入片段，其中L为正整数；尝试将传入片段合并至在第L+1个层级中的一不完整片段以在第L+1个层级中产生第一片段；以及若尝试将传入片段合并至在第L+1个层级中的不完整片段的步骤成功且第一片段为不完整，搜寻在第L个层级中的一完整片段以合并至第一片段。

在一些实施例中，上述更新层次结构的步骤还包括：若尝试将传入片段合并至在第L+1个层级中的不完整片段的步骤不成功，尝试将传入片段合并至在第L个层级中的一完整片段以在第L+1个层级中产生第二片段；以及如果尝试将传入片段合并至在第L个层级中的完整片段的步骤成功并且第二片段为不完整，搜寻在第L个层级中的完整片段以合并至第二片段。

在一些实施例中，上述更新层次结构的步骤还包括：如果尝试将传入片段合并至在第L+1个层级中的不完整片段的步骤成功或者尝试将传入片段合并至在第L个层级中的完整片段的步骤成功，判断是否有片段从不完整改变为完整；如果有第三片段从不完整改变为完整，设定L＝L+1，并且将第三片段当作传入片段；以及重复执行尝试将传入片段合并至在第L+1个层级中的不完整片段的步骤。

在一些实施例中，上述更新层次结构的步骤还包括：如果尝试将传入片段合并至在第L个层级中的完整片段的步骤不成功或者没有片段从不完整改变为完整，判断是否能输出注册用指纹图像；以及若不能输出注册用指纹图像，等待接收另一新指纹图像。

在一些实施例中，上述判断是否能输出注册用指纹图像的步骤包括：取得在最高层级中的一最大片段，并且尝试将在层次结构中所有的片段都合并至最大片段；判断最大片段所包含的指纹图像的数目是否大于一预设值；以及若最大片段所包含的指纹图像的数目大于预设值，将最大片段输出以作为注册用指纹图像。

以另一个角度来说，本发明的实施例提出一种电子装置，包括指纹传感器与计算电路。指纹传感器用以取得新指纹图像。计算电路耦接至指纹传感器，用以建立层次结构。此层次结构包括多个层级，这些层级的数目大于2，当中的最低层级中的每一个片段是通过指纹传感器所产生的单一指纹图像。第二层级中的片段包含了最多M张在第一层级中的片段，第二层级高于第一层级一个层级，M为大于1的正整数。计算电路用以将新指纹图像加入至最低层级中，更新层次结构，并且根据层级中的一最高层级中的片段输出注册用指纹图像。

在一些实施例中，计算电路还用以执行上述的合并方法。

为让本发明的上述特征和优点能更明显易懂，下文特举实施例，并结合附图作详细说明如下。

附图说明

图1是根据一实施例绘示电子装置的示意图；

图2是根据一实施例绘示层次结构的示意图；

图3是根据一实施例说明合并片段的示意图；

图4是根据一实施例绘示更新层次结构的流程图；

图5至图9是根据实施例绘示更新层次结构的中间步骤；以及

图10是根据一实施例绘示指纹图像的合并方法的流程图。

具体实施方式

关于本文中所使用的“第一”、“第二”、…等，并非特别指次序或顺位的意思，其仅为了区别以相同技术用语描述的元件或操作。另外，关于本文中所使用的“耦接”，可指二个元件直接地或间接地作电连接。也就是说，当以下描述“第一对象耦接至第二对象”时，第一对象与第二对象之间还可设置其它的对象。

图1是根据一实施例绘示电子装置的示意图。请参照图1，电子装置100包括了指纹传感器110与计算电路120。电子装置100可以是智能型手机、平板计算机、音乐播放器、笔记本电脑、工业计算机、或其它任意形式的电子装置，本发明并不限于此。指纹传感器110可用以取得人类的指纹图像，指纹传感器110的感测方式可以是光学式、电容式或超音波式等，本发明并不限制指纹传感器110的感测方式。计算电路120可以为中央处理器、微处理器、微控制器、数字信号处理器、基频处理器、图像处理芯片或特殊应用集成电路等。

指纹传感器110会取得人类的多张指纹图像，并将所取得的指纹图像传送给计算电路120，而计算电路120会合并这些指纹图像。图2是根据一实施例绘示层次结构的示意图。请参照图2，计算电路120会建立一个层次结构200，其中包括了N个层级210(1)～210(N)，N为大于2的正整数。其中层级210(1)为最低层级，而层级210(N)为最高层级。在此定义“片段”为每个层级中的一个单元。层级210(2)中的一个片段包括了最多M张在层级210(1)中的片段，M为大于1的正整数。而层级210(3)中的一个片段包括了最多M张在层级210(2)的片段，以此类推。换言之，若在层次结构200中具有第二层级与第一层级，且第二层级高于第一层级一个层级，则第二层级中的一个片段包含了最多M张在第一层级中的片段。

每个片段可分为完整或不完整。首先，在最低层级210(1)中的每一个片段是通过指纹传感器110所产生的单一指纹图像，并且在最低层级210(1)中的每一个片段都是完整的。此外，若在第i个层级中的一个片段包括了在第i-1个层级中的M张完整片段，则可设定在第i个层级中的该片段为完整(否则就是不完整)，其中i为大于1的正整数。举例来说，片段221包括了M个片段222(1)～222(M)，因此片段221为完整。而片段223仅包括了一个片段224，因此片段223为不完整。以另一个角度来说，在第i-1个层级中的M张完整片段可以合并为在第i个层级中的一张完整片段。最高层级210(N)中的片段可用来输出注册用指纹图像240。也就是说，注册用指纹图像240具有足够的面积或特征点以进行注册的程序。当指纹传感器110取得新指纹图像230以后，此新指纹图像230会被加入至最低层级210(1)中，然后计算电路120会更新层次结构200，以下将说明更新的流程。

首先说明两个片段的合并，图3是根据一实施例说明合并片段的示意图。请参照图3，在此假设指纹图像310与指纹图像320为两个片段，图中的线条指的是纹脊(ridge)而在纹脊之间的空间则是纹谷(valley)。指纹图像310、320都不是注册用指纹图像，也就是说指纹图像310、320的面积都不够大。从指纹图像310、320中可撷取多个特征，一般来说至少可撷取纹脊的终点(ending)与分叉(bifurcation)。例如，指纹图像310中具有终点311与分叉312，而指纹图像320中具有终点321与分叉322。指纹图像310中的特征可配对至指纹图像320中的特征。例如，终点311与终点321是彼此配对，而分叉312与分叉322是彼此配对。在配对完特征以后，便可以将指纹图像310、320合并成为指纹图像330。然而，如果指纹图像310、320中没有配对的特征或者是配对的特征不够多，则表示指纹图像310、320不能够合并在一起。然而，上述合并的方法仅为范例，本发明并不限制要从指纹图像中撷取那些特征，也不限定要如何合并两张指纹图像(片段)。

在此实施例中，在同一个层级中只有两个完整片段可以彼此合并，同一个层级中不完整的片段并不会彼此合并；当合并是跨层级时，则较低层级的片段必须要是完整的。以下将结合图4详细说明，图4是根据一实施例绘示更新层次结构的流程图，图4中的各步骤是由计算电路120所执行。请参照图4，在步骤S401中，从指纹传感器110取得新指纹图像，并将新指纹图像设定为传入片段。在步骤S402中，设定第L个层级为最低层级，L为正整数，在此实施例中是将L设定为1。在步骤S403中，将传入片段加入至第L个层级。请同时参照图4与图5，片段510为传入片段，层级中的圆形表示为完整片段，而正方形表示为不完整片段。上述的正整数M是大于2。当传入片段510为新指纹图像时，层级210(L)为层级210(1)，且层级210(1)中的所有片段都是完整的，但为了更一般化的表示合并的流程，在图5中是使用层级210(L)，且层级210(L)中具有不完整片段。

在步骤S404中，尝试将传入片段510合并至在第L+1个层级中的一个不完整片段以产生第一片段。例如，可尝试将传入片段510合并至层级210(L+1)中的不完整片段520。在一些实施例中，若在层级210(L+1)中有多于一个不完整片段，则可先挑选较旧(即停留在层级210(L+1)较久的时间)的不完整片段来合并。若将传入片段510合并至不完整片段520的步骤成功，则会产生新的片段(在此称第一片段530)。

若步骤S404成功，接下来在步骤S405中，判断第一片段530是否为不完整。如果第一片段530为不完整，搜寻在第L个层级中的完整片段以合并至第一片段530。举例来说，请参照图6，由于第一片段530为不完整，因此可尝试将片段610、620都合并至第一片段530。在此实施例中，层级210(L)中有两个完整片段610、620，因此可先挑选较旧的片段610来合并至第一片段530。步骤S405会一直重复执行，直到第一片段530为完整或者是层级210(L)中没有完整片段为止。值得一提的是，虽然层级210(L)中有片段630，但由于片段630并不完整，因此并不会尝试将片段630合并至第一片段530。片段630会交由层级210(L-1)来负责，当处理层级210(L-1)时片段630有可能转变为完整。

在图5与图6的例子中，正整数M是大于2。当正整数M等于2时，则层级210(L+1)中并不会有不完整片段(理由会说明如下)，因此步骤S404必然会失败，且步骤S405并不会执行。

另一方面，若步骤S404不成功，在步骤S406中会尝试将传入片段合并至在第L个层级中的完整片段以在第L+1个层级中产生第二片段。举例来说，请参照图4与图7，可尝试将传入片段510合并至同一个层级210(L)中的完整片段710以在层级210(L+1)中产生第二片段720。在此实施例中正整数M是大于2，因此第二片段720应是不完整。此外，如果层级210(L)中除了传入片段510以外有多于一个完整片段710、730，则可先选择较旧的完整片段710来尝试合并。如果传入片段510无法与片段710合并，则会再尝试合并传入片段510与片段730。

如果步骤S406成功，则在步骤S407中会判断第二片段720是否为不完整，如果第二片段720为不完整，可搜寻在第L个层级中的完整片段以合并至第二片段720。例如，请参照图4与图8，由于第二片段720为不完整，因此可在层级210(L)中搜寻到完整片段730以合并至第二片段720。如果片段730不能合并至第二片段720，则维持第二片段720不变。

值得一提的是，在图7与图8的实施例中正整数M为大于2，但如果正整数M为2则所建立的片段都是完整的。例如，请参照图9，将传入片段510与片段710合并之后所产生的第二片段720是完整的。更进一步来说，如果正整数M为2，则所有层级中的所有片段都会是完整的。

请参照回图4，在步骤S405或步骤S407之后会进行步骤S408，判断是否有片段从不完整改变为完整。在此实施例中，便是判断图6中更新后的第一片段530或图8中新建立的第二片段720是否为完整。如果有一个第三片段(第一片段530或第二片段720)从不完整改变为完整，在步骤S409中，设定L＝L+1，并且将第三片段当作传入片段。接下来根据更新后的传入片段重复执行步骤S404。以另外一个角度来说，如果步骤S408的结果为是，这表示在第L+1个层级中新产生了一个完整片段，因此有可能这个新的完整片段可以继续合并至下一层级。如果步骤S408的结果为否，则表示即使在第L+1个层级中新产生了一个片段，但因为这个新的片段为不完整，因此这个新的片段不可能会合并至下一层级，不需要执行步骤S409。

另一方面，当正整数M为2时并不会执行步骤S405，而在步骤S406所建立的第二片段必定是完整，因此步骤S408的结果必定为是。

如果步骤S406的结果是失败或者步骤S408的结果为否，则进行步骤S410，判断是否输出注册用指纹图像。请参照回图2，在一些实施例中可以先从最高层级210(N)中找到一个最大片段，此最大片段可以是面积最大的指纹图像或者是合并最多张单一指纹图像的指纹图像。在取得最大片段以后，可尝试将层次结构200中所有的片段都合并至此最大片段。接下来，判断最大片段所包含的指纹图像的数目是否大于一个预设值(例如8)。若最大片段所包含的指纹图像的数目大于预设值，则步骤S410的结果为是，在步骤S411中可以将最大片段输出以作为注册用指纹图像。然而，本发明并不在此限，在其它的实施例中，在尝试将层次结构200中所有的片段都合并至最大片段以后，也可以判断最大片段的面积是否大于一预设面积或者判断最大片段的特征的数目是否大于一个预设数目以判断是否要输出注册用指纹图像。或者，如果指纹传感器110已经取得多于一预设数目的指纹图像，则步骤S410中也可以判断为是。本发明并不限制步骤S410的具体内容。

如果步骤S410的结果为否，在步骤S412中计算电路120则会暂停，等待下一张新指纹图像进来(步骤S401)。

图10是根据一实施例绘示指纹图像的合并方法的流程图。请参照图10，在步骤S1001中，建立层次结构。此层次结构包括多于2个层级，其中最低层级中的每一个片段是通过指纹传感器所产生的单一指纹图像。当第二层级高于第一层级一个层级时，第二层级中的一片段包含了最多M张在第一层级中的片段。在步骤S1002中，取得新指纹图像，将新指纹图像加入至最低层级中，并更新层次结构。在步骤S1003中，根据最高层级中的片段输出注册用指纹图像。然而，图10中各步骤已详细说明如上，在此便不再赘述。值得注意的是，图10中各步骤可以实作为多个程序代码或是电路，本发明并不限于此。此外，图10的方法可以搭配以上实施例使用，也可以单独使用。换言之，图10的各步骤之间也可以加入其它的步骤。或者，图10中各步骤也可以重复执行多次(例如步骤S1002)。

在本发明实施例提出的合并方法中，并不会发生错误传递的现象，即使有产生错误，错误的分布也比较均匀。此外，使用上述方法所产生的注册用指纹图像可以增加后续辨识阶段的正确率。

虽然本发明已以实施例揭露如上，然其并非用以限定本发明，任何本领域技术人员，在不脱离本发明的精神和范围内，当可作些许的更动与润饰，故本发明的保护范围当视后附的权利要求所界定者为准。

符号说明：

100：电子装置

110：指纹传感器

120：计算电路

200：层次结构

210(1)～210(N)、210(L)、210(L+1)：层级

221、222(1)～222(M)、223、224：片段

230：新指纹图像

240：注册用指纹图像

310、320、330：指纹图像

311、321：终点

312、322：分叉

S401～S412、S1001～S1003：步骤

510、520、530、610、620、630、710、720、730：片段

Claims (14)

1.一种指纹图像的合并方法，适用于电子装置，所述合并方法包括：

建立层次结构，其中所述层次结构包括多个层级，所述多个层级的数目大于2，所述多个层级中的最低层级中的每一个片段是通过指纹传感器所产生的单一指纹图像，所述多个层级中的第二层级中的片段包含了最多M张在第一层级中的片段，所述第二层级高于所述第一层级一个层级，M为大于1的正整数；

取得新指纹图像，将所述新指纹图像加入至所述最低层级中，并更新所述层次结构；以及

根据所述多个层级中的最高层级中的片段输出注册用指纹图像。

2.如权利要求1所述的合并方法，还包括：

设定在所述最低层级中的多个所述片段中的每一个都为完整；以及

若在第i个层级中的片段包括了在第i-1个层级中的M张完整片段，设定在所述第i个层级中的所述片段为完整，其中i为大于1的正整数。

3.如权利要求2所述的合并方法，其中更新所述层次结构的步骤包括：

设定第L个层级为所述最低层级，将所述新指纹图像设定为传入片段，其中L为正整数；

尝试将所述传入片段合并至在第L+1个层级中的不完整片段以在所述第L+1个层级中产生第一片段；以及

若尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤成功且所述第一片段为不完整，搜寻在所述第L个层级中的完整片段以合并至所述第一片段。

4.如权利要求3所述的合并方法，其中更新所述层次结构的步骤还包括：

若尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤不成功，尝试将所述传入片段合并至在所述第L个层级中的完整片段以在所述第L+1个层级中产生第二片段；以及

如果尝试将所述传入片段合并至在所述第L个层级中的所述完整片段的步骤成功并且所述第二片段为不完整，搜寻在所述第L个层级中的完整片段以合并至所述第二片段。

5.如权利要求4所述的合并方法，其中更新所述层次结构的步骤还包括：

如果尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤成功或者尝试将所述传入片段合并至在所述第L个层级中的所述完整片段的步骤成功，判断是否有片段从不完整改变为完整；

如果有第三片段从不完整改变为完整，设定L＝L+1，并且将所述第三片段当作所述传入片段；以及

重复执行尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤。

6.如权利要求5所述的合并方法，其中更新所述层次结构的步骤还包括：

如果尝试将所述传入片段合并至在所述第L个层级中的完整片段的步骤不成功或者没有片段从不完整改变为完整，判断是否能输出所述注册用指纹图像；以及

若不能输出所述注册用指纹图像，等待接收另一新指纹图像。

7.如权利要求6所述的合并方法，其中判断是否能输出所述注册用指纹图像的步骤包括：

取得在所述最高层级中的最大片段，并且尝试将在所述层次结构中所有的片段都合并至所述最大片段；

判断所述最大片段所包含的指纹图像的数目是否大于预设值；以及

若所述最大片段所包含的指纹图像的数目大于所述预设值，将所述最大片段输出以作为所述注册用指纹图像。

8.一种电子装置，包括：

指纹传感器，用以取得新指纹图像；以及

计算电路，耦接至所述指纹传感器，所述计算电路用以建立层次结构，其中所述层次结构包括多个层级，所述多个层级的数目大于2，所述多个层级中的最低层级中的每一个片段是通过所述指纹传感器所产生的单一指纹图像，所述多个层级中的第二层级中的片段包含了最多M张在第一层级中的片段，所述第二层级高于所述第一层级一个层级，M为大于1的正整数，

所述计算电路用以将所述新指纹图像加入至所述最低层级中，更新所述层次结构，并且根据所述多个层级中的最高层级中的片段输出注册用指纹图像。

9.如权利要求8所述的电子装置，其中

若在第i个层级中的片段包括了M张在第i-1个层级中的片段，所述计算电路设定在所述第i个层级中的所述片段为完整，其中i为正整数；以及

所述计算电路设定在所述最低层级中的多个所述片段中的每一个都为完整。

10.如权利要求9所述的电子装置，其中

所述计算电路设定第L个层级为所述最低层级，将所述新指纹图像设定为传入片段；

所述计算电路尝试将所述传入片段合并至在第L+1个层级中的不完整片段以在所述第L+1个层级中产生第一片段；以及

若尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤成功且所述第一片段为不完整，所述计算电路搜寻在所述第L个层级中的完整片段以合并至所述第一片段。

11.如权利要求10所述的电子装置，其中

若尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤不成功，所述计算电路尝试将所述传入片段合并至在所述第L个层级中的完整片段以在所述第L+1个层级中产生第二片段；以及

如果尝试将所述传入片段合并至在所述第L个层级中的所述完整片段的步骤成功并且所述第二片段为不完整，所述计算电路搜寻在所述第L个层级中的完整片段以合并至所述第二片段。

12.如权利要求11所述的电子装置，其中

如果尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤成功或者尝试将所述传入片段合并至在所述第L个层级中的所述完整片段的步骤成功，所述计算电路判断是否有片段从不完整改变为完整；

如果第三片段从不完整改变为完整，所述计算电路设定L＝L+1，并且将所述第三片段当作所述传入片段；以及

所述计算电路重复执行尝试将所述传入片段合并至在所述第L+1个层级中的所述不完整片段的步骤。

13.如权利要求12所述的电子装置，其中

如果尝试将所述传入片段合并至在所述第L个层级中的完整片段的步骤不成功或者没有片段从不完整改变为完整，所述计算电路判断是否能输出所述注册用指纹图像；以及

若不能输出所述注册用指纹图像，所述计算电路等待接收另一新指纹图像。

14.如权利要求13所述的电子装置，其中

所述计算电路取得在所述最高层级中的最大片段，并且尝试将在所述层次结构中所有的片段都合并至所述最大片段；

所述计算电路判断所述最大片段所包含的指纹图像的数目是否大于预设值；以及

若所述最大片段所包含的指纹图像的数目大于所述预设值，所述计算电路将所述最大片段输出以作为所述注册用指纹图像。