基于改進匈牙利算法對多人人體關鍵點匹配的研究*

鄔春學，賀欣欣

(上海理工大學 光電信息與計算機工程學院，上海 200093)

0 引言

人體姿態估計是計算機視覺任務中重要的一部分，與人體檢測、識別、跟蹤等相關技術息息相關，其主要研究如何準確快速地定位人體關鍵點，并確定各個關鍵點所在的人體目標[1]。目前存在著傳統的定位方法與基于深度學習的方法，它們對推動計算機視覺的研究起著重要的作用。

基于深度學習的檢測方法又可分為自上而下(Top-down)和自下而上(Bottom-up)的方法。Top-down檢測方法的思想是先識別出圖像中的所有人體，然后檢測每個人的關鍵點[2]，但隨著圖像中人數的增加，Top-down方法的計算成本顯著增加，此時則需要考慮使用Bottom-up方法保持穩定。Bottom-up檢測方法的思想是先計算出一個圖像中所有人體的關鍵點，然后再將這些關鍵點通過匈牙利算法、信號聚類等方法劃分給不同的目標人體[2-4]。本文基于自下而上的2D多人人體姿態估計，對求解關鍵點匹配算法進行研究。

在復雜和多人的環境下，傳統的匈牙利算法面臨著關鍵點遮擋、算法性能等關鍵問題。本文基于2017年提出的PAFs理論基礎以及OpenPose模型，針對關鍵點聯系和匹配模塊，提出了一種改進的匈牙利數學模型進行實驗。改進的算法采用親和度向量場與鄰接矩陣結合的方式，通過對矩陣內的數值處理求解最佳匹配，即輸出正確的人體姿態框架圖。

1 相關工作

1.1 人體姿態估計的發展

傳統的人體關鍵點定位方法基于人體姿態模板庫，圖像特征信息到模板庫中姿態的映射通過特定的映射通道實現。在此基礎上，針對人體姿態是千變萬化的特點，學界提出了圖結構模型，此方法突破了模板庫的局限性，使得人體姿態估計方法更加靈活。并且繼Felzenszwalb等人[5]關于人體姿態估計的變形零件模型(DPM)的開創性工作之后，許多算法被提出以改進DPM體系結構[6]。Yang等[7]提出了一種使用支持向量機建模的混合模板，Johnson等[8]通過使用身體部分檢測器的級聯提出了更多的鑒別模板，Pishchulin等[9]提出了基于DPM的高階身體部位依賴性模型，使用Poseletprior和DPM模型[10]捕獲身體部位的空間關系。以上所有方法的共同特征之一是它們可以使用手工制作的立體特征(例如邊緣、輪廓、HoG的特征和顏色直方結構圖)，與學習特征相比，這些特征被證明具有較差的泛化性能和判別能力[11]，因此針對復雜環境下的特征提取，這些方法的性能是不夠的。

基于深度學習的方法與傳統方法相比較，引入了卷積神經網絡(Convolutional Neural Network，CNN)來解決姿態估計問題。Toshev[12]等提出的Deeppose和一系列CNN姿態回歸器使得精度顯著提高。Wei[13]等提出了卷積姿態機(Convolutional Pose Machine，CPM)——一種多階段估計方法，來解決神經網絡層數太深產生的梯度消失問題。Papandreou[14]等提出了G-RMI方法，使用Faster R-CNN自上而下地進行多人姿態估計。此外還有Mask R-CNN[15]、RMPE[16]和Simple Baselines[17]等方法。主流的自下而上的方法有PAFs[18]、DeepCut[19]以及Associative Embedding[20]。與自上而下不同的是，這些算法先檢測出圖像中所有的關鍵點，然后將這些關鍵點關聯和分組于歸屬的人體，即實現關鍵點檢測和聚類。

2017年，來自CMU感知計算實驗室的曹哲等人[18]發表了一篇使用PAFs(Part Affinity Fields)實時預測2D人體姿態的論文，PAFs是對肢體進行標注，表示人體每個肢體的2D向量，同時保持了肢體區域之間的位置信息和方向信息。圖1為一個肢體PAFs的示意圖。如圖所示，若點P在這個肢體上時，則關鍵點j1、j2連線方向上的為單位向量(模長為1)，否則為零向量。判斷條件如式(1)和式(2)所示。

圖1 單個肢體PAFs示意圖

在此理論基礎上，美國卡耐基梅隆大學(CMU)基于卷積神經網絡和監督學習，并以Caffe為框架開發實現了OpenPose人體姿態識別項目。其中實現的基本原理是輸入一幅圖像，經過卷積網絡得到一組特征圖，然后分別使用CNN網絡提取置信度(Part Confidence Maps)和親和度向量場(Part Affinity Fields)，最后基于PAFs把多人關鍵點匹配轉換成圖論問題，采用匈牙利組合算法求解一種類似二分圖匹配的問題，最終組成一個完整的人體姿態結構。

