隨機森林手勢識別算法的高效嵌入式軟件實現

鄭小敏，李翔宇

（清華大學集成電路學院，北京100084）

0 概述

手勢識別能擺脫觸屏束縛，使設備的體積更小巧、佩戴方式更靈活，是一種更自然的人機交互方式。利用電磁波雷達［1-2］或超聲波［3-5］作為手勢識別的感知器，能夠實現對光照條件不敏感、數據量小以及降低算法復雜度。一些輕量級可穿戴設備的控制系統是手勢識別中一個重要的應用場景，但是它們普遍采用嵌入式系統，對實時性和功耗要求較高，因此，實用化的識別算法必須考慮在嵌入式系統中能否實現。

識別算法是手勢識別的關鍵部分，隨機森林［6］為一種泛化能力強且靈活的機器學習算法，其預測過程簡單，只涉及待預測數據與訓練模型的多輪數值比較運算，可以滿足系統實時性的要求，且能量消耗較低，因此，以谷歌的Soli項目［2］為代表的多個基于雷達的手勢識別系統選擇將隨機森林作為手勢識別的分類器。然而，一方面，手勢識別也可以采用其他識別算法，如支持向量機（SVM）、K 近鄰（KNN）和卷積神經網絡（CNN）等［7-9］；另一方面，算法的特征、具體參數和分類數需要因不同應用場景、手勢種類而調整，因此，為了保證系統的靈活性，需要研究高效的識別算法嵌入式軟件實現技術。由于識別模型可以進行離線訓練，只有推理（預測）過程需要在嵌入式平臺上實時運行，因此首要的問題是如何優化推理算法的程序。本文以隨機森林的預測過程嵌入式實現方法為研究對象，針對文獻［10］中提出的“一對其余”（One-vs.-Rest，OvR）多類別隨機森林分類器，提出一種低開銷手勢識別實現算法，以期縮短程序的平均運行時間并降低預測過程的平均能量消耗。另外，本文基于FPGA 的可編程片上系統（System on a Programmable Chip，SOPC）研究基于超聲波的識別算法嵌入式實現技術，結合前端信號處理功能的FPGA 實現，使整個系統在FPGA 上獨立運行并脫離PC 機，從而實現裝置的可移動性。

1 國內外研究現狀

現有多數隨機森林和手勢識別算法的實現是基于PC 平臺，較少在嵌入式系統中實現上述算法。如谷歌的Soli 系統，其采用的也都是高性能的嵌入式處理器［2，11-12］，只能在手機、移動電腦等高性能的設備平臺上使用，系統的成本和功耗與智能手表、智能耳機等可穿戴應用的需求存在一定差距。

隨機森林是由眾多決策樹組成的一種集成學習方法，預測過程依賴訓練時生成的全部決策樹參數。針對大量決策樹的存儲和訪問，文獻［13］提出的方案中每一棵決策樹的選擇路徑映射一個地址，該地址中存放預測的類別，特征與選擇路徑的各個閾值可以同時比較，從而提高隨機森林的預測速度，但是這種以空間換時間的方法會造成大量的存儲資源浪費。文獻［14］對每棵決策樹賦予不同的權重，引入以分類錯誤率為參數的評價指標，舍棄部分決策樹，該方案可以在一定程度上減少存儲空間，但是舍棄決策樹可能對識別率產生不利影響。文獻［15-16］提出基于專用硬件的隨機森林實現方案，研究寄存器傳輸級（RTL）的優化，但是，針對手勢識別的具體應用缺少靈活性，導致RTL 級的優化并不適用。

上述研究都是關于隨機森林的實現方法，分別從減少樹的數量和提高單棵樹的識別速度等方面進行優化。但是在一些多分類應用中，一個分類器可能由多個隨機森林組合而成，在整個分類器層次上的優化方案非常少。本文針對由多個二進制隨機森林按照OvR方式構成的多類別分類器進行實現與優化。

2 手勢識別系統介紹

本文針對文獻［10］所設計的基于超聲波雷達的手勢識別嵌入式系統實現問題進行研究，在該系統原型的基礎上將信號處理和識別算法的部分功能移植到FPGA 平臺上，以減小系統的體積并增強設備的移動性。

2.1 手勢識別系統工作原理

