應(yīng)用全方向形狀特征碼的圖像檢索方法

田澤宇， 門朝光， 湯亞楠， 蔣慶豐

(哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001)

?

應(yīng)用全方向形狀特征碼的圖像檢索方法

田澤宇， 門朝光， 湯亞楠， 蔣慶豐

(哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001)

為提高圖像形狀信息的檢索準確率和效率，提出應(yīng)用全方向形狀特征碼的圖像檢索方法. 該方法在全方向上對形狀進行分割，度量形狀各方向各部分的復(fù)雜度，構(gòu)建形狀的全方向特征碼，計算形狀間的相似度. 通過真實建筑形狀數(shù)據(jù)集和MPEG-7 CE-1 Part B形狀數(shù)據(jù)集對本方法進行了檢索性能測試，并和其他形狀相似性描述方法進行了對比. 實驗結(jié)果表明，本方法具有更高的檢索準確率和較高的檢索效率. 全方向形狀特征碼圖像檢索方法可以準確描述形狀的全局特征與局部特征，具有平移、旋轉(zhuǎn)、尺度不變性，及較強的形狀描述識別能力.

圖像檢索；形狀相似性描述；形狀特征碼；形狀復(fù)雜度；形狀全方向分割

為了快速、準確地從海量圖像數(shù)據(jù)中檢索出需要的圖像，基于內(nèi)容的圖像檢索快速發(fā)展，成為模式識別和計算機視覺領(lǐng)域的研究熱點. 圖像內(nèi)容包括紋理、顏色、形狀等信息. 相對于紋理、顏色等基本特征，形狀是高級別的視覺信息[1]，更具視覺表征性[2]，更能從語義上描述目標圖像的內(nèi)容[3]，是基于內(nèi)容圖像檢索的關(guān)鍵.

現(xiàn)有形狀描述方法主要包括基于輪廓邊界點集和基于骨架的兩類方法. 基于輪廓邊界點集的形狀描述法主要有形狀上下文描述法(Shape context)[4]、內(nèi)距離形狀上下文描述法IDSC(inner-distance shape context)[5]、慣性軸描述法(Axis of Least Inertia)[6-7]、帶符號的三角形面積形狀描述法TAR(triangle area representation)[8-9]和基于變換域的形狀描述法[3,10-12]等. 形狀上下文描述法通過直方圖記錄輪廓序列上某個點與其他所有點的空間分布關(guān)系，具有較強的形狀描述能力[4]. 內(nèi)距離形狀上下文描述法通過輪廓點之間的內(nèi)距離代替形狀上下文描述法中的歐氏距離，更有效地表征形狀的局部信息[5]. 慣性軸描述法以最小慣性軸為參考線提取形狀的特征向量，可同時描述形狀的輪廓和區(qū)域信息，具有描述多層次復(fù)雜形狀的能力[6-7]. 三角形面積描述法在所有尺度級別上通過帶符號的三角形面積，表示形狀中每個點的凹凸性，可以同時描述形狀的局部與全局特征[8-9]. 基于變換域的形狀描述法主要有多級弦長函數(shù)的傅里葉形狀描述子MCLFD(Fourier shape descriptor based on multi-level chord length function)[10]、多尺度拱高形狀描述MSAH(multi-scale arch height shape description)[11]和HSC (hierarchical string cuts)[12]等，這些方法均描述了形狀的全局特征和細節(jié)信息. 基于骨架的形狀檢索方法通過提取形狀的骨架，準確描述形狀的幾何特征和拓撲結(jié)構(gòu)，具有較高的形狀匹配精度[13-14].