1.2 基礎模型的構建

本文基于OpenPose人體姿態估計模型提取人體的骨骼關節點和肢體，對解決兩類不同肢體集合互相連接的匈牙利算法進行了優化，提高了模型在復雜場景下匹配肢體時的性能。OpenPose模型的網絡結構如圖2所示。

圖2 OpenPose網絡結構

OpenPose網 絡 結 構 中，3個 連 續 的3×3卷 積 核組成了卷積塊C的網絡，與原始網絡中7×7卷積核不同。圖像經過網絡提取特征，得到一組關節點和肢體的圖像特征圖F，然后特征圖F作為之后卷積神經網絡的輸入。其中，第一階段中用于推斷的卷積網絡分別為ρ1和φ1，分別對圖像特征F進行處理，且ρ1、φ1、ρt和φt都 包 含5個 卷 積 塊 與2個1×1的卷積。S是置信度網絡，用來預測關節熱度圖，L是親和度向量場網絡，用來預測關節親和域。

第一階段的置信度和親和度向量場如式(3)、式(4)所示：

第二階段及之后的置信度和親和度向量場如式(5)、式(6)所示：

對檢測出來的置信度圖執行非極大值抑制，獲得離散的關鍵點位置候選集如圖3(a)所示。由于圖中有多人，對于每種關鍵點有若干候選，如圖3(b)所示，針對全連接圖的求解問題是十分復雜的，于是本文將全連接圖劃分為若干個子集。利用PAF網絡的大感知場，成對關聯分數隱含地編碼了全局上下文，再通過匈牙利算法實現二部圖圖3(c)到圖3(d)的過程，取得最佳匹配。圖中表示部件j2集合中的頂點1，同理表示部件j3集合中的頂點2表示j2與j3是否有關聯。

圖3 圖的匹配

2 改進的匈牙利算法

2.1 經典匈牙利算法

匈牙利算法是由匈牙利數學家Edmonds于1965年提出的，它可以用于求解多種形式的匹配問題。在實際應用中，若在有權二部圖中，頂點所連接的邊權重不同，要求在頂點匹配的同時考慮總權重最大或者最小的問題，這就是最優匹配問題。建立數學模型如下：設用wij＞0(i，j=1，2，…，n)表示集合A中的頂點i匹配集合B中的頂點j時的權重，定義決策變量：

則問題可以轉化為：

定理1：如果從有權匹配矩陣E(eij)的每一行的元素中分別加上或減去一個常數ui，也可稱作該行的位勢；從每一列的元素中分別加上或減去一個常數vj，也可稱作該列的位勢，得到一個新矩陣F(fij)，若其中fij=eij-ui-vj，則二者的最優解等價。

定理2：若矩陣E的元素可分成零和非零兩類數字，則覆蓋零元素直線的最大數量等于位于不同行、不同列的零元素的最大個數。

由上述定理可總結出匈牙利算法的基本思想是：通過符合定理不斷變換的方式，使得矩陣E的行和列盡可能多地生成零元素，直到能從變換后的矩陣中找出n個位于不同行、不同列的零為止，這些零元素對應的zij=1，其余元素對應的zij=0。

2.2 改進的數學模型

在關鍵點分配中存在一定時間范圍內資源數目和匹配任務不等的問題，可能造成兩類關鍵點在進行配對時出現誤判或者漏判的情況，因此可以用改進匈牙利算法將不平衡的匹配問題轉化成平衡匹配問題。

現有如下二部圖匹配問題：共有m個待匹配的二部圖，其中每個二部圖中的集合各有n個頂點待匹配，考慮到每兩個頂點在匹配時，所產生的連接方向上的積分以及整個二部圖的權重和不同，建立數學模型如下：

首先計算出兩點(dj1，dj2)連線上的線性積分，若的方向與Lc(p)方向一致，則E的值會越大，表明該位置是一個軀干的可能性就非常大。

定義決策變量：

則問題可以轉化為：

2.3 算法步驟及流程圖

由于原匈牙利算法的不足，本文提出改進匈牙利算法結合鄰接矩陣求解最大匹配，它的實現步驟如下：

(1)將原始二部圖中邊的權重取反，構建初始化鄰接矩陣。

(2)對鄰接矩陣進行變換，每行(列)都減去各行(列)的最小值，此時每行(列)至少都有一個0。

①作最少的直線覆蓋住鄰接矩陣中所有的0元素，且直線只能是某一行或者某一列上的，不能跨越不同的行或列。若有元素被兩條直線覆蓋，標記上x*。

②判斷是否需要終止循環，判斷條件為第一步中作得的直線數是否等于各集合中的頂點數，若相等則終止循環繼續步驟(4)，否則繼續操作。

③對鄰接矩陣中的元素作變換得到更多的0元素。具體步驟為：首先將所有沒有被直線覆蓋的元素記作Φ，在Φ中找到最小的元素，記作k；然后將Φ中的所有元素都減去k，并將標記上x*的元素都加上k。

