宋瑩瑩， 王宏民， 于凌濤， 張東青

(1.黑龍江科技學(xué)院 電氣與信息工程學(xué)院，哈爾濱 150027;2.哈爾濱工程大學(xué) 機(jī)電工程學(xué)院，哈爾濱 150001)

一種基于形狀信息描述的圖像特征匹配算法

宋瑩瑩1， 王宏民1， 于凌濤2， 張東青1

(1.黑龍江科技學(xué)院 電氣與信息工程學(xué)院，哈爾濱 150027;2.哈爾濱工程大學(xué) 機(jī)電工程學(xué)院，哈爾濱 150001)

針對(duì)已有匹配方法匹配特征點(diǎn)少、圖像匹配精度低的問題，提出一種基于邊緣形狀描述子的圖像特征匹配算法。該算法首先利用曲線凸性將圖像邊緣分割為近似直線段組，再將連接多個(gè)直線段的點(diǎn)定義為關(guān)鍵點(diǎn)，將關(guān)鍵點(diǎn)周圍直線段組定義為形狀特征包，最后利用局部形狀特征包中所有點(diǎn)集相對(duì)其幾何中心的位置關(guān)系分布形成描述子。實(shí)驗(yàn)結(jié)果表明:該算法的圖像匹配正確率均高于SIFT算法和Shape Context算法，且對(duì)噪聲問題不敏感，可應(yīng)用于基于Hough變換的物體檢測(cè)。

形狀描述子;特征匹配;邊緣檢測(cè);檢測(cè)子

點(diǎn)匹配是指同一物體或場(chǎng)景在不同視圖上的點(diǎn)對(duì)應(yīng)關(guān)系，它對(duì)立體匹配、寬基線匹配、物體檢測(cè)等具有重要作用。點(diǎn)匹配的重要步驟之一是關(guān)鍵點(diǎn)提取與描述。關(guān)鍵點(diǎn)提取是為了尋找具有穩(wěn)定特征的點(diǎn)，而關(guān)鍵點(diǎn)描述則是為描述關(guān)鍵點(diǎn)的特性。關(guān)鍵點(diǎn)提取與描述的常用方法包括基于圖像灰度信息或紋理信息的檢測(cè)子［1－4］和描述子。其中，基于局部特征的描述子，如SIFT［5－6］、Harr小波等［7－11］在點(diǎn)匹配和物體識(shí)別中應(yīng)用廣泛，但上述方法檢測(cè)到的關(guān)鍵點(diǎn)少、誤匹配率高。

近年來，基于輪廓信息的描述子得到了廣泛發(fā)展。利用輪廓信息實(shí)現(xiàn)的匹配，主要包括點(diǎn)到點(diǎn)匹配和邊界輪廓段匹配［12］。實(shí)現(xiàn)點(diǎn)到點(diǎn)匹配的描述子主要包括形狀上下文(Shape Context)［13］、點(diǎn)對(duì)幾何關(guān)系(Pairwise Geometric Relationship)［14］及其改進(jìn)算法。這些方法由于受匹配點(diǎn)周圍點(diǎn)影響，易產(chǎn)生匹配錯(cuò)誤，而利用邊緣輪廓形狀包的信息可避免點(diǎn)噪聲的影響。因此，筆者提出一種基于圖像邊緣信息的局部描述子。

1 關(guān)鍵點(diǎn)檢測(cè)

定義C=(S，E，Cv，M，nC)，其中，C為邊緣輪廓組，通常C=L，故用C表示通用輪廓組;M為曲線類型(直線或曲線);nC為曲線點(diǎn)集邊緣點(diǎn)個(gè)數(shù)。

如果C為直線，則定義直線的兩個(gè)端點(diǎn)為關(guān)鍵點(diǎn)。若C為曲線，根據(jù)歐幾里德平面，定義凸性為

將式(1)離散化為邊緣點(diǎn)后可記為

式中:xi——圖像邊緣點(diǎn);

根據(jù)凸性定義，采用迭代方法可以將復(fù)雜的輪廓曲線分割為幾個(gè)單一曲線段。每一曲線輪廓C可以通過檢測(cè)曲線點(diǎn)共線性檢測(cè)其除兩端點(diǎn)外的其他關(guān)鍵點(diǎn)。曲線點(diǎn)利用直線方程擬合，直線方程為

