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)