莊俊東

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

1 引 言

日常生活中經常會碰到大額人民幣因為保管不善而變成一堆爛鈔，這種情況在偏遠農村普遍存在。由于農村基層金融機構缺乏，農民通常將現(xiàn)鈔保存在手上，經常遭到蟲咬鼠啃、火燒水浸，辛苦得來的錢財成了一堆碎片。若這些碎片拿到銀行去兌換，依據(jù)相關規(guī)定，殘幣須拼出大于原圖的50%方允許兌換。用人工方法進行拼接，費時費力。因此，有必要開發(fā)一種機器方法對碎片進行自動拼接。

要實現(xiàn)這種自動拼接，首先要找到人民幣碎片在基準圖上的位置，也就是要找到一種恰當?shù)膱D像匹配方法。一般而言，圖像匹配的算法可分為兩類：（1）是基于圖像灰度的匹配算法；（2）是基于圖像特征的匹配算法。由于基于灰度的匹配算法計算量大，Barnea于1972年提出序貫相似性算法——SSDA法，而Wong于1978年提出分層序貫匹配算法以加快速度[1]。傳統(tǒng)的基于灰度的匹配方法雖然在匹配精度，對噪聲具有魯棒性等方面具有優(yōu)勢，但對待匹配圖像間的角度旋轉敏感。當待配圖像間存在相對的旋轉角時，就會發(fā)生錯誤匹配。為克服這一缺陷，有人提出了改進算法[2]。由于人民幣碎片圖像不可能與基準圖保持平行關系，因此要想將基于灰度的匹配算法用于碎片圖像匹配，就必須使用改進算法?；谔卣鞯钠ヅ渌惴╗3-5]，則是基于圖像的邊緣、特征點、紋理等特征，將圖像的匹配轉化為少量特征的匹配，從而可提高匹配速度。

人民幣碎片圖像的匹配定位分兩步進行。第一步，找到碎片圖像相對于基準圖的旋轉角；第二步，對碎片圖像進行角度矯正，再使用傳統(tǒng)的灰度互相關法找到碎片圖像在基準圖中的確切位置。

2 碎片圖像相對于基準圖旋轉角度的確定

利用灰度互相關方法考察圖像間的相似性，一種常用的方法是計算這兩幅圖像對應點之間灰度值的差異，如公式（1）所示：

其中：f（x，y）——基準圖上（x，y）點處的灰度值；

t（x-u，y-ν）——模板上相當于人民幣碎片圖上與f（x，y）在對應點處的灰度值；

u，ν——模板在基準圖上沿x軸，y軸的移動值。

假設模板（即碎片）相對于基準圖（即整張人民幣圖）無角度旋轉，將模板沿x方向，y方向進行遍歷搜索到（u，ν）處，在基準圖上與碎片圖相對應的區(qū)域，若式（1）右邊的值為零，此時相似性最大，兩幅圖像完全一致。

將式（1）右邊展開，得：

定義相關系數(shù)：

c值越大，d2f，t（u，ν）值越小，兩圖間的相似性越好。但c（u，ν）不能直接用于判斷兩幅圖像間的相似性。原因在于：（1）假設基準圖中某位置的f（x，y）恒等于灰度最大值，則c（u，ν）的值達到最大值，但此時d2f，t（u，ν）的值不會是所有位置中的最小值；（2）c（u，ν）的大小受匹配圖像大小的影響；（3）c（u，ν）的值受基準圖亮度的影響。為克服以上不足，則提出了歸一化的互相關系數(shù)[6]：

用以判斷兩幅圖像間相似性的大小。

