[發明專利]基于拓撲關系的復雜序列圖形匹配系統及其實現方法

無效

• 申請號: 201010193054.6
• 申請日: 2010-06-03
• 公開（公告）號: CN101894274A
• 公開（公告）日: 2010-11-24
• 發明（設計）人: 張寶印;沈學如
• 申請（專利權）人: 江蘇如意通動漫產業有限公司
• 主分類號: G06K9/64
• 分類號: G06K9/64
• 代理公司: 南京天華專利代理有限責任公司 32218
• 代理人: 徐冬濤

1.一種基于拓撲關系的復雜序列圖形匹配系統，其特征是包括：

識別、提取模塊，用于將前一幀圖形中各多邊形，得到具有相互分離的頂點集合V，以及識別、提取與前一幀相鄰的后一幀圖形中各多邊形，得到具有相互分離的頂點集合W；

有向化模塊，用于將頂點集合V中各元素指向頂點集合W連線，進行有向化，得到連接邊和有向偶圖，獲得前一幀圖形中各多邊形的集合與后一幀圖形中各多邊形的集合中每一個多邊形的拓撲關系；

匹配網絡，用于將有向偶圖形成匹配網絡；

最大流量求解模塊，利用最大流量法獲得匹配網絡中各個連接邊的最大結果流量；

關聯匹配模塊，將獲得的最大結果流量與匹配網絡進行關聯，對頂點集合V和頂點集合W中各元素進行匹配：

完整匹配輸出模塊，根據關聯結果進行前一幀圖形中各多邊形與后一幀圖形中各多邊形的匹配，最終完成前一幀圖形與后一幀圖形的匹配。

2.根據權利要求1所述的基于拓撲關系的復雜序列圖形匹配系統，其特征是所述有匹配網絡中包括超級源s和超級匯z，超級源s到超級匯z之間有若干條通路P。

3.根據權利要求2所述的基于拓撲關系的復雜序列圖形匹配系統，其特征是所述通路P上每條邊是一致定向的并且每條邊上的流量小于通路P流量。

4.根據權利要求1或3所述的基于拓撲關系的復雜序列圖形匹配系統，其特征是還包括查找模塊，用于在匹配網絡中查找通路P；

還包括流量增加模塊，用于沿查找到的通路P增加流量。

5.一種基于拓撲關系的復雜序列圖形匹配的實現方法，其特征是包括以下步驟：

A)識別、提取前一幀圖形中各多邊形，得到具有相互分離的頂點集合V，識別、提取與前一幀相鄰的后一幀圖形中各多邊形，得到具有相互分離的頂點集合W；

B)將頂點集合V中各元素指向頂點集合W連線，得到連接邊，獲得前一幀圖形中各多邊形的集合與后一幀圖形中各多邊形的集合中每一個多邊形的拓撲關系；

C)利用頂點集合V和頂點集合W形成匹配網絡Gt；

D)利用最大流量法獲得步驟C)中匹配網絡Gt中各個連接邊的最大結果流量；

E)將步驟C獲得的最大結果流量與匹配網絡進行關聯，對頂點集合V和頂點集合W中各元素進行匹配：

若從頂點集合V的子集v指向頂點集合W的子集w的邊(v，w)的流量為1，則頂點集合V的子集v與頂點集合W的子集w匹配，則得到匹配網絡的流量給出的一個匹配；

若獲得最大結果流量，則得到最大匹配；

若最大結果流量的值為|V|，則得到完全匹配；

F)根據步驟E的關聯結果進行前一幀圖形中各多邊形與后一幀圖形中各多邊形的匹配，最終完成前一幀圖形與后一幀圖形的匹配。

6.根據權利要求5所述的基于拓撲關系的復雜序列圖形匹配的實現方法，其特征是所述步驟C利用頂點集合V和頂點集合W形成匹配網絡Gt包括以下步驟：

設G是具有相互分離的頂點集合V和W的有向偶圖，其中每條邊的方向從V中的頂點指向W中的頂點，在有向偶圖G中引入超級源s和超級匯z；

將超級源s指向頂點集合V中各元素的每條邊賦值容量1，將頂點集合V中各元素指向頂點集合W中各元素的每條邊賦值容量1，將頂點集合W中各元素指向超級匯z的每條邊賦值容量1，形成匹配網絡Gt。

7.根據權利要求5所述的基于拓撲關系的復雜序列圖形匹配的實現方法，其特征是所述步驟D包括以下步驟：

a)從匹配網絡Gt的一個流量開始，查找匹配網絡Gt中超級源s到超級匯z的一條通路P，該通路P上每條邊是一致定向的并且每條邊上的流量小于通路P流量；

b)若滿足上述條件的通路P不存在，則結束查找，通路P上每條邊的流量是最大結果流量；

c)若查找到滿足上述條件的通路P，則沿該通路增加流量△，直到查找不到滿足上述條件的通路P，則返回步驟b。

8.根據權利要求7所述的基于拓撲關系的復雜序列圖形匹配的實現方法，其特征是所述流量△＝minX，X由數C_ij-F_ij組成；其中C_ij為通路P的流量，F_ij為通路P中一致定向的邊(i，j)的流量。