◆朱大龍 易云山

安全模型、算法與編程

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

◆朱大龍 易云山

（網(wǎng)絡(luò)通信與安全紫金山實(shí)驗(yàn)室 江蘇 211100）

車牌定位是車牌自動(dòng)識(shí)別系統(tǒng)中一個(gè)關(guān)鍵的問題。本文提出了基于SIFT算法的車牌定位算法。首先使用SIFT（Scale-invariant feature transform）算法提取出模板和待定位圖像的特征；然后用最鄰近匹配算法確定模板和待定位圖像特征的匹配關(guān)系，接著用RANSAC（Random Sample Consensus）算法刪除誤匹配關(guān)系并用最小二乘法求取仿射變換模型參數(shù)；再然后根據(jù)仿射變換模型參數(shù)，確定待定位圖像中車牌的位置；最后用GPU（Graphic Processing Unit）對(duì)SIFT進(jìn)行并行加速，提高運(yùn)算速度。由實(shí)驗(yàn)結(jié)果可知，本文所提出的算法對(duì)旋轉(zhuǎn)、縮放等變換的車牌定位準(zhǔn)確且運(yùn)算速度快。

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

隨著人們生活水平的不斷提高，汽車數(shù)量日益增多，這在方便人們生活的同時(shí)也帶來一系列的問題，如車輛管理，交通事故等。為了提高車輛管理效率，減少交通事故，智能交通管理系統(tǒng)（Intelligent Transportation System, ITS）已成為當(dāng)前公路交通、城市交通管理的主要手段和發(fā)展方向，而車牌識(shí)別技術(shù)又是智能交通管理系統(tǒng)的核心技術(shù)。一個(gè)完整的車牌識(shí)別系統(tǒng)主要包括三部分：（1）車牌定位；（2）車牌字符分割；（3）車牌字符識(shí)別。可見，車牌定位是其他兩部分的前提，車牌定位質(zhì)量的好壞直接影響后續(xù)兩部分的質(zhì)量的好壞。所以研究車牌定位技術(shù)具有重要的現(xiàn)實(shí)意義。

隨著國內(nèi)外研究人員的不懈努力，車牌定位算法不斷涌現(xiàn)出來。常用的車牌定位算法主要分為如下幾種：（1）基于邊緣的車牌定位方法[1]；（2）基于車牌色彩分割的車牌定位方法[2]；（3）基于變換域的車牌定位方法[3]。這些方法各有有缺點(diǎn)，基于邊緣的車牌定位方法定位準(zhǔn)確率較高，反應(yīng)時(shí)間短，但當(dāng)背景復(fù)雜時(shí)會(huì)導(dǎo)致定位失??；基于車牌色彩分割的車牌定位方法利用了車牌顏色的信息使得定位更加準(zhǔn)確，但是也會(huì)相應(yīng)加大運(yùn)算量，此外隨著光照變化，拍攝到的車牌顏色也會(huì)發(fā)生變換；基于變換域的車牌定位方法，在噪聲較大時(shí)，定位可能會(huì)失敗，此外需要把圖像從空間域變換到頻率域，這增加了運(yùn)算量和算法的復(fù)雜度。

本文總結(jié)了目前常用的車牌定位方法的優(yōu)缺點(diǎn)，提出了基于SIFT算法的車牌定位方法。2004年，David. Lowe總結(jié)了現(xiàn)有圖像匹配算法的優(yōu)缺點(diǎn)，在此基礎(chǔ)上提出了具有明顯獨(dú)特性的圖像特征，即SIFT特征，該特征對(duì)圖像縮放、旋轉(zhuǎn)、光照變換、輕微仿射變換都具有不變性[4]。由實(shí)驗(yàn)可知，本文所提出的算法定位準(zhǔn)確。

1 SIFT算法

1.1 尺度空間極值點(diǎn)檢測(cè)

圖1 高斯金字塔

圖2 建立過程

1.2 極值點(diǎn)確定位

DoG函數(shù)在圖像邊緣響應(yīng)較差，于是為了進(jìn)一步提高極值點(diǎn)的穩(wěn)定性，需要消除邊緣響應(yīng)的影響。該主曲率可以通過估算該點(diǎn)的二階Hessian矩陣得到：

1.3 關(guān)鍵點(diǎn)主方向的計(jì)算

把范圍為~360度的梯度角均勻分為36份，統(tǒng)計(jì)方向直方圖，用圓形高斯函數(shù)對(duì)關(guān)鍵點(diǎn)局部區(qū)域的梯度分配權(quán)重，把加權(quán)后的梯度加到相應(yīng)的直方圖柱中。尋找高于0.8倍直方圖峰值的位置，對(duì)該位置進(jìn)行拋物線擬合，求出極值點(diǎn)所對(duì)應(yīng)的位置，該位置即為關(guān)鍵點(diǎn)所對(duì)應(yīng)的主方向。

