張鴻志 徐峰磊 任明武

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

印鑒在我國以及亞洲其它一些國家被廣泛使用，并被視為法律意義的標志和證據(jù)。在質(zhì)檢領域所涉及的檢定證書和測試證書上，印鑒是法律與權(quán)威的象征。印鑒圖案的基本要求是：圖案清晰，完整。本文針對印鑒缺陷檢測模塊中［1］印鑒配準問題進行研究。

對于印鑒配準問題，國內(nèi)外學者進行了許多研究。Ueda針對圓形印鑒提出了一種基于印鑒若干局部和全局特征進行模板匹配的方法［2］。該方法適用于圓形印鑒，當印鑒外邊緣存在殘缺時，誤差較大。Fan T J提取印鑒圖案筆畫骨架進行配準，該方法抵抗噪聲能力較差［3］。史晶晶提出了一種基于SIFT特征的印鑒配準算法［4］，該方法魯棒性較高，但是提取SIFT特征速度較慢。梁吉勝針對圓形印鑒，提出一種基于輻射狀模板印鑒配準方法［5］，該方法對于印鑒圖案存在缺陷問題時的效果較差。

本文提出一種基于ORB特征的圓形印鑒快速配準方法，該方法不受印鑒存在缺陷問題的影響，具有較強的適應性與魯棒性，對于存在尺度不一問題的印鑒也能夠準確配準，同時也能夠保證較高的速度。

2ORB特征算子

近些年來，國內(nèi)外學者對局部不變特征進行了大量的研究，提出了多種特征提取算法以及改進算法，其中，SIFT和SURF是最著名的兩種局部特征提取算子。針對SIFT和SURF在實時性上的缺陷，Ethan Rublee等于2011年提出了ORB特征提取算子［6］，極大地提高了局部特征提取速度。該算法在特征點檢測部分利用運算快速的FAST角點提取算子。特征點描述部分利用BRIEF特征描述子。

2.1 特征提取算子

ORB算法采用的是FAST特征提取算子來提取特征點，并給提取到的FAST特征點加入方向信息。

FAST特征點定義是：在像素點的周圍領域內(nèi)有足夠多的像素點與該點處于不同的區(qū)域。FAST特征點提取算子的基本原理如下：假設待判斷像素點為P，以P為中心，半徑為3個像素的圓弧經(jīng)過16個像素點，將其編號為 p1，p2，…，p16，如圖1所示。圓弧上任意一個像素點相對于中心點P，都有三種情況1）darker；2）similar；3）brighter。如式（1）所示。

式（1）中，t是閾值，Ip表示 P點的灰度值，Ip→x表示與P對應編號為x的像素點灰度值。當Ip≥Ip→x+t時，編號為 x的像素點屬于 darker，Sp→x=d ；當 Ip≤Ip→x-t時，編號為 x的像素點屬于 brighter，Sp→x=b；其它情況下，屬于 similar，Sp→x=s。這樣，16個像素點就可以分為d、s、b三種類型。統(tǒng)計d和b出現(xiàn)的次數(shù)N，當N＞n時，那么該中心像素點就認為是候選角點。通常，n可取9、10、11、12。

圖1 分割測試角點檢測算法示意圖

FAST特征提取算子具有計算簡單，速度快的優(yōu)點，但是該特征提取算子不具有方向特性以及尺度特性。

ORB采用灰度質(zhì)心法解決FAST特征點不具有方向性的問題?；叶荣|(zhì)心法假設特征點的灰度與質(zhì)心之間存在偏移，這個偏移可以用來表示方向［7］。對于任意一個特征點P來說，定義P的鄰域Patch像素的矩為

I(x，y)為像素點(x，y)處的灰度值。計算得到鄰域Patch的質(zhì)心為

特征點與計算得到的質(zhì)心的連線組成的向量的方向即FAST特征點的方向：

2.2 特征描述子

提取到特征點后，需要以一定的方式來描述特征點的屬性，描述特征點的屬性稱為特征描述子（Feature Descriptors）。特征描述子應具備以下性質(zhì)，即在大小、明暗、方向不同的圖像中，同一特征點應具備相似的特征描述子，稱為特征描述子的可復現(xiàn)性。

ORB算法采用BRIEF特征描述子并對其進行了改進。和傳統(tǒng)的利用區(qū)域灰度直方圖描述特征點的方法不同，BRIEF描述子采用二進制編碼，能夠很快建立特征描述子，同時減少了特征匹配時間。BRIEF算法的步驟如下［8］：

