0 引言

    SMT-PAAG是一款由西安郵電大學設計的專用于圖形圖像處理的可編程邏輯陣列的多核處理器。該多線程陣列機^[1]支持3種并行計算模型：數據并行、任務并行、流水線技術。SMT-PAAG整體架構是由16個處理單元PE(Processing Element)互連構成的二維陣列^[2]，包含算術邏輯運算器ALU單元、線程管理器(Thread Manager，TM)^[3]、4個近鄰共享FIFO(First In First out)、數據存儲(Data Memory，D-MEM)、指令存儲(Instruction Memory，I-MEM)、路由器(Router，RU)。本文結合SMT-PAAG平臺特征，主要研究SMT-PAAG陣列機上Harris角點檢測與匹配算法的并行化。

1 Harris角點檢測與匹配算法

1.1 Harris角點檢測

    Harris角點檢測^[4]的原理是使用一個檢測窗口在圖像上移動，當窗口遇到角點時各個方向都有明顯的變化，該點的響應值(角點鄰域內變化強度的平均值)就是Harris角點檢測的標準，當R達到一定閾值時，則判定該點為角點，根據Harris角點檢測原理，設計步驟如下。

    (1)輸入RGB圖像，將其轉換為灰度圖，對灰度圖進行平滑處理得到image。平滑是選擇一個卷積核在整個圖像上移動，利用卷積算法求出中心點的像素值，選取高斯濾波算法，卷積核為：

    (5)閾值操作，選取一個閾值T，掃描R矩陣，用R中的每一個元素和閾值T進行比較，若R中元素的值大于T，保留進入下一步驟進行判定，否則丟棄。

    (6)進行局部極大值抑制，抑制窗口大小為3，掃描R矩陣，判斷元素值與以該點為中心的3×3鄰域的局部極大值是否相同，相同則保留即判定為角點，記錄坐標，否則丟棄。

    (7)輸出Harris角點的坐標。

1.2 Harris角點匹配

    角點匹配是尋找兩幅圖像上角點之間的對應關系。Harris角點的匹配分三步：角點的向量描述、粗匹配、精確匹配。

    Harris角點的向量描述是將角點由點特征轉換為向量特征。粗匹配是初步篩選出兩幅圖像中匹配的角點。精確匹配使用隨機采樣一致性RANSAC^[5]算法。RANSAC屬于迭代算法，常用于參數估計。基本思想是在進行參數估計時，將具體問題抽象成一個目標函數^[6]，隨機選取一組數據估計該函數的參數值，利用這些參數把所有的數據分為兩類：有效數據和無效數據，其中有效數據為滿足估計的部分(內點)，無效數據不滿足估計參數(外點)，多次執行以上操作，直到選出的有效數據在原始所有數據中比例最大的一組參數，RANSAC用于角點精確匹配的主要步驟為：

    (1)根據粗匹配角點對的數目s確定RANSAC迭代次數N，使得精匹配中已匹配的角點對都是內點的概率p足夠高，實際應用中p達到95%即可，取ε為期望任何點對為外點的概率，則：

2 角點檢測與匹配算法的設計與實現

2.1 Harris角點檢測算法的數據并行模塊

    Harris角點檢測就是根據角點的響應值R挑選出合適的點，每個像素點R值的計算是圖像處理上一個局部操作，只與該點的鄰域有關，具有良好的數據并行性。

    根據1.1節中Harris角點檢測步驟，步驟(1)為高斯濾波處理，邊界需要處理；步驟(2)為梯度計算，求水平方向和豎直方向上的梯度，屬于圖像局部操作，而每個線程所需的邊界數據存儲在其他線程的私有存儲，如圖1所示，Thread0需要的邊界數據分別在存放在Thread1和Thread2中，這些數據只有通過線程間通信才能取到，圖中帶箭頭的虛線表示線程間的通信，箭頭方向表示數據的流向，Block3實現框內上下左右4條虛線標記出了需要發送的數據，Thread3要給上(Thread1)、下、左(Thread2)、右4個線程發送數據，同時接收自己所需的數據，這里數據收發使用SMT-PAAG通信中阻塞模式；步驟(6)局部極大值抑制也是局部操作，通信方式與步驟(2)相同。

2.2 Harris角點檢測算法的任務并行模塊

    任務并行Harris角點檢測如圖2所示。高斯濾波由Thread0獨立執行，將結果發送給Thread1，后面計算由Thread0、Thread1和Thread2交叉計算R，這種拆分后的計算消除了線程長時間的等待，算法執行效率更高一些。對于較大分辨率圖像，圖像數據分塊，每個數據塊由3個線程使用任務并行算法進行計算。

