賈耕云，趙海英，周 倩，李學(xué)明

?

對稱不變形狀上下文特征提取與匹配

賈耕云，趙海英，周 倩，李學(xué)明

(北京郵電大學(xué)信息與通信工程學(xué)院，北京 100876)

形狀上下文是一種廣泛應(yīng)用的圖像形狀特征提取與匹配算法，針對其特征不具有對稱不變性，無法對互相對稱的相似圖像建立匹配的問題，提出了一種具有對稱不變性的改進形狀上下文特征提取與匹配算法。在形狀邊緣采樣點上計算形狀上下文中的角度關(guān)系描述時，令該點的梯度方向為極坐標系的0°，并比較特征0到π與π到2π兩個角度區(qū)間內(nèi)其他邊緣點的數(shù)量大小，根據(jù)比較結(jié)果，調(diào)整極坐標系中角度增加的方向，從而使特征具備對稱不變性。在迭代變形與計算形狀上下文時，僅在第一次迭代中使用改進的形狀上下文特征，從而使匹配更加穩(wěn)定。仿真實驗證明，該算法能夠有效地在互相對稱的相似圖像間建立匹配，提高檢索精度。

圖像匹配；形狀上下文；對稱不變性；匹配穩(wěn)定性

形狀特征是一類重要的圖像特征，其中形狀上下文(shape context)[1-2]是一種應(yīng)用廣泛的圖像形狀特征，該方法使用圖像輪廓點作為特征點，在對數(shù)極坐標系下計算每一點與輪廓上其他點的位置關(guān)系組成直方圖，在很多匹配、識別、檢索任務(wù)上都取得了較好的效果，如MNIST[3]字體識別等。該算法在處理非線性形變以及少量離群點時具有一定的魯棒性，并具有平移、尺度和旋轉(zhuǎn)不變性。

在現(xiàn)實生活中，互相對稱的相似圖像廣泛存在。如圖1所示，兩幅圖像中的形狀以豎直方向為對稱軸互相對稱，且由于形狀不具備自身對稱性，即不存在任何直線，使以該直線為對稱軸進行對稱變換后的圖像與原圖一樣，所以一個形狀無法通過旋轉(zhuǎn)得到另一個。

圖1 互相對稱的形狀與形狀上的對應(yīng)點

形狀上下文特征不具備對稱不變性，當在互相對稱的兩個形狀的對應(yīng)點上，如圖1中紅框里的兩個頂點上，分別提取形狀上下文特征時，差別會很大，從而無法對兩個形狀建立正確的匹配，也無法對含有這種圖像的集合進行有效地檢索。一種直接的解決方法是對數(shù)據(jù)集中的每個圖像，都增加對稱變換的圖像，然后對兩個圖像進行匹配，但這種方法將大幅增加運行時間，效率較低。為解決該問題，本文提出了一種改進的形狀上下文特征提取方法，其以邊緣點梯度方向作為特征極坐標起始方向，并根據(jù)該邊緣點兩側(cè)其他點的數(shù)量，對極坐標旋轉(zhuǎn)方向進行調(diào)整，從而使形狀特征具備對稱不變性。與傳統(tǒng)形狀上下文算法相比，該方法能有效地直接在對稱圖像之間建立匹配關(guān)系。

1 研究現(xiàn)狀

圖像檢索與匹配基于如顏色、紋理、形狀、空間位置等圖像的各種特征，根據(jù)情況單獨或聯(lián)合使用。此外還有一些難以直接描述其物理含義的特征，如SIFT(scale-invariant feature transform)特征[4]等，對圖1中所示的二值形狀圖像，其沒有豐富的局部灰度變化與分布特征，因此SIFT等基于灰度梯度統(tǒng)計的方法難以有效提取特征，而其含有清晰的形狀邊界信息，對這種圖像，使用形狀特征進行匹配和檢索效果最好。

基于形狀特征的匹配與檢索，其核心在于形狀特征的提取，迄今為止已有很多方法被提出，可分為函數(shù)表示法、多邊形近似、內(nèi)部空間關(guān)系特征、尺度空間法以及變換域方法等[5]。形狀上下文描述的是一種形狀的內(nèi)部空間關(guān)系特征，在這一類形狀特征提取方法中，比較典型的還有鏈 碼[6]、基于中軸的shock graph[7]以及基于張量尺度的方法[8]等。

