[發(fā)明專利]一種基于譜匹配的三維網(wǎng)格模型的匹配方法

無效

• 申請?zhí)枺?/td>: 201110211719.6
• 申請日: 2011-07-27
• 公開（公告）號: CN102289661A
• 公開（公告）日: 2011-12-21
• 發(fā)明（設(shè)計）人: 趙杰煜;任振華;劉定鳴;秦配偉
• 申請（專利權(quán)）人: 寧波大學(xué)
• 主分類號: G06K9/00
• 分類號: G06K9/00;G06T17/00
• 代理公司: 寧波奧圣專利代理事務(wù)所(普通合伙) 33226
• 代理人: 程曉明;周玨

1.一種基于譜匹配的三維網(wǎng)格模型的匹配方法，其特征在于包括以下步驟：

①分別選取兩個待匹配的三維網(wǎng)格模型中的角點作為各自的關(guān)鍵點，每個關(guān)鍵點所包含的特征為其自身的三維坐標(biāo)值，將從其中一個三維網(wǎng)格模型中提取得到的關(guān)鍵點的集合定義為模板點集，記為P，P＝{p_i|i＝1，2，…，n_p}，將從另一個三維網(wǎng)格模型中提取得到的關(guān)鍵點的集合定義為目標(biāo)點集，記為Q，Q＝{q_j|j＝1，2，…，n_q}，其中，p_i表示模板點集P中的第i個關(guān)鍵點，n_p表示模板點集P中關(guān)鍵點的個數(shù)，q_j表示目標(biāo)點集Q中的第j個關(guān)鍵點，n_q表示目標(biāo)點集Q中關(guān)鍵點的個數(shù)；

②根據(jù)模板點集P和目標(biāo)點集Q構(gòu)造分配圖及分配圖的親近矩陣，具體過程為：

②-1、定義模板點集P中的關(guān)鍵點與目標(biāo)點集Q中的關(guān)鍵點組成的組合為分配；

②-2、設(shè)置一個加權(quán)無向圖G，將模板點集P中的各個關(guān)鍵點與目標(biāo)點集Q中的各個關(guān)鍵點組成的所有可能的分配的集合作為加權(quán)無向圖G的頂點的集合，并記為V(G)，V(G)＝{v₁，v₂，…，v_n}，將加權(quán)無向圖G的無向邊的集合記為E(G)，E(G)＝{e₁，e₂，…，e_m}，其中，v_s＝(p_i，q_j)表示V(G)中的第s個頂點，s∈[1，n]，n＝n_p×n_q，p_i∈P，q_j∈Q，e_k＝{v_s，v_t}表示以V(G)中的第s個頂點v_s和第t個頂點v_t為端點的無向邊，k∈[1，m]，v_t＝(p_i′，q_j′)，p_i′∈P，q_j′∈Q，i′[1，n_p]，j′∈[1，n_q]，t∈[1，n]，s≠t；然后將無向邊e_k上的權(quán)值表示為w{v_s，v_t}；

②-3、根據(jù)加權(quán)無向圖G中的任意兩個頂點各自所代表的分配與一對一匹配的約束條件是否相矛盾，確定以該兩個頂點為端點的無向邊的權(quán)值，具體過程為：設(shè)v_s＝(p_i，q_j)和v_t＝(p_i′，q_j′)為當(dāng)前在加權(quán)無向圖G中任意所取的兩個頂點，判斷(p_i＝p_i′)and(q_j≠q_j′)或(p_i≠p_i′)and(q_j＝q_j′)是否成立，如果成立，則表示v_s和v_t各自所代表的分配與一對一匹配的約束條件相矛盾，確定以v_s和v_t為端點的無向邊e_k上的權(quán)值w{v_s，v_t}＝0，否則，表示v_s和v_t各自所代表的分配與一對一匹配的約束條件不相矛盾，然后根據(jù)三維網(wǎng)格模型中的關(guān)鍵點的幾何關(guān)系，確定以v_s和v_t為端點的無向邊e_k上的權(quán)值其中，e為自然對數(shù)的底數(shù)，“||”為絕對值符號，表示p_i與p_i′之間的歐氏距離，表示q_j與q_j′之間的歐氏距離，σ²表示尺度變化參數(shù)；

②-4、將加權(quán)無向圖G作為分配圖，將分配圖表示為n×n的親近矩陣M，親近矩陣M的對角元素M(v_s，v_s)表示v_s＝(p_i，q_j)中p_i與q_j的特征之間的相似性度量，M(v_s，v_s)＝0，親近矩陣M的非對角元素M(v_s，v_t)表示以v_s和v_t為端點的無向邊e_k上的權(quán)值，M(v_s，v_t)＝w{v_s，v_t}，其中，n＝n_p×n_q；

③對分配圖的親近矩陣M進行譜分析，獲得親近矩陣M的主特征向量；

④根據(jù)線性代數(shù)中的Rayleigh定理，采用基于貪婪思想的譜匹配算法對親近矩陣M的主特征向量進行迭代處理，得到二值化后的解向量x，該解向量x為兩個三維網(wǎng)格模型匹配的近似最優(yōu)解。