圖案間特徵對應設備、其圖案間特徵對應方法及其程序的製作方法

2023-10-08 20:14:34

專利名稱：圖案間特徵對應設備、其圖案間特徵對應方法及其程序的製作方法
技術領域：
本發明涉及圖案間特徵對應設備、用於該圖案間特徵對應設備的圖案間特徵對應 方法以及針對該方法的程序，具體涉及一種確定圖案間特徵對應關係的技術。
背景技術：
例如，在專利文獻1中描述的指紋驗證設備使用這種技術來確定圖案間特徵對應 關係。這種指紋驗證設備是一種用於驗證指紋圖案之間的匹配的設備。上述指紋驗證設備對於所有特徵點，通過強力(brute force)方法來檢驗要搜索 的指紋與參考指紋之間的匹配，並確定某個區域的坐標匹配量，在所述區域中從已經被確 定為候選的對應特徵點中以投票的方式選舉出坐標匹配參數空間。此外，指紋驗證設備基於該坐標匹配量來執行特徵點的坐標匹配，執行精細選擇 過程並確定對應特徵點，在所述精細選擇過程中刪除彼此之間特徵相差極大的候選對。此外，作為確定圖案間特徵對應關係的另一種技術，以示例的方式示出了以下技 術在該技術中，為了確定對應點，將點用作單元，基於從每個點所具有的局部圖案信息得 到的特徵量來計算對應點的類似程度，執行對應程度的初始化，執行更新，進行收斂判定， 並且提取對應程度高的對應點(例如，參考專利文獻2)。此外，作為確定圖案間特徵對應關係的另一種技術，提出了以下技術在該技術 中，基於脊上特徵點的連接狀態來執行匹配檢驗(例如，參考專利文獻3)。[專利文獻1]日本專利申請公開No.1984-778[專利文獻2]日本專利申請公開No.1999-110542[專利文獻3]日本專利申請公開No. 1999-195119