1.4 關(guān)鍵點(diǎn)描述子的計(jì)算

圖3 描述子生成示意圖（）（a）是均與劃分區(qū)域以及梯度、梯度角示意圖，（b）是關(guān)鍵點(diǎn)描述子）

2 RANSAC算法

當(dāng)待定位車牌圖像和車牌模板圖像求取SIFT特征后，接著對(duì)這些特征確定匹配關(guān)系，本文使用最鄰近（Nearest Neighbor， NN）算法進(jìn)行特征點(diǎn)粗匹配[7]。然而經(jīng)過NN匹配算法確定的匹配關(guān)系會(huì)存在誤匹配關(guān)系，為了增加車牌定位的準(zhǔn)確度，本文使用RANSAC算法刪除這些誤匹配關(guān)系[8]。本文使用的是仿射變換模型[9]，該模型能夠適用于現(xiàn)實(shí)生活中絕大部分情況，刪除誤匹配關(guān)系操作如下：

（3）重復(fù)上述兩步驟若干次，選擇內(nèi)點(diǎn)數(shù)最多所對(duì)應(yīng)的次數(shù)，刪除外點(diǎn)數(shù)即為刪除后的匹配點(diǎn)對(duì)。

3 算法并行化研究

SIFT算法以及改進(jìn)的SIFT算法較復(fù)雜，運(yùn)算時(shí)間較長，對(duì)運(yùn)算速度要求較高的場(chǎng)合難以應(yīng)用。由前兩節(jié)可以看出，SIFT算法有大量可以并行化的步驟，對(duì)這些步驟進(jìn)行并行化研究，并在并行化平臺(tái)（GPU）上運(yùn)行可以大幅提高運(yùn)算速度。

3.1 CUDA簡介

GPU最初設(shè)計(jì)目的是輔助CPU進(jìn)行圖像渲染，圖像顯示等工作。隨著GPU性能的不斷提高、架構(gòu)的不斷改良，加上它天生的并行計(jì)算能力，GPU用作通用計(jì)算被越來越多的研究工作者所采納[10]。當(dāng)前，常用的并行處理器有：多核的CPU系統(tǒng)和GPU處理器。為了使得GPU通用編程難度降低，英偉達(dá)公司推出專為通用計(jì)算設(shè)計(jì)的全新CUDA（Compute Unified Device Architecture）架構(gòu)。在該架構(gòu)下，編程人員只要使用類C語言就可以完成GPU的編程，而不需要了解GPU等相關(guān)知識(shí)。CUDA C是對(duì)標(biāo)準(zhǔn)C語言的擴(kuò)展，熟悉C語言的開發(fā)者在不需要專業(yè)學(xué)習(xí)的情況下就能很輕松地使用CUDA C進(jìn)行GPU通用編程。這使得在不需要購買專業(yè)的并行平臺(tái)的情況下，帶顯卡的普通PC機(jī)通過CUDA C就能提高幾個(gè)數(shù)量級(jí)的加速，為科研人員帶來了極大的好處。

3.2 建立高斯金字塔并行化

圖4 高斯并行化流程圖

3.3 建立DoG金字塔并行化

DoG金字塔是由相鄰高斯圖像相減而獲得，這也存在大量的并行化操作。把待相減的兩幅高斯圖像綁定到紋理內(nèi)存中，為圖像中的每一個(gè)像素建立一個(gè)CUDA線程；調(diào)用核函數(shù)，使得每個(gè)CUDA線程完成一個(gè)像素相減操作，結(jié)果存儲(chǔ)在全局存儲(chǔ)器中；待所有像素計(jì)算完畢，結(jié)果拷貝到CPU內(nèi)存中，運(yùn)算完成。

3.4 尋找極值點(diǎn)并行化

極值點(diǎn)是通過比較該點(diǎn)與周圍以及上下兩層共26個(gè)點(diǎn)的像素值大小來確定的，如果該點(diǎn)像素值比26點(diǎn)的像素值都大或者都小，則該點(diǎn)為極值點(diǎn)?？梢?，每個(gè)像素的比較與其他像素的比較結(jié)果無關(guān)，是一個(gè)并行的過程。尋找極值點(diǎn)并行化流程如下：首先，把當(dāng)前層以及上下兩層共三層圖像綁定到紋理內(nèi)存中，以便進(jìn)一步處理；然后，把圖像每個(gè)像素建立一個(gè)CUDA線程塊，對(duì)圖像每個(gè)像素周圍的26個(gè)像素進(jìn)行劃分，為這些像素建立一個(gè)CUDA線程；再然后，調(diào)用核函數(shù)使得每個(gè)線程進(jìn)行一個(gè)像素是否是極值點(diǎn)的判斷，并把比較結(jié)果存儲(chǔ)在全局存儲(chǔ)器中；最后，待所有像素比較完畢，把計(jì)算數(shù)據(jù)復(fù)制到CPU中，算法結(jié)束。

