基于SIFT算法的车牌定位及并行化研究

◆朱大龙 易云山

安全模型、算法与编程

基于SIFT算法的车牌定位及并行化研究

◆朱大龙 易云山

（网络通信与安全紫金山实验室 江苏 211100）

车牌定位是车牌自动识别系统中一个关键的问题。本文提出了基于SIFT算法的车牌定位算法。首先使用SIFT（Scale-invariant feature transform）算法提取出模板和待定位图像的特征；然后用最邻近匹配算法确定模板和待定位图像特征的匹配关系，接着用RANSAC（Random Sample Consensus）算法删除误匹配关系并用最小二乘法求取仿射变换模型参数；再然后根据仿射变换模型参数，确定待定位图像中车牌的位置；最后用GPU（Graphic Processing Unit）对SIFT进行并行加速，提高运算速度。由实验结果可知，本文所提出的算法对旋转、缩放等变换的车牌定位准确且运算速度快。

车牌定位；SIFT算法；RANSAC算法；GPU

随着人们生活水平的不断提高，汽车数量日益增多，这在方便人们生活的同时也带来一系列的问题，如车辆管理，交通事故等。为了提高车辆管理效率，减少交通事故，智能交通管理系统（Intelligent Transportation System, ITS）已成为当前公路交通、城市交通管理的主要手段和发展方向，而车牌识别技术又是智能交通管理系统的核心技术。一个完整的车牌识别系统主要包括三部分：（1）车牌定位；（2）车牌字符分割；（3）车牌字符识别。可见，车牌定位是其他两部分的前提，车牌定位质量的好坏直接影响后续两部分的质量的好坏。所以研究车牌定位技术具有重要的现实意义。

随着国内外研究人员的不懈努力，车牌定位算法不断涌现出来。常用的车牌定位算法主要分为如下几种：（1）基于边缘的车牌定位方法[1]；（2）基于车牌色彩分割的车牌定位方法[2]；（3）基于变换域的车牌定位方法[3]。这些方法各有有缺点，基于边缘的车牌定位方法定位准确率较高，反应时间短，但当背景复杂时会导致定位失败；基于车牌色彩分割的车牌定位方法利用了车牌颜色的信息使得定位更加准确，但是也会相应加大运算量，此外随着光照变化，拍摄到的车牌颜色也会发生变换；基于变换域的车牌定位方法，在噪声较大时，定位可能会失败，此外需要把图像从空间域变换到频率域，这增加了运算量和算法的复杂度。

本文总结了目前常用的车牌定位方法的优缺点，提出了基于SIFT算法的车牌定位方法。2004年，David. Lowe总结了现有图像匹配算法的优缺点，在此基础上提出了具有明显独特性的图像特征，即SIFT特征，该特征对图像缩放、旋转、光照变换、轻微仿射变换都具有不变性[4]。由实验可知，本文所提出的算法定位准确。

1 SIFT算法

1.1 尺度空间极值点检测

图1 高斯金字塔

图2 建立过程

1.2 极值点确定位

DoG函数在图像边缘响应较差，于是为了进一步提高极值点的稳定性，需要消除边缘响应的影响。该主曲率可以通过估算该点的二阶Hessian矩阵得到：

1.3 关键点主方向的计算

把范围为~360度的梯度角均匀分为36份，统计方向直方图，用圆形高斯函数对关键点局部区域的梯度分配权重，把加权后的梯度加到相应的直方图柱中。寻找高于0.8倍直方图峰值的位置，对该位置进行抛物线拟合，求出极值点所对应的位置，该位置即为关键点所对应的主方向。

1.4 关键点描述子的计算

图3 描述子生成示意图（）（a）是均与划分区域以及梯度、梯度角示意图，（b）是关键点描述子）

2 RANSAC算法

当待定位车牌图像和车牌模板图像求取SIFT特征后，接着对这些特征确定匹配关系，本文使用最邻近（Nearest Neighbor， NN）算法进行特征点粗匹配[7]。然而经过NN匹配算法确定的匹配关系会存在误匹配关系，为了增加车牌定位的准确度，本文使用RANSAC算法删除这些误匹配关系[8]。本文使用的是仿射变换模型[9]，该模型能够适用于现实生活中绝大部分情况，删除误匹配关系操作如下：

（3）重复上述两步骤若干次，选择内点数最多所对应的次数，删除外点数即为删除后的匹配点对。

3 算法并行化研究

SIFT算法以及改进的SIFT算法较复杂，运算时间较长，对运算速度要求较高的场合难以应用。由前两节可以看出，SIFT算法有大量可以并行化的步骤，对这些步骤进行并行化研究，并在并行化平台（GPU）上运行可以大幅提高运算速度。

3.1 CUDA简介

GPU最初设计目的是辅助CPU进行图像渲染，图像显示等工作。随着GPU性能的不断提高、架构的不断改良，加上它天生的并行计算能力，GPU用作通用计算被越来越多的研究工作者所采纳[10]。当前，常用的并行处理器有：多核的CPU系统和GPU处理器。为了使得GPU通用编程难度降低，英伟达公司推出专为通用计算设计的全新CUDA（Compute Unified Device Architecture）架构。在该架构下，编程人员只要使用类C语言就可以完成GPU的编程，而不需要了解GPU等相关知识。CUDA C是对标准C语言的扩展，熟悉C语言的开发者在不需要专业学习的情况下就能很轻松地使用CUDA C进行GPU通用编程。这使得在不需要购买专业的并行平台的情况下，带显卡的普通PC机通过CUDA C就能提高几个数量级的加速，为科研人员带来了极大的好处。