為得到碎片圖像相對于基準圖的旋轉角度，可將基準圖在0°～360°逐度旋轉。在每一角度上，求出兩圖的最大互相關系數(shù)γ（u，ν），這些相關系數(shù)在正確的角度上將達到最大值，由此可得兩圖間的相對轉角[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所示，利用工業(yè)顯微鏡的旋轉工作臺進行實測。旋轉工作臺最小分度為5′，攝像頭為臺電科技T838網絡攝像頭。

實驗時，首先將旋轉工作臺置于0°位置，拍攝此時的人民幣圖像作為基準圖。然后將旋轉工作臺分別轉至四個象限，共在八個位置拍攝到的圖像與基準圖相比較，用基于灰度互相關算法計算它們間的轉角，同時又可直接讀出旋轉工作臺的轉角，比較如表2所示。由表2可知，在每個象限中，旋轉工作臺的實際轉角與經圖像處理方法得到的圖像的轉角相比較，其誤差在±1°內，這已經能滿足使用要求。證明上述方法是可行的。

表2 計算所得角度與實際旋轉角度的比較

4 旋轉角度的最優(yōu)搜索

4.1 優(yōu)化搜索的思路

由以上討論知，人民幣碎片相對于基準圖的旋轉角度宜采用基于灰度互相關的方法來進行。此方法的思想是要將基準圖在0°～360°內逐度旋轉，每旋轉1°，則計算一次兩待匹配圖的最大互相關系數(shù)，這樣要計算360次。如果能減少計算次數(shù)，則可大大提高速度。提出以下三種方法。

方法一：采用先粗搜索后精搜索的方法。即先每隔10°旋轉基準圖，找到這些角度中具有最大相關系數(shù)的值，而后在此角度作上下10°的范圍內，以1°為步長逐度計算，找到具有最大相關系數(shù)時對應的角度。

方法二：采用Matlab優(yōu)化工具箱求相關系數(shù)的極大值所對應的角度。

方法三：采用遺傳算法。

4.2 各種優(yōu)化搜索方法間的對比

圖5 人民幣基準圖

圖6 人民幣碎片圖

以圖5和圖6作為測試用圖，均由T838網絡攝像頭所拍，圖5大小為582×291，圖6為人民幣碎片圖。測試結果如表3所示。

方法一：耗時64.412471s，兩圖相對轉角為29°。

方法二：在0°～360°范圍內搜索時，無法得出正確結果。原因分析如下：首先，在0°～360°范圍內，計算每一度對應的最大相關系數(shù)，如圖7所示，在整個范圍內，有很多局部最大值。其次，在29°附近的尖峰區(qū)，從26°～33°每隔0.1°計算對應的最大相關系數(shù),如圖8所示。由圖可見，要找到一個合適的單峰區(qū)間比較困難。而Matlab最優(yōu)工具箱所用的各種搜索方法，重要的一點是搜索必須在單峰區(qū)間內進行[9]。因而使用最優(yōu)工具箱進行最優(yōu)搜索不是一個恰當?shù)姆椒ā?/p>

表3 三種優(yōu)化方法求旋轉角度的比較

方法三：遺傳算法受很多參數(shù)的影響，例如群體規(guī)模、初始個體間的距離等。假定其余參數(shù)不變，而 Initial Range 設為[1；50]，得到結果耗時20.960162s，轉角 27.7972°。Initial Range設為[1；25]，得到結果耗時29.699520s，轉角23.9802°。因此，如果采用遺傳算法，則須事先找到最佳的參數(shù)配置。

綜上所述，要找到最佳的旋轉角，可采用方法一或方法三，這兩種方法各有千秋。方法一易于理解，能得到最接近最大相關系數(shù)的角度，當然它只能精確到1°。方法三用時是方法一的一半，如果仔細調整算法終止條件，用時可望進一步減少。但方法三須探索尋找最恰當?shù)膮?shù)，當這些參數(shù)有很多個時，這是相當麻煩的。

5 最終的匹配效果

采用上述方法，得到碎片圖相對于基準圖的轉角。將碎片圖矯正到與基準圖平行的位置后，可方便地用互相關法確定碎片圖在基準圖中的位置，效果如圖9所示。至此，單張碎片圖在基準圖上的匹配定位即告完成。

圖9 匹配效果圖

6 結束語

采用文中所述方法可方便地得到碎片圖像相對于基準圖的旋轉角度，進而依據(jù)該角度值對碎片圖進行矯正，再進一步用通常的灰度互相關算法即可得到碎片圖在基準圖上的正確位置。但實現(xiàn)單張碎片圖在基準圖上的匹配定位只是第一步。要真正實現(xiàn)人民幣碎片的自動拼接，還必須解決如何確定哪些碎片是來自同一張鈔票，這需要進一步的研究。

[1]曹 炬，馬 杰，譚毅華，等.基于像素抽樣的快速互相關圖像匹配算法[J].宇航學報，2004，25（2）：173－178.

[2]孫卜郊，周東華.基于NCC的存在旋轉的圖像匹配方法[J].傳感器與微系統(tǒng)，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]岡薩雷斯.數(shù)字圖像處理 [M].北京：電子工業(yè)出版社，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]謝 政，李建平，湯澤瀅.非線性最優(yōu)化[M].長沙：國防科技大學出版社，2003.