[發明專利]一種從m部圖中得到極大完全子圖的數據庫搜索方法

有效

• 申請號: 201710132397.3
• 申請日: 2017-03-07
• 公開（公告）號: CN107038215B
• 公開（公告）日: 2020-07-17
• 發明（設計）人: 殷永;李越
• 申請（專利權）人: 東方網力科技股份有限公司
• 主分類號: G06F16/583
• 分類號: G06F16/583;G06K9/00
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 皋吉甫

本發明提供一種從m部圖中得到極大完全子圖的數據庫搜索方法，所述搜索方法應用于從人臉識別數據庫，所述方法通過建立無向圖模型，構成一個k階極大完全子圖，并通過鄰接鏈表來存儲無向圖G，以正序邊和最大頂點為基本量，通過剪枝法對無向圖G的頂點數和k階完全子圖的計算量T_k進行計算，從而得到該極大完全子圖的空間復雜度和時間復雜度，完成對極大完全子圖的搜索，并將搜索結果用于人臉識別數據中，通過尋找頻繁項集，大幅減少對數據庫的訪問，提高識別效率。

技術領域

本發明屬于人臉研判分析系統技術領域，具體涉及一種從m部圖中得到極大完全子圖的數據庫搜索方法。

背景技術

極大完全子圖有著十分廣泛的應用。在管理決策方面，一些管理事物問題如人員管理、運輸調度等均可抽象為求解極大完全子圖問題。在數據挖掘方面，關聯規則的挖掘是數據挖掘研究的重要內容之一，利用極大完全子圖來尋找頻繁項集，可以在很大程度上減少對數據庫的訪問，提高CPU的利用率。

最大完全子圖問題是一個著名的組合優化問題，它也是最早被證明的NP-完全問題之一。由于理論研究及應用的需要，人們致力于尋找一些可行的算法。總體上分為兩類：一類是求解最大完全子圖的確定性算法，如上個世紀80年代提出的深度優先列舉算法。另一類是求解最大完全子圖的啟發式算法，如順序貪婪啟發式算法。這些算法無論是確定性算法還是啟發式方法，其尋找完全子圖的過程大部分都是先尋找極大完全子圖集，再從中找出頂點個數最多的作為最大完全子圖。因此，研究有效的極大完全子圖算法既具有理論意義也具有應用價值。

重慶大學計算機學院和東北大學機械工程與自動化學院的郭平、康艷榮、史曉晨于2006年在計算機科學學報上發表論文《基于最大Code碼的極大完全子圖搜索算法》。論文中提出了一種尋找圖的極大完全子圖的FMCSG算法，該算法基于逆導出子圖概念，首選將圖分解成若干個逆導出子圖，然后找出每個逆導出子圖的所有極大完全子圖，從而得到原圖的所有極大完全子圖。該算法用鄰接矩陣表示圖，在尋找極大完全子圖時根據得到的code碼及時減掉非極大code碼的子矩陣，從而減少對矩陣的遍歷次數，提高了算法的效率。

云南師范大學信息學院的時燕和張玉琢與2016年在電腦知識與技術學報上發表論文《一種改進的極大完全子圖挖掘算法》。論文主要是針對郭平等人提出的FMCSG算法進行了改進，并設計了相關的數據結構，提升了算法的運行效率。其核心操作是在由階矩陣生成階矩陣時，依據一定的規則，避免一些不必要的判斷操作。

現有的極大完全子圖搜索算法的研究對象都是普通圖，這類算法的時間復雜度和空間復雜度都比較高。比如，當圖的頂點個數為n時，基于最大Code碼的極大完全子圖搜索算法的時間復雜度為T(n)＝T(n-1)*T(n-1)+O(n²)，空間復雜度為O(n²)。改進的極大完全子圖挖掘算法雖然做了一些優化，但是時間復雜度和空間復雜度的量級并沒有改變。本發明針對一種比較特殊的圖—m部圖提出了搜索其所有的k(3≤k≤m)階極大完全子圖的算法。m部圖不同于普通圖之處在于它的所有頂點可以劃分為多個集合，任意一條邊的兩個頂點都是來自于不同的集合。

軌跡查人功能是指用戶在地圖上通過標注多個點位操作或者多次框選區域操作勾畫出一條運動軌跡，系統可找出運動軌跡和指定軌跡具有一定吻合度的人員及其對應的活動詳情，同時計算出每個人員的運動軌跡與指定軌跡的吻合度。此功能主要用于刑偵、科研以及一些安全領域，用戶只需要掌握一個大概的時間范圍和目標人物的活動軌跡，即可通過軟件的智能分析將目標人員從海量人臉照片數據中挖掘出來。

運動軌跡上的每一個節點對應現實場景中的一個區域，每個區域架設數量不等的人臉相機。在一定時間范圍內，每個區域的人臉相機都會采集到很多數量的人臉照片。分別從多個不同的區域中按照時間先后順序拿出多張人臉照片，若它們是同一個人的照片，我們就找到了活動軌跡與指定軌跡具有一定吻合度的人員。由于人臉比對之間總會存在一些誤差，所以比較合理的做法就是：若多張人臉照片兩兩相似度較高，就認為它們是同一個人的照片。