3.2 建立高斯金字塔并行化

图4 高斯并行化流程图

3.3 建立DoG金字塔并行化

DoG金字塔是由相邻高斯图像相减而获得，这也存在大量的并行化操作。把待相减的两幅高斯图像绑定到纹理内存中，为图像中的每一个像素建立一个CUDA线程；调用核函数，使得每个CUDA线程完成一个像素相减操作，结果存储在全局存储器中；待所有像素计算完毕，结果拷贝到CPU内存中，运算完成。

3.4 寻找极值点并行化

极值点是通过比较该点与周围以及上下两层共26个点的像素值大小来确定的，如果该点像素值比26点的像素值都大或者都小，则该点为极值点。可见，每个像素的比较与其他像素的比较结果无关，是一个并行的过程。寻找极值点并行化流程如下：首先，把当前层以及上下两层共三层图像绑定到纹理内存中，以便进一步处理；然后，把图像每个像素建立一个CUDA线程块，对图像每个像素周围的26个像素进行划分，为这些像素建立一个CUDA线程；再然后，调用核函数使得每个线程进行一个像素是否是极值点的判断，并把比较结果存储在全局存储器中；最后，待所有像素比较完毕，把计算数据复制到CPU中，算法结束。

3.5 关键点描述子并行化

首先，把关键点周围的圆形特征区域绑定到纹理内存中，并划分为若干子区域；然后，把每个子区域建立一个CUDA线程块，为每个子区域的像素建立一个CUDA线程；再然后，调用核函数，一个线程负责一个像素梯度和梯度角的计算并统计每个子区域的方向直方图；最后，按一定顺序排列得到该关键点的描述子，拷贝回到CPU内存中，程序执行结束。

3.6 NN并行化研究

3.7 RANSAC算法并行化

4 实验结果及分析

本实验所使用的硬件平台分别为CPU和GPU，软件平台为VS2010。本实验使用的CPU的参数为奔腾双核，主频3.00GHz，内存为2G，GPU型号为NVIDA GeForce GT 440。实验所使用的图像均有相机拍摄，如图5所示为本文定位所使用的模板图像，它是从图像中剪切下来并把后面字符用背景色掩盖而形成。实验以合肥市以皖A开头的车牌检测为例。对于其他字符开头的车牌，可以用类似的办法进行处理。

图5 车牌定位模板

用SIFT算法提取模板图像和待定位图像关键点并用NN算法进行匹配，匹配结果如图6所示。图6(a)中待定位车牌角度较倾斜，(b)中待定位车牌图像背景较复杂。由图可以看出，匹配关系存在错误匹配，需要进一步删除。本文用RANSAC算法删除误匹配，实验结果如图7所示。

图6 待定位图像和模板图像匹配结果

待误匹配关系删除以后，直接对车牌进行定位，定位结果如图8所示。图8中红色的矩形框，即为定位后的结果。由图8(a)可见，即使车牌视角变化很大，也能较精确的定位车牌；(b)背景复杂也能很准确的确定车牌位置。

最后比较经GPU并行化加速后，与传统串行处理的加速比，实验结果如表1所示。由表1可见，经GPU加速后加速比约为4，提高了程序的执行效率。

图8 定位实验结果

表1 运行时间结果

5 结束语

车牌定位是车牌识别系统非常关键的一步，其质量的好坏直接影响到车牌识别系统质量的好坏。本文使用基于SIFT算法的车牌定位算法，对待定位车牌背景复杂以及视角偏移较大的图像都能较准确的定位车牌，并在此基础上使用GPU进行并行化加速，提高算法的执行效率，由实验结果可见，本文所提出的算法定位准确，执行效率高。

[1]卓均飞，胡煜. 基于边缘检测和投影法的车牌定位算法研究[J]. 科学通报, 26(3): 438-441.

[2]Xifanshi, Weizhong Zhao, Yonghang Shen. Automatic license plate recognition system based on color image processing [C]. ICCSA , 2005.

[3]R.Parisi. Car plate recognition by neural networks and image processing[J]. In Proc. IEEE ISCAS. USA, 1998.

[4]Lowe DG. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[5]Koenderink, P.V.V. The structure of images [J]. Biological Cybernetics, 1984（50）: 363-396.

[6]Lindeberg, T. Scale-space theory: A basic tool for analyzing structures at different scales [J]. Journal of Applied Statistics, 1994, 21(2): 224-270.

[7]张晶，李志敏，黄凡. 一种改进的自适应模板匹配法[J]. 微计算机信息, 2002, 24(93): 13-16.

[8]M.Fischler, R. Bolles. Random sample consensus: A paradigm for model fitting with application to image analysis and automated cartography [J]. Communications of the ACM, 1981： 381-395.

[9]杨艳伟. 基于SIFT特征点的图像拼接技术研究[D]. 西安: 西安电子科技大学, 2009.

[10]谭兵. 图像显著性区域检测及其GPU并行计算[D]. 大连: 大连理工大学, 2012.