基于Zynq的光流法软硬件协同设计与实现
基于Zynq的光流法軟硬件協同實現
一、 前言
光流場(Optical Flow Field)[1]是指圖像中所有像素點構成的一種二維(2D)瞬時速度場，其中的二維速度矢量是景物中可見點的三維速度矢量在成像表面的投影。通過光流場計算能夠在相機運動以及不知道場景信息的情況下檢測出運動對象。因此光流場計算方法（即光流法）在模式識別、計算機視覺以及圖像處理等領域具有極其重要的基礎地位。基于光流可以實現在軍事航天、交通監管、信息科學、氣象、醫學等多個領域的重要應用。例如利用光流場可以非常有效的對圖像目標進行檢測和分割，這對地對空導彈火控系統的精確制導，自動飛行器精確導航與著陸，戰場的動態分析，軍事偵察的航天或衛星圖片的自動分析系統，醫學上異常器官細胞的分析與診斷系統，氣象中對云圖的運動分析，城市交通的車流量進行監管都具有重要價值。
光流在是由于場景中前景目標本身的移動、相機的運動，或者兩者的共同運動所產生的。對光流算法的研究，真正提出有效光流計算方法還歸功于Horn和Schunck [5]在1981年創造性地將二維速度場與灰度相聯系，引入光流約束方程的算法，是光流算法發展的基石。在此基礎上出現了大量的方法來解決這一問題：變分光流法，如Combing-Brightness-Gradient [6]、Combing-Local-Global [7]；局部差分法，如Lucas-Kanade [2]、Farneback [10];?基于特征的方法，如Wills [11];?基于匹配的方法，如Anandan [12]；基于頻域的方法，如Heeger [13];?以及基于相位的光流法：Fleet [14]。其中，變分光流法以其透明建模、旋轉的不變性、稠密光流場和高質量光流場?[8] [9]成為了光流計算的首選。下面以變分光流法為主線，從計算效果和計算性能兩個方面來闡述。
在研究提高光流場計算效果的過程中，Horn和Schunck [5]根據同一個運動物體的光流場具有連續、平滑的特點,?提出一個附加約束條件，將光流場的整體平滑約束轉換為一個變分的問題；為了處理分段平滑的和不連續的光流場，Enkelmann [12]在Horn和Schunck的模型上引入了二次的平滑項約束；?Weickert和Schnorr [15]在平滑項上引入了魯棒性的非二次的平滑項約束以減少外部影響；同樣地，在也有了非二次的數據項約束；在光照不均衡的情況下，灰度守恒不能很好的計算光流，為此Brox等人?[7]提出了梯度守恒。Lucas-Kanade [2]局部光流法的魯棒性更好，而全局光流法計算出的是稠密光流法，因此，Bruhn等人?[7]提出了CLG的光流能量模型；為了處理較大位移的運動模型，Brox等人[8] [16]引入了一種非線性的能量守恒的能量方程。
在研究提升光流場計算性能的過程中，Black和Anandan [17]提出了由粗到精的金字塔多級結構的計算方法；Bruhn和Weickert [18]提出了多尺度的解決方法；Gwosdek [19]提出了一種線性的多尺度紅黑超松弛計算方法。隨著CUDA技術的發展，基于GPU的光流計算系統?[20]也受到了更多關注。由于細粒度并行支持、硬件的可重構特性及更適合嵌入式系統中實現等原因，基于FPGA的光流系統?[21] [22] [23]的高性能實現受到了最多的關注。
目前，限制光流法廣泛應用的最大難題在于計算耗時，實時性差。比如常用的KLT光流法[2][3]，當要處理的圖像分辨率為1024*768，特征點數為1000時，在主頻3GHz的P4處理器下每秒鐘只能處理約2-3幀圖像[4]。而稠密光流法[5][6][7]，其因需要上千次迭代才能得到最優解，在現有的硬件架構下，計算相當耗時，幾秒鐘甚至更長時間才能處理完一幅圖像，顯然遠遠無法滿足實時處理的需要。隨著異構芯片的發展，Chun [24]等人認為異構芯片有優勢打破傳統硬件單一體系結構的局限，因此，這為光流場的實時計算提供了可能。Xilinx [25]在2012年率先推出了基于Zynq-7000的體系結構的異構芯片,集成了ARM和FPGA到一塊芯片。Zynq-7000?系列器件將處理器的軟件可編程能力與?FPGA?的硬件可編程能力實現完美結合，以低功耗和低成本等系統優勢實現無以倫比的系統性能、靈活性、可擴展性。
本項目通過分析與研究變分光流法計算效率、硬件加速方法及最佳軟硬件協作方式，在Zedboard實現上對光流場的實時計算。其中變分光流法的模型是基于Horn-Schunck [5]。如圖1所示，項目實現的基本流程是：1)?先對光流算法的基本理論進行分析，包括算法的工作流程、計算復雜性、可并行性和軟硬件模塊的劃分。2)關鍵接口層實現，特別是ARM與FPGA之間大數據通信的并行訪問機制、高級語言對硬件結構化的描述。?3）系統設計接口層實現，比如ARM控制FPGA的IP核的初始化、配置和啟動，以及軟硬件協同的設計，最終基準數據測試。
二、光流算法介紹
本項目采用的光流算法是基于Horn-Schunck [5]的模型,?與Lucas- Kanade [2]光流算法相比，它算出的光流更稠密，能夠精確到每一個像素點；但是它因需要求解歐拉-拉格朗日方程需要成大量的迭代，因此計算光流的時間相當耗時，比如在Zedboard的單核ARM上處理640x480的圖片序列需要24.14s才能完成，這表明在傳統單架構的嵌入式平臺上很難滿足光流場實時計算的要求。
1.?基于Horn-Schunck模型的光流算法
1.1?????光流的約束條件
光流 的假設條件認為圖像序列,在時間t 的某一像素點與在時間t+1的這一像素點的偏移量保持不變，即?。這就是灰度值守恒假設，通過Taylor展開，就能得到光流的約束條件(OFC):?，其中下標表示圖像的梯度。
1.2?????Horn-Schunck?模型
1981年，Horn和Schunck根據同一個運動物體的光流場具有連續、平滑的特點,?提出一個附加約束條件，將光流場的整體平滑約束轉換為一個變分的問題。它的能量方程如下：
???????其中數據項表示灰度值守恒約束，平滑項表示光流平滑約束。
1.3?????Euler-Lagrange方程
根據Horn-Schunck能量方程，可以推導出離散的歐拉-拉格朗日方程如下：
其中，?表示圖像像素點的坐標，??表示一個像素點的上下左右四個方向的相鄰的像素點，當然，在圖像的邊界會少于四個元素。
1.4?????超松弛迭代?（SOR）
根據上面的歐拉-拉格朗日方程，不難推到出迭代方程。這里選用收斂速度最快的超松弛算法（SOR），光流的初始值是，迭代方程如下：
??????
其中，??w是迭代的權重因子, k?是迭代的次數，?是光流的計算的權值，?表示第?個像素點的上和左的相鄰像素點，表示第?個像素點的下和右的相鄰像素點。
2? ? ?工作流程介紹
根據上面的理論分析，可以把光流法的計算劃分為四個階段：預處理階段（P1）、梯度計算階段（P2）、運動模型構造階段（P3）和迭代階段（P5），如圖2所示。
2.1?????預處理階段（P1）
這一階段是平滑處理的圖像序列，它的作用是用來減少圖像噪音和外部的影響，通常用卷積來實現的。這一階段是一個通用的圖像操作。
2.2?????梯度計算階段（P2）
這一階段是用來計算平滑好的圖像的梯度，包括水平梯度、垂直梯度和時間梯度。計算梯度通常也是通過卷積來實現的。
2.3?????運動模型構造階段（P3）
這一階段是根據計算出來的梯度來構造運動模型的信息。根據超松弛公式可以推出需要構造五個運動模型的信息，即J11、J12、J13、J22、J23。它的操作就是矩陣乘法。
2.4?????迭代階段（P4）
這一階段就是通過超松弛算法計算光流的結果，每一次迭代完了需要把光流的信息更新一遍，再作為初始值進行下一次迭代。這一階段的操作是根據迭代公式來實現的。
圖?1??算法的工作流程
2.3?????軟件的執行時間
軟件的實驗平臺是在Zedboard上ARM Cortex-A9處理器上來測試的，其中包括2個32KB?一級緩存和512KB的共享二級緩存，以及512MB的內存空間，采用的測試集下載自http://vision.middlebury.edu/flow/data/。Horn-Schunck光流算法是通過ANSI C實現的。其中迭代的次數設為100次。
基于Horn-Schunck模型的稠密光流法在軟件上的執行時間如表1所示，不難發現，隨著圖像的不斷變大，所需要的執行時間不斷增大；其中迭代部分（P4）占到很大的時間比例。
| Images | Size | Modules[s] | Total Time [s] | |||
| P1 | P2 | P3 | P4 | |||
| Yosemite | 316x252 | 0.25 | 0.11 | 0.03 | 4.40 | 4.85 |
| Venus | 420x380 | 0.52 | 0.21 | 0.05 | 9.99 | 10.85 |
| RubberWhale | 584x388 | 0.74 | 0.29 | 0.08 | 14.41 | 15.63 |
| Grove2 | 640x480 | 1.00 | 0.40 | 0.10 | 22.49 | 24.14 |
? ? ? ? ? ? ?
?? ?表1??軟件執行算法的時間
三、并行性分析
? ? ?在分析了各個模塊及整個光流算法的軟件執行時間，有必要從任務并行、數據并行和流水線并行給出它們的并行性分析，進行軟硬件協同劃分。
3.1 任務并行
任務并行就是把處理數據粗粒度地劃分為各個模塊，每一個模塊的相應數據都能夠獨立處理。在理想狀況下，在有足夠硬件資源的情況下，并行化的HS工作流程如圖3所示。
圖3 任務并行化的HS光流計算
具體地說，兩張要處理的圖片（img1和img2）經過兩個并發進行的平滑后得到平滑后的圖片（simg1和simg2）；然后通過水平、垂直和時間梯度的三個任務的并發計算同時得到Ex、Ey和Et;然后通過五個矩陣乘法器得到模型運動的信息（J11、J12、J13、J22和J23）；最后再送給迭代模塊。
3.2 數據并行
數據并行就是處理的數據進行細粒度地劃分，也就是具體到模塊內部。預處理階段（P1）和梯度計算階段（P2）通過卷積來運算，運動模型構造階段(P3)通過簡單的矩陣相乘，這三個模塊的才做很通用，沒有太大的數據相關性，因此特別適合做數據并行。然而，迭代階段（P5）的數據并行性不是很好，它的數據相關性很大，在硬件設計時，如何消除這一數據相關性是關鍵。
3.3 流水線并行
流水線并行特別適合FPGA處理，在HS光流算法中，如何銜接各個模型間的計算節點，特別是迭代部分的結算節點成了制約流水線關鍵的一個因素。
圖4 光流場計算的模塊間的流水線
如圖4所示，P4模塊需要迭代100次，然而前面的P1、P2、P3模塊處理完成的數據如果P4來不及處理的哇，就會造成大量的數據丟失，因此需要存到外部空間，才能讓數據不會丟失，這就制約了流水線的性能，是整個流水系統陷入了惡性循環中。
四、基于Zynq的系統設計
在分析了算法的并行性后，下面將從硬件設計、軟件設計與系統的優化等角度來說明如何在Zedboard上實現與優化復雜的圖像算法的加速機制。
4.1 流水線設計
根據上一章的流水線并行性的分析，可以知道迭代模塊是破壞流水性能下降的一個關鍵點，降低或者消除它的影響成為一個關鍵點。從流水線的角度，可以通過拉長流水線的級數，來增加流水線的性能；也就是在迭代內部，使用多份P4模塊來緩沖從P3級進來的數據，減少了外部迭代的次數，如圖5所示。
圖5 流水線的優化1
從通信量的角度，光流場的計算需要迭代，需要高速并行訪問存儲器的結構，因此，數據位寬的大小對通信量有很大的影響。比如迭代的起始點放在P4上，需要256-bit的數據位寬即（J11, J12, J13, J22, J23, u, v），這樣會對存儲器的讀寫速率有很高的要求，然而一旦存儲器達不到，也同樣會堵塞數據流的操作。因此，選擇合適的迭代起始點也是一個很重要的因素。如圖6所示，如果把迭代的起始點放在P1模塊，只需要128-bit的數據位寬即（img1，img2，u, v），相比較圖5的流水線結構，它的通信量會下降一半。
圖6 流水線的優化2
4.2 迭代系統的設計
在優化完算法的流水線后，流水線與存儲器的接口需要進一步優化。在Zedboard的PL端FPGA與DDR的通信方式是基于AXI總線協議的，PL端通用AXI VDMA來讀寫DDR的數據，具體的硬件結構圖如圖7表示。
圖7 迭代系統的硬件結構圖
數據流從HP0口通過VDMA0的MM2S端流到光流算法的IP核，經過流水線處理后寫到VDMA0的S2MM端，從VDMA0的S2MM端把數據流寫到輸出數據區；接著VDMA1的MM2S從HP2口讀更新好的值，送給光流算法的IP核處理，處理完的數據由VDMA1的S2MM寫入輸入數據區；這樣流水線的輸入輸出數據才能與DDR高效地流起來。
4.3 光流算法IP核的設計
根據第三章的并行性分析可知，在光流場計算的內部，迭代階段的并行性不是很好，具體地表現為每產生一個像素點的光流新值都會去更新，也就是一個像素點與之相鄰的上下左右四個像素點的光流值有數據依賴性，因此，消除數據相關性會大大地提高算法的并行性。在設計FPGA的IP核時，采用改進的奇偶超松弛迭代法，能夠有效地消除光流的數據相關性。如圖8所示，紅顏色表示奇數層的迭代，等奇數層的迭代完成之后偶數層再迭代，這樣大大提高了算法的并行性。
圖8 奇偶機制的數據相關性
光流算法的IP核是使用Xilinx的高層綜合語言（HLS）來實現的，它能快速地把C、C++和SystemC三種高層次的軟件語言轉化為VHDL或者Verilog的硬件描述語言。
圖8顯示了簡單的綜合流程，從C/C++/SystemC設計開始。C/C++/SystemC 測試平臺用于驗證設計功能的正確性，同時還可用于RTL和C的協同仿真。協同仿真包括驗證生成的RTL設計（.v或.vhd）功能，這要使用C/C++/SystemC測試平臺而不是RTL測試平臺或者采用e或Vera驗證語言編寫的測試平臺。時鐘周期約束設置了設計應該運行的目標時鐘周期。設計將被映射到目標FPGA器件——Xilinx FPGA上，如圖9所示。
圖9 采用Vivado HLS進行FPGA綜合的流程
對于Vivado HLS中的許多高級特性而言，需要了解什么樣的硬件架構，從而進行源代碼的調整, 具體地開發手冊可以參考[26]。為了適應不同圖片的大小，增強IP核的通用性，綜合硬件資源等方面的考慮，調用IP核中圖片寬度最大支持到640，具體的光流算法的HLS設計可以參考我們的源代碼。
4.4 FPGA的資源利用率
表2是在Zedboard下FPGA的資源利用率，其中光流計算的IP核中P5的硬件結構是2份，數據通路的工作頻率是100MHZ，控制通路的工作頻率是50MHZ。從表中可以看出，FPGA的資源已經消耗了一大半，如果在硬件資源足夠的情況下，可以把P5做成更多的份數，這樣可以減少外部迭代的次數，從而提高整個系統的吞吐率。
表2 FPGA的資源利用率
4.5 軟硬件協同設計
在硬件結構的設計中，模塊中需要軟件去控制或者配置FPGA的IP核,這些信號線通過AXI4-lite總線映射到內存區域，也就是地址線。這樣就使得硬件的可擴展性大大地增強。光流算法的IP核的地址控制信號如表3所示，通過地址信號線的寄存器的設置對FPGA的IP核進行軟件配置、復位、啟動。VDMA的IP核的控制可以參考[27] 。
表3 光流計算的IP核的軟件控制
Note: SC = Self Clear, COR = Clear on Read, TOW = Toggle on Write,
COH = Clear on Handshake
五、實驗
5.1 迭代對時間的影響
不同的迭代次數對算法的執行效率有很大的影響，如圖10所示，?HSW表示軟硬件協同的執行時間，對應于左邊的時間標注；?SW表示軟件的執行時間，對應于右邊的時間標注；測試圖片大小為640x480。隨著迭代次數的增加，不管是軟件還是軟硬件協同，系統的執行時間都會有相應的增長；但是軟件的執行時間隨著迭代次數的增加，上升的幅度比軟硬件的執行時間要大得多。然而軟硬件協同工作的方式的執行時間在同樣的迭代次數下比純軟件操作要快35倍。
圖10?迭代次數對執行時間的影響
5.2 不同圖片大小對時間的影響
在通用CPU的環境中，如純ARM處理器下，隨著圖片的不斷增大，算法的執行效率會直線下降；在軟硬件協同的情況下，FPGA對核心算法的進行加速運算，軟件對FPGA內部的IP核進行控制，以及加載初始化數據與保存最種結果。從表4下可以看出，隨著圖片的變大，FPGA處理的部分增長的很小，ARM外圍控制的時間顯得就突出出來；但是軟硬件協同執行的時間平均要比軟件的執行時間快25倍左右，特別是對于大的圖片，比如640x480的分辨率，軟硬件協同的執行時間比純軟件執行要快35倍。對于光流算法，分辨率越大，計算出來的光流的細粒度也就越好，效果也就越準確。
| Image | Size | SW Time [s] | HSW Time [s] | ||
| HW | SW | Real Time | |||
| Yosemite | 316x252 | 4.84 | 0.26 | 0.12 | 0.38 |
| Venus | 420x380 | 10.99 | 0.26 | 0.23 | 0.49 |
| RubberWhale | 584x388 | 15.16 | 0.28 | 0.33 | 0.61 |
| Grove2 | 640x480 | 24.18 | 0.29 | 0.42 | 0.71 |
表4?不同圖片大小對時間的影響
5.3 ? 軟件和軟硬件協同工作效果的比較
軟件與軟硬件協同工作的光流場計算效果如圖11所示，實驗效果表明，在同樣的配置參數下，軟硬件協同計算光流的效果與軟件計算的光溜效果相差不大。在Yosemite圖片中，底部出現了一些瑕疵點，原因是計算光流的IP核里面的一些數據還停留在流水線里，需要再添加幾行的數據將其頂出來。
?
? 圖11?軟件與硬件效果圖比較
六、實驗
參考文獻
[1]?http://en.wikipedia.org/wiki/Optical_flow.
[2] Bruce D. Lucas and Takeo Kanade, An iterative image registration technique with an application to stereo vision, Proceedings of Imaging Understanding Workshop, 1981, pp. 121-130.
[3] Jianbo Shi and Carlo Tomasi, Good features to track, IEEE Conference on Computer Vision and Pattern Recognition, (CVPR 1994), pp. 593-600.
[4] M. P. Sudipta, N. Sinha, Jan-Michael Frahm and Y. Genc, Feature tracking and matching in video using programmable graphics hardware, Machine Vision and Applications, 2007, vol. 30, pp. 185-198.
[5] Berthold K.P. Horn and Brian G. Schunck, Determining optical flow, Artificial Intelligence (AI 1981), Volume 17, Issues 1-3, pp. 185-203.
[6] T. Brox, A. Bruhn, N. Papenberg, and J. Weickert, High accuracy optical ?ow estimation based on a theory for warping, 8th European Conference on Computer Vision (ECCV 2004), pp. 25-36.
[7] A. Bruhn, J. Weickert, and C. Schnorr, Lucas/kanade meets horn/schunck: Combining local and global optic flow methods, International Journal of Computer Vision (IJCV 2005), 61:3, pp. 211–231.
[8] J.L. Barron, D.J. Fleet, S.S. Beauchemin, Performance of optical flow Techniques, International Journal of Computer Vision (IJCV 1994), 12:1, pp.43-77.
[9] S. Baker, D. Scharstein, J. Lewis, S. Roth, M. J. Black, and R. Szeliski, A database and evaluation methodology for optical ?ow. International Journal of Computer Vision (IJCV 2011) 92, 1–31.
[10] G. Farneback. Very high accuracy velocity estimation using orientation tensors, parametric motion, and simultaneous segmentation of the motion ?eld. In Proc. Eighth International Conference on Computer Vision (ICCV 2001), volume 1, pp.171–177.
[11] J. Wills, S. Agarwal, and S. Belongie. A feature-based approach for dense segmentation and estimation of large disparity motion. International Journal of Computer Vision (IJCV 2006), 68:2, pp.125–143.
[12] Anandan P, A computational framework and an algorithm for the measurement of visual motion, International Journal of Computer Vision (IJCV 1989) 2, pp. 283-310.
[13] Heeger D.J, Optical flow using spatiotemporal filters, International Journal of Computer Vision (IJCV 1990) 1, pp. 279-302.
[14] Fleet D.J. and Jepson A.D, Computation of component image velocity from local phase information, International Journal of Computer Vision (IJCV 1990), Vision 5, pp. 77-104.
[15] J. Weickert and C. Schnorr,CHNORR, A theoretical framework for convex regularizers in pde-based computation of image motion. International Journal of Computer Vision (IJCV 2001), 45: 3, pp. 245–264.
[16] Thomas Brox, Jitendra Malik, large displacement optical flow: descriptor matching in variational motion estimation, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI 2011), pp. 500 - 513.
[17] M. J. Black and P. Anandan, The robust estimation of multiple motions: Parametric and piecewise smooth ?ow ?elds, Computer Vision and Image Understanding (CVIU 1996), 63:1, pp. 45–104.
[18] A. Bruhn and J. Weickert, A multigrid platform for real-time motion computation with discontinuity-preserving variational methods, International Journal of Computer Vision(IJCV 2006), 70, pp. 257–277.
[19] P. Gwosdek, A. Bruhn, and J. Weickert, Variational optic flow on the sony playstation 3. Real Time Image Proc ( RTIP 2010), 5.
[20] H. Grossauer and P. Thoman, Gpu-based multi-grid:real-time performance in high resolution nonlinear image processing. International Conference on Computer Vision System (ICVS 2008), pp.141–150.
[21] Zhilei Chai, Jianbo Shi, Improving KLT in embedded systems by processing oversampling video sequence in real-time, 5th International Conference on Reconfigurable Computing and FPGAs (Reconfig2011), pp. 297-302.
[22] J. L. Martin, A. Zuloaga, C. Cuadrado, J. Lazaro and U. Bidarte, Hardware implementation of optical flow constraint equation using FPGAs, Computer Vision and Image Understanding (CVIU 2005), pp. 462-490.
[23] R. Rustam, N. H. Hamid and F. A. Hussin, FPGA-based Hardware Implementation of Optical Flow Constraint Equation of Horn and Schunck, 2012 4th International Conference on Intelligent and Advanced Systems (ICIAS2012), pp. 790-794.
[24] E. S. Chung, P. A. Milder, J. C. Hoe, and K. Mai, “Single-Chip Hetero-
geneous Computing:Does the Future Include Custom Logic, FPGAs, and
GPGPUs,” in Proc. 43rd Annual IEEE/ACM International Symposium on
Microarchitecture, Atlanta, GA, Dec 4-8, 2010.
[25] Xilinx. [Online]. Available:?http://www.xilinx.com/products/silicon-devices/soc/zynq-7000/index.htm
總結
以上是生活随笔為你收集整理的基于Zynq的光流法软硬件协同设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： WIN10 3个手指拖动_用好笔记本的触
- 下一篇： 思科ISR4400交换机查看光模块光功率