一种基于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特征点定义是：在像素点的周围领域内有足够多的像素点与该点处于不同的区域。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三种类型。统计d和b出现的次数N，当N＞n时，那么该中心像素点就认为是候选角点。通常，n可取9、10、11、12。

图1 分割测试角点检测算法示意图

FAST特征提取算子具有计算简单，速度快的优点，但是该特征提取算子不具有方向特性以及尺度特性。

ORB采用灰度质心法解决FAST特征点不具有方向性的问题。灰度质心法假设特征点的灰度与质心之间存在偏移，这个偏移可以用来表示方向［7］。对于任意一个特征点P来说，定义P的邻域Patch像素的矩为

I(x，y)为像素点(x，y)处的灰度值。计算得到邻域Patch的质心为

特征点与计算得到的质心的连线组成的向量的方向即FAST特征点的方向：

2.2 特征描述子

提取到特征点后，需要以一定的方式来描述特征点的属性，描述特征点的属性称为特征描述子（Feature Descriptors）。特征描述子应具备以下性质，即在大小、明暗、方向不同的图像中，同一特征点应具备相似的特征描述子，称为特征描述子的可复现性。

ORB算法采用BRIEF特征描述子并对其进行了改进。和传统的利用区域灰度直方图描述特征点的方法不同，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 尺度归一化

不同传感器采集到的印鉴图像或同一传感器在不同分辨率下采集到的印鉴图像的尺度（图像中印鉴大小）会有所不同。本文利用计算得到的印鉴圆心位置与印鉴半径将待配准的印鉴归一化到同一尺度空间下，再提取特征点。

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 同一坐标系下一对匹配特征点角度关系

根据三角形余弦定理有：

此时计算得到的偏转角度Δθ只是偏转角度的大小，对于偏转角度的方向，需要进一步计算得到。下面，介绍一种通过向量外积（又叫做叉乘，与向量内积区分）来计算偏转角度方向的方法。如图4所示，将图3的坐标轴扩充到三维。

图4 将坐标轴由二维扩充到三维

设 A'点 坐 标 为 (x'，y'，0)，A 点 坐 标 为(x，y，0)，O 为坐标轴原点，坐标为 (0，0，0)，根据向量叉乘公式：

综上，Δθ的范围应为：-180◦≤Δθ＜180◦。设置一个计数器Count[θ]，分别统计每一对匹配的特征点之间的偏转角度，对计算得到的每一个Δθ，将 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 实验结果分析

根据上一小节的分析，本文提出的基于ORB特征的印鉴快速配准算法的步骤如下：

Step1.计算待配准印鉴圆心与半径，进行尺度归一化；

Step2.提取待配准印鉴与标准印鉴的ORB特征点，并计算特征点描述子；

Step3.特征点匹配；

Step4.使用RANSAC算法消除误匹配特征点对；

Step5.计算相对于印鉴圆心的偏转角度。

为测试本文提出算法的性能，本节设计实验进行测试，实验结果表明，本文算法在准确性、适应性与实时性方面均有较大优势。

4.1 印鉴配准

选取50枚印鉴图像作为测试样本，对本文配准算法进行测试。样本中包含尺度不同、偏转角度不同以及存在残缺的印鉴图像，使用Photoshop软件手动计算偏转角度作为实际值。下面以其中一枚存在残缺问题的印鉴为例，说明本文印鉴配准算法流程。

如图5所示为待配准印鉴与标准印鉴图像，待配准印鉴图像存在残缺问题。经人工计算，得到待配准印鉴相对标准印鉴的偏转角度为-7.8°。

图5 待配准印鉴与标准印鉴图像

对图5（a）印鉴图像计算圆心与半径，进行尺度归一化。结果如图6所示（在实际应用过程中，标准印鉴的圆心、半径以及特征点都已预先计算得到）。

图6 归一化后的待配准印鉴与标准印鉴图像

提取归一化后的特匹配印鉴图像与标准印鉴图像的ORB特征点，并计算特征点描述子。如图7所示。

图7 提取得到的ORB特征点

对提取的特征点使用暴力法进行匹配，结果如图8所示。观察可发现存在大量的误匹配特征点。

图8 使用暴力法进行匹配后结果

使用RANSAC算法消除误匹配特征点对。结果如图9所示。

使用本文计算偏转角度的方法，计算每一对特征点对的Δθ以及方向，统计Count[Δθ+180]，绘制Count[Δθ+180]的曲线图，如图10所示，波峰对应的众数点为78，即对应的度数为-7.8°。

图9 消除误匹配特征点后

图10 投票结果

4.2 实验结果统计

统计计算得到的50枚印鉴与标准印鉴的偏转角度，以及耗费时间，得到实验结果如表1所示（部分样本），其中编号加*的代表存在残缺问题的印鉴。表2为本文算法与文献4算法速度对比结果。实验环境为Win10 64位系统，i5，2.30GHz，4GB内存，Visual Studio 2015，OpenCV2.4.10。

表1 部分样本实验结果统计

表2 速度对比

观察表1实验结果，发现本文算法能够准确计算出正常印鉴与存在缺陷印鉴相对于标准印鉴的偏转角度。另外由表2与文献4算法速度对比可发现，采用ORB特征点匹配与投票策略计算偏转角度，能够极大地提高运算速度。可见本文算法具有较高的准确性、适应性与实时性。

5 结语

本文针对圆形印鉴，提出了一种基于ORB特征的印鉴快速配准算法。传统的印鉴配准算法易受噪声或印鉴残缺的影响，且算法速度较慢。本文采用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.