由邊緣點(diǎn)計(jì)算的直線長(zhǎng)度為

曲線C上距離式(2)最遠(yuǎn)的點(diǎn)即是關(guān)鍵點(diǎn)，將此關(guān)鍵點(diǎn)定義為圖像性狀特征關(guān)鍵點(diǎn)，其坐標(biāo)可由

獲取。

圖1 關(guān)鍵點(diǎn)檢測(cè)流程Fig.1 Keypoint detection flowchart

以采集的圖像為例，進(jìn)行邊緣圖像關(guān)鍵點(diǎn)檢測(cè)，如圖2所示。通過對(duì)比可知，物體所處環(huán)境越復(fù)雜關(guān)鍵點(diǎn)個(gè)數(shù)越多。

圖2 關(guān)鍵點(diǎn)檢測(cè)結(jié)果Fig.2 Key point detection result

2 關(guān)鍵點(diǎn)描述與匹配

2.1 關(guān)鍵點(diǎn)描述

將圖像中每一關(guān)鍵點(diǎn)周圍的所有近似直線段歸為一組，則由該關(guān)鍵點(diǎn)及其周圍近似直線段所組成的邊緣特征包稱為局部形狀包。文中將所有局部形狀特征包歸結(jié)為圖3顯示的情況。若局部形狀包中包含3條或3條以上直線段，只考慮所有直線段中最長(zhǎng)的兩條，忽略掉其他的短線段。如果局部形狀包中只包含一條線段，則認(rèn)為是兩條直線段重合在一起。

圖3 局部形狀特征包及關(guān)鍵點(diǎn)、端點(diǎn)Fig.3 Key point，starting point and end point of local shape patch

為使局部形狀包具有較強(qiáng)的區(qū)分能力，規(guī)定了主方向。如圖4所示，A、B分別為起點(diǎn)和末端點(diǎn)，α為主方向。將主方向旋轉(zhuǎn)為0，所有局部形狀包上的邊緣點(diǎn)均將按照主方向進(jìn)行排序。

圖4 局部形狀特征包繞主方向旋轉(zhuǎn)圖Fig.4 Local shape patches rotated to key point

每一局部形狀特征包可以由(Ci，Pi，Si，Hi，θi1，θi2，αi)等參數(shù)表示，其中，Ci為局部形狀特征包上所有邊緣點(diǎn)，Pi為關(guān)鍵點(diǎn)，Si為起點(diǎn)，Hi為終點(diǎn)，θij為利用邊緣梯度方向統(tǒng)計(jì)直方圖獲取的直線段的主方向，αi為局部形狀特征包的主方向。

目前，點(diǎn)對(duì)間的匹配方法主要以點(diǎn)(梯度方向)的分布直方圖作為描述子實(shí)現(xiàn)。假定某一圖像中所有關(guān)鍵點(diǎn)集I={P1，P2，…，Pn}，n為關(guān)鍵點(diǎn)數(shù)量，所有邊緣輪廓點(diǎn)可以分組為E={E1，E2，…，En}，Ei為關(guān)鍵點(diǎn)Pi周圍的局部形狀特征包，按照點(diǎn)對(duì)間的分布情況，可以表示為

式(3)即為形狀上下文描述子，nr為點(diǎn)與點(diǎn)之間的距離分段的數(shù)量。

受形狀上下文描述子的啟發(fā)，采用一種簡(jiǎn)化的邊緣點(diǎn)相對(duì)局部形狀特征包中心點(diǎn)的分布統(tǒng)計(jì)直方圖描述局部形狀特征包。

設(shè)Oi為局部形狀包的中心點(diǎn)，則局部形狀特征包上的點(diǎn)相對(duì)于中心點(diǎn)的分布情況為

式中:Rj——邊緣點(diǎn)相對(duì)中心點(diǎn)的距離矢量，Rj=，|Rj|);

N——邊緣點(diǎn)相對(duì)中心點(diǎn)距離的最大值，N= max(|R1|，|R2|，…，|Rk|)。

