0 引言

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

1 Harris角點(diǎn)檢測與匹配算法

1.1 Harris角點(diǎn)檢測

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

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

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

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

    (7)輸出Harris角點(diǎn)的坐標(biāo)。

1.2 Harris角點(diǎn)匹配

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

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

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

[3] 錢博文，李濤，韓俊剛，等.多態(tài)并行處理器中的線程管理器設(shè)計(jì)[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] 汪華琴.基于特征點(diǎn)匹配的圖像拼接方法研究[D].武漢：華中師范大學(xué)，2007.

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

作者信息:

車  芳，韓俊剛，郭志全

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710121)