Step1.對圖像進行高斯濾波以減少噪聲的干擾，方差為2，窗口大小為9×9；

Step2.以特征點為中心，取31×31的鄰域窗口，在窗口內(nèi)隨機選取一對像素點，比較灰度值的大小，按如下方式進行賦值：

x、y為兩個隨機點處的像素灰度值；

Step3.隨機在窗口內(nèi)選取N對像素點，重復Step2，得到一個二進制編碼，該二進制編碼就是對特征點的描述。一般N取值256。

由于BRIEF特征描述子抵抗噪聲能力與抗旋轉(zhuǎn)能力較差。針對這些問題，ORB算法按如下方法對其進行改進。

1）解決噪聲敏感的問題

BRIEF中采用9×9的高斯算子進行濾波，雖然可以一定程度地解決噪聲敏感問題，但是，一個濾波顯然是不夠的，ORB算法的做法是：在31×31的鄰域窗口內(nèi)，產(chǎn)生一對隨機點后，以隨機點為中心，取5×5的子窗口，比較兩個子窗口內(nèi)像素和的大小進行二進制編碼。像素和可以利用積分圖完成。

2）解決旋轉(zhuǎn)不變性問題

要使BRIEF特征描述子具有旋轉(zhuǎn)不變性，就要將特征點的鄰域旋轉(zhuǎn)一個角度，該角度即為FAST特征點的方向θ。在每一個特征點處，將產(chǎn)生的N對隨機點組成一個矩陣S。

對矩陣S旋轉(zhuǎn)θ，得到矯正后的Sθ。

在得到新的隨機點位置后，利用積分圖像進行二進制編碼，即得到ORB特征描述子。

3 基于ORB特征的印鑒配準算法

3.1 尺度歸一化

不同傳感器采集到的印鑒圖像或同一傳感器在不同分辨率下采集到的印鑒圖像的尺度（圖像中印鑒大?。兴煌?。本文利用計算得到的印鑒圓心位置與印鑒半徑將待配準的印鑒歸一化到同一尺度空間下，再提取特征點。

3.2 特征點匹配

對于每個特征點，都會生成一個256位的二進制編碼，該二進制編碼即為特征點描述子。本文使用Hamming距離判斷兩個特征點是否匹配，采用暴力匹配法搜索匹配的特征點對。

3.3 消除誤匹配特征點

由于特征點的提取以及特征點描述子很難達到絕對的精確，再加上圖片噪聲等因素的影響，最初得到的匹配的特征點對中有許多誤匹配特征點。

RANSAC算法［9］是由Fischler和Bolles于1981年提出的。它是根據(jù)一組包含異常數(shù)據(jù)的樣本數(shù)據(jù)集，計算出數(shù)據(jù)的數(shù)學模型參數(shù)，得到有效樣本數(shù)據(jù)的算法。該算法的基本思想是：先設計目標函數(shù)，然后通過反復提取最小點集估計該函數(shù)中參數(shù)的初始值，利用這些初始值把所有的數(shù)據(jù)分為“內(nèi)點”和“外點”，最后用所有的內(nèi)點重新計算和估計函數(shù)的參數(shù)。本文利用RANSAC算法消除誤匹配點。

3.4 偏轉(zhuǎn)角度計算

通常情況下，待配準印鑒與標準印鑒之間相對于印鑒圓形可能會存在一定的偏轉(zhuǎn)角度。計算該偏轉(zhuǎn)角度即可將印鑒配準。

如圖2所示，點O'、O分別為待配準印鑒與標準印鑒的圓心，坐標分別為(x'，y')、(x，y)。點 A'和點A分別為一對匹配的特征點。設點A'坐標為(x0'，y0')，點 A坐標為 (x0，y0)。實線表示圖像坐標系。

圖2 不同坐標系下一對匹配特征點角度關系

設偏轉(zhuǎn)角為Δθ，將待檢測印鑒圓心與標準印鑒變換到同一個坐標系下，如圖3所示。

圖3 同一坐標系下一對匹配特征點角度關系

根據(jù)三角形余弦定理有：

此時計算得到的偏轉(zhuǎn)角度Δθ只是偏轉(zhuǎn)角度的大小，對于偏轉(zhuǎn)角度的方向，需要進一步計算得到。下面，介紹一種通過向量外積（又叫做叉乘，與向量內(nèi)積區(qū)分）來計算偏轉(zhuǎn)角度方向的方法。如圖4所示，將圖3的坐標軸擴充到三維。

