王芝斌，陽文敏，張圓蒲，柴志雷

江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫 214122

基于ZYNQ的稠密光流法軟硬件協(xié)同處理

王芝斌，陽文敏，張圓蒲，柴志雷

江南大學物聯(lián)網(wǎng)工程學院，江蘇無錫 214122

1 引言

光流法在許多視頻或圖像應用中有廣泛的應用前景，比如運動物體檢測、運動物體估計、視頻壓縮等。光流法是由于場景中前景目標本身的移動、相機的運動，或者兩者的共同運動所產(chǎn)生的。對光流算法的研究，真正提出有效光流計算方法還歸功于Horn-Schunck[1]在1981年創(chuàng)造性地將二維速度場與灰度相聯(lián)系，引入光流約束方程的算法，是光流算法發(fā)展的基石。通過光流法評估機制[2-3]的驗證，基于Horn-Schunck[1]的稠密光流法模型，與經(jīng)典的稀疏光流法Lucas-Kanada[4]相比，不但能夠產(chǎn)生稠密光流法，而且能計算出很好的光流效果。

高質量的光流算法計算機非常復雜。對于分辨率為640×480的灰度圖片，在Xilinx的FPGA+ARM異構芯片（即ZYNQ）上，單獨利用ARM Cortex-A9的處理器上，計算基于HS（即Horn-Schunck）模型的稠密光流場需要24.40 s。低效的計算速度限制了光流法在現(xiàn)實世界的可應用性。目前有很多工作都關注于高效能的稠密光流計算。在通用處理器上研究降低光流計算的復雜度[5-6]，更多的工作關注在專用硬件平臺上加速光流的計算[7-8]。

Martin等人[9]在Altera APEX20XK的FPGA上也實現(xiàn)了基礎的HS光流法，處理256×256的圖片序列每秒能夠達到60幀，但是影響HS光流法計算時間的一個關鍵參數(shù)（即迭代次數(shù)）沒有清晰的說明。Rustam等人[10]提出使用了整數(shù)和組合整數(shù)、小數(shù)的基于HS光流法的硬件體系。同樣地，光流法的迭代次數(shù)也沒有詳細給出。Gultekin等人[11]在Altera Cyclone-II的FPGA平臺上，實現(xiàn)了基于HS的光流法，在工作頻率為50 MHz的情況下，每秒可以處理257幀的256×256圖片序列。但是，它并不是計算整張圖片的稠密光流，而是計算圖片內(nèi)的一塊小區(qū)域。然而，由于不易調試和底層的編程語言，即VHDL/Verilog，在單純的FPGA上實現(xiàn)復雜圖像算法非常耗時。所以，目前基于FPGA的光流法計算大部分停留在一些最基礎的光流算法[9-11]。

隨著異構芯片技術的不斷發(fā)展，傳統(tǒng)處理器和FPGA組成的異構系統(tǒng)芯片有潛力能夠勝任高效能計算[12-13]，如Xilinx公司的FPGA異構系統(tǒng)芯片（ZYNQ）。而且與傳統(tǒng)的FPGA開發(fā)語言相比（即VHDL/Verilog）相比，隨著高層綜合語言的發(fā)展，集成了Xilinx開發(fā)環(huán)境的高層綜合（HLS）技術，80%的高層綜合語言（即C、C++、System C）與20%的底層綜合語言（即VHDL、Verilog），能夠大幅度提高FPGA的開發(fā)效率。

本文針對FPGA的異構系統(tǒng)平臺（即ZYNQ），利用最新的高層綜合（HLS）語言與傳統(tǒng)的硬件描述語言相結合，通過算法的可并行性分析，重構與優(yōu)化FPGA可運行的C代碼，設計了基于HS稠密光流法的硬件加速器的IP核。針對ZYNQ平臺的特點，調用已設計好的光流算法IP核，完成系統(tǒng)的硬件與軟件設計。實驗結果顯示，對于640×480大小的圖片，基于ZYNQ的軟硬件協(xié)同的方式比純軟件方式的計算性能提高了34倍，執(zhí)行時間從24.40 s降低到0.71 s。

2 稠密光流算法的工程流程介紹

圖1所示是基于HS稠密光流法的基本工作流程，可以把光流法的計算劃分為四個階段：預處理（S1）、梯度計算（S2）、運動模型構造（S3）和迭代計算（S4）。

2.1 預處理（S1）

預處理（S1）階段是平滑處理圖像序列，它的作用即是用來減少圖像噪音和外部的影響，一般用卷積來實現(xiàn)。這一階段是一個通用的圖像操作。

