基于改進的加權Ｈａｕｓｄｏｒｆｆ距離的圖像匹配

摘要：提出了一種改進的加權Hausdorff距離，并將其應用于字符圖像的匹配。該方法根據字符圖像的結構特征對字符不同區域設置不同的權重。實踐表明該方法改善了圖像匹配效果。

關鍵詞：相似性度量；Hausdorff距離；圖像匹配

中圖分類號：TP391.41文獻標志碼：A

文章編號：1001-3695(2007)04-0182-02

模式識別技術已經在天氣預報、航空圖片解釋、工業檢測、字符識別、指紋識別、醫學圖像分析等許多方面有了廣泛的應用。OCR^[1]即是其中的一個典型例子。圖像匹配是模式識別研究中的一個重要領域，經過多年的努力，已經取得了一定的研究成果。由于模板圖像與實際圖像的拍攝時間和條件不同，以及成像設備的限制，使得兩幅圖像之間不僅存在嚴重的灰度差異，而且還存在一定的灰度失真和幾何形變。因此，如何使算法具有良好的抗噪聲能力和抗幾何形變的能力成為一個重要的研究課題。其中Hausdorff距離是獲得較多研究的一種相似性度量尺度，尤其是在圖像比較^[2]、定位^[3，4]、匹配和識別^[5~9]等領域有廣泛的應用。

1改進的加權Hausdorff距離 

1.1傳統Hausdorff距離（HD）的定義^[2]

給定兩個點集A＝{a1，…，ap} 和B＝{b1，…，bq}，Hausdorff距離的定義如下

其中：h(A，B)=maxa∈A minb∈B‖a-b‖(2)

‖a-b‖是點a與點b之間的歐氏距離；函數h(A，B)為點集A到點集B的有向Hausdorff距離。

如果定義點x∈A到點集B的距離為d(x)=minb∈B‖x-b‖，點x∈B到點集A的距離為d

可以看出，有向Hausdorff距離h(A，B)確定了一點a∈A，a到點集B的距離最大，h(A，B)即為點a與其在B中的最近鄰點之間的距離。直觀地看，如果h(A，B)＝d，那么對于A中的每一點，在B中必定存在某些點，使它們之間的距離小于等于d。Hausdorff距離H(A，B)是h(A，B)和h(B，A)的最大值。因此，它反映了點集A與B的不相似度。如果H(A，B)＝d，則對于A中的每一點，在B中必定存在某些點，使它們之間的距離小于等于d，反之亦然。與其他形狀比較算法的不同之處在于，Hausdorff距離并沒有明確的點集A和B之間的點點對應關系，而它所反映的是點集之間的對應關系。

1.2基于平均距離值的Hausdorff 距離

Dubuisson和Jain^[7]在匹配被四種噪聲污染的綜合圖像時，提出了基于平均距離值的Hausdorff距離(Modified Hausdorff Distance，MHD)。這種匹配方法在有零均值高斯噪聲的圖像中可以估計出最佳的匹配位置，而且不需要參數。有向MHD定義為

hMHD(A，B)=1/Na∑a∈Ah(a，B)（6）

這種方法考慮到噪聲污染的情況，沒有考慮到實際應用中圖像具有特定特征等因素。

1.3基于加權的Hausdorff距離

Lu和Tan^[8，9]根據字符的特征將圖像目標分成不同的區域，然后再根據特征區域在字符輪廓中的地位來設置不同的權值提出一種加權的Hausdorff距離(Weighted Hausdorff Distance，WHD)。其有向WHD定義為

其中，∑a∈Aw(a)=Na。

這種方法在圖像匹配過程中比MHD方法好，在中英文檔圖像匹配應用中都能很好地實現^[8]，是一種比較理想的方法。但這種方法是對所有的單詞或漢字進行統一的分類加權，停留在單詞這個水平上，沒有考慮到單詞中字母的具體特征。

1.4改進的加權Hausdorff距離

本文以英文字母的圖像匹配作為研究對象，提出一種改進的加權Hausdorff距離（Improved Weighted Hausdorff Distance，IWHD）。在圖像中，英文26個字母都有自己的分布特征，以此對不同字母的不同區域設置不同的權值，即根據體現字母信息的主次將一個字母圖像分成若干不同的區域。例如，可以看到字母C的右面是有很大開口，該區域在識別時至關重要，對此設置較重的權值。

首先根據26個字母的特征輪廓相似性，將它們分成五個大類；每個大類采用相同的區域劃分。這五個大類是：

在第Ⅰ類字符中，可以看出，它們都有共有的特征就是有一個方向開口。在設置權值時將考慮到這個特殊的部位，如圖1所示字符圖像區域被分成四個小的區域，并將設置不同的權重。對圖2所示的字符圖像“e”和“c”，其不同區域的權重設置為

同樣，對于如圖3所示的字符圖像“m”和“n”，權重設置為

對于如圖4所示的字符圖像“u”“v”和“w”，權重設置為

對Ⅱ類中的字母，根據這類字母上、下特有的分布特征把整個區域分成上、下兩個小區域(U區和B區)，如圖5所示。對圖6所示的字符圖像“h”“b”和“d”的權值設置為

對于字符圖像“a”，設置w(U)=2 w(B)；而對于字符圖像“r”，設置w(B)=2 w(U)，如圖7所示。

對于Ⅲ類中的字母，區域劃分與Ⅱ類同樣，如圖8所示，但權值的設置為

Ⅳ類字符圖像的區域劃分如圖9所示。對于如圖10所示的字符“p”“q”“g”“y”的權值設置為

第Ⅴ類中字母的區域劃分如圖11所示。對于圖11中字符圖像的權值設置為

2實驗結果及結論

將本文介紹的改進加權Hausdorff距離應用于實際的文本圖像匹配中。圖12是從文本圖像中分割出的真實詞圖像，以此圖像來測試本文方法。經過適當的預處理，去除圖像中的噪聲，得到如圖13所示的圖像。然后分割出其中的每個字符圖像并對其進行大小歸一化等處理，得到圖14。

計算每個字符圖像與標準模板之間的Hausdorff距離，并與原來的加權Hausdorff距離進行比較。

為客觀比較，定義評價函數為

其中：Sα=H(x，α)(9)

在式（8）中，Sα是待測樣本圖像與模板圖像α的Hausdorff距離，Smin是其最小值。評價函數F越大，對樣本的區分能力越強，性能也就越好。用FWHD和FIWHD分別表示WHD和本文方法得到的評價函數值。表1給出了兩種方法對圖14中幾個字符的效果比較。

表1算法效果的比較

從表1可以看出，兩種算法對字符圖像t的效果是一樣的。這是因為本文方法采用了與WHD方法一樣的權值設置。而對其他字母，本文算法所得出的評價函數數值要比WHD所得出的數值大。也就是說明本文的算法比WHD算法更優。

此外，本文對5 200個字樣組成的字符圖像數據庫進行測試。實驗結果表明本文方法得到的平均正確識別率為95.79%，而WHD方法的識別率為93.15%，即與WHD方法相比，本文方法的正確識別率提高了2.64%。這也進一步說明了采用本文提出的對不同區域設置不同權重的改進加權Hausdorff距離是一種能更好地表示字符圖像相似性的度量尺度。

但是本文方法中的區域劃分和權重設置完全是根據人的經驗確定的，并且是針對英文字符這樣的特定對象設置的。為了適應各種不同的目標對象，今后的研究將集中在如何自動確定最佳的劃分區域，以及如何獲取最佳的權重，使得匹配效果更好。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。