應用全方向形狀特征碼的圖像檢索方法

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

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

?

應用全方向形狀特征碼的圖像檢索方法

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

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

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

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

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

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

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

1 形狀特征碼

1.1 形狀復雜度

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

(1)

(2)

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

圖1 形狀復雜度SC示例

1.2 形狀特征碼

規定某一方向為初始方向Odir(0)，求出與初始方向平行且與形狀輪廓最外側相交的兩條邊界線，如圖2中規定0度方向為初始方向，兩條實線為邊界線. 利用與初始方向平行的n條直線將兩條邊界線之間的部分平均分割為n+1等份，如圖2中8條虛線將邊界線之間的部分平均分割為9等份. 利用式(1)計算形狀每個分割份中每個點的STAR值，利用式(2)計算形狀n+1個分割份的形狀復雜度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))，直到旋轉回初始方向為止，共有m=360/dangle分割方向. 間隔角度dangle必須能被360整除，當間隔角度dangle為1時，分割方向m值最大為360. 形狀特定方向Odir(i)的特征碼FC(Odir(i))為

m個分割方向的特征碼共同構成形狀的全方向特征碼FC：

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

1.3 形狀相似性度量

進行形狀相似性匹配時，待匹配形狀A和B可能發生過旋轉，導致各分割方向不對應. 為了確定對應的分割方向，需計算形狀A、B各自的最小慣性軸，該軸不隨形狀轉換而改變，唯一保存了形狀的主方向. 形狀主方向位于通過形狀重心且傾角為θ的直線上，傾角θ公式為[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

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

(3)

圖6 形狀主方向

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

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

形狀A、B的形狀相似度S為

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

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

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

2 復雜性分析

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

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

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

3 實驗結果和分析

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

圖7 真實建筑形狀數據集

形狀描述法檢索率/%平均檢索時間/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形狀數據集檢索率

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

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

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

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

4 結 論

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

[1] 周瑜, 劉俊濤, 白翔. 形狀匹配方法研究與展望[J]. 自動化學報, 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]王斌. 一種不變的基于傅里葉變換的區域形狀描述子[J]. 電子學報, 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]. 通信學報, 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]王斌. 一種基于多級弦長函數的傅里葉形狀描述子[J]. 計算機學報, 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]. 電子學報, 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—)，男，教授，博士生導師

門朝光, menchaoguang@hrbeu.edu.cn

TP391.3

A

0367-6234(2016)11-0129-06