0 引言

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

1 Harris角點檢測與匹配算法

1.1 Harris角點檢測

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

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

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

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

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

1.2 Harris角點匹配

    角點匹配是尋找兩幅圖像上角點之間的對應(yīng)關(guān)系。Harris角點的匹配分三步：角點的向量描述,、粗匹配,、精確匹配。

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

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

2 角點檢測與匹配算法的設(shè)計與實現(xiàn)

2.1 Harris角點檢測算法的數(shù)據(jù)并行模塊

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

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

2.2 Harris角點檢測算法的任務(wù)并行模塊

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

2.3 Harris角點匹配算法的數(shù)據(jù)并行模塊

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

4 結(jié)束語

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

參考文獻

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

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

[3] 錢博文,，李濤,，韓俊剛，等.多態(tài)并行處理器中的線程管理器設(shè)計[J].電子技術(shù)應(yīng)用,，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] 郭曉冉,，崔少輝.局部特征點的魯棒性數(shù)字穩(wěn)像[J].光電工程,，2013(5)：106-112.

作者信息:

車  芳，韓俊剛,，郭志全

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