鄭小敏，李翔宇

（清華大學(xué)集成電路學(xué)院，北京100084）

0 概述

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

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

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

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

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

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

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

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

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

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

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

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

2.2 OvR 隨機(jī)森林多分類算法

2.2.1 隨機(jī)森林分類器

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

圖2 隨機(jī)森林分類器Fig.2 Random forest classifier

2.2.2 特征對(duì)齊的隨機(jī)森林算法

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

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

圖3 識(shí)別算法的訓(xùn)練和預(yù)測(cè)Fig.3 Training and prediction of recognition algorithm

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

3 基于FPGA 平臺(tái)的手勢(shì)識(shí)別SOPC

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖6 傳統(tǒng)隨機(jī)森林預(yù)測(cè)算法的運(yùn)行時(shí)間分布Fig.6 Running time distribution of traditional random forest prediction algorithm

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

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

算法1OvR 多分類隨機(jī)森林預(yù)測(cè)算法

隨機(jī)森林預(yù)測(cè)算法的基本思想是：

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

2）在每一輪測(cè)試后（即各個(gè)支路每多執(zhí)行一棵樹的判定）就做如下檢查：如果出現(xiàn)某一個(gè)類別j，其正結(jié)論的票數(shù)加上j類剩下的決策樹數(shù)量之和小于此時(shí)其他類的得票數(shù)的最大值，則停止j類剩下的預(yù)測(cè)操作，即截?cái)嘀穓；被截?cái)嗟闹吩诮酉聛淼臏y(cè)試中不再?gòu)闹刑崛Q策樹進(jìn)行判定，從而節(jié)省不必要的數(shù)據(jù)讀入和閾值比較時(shí)間。上述過程不斷進(jìn)行，直到只剩下一條支路，則預(yù)測(cè)類別為該支路的類別，或者未截?cái)嘀肥Ｓ嗟臎Q策樹為0 時(shí)，找出累計(jì)得票數(shù)最多的類別，即為預(yù)測(cè)類別，此時(shí)預(yù)測(cè)過程結(jié)束。

關(guān)于上述改進(jìn)隨機(jī)森林預(yù)測(cè)算法中的參數(shù)τ的取值，因?yàn)檫M(jìn)行τ輪測(cè)試后，可能出現(xiàn)票數(shù)最大值不會(huì)超過τ，即存在限制不等式（1），又因?yàn)橹挥性撟畲笾荡笥诿拷M隨機(jī)森林剩下的決策樹數(shù)目時(shí)，才可能滿足剪枝條件，所以τ應(yīng)滿足不等式（2）。

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

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

1）每個(gè)隨機(jī)森林各拿出26 棵決策樹，分別按照?qǐng)D5（b）的方式存入FLASH 的8 個(gè)塊中，每個(gè)塊存儲(chǔ)26 棵樹。

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

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

5 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

6 結(jié)束語

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