[發明專利]一種基于譜匹配的三維網格模型的匹配方法

無效

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

技術領域

本發明涉及一種點模式匹配技術，尤其是涉及一種基于譜匹配的三維網格模型的匹配方法。

背景技術

點模式(或稱點集)匹配技術廣泛應用于圖像配準、圖像分類與檢索、目標識別、形狀匹配和立體視覺等領域。目前，點模式匹配算法大致可以分為兩大類：第一類是基于變換關系求解的算法，其通過估計點模式之間的空間變換參數，利用該空間變換參數恢復或模擬點模式間的變換，從而求解點模式匹配問題，也稱之為基于變換參數估計的算法，這類算法主要有迭代最近點算法、軟指派算法等；第二類是基于匹配關系求解的算法，其通過提取點集中點的特征，而后運用匹配識別方法獲得點模式間的匹配關系，從而求解點模式匹配問題，這類算法可更形象地稱為基于特征的匹配算法。

圖匹配方法是基于匹配關系求解的算法中較新穎的一種方法。圖作為一個基本的數據結構，其可以用來有效地代表了許多計算機視覺應用中的各種對象。一般來說，圖的頂點主要包含的是從圖像局部區域、輪廓或者興趣點中提取的重要信息。只要選擇一種恰當的圖結構表示方法，總是可以把許多應用轉換為圖匹配問題加以解決，如目標識別、形狀匹配、寬基線立體視、二維或三維配準等。

一般地，圖匹配問題是在兩個特征集合之間找到一種一致對應關系，使得兩個特征集合間對應的特征盡可能相似。作為一個計算機科學的基礎理論問題，它關系到計算機視覺、模式識別、機器學習和其他許多研究課題。圖匹配方法在過去的三十年間取得了長足的發展。十年前，很多圖匹配方法都沒有一個精確定義的目標函數，只有一個簡單的迭代形式來計算一元局部屬性和二元幾何屬性。近幾年，很多利用優化組合的特征匹配方法被提出，改變了這種局面。最近，計算機視覺中的大部分的圖匹配工作被形式化為二次整數規劃問題，并用屬性圖結構化地描述復雜的一元局部屬性和兩兩一元屬性間的二元幾何屬性。

一個屬性圖包括頂點集合和這些頂點之間的邊的集合。這些頂點代表一元局部特征，而它們的邊及邊的權值則代表一元局部特征間的二階關系。一元局部特征一般包含局部表觀特征描述子，這些描述子可以是興趣點、圖像區域、局部顏色、紋理或者形狀等等。對于某些間題來說，這些一元局部特征是沒有區分度的或者它們的區分度不足，這時就有必要使用包含二階關系的二元特征以輔助匹配，從而找到正確的對應關系。這些二階關系可以包括空間幾何關系或者其它的兩兩局部表觀特征間的信息，它們作為邊的權值保存在圖的邊集中。一般來說，圖匹配被形式化地描述為尋找兩個圖的對應關系的問題。為了保證結果最優，必須保持兩個圖的頂點上的一元信息和邊上的二元信息盡可能同時一致。從數學上說，圖匹配可以形式化地描述為一個求特定目標函數最優化的問題，一般稱為二次整數規劃問題。由于二次整數規劃是一個NP問題，因此必須找到原問題的一個近似最優解。

目前，有很多近似最優化方法被應用于圖匹配問題上，比如：遺傳算法、神經網絡、EM(estimate?maximize)算法、分層指派(graduated?assignment)算法和譜方法等等。其中，譜方法基于這樣一個觀察：一個圖的鄰接矩陣的特征值和特征向量對不同的頂點排列具有不變性，因此兩個同構圖的鄰接矩陣具有同樣的特征值和特征向量。但這個結論的逆命題并不成立，所以不能根據對應的特征值和特征向量相等來判定兩個圖的同構性。然而，因為特征值和特征向量的計算相對簡單，可以在多項式時間內完成，所以譜方法非常適合圖匹配問題。

基于譜圖理論的圖匹配方法是一類利用鄰接矩陣或者與其密切相關的Laplacian矩陣的特征值和特征矢量來刻畫點集全局結構的方法。Scott和Longuet-higgins首次將譜方法應用于點模式匹配中，即通過定義點集之間的親近矩陣，并對該親近矩陣進行SVD(Sigular?Value?Decomposition，奇異值分解)操作，以獲得對應關系，這種方法可處理不同大小的點集，但對較大角度的旋轉效果不好。為了克服上述方法的不足，Shapiro和Brady采用了點集內部點的親近矩陣來進行匹配，這種方法對待匹配的每一個點集，首先利用其內部點之間距離的高斯函數值來構造親近矩陣，然后分別計算親近矩陣的特征值和特征向量，其對應關系可以通過比較點集親近矩陣的有序特征向量來獲得，若所需匹配的點集大小相同，則這種方法對隨機點抖動和較小的仿射變換都可以給出相對較好的結果。