圖1所示為本文手勢識別系統采用的實驗裝置，通過一個超聲波發射器主動發射超聲波以進行目標探測，發射波經手反射產生回波信號，系統中有3 個超聲波接收器，手勢的3 路回波信號經過數字信號處理后得到一系列RDM 圖（能量在距離和速度維的聯合分布）［17］。系統從RDM 圖序列中提取特征，特征經過分類器后完成手勢識別的訓練和預測。

圖1 手勢識別系統實驗裝置Fig.1 Experimental device of gesture recognition system

文獻［10］中提取的系列特征包括從3 路信號的RDM 圖中提取最大速度、最大距離、平均速度和平均距離等，共45 維特征。1 s 的回波信號采用滑窗的方式切分為19 幀［10］，對45 維特征中某一維特征，計算其在19 幀數據中的均值、標準差、均方根、最大值和最小值，總的特征數目為45×19+45×5=1 080。

2.2 OvR 隨機森林多分類算法

2.2.1 隨機森林分類器

隨機森林由多個決策樹組成，一棵訓練好的二叉決策樹的結構示意圖如圖2（a）所示，樹的每個節點存儲一個特征和對應的閾值，測試樣本對應的特征（圖2（a）中的X1、X2、X3）與閾值比較，根據比較結果進行分支跳轉，直至到達葉子節點，則葉子節點對應的類別為樣本的預測類別。對于一棵決策樹，其中包含的有用信息為選擇的特征編號、比較閾值、內部節點的左右節點和葉子節點的輸出類別。圖2（b）所示為二分類隨機森林分類器的預測過程，對于測試數據，每棵決策樹經過層層比較（比較路徑為圖中灰線部分）給出一個判定結果（測試樣本是否屬于當前類，“1”表示屬于，“0”表示不屬于）。隨機森林會統計所有決策樹輸出“1”的比例，該比例即為測試樣本屬于該類別的概率。

圖2 隨機森林分類器Fig.2 Random forest classifier

2.2.2 特征對齊的隨機森林算法

本文采用文獻［10］中提出的用于多種手勢識別的識別算法——特征對齊的隨機森林算法。由于每個人的手勢快慢不同，提取的時序特征在時間上存在錯位，當測試樣本的特征和訓練樣本之間存在錯位時，直接采用隨機森林進行分類，會出現樣本和模型特征對應錯位的問題，從而影響識別率。為了提高跨用戶（訓練集中不含有測試者的數據）的識別精度，特征在送入分類器之前需要經過一些處理從而解決特征序列扭曲的問題。在提取的眾多特征中，平均速度特征能衡量手勢的整體運動趨勢，因此，本文運用所有訓練樣本的平均速度計算得到模板特征，然后通過動態時間規整（DTW）算法［18］計算測試樣本的平均速度以及與模板特征的距離，找到規整路徑并進行幀對齊。特征集中所有時序特征根據規整路徑進行縮放，將對應模板同一幀的一幀或幾幀的特征求平均值以壓縮成一幀的特征，或者將一幀的特征復制多份拓展到相鄰幀。經過處理后的時序特征稱為對齊后特征，對齊后特征加上統計特征再作為最終分類器的輸入。實驗結果表明，在其他實驗條件不變的情況下，與傳統的隨機森林相比，特征對齊的隨機森林算法中7 個人交叉驗證的平均識別率提高3.2%。最終分類器采用的是OvR［19-20］的多分類器架構，總的多分類分類器由一組二分類隨機森林組成，每個類別（手勢）有一個二分類隨機森林的子分類器。

圖3（a）所示為OvR 隨機森林分類器的訓練過程，當訓練類別1 的隨機森林時，首先使用類別1 的所有訓練樣本生成一個特征模板，然后將每個訓練樣本與該特征模板對齊，其對應的手勢1 的對齊特征為正樣本，其他手勢的對齊特征均為負樣本，正樣本定義為“1”類，負樣本為“0”類，然后用正負樣本訓練一個二分類隨機森林分類器。以此類推，有c種手勢則共訓練c個二分類隨機森林，共同組成OvR 多分類隨機森林。圖3（b）所示為預測過程，對于進入的測試數據，經過特征對齊后，再用每個類別的子分類器按照圖2（b）進行判定，測試數據經過c組二分類隨機森林判定后，可以得出屬于各個類的概率，找出概率最大值對應的類別，即為測試數據的預測類別。隨機森林決策樹的數目和深度這兩個可調的參數影響最終的識別率和模型大小。此外，為了方便存儲和硬件讀寫，模型中的決策樹均采用規則的二叉樹。