2.2 梯度計算（S2）

梯度計算（S2）階段是在平滑后的圖片的基礎上計算圖像的梯度，包括水平梯度(Ex)、垂直梯度(Ey)和時間梯度(Et)。基于HS的模型只需要一階梯度的信息，通常梯度計算也是通過卷積來實現(xiàn)的。

圖1 基于HS的稠密光流法工作流程

2.3 運動模型構造（S3）

運動模型構造（S3）階段是根據(jù)梯度信息來構造運動模型的信息?；贖S的稠密光流模型，需要構造5個運動模型信息(J11、J12、J13、J22和J23)。對于不同的運動模型由不同的梯度信息融合而構成。這一階段的操作就是矩陣相乘，如公式（1）所示，J表示構造的運動模型，E表示梯度。

2.4 迭代階段（S4）

迭代計算（S4）階段是通過全局迭代計算光流，對于基于HS稠密光流法的模型，只需要更新光流模型(u，v)。如公式（2）所示，迭代體的計算是根據(jù)線性的超松弛算法（SOR），其中，i表示像素點的行坐標，j表示像素點的列坐標，J表示構造的運動模型，u和v分別表示水平和垂直的光流模型，N-(i)表示第i個像素點的上和左的相鄰像素點，N+(i)表示第i個像素點的下和右的相鄰像素點，w是超松弛迭代的權重因子，k是迭代的次數(shù)，ɑ是光流平滑的權值。

圖2 光流計算的數(shù)據(jù)相關性

3 并行性分析

下面從任務并行、數(shù)據(jù)并行和流水線并行給出基于HS稠密光流法的并行性分析。

3.1 任務并行

如圖2所示，每個階段之間的操作都存在數(shù)據(jù)相關性，但是在同一個階段內(nèi)，多種操作可以自己獨立計算。通過平滑處理圖片序列(img1，img2)，可以同時得到平滑后的圖片(simg1，simg2)；然后根據(jù)兩張平滑后的圖片的平均值((simg1+simg2)/2)，可以計算水平梯度(Ex)和垂直梯度(Ey)，同時時間梯度(Et)是兩張圖片相減所獲得的；同樣地由公式（1）可以同時得到5個運動模型的信息。這些操作都可以獨立和同時計算，迭代計算部分的并行性會在下面分析。

3.2 數(shù)據(jù)并行

預處理和梯度計算的操作都可以通過卷積來實現(xiàn)，卷積操作是一個典型的數(shù)據(jù)并行。對于運動模型構造階段，每一個運動模型的計算都可以通過相同的指令，這些操作都能夠高效地實現(xiàn)并行計算。

3.3 流水并行

對于前三個階段（S1，S2，S3），每一個階段之間的數(shù)據(jù)交互，在合適的硬件上可以全流水線地工作。如圖3所示，迭代計算需要迭代次數(shù)去獲取結果，這就導致了整個系統(tǒng)的流水線性能的下降。因此，迭代計算部分應該首先被重構與優(yōu)化。在實際優(yōu)化中，展開迭代，需要展開以提高流水線的性能；在理想狀態(tài)下，硬件資源足夠的條件，整個系統(tǒng)幾個周期全流水完成處理。

圖3 SOR與Red-Black SOR的數(shù)據(jù)相關性

4 重構與優(yōu)化FPGA運行的光流計算C代碼

4.1 重構與優(yōu)化FPGA可運行的迭代體

從并行性分析可知，迭代階段（S4）首先重構與優(yōu)化迭代體，由公式（2）可知，在計算光流（u或者v）的時候，它的每一個像素點的4個鄰居都有數(shù)據(jù)相關性。如圖3（a）所示，假設像素點7正在計算，像素點2，6，8，12都需要計算，特別是左上的像素點2，6已經(jīng)更新了，而右下的像素點8，12沒有更新。因為左上的兩個像素點需要立即更新，這導致了原始的超松弛算法（SOR）不能并行處理。為了避免數(shù)據(jù)相關性，這里使用改進的紅黑超松弛算法（Red-Black SOR）。如圖3（b）所示，用紅黑兩次掃描來替代一次掃描，首先是紅掃描處理的就是紅色的像素點，此時它的4個鄰居都是黑色沒有更新的像素點；接著就是黑色像素點的處理，此時它的4個鄰居都是已經(jīng)更新的紅色的像素點。不管哪一個顏色掃描，它周圍的4個像素點都能夠被同時處理，適合在FPGA上的并行計算。

