基于图像处理的人民币碎片匹配定位

庄俊东

（上海交通大学，上海 200240）

1 引 言

日常生活中经常会碰到大额人民币因为保管不善而变成一堆烂钞，这种情况在偏远农村普遍存在。由于农村基层金融机构缺乏，农民通常将现钞保存在手上，经常遭到虫咬鼠啃、火烧水浸，辛苦得来的钱财成了一堆碎片。若这些碎片拿到银行去兑换，依据相关规定，残币须拼出大于原图的50%方允许兑换。用人工方法进行拼接，费时费力。因此，有必要开发一种机器方法对碎片进行自动拼接。

要实现这种自动拼接，首先要找到人民币碎片在基准图上的位置，也就是要找到一种恰当的图像匹配方法。一般而言，图像匹配的算法可分为两类：（1）是基于图像灰度的匹配算法；（2）是基于图像特征的匹配算法。由于基于灰度的匹配算法计算量大，Barnea于1972年提出序贯相似性算法——SSDA法，而Wong于1978年提出分层序贯匹配算法以加快速度[1]。传统的基于灰度的匹配方法虽然在匹配精度，对噪声具有鲁棒性等方面具有优势，但对待匹配图像间的角度旋转敏感。当待配图像间存在相对的旋转角时，就会发生错误匹配。为克服这一缺陷，有人提出了改进算法[2]。由于人民币碎片图像不可能与基准图保持平行关系，因此要想将基于灰度的匹配算法用于碎片图像匹配，就必须使用改进算法。基于特征的匹配算法[3-5]，则是基于图像的边缘、特征点、纹理等特征，将图像的匹配转化为少量特征的匹配，从而可提高匹配速度。

人民币碎片图像的匹配定位分两步进行。第一步，找到碎片图像相对于基准图的旋转角；第二步，对碎片图像进行角度矫正，再使用传统的灰度互相关法找到碎片图像在基准图中的确切位置。

2 碎片图像相对于基准图旋转角度的确定

利用灰度互相关方法考察图像间的相似性，一种常用的方法是计算这两幅图像对应点之间灰度值的差异，如公式（1）所示：

其中：f（x，y）——基准图上（x，y）点处的灰度值；

t（x-u，y-ν）——模板上相当于人民币碎片图上与f（x，y）在对应点处的灰度值；

u，ν——模板在基准图上沿x轴，y轴的移动值。

假设模板（即碎片）相对于基准图（即整张人民币图）无角度旋转，将模板沿x方向，y方向进行遍历搜索到（u，ν）处，在基准图上与碎片图相对应的区域，若式（1）右边的值为零，此时相似性最大，两幅图像完全一致。

将式（1）右边展开，得：

定义相关系数：

c值越大，d2f，t（u，ν）值越小，两图间的相似性越好。但c（u，ν）不能直接用于判断两幅图像间的相似性。原因在于：（1）假设基准图中某位置的f（x，y）恒等于灰度最大值，则c（u，ν）的值达到最大值，但此时d2f，t（u，ν）的值不会是所有位置中的最小值；（2）c（u，ν）的大小受匹配图像大小的影响；（3）c（u，ν）的值受基准图亮度的影响。为克服以上不足，则提出了归一化的互相关系数[6]：

用以判断两幅图像间相似性的大小。

为得到碎片图像相对于基准图的旋转角度，可将基准图在0°～360°逐度旋转。在每一角度上，求出两图的最大互相关系数γ（u，ν），这些相关系数在正确的角度上将达到最大值，由此可得两图间的相对转角[2]。而基于Radon变换，首先对图像进行边缘检测，得到一二值图，对该二值图作Radon变换。设两图间有θ角的夹角，则基准图在θ角时的Radon变换与模板图在0°时的Radon变换相同。更详细的原理可参见文献[7-8]。

3 仿真及实验

3.1 仿真

图1 基准图

图2 旋转后的图

图3 截取图

图1是Matlab图像处理工具箱中的Cameraman.tif图片，在这里作为基准图，是256×256大小的灰度图。图2为图1逆时针旋转31°后所得，大小与图1相同。图3（a）、图3（b）均为从图2中截取的一部分。图3（c）为将基准图逆时针旋转140°后从中截取的一部分。图3（d）为将基准图逆时针旋转224°后从中截取的一部分。图3（e）为将基准图逆时针旋转316°后从中截取的一部分。分别用前述方法利用Matlab图像处理工具箱对各图进行测试，结果如表1所示。

表1 两种方法求旋转角度的比较

由以上可知，两种方法均可获得满意的结果，测试所得到的角度误差在可接受的范围内。基于Radon 变换的方法在检测图 3（a）～图 3（e）所示的截图时，所耗费的时间为基于灰度互相关方法所耗费时间的50倍左右。人民币碎片图与图3中的各图相类似，显然，采用基于灰度互相关方法来获取人民币碎片相对于基准图的转角是更可取的方法。

3.2 实验

图4 实验图

