·1206 北京科技大学学报 第35卷 所需时间为20组实验的平均值.七个描述子在各 参考文献 阶段所需的处理时间如表1所示.从表中可以看 出，七种傅里叶描述子完成匹配所需的时间差异很 [1]Datta R,Joshi D,Li J,et al.Image retrieval:ideas,in- 小.在三个阶段中，傅里叶变换所需时间最短，如 fluences,and trends of the new age.ACM Comput Surv, 2008,40(2):1 MTAFD进行傅里叶变换不到其匹配阶段所用时间 的2%.这得益于快速傅里叶变换的使用.七种傅里 [2]Huang W,Gao Y,Chan K L.A review of region-based image retrieval.J Signal Process Syst,2010,59(2):143 叶描述子完成轮廓线函数提取时间差别较明显，如 [3 Wang CZ,Yang Y D,Feng Y L,et al.Identification and MTAFD完成轮廓线函数提取需2.927ms,远小于 detection of deep-sea obstacles and terrains based on im- AHRFD、AF、PAF+CD以及FPD所需的时间.这 age processing.J Univ Sci Technol Beijing,2011,33(7): 主要是由于FPD每个点所对应的最远点不同，增 777 加了提取最远点函数的计算量.AHRFD在计算拱 (王财政，杨耀东，冯雅丽，等。基于图像处理的深海底障 高半径复函数时，轮廓线上每个点的拱高都通过计 碍物和地形识别及检测.北京科技大学学报，2011,33(7)： 算该点的半径及相应长度的弧线来确定，且拱高符 777) 号的判断也增加了AHRFD的计算复杂度，PAF的 [4]Adamek T,O'Connor N E.A multiscale representation method for nonrigid shapes with a single closed contour. 计算中也存在类似的情况.MTAFD在计算多级三 IEEE Trans Circuits Syst Video Technol,2004,14(5):742 角形面积时，所需参数少且原理相对简单，因而计 5]Wang B.A Fourier shape descriptor based on multi-level 算复杂度较小 chord length function.Chin J Comput,2010,33(12):2387 表1七种描述子在轮廓线函数提取、傅里叶变换及匹配阶 (任斌.一种基于多级弦长函数的傅立叶形状描述子.计算 段平均所需时间 机学报，2010,33(12)：2387) Table 1 Average processing time required in the feature (6]Zhang D,Lu G.Review of shape representation and de function extraction stage,Fourier transform stage and match- scription techniques.Pattern Recognit,2004,37(1):1 ing stage for seven descriptors ms [7 Zhang D,Lu G.Study and evaluation of different Fourier 描述子轮廓线函数提取时间傅里叶变换时间匹配时间 methods for image retrieval.Image Vis Comput,2005, MTAFD 2.927 0.020 1.736 23(1):33 AHRFD 15.200 0.036 1.713 8 El-ghazal A,Basir O,Belkasim S.Farthest point distance: CD 0.010 0.003 1.680 a new shape signature for Fourier descriptors.Signal Pro- PAF+CD 15.162 0.007 1.714 cess:Image Commun,2009,24(7):572 FPD 30.497 0.003 1.733 AF 1.703 9 Wang B.Shape description using arc-height radius com- 27.933 0.005 ARF 1.660 0.017 1.721 plex function.Acta Electron Sin,2011,39(4):831 (王斌.一种用于形状描述的拱高半径复函数.电子学报 由此可以看出，与其他傅里叶描述子相比， 2011,39(4:831) MTAFD进行形状描述和匹配所需的计算时间较 [10]Wang B.Shape retrieval using combined Fourier features. 少，在复杂度上具有明显的优势 Opt Commun.2011,284(14):3504 [11]Alajlan N,Rube I E,Kamel M S,et al.Shape retrieval us- 4结论 ing triangle-area representation and dynamic space warp- 提出了一种用于形状检索的基于多级三角形 ing.Pattern Recognit,2007,40(7):1911 面积函数的傅里叶描述子.它产生于轮廓的非等弧 [12]Bandera A,Marfil R,Antuinez E.Affine-invariant con- 长分割，可以很好地描述形状的整体特征和局部细 tours recognition using an incremental hybrid learning ap- 节特征，且具有仿射不变性.在标准的MPEG-7形 proach.Pattern Recognit Lett,2009,30(14):1310 状图像库上进行的形状图像检索实验结果表明，与 [13 Latecki L J,Lakamper R,Eckhardt T.Shape descriptors for non-rigid shapes with a single closed contour /Pro- 中心距离函数、面积函数、最远点距离函数、角度 ceedings of the IEEE Conference on Computer Vision and 半径复函数、拱高半径复函数以及混合傅里叶描述 Pattern Recognition.South Carolina,2000:424 子相比，基于多级三角形面积函数的傅里叶描述子 [14 Kunttu I,Lepist L.Shape-based retrieval of industrial 取得了最优的检索性能，且在计算复杂度上具有较 surface defects using angular radius Fourier descriptor 明显的优势 IET Image Process,2007,1(2):231· 1206 · 北 京 科 技 大 学 学 报 第 35 卷 所需时间为 20 组实验的平均值. 七个描述子在各 阶段所需的处理时间如表 1 所示. 从表中可以看 出，七种傅里叶描述子完成匹配所需的时间差异很 小. 在三个阶段中，傅里叶变换所需时间最短，如 MTAFD 进行傅里叶变换不到其匹配阶段所用时间 的 2%. 这得益于快速傅里叶变换的使用. 七种傅里 叶描述子完成轮廓线函数提取时间差别较明显，如 MTAFD 完成轮廓线函数提取需 2.927 ms，远小于 AHRFD、AF、PAF+CD 以及 FPD 所需的时间. 这 主要是由于 FPD 每个点所对应的最远点不同，增 加了提取最远点函数的计算量. AHRFD 在计算拱 高半径复函数时，轮廓线上每个点的拱高都通过计 算该点的半径及相应长度的弧线来确定，且拱高符 号的判断也增加了 AHRFD 的计算复杂度，PAF 的 计算中也存在类似的情况. MTAFD 在计算多级三 角形面积时，所需参数少且原理相对简单，因而计 算复杂度较小. 表 1 七种描述子在轮廓线函数提取、傅里叶变换及匹配阶 段平均所需时间 Table 1 Average processing time required in the feature function extraction stage, Fourier transform stage and match￾ing stage for seven descriptors ms 描述子 轮廓线函数提取时间 傅里叶变换时间 匹配时间 MTAFD 2.927 0.020 1.736 AHRFD 15.200 0.036 1.713 CD 0.010 0.003 1.680 PAF+CD 15.162 0.007 1.714 FPD 30.497 0.003 1.733 AF 27.933 0.005 1.703 ARF 1.660 0.017 1.721 由此可以看出，与其他傅里叶描述子相比， MTAFD 进行形状描述和匹配所需的计算时间较 少，在复杂度上具有明显的优势. 4 结论 提出了一种用于形状检索的基于多级三角形 面积函数的傅里叶描述子. 它产生于轮廓的非等弧 长分割，可以很好地描述形状的整体特征和局部细 节特征，且具有仿射不变性. 在标准的 MPEG-7 形 状图像库上进行的形状图像检索实验结果表明，与 中心距离函数、面积函数、最远点距离函数、角度 半径复函数、拱高半径复函数以及混合傅里叶描述 子相比，基于多级三角形面积函数的傅里叶描述子 取得了最优的检索性能，且在计算复杂度上具有较 明显的优势. 参 考 文 献 [1] Datta R, Joshi D, Li J, et al. Image retrieval: ideas, in- fluences, and trends of the new age. ACM Comput Surv, 2008, 40(2): 1 [2] Huang W, Gao Y, Chan K L. A review of region-based image retrieval. J Signal Process Syst, 2010, 59(2): 143 [3] Wang C Z, Yang Y D, Feng Y L, et al. Identification and detection of deep-sea obstacles and terrains based on im￾age processing. J Univ Sci Technol Beijing, 2011, 33(7): 777 (王财政, 杨耀东, 冯雅丽, 等. 基于图像处理的深海底障 碍物和地形识别及检测. 北京科技大学学报, 2011, 33(7): 777) [4] Adamek T, O’Connor N E. A multiscale representation method for nonrigid shapes with a single closed contour. IEEE Trans Circuits Syst Video Technol, 2004, 14(5): 742 [5] Wang B. A Fourier shape descriptor based on multi-level chord length function. Chin J Comput, 2010, 33(12): 2387 (王斌. 一种基于多级弦长函数的傅立叶形状描述子. 计算 机学报, 2010, 33(12): 2387) [6] Zhang D, Lu G. Review of shape representation and de￾scription techniques. Pattern Recognit, 2004, 37(1): 1 [7] Zhang D, Lu G. Study and evaluation of different Fourier methods for image retrieval. Image Vis Comput, 2005, 23(1): 33 [8] El-ghazal A, Basir O, Belkasim S. Farthest point distance: a new shape signature for Fourier descriptors. Signal Pro￾cess: Image Commun, 2009, 24(7): 572 [9] Wang B. Shape description using arc-height radius com￾plex function. Acta Electron Sin, 2011, 39(4): 831 (王斌. 一种用于形状描述的拱高半径复函数. 电子学报, 2011, 39(4): 831) [10] Wang B. Shape retrieval using combined Fourier features. Opt Commun, 2011, 284(14): 3504 [11] Alajlan N, Rube I E, Kamel M S, et al. Shape retrieval us￾ing triangle-area representation and dynamic space warp￾ing. Pattern Recognit, 2007, 40(7):1911 [12] Bandera A, Marfil R, Ant´unez E. Affine-invariant con￾tours recognition using an incremental hybrid learning ap￾proach. Pattern Recognit Lett, 2009, 30(14): 1310 [13] Latecki L J, Lakamper R, Eckhardt T. Shape descriptors for non-rigid shapes with a single closed contour // Pro￾ceedings of the IEEE Conference on Computer Vision and Pattern Recognition. South Carolina, 2000: 424 [14] Kunttu I, Lepist L. Shape-based retrieval of industrial surface defects using angular radius Fourier descriptor. IET Image Process, 2007, 1(2): 231