圖4所示的是用高層綜合語言重構的C代碼的紅黑超松弛算法的硬件結構圖。通過3×3的窗口的操作，在幾個周期的延遲后，窗口內(nèi)的9個像素點是能夠滿足同時訪問光流的4個鄰居像素點，這就是滿足了并行計算的條件。在SOR初始化延遲后，每隔5個周期，每一組的數(shù)據(jù)流(inu、inv、J11、J12、J13、J22和J23)都會被立即處理，最后獲得每一次迭代的光流值（outu、outv）。

4.2 優(yōu)化迭代計算及其與外部存儲器的帶寬

如圖4所示，迭代體的輸入數(shù)據(jù)通道的接口由5個32位的運動模型和2個32位的光流模型構成，高帶寬的輸入數(shù)據(jù)通道（224位），易導致低效地訪問外部存取器。為了高效地利用外部存取器，從兩個方面來優(yōu)化，一方面是減少訪問外部存取器的次數(shù)，另一方面是降低通信的帶寬。

為了減少訪問外部存取器的次數(shù)，通過迭代展開可以有效地減少外部迭代的次數(shù)，使得多份迭代體能夠流水地并行計算，增加了流水線指令的計算性能。為了降低通信的帶寬，如圖5所示，從預處理（S1）到運動模型構造（S3）也放在了迭代體的內(nèi)部。對于每一次迭代，原始圖片序列(img1，img2)與光流模型(u，v)構成了迭代體的輸入數(shù)據(jù)端口，訪問外部存取器的帶寬降到了128位。前三階段的計算時間要比訪問高位寬外部存取器的時間短得多。

圖4 用C描述的紅黑迭代體的硬件結構圖

圖5 改進的光流法的流水線

4.3 重構光流計算的其他階段

在優(yōu)化后的迭代體的內(nèi)部，光流計算的前三個階段（S1、S2、S3）也需要重構與優(yōu)化FPGA可執(zhí)行的C代碼。預處理（S1）和梯度計算（S2）都是用卷積來實現(xiàn)的。卷積在FPGA上并行計算在前面的工作[14]已經(jīng)詳細討論過了。運動模型構造（S3）是簡單的乘法計算，可以直接在FPGA上實現(xiàn)。

5 稠密光流法在ZYNQ上的系統(tǒng)設計

使用Xilinx的高層綜合（HLS）語言重構與優(yōu)化了基于HS的稠密光流法計算，生成了基于ZYNQ的光流計算的IP核。下面針對ZYNQ的體系結構，結合HLS生成的光流算法的IP核，實現(xiàn)稠密光流法在ZYNQ上的軟硬件協(xié)同。圖6所示的是基于ZYNQ的稠密光流法的體系結構圖，ZYNQ系統(tǒng)芯片集成了基于ARM的處理系統(tǒng)（PS）和可編程邏輯（PL）。

圖6 基于ZYNQ光流法軟硬件協(xié)同的結構圖

PL端光流IP核與外部存取器（DDR）的通信方式是基于ARM的AXI4總線協(xié)議，其中PL端的數(shù)據(jù)通路是由視頻直接存取訪問（AXI VDMA，Video Direct Memory Access）來讀寫外部存取器的數(shù)據(jù)，PS端通過通用輸入輸出接口（GPIO）主動控制PL端的控制通路。為了完成外部迭代計算，使用兩個光流的IP核流水地并行計算。光流的IP Core0通過AXI VDMA0讀取數(shù)據(jù)區(qū)A，經(jīng)過光流IP核的硬件延遲，處理完成的結果由AXI VDMA0寫入數(shù)據(jù)區(qū)B；此時控制光流的IP Core1通過AXI VDMA1讀取數(shù)據(jù)區(qū)B，經(jīng)過PL端加速，處理完成的結果由AXI VDMA1寫入數(shù)據(jù)區(qū)A；形成了一個高效的迭代計算環(huán)。

6 綜合實驗

綜合實驗采用平臺是Digilent的Zedboard，其芯片是由FPGA與ARM組成的ZYNQ（ZYNQ7020CLG484）異構系統(tǒng)芯片。對于純軟件的處理方式，光流計算是在ZYNQ上的ARM Cortex-A9（即Processing System，PS）上處理的，其中PS端有兩個32 KB的一級緩存、一個512 KB的共享二級緩沖和512 MB的外部存取器。對于軟硬件協(xié)同的處理方式，ARM端和FPGA端協(xié)同工作。選用的圖片序列是最新的Middlebury[2]光流測試集。

6.1 基于ZYNQ的光流法軟硬件協(xié)同的資源利用率和功耗