針對形狀上下文方法，MORI等[9]提出了剪枝形狀上下文方法，只計算部分輪廓點的形狀上下文特征來表示輪廓，或?qū)π螤钌舷挛倪M行向量量化，提高了圖像檢索效率。XIE等[10]則提出基于形狀骨架以優(yōu)化邊緣采樣，并根據(jù)骨架端點建立一個由粗到細的匹配框架，降低計算復(fù)雜度，減少了計算時間。溫麗華和賴康生[11]將形狀上下文與序貫相似性檢測結(jié)合起來，縮短了非匹配字符的匹配時間，提高了效率。徐衍魯?shù)萚12]提出將SIFT與形狀上下文結(jié)合，將兩種特征級聯(lián)匹配。鄭丹晨和韓敏[13]提出一種利用角點典型形狀上下文特征進行快速形狀識別的方法，僅以少數(shù)角點作為代表點生成直方圖，對目標形狀關(guān)鍵特征進行描述，通過減少匹配的特征數(shù)目降低了采樣點匹配時間。吳曉雨等[14]提出尋找采樣點最多的角度區(qū)間的方法改變圖像角度，從而給出了加入旋轉(zhuǎn)不變性的另一種方法。

上述方法均對形狀上下文特征提取與匹配算法進行了一定程度的改進，但均未解決傳統(tǒng)算法不具備對稱不變性的問題。

2 基于形狀上下文的圖像特征提取與匹配

(1) 特征提取。首先提取目標形狀的邊緣并隨機采樣邊緣點(圖2(a)~(b))，并計算邊緣點的方向，然后再采用如圖2(c)所示的極坐標系統(tǒng)對每個點計算其他與剩余邊緣點的位置關(guān)系，其中距離根據(jù)圖中點之間的平均距離歸一化，得到如圖2(d)所示的形狀上下文直方圖。

(2) 匹配。首先對兩組邊緣點根據(jù)其形狀上下文和邊緣方向特征計算相似度，用Hungarian算法得到兩組邊緣點的匹配，如圖3所示；然后對待匹配圖像進行仿射和薄板樣條(thin plate spline，TPS)變換，使待匹配圖變形為與目標圖更相似的圖像，并計算變形后的特征相似度。重復(fù)以上計算相似度-匹配-變形的步驟直至預(yù)設(shè)的變形次數(shù)。

圖2 形狀上下文特征提取

圖3 形狀匹配對應(yīng)點

關(guān)于旋轉(zhuǎn)不變性，文獻[2]介紹了一種為形狀上下文特征引入旋轉(zhuǎn)不變性的方法，在計算直方圖時定義邊緣點的切向量方向為極坐標0°，使特征具備旋轉(zhuǎn)不變性。

3 對稱不變性形狀上下文特征提取與匹配

3.1 對稱不變性

圖像的對稱變換改變圖像點與點之間的角度位置關(guān)系，但距離關(guān)系不變。如對圖像沿豎直軸做左右對稱變換，則對應(yīng)點的左右位置關(guān)系反轉(zhuǎn)。為使形狀上下文特征能夠在對稱變換中保持不變，應(yīng)使特征極坐標中的角度部分做相應(yīng)變換。即需對極坐標系0°位置和角度增加的方向(順時針或逆時針)做相應(yīng)調(diào)整，如圖4所示。

圖4 極坐標0°位置與角度增加方向示意圖

定位極坐標系0°位置。以該點的梯度方向作為極坐標系中的0°，由于點梯度方向會隨對稱變換進行相應(yīng)變換，因此該方法可以使0°位置具備對稱不變性。

對角度增加的方向?？疾烀嫦蛱荻确较驎r需考慮該點左右兩側(cè)其他邊緣點的數(shù)量，角度從數(shù)量多的一側(cè)開始增加。若兩點是兩個互相對稱圖像中的對應(yīng)點，則其應(yīng)以梯度方向開始，互相反向旋轉(zhuǎn)一周才能獲得相同的形狀上下文特征描述。同時，梯度方向的左右兩側(cè)點的數(shù)量多數(shù)情況下也具有這種反向性，因此該方法可使角度增加的方向具備對稱不變性。在圖4(a)中梯度方向右側(cè)半圓區(qū)域內(nèi)邊緣點多，角度順時針增加；圖4(b)梯度方向左側(cè)半圓區(qū)域內(nèi)邊緣點多，角度逆時針增加。

3.2 匹配穩(wěn)定性

通過定義梯度方向為極坐標0°，然后自適應(yīng)改變角度增加方向，引入對稱不變性并保持了旋轉(zhuǎn)不變性，但該方法提取的特征穩(wěn)定性有所降低，更容易使非對應(yīng)部位出現(xiàn)相似的特征，這種問題在引入文獻[2]的旋轉(zhuǎn)不變性時也會出現(xiàn)。

為了解決這個問題，在迭代計算形狀上下文與圖像變形的流程中，僅在第一次迭代時使用對稱不變的形狀上下文提取算法，經(jīng)過一次TPS變換后，使用傳統(tǒng)的形狀上下文特征(無旋轉(zhuǎn)不變性)。由于對稱不變形狀上下文特征在第一次匹配時能夠提供足量的正確匹配，因此第一次TPS變換能夠判斷目標圖像是否與待匹配圖對稱，進而使目標圖像實現(xiàn)對稱變形，如圖5所示，這使得第二次迭代時目標圖與待匹配圖恢復(fù)非對稱關(guān)系，從而能夠使用穩(wěn)定性更高的傳統(tǒng)形狀上下文匹配算法。