如图4所示，利用工业显微镜的旋转工作台进行实测。旋转工作台最小分度为5′，摄像头为台电科技T838网络摄像头。

实验时，首先将旋转工作台置于0°位置，拍摄此时的人民币图像作为基准图。然后将旋转工作台分别转至四个象限，共在八个位置拍摄到的图像与基准图相比较，用基于灰度互相关算法计算它们间的转角，同时又可直接读出旋转工作台的转角，比较如表2所示。由表2可知，在每个象限中，旋转工作台的实际转角与经图像处理方法得到的图像的转角相比较，其误差在±1°内，这已经能满足使用要求。证明上述方法是可行的。

表2 计算所得角度与实际旋转角度的比较

4 旋转角度的最优搜索

4.1 优化搜索的思路

由以上讨论知，人民币碎片相对于基准图的旋转角度宜采用基于灰度互相关的方法来进行。此方法的思想是要将基准图在0°～360°内逐度旋转，每旋转1°，则计算一次两待匹配图的最大互相关系数，这样要计算360次。如果能减少计算次数，则可大大提高速度。提出以下三种方法。

方法一：采用先粗搜索后精搜索的方法。即先每隔10°旋转基准图，找到这些角度中具有最大相关系数的值，而后在此角度作上下10°的范围内，以1°为步长逐度计算，找到具有最大相关系数时对应的角度。

方法二：采用Matlab优化工具箱求相关系数的极大值所对应的角度。

方法三：采用遗传算法。

4.2 各种优化搜索方法间的对比

图5 人民币基准图

图6 人民币碎片图

以图5和图6作为测试用图，均由T838网络摄像头所拍，图5大小为582×291，图6为人民币碎片图。测试结果如表3所示。

方法一：耗时64.412471s，两图相对转角为29°。

方法二：在0°～360°范围内搜索时，无法得出正确结果。原因分析如下：首先，在0°～360°范围内，计算每一度对应的最大相关系数，如图7所示，在整个范围内，有很多局部最大值。其次，在29°附近的尖峰区，从26°～33°每隔0.1°计算对应的最大相关系数,如图8所示。由图可见，要找到一个合适的单峰区间比较困难。而Matlab最优工具箱所用的各种搜索方法，重要的一点是搜索必须在单峰区间内进行[9]。因而使用最优工具箱进行最优搜索不是一个恰当的方法。

表3 三种优化方法求旋转角度的比较

方法三：遗传算法受很多参数的影响，例如群体规模、初始个体间的距离等。假定其余参数不变，而 Initial Range 设为[1；50]，得到结果耗时20.960162s，转角 27.7972°。Initial Range设为[1；25]，得到结果耗时29.699520s，转角23.9802°。因此，如果采用遗传算法，则须事先找到最佳的参数配置。

综上所述，要找到最佳的旋转角，可采用方法一或方法三，这两种方法各有千秋。方法一易于理解，能得到最接近最大相关系数的角度，当然它只能精确到1°。方法三用时是方法一的一半，如果仔细调整算法终止条件，用时可望进一步减少。但方法三须探索寻找最恰当的参数，当这些参数有很多个时，这是相当麻烦的。

5 最终的匹配效果

采用上述方法，得到碎片图相对于基准图的转角。将碎片图矫正到与基准图平行的位置后，可方便地用互相关法确定碎片图在基准图中的位置，效果如图9所示。至此，单张碎片图在基准图上的匹配定位即告完成。

图9 匹配效果图

6 结束语

采用文中所述方法可方便地得到碎片图像相对于基准图的旋转角度，进而依据该角度值对碎片图进行矫正，再进一步用通常的灰度互相关算法即可得到碎片图在基准图上的正确位置。但实现单张碎片图在基准图上的匹配定位只是第一步。要真正实现人民币碎片的自动拼接，还必须解决如何确定哪些碎片是来自同一张钞票，这需要进一步的研究。

[1]曹 炬，马 杰，谭毅华，等.基于像素抽样的快速互相关图像匹配算法[J].宇航学报，2004，25（2）：173－178.

[2]孙卜郊，周东华.基于NCC的存在旋转的图像匹配方法[J].传感器与微系统，2008，27（5）：43-45.

[3]丁险峰，吴 洪，张宏江，等.形状匹配综述[J].自动化学报，2001，27（5）：678－694.

[4]潘荣江.计算机辅助文物复原中的若干问题研究[D].济南：山东大学，2005.

[5]Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004，60（2）：91-110.

[6]冈萨雷斯.数字图像处理 [M].北京：电子工业出版社，2007.

[7]李中科，杨晓辉，吴乐南.针对旋转和平移运动的一种图像配准方法[J].应用科学学报，2005，23（3）：282-286.

[8]Onishi H，Suzuki H.Detection of rotation and paraller translation using hough and fourier transforms[C]∥IEEE Inter Conf.Image Processing，1996（3）：827-830.

[9]谢 政，李建平，汤泽滢.非线性最优化[M].长沙：国防科技大学出版社，2003.