[發明專利]一種無向圖匹配的方法、設備和存儲介質

在審

• 申請號: 201711124245.5
• 申請日: 2017-11-14
• 公開（公告）號: CN109784353A
• 公開（公告）日: 2019-05-21
• 發明（設計）人: 錢德恒;張輝;俞炳仁
• 申請（專利權）人: 北京三星通信技術研究有限公司;三星電子株式會社
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06K9/46
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 錢大勇

本申請涉及一種計算機實施的將無向圖進行匹配的方法，包括：接收第一無向圖和第二無向圖；獲得分別與第一無向圖和第二無向圖對應的第一點陣和第二點陣；以及對第一點陣和第二點陣進行匹配。通過所述通信方法，可以將無向圖的匹配問題轉化為點陣之間的匹配問題，從而降低求解的復雜度，并提高匹配的精度。

技術領域

本申請涉及模式識別和計算機視覺領域，具體而言，本申請涉及一種用于處理無向圖的匹配問題的方法和設備。

背景技術

在由多個點構成的圖中，點之間的邊沒有方向的圖被稱為無向圖。在實際應用中，無向圖模型是一種廣泛采用的數學模型，它可以用來表達各種關系和過程。一般說來，多個無向圖的匹配可以用于圖像拼接、物體的位置和姿態估計等問題。無向圖的匹配的效率和精度，在很大程度上將會影響這些問題的處理結果。

特別的，在圖像拼接中的某些應用場景下，一些傳統的圖匹配算法將會失效。例如，如圖1中所示的場景，其中的圖像主要是重復的紋理，以及如圖2中所示的場景，其中的圖像缺乏灰度的變化；在類似于圖1和圖2的應用場景下，基于點的局部特征(例如SIFT(Scale-invariant feature transform，尺度不變特征變換)特征)的圖匹配算法豆漿失效。此時，必須使用基于點之間結構信息的圖匹配算法。

二次指派問題是運籌學中的一種模型，對該問題的求解屬于NP難問題。對無向圖的匹配問題，現有技術的一種主要處理方式是將該問題表達成一個二次指派問題，然后求該問題的近似解。具體而言，可以將無向圖視為一個圖模型G，其包含節點V和邊E，其中，邊E是沒有方向的。一個無向圖的點V和邊E分別有相應的特征F和W。對兩個無向圖進行匹配其實就是要將這兩個無向圖的點和邊的特征進行匹配。二次指派問題就是要對某個目標函數進行優化，從而使得兩個無向圖之間點和邊之間相互匹配的特征的相似性達到最大化。

由于對二次指派問題的求解屬于NP難問題，因此一般而言，沒有算法可以在多項式時間內找到相應的目標函數的最優解。在實踐中，現有的算法主要在于對該問題進行近似求解，然而，這些現有算法所獲得的匹配精度比較低，并且時間復雜度較高。尤其是當形變較大、受噪聲或外點污染、或者無向圖模型的規模較大時的匹配的情況下，現有的算法難以處理對目標函數的近似最優解的求解。

發明內容

本申請的目的旨在至少解決上述技術缺陷之一，通過采用圖模型來刻畫結構信息。然后匹配兩個圖模型，找出兩幅圖像中的對應關系，進而實現圖像的拼接。特別地，可以通過利用一個點陣來表達無向圖，其中無向圖的特征通過點陣的特征來表達。通過這種方法，可以將無向圖的匹配問題轉換成為點陣的匹配問題，從而不需要對上述的二次指派問題進行求解，因此降低了計算匹配的復雜度并提高了處理的精度。

根據本申請的一方面，提供了一種計算機實施的將無向圖進行匹配的方法，包括：接收第一無向圖和第二無向圖；獲得分別與第一無向圖和第二無向圖對應的第一點陣和第二點陣；以及對第一點陣和第二點陣進行匹配。

根據本申請的另一方面，提供了一種將無向圖進行匹配的計算機系統，包括：處理器；以及存儲器，其上存儲有可由所述處理器執行的指令，當所述指令由所述處理器執行時，使得所述處理器執行如下步驟：接收第一無向圖和第二無向圖；獲得分別與第一無向圖和第二無向圖對應的第一點陣和第二點陣；以及對第一點陣和第二點陣進行匹配。

根據本申請的另一方面，提供了一種機器可讀的存儲介質，其上存儲有可由所述機器執行的指令，當所述指令由所述機器執行時，使得所述機器執行如下步驟：接收第一無向圖和第二無向圖；獲得分別與第一無向圖和第二無向圖對應的第一點陣和第二點陣；以及對第一點陣和第二點陣進行匹配。

通過本申請提出的將無向圖進行匹配的方法、設備及存儲介質，能夠有效地解決對無向圖進行匹配的問題，降低處理的復雜度并提高匹配的精度。

附圖說明