若兩幅圖像僅有一部分相互對稱，使用提出的改進算法，可以在第一次迭代匹配時得到基本正確的匹配結(jié)果。但由于在后續(xù)的迭代匹配與變形中對圖像進行的是全局變形，從而在第二次及以后的匹配中，匹配效果會變差，因此本算法只能對局部對稱的圖像進行一次粗略匹配，無法通過多次變形獲得高精度的匹配。

圖5 互相對稱的相似圖像以及第一次TPS變換結(jié)果

((c)中藍色“+”為(a)經(jīng)過一次TPS變換的結(jié)果)

3.3 算法與分析

本文算法具體步驟為：

步驟2. 根據(jù)當前循環(huán)次數(shù)的取值，選擇計算形狀上下文直方圖的方法，其中距離關(guān)系計算在兩種方法中一致，區(qū)間劃分均采用對數(shù)形式，并使用所有點距離的均值進行歸一化。

若>1，則按照傳統(tǒng)形狀上下文匹配算法計算特征，最終角度值即為初始角度，即

其中，為形狀上下文的直方圖，而邊緣點角度差為

根據(jù)損失矩陣，對兩組采樣點用Hungarian算法進行匹配，得到匹配損失最小的一組對應(yīng)關(guān)系，即

步驟4. 根據(jù)采樣點的對應(yīng)關(guān)系，對目標形狀圖像進行TPS變換，使目標形狀按照與原形狀圖像更相似的方向變形，得到目標形狀的一組新的采樣點。

算法分析：

在每一次循環(huán)中，均根據(jù)上一次的匹配結(jié)果對一幅圖像進行TPS變換，變換使得兩幅圖像上互相對應(yīng)的邊緣點之間距離降低。因此圖像更加相似，從而兩幅圖像形狀上下文特征的卡方距離得以降低，具體變換的過程參考文獻[2]。雖然本文算法引入了對稱不變性，但僅在第一次循環(huán)中使用了改進的形狀上下文特征，因此收斂性得以保持。

為了降低離群點的影響，本文算法還在式(6)的損失矩陣中引入虛擬點，一旦某個點與其他所有點的損失都高于給定閾值，則該點會與虛擬點進行匹配，因此互相匹配的點都能夠保持一定程度的相似性，增強了算法的魯棒性。

4 仿真實驗與分析

4.1 數(shù)據(jù)集與參數(shù)設(shè)置

為驗證改進形狀上下文特征匹配算法的有效性與準確性，在MPEG-7數(shù)據(jù)集中，選擇了100個形狀作為圖像集，該圖像集中有互相對稱的相似圖像，但每個圖像都不具備自身對稱性，100個圖像共分為10類，每類10個。另外還收集了一些典型民族服飾圖案作為圖像集，包含10類共59個形狀圖案。如圖6所示，在這兩個數(shù)據(jù)集上分別進行匹配與檢索仿真實驗。

4.2 仿真實驗

4.2.1 對稱圖像匹配實驗

圖6 實驗用數(shù)據(jù)集

圖7 形狀上下文損失變化曲線

圖8 匹配實驗部分結(jié)果

如圖8所示，本文算法能夠?qū)ハ鄬ΨQ的圖像建立較為準確的匹配，包括部分形變(圖8(a)中第1列的鳥圖案和第3列的錘子圖案)以及旋轉(zhuǎn)(圖8(a)中的錘子圖案)的情況下仍有良好的匹配效果，而傳統(tǒng)算法則無法使對應(yīng)點建立匹配。

4.2.2 檢索實驗

圖9 檢索實驗結(jié)果

由圖9可以看出，本文提出的對稱不變形狀上下文算法在100個MPEG-7圖像上檢索效果略優(yōu)于IDSC算法，且明顯優(yōu)于傳統(tǒng)形狀上下文算法(包括沒有和有旋轉(zhuǎn)不變性兩類)，在傳統(tǒng)民族服飾圖案檢索上，本文算法效果明顯優(yōu)于其他算法。實驗還驗證了匹配穩(wěn)定性問題，如圖中紅色“*”曲線所示，若在4次迭代中均使用對稱不變形狀上下文特征，其檢索效果弱于旋轉(zhuǎn)不變的傳統(tǒng)形狀上下文算法。

5 結(jié)束語

