數據算法_組合優化_匈牙利算法

組合優化問題 (Combinatorial optimization problem,COP)

 是一類在離散狀態下求極值的最優化問題二分圖(Bipartite graph)  匹配是由一組沒有公共端點的邊構成的集合。   U與V之間的關聯視為前一幀與當前幀的同一id目標的檢測框的關聯數據關聯是多目標跟蹤任務中的關鍵步驟,    運籌學方法,比較經典的即為匈牙利匹配算法和KM算法-傳統方法被計算量限制,   數據關聯的最大瓶頸是計算量爆炸的問題-只需要用一個方法找到最優解即可。從這個角度,問題變成了一個分配問題求最優解的過程    隨機有限集(RFS)理論-實現長時間追蹤一百萬數量以上的目標

匈牙利算法(Hungarian algorithm

匈牙利算法主要用來解決兩個問題:求二分圖的最大匹配數和最小點覆蓋數匈牙利算法計算  1. 算法條件     求目標函數的最小值     人數和任務數相等     效率非負  2.算法本質:變換系數矩陣(效率),找到n個不同行不同列的0,使指派問題達到最優

jonker-volgenant算法

(也稱lapjv算法)是一個比匈牙利解法更快的算法

KM算法

KM算法(Kuhn-Munkres Algorithm)   KM算法解決的是帶權二分圖的最優匹配問題,即引入了權值這     引入了權值作為約束條件,可以使匹配成功率大大提高   

場景

 場景是這樣,檢測中有9個ground truth,我預測了10個檢測,他們和每個ground truth的IOU矩陣如下   需要把最合適的預測和標簽綁定到一起,并且每個預測和標簽只能使用一次    混淆矩陣 Confusion Matrix  IOU(交并比)矩陣  cost: 距離計算處理出來的,具體有余弦距離,歐氏距離和IOU距離目標跟蹤(Object-Tracking)  利用檢測+跟蹤的模式  利用將檢測器和re-id模型兩個結合成一個網絡結構,這    單目標跟蹤典型算法有:Mean Shift、TLD(基于在線學習的跟蹤)、KCF(基于相關濾波性)  DFT(Deteciton-Free Tracking) 需要人工標定視頻的第一幀圖像中的目標,之后邊檢測邊跟蹤,常用于單目標跟蹤    Multi-Object-Tracking 多目標跟蹤算法典型有:SORT、DeepSORT      TBD(Tracking-by-Detecton),又或者也可叫DBT(Detection-Based-Tracking)     在線跟蹤(Online Tracking)和離線跟蹤(Offline Tracking)    Deepsort的前身是sort算法,sort算法的核心是卡爾曼濾波算法和匈牙利算法    而Deepsort算法在sort算法的基礎上增加了級聯匹配(Matching Cascade)和新軌跡的確認(confirmed)    跟蹤框與檢測框:     卡爾曼濾波(Kalman filtering)是一種利用線性系統狀態方程,它將兩個都不是那么可靠的方式做了融合,從而可以有效抵抗噪點等外部影響,得到相對準確的預測值?？柭鼮V波算法就是根據你檢測框的位置去預測目標在下一幀的位置檢測框與跟蹤框(卡爾曼濾波預測出來的跟蹤框)他們匹配起來,找到最優(最佳)的匹配,從而實現跟蹤  多目標跟蹤算法benckmark   數據集 算法評價指標

代碼示例

import numpy as npfrom scipy.optimize import linear_sum_assignmentif __name__ == '__main__':    ## data    base_row = ["a","b","c"]    comp_col = ["x","z","y"]    #square matrix     cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])    base_row = ["a","b","c"]    comp_col = ["x","z","y","i"]    # rectangular  matrix    cost = np.array([[4, 1, 3,3], [2, 0, 5,7], [3, 2, 2,0]])    ## method    row_ind, col_ind = linear_sum_assignment(cost)    print(row_ind,"$")#開銷矩陣對應的行索引    print(col_ind,"#")#對應行索引的最優指派的列索引    print(cost[row_ind,col_ind])#提取每個行索引的最優指派列索引所在的元素,形成數組    print(cost[row_ind, col_ind].sum())    for i in range(len(row_ind)):        print(base_row[row_ind[i]],comp_col[col_ind[i]])

源碼

from ._lsap import linear_sum_assignment  線性和分配問題   linear_sum_assignment -- Solves the linear-sum assignment problem.  二次指派問題(quadratic assignment problem)     quadratic_assignment -- Solves the quadratic assignment problem.   scipy.sparse.csgraph.maximum_bipartite_matching 最大匹配問題:   scipy.sparse.csgraph.min_weight_full_bipartite_matching   scipy.optimize.linear_sum_assignment 求權值最小scipy是一個python開源的數學計算庫,可以應用于數學、科學以及工程領域,它是基于numpy的科學計算庫    scipy.sparse 提供了 7 種稀疏矩陣數據結構,或者稱之為稀疏格式Scikit-learn(以前稱為scikits.learn,也稱為sklearn) sklearn 里的linear_assignment() 指派問題或分派問題  idx_main, idx_other = scipy.optimize.linear_sum_assignmen(cost_matrix)  scipy.optimize.linear_sum_assignment 可以解指派問題(the linear sum assignment problem)  scipy中有對應的接口scipy.optimize.linear_sum_assignment, 輸入代價矩陣,即可得到分配問題的結果  scipy.optimize.linear_sum_assignment   輸入和返回值    maximum  cost_matrix[row_ind, col_ind].sum() numpy.arange(cost_matrix.shape[0]).  方矩陣 square matrix   矩陣矩形  a generalization of the classic assignment problem where the cost matrix is rectangular     jonker-volgenant(lapjv:Linear Assignment Problem solver using Jonker-Volgenant algorithm)     jonker-volgenant算法(也稱lapjv算法)是一個比匈牙利解法更快的算法interval=100 time_gap = abs(float(txt_timestamp) - float(get_ime_timestamp(img_file)))time_gap = time_gapif time_gap <=  interval else 10000”E“ 是 exponent(指數) 的縮寫。  3.14E3表示3140  科學計數法中E代表10的次冪 或者 3.14E+03表示3140   “E+”后面要精確到十分位位數不夠末尾補0

參考

源碼: https://github.com/scipy/scipyhttps://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html Assignment problem https://en.wikipedia.org/wiki/Assignment_problemhttps://blog.csdn.net/weixin_39548859/article/details/120276651 IOU計算,鄰接矩陣法 https://blog.csdn.net/zhuhuigege/article/details/127508137DeepSORT目標跟蹤里的匈牙利算法 最小代價分配問題 https://zhuanlan.zhihu.com/p/544534720DETR中匈牙利Hungarian算法介紹  taken from # scikit-learn  https://blog.csdn.net/wsLJQian/article/details/118365084