在現(xiàn)有形狀描述方法的基礎(chǔ)上，為進一步提高形狀的識別精度，本文提出應(yīng)用全方向形狀特征碼的圖像檢索方法. 本方法在特定方向上利用一組等距分割線將形狀分成若干分割份，計算所有分割份中每個點的帶符號三角形面積和每個分割份的形狀復(fù)雜度SC(shape complex)，得到形狀特定方向上的特征碼. 旋轉(zhuǎn)該組分割線，計算形狀每個分割方向上的特征碼，得到形狀的全方向特征碼. 計算待匹配形狀的主方向，確定兩個待匹配形狀的對應(yīng)方向，計算兩個待匹配形狀的相似度. 全方向形狀特征碼描述法進一步將形狀的全局特征和局部特征融合，具有平移、尺度、旋轉(zhuǎn)不變性，對形狀的形變具有一定的魯棒性，具有更高的形狀識別精度.

1 形狀特征碼

1.1 形狀復(fù)雜度

帶符號的三角形面積形狀描述同時包含了形狀的局部與全局特征，具有平移、旋轉(zhuǎn)和縮放不變性，且有較強的抗噪聲和扭曲能力[8-9]. 設(shè)形狀由N個輪廓點組成，任意3個連續(xù)輪廓點(xn-t,yn-t)、(xn,yn)、(xn+t,yn+t)構(gòu)成的帶符號三角形面積STAR為

(1)

(2)

如圖1所示，從人類視覺的感知角度，圖1(a)、(b)、(c)、(d)這4個形狀越來越復(fù)雜，形狀復(fù)雜度SC也逐漸增大. 圖1(a)、(b)相似度較高，形狀復(fù)雜度相近；圖1(c)、(d)相似度較高，形狀復(fù)雜度相近.

圖1 形狀復(fù)雜度SC示例

1.2 形狀特征碼

規(guī)定某一方向為初始方向Odir(0)，求出與初始方向平行且與形狀輪廓最外側(cè)相交的兩條邊界線，如圖2中規(guī)定0度方向為初始方向，兩條實線為邊界線. 利用與初始方向平行的n條直線將兩條邊界線之間的部分平均分割為n+1等份，如圖2中8條虛線將邊界線之間的部分平均分割為9等份. 利用式(1)計算形狀每個分割份中每個點的STAR值，利用式(2)計算形狀n+1個分割份的形狀復(fù)雜度SC，則形狀初始方向Odir(0)上的特征碼FC(Odir(0))為

圖2中形狀初始方向上的特征碼如圖3所示.

圖2 初始方向形狀分割示意圖Fig.2 Diagram of the shape segmentation in the original direction

圖3 形狀初始方向特征碼示意圖Fig.3 Diagram of the shape feature code in the original direction 從初始方向Odir(0)開始，每次間隔特定角度dangle對形狀進行分割，計算形狀特定方向Odir(i)上的特征碼FC(Odir(i))，直到旋轉(zhuǎn)回初始方向為止，共有m=360/dangle分割方向. 間隔角度dangle必須能被360整除，當(dāng)間隔角度dangle為1時，分割方向m值最大為360. 形狀特定方向Odir(i)的特征碼FC(Odir(i))為

m個分割方向的特征碼共同構(gòu)成形狀的全方向特征碼FC：

圖4為圖2從初始方向0度開始，每次間隔1度，10度和20度方向分割示意圖，圖5為圖2形狀全方向特征碼的三維示意圖.

1.3 形狀相似性度量

進行形狀相似性匹配時，待匹配形狀A(yù)和B可能發(fā)生過旋轉(zhuǎn)，導(dǎo)致各分割方向不對應(yīng). 為了確定對應(yīng)的分割方向，需計算形狀A(yù)、B各自的最小慣性軸，該軸不隨形狀轉(zhuǎn)換而改變，唯一保存了形狀的主方向. 形狀主方向位于通過形狀重心且傾角為θ的直線上，傾角θ公式為[15]

式中u11,u02,u20為形狀的p+q階中心矩. 圖6中Hammer15、Hammer5的主方向為帶箭頭的實線所示.

(a) 10度方向形狀分割

(b) 20度方向形狀分割

圖5 形狀全方向特征碼三維示意圖

Fig.5 Three-dimensional diagram of the omnidirectional shape feature code

