鄭小敏，李翔宇

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

0 概述

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

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

1 國內(nèi)外研究現(xiàn)狀

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

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

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

2 手勢識別系統(tǒng)介紹

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

2.1 手勢識別系統(tǒng)工作原理

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

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

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

2.2 OvR 隨機森林多分類算法

2.2.1 隨機森林分類器

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

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

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

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

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

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

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

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

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

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

圖4 系統(tǒng)結(jié)構(gòu)框圖Fig.4 System structure block diagram

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

4 隨機森林的嵌入式實現(xiàn)

4.1 模型數(shù)據(jù)結(jié)構(gòu)

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

圖5 決策樹的存儲結(jié)構(gòu)Fig.5 Storage structure of decision tree

表1 節(jié)點數(shù)據(jù)結(jié)構(gòu)的字段解釋Table 1 Field explanation of node data structure

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

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

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

4.2 分支定界的最終分類器實現(xiàn)算法

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

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

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

圖7 隨機森林預測算法結(jié)構(gòu)框圖Fig.7 Block diagram of random forest prediction algorithm

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

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

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

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

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

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

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

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

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

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

5 實驗結(jié)果分析

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

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

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

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

表3 精簡數(shù)據(jù)結(jié)構(gòu)下不同識別算法的運行時間Table 3 The running time of different recognition algorithms under reduced data structure

6 結(jié)束語

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