基于圖像處理的人民幣碎片匹配定位

莊俊東

（上海交通大學(xué)，上海 200240）

1 引 言

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

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

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

2 碎片圖像相對于基準(zhǔn)圖旋轉(zhuǎn)角度的確定

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

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

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

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

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

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

定義相關(guān)系數(shù)：

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

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

為得到碎片圖像相對于基準(zhǔn)圖的旋轉(zhuǎn)角度，可將基準(zhǔn)圖在0°～360°逐度旋轉(zhuǎn)。在每一角度上，求出兩圖的最大互相關(guān)系數(shù)γ（u，ν），這些相關(guān)系數(shù)在正確的角度上將達(dá)到最大值，由此可得兩圖間的相對轉(zhuǎn)角[2]。而基于Radon變換，首先對圖像進(jìn)行邊緣檢測，得到一二值圖，對該二值圖作Radon變換。設(shè)兩圖間有θ角的夾角，則基準(zhǔn)圖在θ角時的Radon變換與模板圖在0°時的Radon變換相同。更詳細(xì)的原理可參見文獻(xiàn)[7-8]。

3 仿真及實驗

3.1 仿真

圖1 基準(zhǔn)圖

圖2 旋轉(zhuǎn)后的圖

圖3 截取圖

圖1是Matlab圖像處理工具箱中的Cameraman.tif圖片，在這里作為基準(zhǔn)圖，是256×256大小的灰度圖。圖2為圖1逆時針旋轉(zhuǎn)31°后所得，大小與圖1相同。圖3（a）、圖3（b）均為從圖2中截取的一部分。圖3（c）為將基準(zhǔn)圖逆時針旋轉(zhuǎn)140°后從中截取的一部分。圖3（d）為將基準(zhǔn)圖逆時針旋轉(zhuǎn)224°后從中截取的一部分。圖3（e）為將基準(zhǔn)圖逆時針旋轉(zhuǎn)316°后從中截取的一部分。分別用前述方法利用Matlab圖像處理工具箱對各圖進(jìn)行測試，結(jié)果如表1所示。

表1 兩種方法求旋轉(zhuǎn)角度的比較

由以上可知，兩種方法均可獲得滿意的結(jié)果，測試所得到的角度誤差在可接受的范圍內(nèi)?；赗adon 變換的方法在檢測圖 3（a）～圖 3（e）所示的截圖時，所耗費的時間為基于灰度互相關(guān)方法所耗費時間的50倍左右。人民幣碎片圖與圖3中的各圖相類似，顯然，采用基于灰度互相關(guān)方法來獲取人民幣碎片相對于基準(zhǔn)圖的轉(zhuǎn)角是更可取的方法。

3.2 實驗

圖4 實驗圖

如圖4所示，利用工業(yè)顯微鏡的旋轉(zhuǎn)工作臺進(jìn)行實測。旋轉(zhuǎn)工作臺最小分度為5′，攝像頭為臺電科技T838網(wǎng)絡(luò)攝像頭。

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

表2 計算所得角度與實際旋轉(zhuǎn)角度的比較

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

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

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

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

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

方法三：采用遺傳算法。

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

圖5 人民幣基準(zhǔn)圖

圖6 人民幣碎片圖

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

方法一：耗時64.412471s，兩圖相對轉(zhuǎn)角為29°。

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

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

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

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

5 最終的匹配效果

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

圖9 匹配效果圖

6 結(jié)束語

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

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

[2]孫卜郊，周東華.基于NCC的存在旋轉(zhuǎn)的圖像匹配方法[J].傳感器與微系統(tǒng)，2008，27（5）：43-45.

[3]丁險峰，吳 洪，張宏江，等.形狀匹配綜述[J].自動化學(xué)報，2001，27（5）：678－694.

[4]潘榮江.計算機(jī)輔助文物復(fù)原中的若干問題研究[D].濟(jì)南：山東大學(xué)，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]李中科，楊曉輝，吳樂南.針對旋轉(zhuǎn)和平移運動的一種圖像配準(zhǔn)方法[J].應(yīng)用科學(xué)學(xué)報，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].長沙：國防科技大學(xué)出版社，2003.