發明內容
本發明要解決的技術問題然而，在上述指紋驗證設備中，在採用在以上提到的專利文獻1中描述的技術的 情況下，每當採集指紋時指紋圖案變化。因此，在要驗證的圖案包括不能通過所採取的幾何 變換來指示的彈性畸變成分的情況下，當通過使用坐標匹配參數來指示要驗證的圖案之間 的總變化時，實際對應特徵點可能彼此極大地不同。由此，出現的問題是圖案之間匹配的驗 證變難。在上述指紋驗證設備中，在為了精細選擇候選對而執行的特徵點坐標匹配過程 中，作為剛體運動來處理要驗證的圖案之間的總變化。因此，當要驗證的圖案包括不能通過 所採取的幾何變換來指示的彈性畸變分量時，通過該過程刪除實際對應特徵點的一部分。 相應地，出現的問題是沒有充分提取用於鑑別的對應特徵點。此外，當不使用每個點的標識信息時，不能通過使用以上提到的專利文獻2中所 描述的技術來計算點之間的類似程度。專利文獻3中描述的技術不能用於沒有脊的圖案。相應地，本發明的目的是提供一種圖案間特徵對應設備，可以解決上述問題並且即使要驗證的圖案有畸變也可以以高精度確定圖案之間的特徵對應關係，本發明的目的還 包括提供一種用於這種圖案間特徵對應設備的圖案間特徵對應方法以及針對該方法的程序。解決問題的手段根據本發明的圖案間特徵對應設備包括產生裝置，用於將所輸入的圖案信號中彼此在位置上接近的N個特徵點設置為鄰 近特徵點組，將鄰近特徵點組和布置關係數值組設置為特徵點組布置，並產生鄰近特徵點 組、布置關係數值組和特徵點組布置中的至少一個，所述布置關係數值組表示鄰近特徵點 組的特徵點之間的布置關係，N是大於等於2的整數，檢測裝置，用於執行對第一圖案的布置關係數值與由產生裝置產生的第二圖案的 布置關係數值的比較，以檢測彼此相對應的對應特徵點組布置候選，更新裝置，用於對於對應特徵點組布置候選，執行對與每個特徵點組布置的特徵 點和在位置上接近特徵點組布置的特徵點有關的布置關係數值的比較，分別將彼此相對應 的鄰近特徵點添加到對應特徵點組布置候選，並更新對應特徵點組布置候選，用於檢驗由更新裝置更新的對應特徵點組布置候選的伴隨對應特徵點候選，以確 定對應特徵點組布置候選的伴隨對應特徵點的裝置，以及用於檢驗對應特徵點組布置候選，以確定在圖案之間彼此相對應的對應特徵點的
直ο根據本發明的圖案間特徵對應方法包括第一步驟，在所述第一步驟中，將所輸入的圖案信號中彼此在位置上接近的N個 特徵點設置為鄰近特徵點組，將鄰近特徵點組和布置關係數值組設置為特徵點組布置，並 產生鄰近特徵點組、布置關係數值組和特徵點組布置中的至少一個，所述布置關係數值組 表示鄰近特徵點組的特徵點之間的布置關係，N是大於等於2的整數，第二步驟，在所述第二步驟中，執行對第一圖案的布置關係數值與在第一步驟中 產生的第二圖案的布置關係數值的比較，以檢測彼此相對應的對應特徵點組布置候選，第三步驟，在所述第三步驟中，對於對應特徵點組布置候選，執行對與每個特徵點 組布置的特徵點和在位置上接近特徵點組布置的特徵點有關的布置關係數值的比較，分別 將彼此相對應的鄰近特徵點添加到對應特徵點組布置候選，並更新對應特徵點組布置候 選，第四步驟，在所述第四步驟中，檢驗在第三步驟中更新的對應特徵點組布置候選 的伴隨對應特徵點候選，以確定對應特徵點組布置候選的伴隨對應特徵點，以及第五步驟，在所述第五步驟中，檢驗對應特徵點組布置候選，以確定在圖案之間彼 此相對應的對應特徵點。根據本發明的程序允許圖案間特徵對應設備中的中央處理單元執行處理，以通過 使用圖案的特徵點信息使圖案間特徵彼此相對應，所述程序包括以下進程第一進程，在所述第一進程中，將所輸入的圖案信號中彼此在位置上接近的N個 特徵點設置為鄰近特徵點組，將鄰近特徵點組和布置關係數值組設置為特徵點組布置，並 產生鄰近特徵點組、布置關係數值組和特徵點組布置中的至少一個，所述布置關係數值組 表示鄰近特徵點組的特徵點之間的布置關係，N是大於等於2的整數，
第二進程，在所述第二進程中，執行對第一圖案的布置關係數值與在第一進程中 產生的第二圖案的布置關係數值的比較，以檢測彼此相對應的對應特徵點組布置候選，第三進程，在所述第三進程中，對於對應特徵點組布置候選，執行對與每個特徵點 組布置的特徵點和在位置上接近特徵點組布置的特徵點有關的布置關係數值的比較，分別 將彼此相對應的鄰近特徵點添加到對應特徵點組布置候選，並更新對應特徵點組布置候 選，第四進程，在所述第四進程中，檢驗在第三進程中更新的對應特徵點組布置候選 的伴隨對應特徵點候選，以確定對應特徵點組布置候選的伴隨對應特徵點，以及第五進程，在所述第五進程中，檢驗對應特徵點組布置候選以確定在圖案之間彼 此相對應的對應特徵點。本發明的效果本發明具有上述配置並如上所述來操作。因此，本發明具有的效果是即使要驗證 的圖案有畸變，也可以以高精度來確定圖案之間的特徵對應關係。


