第3卷第3期 智能系统学报 Vol 3 Na 3 2008年6月 CAA I Transactions on Intelligent System s Jun 2008 局部搜索的音频数据检索 李应 (福州大学数学与计算机科学学院，福建福州350108) 摘要：根据多媒体音频数据的特点，提出一种适用于快速音频数据检索的局部搜索数据结构，即局部搜索树(bcal search tr心e,LS-tee).在局部搜索树中，分别以音频数据小波变换系数的过零率和平均幅度作为主、次关键码，基于局 部范围对作为索引的其他系数进行组织.其次，基于局部搜索树，提出采用小波包最好基小波塔型算法实现音频数 据检索.最后，把采用局部搜索树的小波包最好基小波塔型算法的搜索和基于小波不同级系数的检索方法相比 较，结果表明，这种方法对音频数据检索的快速和有效性. 关键词：音频数据检索；局部搜索树；小波包最好基；塔型算法 中图分类号：TP391.3,TP31112文献标识码：A文章编号：1673-4785(2008)030259-06 An audio da ta retrieval method ba sed on local search trees LIYing (College ofMathematics and Computer Science,Fuzhou University,Fuzhou 350108,China) Abstract:For fast audio data retrieval,a lcal search tree (LS-k,tree)structure is proposed according o the char- acteristics ofmultmedia audio data In an LS-k tree,the zero-k crossing rate and the average magnitude of the wavelet transfom coefficients in the audio data are taken as main and secondary key codes respectively,and the other coefficients used for the index are organized in the local range On the basis of thisLS-k,tree,an audio data retrieval app roach is presented using the wavelet packet best base and the wavelet pyram idal algorithm.Finally,the research results obtained from the proposed approach are compared with those obtained using the different-k,level wavelet transfom coefficients It is found that the proposed approach is effective and fast for audio data retrieval Keywords:audio data retrieval,bcal search tree (LS-k,tree);wavelet packet best base;pyram idal algorithm 多媒体音频数据，已经成为网络、信息时代信息矩形，而非叶结点包含一组矩形.在R-te中进行插 的重要组成部分.目前，对于基于例子的音频数据分 入一个矩形操作时，遵循原则：结点包含的矩形数n 类、索引、检索、组织和管理方法，己经引起广泛的研 应满足n∈[K/21,K];当插入矩形时，必须使得 究.在文献[1中，Samet对多维数据结构与多媒体 与根结点相关的矩形所需要的扩张最少（以面积计 数据管理中的常用算法进行了全面的描述.其中包 算).当进行一个矩形的搜索操作时，从根结点开 括KDtree点4分树、MX-4分树、R-tree的插入、删 始，根据所查找矩形的坐标，递归地选择子结点，直 除、搜索和范围查询等方法.而R-tree实际上已经成 到找到叶结点为止.与此相对照，在R-tree中删除一 为目前多媒体数据组织和管理的基础，尤其，它对于 个对象，必须避免可能引起的R-tree中的结点“下 在磁盘中存储大量图像数据的情况特别有用2).R- 溢”，确保结点至少包含K2T个矩形 tree结构的大致特点是：每个R-tee有一个值为整 以R-tree为基础，衍生出来的TV-tree,主要根 数K的序.每一个非叶的R-tree结点包含一个矩形 据正被检索的数据，动态和柔性地决定怎样分支的 集合，这个集合最多有K个、至少有「K2个矩形 问题)这种数据结构多用于多媒体文档的搜索。 根结点例外).对于叶结点，每个结点包含一个实 同样衍生于R-tree的贞段树(frame segnent tree)和 R段树(R-Segnent tree or RS-tree)适用于变长度的 收稿日期：2007-1105 基金项目：福建省自然科学基金资助项目(A0510006). 分段.它常用于视频数据的搜索.近年来，又提出 通讯作者：李应.Emai让fi liying@sohu com. 了适用于各种多媒体应用场合的其他空间数据结 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 3期 智 能 系 统 学 报 Vol. 3 №. 3 2008年 6月 CAA I Transactions on Intelligent System s Jun. 2008 局部搜索的音频数据检索 李 应 (福州大学 数学与计算机科学学院 ,福建 福州 350108) 摘 要 :根据多媒体音频数据的特点 ,提出一种适用于快速音频数据检索的局部搜索数据结构 ,即局部搜索树 ( local search tree,LS2tree). 在局部搜索树中 ,分别以音频数据小波变换系数的过零率和平均幅度作为主、次关键码 ,基于局 部范围对作为索引的其他系数进行组织. 其次 ,基于局部搜索树 ,提出采用小波包最好基小波塔型算法实现音频数 据检索. 最后 ,把采用局部搜索树的小波包最好基 —小波塔型算法的搜索和基于小波不同级系数的检索方法相比 较 ,结果表明 ,这种方法对音频数据检索的快速和有效性. 关键词 :音频数据检索 ;局部搜索树 ;小波包最好基 ;塔型算法 中图分类号 : TP391. 3; TP311. 12 文献标识码 : A 文章编号 : 167324785 (2008) 0320259206 An audio data retr ieval method based on local search trees L I Ying (College ofMathematics and Computer Science, Fuzhou University, Fuzhou 350108, China) Abstract:For fast audio data retrieval, a local search tree (LS2kd tree) structure is p roposed according to the char2 acteristics of multimedia audio data. In an LS2kd tree, the zero2kd crossing rate and the average magnitude of the wavelet transform coefficients in the audio data are taken as main and secondary key codes respectively, and the other coefficients used for the index are organized in the local range. On the basis of thisLS2kd tree, an audio data retrieval app roach is p resented using the wavelet packet best base and the wavelet pyram idal algorithm. Finally, the research results obtained from the p roposed app roach are compared with those obtained using the different2kd level wavelet transform coefficients. It is found that the p roposed app roach is effective and fast for audio data retrieval. Keywords: audio data retrieval; local search tree (LS2kd tree) ; wavelet packet best base; pyram idal algorithm 收稿日期 : 2007211205. 基金项目 :福建省自然科学基金资助项目 (A0510006). 通讯作者 :李 应. E2mail: fj_liying@ sohu. com. 多媒体音频数据 ,已经成为网络、信息时代信息 的重要组成部分. 目前 ,对于基于例子的音频数据分 类、索引、检索、组织和管理方法 ,已经引起广泛的研 究. 在文献 [ 1 ]中 , Samet对多维数据结构与多媒体 数据管理中的常用算法进行了全面的描述. 其中包 括 K2D tree、点 4分树、MX24分树、R2tree的插入、删 除、搜索和范围查询等方法. 而 R2tree实际上已经成 为目前多媒体数据组织和管理的基础 ,尤其 ,它对于 在磁盘中存储大量图像数据的情况特别有用 [ 2 ] . R2 tree结构的大致特点是 :每个 R2tree有一个值为整 数 K的序. 每一个非叶的 R2tree结点包含一个矩形 集合 ,这个集合最多有 K个、至少有 「K/2 ô个矩形 (根结点例外 ). 对于叶结点 ,每个结点包含一个实 矩形 ,而非叶结点包含一组矩形. 在 R2tree中进行插 入一个矩形操作时 ,遵循原则 :结点包含的矩形数 n 应满足 n ∈ [「K/2ô, K ];当插入矩形时 ,必须使得 与根结点相关的矩形所需要的扩张最少 (以面积计 算 ). 当进行一个矩形的搜索操作时 ,从根结点开 始 ,根据所查找矩形的坐标 ,递归地选择子结点 ,直 到找到叶结点为止. 与此相对照 ,在 R2tree中删除一 个对象 ,必须避免可能引起的 R2tree中的结点“下 溢 ”,确保结点至少包含 「K /2ô个矩形. 以 R2tree为基础 ,衍生出来的 TV2tree,主要根 据正被检索的数据 ,动态和柔性地决定怎样分支的 问题 [ 3 ] . 这种数据结构多用于多媒体文档的搜索. 同样衍生于 R2tree的贞段树 ( frame segment tree)和 R2段树 (R2Segment tree or RS2tree)适用于变长度的 分段 [ 1 ] . 它常用于视频数据的搜索. 近年来 ,又提出 了适用于各种多媒体应用场合的其他空间数据结