主方向可能會因形狀的不均勻形變，產(chǎn)生一定的改變，導(dǎo)致兩個待匹配形狀對應(yīng)方向的確定出現(xiàn)誤差. 為了準確確定形狀A(yù)、B的對應(yīng)方向，以形狀A(yù)、B的主方向為參考，計算兩個形狀主方向附近分割方向的特征碼差異，將特征碼差異最小的兩個分割方向作為形狀A(yù)、B的對應(yīng)方向，圖6中帶箭頭的虛線表示主方向附近的分割方向. 設(shè)形狀A(yù)的某一分割方向為Odir(a)，形狀B的某一分割方向為Odir(b)，則形狀A(yù)、B的分割方向Odir(a)、Odir(b)的特征碼FCA(Odir(a))、FCB(Odir(b))差異度為

(3)

圖6 形狀主方向

設(shè)形狀A(yù)、B的對應(yīng)方向為Odir(a)、Odir(b)，從對應(yīng)方向開始，通過式(3)計算形狀A(yù)、B各分割方向的特征碼差異度，得到{D0,D1,…,Dm-1}，形狀A(yù)、B全方向特征碼差異度為

式中，間隔角度dangle必須能被360整除.

形狀A(yù)、B的形狀相似度S為

1.4 全方向形狀特征碼的描述性能分析

全方向形狀特征碼滿足尺度、旋轉(zhuǎn)、平移不變性. 全方向形狀特征碼使用每個方向所有分割份形狀復(fù)雜度SC的和，對每個分割份的形狀復(fù)雜度SC進行歸一化，滿足尺度不變性. 全方向形狀特征碼是利用各分割方向?qū)π螤钸M行分割，形狀復(fù)雜度SC是計算帶符號的三角形面積STAR，均與形狀特征點的絕對位置無關(guān)，不會因形狀的平移產(chǎn)生變化，滿足平移不變性. 全方向形狀特征碼利用形狀最小慣性軸保存的形狀主方向，確定兩個待匹配形狀的對應(yīng)方向，滿足旋轉(zhuǎn)不變性.

全方向形狀特征碼結(jié)合了三角形面積描述法[8]和慣性軸描述法[6]，并通過全方向的形狀分割，進一步將形狀的局部與全局特征融合，對發(fā)生了形變和扭曲的形狀具有更強的識別能力.

2 復(fù)雜性分析

全方向形狀特征碼圖像檢索方法的時間復(fù)雜度分為全方向特征碼計算時間復(fù)雜度和形狀匹配時間復(fù)雜度兩部分. 設(shè)共有分割方向m個，形狀特征點N個，每個分割方向下分割線n條，主方向附近分割方向的搜索范圍為w.

全方向特征碼的計算包含各分割方向的帶符號三角形面積STAR和形狀復(fù)雜度SC的計算. 在某一分割方向下，n條分割線將形狀分為n+1份. 當(dāng)分割線數(shù)目n為0，即形狀沒有被分割時，帶符號三角形面積STAR的計算時間復(fù)雜度最大為O(N2)，形狀復(fù)雜度SC的計算時間復(fù)雜度為O(N)，則單一分割方向下，形狀特征碼的最大計算時間復(fù)雜度為O(N2). 全方向形狀特征碼的最大計算時間復(fù)雜度為O(m*N2)，分割方向數(shù)m的最大值為360，則全方向形狀特征碼的最大計算時間復(fù)雜度為O(N2).

形狀匹配包括主方向的計算、兩個待匹配對象對應(yīng)分割方向的計算和全方向特征碼差異度的計算. 主方向的計算時間復(fù)雜度為O(N)[15]. 兩個待匹配對象的對應(yīng)分割方向的計算時間復(fù)雜度為O(w2*(n+1))，w最大取值為10. 全方向特征碼差異度的計算時間復(fù)雜度為O(m*(n+1))，分割方向數(shù)m的最大值為360. 形狀匹配的時間復(fù)雜度為O(N+(n+1)(m+w2))，w最大取值為10，分割方向數(shù)m的最大值為360，分割線數(shù)目n通常為9，形狀匹配階段的時間復(fù)雜度較低，小于IDSC[5]、TAR[8]等的匹配時間復(fù)雜度.