圖3 識別算法的訓練和預測Fig.3 Training and prediction of recognition algorithm

為了衡量特征對齊的隨機森林算法在實際系統中的應用可行性，本文評估該算法推理過程的計算復雜度。設一個模板所占的空間為A1，一個二分類隨機森林的空間復雜度為A2，則本文算法的空間復雜度為cA1+cA2（模板的數據量遠小于二分類隨機森林的數據量）。每個樣本的識別要執行一次特征對齊，使用DTW 算法對序列完成一次對齊的時間復雜度主要與序列長度L有關，為O（L2），采用加速算法可將時間復雜度降至O（L），二分類隨機森林測試一個樣本的時間復雜度為O（nD），其中，n和D分別為隨機森林中決策樹的棵數和最大深度，則手勢識別算法完成一次手勢預測的時間復雜度為O(c(L+nD))。特征對齊的隨機森林算法推理的時間復雜度和空間復雜度都和手勢類別數目c成正比。在實際應用中，手勢的種類不會過多，一般不超過10，因此，該算法能夠滿足系統對實時性的要求。當L=19，n=50，D=10，c=8 時，特征對齊的隨機森林算法在PC 機上的模型大小為700 KB，運算時間為37 ms［10］。

3 基于FPGA 平臺的手勢識別SOPC

文獻［10］中僅在PC機上采用Python語言實現OvR多分類隨機森林算法，核心算法調用的現有DTW 和隨機森林算法庫無法直接移植到嵌入式平臺上。本文手勢識別系統在Xilinx 的Artix7-100T FPGA 的Nexys4 開發板上實現，其為一個基于Xilinx FPGA 的SOPC 平臺的嵌入式系統，采用Xilinx 的軟核微處理器Microblaze作為CPU。基于FPGA 實現嵌入式系統的優勢在于：1）可以在系統中添加硬件加速模塊，提高系統的能量效率，效果優于基于單一嵌入式處理器的方案；2）開發周期短，設計靈活，易于修改。

圖4所示為整個系統結構框圖，包括信號處理、特征提取和分類識別等模塊，其中，數字信號處理、特征提取由專門的硬件加速模塊實現（硬件加速模塊的設計不是本文的討論范圍），識別算法則采用軟件實現，即由CPU 運行。硬件部分輸出的特征作為識別算法的輸入，再根據加載的手勢模型進行手勢預測，輸出的類別信息傳遞給具體應用。識別程序主要包括基于DTW 算法的特征對齊和最終OvR 隨機森林分類器的推理計算兩個部分，隨機森林推理占其中主要的時間和功耗，因此，本文主要研究隨機森林推理的程序設計問題。

圖4 系統結構框圖Fig.4 System structure block diagram

系統的CPU 主頻設置為100 MHz，Artix7-100T FPGA 電路板上有一個16 MB 的偽靜態存儲器（PSRAM），用來存放SDK 中的代碼和支持代碼運行的數據。手勢識別模型的訓練采用離線的方式，因此，本文系統中只需實現手勢的預測運算，訓練好的模型存處在開發板提供的FLASH 芯片上，識別時加載到片內存儲器使用。為了節省FPGA 片內存儲器和PSRAM的存儲資源，采用動態加載模型的方式，即在識別算法運行過程中根據需要實時地從FLASH中讀取所需的部分模型數據，而非一次性地將整個模型加載至片內。

4 隨機森林的嵌入式實現

4.1 模型數據結構