2.3 Harris角點匹配算法的數據并行模塊

    Harris角點匹配過程中角點的向量描述和粗匹配屬于圖像的局部操作，用數據并行方式就能實現并行化，這里主要介紹RANSAC的并行設計，基于數據并行提出兩種并行化思路：

    (1)RANSAC是在同一個數據集合(粗匹配的角點)上重復多次執行同一操作(統計內點數目)，將N次重復執行分配給n(最大為16×8)個線程去執行，每個線程都執行一次或者多次并記錄最大的內點數目與相應的變換模型H；對這n個線程，先將PE內部線程使用線程間通信進行兩兩歸并，將結果保存在每個PE的Thread0；再進行PE之間Thread0歸并，將結果歸并到PE5的Thread0，PE間歸并如圖3所示，圖中箭頭表示歸并方向，箭頭上的數字表示歸并的順序，這種歸并方式保證了PE間歸并通信全都使用近鄰通信。

    (2)將RANSAC步驟(3)中誤差計算分配到多個線程計算，具體做法是PE0的Thread0隨機選取點對，計算變換模型H，然后把剩余的角點對進行劃分并加載到多個線程中，同時將H和誤差閾值由PE0的Thread0廣播給所有線程，由這些線程進行誤差計算和內點判定，最后將結果回收到PE0的Thread0上并比較記錄，重復以上操作N次，選出最優結果。

3 實驗結果與分析

    本文以Linux操作系統、SMT-PAAG仿真器為平臺，將Harris角點檢測與匹配算法采用串行和并行的方式分別實現，并比較試驗結果。其中串行實驗是在SMT-PAAG單線程上實現，并行實驗是在SMT-PAAG采用單核多線程（每個PE8個線程）和多核多線程上實現。最后利用OpenCV HighGUI中的API將數據轉換為圖像并顯示。

    用160×128分辨率的圖像在不同數目線程下進行數據并行和任務并行兩種模式的比對實驗。圖4、圖5是兩幅圖像Harris角點檢測的結果，左圖為原始圖像、右圖為非極大值自適應抑制半徑r=10的角點，兩幅圖像部分區域比較平滑，檢測出角點數目并不多，其中圖4右圖上有73個角點，圖5右圖上有49個角點，它們的匹配結果如圖6所示，有15對角點匹配成功，可以看出圖中有些角點未匹配成功，原因是在角點向量化階段，左右重疊部分明亮程度差別太大，使得最后角點的向量表達差別較大。

    表1給出了數據并行Harris角點檢測算法在不同數目線程下執行所需時間，表2為任務并行執行所需時間，圖7為加速比變化曲線，圖8為加速效率變化曲線。從圖7、圖8可以看出，隨著線程數目的增大，加速比增高，加速效率降低。隨著線程數目的增大，每個線程通信數據量減少，但通信復雜度增高并使用了近鄰通信，整個通信的開銷增大，加速效率降低。任務并行的加速比與加速效率變化情況與數據并行基本一致，但是任務并行較于數據并行還是有一定的優勢。

    SMT-PAAG上角點匹配算法中線程間矩陣的計算是相互獨立的，只有在歸并時有少量的通信開銷，因此可以獲得良好的加速比。

4 結束語

    本文結合SMT-PAAG硬件設計的特性，實現Harris角點檢測與匹配算法的并行化，在SMT-PAAG仿真器上進行了對比實驗，分析了實驗結果。實驗結果表明，SMT-PAAG上計算Harris角點檢測與匹配并行相當有優勢。作為國內自主研發的陣列機，SMT-PAAG 上計算機視覺算法高效的并行化實現，為后人在多核平臺的設計和計算機視覺算法并行化上提供了借鑒和參考。

參考文獻

[1] 周佳佳，李濤，黃小康.多核同時多線程處理器的線程調度器設計[J].電子技術應用，2016，42(1)：19-21.

[2] 李濤，楊婷，易學淵，等.螢火蟲2：一種多態并行機的硬件體系結構[J].計算機工程與科學，2014，36(2)：191-200.

[3] 錢博文，李濤，韓俊剛，等.多態并行處理器中的線程管理器設計[J].電子技術應用，2014，40(2)：30-32.

[4] HARRIS C，STEPHENS M.A combined corner and edge detector[C].Alvey Vision Conference.1988,15:50.

[5] 汪華琴.基于特征點匹配的圖像拼接方法研究[D].武漢：華中師范大學，2007.

[6] 郭曉冉，崔少輝.局部特征點的魯棒性數字穩像[J].光電工程，2013(5)：106-112.

作者信息:

車  芳，韓俊剛，郭志全

(西安郵電大學 計算機學院，陜西 西安710121)