表1是基于ZYNQ光流法軟硬件協(xié)同在PL端的資源利用率，其中光流計算的IP核迭代計算（S4）流水的分數(shù)是2。從表中可以看出，F(xiàn)PGA的資源已經(jīng)消耗了很多，如果在硬件資源足夠的情況下，可以把P5做成更多的份數(shù)，這樣可以減少外部迭代的次數(shù)，從而提高整個系統(tǒng)的吞吐率。數(shù)據(jù)通路的工作頻率是100 MHz，控制通路的頻率是50 MHz，而且整個系統(tǒng)的片上功耗只有1.911 W。

表1 PL端的資源利用率

6.2 軟硬件協(xié)同與純軟件工作模式下的計算光流的時間比較與分析

在ZYNQ的ARM端軟件單獨計算稠密光流，隨著圖片的不斷增大，算法的執(zhí)行效率會直線下降；在軟硬件協(xié)同的情況下，F(xiàn)PGA端對核心算法的進行加速運算，ARM端對FPGA端的IP核進行控制。如表2所示，軟硬件協(xié)同執(zhí)行的時間平均要比軟件的執(zhí)行時間快25倍左右，特別是對于大的圖片，比如640×480的分辨率，軟硬件協(xié)同的執(zhí)行時間比純軟件執(zhí)行要快34倍。對于光流算法，分辨率越大，計算出來的光流的細粒度也就越好，效果也就越準確。例外，純軟件工作下的迭代計算方法是原始的SOR迭代方法，迭代的次數(shù)為100；軟硬件協(xié)同的采用改進的Red-Black SOR的迭代方法，迭代的次數(shù)同樣也為100。

表2 基于ZYNQ的光流法軟件與軟硬件協(xié)同的執(zhí)行時間比較

6.3 軟硬件協(xié)同與純軟件工作模式下的計算光流的效果比較與分析

表3所示的是基于HS的光流法軟件與軟硬件協(xié)同工作模式下的光流效果的比較，采用的評價機制是平均角誤差[2]（Average Angular Error，AAE）。其中在純軟件工作模式下，給出了原始的SOR迭代方法與改進的SOR迭代方法的光流效果AAE誤差。實驗結果顯示原始的SOR迭代方法計算的光流的結果更平滑，但是其細粒度的數(shù)據(jù)相關性不適合FPGA的并行計算，而Red-Black SOR在消除了其數(shù)據(jù)相關性的同時，也對其光流效果產(chǎn)生了影響。在軟硬件協(xié)同的情況下，Red-Black SOR的迭代方法與純軟件下的Red-Black SOR的光流效果的誤差主要在硬件模塊內(nèi)部處理使用的定點計算，而軟件使用的是浮點計算，會使得結果更為平滑。表4所示的是軟硬件協(xié)同與軟件光流處理的光流效果對比，其中軟件效果采用的原始的SOR迭代方法，軟硬件協(xié)同效果是改進的Red-Black SOR迭代方法。

表3 軟件與軟硬件協(xié)同的光流效果AAE的評價

表4 軟件與軟硬件協(xié)同的光流效果的比較

7 結束語

在處理640×480大小的圖片時，基于ZYNQ的軟硬件協(xié)同方式比純軟件方式快34倍左右，執(zhí)行時間從24.40 s降到了0.71 s，而ZYNQ芯片的片上功率為1.911 W。如果FPGA資源足夠，通過迭代展開、減少FPGA與存取器的數(shù)據(jù)通信量等方式，還可以進一步提高整個系統(tǒng)的性能。

[1]Horn B K P，Schunck B G.Determining optical flow[J]. Artificial Intelligence，1981，17（1/3）：185-203.

[2]Barron J L，F(xiàn)leet D J，Beauchemin S S.Performance of optical flow techniques[J].International Journal of Computer Vision，1994，12（1）：43-47.

[3]Baker S，Scharstein D，Lewis J P，et al.A database and evaluation methodology for optical flow[J].International Journal of Computer Vision，2011，92（1）：1-31.

[4]Lucas B，Kanade T.An iterative image registration technique with an application in stereo vision[C]//7th International Joint Conference on Artificial Intelligence，Vancouver，Brithish Columbia，1981：674-679.

[5]Bruhn A，Weickert J.Towards ultimate motion estimation：combining highest accuracy with real-time performance[C]// 10th IEEE International Conference on Computer Vision，2005：749-755.

[6]BruhnA.Variationalopticalflowcomputation[D].Saarbrucken：Saarland University，2006.