由PC 程序訓練生成的隨機森林模型文件大小為5.4 MB，其中包含大量預測過程不需要的信息，如衡量特征之間相關性的基尼指數、隨機抽樣抽取的樣本大小、參數含義的文字說明等。為了減少模型的存儲空間，對該模型進行精簡，只保留決策樹的有用信息并對數據進行組合存儲。為了方便硬件讀取訪問，決策樹的數據存儲設置為如圖5所示，每個節點的數據結構包含圖5（a）所示的6 個域，每個節點分配一個編號，該編號是節點存儲位置相對于整個樹結構起始地址的偏移量；對于內部節點，如圖5（a）所示，數據結構中的葉子節點標志位為0；對于葉子節點，葉子節點標志位為1，左節點編號和右節點編號均為0。在硬件中，為了提高實現效率，一般采用定點數計算，系統中提取出的特征以定點數表示，考慮到定點數的不同位寬對識別率的影響，通過實驗確定所有特征的最佳定點化位寬為16 位，則決策樹中的特征閾值位寬為16 位。因為特征總數為1 080（210＜1080 ＜211），特征編號至少需要11 位的二進制數存儲，所以一個節點數據結構占8 個字節，節點數據的各個位寬說明如表1所示。精簡模型數據與原始模型相比，只有對特征閾值的處理這一操作會損失數據精度，影響最終的識別率。由于分類器本身的泛化功能，在訓練隨機森林模型時特征也會定點化，保留16 位的位寬。實驗測試結果表明，采用精簡模型數據結構，識別率下降低于0.3%。

圖5 決策樹的存儲結構Fig.5 Storage structure of decision tree

表1 節點數據結構的字段解釋Table 1 Field explanation of node data structure

FLASH 的讀寫操作以頁為最小單位，寫操作時，必須先擦除后寫入，擦除的最小單位為1個塊；讀操作時，每次最少讀取一頁。本文系統中采用Spansion 的一款型號為S25FL128 的FLASH 芯片，其一頁的大小為256 B，一個塊為256 頁，大小為64 KB。

模型在FLASH 中存儲時，考慮每棵決策樹的大小約為1.8 KB，所以一棵決策樹需要8 頁儲存，一個塊最少可存儲32 棵樹。根據程序設計，每一棵樹的數據在FLASH 和內存中集中存儲，圖5（b）顯示了決策樹在FLASH 中的數據存儲方式。每棵樹各個節點的數據結構按照深度優先的規則順序存儲，對于每個塊，先存儲該塊中每棵決策樹所占的頁數，然后存儲決策樹的數據，一棵決策樹的數據大小如果不是頁容量（256 KB）的整數倍，則用零補全，后一棵決策樹緊接下一頁開始，保證不會有兩棵樹的數據存儲在同一頁內，直到完成FLASH 一個塊的數據填充。按照這種方式存儲模型的所有決策樹。不同的塊有不同的基地址，根據記錄的每棵決策樹的頁首地址，可以任意訪問不同的決策樹。

本文定義8 種手勢，訓練8 個隨機森林。在手勢集選擇時，主要考慮動作類型的代表性，其中包括：4 種宏觀手勢（即手作為一個整體運動），分別對應于3 維空間中整個手從左向右移動、從右向左移動、靠近目標和遠離目標4種不同維度和方向的運動；4種微觀手勢（即手指運動，手被看作存在形變的目標），包括兩種手指之間的滑動和多個手指的張開-聚合等。這些手勢的典型性可以較完備地考察系統的識別能力。本文系統的算法與具體手勢無關，在實際應用中用戶可以根據實際需要定義適合的手勢集合。當實際定義的手勢種類變化時，只需更新訓練的隨機森林模型和模板數據。只要手勢類型數量不變，改變手勢集合對本文識別算法和程序的計算復雜度沒有影響。每個隨機森林有50 棵樹，總的決策樹共有50×8=400 棵，400 棵樹之間相互獨立，互不影響。按照上述方案精簡后的模型數據文件大小僅為700 KB，較大程度地減輕了硬件的存儲壓力。

4.2 分支定界的最終分類器實現算法

根據傳統的隨機森林預測算法，決策樹按照預測時的讀取順序集中存儲在FLASH 中，測試數據經過每組隨機森林的所有決策樹的判定，才得出最終的結果。該方案需要從FLASH中順序加載全部400棵樹的數據，且進行400 棵決策樹的判定，如果一棵決策樹的最大深度為D，則一棵樹的判定過程最多需要進行D次比較和節點數據讀取。由于決策樹的數目很多，程序運行消耗大量時間，降低了系統的運行速度。圖6所示為在本文SOPC 系統中實現傳統OvR隨機森林分類器測試程序時各部分操作的所用時間占比，從圖6 可以看出，讀FLASH 數據占據了程序執行的絕大部分時間，因此，本文優化的重點是減少FLASH 數據的讀取時間，包括壓縮模型的大小和減少對FLASH 的訪問兩個方面。