為進(jìn)一步增強(qiáng)描述子的區(qū)分能力，考慮圖像的邊緣梯度方向信息。局部形狀特征包的描述子可表征為

2.2 關(guān)鍵點(diǎn)匹配

用TC(a，b)表征局部形狀特征包Ca、Cb間的相似度，則式中:Cori——用L2范數(shù)計(jì)算的梯度方向形似度，Cori(Oria，Orib)=‖Oria－Orib‖2;

c1——權(quán)重系數(shù)。

受邊緣提取時(shí)的噪聲等因素影響，提取的邊緣輪廓的長(zhǎng)度等信息可能不一致，且方向信息變化較小，因此梯度方向所占權(quán)重較大，文中測(cè)得c1=4。

利用上述方法測(cè)量一組形狀特征(圖5)的相似度，結(jié)果如表1所示。

圖5 一組形狀特征包Fig.5 Group of shape patch

表1 特征包相似度Table 1 Similarity of shape patch

由表可知，形狀特征包之間的相似度受邊緣輪廓長(zhǎng)度信息影響不大，主要受方向信息變化的影響。

3 結(jié)果分析

3.1 圖像匹配實(shí)驗(yàn)

分別采用文中算法和SIFT算法對(duì)普通雙目視覺系統(tǒng)采集的圖像進(jìn)行匹配實(shí)驗(yàn)，結(jié)果如圖6所示。

圖6 圖像匹配結(jié)果比較Fig.6 Comparison of image matching result

由圖中可以看出，利用SIFT算子分別檢測(cè)出45和53個(gè)特征點(diǎn)，正確匹配數(shù)為18，誤匹配數(shù)為1。該方法檢測(cè)出的相似區(qū)域不能很好的匹配，如鉗子的手柄部分，雖然檢測(cè)出了關(guān)鍵點(diǎn)，但是未正確匹配出任何關(guān)鍵點(diǎn)。利用文中算法分別檢測(cè)出11和17個(gè)特征點(diǎn)，正確匹配數(shù)為7。該方法對(duì)物體全局均檢測(cè)出了關(guān)鍵點(diǎn)，并且檢測(cè)出的關(guān)鍵點(diǎn)不受外觀影響，誤匹配數(shù)為0?？梢姡闹兴惴ǖ钠ヅ湫Ч^好，有利于少特征物體的匹配與跟蹤。

3.2 形狀匹配實(shí)驗(yàn)

利用文中算法檢測(cè)出的關(guān)鍵點(diǎn)如圖7所示，該算法分別檢測(cè)出了21個(gè)(圖7a)和43個(gè)關(guān)鍵點(diǎn)(圖7b)。

圖7 關(guān)鍵點(diǎn)檢測(cè)Fig.7 Keypoints detection shape image

文中算法與Shape Context算法的匹配結(jié)果如圖8所示，其中，圖8a為加入一些噪聲點(diǎn)后的匹配結(jié)果。從結(jié)果可以看出，文中算法具有較強(qiáng)的抗噪聲性能，成功匹配關(guān)鍵點(diǎn)的個(gè)數(shù)為16;而Shape Context算法成功匹配關(guān)鍵點(diǎn)的個(gè)數(shù)為15，可見，文中算法的形狀匹配效果良好。

圖8 匹配結(jié)果比較Fig.8 Comparison of matching results

4 結(jié)束語

針對(duì)傳統(tǒng)模板匹配方法匹配少特征圖像存在誤匹配率高、匹配精度低等問題，提出基于形狀特性的局部形狀包描述方法。實(shí)驗(yàn)結(jié)果表明文中算法的圖像特征匹配正確率均高于SIFT算法和Shape Context算法，可以應(yīng)用于基于概率Hough變換框架下的物體檢測(cè)，若其結(jié)合全局形狀信息，則可以進(jìn)一步提高匹配正確率。該算法對(duì)邊緣檢測(cè)算法的依賴性較強(qiáng)，當(dāng)兩幅圖像的光照情況不同時(shí)，邊緣檢測(cè)結(jié)果不同，匹配效果也不穩(wěn)定。因此，該算法仍需進(jìn)一步改進(jìn)，使其對(duì)光照具有不變性。