[7]Mizukami Y，Tadamura K.Optical flow computation on compute unified device architecture[C]//14th International Conference on Image Analysis and Processing（IAIAP），Modena，Italy，2007.

[8]Diaz J，Ros E，Pelayo F，et al.FPGA-based real-time optical-flow system[J].IEEE Transactions on Circuits and Systems for Video Technology，2006，16（2）：274-279.

[9]Martin J L，Zuloaga A，Cuadrado C，et al.Hardware implementation of optical flow constraint equation using FPGAs[J].ComputerVisionandImageUnderstanding，2005，98：462-490.

[10]Rustam A，Hamid N H，Hussin F A.FPGA-based hardware implementation of optical flow constraint equation of Horn and Schunck[C]//4th International Conference on Intelligent and Advanced Sytems（ICIAS），2012：790-794.

[11]Gultekin G，Saranli A.An FPGA based high performance optical flow hardware design for computer vision applications[J].MicroprocessorsandMicrosystems，2013，37：270-286.

[12]Chung E S，Milder P A，Hoe J C，et al.Single-chip heterogeneous computing：does the future include custom logic，F(xiàn)PGAs，and GPGPUs[C]//43rd Annual IEEE/ACM International Symposium on Microarchitecture，Atlanta，USA，2010.

[13]原魁，肖晗，何文浩.采用FPGA的機器視覺系統(tǒng)發(fā)展現(xiàn)狀與趨勢[J].計算機工程與應用，2010，46（36）：1-6.

[14]Chai Zhilei，Shi Jianbo.Improving KLT in embedded systems by processing oversampling video sequence in realtime[C]//International Conference on Reconfigurable Computing and FPGAs，Cancun，Mexico，2011.

[15]朱學亮，柴志雷，梁久禎，等.KLT織物疵點檢測算法研究及FPGA實現(xiàn)[J].計算機工程與應用，2012，48（24）：144-148.

WANG Zhibin,YANG Wenmin,ZHANG Yuanpu,CHAI Zhilei

School of Internet of Things,Jiangnan University,Wuxi,Jiangsu 214122,China

Techniques of optical flow computation are widely used in many video/image based applications such as motion detection,motion estimation and video analysis etc.However,high-quality optical flow algorithms are computationally intensive.Slow computation limits the applicability of optical flow computation in real-world applications,especially in embedded systems.In this paper,an implementation of Horn-Schunck optical flow algorithm based on Xilinx ZYNQ is presented.The High-Level Synthesis（HLS）language together with traditional hardware description language is used to describe optical flow accelerator in the software-hardware co-processing mode.Taking resolution 640×480 as instance, the result shows that FPGA-accelerated HS outperforms 34x than the pure software vision on ZYNQ.The execution time is decreased from 24.40 s to 0.71 s.

optical flow accelerator;ZYNQ;high-level synthesis language;software-hardware co-processing;Field-Programmable Gate Array（FPGA）

光流法是計算機視覺中一個基礎性的算法，可廣泛應用于運動檢測、運動估計、視頻分析等領域。但光流法最大的問題是計算復雜、速度慢，限制了它在實際系統(tǒng)尤其是嵌入式系統(tǒng)中的應用。利用最新的高層綜合（HLS）語言與傳統(tǒng)的硬件描述語言相結合，在Xilinx的FPGA異構系統(tǒng)芯片（即ZYNQ）平臺上，以軟硬件協(xié)同的工作方式，設計了基于Horn-Schunck稠密光流法的硬件加速器。實驗證明，對于640×480大小的圖片，軟硬件協(xié)同處理比純軟件處理的計算性能提高了34倍，執(zhí)行時間從24.40 s降低到0.71 s。

光流加速器；ZYNQ；高層綜合語言；軟硬件協(xié)同處理；可編程器件

A

TP391

10.3778/j.issn.1002-8331.1311-0181

WANG Zhibin,YANG Wenmin,ZHANG Yuanpu,et al.Dense optical flow software-hardware co-processing based on ZYNQ.Computer Engineering and Applications,2014,50（18）：44-49.

國家自然科學基金（No.60703106，No.61170121，No.61202312）。

王芝斌（1989—），男，碩士研究生，主要研究領域為光流場的實時計算、高層綜合語言描述、基于FPGA的機器視覺設計；陽文敏，研究生；張圓蒲，研究生；柴志雷，副教授，碩士生導師。E-mail：zlchai@jiangnan.edu.cn

2013-11-13

2014-01-09

1002-8331（2014）18-0044-06

CNKI網(wǎng)絡優(yōu)先出版：2014-04-01，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0181.html