一種改進(jìn)的輪廓曲線匹配算法

任家祥 張志剛 西安財經(jīng)大學(xué) 信息學(xué)院

1 概述

圖像形狀匹配是計(jì)算機(jī)視覺的重要研究領(lǐng)域，目前輪廓曲線的匹配分為兩種，一是基于區(qū)域，二是基于特征點(diǎn)。文獻(xiàn)中將提取到的曲線進(jìn)行最大公共子序列進(jìn)行匹配，缺點(diǎn)是對于機(jī)器的性能要求較高，且匹配速度較慢?；诮屈c(diǎn)，采取粗、精兩種匹配方法，粗匹配基于歸一化角點(diǎn)距離矩陣，精匹配基于同心圓。因?yàn)樾枰M(jìn)行同心圓計(jì)算，其匹配速率仍不高。將多邊形逼近算法與提取曲率相結(jié)合，提出一種速度較快的匹配方法，但是在進(jìn)行多邊形匹配的時候，頂點(diǎn)的數(shù)目并不能確定，從而限制了匹配結(jié)果。

本文提出了一種輪廓曲線匹配算法：使用Canny 邊緣檢測算法提取出邊緣，使用Shi-Tomashi 算法對目標(biāo)邊緣曲線角點(diǎn)進(jìn)行提取。根據(jù)角點(diǎn)的位置點(diǎn)信息來建立出角點(diǎn)距離矩陣，并對其進(jìn)行標(biāo)準(zhǔn)化處理。對處理過的角點(diǎn)距離矩陣視情況使用快匹配或慢匹配，分別適用于兩種不同的圖像匹配情況。

2 預(yù)處理

首先采用Canny 邊緣檢測算法得到細(xì)且明亮的輪廓曲線，再提取特征點(diǎn)，我們以角點(diǎn)作為圖像中重要的局部特征。本文采用的Shi-Tomasi 角點(diǎn)檢測算法基于灰度值，是對Harris 角點(diǎn)算法的改進(jìn)。Shi-Tomasi 檢測算法流程如下：