3 實驗結(jié)果和分析

為評估本文提出的全方向形狀特征碼圖像檢索方法的檢索性能，使用兩個圖像數(shù)據(jù)庫進行測試. 一個圖像數(shù)據(jù)庫是被廣泛用來測試形狀檢索性能的標準測試集MPEG-7 CE-1 Part B，該數(shù)據(jù)庫包含按語義分類的70類形狀，每類20個，共1 400個形狀圖像. 另一個圖像數(shù)據(jù)庫是本文通過真實建筑形狀構(gòu)建的數(shù)據(jù)集，該數(shù)據(jù)庫從真實地圖中選取70個形狀各異的建筑物，如圖7中上方圖所示. 對每一個建筑物分別縮放0.49、0.7、1.37倍，得到3個建筑物，如圖7中下方圖第一行從左至右依次是原始建筑、縮放0.49倍建筑、縮放0.7倍建筑、縮放1.37倍建筑. 對原始建筑和3個縮放建筑分別旋轉(zhuǎn)45°、135°、225°得到12個建筑，如圖7中下方圖第二行、第三行、第四行的建筑分別為第一行建筑旋轉(zhuǎn)45°、135°、225°. 對原始建筑進行四種仿射變換，得到4個建筑，如圖7中下方圖第五行所示. 對每個建筑共進行了19次變換，得到了19個建筑，加上原始建筑，構(gòu)成了一類相似建筑的20種形變. 70個原始建筑共形成了70類，每類20個相似建筑，共1 400個建筑的形狀數(shù)據(jù)集. 性能評估使用通用的Bulls-eye測試方法[12]，該方法對形狀數(shù)據(jù)集中的每個形狀均進行一次檢索，共進行1 400次檢索實驗. 在每次實驗檢索出的前40個相似性最高的形狀中，計算檢索形狀的同類相似形狀個數(shù)，并統(tǒng)計1 400次檢索實驗相似形狀的總和. 因一類相似形狀有20個，共1 400次實驗，相似形狀總和最大為20*1400=28 000. 統(tǒng)計得到的相似形狀總和除以28 000為Bulls-eye測試的檢索率. 形狀檢索的時間是待檢索形狀和數(shù)據(jù)集中1 400個形狀的特征匹配時間. MSAH[11]、MCLFD[10]、HSC[12]、IDSC[5]、TAR[8]與本文全方向形狀特征碼描述法在真實建筑形狀數(shù)據(jù)集上的檢索率和平均檢索時間如表1所示，在MPEG-7 CE-1 Part B形狀數(shù)據(jù)集上的檢索率和平均檢索時間如表2所示.

圖7 真實建筑形狀數(shù)據(jù)集

形狀描述法檢索率/%平均檢索時間/msMSAH[11]90.651.36×102MCLFD[10]88.132.40×102TAR[8]94.762.49×104HSC[12]95.131.15×102IDSC[5]92.891.71×104全方向形狀特征碼描述法96.172.32×103

表2 MPEG-7形狀數(shù)據(jù)集檢索率

從表1可以看出，在真實建筑形狀數(shù)據(jù)集中本文全方向形狀特征碼描述法的檢索率高于其他5個形狀描述法. 全方向形狀特征碼描述法可以準確識別真實建筑形狀數(shù)據(jù)集中所有經(jīng)過放大、縮小和旋轉(zhuǎn)的形狀，具有平移、旋轉(zhuǎn)和尺度不變性，對因仿射變換造成的形狀形變具有一定的魯棒性. 但較大程度的仿射變換導(dǎo)致建筑形變較大，造成誤匹配和漏匹配，影響本文形狀描述法的檢索率. 全方向形狀特征碼描述法的平均檢索時間大于MSAH[11]、MCLFD[10]和HSC[12]，主要是因為本文形狀描述方法為了提高檢索準確率，利用的形狀特征較多，導(dǎo)致檢索時間增加.

