一種基于ORB特征的印鑒快速配準算法?

張鴻志 徐峰磊 任明武

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

1 引言

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

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

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

2ORB特征算子

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

2.1 特征提取算子

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

FAST特征點定義是：在像素點的周圍領域內有足夠多的像素點與該點處于不同的區(qū)域。FAST特征點提取算子的基本原理如下：假設待判斷像素點為P，以P為中心，半徑為3個像素的圓弧經過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出現的次數N，當N＞n時，那么該中心像素點就認為是候選角點。通常，n可取9、10、11、12。

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

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

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

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

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

2.2 特征描述子

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

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

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

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

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

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

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

1）解決噪聲敏感的問題

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

2）解決旋轉不變性問題

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

對矩陣S旋轉θ，得到矯正后的Sθ。

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

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

3.1 尺度歸一化

不同傳感器采集到的印鑒圖像或同一傳感器在不同分辨率下采集到的印鑒圖像的尺度（圖像中印鑒大?。兴煌１疚睦糜嬎愕玫降挠¤b圓心位置與印鑒半徑將待配準的印鑒歸一化到同一尺度空間下，再提取特征點。

3.2 特征點匹配

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

3.3 消除誤匹配特征點

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

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

3.4 偏轉角度計算

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

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

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

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

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

根據三角形余弦定理有：

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

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

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

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

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

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

4 實驗結果分析

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

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

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

Step3.特征點匹配；

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

Step5.計算相對于印鑒圓心的偏轉角度。

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

4.1 印鑒配準

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

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

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

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

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

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

圖7 提取得到的ORB特征點

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

圖8 使用暴力法進行匹配后結果

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

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

圖9 消除誤匹配特征點后

圖10 投票結果

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

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

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

表2 速度對比

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

5 結語

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

［1］張躍龍.對紙質文件自動質檢、施印、掃描、裝訂及收集的裝置：中國，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.