[發明專利]分階段的精確形狀匹配方法

有效

• 申請號: 201711211932.0
• 申請日: 2017-11-27
• 公開（公告）號: CN107978010B
• 公開（公告）日: 2021-03-05
• 發明（設計）人: 楊文武
• 申請（專利權）人: 浙江工商大學
• 主分類號: G06T13/00
• 分類號: G06T13/00
• 代理公司: 杭州杭誠專利事務所有限公司 33109
• 代理人: 尉偉敏;閻忠華

1.一種分階段的精確形狀匹配方法，其特征是，包括如下步驟：

(1-1)設定源形狀中線條的“模糊拓撲”；

(1-1-1)給定一個由一組線條組成的源形狀{S_i}，設S為源形狀中的任一根線條；其中，μ_S(S_i)為線條S_i的各個端點到線條S的最小距離；

(1-1-2)給定一個閾值α，對于形狀中的任意一對線條S_i和S_j，如果或者則稱線條S_i和S_j之間存在內在連接關系，也稱為α-連接；

(1-1-3)設S在源形狀中的“模糊拓撲”為一個有序點集，記為F_s＝{p₁，p₂，...，p_k，...}；

有序點集具有如下屬性：

每個點p_k均與{S_i}中的一條線條相關聯，所述線條與線條S之間存在α-連接關系，并且F_S中不存在兩個點關聯到{S_i}中的同一根線條；

令S_k為與p_k相關聯的線條，如果則p_k對應著S的一個端點；否則，若μ_S(S_k)≤α，則p_k為S_k的某個端點在S上的投影點；p_k在F_S中的次序由其在線條S上從初始頂點到末尾頂點的先后位置決定；

(1-2)設定目標形狀中線條的“模糊拓撲”；

(1-2-1)給定一個由一組線條組成的目標形狀{T_j}，設T為目標形狀中的任一根線條，其中，μ_T(T_j)為線條T_j的各個端點到線條T的最小距離；

(1-2-2)對于形狀中的任意一對線條T_i和T_j，如果或者則稱線條T_i和T_j之間存在內在連接關系，也稱為α-連接；

(1-2-3)設T在目標形狀中的“模糊拓撲”為一個有序點集，記為F_T＝{q₁，q₂，...，q_k，...}；

有序點集F_T＝{q₁，q₂，...，q_k，...}具有如下屬性：

每個點q_k與{T_j}中的一條線條相關聯，所述線條與線條T之間存在α-連接關系，并且F_T中不存在的兩個點關聯到{T_j}中的同一根線條；

令T_k為與q_k相關聯的線條，如果則q_k對應著T的一個端點；否則，若μ_T(T_k)≤α，則q_k為T_k的某個端點在T上的投影點；q_k在F_T中的次序由其在線條T上從初始頂點到末尾頂點的先后位置決定；

(1-3)分階段進行形狀匹配

分兩個階段建立源形狀{S_i}和目標形狀{T_j}之間線條的一一對應關系，包括如下步驟：

(4-1)第一階段

(4-1-1)分別把源形狀中的每一根線條匹配到目標形狀中的每一根線條，然后選取擁有最大匹配度的一對線條,作為一對對應線條,并作為初始種子；

(4-1-2)給定一對對應線條(S_i,T_j)，以(S_i,T_j)為依據從源形狀和目標形狀的尚未建立對應關系的線條中，生成一組可能的對應線條對，并放入到一個候選對應線條列表中；

(4-1-3)從候選對應線條列表中，提取出具有最大匹配度的線條對，并在該對線條之間建立對應關系，同時把該對線條作為一個新的種子；

(4-1-4)重復步驟(4-1-2)和(4-1-3)，直到候選對應線條列表為空；

(4-2)第二階段

(4-2-1)把第一階段生成的對應線條對作為初始種子；

(4-2-2)給定一對對應線條(S_i,T_j)，令N(S_i)為與線條S_i相鄰的線條的集合、N(T_j)為與線條T_j相鄰的線條的集合，通過匹配N(S_i)中的每一根線條到N(T_j)中的每一根線條，依次生成一組可能的對應線條；

(4-2-3)從候選對應線條列表中，提取出具有最大匹配度的線條對，并在該對線條之間建立對應關系，同時把該對線條作為一個新的種子；

(4-2-4)重復運行(4-2-2)和(4-2-3)，直到候選對應線條列表為空。

2.根據權利要求1所述的分階段的精確形狀匹配方法，其特征是，步驟(4-1-2)包括如下步驟：

(5-1)當且僅當集合F_S和F_T具有相同個數元素時，線條S_i的模糊拓撲F_S與線條T_j的模糊拓撲F_T同構；

(5-2)對F_S中的每個元素p_k及其在F_T中的對應元素q_k，令S_k為p_k的關聯線條、T_k為q_k的關聯線條，通過匹配S_k與T_k生成一對可能的對應線條對(S_k,T_k)。