資源簡介

(共20張PPT)
浙教版四年級上冊
第13課 數據有關聯
CONTENTS
目錄
匈牙利算法的數據關聯應用
02
總結回顧
04
匈牙利算法的數據關聯概念
01
作業布置
03
匈牙利算法的數據關聯概念
01
匈牙利算法的數據關聯概念
依次進行數據關聯是局部最優解，并不能代表全局最優解。而匈牙利算法則在追求全局最優，是一種在多項式時間內求解分配問題的組合優化算法。多目標跟蹤數據關聯問題可以轉化為有權二分圖最小權匹配問題，匈牙利算法就是解決數據關聯問題的圖算法。
匈牙利算法的數據關聯應用
02
圖（Graph，G），是由頂點集合（Vertices，V）和邊集合（Edges，E）組成的二元組，表征了不同頂點間的拓撲連接關系，圖中的邊是否具有單向性可將圖分為有向圖和無向圖，根據圖中的邊是否具有不同的權重可將圖分為有權圖和無權圖。
二分圖（Bipartite Graph）是一種特殊的圖，又稱二部圖。二分圖的頂點集可以被劃分為兩個互不相交的獨立子集U和V。二分圖邊集合 E 中的每一條邊分別連接了頂點子集 U 和 V 中的一個頂點，但 U 和 V 內部的頂點互不相連。
二分圖的結構與多目標跟蹤任務的結構很相像，可以把U與V看成是多目標跟蹤任務中的前一幀與當前幀的檢測框集合，U與V之間的關聯視為前一幀與當前幀的同一id目標的檢測框的關聯，我們需要做的就是將相鄰兩幀的目標檢測框盡可能準確的兩兩匹配。
匹配：
給定圖G=(U，V，E)，一個匹配表示多個U和多個V之間的關聯M。M是E的一部分，即子集。匹配不僅僅是兩個點一條線，而是多個關聯的組合。匹配是一種關聯的方案。匹配中的線是一一對應的，是一個點鏈接另外一個點的，在目標檢測中就是當前幀的檢測框一一對應到上一幀的檢測框。如下圖的U5和V4，U3和V3，U2和V1共同組成一個匹配。匹配上的邊叫匹配邊，未匹配上的邊叫未匹配邊。同樣的，匹配上的點叫匹配點，未匹配上的點叫未匹配點。
最大匹配（Maximum-Cardinality Matching）表示圖的所有匹配中邊數最多的匹配方案，最大匹配不唯一。匹配邊數最大值就是一個集合點的個數。
01
大權匹配：對于有權圖而言，最大權匹配（Maximum-Weight Matching）表示的是有權圖的所有匹配中邊的權重之和最大的那些匹配。
02
最小權匹配：對于有權圖而言，最小權匹配（Minimum-Weight Matching）表示的是有權圖的所有匹配中邊的權重之和最小的那些匹配。
03
多目標跟蹤數據關聯問題
多目標跟蹤數據關聯問題可以轉化為有權二分圖最小權匹配問題。跟蹤過程中的上一幀目標可以看成U，下一幀目標可以看做V，邊的權重可以看作是上一幀目標和下一幀目標通過某種方式計算得到的匹配距離，這個匹配距離我們稱之為代價（Cost），所有的匹配距離構成了代價矩陣（Cost Matrix），我們要找到匹配關系使得總的匹配距離最小（代價最低）。
交替路
從某個未匹配點出發，交替經過未匹配邊和匹配邊形成的路徑。
增廣路（Augmenting Path）是一條特殊的交替路，增廣路從圖中的某個未匹配點起始，交替經過未匹配邊和匹配邊，并終止于不同于起始點的另一個未匹配點。
性質：
Berge 定理：對于給定的圖G和它的一個匹配M，M是G的最大匹配的充要條件是G中不存在匹配M的增廣路。增廣路上的邊個數一定是奇數，是奇數就意味著是一邊的點到另外一個的點。這樣增廣路上的邊未匹配的邊一定比匹配邊多1。
如何找到最大權匹配？
對于一個給定的二分圖 G=(U,V,E)和初始為空的匹配M，只要反復搜索增廣路就能逐漸擴展匹配的大小，最終當我們找不到增廣路時就得到了一個最大匹配。利用增廣路找最大匹配的算法，就叫做匈牙利算法。
總結回顧
03
總結回顧
通過今天的學習有哪些收獲？請分享一下。
作業布置
04
作業
繼續查找有關數據關聯的資料，我們下節課一起分享。
感謝聆聽

展開更多......

收起↑