從表2可以看出，在MPEG-7 CE-1 Part B形狀數(shù)據(jù)集中本文全方向形狀特征碼描述法的檢索率高于其他5個形狀描述法，具有更強的形狀描述能力，對發(fā)生了形變的形狀具有更強的識別能力. 在檢索率大于80%的形狀描述法中，本文全方向形狀特征碼描述法的平均檢索時間小于TAR[8]、IDSC[5]的平均檢索時間，僅大于HSC[12]的平均檢索時間. 在保證檢索準確率的情況下，本文形狀描述法具有較高的檢索效率. 圖8給出了本文全方向形狀特征碼描述法在MPEG-7 CE-1 Part B形狀數(shù)據(jù)集上的部分檢索結(jié)果. 圖8中第1列為待檢索形狀，第2列到第8列為從MPEG-7數(shù)據(jù)集中檢索出的與待檢索形狀相似度最高的7個形狀，其中誤匹配被用圓圈標出. 從圖8中可以看出，誤匹配形狀與待檢索形狀還是存在一定程度相似性的，僅通過形狀特征的識別，MPEG-7 CE-1 Part B形狀數(shù)據(jù)集的檢索率不可能達到100%[8].

圖8 全方向形狀特征碼描述法部分檢索結(jié)果示例

Fig.8 Part of search results of the omnidirectional shape feature code method

4 結(jié) 論

本文提出的全方向形狀特征碼圖像檢索方法通過全方向的形狀分割和形狀復(fù)雜度概念，度量形狀各方向各部分的復(fù)雜度，進一步將形狀的局部與全局特征融合. 通過真實建筑形狀數(shù)據(jù)集和MPEG-7 CE-1 Part B形狀數(shù)據(jù)集的檢索實驗，表明本方法具有較高的形狀檢索準確率，具有平移、尺度、旋轉(zhuǎn)不變性，對發(fā)生了形變和扭曲的形狀具有較強的識別能力.

[1] 周瑜, 劉俊濤, 白翔. 形狀匹配方法研究與展望[J]. 自動化學(xué)報, 2012, 38(6): 889-910. DOI: 10.3724/SP.J.1004.2012.00889.

ZHOU Yu, LIU Juntao, BAI Xiang. Research and perspective on shape matching[J]. Acta Automatica Sinica, 2012, 38(6): 889-910. DOI: 10.3724/SP.J.1004.2012.00889.

[2] EL-GHAZAL A, BASIR O, BELKASIM S. Invariant curvature-based Fourier shape descriptors[J]. Journal of Visual Communication and image Representation, 2012, 23(4): 622-633.DOI:10.1016/j.jvcir.2012.01.011.

[3]王斌. 一種不變的基于傅里葉變換的區(qū)域形狀描述子[J]. 電子學(xué)報, 2012, 40(1): 84-88. DOI:10.3969/ j.issn.0372-2112 .2012.01.014.

WANG Bin. An invariant region-shape descriptor based on fourier transform[J]. Acta Electronica Sinica, 2012, 40(1): 84-88. DOI:10.3969/ j.issn.0372-2112 .2012.01.014.

[4] 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. DOI: 10.1109/TPAMI.2005.220.