圖4 將坐標軸由二維擴充到三維

設 A'點 坐 標 為 (x'，y'，0)，A 點 坐 標 為(x，y，0)，O 為坐標軸原點，坐標為 (0，0，0)，根據(jù)向量叉乘公式：

綜上，Δθ的范圍應為：-180?≤Δθ＜180?。設置一個計數(shù)器Count[θ]，分別統(tǒng)計每一對匹配的特征點之間的偏轉(zhuǎn)角度，對計算得到的每一個Δθ，將 Count[Δθ+180] 加 1， 計 算 得 到 的Count[Δθ+180]應服從高斯分布：

式（13）中，μ和σ分別是均值與標準差。從概率角度分析，這些偏轉(zhuǎn)角計數(shù)器中的眾數(shù)點出現(xiàn)的概率最大［10］，因此，眾數(shù)點對應的偏轉(zhuǎn)角度最可能是待配準印鑒與標準印鑒之間的偏轉(zhuǎn)角度。

實際檢測中，為了提高計算得到的偏轉(zhuǎn)角精度，計數(shù)器的范圍取0～3600，其中0～1800對應偏轉(zhuǎn)角度 -180.0°～0.0°，1800～3600對應偏轉(zhuǎn)角度 0.0°～180.0°。比如755，對應的偏轉(zhuǎn)角度為-75.5°，2400對應的偏轉(zhuǎn)角度為60°。

4 實驗結(jié)果分析

根據(jù)上一小節(jié)的分析，本文提出的基于ORB特征的印鑒快速配準算法的步驟如下：

Step1.計算待配準印鑒圓心與半徑，進行尺度歸一化；

Step2.提取待配準印鑒與標準印鑒的ORB特征點，并計算特征點描述子；

Step3.特征點匹配；

Step4.使用RANSAC算法消除誤匹配特征點對；

Step5.計算相對于印鑒圓心的偏轉(zhuǎn)角度。

為測試本文提出算法的性能，本節(jié)設計實驗進行測試，實驗結(jié)果表明，本文算法在準確性、適應性與實時性方面均有較大優(yōu)勢。

4.1 印鑒配準

選取50枚印鑒圖像作為測試樣本，對本文配準算法進行測試。樣本中包含尺度不同、偏轉(zhuǎn)角度不同以及存在殘缺的印鑒圖像，使用Photoshop軟件手動計算偏轉(zhuǎn)角度作為實際值。下面以其中一枚存在殘缺問題的印鑒為例，說明本文印鑒配準算法流程。

如圖5所示為待配準印鑒與標準印鑒圖像，待配準印鑒圖像存在殘缺問題。經(jīng)人工計算，得到待配準印鑒相對標準印鑒的偏轉(zhuǎn)角度為-7.8°。

圖5 待配準印鑒與標準印鑒圖像

對圖5（a）印鑒圖像計算圓心與半徑，進行尺度歸一化。結(jié)果如圖6所示（在實際應用過程中，標準印鑒的圓心、半徑以及特征點都已預先計算得到）。

圖6 歸一化后的待配準印鑒與標準印鑒圖像

提取歸一化后的特匹配印鑒圖像與標準印鑒圖像的ORB特征點，并計算特征點描述子。如圖7所示。

圖7 提取得到的ORB特征點

對提取的特征點使用暴力法進行匹配，結(jié)果如圖8所示。觀察可發(fā)現(xiàn)存在大量的誤匹配特征點。

圖8 使用暴力法進行匹配后結(jié)果

使用RANSAC算法消除誤匹配特征點對。結(jié)果如圖9所示。

使用本文計算偏轉(zhuǎn)角度的方法，計算每一對特征點對的Δθ以及方向，統(tǒng)計Count[Δθ+180]，繪制Count[Δθ+180]的曲線圖，如圖10所示，波峰對應的眾數(shù)點為78，即對應的度數(shù)為-7.8°。

圖9 消除誤匹配特征點后

圖10 投票結(jié)果

4.2 實驗結(jié)果統(tǒng)計

統(tǒng)計計算得到的50枚印鑒與標準印鑒的偏轉(zhuǎn)角度，以及耗費時間，得到實驗結(jié)果如表1所示（部分樣本），其中編號加*的代表存在殘缺問題的印鑒。表2為本文算法與文獻4算法速度對比結(jié)果。實驗環(huán)境為Win10 64位系統(tǒng)，i5，2.30GHz，4GB內(nèi)存，Visual Studio 2015，OpenCV2.4.10。