本文針對形狀上下文特征提取與匹配算法不具備對稱不變性的問題，提出了一種改進的形狀上下文算法。算法在提取形狀上下文特征時，令采樣點的梯度方向為極坐標0°，并比較梯度方向兩側(cè)采樣點數(shù)量，調(diào)整極坐標角度增加方向，使特征獲得對稱不變性；同時，在迭代匹配步驟中，僅在第一次迭代使用對稱不變特征，加強了匹配的穩(wěn)定性。實驗證明，本文算法能有效地對互相對稱的相似圖像建立匹配，并提高檢索的準確率。

[1] BELONGIE S, MALIK J, PUZICHA J. Shape context: a new descriptor for shape matching and object recognition [C]//NIPS’00 Proceedings of the 13thInternational Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2001: 831-837.

[2] BELONGIE S, MALIK J, PUZICHA J. Shape matching and object recognition using shape contexts [J]. IEEE Transactions on Pattern Analysis and MachineIintelligence, 2002, 24(4): 509-522.

[3] LECUN Y, BOTTOU L, BENGIO Y, et al. Gradient-based learning applied to document recognition [J]. Proceedings of the IEEE, 1998, 86(11): 2278-2324.

[4] LOWE, D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[5] YANG M Q, KPALMA K, RONSIN J. A survey of shape feature extraction techniques [M]//Pattern Recognition Techniques, Technology and Applications. Vienna: IN-TECH Open Access Publisher, 2008: 43-90.

[6] IIVARINEN J, VISA A J E. Shape recognition of irregular objects [C]//Proceedings of SPIE 2904: Intelligent Robots and Computer Vision XV: Algorithms, Techniques, Active Vision, and Materials Handling. Berlingham: the International Society for Optics and Photonics, 1996: 25-32.

[7] SIDDIQI K, SHOKOUFANDEH A, DICKINSON S J, et al. Shock graphs and shape matching [J]. International Journal of Computer Vision, 1999, 35(1): 13-32.

[8] ANDALó F A, MIRANDA P A V, TORRES R S, et al. Shape feature extraction and description based on tensor scale [J]. Pattern Recognition, 2010, 43(1): 26-36.

[9] MORI G, BELONGIE S, MALIK J. Efficient shape matching using shape contexts [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(11): 1832-1837.

[10] XIE J, HENG P A, SHAH M. Shape matching and modeling using skeletal context [J]. Pattern Recognition, 2008, 41(5): 1756-1767.

[11] 溫麗華, 賴康生. 基于形狀上下文的字符識別算法的改進[J]. 工業(yè)控制計算機, 2014, 27(7): 137-139.

[12] 徐衍魯, 馬燕, 李順寶, 等. 結(jié)合顏色不變量的SIFT和形狀上下文圖像匹配算法[J]. 計算機科學(xué), 2014, 41(Z11): 144-146,177.

[13] 鄭丹晨, 韓敏. 基于改進典型形狀上下文特征的形狀識別方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2013, 25(2): 215-220.

[14] 吳曉雨, 何彥, 楊磊, 等. 基于改進形狀上下文特征的二值圖像檢索[J]. 光學(xué)精密工程, 2015, 23(1): 302-309.

[15] ZHENG Y, DOERMANN D. Robust point matching for nonrigid shapes by preserving local neighborhood structures [J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2006, 28(4): 643-649.

Symmetry Invariance Shape Context Feature Extraction and Image Matching

JIA Gengyun, ZHAO Haiying, ZHOU Qian, LI Xueming

(School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China)

Shape context is a popular algorithm of image shape feature extraction and matching, traditional shape context algorithm lacks symmetry invariance, which means it can not match two similar but symmetrical shapes. To overcome this shortcoming, this article proposed an improved shape context algorithm with symmetry invariance. The method defines the gradient direction of a sample point as its 0 rad in log polar coordinates when computing the angle relations in shape context, then compare the number of sample points in 0 rad to π rad and π rad to 2π rad, and adjust the angel increasing direction in the coordinate according to the results. In the process of iterative shape warping and shape contexts calculation, the symmetry invariance descriptors are only applied in the first iteration to obtain a more stable matching result. Experimental results show that the proposed algorithm can effectively establish match between two similar and symmetrical shapes, and therefor improve the retrieval precision.

image matching; shape context; symmetry invariance; matching stability

TP 391

10.11996/JG.j.2095-302X.2018030470

A

2095-302X(2018)03-0470-07

2017-01-14；

2017-05-11

國家自然科學(xué)基金項目(61163044)；北京市科委基金課題(D171100003717003)；財政部項目(GSSKS-2015-035)

賈耕云(1992–)，男，山東泰安人，碩士研究生。主要研究方向為文化計算與模式識別。E-mail：jiagengyun@bupt.edu.cn

趙海英(1972–)，女，山東煙臺人，副教授，博士。主要研究方向為文化計算與模式識別。E-mail：zhaohaiying@bupt.edu.cn