(1）使用差分算子計(jì)算出x，y 方向的偏導(dǎo)數(shù)，計(jì)算出Ix^2，IxIy，Iy^2 四個元素值組成的2x2 的矩陣

(2）使用高斯濾波器處理（1）中的2x2 矩陣，得到結(jié)構(gòu)張量矩陣M。

(3）由M 求得行列式的特征值r1 和r2，根據(jù)r1，r2 中的最小值來判定該像素點(diǎn)為強(qiáng)角點(diǎn)

(4）設(shè)定閾值Tc 和Td，對提取的特征點(diǎn)的數(shù)目和相鄰特征點(diǎn)的距離進(jìn)行約束，這樣便于匹配點(diǎn)對數(shù)目的衡量和防止描述區(qū)域的重疊。

3 RPCP 輪廓曲線匹配算法

3.1 歸一化角點(diǎn)距離矩陣

在平移和旋轉(zhuǎn)之后，角點(diǎn)的位置會發(fā)生變化，為描述角點(diǎn)之間的相對位置，計(jì)算N個角點(diǎn)的歐式距離，從而建立一個N*N的二維矩陣，其計(jì)算公式為：

其中的max 和min 表示二維矩陣中所有元素的最大值和最小值。

3.2 快匹配

由上式得到兩個N*N 二維數(shù)組，如果將每個元素都與其余元素進(jìn)行比較，那么總共需進(jìn)行N^4 次比較操作。設(shè)兩個不同圖像的歸一化角點(diǎn)距離矩陣A 和B：

在快匹配算法中，將距離最大值點(diǎn)作為基準(zhǔn)點(diǎn)，若該點(diǎn)到其它點(diǎn)的距離都能與另一點(diǎn)相匹配，則可以確定所有點(diǎn)之間的位置關(guān)系成功匹配。

算法流程如下：

(1）對矩陣的每一行按從小到大的順序進(jìn)行快速排序。

(2）查找A、B 矩陣各自的最大值，記錄其所在的行，記錄結(jié)果為a1，a2，b1，b2。

(3）將a1，b1 進(jìn)行匹配，若匹配結(jié)果不理想，則將a1，b2 進(jìn)行匹配，記錄兩次匹配中的最優(yōu)匹配結(jié)果。

(4）若匹配結(jié)果不理想，則將a1，a2 或b1，b2 換為次于當(dāng)前距離的角點(diǎn)距離所在行。如果當(dāng)前角點(diǎn)距離是前25%大，則進(jìn)行（3），否則結(jié)束，將最優(yōu)匹配結(jié)果輸出。

如果算法進(jìn)行第（4）步多次，則快速匹配算法失效，說明這兩個矩陣之間極大值差距較大，則應(yīng)采用慢匹配算法。

快匹配算法的時間復(fù)雜度在平均情況下是O(n).

3.3 慢匹配

慢匹配算法同樣基于歸一化角點(diǎn)距離矩陣，但慢匹配的目標(biāo)不在于快速對兩個歸一化角點(diǎn)距離矩陣進(jìn)行匹配，而在于最大限度得找出兩個矩陣之間的匹配程度。

在快匹配算法之中，優(yōu)先匹配極大值角點(diǎn)距離，而慢匹配對所有角點(diǎn)距離一視同仁，原則上需要將每個點(diǎn)同其它所有點(diǎn)進(jìn)行匹配。為減少匹配的次數(shù)，先進(jìn)行排序，這樣匹配單位便由個上升為了行。其次，若該點(diǎn)與某一點(diǎn)的匹配程度理想，則應(yīng)取消該點(diǎn)繼續(xù)匹配下去，這樣也能顯著降低匹配次數(shù)。算法流程如下：

設(shè)有兩條需要匹配曲線的歸一化角點(diǎn)距離矩陣A、B，A、B 為N*N 二維矩陣。

(1）將A，B 的每一行按從小到達(dá)的順序進(jìn)行快速排序。

(2）將A 中的第n 行依次與B 中的每一行進(jìn)行匹配，將匹配結(jié)果記錄下來，若匹配結(jié)果理想，則終止該行的匹配。

(3）n 值加一，重復(fù)（2）中的操作，記錄下每一行的最優(yōu)匹配結(jié)果，直到所有行都匹配完畢。

(4）將每一行的最優(yōu)匹配結(jié)果相加，得出最終匹配結(jié)果。

慢匹配算法的事件復(fù)雜度在平均情況下是O(n^3)

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)以某汽車品牌的標(biāo)志為對象，共提取出了目標(biāo)曲線20 個最優(yōu)角點(diǎn)，建立歸一化角點(diǎn)距離矩陣之后，進(jìn)行匹配。最終匹配程度達(dá)到95%。說明快匹配算法對于同一曲線的匹配有效。之后將一張紙不規(guī)則撕扯成兩半，并進(jìn)行旋轉(zhuǎn)，同樣對圖像進(jìn)行預(yù)處理并提取輪廓曲線。提取出20 個最優(yōu)角點(diǎn)，將角點(diǎn)標(biāo)記出來，如下圖：

圖 4-1 原圖和角點(diǎn)提取圖

建立歸一化角點(diǎn)距離矩陣之后，使用快匹配算法，匹配程度為10%。說明快匹配算法對于不同曲線的匹配并不合適。則使用慢匹配算法，慢匹配算法的匹配程度達(dá)到75%，符合預(yù)期。說明慢匹配算法相較于快匹配更具有普適性。在對于差異較大的兩個矩陣進(jìn)行匹配時采用慢匹配算法更為合適。

5 結(jié)論

本文提出了一種基于歸一化角點(diǎn)距離矩陣的輪廓曲線匹配算法，根據(jù)應(yīng)用場景的不同，提出了快匹配算法和慢匹配算法。經(jīng)過測試，快匹配算法對差異反應(yīng)強(qiáng)烈，更適合于對曲線相似度要求高的領(lǐng)域。慢匹配算法能耐心地尋找出兩條輪廓曲線之間的最大相似程度，但時間復(fù)雜度較高。該算法的精度在一定程度上依賴于邊緣檢測算法和角點(diǎn)檢測算法。