［1］HARRIS C，STEPHENS M.A combined corner and edge detector［C］//Alvey Vision Conference，Manchester:University of Manchester，1988.

［2］ROTH P，WINTER M.Survey of appearance-based methods for object recognition［R］//Inst.for Computer Graphics and Vision，Graz:Graz University of Technology，2008.

［3］MIKOLAJCZYK K，TUYTELAARS T，SCHMID C，et al.A comparison of affine region detectors［J］.International Journal of Computer Vision，2005，65(1):43－72.

［4］KADIR T，BRADY M.Scale saliency:a novel approach to salient feature and scale selection［C］//International Conference on Visual Information Engineering，Citeseer:IEE Conference Publication，2003.

［5］KE Y，SUKTHANKAR R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//Conference on Computer Vision and Pattern Recognition，Washington:IEEE Computer Society，2004.

［6］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615－1630.

［7］BAY H，TUYTELAARS T，VAN GOOL L.Surf:Speeded up robust features［C］//9thEuropean Conference on Computer Vision， Graz:ECCV，2006.

［8］MOHAN A，PAPAGEORGIOU C，POGGIO T.Example-based object detection in images by components［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(4): 349－361.

［9］MIKOLAJCZYK K，SCHMID C，ZISSERMAN A.Human detection based on a probabilistic assembly of robust part detectors［C］//European Conference on Computer Vision，Berlin:Springer Berlin Heidelberg，2004.

［10］MARIMON D，EBRAHIMI T.Orientation histogram-based matching for region tracking［C］//Eighth International Workshop on Image Analysis for Multimedia Interactive Services，Santorini: WIAMIS，2007.

［11］LEIBE B，LEONARDIS A，SCHIELE B.Combined object categorization and segmentation with an implicit shape model［C］// Workshop on Statistical Learning in Computer Vision，Prague: ECCV，2004.

［12］DALAL N，TRIGGS B.Histograms of oriented gradients for human detection［C］//Conference on Computer Vision and Pattern Recognition，Paris:IEEE Computer Society，2005.

［13］XU C，LIU J，TANG X.2d shape matching by contour flexibility［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31(1):180－186.

［14］BELONGIE S，MALIK J，PUZICHA J.Shape matching and object recognition using shape contexts［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(24): 509－522.

［15］周文理，金施群.基于SIFT算法的可見光圖像與紅外圖像配準(zhǔn)［J］.黑龍江科技學(xué)院學(xué)報(bào)，2011(2):121－123.

Local shape patch based feature matching method

SONG Yingying1， WANG Hongmin1， YU Lingtao2， ZHANG Dongqing1
(1.College of Electic＆Information Engineering，Heilongjiang Institute of Science＆Technology，Harbin 150027，China; 2.College of Mechanical＆Electrical，Harbin Engineering University，Harbin 150001，China)

Aimed at improving lower image matching accuracy due to fewer matching feature points in matching method in use，this paper proposes a novel image feature matching algorithm based on edge of the shape descriptor.The algorithm starts with dividing the edge map into a group of roughly straight lines，based on the property of the curve convexity of the edge points，proceeds to define the connection point of more than one straight line as the key point and form a local shape patch by using all the straight lines around the key point，and ends by forming a novel descriptor by using the distribution of the edge points of the local shape patch related to the center of the shape patch.Experiments of image matching and shape matching carried out by using the algorithm introduced in this paper presents indicate that the proposed method features a greater correct matching probability than SIFT algorithm and Shape Context algorithm and offers lower sensitivity to the noise，promising the application in object detection under the Hough transform.

shape descriptor;feature match;edge detection;detector

TP391.4

A

1671－0118(2011)04－0325－04

2011－06－13

中國(guó)博士后科學(xué)基金特別資助項(xiàng)目(200902372);黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目(11553094)

宋瑩瑩(1980－)，女，黑龍江省雞西人，工程師，碩士，研究方向:圖像處理與自動(dòng)控制，E-mail:wang－h(huán)ongmin@163.com。

(編輯荀海鑫)