圖1示出了根據本發明第一示例實施例的圖案間特徵對應設備的示例配置的框 圖。圖2示出了根據本發明第一示例實施例的圖案間特徵對應方法的操作的流程圖。圖3A和圖3B示出了在本發明第一示例實施例中產生鄰近特徵點組布置的方法的 圖。圖4A和圖4B示出了在本發明第一示例實施例中檢測對應特徵點組布置候選的方 法的圖。圖5A和圖5B示出了在本發明第一示例實施例中更新對應特徵電組布置候選的方 法的圖。圖6A和圖6B示出了在本發明第一示例實施例中選擇伴隨對應特徵點候選的圖。圖7示出了在本發明第一示例實施例中特徵點相關布置關係數值的圖。圖8A和圖8B示出了在本發明第一示例實施例中的布置關係的比較的圖，其中每 個布置關係示出了特徵點組布置的特徵點以及靠近特徵點組布置的特徵點的布置。圖9示出了根據本發明第二示例實施例的圖案間特徵對應設備的示例配置的框 圖。圖10示出了根據本發明第三示例實施例的圖案驗證設備的示例配置的框圖。符號的描述1圖案間特徵對應設備2CPU3程序存儲單元4圖案驗證設備11圖案鄰近特徵點組布置創建單元Ila搜索圖案鄰近特徵點組布置創建單元lib參考圖案鄰近特徵點組布置創建單元
12對應布置候選檢測單元13對應布置候選更新單元14對應布置候選對應特徵點確定單元15對應特徵點確定單元41搜索圖案特徵存儲單元42參考圖案特徵存儲單元43驗證確定單元
具體實施例方式接下來將參考附圖描述本發明的示例實施例。圖1示出了根據本發明第一示例實 施例的圖案間特徵對應設備的示例配置的框圖。在圖1中，圖案間特徵對應設備1包括圖 案鄰近特徵點組布置創建單元11、對應布置候選檢測單元12、對應布置候選更新單元13、 對應布置候選對應特徵點確定單元14和對應特徵點確定單元15。圖2示出了根據本發明第一示例實施例的圖案間特徵對應方法的操作的流程圖。 將參考圖1和圖2來描述根據本發明第一示例實施例的圖案間特徵對應方法的操作。圖案間特徵對應設備1的圖案鄰近特徵點組布置創建單元11輸入圖案信號並創 建圖案信號中鄰近特徵點組的布置(圖2中的步驟Si)。對應布置候選檢測單元12對於輸 入圖案，檢測圖案鄰近特徵點組布置創建單元11創建的圖案信號中的鄰近特徵點組布置 之間的匹配，並檢測彼此相對應的特徵點組布置候選(圖2中的步驟S2)。對應布置候選更新單元13對於對應布置候選檢測單元12檢測到的對應(特徵點 組)布置候選，針對每個特徵點組布置及其鄰近特徵點來檢驗布置關係的匹配，添加彼此 相對應的鄰近特徵點並更新對應布置候選(圖2中的步驟S3)。對應布置候選對應特徵點確定單元14對於對應布置候選更新單元13已完成更新 的每個對應布置候選，檢驗伴隨對應布置候選的每個對應特徵點候選，並確定伴隨對應布 置候選的對應特徵點(圖2中的步驟S4)。對應特徵點確定單元15檢驗由對應布置候選對應特徵點確定單元14已確定其伴 隨對應特徵點的每個對應布置候選，並得到在圖案之間彼此相對應的對應布置以及伴隨該 對應布置的對應特徵點(圖2中的步驟S5)。圖3A和圖3B示出了在本發明第一示例實施例中產生鄰近特徵點組布置的方法的 圖。圖4A和圖4B示出了在本發明第一示例實施例中檢測對應特徵點組布置候選的方法的 圖。圖5A和圖5B示出了在本發明第一示例實施例中更新對應特徵點組布置候選的方法的 圖。圖6A和圖6B示出了在本發明第一示例實施例中選擇伴隨對應特徵點候選的圖。 圖7示出了在本發明第一示例實施例中特徵點相關布置關係數值的圖。圖8A和圖8B示出 了在本發明第一示例實施例中布置關係的比較的圖，其中每個布置關係示出了特徵點組布 置的特徵點以及在位置上接近特徵點組布置的特徵點的布置。將參考圖1至圖8來詳細描述本根據本發明第一示例實施例的圖案間特徵對應方 法的操作。上述圖案間特徵對應設備1的所有單元操作如下。圖案鄰近特徵點組布置創建單元11輸入圖案信號並創建圖案信號中的鄰近特徵點組的布置。鄰近特徵點組的布置包括在圖案信號中檢測到的特徵點集合以及布置關係數 值組，所述布置關係數值組表示特徵點集合的特徵點之間的布置關係。特徵點相關布置關 係數值包括可以用來確定特徵點之間的布置的數值，如，特徵點之間的距離、連接特徵點的 矢量之間的交叉角、特徵點之間特徵點方向的差異、或其他。在該示例實施例中，鄰近特徵點組是在圖案信號中位置上彼此接近的特徵點的集 合。鄰近特徵點組的所有布置都由標識符(ID)來標識，並且被管理。此外，希望所創建的 鄰近特徵點組布置的特徵點數目是大於等於2的固定整數N。圖3A和圖3B示意性地示出了指紋圖案的特徵點及其鄰近特徵點組布置的不完整 放大圖作為圖案的示例。圖3A示出了指紋的特徵點(Pl至P6)的空間分布。圖3B示出了 鄰近特徵點組的布置(Dl至D4)，每個布置包括包括三個特徵點。圖7示意性地示出了特徵點相關布置關係數值的示例。例如，特徵點Pl與特徵點 P2之間的距離L12、特徵點間矢量P2P1與特徵點間矢量P2P3之間的交叉角、或特徵點方向 Vl可以用作特徵點相關布置關係數值，其中特徵點方向Vl是當可以針對如指紋圖案一樣 的每個特徵點檢測到特徵點方向時，特徵點Pl的相對於布置P1P2P3的任意特徵點間矢量 等而言的特徵點方向。對應布置候選檢測單元12對於輸入圖案，檢驗在圖案信號中創建的所有特徵點 組布置之間的匹配，以檢測彼此相對應的特徵點組布置候選。通過檢驗特徵點相關布置關 係數值等之間的差異是否在預定的可允許範圍之內來執行特徵點組布置的匹配檢驗。對應 布置候選檢測單元12登記特徵點組布置，所述特徵點組布置在圖案之間彼此相對應並且 通過匹配檢驗作為對應布置候選。可以通過使用參考坐標系的一般圖像坐標系來測量用於對特徵點組布置進行匹 配檢驗的特徵點相關布置關係數值。然而，當如指紋驗證一樣在圖案之間包括彈性畸變成 分時，希望使用本申請的申請人提出的圖案中的流線坐標系來作為參考坐標系。通過使用 該坐標系，特徵點相關布置關係數值的變化變小。因此，可以通過減小可允許範圍來減小由於特徵點組布置等的錯誤檢測而引起的 諸如錯誤對應之類的「噪聲」的影響，從而可以提高檢測精度，例如，得到可以容易檢測的實 際對應特徵點組布置。當流線坐標系用作參考坐標系時，位置上彼此分離的特徵點可以被 看作是鄰近特徵點。得到的效果是可以驗證的圖案的數目增大。通過檢測圖案信號中的流線並設置與檢測到的流線的方向相對應的坐標系(稱 作「流線坐標系」)，來得到流線坐標系。例如，特別地由條帶圖案上圖案的流動方向的分布 來確定的坐標系被限定為圖案的流線坐標系(稱作「自然坐標系」)，其中所述條帶圖案被 由彼此正交的流線曲線和法線曲線組成的曲線組變形和指定。曲線組稱作「坐標曲線組」， 諸如圖案中的每個點在流線坐標系中的位置、姿勢或其他之類的屬性由點與每個坐標曲線 之間的關係來確定。圖4A和圖4B示意性地示出了要搜索的圖案和參考圖案的特徵點和鄰近特徵點組 布置的不完整放大圖，其中將要搜索的圖案和參考圖案相互比較，以說明圖案中彼此相對 應的對應布置候選的檢測。圖4A示出了要搜索的圖案的鄰近特徵點組布置Dl至D4。圖4B 示出了參考圖案的鄰近特徵點組布置Ml至M3。在該示例中，多對鄰近特徵點組布置(D1， Ml), (D2，M2)和(D3，M3)通過匹配檢驗並且這多對特徵點組布置被檢測為對應布置候選。
對應布置候選更新單元13對於對應布置候選，檢驗對應布置候選的每個特徵點 組布置的特徵點和在位置上靠近特徵點組布置的特徵點的布置關係數值之間的匹配，並向 對應特徵點組布置添加基於檢驗結果被確定為布置關係數值彼此匹配的鄰近特徵點作為 新的對應特徵點候選。順序地對所有鄰近特徵點執行這種檢驗和添加過程，儘可能多地連 續執行對應布置候選的更新。圖5A和圖5B對於要搜索的圖案和參考圖案，示意性地示出了被確定為布置關係 數值彼此匹配的布置候選，以及這些布置的鄰近特徵點。圖5A示出了要搜索的圖案的特徵 點組布置Dl及其鄰近特徵點P4至P6。圖5B示出了參考圖案的特徵點組布置Ml及其鄰近 特徵點Q4至Q5。 在本示例中，特徵點組布置Dl和Ml是通過布置匹配檢驗的對應布置候選。為了更 新對應布置候選，例如，將布置Dl和特徵點P4的位置關係數值與布置Ml和特徵點Q4的位 置關係數值相比較。如果位置關係數值的差異在預定的可允許範圍內，則分別將特徵點P4 和Q4添加到特徵點組布置Dl和Ml，將對應布置(D1,M1)替換成新的對應布置(D1，，M1，)。如圖8A和8B所示，例如，在將布置Dl和特徵點P4的位置關係數值與布置Ml和 特徵點Q4的位置關係數值相比較時，將特徵點Pl和P4之間的距離L14與特徵點Ql和Q4 之間的距離N14相比較，此外，必須執行對特徵點間矢量P1P2和特徵點間矢量P1P4之間的 交叉角與特徵點間矢量Q1Q2和特徵點間矢量Q1Q4之間的交叉角的比較等等。這是因為特 徵點P4與布置P1P2P3之間的位置關係不能通過僅使用距離L14來確定。如果可以如指紋圖案一樣檢測到特徵點的特徵點方向，則可以執行對特徵點方向 Vl和特徵點矢量之間的交叉角與特徵點方向wl和對應特徵點矢量之間的交叉角的比較， 而不是執行上述對特徵點矢量的交叉角的比較。以同樣的方式，關於新創建的對應布置(Dl，，Ml，)，將布置D1，和鄰近特徵點P5 之間的位置關係數值與布置Ml』和鄰近特徵點Q5之間的位置關係數值相比較，如果布置關 係數值之間的差異在預定的可允許範圍之內，則分別將特徵點P5和Q5添加到布置D1』和 Ml，。將對應布置(D1』，M1』)替換成對應布置(D1」，M」)。因此，對應布置候選更新單元13繼續順序地執行對應布置候選的檢驗和更新。當 已針對所有對應布置候選完成了檢驗時，對應布置候選更新單元13記錄不再更新的對應 布置。已完成更新的對應布置候選(D1」，M1」)的特徵點對P1-Q1、P2-Q2、P3-Q3、P4-Q4和 P5-Q5被設置為對應布置候選的伴隨對應特徵點候選，其中這些特徵點對中的特徵點彼此 相對應。對應布置候選對應特徵點確定單元14對於已完成更新的對應布置候選，檢驗伴 隨對應布置候選的每個對應特徵點候選並確定對應布置候選的對應特徵點。基於對應特徵 點候選的鄰近特徵點的對應關係來執行每個對應特徵點候選的檢驗。需要該過程，因為當在對應布置候選更新單元13中添加對應鄰近特徵點時，新添 加的對應特徵點與已存在的伴隨對應特徵點候選之間可能並不滿足特徵點對應的一對一 特性。圖6A和圖6B示出了上述不滿足特徵點對應的一對一特性的對應布置。圖6A的 布置Dl和圖6B的布置Ml是對應布置候選。有必要確定布置Dl的鄰近特徵點(P4和P7) 與布置Ml的鄰近特徵點(Q4)之間的對應關係。然而，如果基於與對應布置(Dl，Ml)有關的信息來選擇該對應關係，則錯誤選擇的可能性很大。為此，為了儘可能保持實際對應特徵點，即使在對應布置候選更新單元13中不滿 足特徵點對應的一對一特性時，也將鄰近特徵點P4-Q4和P7-Q4添加到對應布置作為對應 鄰近特徵點。當已完成對應布置的更新時，可以執行以下過程對於並不滿足一對一特性的 對應特徵點候選，保存對應程度高的候選。基於鄰近區域中特徵點的對應程度來確定對應 程度，所述鄰近區域的中心是特徵點候選、例如對應特徵點的數目或其他。對應特徵點確定單元15評估已完成伴隨對應特徵點的確定的每個對應布置候 選，並得到最終對應布置和伴隨對應特徵點。可以通過使用以下方法來有效地執行對應布 置候選的評估基於對應布置候選的伴隨對應特徵點的數目來執行評估。一旦確定了對應 布置，就希望對應特徵點確定單元15輸出伴隨該對應布置的對應特徵點作為最終對應特 徵點。因此，在該示例實施例中，即使在要驗證的圖像之間產生了畸變，也可以抑制畸變 的效應並且可以對圖案之間的匹配進行驗證。此外，在該示例實施例中，即使在要驗證的圖 案之間產生畸變，也可以抑制畸變的效應並且可以執行圖案之間彼此相對應的對應特徵點 的提取。圖9示出了根據本發明第二示例實施例的圖案間特徵對應設備的示例配置的框 圖。在圖9中，圖案間特徵對應設備1包括CPU(中央處理單元)2和用於存儲供CPU 2執 行的程序的程序存儲單元3。在圖案間特徵對應設備1中，CPU 2執行存儲在程序存儲單元3中的程序，從而實 現由以上提到的圖案鄰近特徵點組布置創建單元11、對應布置候選檢測單元12、對應布置 候選更新單元13、對應布置候選對應特徵點確定單元14和對應特徵點確定單元15所執行 的處理。相應地，在本發明第二示例實施例的圖案間特徵對應設備中，CPU 2執行存儲在程 序存儲單元3中的程序，從而第二示例實施例的圖案間特徵對應設備具有與第一實施例的 圖案間特徵對應設備相同的效果。圖10示出了根據本發明第三示例實施例的圖案驗證設備的示例配置的框圖。在 圖10中，圖案驗證設備4包括搜索圖案特徵存儲單元41、參考圖案特徵存儲單元42、搜索 圖案鄰近特徵點組布置創建單元11a、參考圖案鄰近特徵點組布置創建單元lib、對應布置 候選檢測單元12、對應布置候選更新單元13、對應布置候選對應特徵點確定單元14、對應 特徵點確定單元15和驗證確定單元43。搜索圖案特徵存儲單元14 一併存儲從要搜索的圖案中檢測到的圖案特徵以及包 括其圖案特徵的位置數據在內的屬性數據。參考圖案特徵存儲單元42—並保存從參考圖 案中檢測到的圖案特徵以及包括圖案特徵的位置數據在內的屬性數據。搜索圖案鄰近特徵點組布置創建單元Ila檢測與搜索圖案特徵存儲單元41中保 存的圖案特徵數據的組合在位置上接近的特徵點的組合，作為搜索圖案側鄰近特徵點組布 置。參考圖案鄰近特徵點組布置創建單元lib檢測與參考圖案特徵存儲單元42中保存的 圖案特徵數據的組合在位置上接近的特徵點的組合，作為參考圖案側鄰近特徵點組布置。對應布置候選檢測單元12依次讀出搜索圖案鄰近特徵點組布置創建單元Ila和 參考圖案鄰近特徵點組布置創建單元lib檢測到的每個鄰近特徵點組布置數據，對於鄰近特徵點組布置，對特徵點間相對距離、交叉角、特徵點方向等進行比較，並通過強力方法來 檢測彼此相對應的對應特徵點組布置。對應布置候選更新單元13檢驗彼此相對應的特徵點組布置與該特徵點組布置的 鄰近特徵點之間關係的匹配，基於檢驗結果將鄰近特徵點添加到對應特徵點組布置作為對 應鄰近特徵點，並更新對應特徵點組布置。對應布置候選對應特徵點確定單元14對於已完成更新的每個對應布置候選，基 於對應特徵點候選的鄰近特徵點的對應程度來最終選擇伴隨對應布置候選的每個對應特 徵點候選，並確定對應特徵點。對應特徵點確定單元15評估已完成伴隨對應特徵點的確定 的每個對應布置候選，確定適當的對應布置並輸出伴隨該對應布置的對應特徵點。驗證確定單元43根據輸出至對應特徵點確定單元15的對應特徵點的數據來確定 圖案的匹配。例如，從對應特徵點的數目得到得分，當得分超過預定的閾值時，可以通過驗 證結果來確定圖案相互匹配。當根據該示例實施例的圖案驗證設備4用於指紋驗證系統(安全管理系統)時， 驗證確定單元43的確定結果用於例如允許進入建築物、允許進入建築物中的區域等等。在該示例實施例中，由於基於特徵點的局部位置關係來執行從圖案特徵點的輸入 過程到對應特徵點的確定過程的所有過程，所以與基於坐標匹配的對應特徵點確定設備相 比，即使當圖案具有畸變時，也可以以高精度來提取對應特徵點。因此，可以通過使用本示 例實施例來實現高精度圖案驗證。此外，搜索圖案鄰近特徵點組布置創建單元11a、參考圖案鄰近特徵點組布置創建 單元lib、對應布置候選檢測單元12、對應布置候選更新單元13、對應布置候選對應特徵點 確定單元14、對應特徵點確定單元15和驗證確定單元43所執行的全部或部分處理/功能 可以由在計算機上執行的程序來實現。本申請要求於2007年12月26日提交的日本專利申請No. 2007-333390的優先權， 其全部公開一併在此作為參考。工業應用本發明可以應用於諸如個人識別、個人身份確認或嫌犯搜索等應用中，在這些應 用中檢驗指紋圖案或掌紋圖案的匹配。
權利要求
一種圖案間特徵對應設備，包括產生裝置，用於將所輸入的圖案信號中彼此在位置上接近的N個特徵點設置為鄰近特徵點組，將鄰近特徵點組和布置關係數值組設置為特徵點組布置，並產生鄰近特徵點組、布置關係數值組和特徵點組布置中的至少一個，所述布置關係數值組表示鄰近特徵點組的特徵點之間的布置關係，N是大於等於2的整數，檢測裝置，用於執行對第一圖案的布置關係數值與由產生裝置產生的第二圖案的布置關係數值的比較，以檢測彼此相對應的對應特徵點組布置候選，更新裝置，用於對於對應特徵點組布置候選，執行對與每個特徵點組布置的特徵點和在位置上接近特徵點組布置的特徵點有關的布置關係數值的比較，分別將彼此相對應的鄰近特徵點添加到對應特徵點組布置候選，並更新對應特徵點組布置候選，用於檢驗由更新裝置更新的對應特徵點組布置候選的伴隨對應特徵點候選，以確定對應特徵點組布置候選的伴隨對應特徵點的裝置，以及用於檢驗對應特徵點組布置候選，以確定在圖案之間彼此相對應的對應特徵點的裝置。
2.根據權利要求1所述的圖案間特徵對應設備，包括用於檢測圖案信號中的流線並設 置與檢測到的流線的方向相對應的流線坐標系的裝置，通過將流線坐標系用作參考坐標系 來得到特徵點相關布置關係數值。
3.根據權利要求1所述的圖案間特徵對應設備，其中，特徵點相關布置關係數值包括 以下項目中的至少一項從一個特徵點看在參考坐標系中另一特徵點的距離； 從一個特徵點看在參考坐標系中其他兩個特徵點的方位角的偏移；以及 從一個特徵點看在參考坐標系中另一特徵點的特徵點方向的偏移。
4.根據權利要求1所述的圖案間特徵對應設備，其中，對於對應特徵點組布置候選，針 對以下項目來執行比較每個特徵點組布置的第一特徵點與在位置上接近對應特徵點組布 置的第二鄰近特徵點之間的距離，以及從第一特徵點看在第二鄰近特徵點與另一對應特徵 點組布置的第三特徵點之間的方位角偏移；將彼此相對應的鄰近特徵點添加到對應特徵點 組布置候選；以及更新對應特徵點組布置候選。
5.根據權利要求1所述的圖案間特徵對應設備，其中，對於對應特徵點組布置候選，針 對以下項目來執行比較在每個特徵點組布置的第一特徵點與在位置上接近特徵點組布置 的第二鄰近特徵點之間的距離，以及第二鄰近特徵點至第一特徵點的特徵點方向的偏移； 將彼此相對應的鄰近特徵點添加到對應特徵點組布置候選；以及更新對應特徵點組布置候 選。
6.根據權利要求1所述的圖案間特徵對應設備，其中，對於不滿足一對一特性的對應 特徵點候選，執行對更新裝置所更新的對應特徵點組布置候選的伴隨對應特徵點候選的檢驗。
7.根據權利要求1所述的圖案間特徵對應設備，其中，對更新裝置所更新的對應特徵 點組布置候選的伴隨對應特徵點候選的檢驗基於對應特徵點候選的鄰近特徵點的對應關係。
8.根據權利要求1所述的圖案間特徵對應設備，其中，對對應特徵點組布置候選的檢驗基於對應特徵點組布置候選的伴隨對應特徵點的數目。
9.一種圖案間特徵對應方法，包括第一步驟，在所述第一步驟中，將所輸入的圖案信號中彼此在位置上接近的N個特徵 點設置為鄰近特徵點組，將鄰近特徵點組和布置關係數值組設置為特徵點組布置，並產生 鄰近特徵點組、布置關係數值組和特徵點組布置中的至少一個，所述布置關係數值組表示 鄰近特徵點組的特徵點之間的布置關係，N是大於等於2的整數，第二步驟，在所述第二步驟中，執行對第一圖案的布置關係數值與在第一步驟中產生 的第二圖案的布置關係數值的比較，以檢測彼此相對應的對應特徵點組布置候選，第三步驟，在所述第三步驟中，對於對應特徵點組布置候選，執行對與每個特徵點組布 置的特徵點和在位置上接近特徵點組布置的特徵點有關的布置關係數值的比較，分別將彼 此相對應的鄰近特徵點添加到對應特徵點組布置候選，並更新對應特徵點組布置候選，第四步驟，在所述第四步驟中，檢驗在第三步驟中更新的對應特徵點組布置候選的伴 隨對應特徵點候選，以確定對應特徵點組布置候選的伴隨對應特徵點，以及第五步驟，在所述第五步驟中，檢驗對應特徵點組布置候選，以確定在圖案之間彼此相 對應的對應特徵點。
10.根據權利要求9所述的圖案間特徵對應方法，包括檢測圖案信號中的流線並設置 與檢測到的流線的方向相對應的流線坐標系的步驟，以及通過將流線坐標系用作參考坐標系來得到特徵點相關布置關係數值。
11.根據權利要求9所述的圖案間特徵對應方法，其中，特徵點相關布置關係數值包括 以下項目中的至少一項從一個特徵點看在參考坐標系中另一特徵點的距離；從一個特徵點看在參考坐標系中其他兩個特徵點的方位角的偏移；以及從一個特徵點看在參考坐標系中另一特徵點的特徵點方向的偏移。
12.根據權利要求9所述的圖案間特徵對應方法，其中，對於對應特徵點組布置候選， 針對以下項目來執行比較每個特徵點組布置的第一特徵點與在位置上接近對應特徵點組 布置的第二鄰近特徵點之間的距離，以及從第一特徵點看在第二鄰近特徵點與另一對應特 徵點組布置的第三特徵點之間的方位角偏移；將彼此相對應的鄰近特徵點添加到對應特徵 點組布置候選；以及更新對應特徵點組布置候選。
13.根據權利要求9所述的圖案間特徵對應方法，其中，對於對應特徵點組布置候選， 針對以下項目來執行比較在每個特徵點組布置的第一特徵點與在位置上接近特徵點組 布置的第二鄰近特徵點之間的距離，以及第二鄰近特徵點至第一特徵點的特徵點方向的偏 移；將彼此相對應的鄰近特徵點添加到對應特徵點組布置候選；以及更新對應特徵點組布 置候選。
14.根據權利要求9所述的圖案間特徵對應方法，其中，對於不滿足一對一特性的對應 特徵點候選，執行對在第三步驟中更新的對應特徵點組布置候選的伴隨對應特徵點候選的 檢驗。
15.根據權利要求9所述的圖案間特徵對應方法，其中，對在第三步驟中更新的對應特 徵點組布置候選的伴隨對應特徵點候選的檢驗基於對應特徵點候選的鄰近特徵點的對應 關係。
16.根據權利要求9所述的圖案間特徵對應方法，其中，對對應特徵點組布置候選的檢 驗基於對應特徵點組布置候選的伴隨對應特徵點的數目。
17.一種程序，所述程序允許圖案間特徵對應設備中的中央處理單元執行處理，以通過 使用圖案的特徵點信息使圖案間特徵彼此相對應，所述程序包括以下進程第一進程，在所述第一進程中，將所輸入的圖案信號中彼此在位置上接近的N個特徵 點設置為鄰近特徵點組，將鄰近特徵點組和布置關係數值組設置為特徵點組布置，並產生 鄰近特徵點組、布置關係數值組和特徵點組布置中的至少一個，所述布置關係數值組表示 鄰近特徵點組的特徵點之間的布置關係，N是大於等於2的整數，第二進程，在所述第二進程中，執行對第一圖案的布置關係數值與在第一進程中產生 的第二圖案的布置關係數值的比較，以檢測彼此相對應的對應特徵點組布置候選，第三進程，在所述第三進程中，對於對應特徵點組布置候選，執行對與每個特徵點組布 置的特徵點和在位置上接近特徵點組布置的特徵點有關的布置關係數值的比較，分別將彼 此相對應的鄰近特徵點添加到對應特徵點組布置候選，並更新對應特徵點組布置候選，第四進程，在所述第四進程中，檢驗在第三進程中更新的對應特徵點組布置候選的伴 隨對應特徵點候選，以確定對應特徵點組布置候選的伴隨對應特徵點，以及第五進程，在所述第五進程中，檢驗對應特徵點組布置候選以確定在圖案之間彼此相 對應的對應特徵點。
全文摘要
一種圖案間特徵對應設備(1)，用於即使在要比較的圖案有畸變的情況下也以高精度來確定特徵對應關係。該設備(1)包括產生其中的特徵點在圖案中的位置彼此接近的鄰近特徵點組和將鄰近特徵點組的特徵點之間的位置關係指示為特徵點組位置的位置關係數值的裝置(11)；比較所產生的位置關係數值以檢測對應特徵點組位置候選的裝置(12)；比較對應特徵點組位置候選的每個特徵點組位置的特徵點與鄰近特徵點組位置的特徵點之間的位置關係數值，將對應鄰近特徵點添加到對應特徵點組位置候選，並更新對應特徵點組位置候選的裝置(13)；檢查更新後的對應特徵點組位置候選的相關對應特徵點候選以設置對應特徵點組位置候選的相關對應特徵點的裝置(14)；以及檢查對應特徵點組位置候選以設置圖案間對應特徵點的裝置(15)。
文檔編號G06T7/00GK101911115SQ20088012290
公開日2010年12月8日 申請日期2008年12月19日 優先權日2007年12月26日
發明者黃雷 申請人:日本電氣株式會社