[5] LING H B, JACOBS D W. Shape classification using the inner-distance[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(2): 286-299. DOI: 10.1109/TPAMI.2007.41.

[6] GURU D S, NAGENDRASWAMY H S. Symbolic representation of two-dimensional shapes[J]. Pattern Recognition Letters, 2007, 28(7): 144-155. DOI:10.1016/j.patrec.2006.06.017.

[7]李宗民, 陸天波, 桑鑫焱, 等. 基于最小慣性軸及鏈碼的圖像形狀描述方法[J]. 通信學(xué)報, 2009, 30(4): 1-5. DOI:1000-436X(2009)04-0001-05.

LI Zongmin, LU Tianbo, SANG Xinyan, et al. Shape description based on axis of least inertia and chain[J]. Journal on Communications, 2009, 30(4): 1-5. DOI:1000-436X(2009)04-0001-05.

[8] ALAJLAN N, EL RUBE I, KAMEL M S, et al. Shape retrieval using triangle-area representation and dynamic space warping [J]. Pattern Recognition, 2007, 40(7): 1911-1920. DOI:10.1016/j.patcog.2006.12.005.

[9] ALAJLAN N, KAMEL M S, FREEMAN G. Geometry-based image retrieval in binary image databases [J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(6): 1003-1013. DOI: 10.1109/TPAMI.2008.37.

[10]王斌. 一種基于多級弦長函數(shù)的傅里葉形狀描述子[J]. 計算機學(xué)報, 2010, 33(12): 2387-2396. DOI:10.3724/ SP.J.1016 .2010.02387.

WANG Bin. A fourier shape descriptor based on multi-level chord length function[J]. Chinese Journal of Computers, 2010, 33(12): 2387-2396. DOI:10.3724/ SP.J.1016 .2010.02387.

[11]王斌. 一種基于多尺度拱高形狀描述的圖像檢索方法[J]. 電子學(xué)報, 2013, 41(9): 1821-1825. DOI:10.3969/j.issn.0372-2112.2013.09.024.

WANG Bin. Image retrieval using multi-scale arch height shape description[J]. Acta Electronica Sinica, 2013, 41(9): 1821-1825.DOI:10.3969/j.issn.0372-2112.2013.09.024.

[12]WANG B, GAO Y. Hierarchical string cuts: a translation, rotation, scale, and mirror invariant descriptor for fast shape retrieval[J]. IEEE Transactions on Image Processing, 2014, 23(9): 4101-4111. DOI: 10.1109/TIP.2014.2343457.

[13]BAI X, LATECKI L J. Path similarity skeleton graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7): 1282-1292. DOI: 10.1109/TPAMI.2007.70769.

[14]ERDEM A, TARI S. A similarity-based approach for shape classification using Aslan skeletons[J]. Pattern Recognition Letters, 2010, 31(13): 2024-2032. DOI:10.1016/j.patrec.2010.06.003.

[15]ZUNIC J, ROSIN P L, KOPANJA L. On the orientability of shapes[J]. IEEE Transactions on Image Processing, 2006, 15(11): 3478-3487. DOI: 10.1109/TIP.2006.877527.

(編輯 王小唯 苗秀芝)

Image retrieval based on the omnidirectional shape feature code

TIAN Zeyu, MEN Chaoguang, TANG Yanan, JIANG Qingfeng

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

To improve retrieval accuracy and efficiency of the image shape information, this paper proposes an image retrieval method based on the omnidirectional shape feature code. This method segments the shape omnidirectially, measures the shape complexity of every direction and part, constructs the omnidirectional feature codes of the shape, and calculates the similarity of shapes. The actual structure shape data set and MPEG-7 CE-1 Part B shape data set are used to test the retrieval performance of this method, and this method is compared with other description methods of shape similarity. Experimental results show that this method has higher retrieval accuracy and efficiency. The image retrieval method based on the omnidirectional shape feature code can describe exactly global features and partial features of the shape. This method is invariant to translation, rotation, scaling, and strong ability to describe and recognize the shape.

image retrieval; shape similarity description; shape feature code; shape complexity; shape omnidirectional segment

10.11918/j.issn.0367-6234.2016.11.020

2015-11-19

田澤宇(1987—)，男，博士研究生； 門朝光(1963—)，男，教授，博士生導(dǎo)師

門朝光, menchaoguang@hrbeu.edu.cn

TP391.3

A

0367-6234(2016)11-0129-06