3.5 關(guān)鍵點(diǎn)描述子并行化

首先，把關(guān)鍵點(diǎn)周圍的圓形特征區(qū)域綁定到紋理內(nèi)存中，并劃分為若干子區(qū)域；然后，把每個(gè)子區(qū)域建立一個(gè)CUDA線程塊，為每個(gè)子區(qū)域的像素建立一個(gè)CUDA線程；再然后，調(diào)用核函數(shù)，一個(gè)線程負(fù)責(zé)一個(gè)像素梯度和梯度角的計(jì)算并統(tǒng)計(jì)每個(gè)子區(qū)域的方向直方圖；最后，按一定順序排列得到該關(guān)鍵點(diǎn)的描述子，拷貝回到CPU內(nèi)存中，程序執(zhí)行結(jié)束。

3.6 NN并行化研究

3.7 RANSAC算法并行化

4 實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)所使用的硬件平臺(tái)分別為CPU和GPU，軟件平臺(tái)為VS2010。本實(shí)驗(yàn)使用的CPU的參數(shù)為奔騰雙核，主頻3.00GHz，內(nèi)存為2G，GPU型號(hào)為NVIDA GeForce GT 440。實(shí)驗(yàn)所使用的圖像均有相機(jī)拍攝，如圖5所示為本文定位所使用的模板圖像，它是從圖像中剪切下來并把后面字符用背景色掩蓋而形成。實(shí)驗(yàn)以合肥市以皖A(yù)開頭的車牌檢測(cè)為例。對(duì)于其他字符開頭的車牌，可以用類似的辦法進(jìn)行處理。

圖5 車牌定位模板

用SIFT算法提取模板圖像和待定位圖像關(guān)鍵點(diǎn)并用NN算法進(jìn)行匹配，匹配結(jié)果如圖6所示。圖6(a)中待定位車牌角度較傾斜，(b)中待定位車牌圖像背景較復(fù)雜。由圖可以看出，匹配關(guān)系存在錯(cuò)誤匹配，需要進(jìn)一步刪除。本文用RANSAC算法刪除誤匹配，實(shí)驗(yàn)結(jié)果如圖7所示。

圖6 待定位圖像和模板圖像匹配結(jié)果

待誤匹配關(guān)系刪除以后，直接對(duì)車牌進(jìn)行定位，定位結(jié)果如圖8所示。圖8中紅色的矩形框，即為定位后的結(jié)果。由圖8(a)可見，即使車牌視角變化很大，也能較精確的定位車牌；(b)背景復(fù)雜也能很準(zhǔn)確的確定車牌位置。

最后比較經(jīng)GPU并行化加速后，與傳統(tǒng)串行處理的加速比，實(shí)驗(yàn)結(jié)果如表1所示。由表1可見，經(jīng)GPU加速后加速比約為4，提高了程序的執(zhí)行效率。

圖8 定位實(shí)驗(yàn)結(jié)果

表1 運(yùn)行時(shí)間結(jié)果

5 結(jié)束語

車牌定位是車牌識(shí)別系統(tǒng)非常關(guān)鍵的一步，其質(zhì)量的好壞直接影響到車牌識(shí)別系統(tǒng)質(zhì)量的好壞。本文使用基于SIFT算法的車牌定位算法，對(duì)待定位車牌背景復(fù)雜以及視角偏移較大的圖像都能較準(zhǔn)確的定位車牌，并在此基礎(chǔ)上使用GPU進(jìn)行并行化加速，提高算法的執(zhí)行效率，由實(shí)驗(yàn)結(jié)果可見，本文所提出的算法定位準(zhǔn)確，執(zhí)行效率高。

[1]卓均飛，胡煜. 基于邊緣檢測(cè)和投影法的車牌定位算法研究[J]. 科學(xué)通報(bào), 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ìn)的自適應(yīng)模板匹配法[J]. 微計(jì)算機(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特征點(diǎn)的圖像拼接技術(shù)研究[D]. 西安: 西安電子科技大學(xué), 2009.

[10]譚兵. 圖像顯著性區(qū)域檢測(cè)及其GPU并行計(jì)算[D]. 大連: 大連理工大學(xué), 2012.