表1 部分樣本實驗結(jié)果統(tǒng)計

表2 速度對比

觀察表1實驗結(jié)果，發(fā)現(xiàn)本文算法能夠準確計算出正常印鑒與存在缺陷印鑒相對于標準印鑒的偏轉(zhuǎn)角度。另外由表2與文獻4算法速度對比可發(fā)現(xiàn)，采用ORB特征點匹配與投票策略計算偏轉(zhuǎn)角度，能夠極大地提高運算速度?？梢姳疚乃惴ň哂休^高的準確性、適應性與實時性。

5 結(jié)語

本文針對圓形印鑒，提出了一種基于ORB特征的印鑒快速配準算法。傳統(tǒng)的印鑒配準算法易受噪聲或印鑒殘缺的影響，且算法速度較慢。本文采用ORB算法提取印鑒圖像特征點，極大地加快了算法速度。首先，根據(jù)印鑒半徑大小，將待配準印鑒變換同一尺度下；然后采用ORB算法提取印鑒特征點并進行匹配；再使用RANSAC算法消除誤匹配的特征點；最后采用投票策略計算相對印鑒圓心的偏轉(zhuǎn)角度，實現(xiàn)配準。實驗部分，對本文算法設計實驗，驗證了本文算法具有較高的準確性、適應性與實時性。

［1］張躍龍.對紙質(zhì)文件自動質(zhì)檢、施印、掃描、裝訂及收集的裝置：中國，4159515［P］.2014-10-29.

ZHANG Yuelong.Automatic paper quality inspection，printing，scanning，binding and collection devices：China，4159515［P］.2014-10-29.

［2］Ueda K.Automatic Seal Imprint Verification System with Imprint Quality Assessment Function and Its Performance Evaluation［J］.Ieice Transactions on Information&Sys?tems，1994，77（8）：885-894.

［3］Fan T J，Tsai W H.Automatic Chinese seal identification［J］.Computer Vision Graphics&Image Processing，1984，25（3）：311-330.

［4］史晶晶，杜江，王磊，等.基于SIFT的印鑒配準算法研究［J］.計算機應用與軟件，2013，30（12）：315-317.

SHI Jingjing，DU Jiang，WANG Lei，et al.Research on Seal Registration Algorithm Based on SIFT［J］.Computer Applications and Software，2013，30（12）：315-317.

［5］梁吉勝，吳亞娟，李波，等.基于輻射狀模板的圓形印章配準方法［J］.東北石油大學學報，2011，35（4）：87-90.

LIANG Jisheng，WU Yajuan，LI Bo，et al.Circular Seal Registration Method Based on Radial Template［J］.Jour?nal of Northeast Petroleum University，2011，35（4）：87-90.

［6］Rublee E，Rabaud V，Konolige K，et al.ORB：An effi?cient alternative to SIFT or SURF［C］//IEEE International Conference on Computer Vision.IEEE，2011：2564-2571.

［7］李小紅，謝成明，賈易臻，等.基于ORB特征的快速目標檢測算法［J］.電子測量與儀器學報，2013，27（5）：455-460.

LI Xiaohong，XIE Chengming，JIA Yizhen，et al.Fast Ob?ject Detection Algorithm Based on ORB Feature［J］.Jour?nal of Electronic Measurement and Instrument，2013，27（5）：455-460.

［8］Calonder M，Lepetit V，Strecha C，et al.BRIEF：Binary Robust Independent Elementary Features［C］//Computer Vision-ECCV 2010，European Conference on Computer Vision，Heraklion，Crete，Greece，September 5-11，2010，Proceedings.2010：778-792.

［9］陳付幸，王潤.基于預檢驗的快速隨機抽樣一致性算法［J］.軟件學報，2005，16（8）：1431-1437.

CHEN Fuxing，WANG Run.A Fast Random Sampling Consistency Algorithm Based on Preinspection［J］.Jour?nal of Software，2005，16（8）：1431-1437.

［10］嚴筱永，閻浩，沈維燕，等.基于改進的Hough變換的圓檢測［J］.金陵科技學院學報，2009，25（1）：18-21.

YAN Xiaoyong，YAN Hao，SHEN Weiyan，et al.Circle Detection Based on Improved Hough Transform［J］.Jour?nal of Jinling Institute of Technology，2009，25（1）：18-21.