TW201835813A - 指紋影像的合併方法與電子裝置 - 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的正整數。計算電路用以將新指紋影像加入至最低層級中，更新層次結構，並且根據層級中的一最高層級中的片段輸出註冊用指紋影像。

在一些實施例中，計算電路還用以執行上述的合併方法。

為讓本發明的上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。

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‧‧‧片段

[圖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)。

在本發明實施例提出的合併方法中，並不會發生錯誤傳遞的現象，即使有產生錯誤，錯誤的分佈也比較均勻。此外，使用上述方法所產生的註冊用指紋影像可以增加後續辨識階段的正確率。

雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明的精神和範圍內，當可作些許的更動與潤飾，故本發明的保護範圍當視後附的申請專利範圍所界定者為準。

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項所述之電子裝置，其中該計算電路取得在該最高層級中的一最大片段，並且嘗試將在該層次結構中所有的片段都合併至該最大片段；該計算電路判斷該最大片段所包含的指紋影像的數目是否大於一預設值；以及若該最大片段所包含的指紋影像的數目大於該預設值，該計算電路將該最大片段輸出以作為該註冊用指紋影像。