圖6 傳統隨機森林預測算法的運行時間分布Fig.6 Running time distribution of traditional random forest prediction algorithm

分支定界的思想就是在搜索過程中當發現某個分支所可能取得的最好結果也不會超過現有最優解時，則放棄對該分支的繼續搜索，從而節省不必要的運算。將該思想用于本文隨機森林分類器，并基于如下的事實：本文采用的OvR 隨機森林分類器，就是在尋找各個隨機森林中的決策樹給正結論（樣本屬于該類）“投票”的票數最大值，如果所有隨機森林并行測試，即測試過程分成若干輪，每輪測試每個隨機森林各自使用1 棵決策樹，當過程進行到第k步，即所有隨機森林都已經用k棵決策樹進行判定時，如果某一個類累計得到正結論的次數為M，使得即使該隨機森林內剩余的決策樹（（50-k）棵）全部得出正結論，其總的得票數（M+50-k）也不大于當前其他類的最高得票數（隨機森林中給出正結論的決策樹棵數），則測試樣本必然不屬于該類，對這個類就不再繼續執行剩余的決策樹判定，因此，可以對8 個隨機森林的測試過程進行如下優化：將c個類別的隨機森林測試過程稱為c個并行支路，每條支路對應隨機森林中的所有決策樹遍歷判定過程。本文提出的隨機森林預測算法結構框圖如圖7所示，偽代碼如算法1所示。

圖7 隨機森林預測算法結構框圖Fig.7 Block diagram of random forest prediction algorithm

算法1OvR 多分類隨機森林預測算法

隨機森林預測算法的基本思想是：

1）按照廣度優先的原則，每輪測試每個隨機森林各拿出1 棵決策樹進行判定，然后再取各個隨機森林中的第2 棵樹進行判定，以此類推，使得各支路并行進行，根據前面的分析可得，只有當已經判定的輪次達到一定數量（設為τ輪）時，才可能出現某個支路能夠判定為淘汰的情況，因此，在前τ輪，所有支路都進行判定，不用做分支定界條件的檢查，當第τ輪測試結束，開始分別統計每個隨機森林得出正結論的總票數。

2）在每一輪測試后（即各個支路每多執行一棵樹的判定）就做如下檢查：如果出現某一個類別j，其正結論的票數加上j類剩下的決策樹數量之和小于此時其他類的得票數的最大值，則停止j類剩下的預測操作，即截斷支路j；被截斷的支路在接下來的測試中不再從中提取決策樹進行判定，從而節省不必要的數據讀入和閾值比較時間。上述過程不斷進行，直到只剩下一條支路，則預測類別為該支路的類別，或者未截斷支路剩余的決策樹為0 時，找出累計得票數最多的類別，即為預測類別，此時預測過程結束。

關于上述改進隨機森林預測算法中的參數τ的取值，因為進行τ輪測試后，可能出現票數最大值不會超過τ，即存在限制不等式（1），又因為只有該最大值大于每組隨機森林剩下的決策樹數目時，才可能滿足剪枝條件，所以τ應滿足不等式（2）。

由式（1）和式（2）得：

當τ滿足式（3）時，τ越大，進行剪枝條件檢查的次數越少，但是決策樹的平均判定次數越多，由于一棵決策樹的判定過程的計算量遠大于一次剪枝條件檢查，因此應該選擇盡量小的τ值。因為本文設定的模型中每個隨機森林的決策樹數目N=50，所以τ的最優值為26。每個隨機森林分別進行26 次決策樹判定后，再開始運用分支定界決定是否可以截斷某條支路。對于每個隨機森林剩下的24 棵決策樹，每輪每個森林的一棵決策樹參與判定后，進行一次分支定界。考慮到FLASH的一個塊最少可以存儲32 棵決策樹，為了便于分支定界預測方案的實現，8個類別各取4棵樹一起組合成32棵樹，存放入一個塊中。模型的最終存儲方案如下：

1）每個隨機森林各拿出26 棵決策樹，分別按照圖5（b）的方式存入FLASH 的8 個塊中，每個塊存儲26 棵樹。