(4)輸出變換后的鄰接矩陣，從只有一個0元素的行或者列開始，將這個0元素標記為0*，這樣做的目的是確保本行或列的頂點一定有另一個點做匹配，然后將0*所在的行和列中的其他元素忽略。對于出現多種同一列或同一行的獨立零的情況，根據次小值越大對其行或列中的零元素優先匹配。反復選取之后，矩陣中的0*分別處于不同的行且分布在不同的列中，則代表此次最大匹配已完成，0*對應的頂點即為匹配的結果。改進的匈牙利算法的流程圖如圖4所示。

圖4 改進的匈牙利算法的流程圖

圖5和圖6給出了算法的兩個示例，有助于理解算法的計算過程。

圖5 示例1

圖6 示例2

3 實驗與分析

為了驗證改進匈牙利匹配算法的性能以及在人體關鍵點匹配中求解最佳匹配的可行性，本文實驗首先將改進的匈牙利算法與未改進的匈牙利算法在求解m×n階矩陣最佳匹配時消耗的時間和計算誤差進行對比，之后選取100張包含多場景、多人的圖像輸入原始TensorFlow版本的模型和搭載了改進后匈牙利算法的模型進行處理圖像的對比實驗。實驗采用的操作系統是Windows 10，其他設備信息是Intel?CoreTMi7-8700K CPU@3.70 GHz，64 GB內存以及NVIDIA GeForce 1080Ti顯卡，基于Python3.5編程設計語言完成應用模型設計實驗。

由于企業公允價值確認在大多數時是一個估計的結果，所以，其在企業實際應用過程中極易被利用成為操縱利潤的工具。同時，企業會計準則不是一種技術手段，不同準則會生成不同的企業會計信息。企業公允價值變動被計入到當期損益之中，其對企業的實際經濟收益情況造成了改變，比如當企業交易性金融資產公允價值發生變動時，其將會使得企業產生經濟利得或造成經濟損失，從而改變企業的短期投資，且只確認了資產的減值，并未確認資產的升值收益；而企業衍生金融工具，其不但能夠增加企業的資產或負債，同時還能夠直接對企業當期損益情況造成影響。

在本次實驗中，為評測改進算法的性能，分別測量改進算法和未改進算法在運行過程中占用內存的時間，首先使用代碼自動生成k個m×n且均勻分布的隨機數矩陣，然后通過對k個矩陣分別進行10次、50次、100次求解，將累計計算的平均運行時間進行比較，可更加直觀地看出兩種算法在運行時間上的差距。

通過分析表1的數據，能夠較為直觀地發現相對于經典算法，改進算法能夠在較短時間內完成相同的任務量。

表1 兩種算法的平均累計時間 (s)

在對改進匈牙利算法的精確度分析上，把得到的目標函數值與真實值的差以及矩陣維數作為分析的主要指標。下面分別使用兩種方法對15維、50維、100維、200維 的 矩 陣 進 行10次、50次、100次的反復計算，得到改進算法誤差絕對值累計數據與誤差率，如表2所示。

表2 改進算法的精度分析

通過分析表2的數據，能夠較為直觀地發現：改進后的算法在求解100×100以內矩陣的全局最優值時，存在著微小的誤差，同時隨著矩陣維數的增加，精確度的誤差率有微小的增加波動。

實驗最后進行了原始TensorFlow版本的模型和搭載了改進后的匈牙利算法的模型處理圖像的對比實驗。所選圖像包含多人且人物與背景不易區分，在經過模型處理后分別輸出結果圖，部分結果如圖7所示，圖8顯示了兩種模型在運行時CPU的負載情況。

圖7 多人圖像測試對比結果

圖8 不同模型對計算機的負載率對比

從實驗結果可以看出，在處理相同圖像的情況下，搭載了改進的匈牙利算法的模型相對于未改進的模型關鍵點匹配正確率提升了至少40%，尤其是對多人下肢的匹配性能有明顯的提升，并且運算速度較之前至少提升5%，且對計算機的負載率降低20%。

4 結論

通過研究在關鍵點匹配背景下的合理求解最佳匹配問題，提出基于改進匈牙利算法的二部圖鄰接矩陣求解最佳匹配的方法，同時綜合考慮了在不同維度矩陣下兩種算法的運行時間、改進算法的精確率，解決了傳統匈牙利法在人體關鍵點匹配中復雜度高、耗時久、網絡結構冗余等問題，為待匹配候選點的多對多匹配提出了一種新的思路，實現了關鍵點的合理、有效分配，提高了模型整體效率。

后續研究將重點關注如何在占用更少的硬件資源和軟件資源的基礎條件下，加快批量提取各種人體姿態圖像特征，以及在檢測所得到的人體圖像基礎上如何進行圖像SLAM的研究。