2）每個隨機森林將剩下的決策樹分為6 組，每組4 棵樹，每個塊中存儲8 個類別的一組決策樹，共4×8=32 棵樹，一共占用6 個塊。

分類器預測過程中涉及的主要操作，或時間與功耗的主要來源是決策樹的閾值比較和FLASH 數據讀取，前者的最壞情況和決策樹深度成正比，后者則主要取決于所讀取的FLASH 頁數。通過本文算法可以避免不必要的決策樹判定，而且當一個分支被截斷后，其數據也不用再讀入片內存儲器，還可以減少FLASH 數據的讀取，既節省了程序的執行時間又降低了數據讀取的能耗。

5 實驗結果分析

在FPGA 的Microblaze 上實現有/無采用精簡數據存儲結構、有/無采用分支定界思想的4 組隨機森林預測算法，系統的工作頻率設置為100 MHz。在傳統的隨機森林預測算法中，每個樣本需要8×50=400 次決策樹判定。運用分支定界思想后，實際的判定次數和從FLASH 實際讀取的頁數都與被測樣本有關，不是確定的，因此，為了對改進算法的性能進行評估，選取800個隨機樣本（每種手勢各100 個樣本）進行測試，統計各自的決策樹判定次數和從FLASH 實際讀取的頁數，實驗結果表明，決策樹平均判定次數為243。樣本的決策樹判定次數決定了一次推理所需參與的決策樹數目，與CPU 訪問FLASH 的時間成正相關關系，統計得到精簡數據結構下的一個樣本平均讀取1 696 頁。

Xilinx 的axi_timer IP 核可以記錄運行一段程序所需的時鐘數，在每個操作對應代碼的始末位置，調用計數函數得到完成該操作所消耗的時鐘數與系統時鐘頻率的商值，即為實際運行時間。

為了評估精簡模型和分支定界算法對系統性能的影響，分別進行如下對比實驗：原始樹模型的有用信息未經組合壓縮且比較閾值保留原來的整型數據類型，分別使用傳統和分支定界的RF 識別算法在實驗平臺上運行，得到的運行時間如表2所示。采用精簡的節點存儲結構，不同算法的運行時間如表3所示。表2、表3 中的測試時間均為800 個隨機樣本的平均值。對比表2、表3 可以看出，采用精簡的節點數據存儲結構，傳統RF 算法訪問FLASH 的時間從1.741 s 下降到1.147 s，減少0.594 s，說明模型壓縮的重要性和數據結構設計的合理性。另外，在精簡節點數據存儲結構下，由于葉子節點標志位和類別信息需要經過與和移位運算得出，導致決策樹的判定時間略有增加，從0.021 s上升到0.024 s，但是精簡節點數據結構的使用減少了訪問FLASH 的平均次數。分支定界思想在隨機森林算法中的運用縮短了模型的加載時間，同時減少了CPU執行決策樹判定的運算時間，在未優化的模型存儲結構下，改進RF 算法總的運行時間（FLASH 讀取數據與決策樹判定時間之和）從1.773 s 下降到1.114 s，減少0.659 s。同時，采用模型存儲結構精簡和識別算法優化時得到的總運行時間為0.712 s。對比一般存儲結構下的傳統RF 算法，最終整個程序的總執行時間縮短了約60%。

表2 原始模型存儲結構下不同識別算法的運行時間Table 2 The running time of different recognition algorithms under the original model storage structure

表3 精簡數據結構下不同識別算法的運行時間Table 3 The running time of different recognition algorithms under reduced data structure

6 結束語

本文提出一種OvR 多類別隨機森林分類算法嵌入式軟件實現方案，并將其用于手勢識別SOPC 系統，以縮短系統的識別時間，減少FLASH 訪問能耗以及內存空間。設計更緊湊的模型節點數據結構，針對模型存放在片外FLASH 時FLASH 讀取數據以頁為最小單位的情況，設計減少低速設備FLASH 讀取次數和決策樹判定運算的分支定界多隨機森林OvR分類器推理算法，根據算法設計相應的模型存儲空間分配方案。實驗結果表明，與傳統的隨機森林預測算法相比，本文算法在FPGA 上的實測時間約縮短60%。下一步將采用神經網絡算法作為手勢識別的分類器，選擇一種計算復雜度滿足系統實時性和存儲需求的網絡結構，并研究其嵌入式實現方案。