第3期 李应：基于局部搜索的音频数据检索方法 ·263· 文件范围缩小.也就是说，在经过小波包最佳树结构 系数和小波塔型算法检索之前，首先通过LS-tree进 占用时间比= 该层检索所用单位时间 行搜索，只对这个搜索的结果文件进行小波包最佳 4级小波系数检索所用单位时间 树结构系数的分类」 经过小波包最佳树结构系数的分类，如果只把 表2基于LS-tr©e的小波最佳树塔型算法和不同级小波 塔型算法的第一层检索作为结果，即把查询数据与 系数检索的结果 音频数据的6级小波系数进行比较作检索结果.那 Table 2 Search result w ith wavelet packet best ba se py- ram idal a lgorithm base on LS-tree and different 么要分辩出100个音频数据文件，需要2582次查 level coeff ic ien ts 询数据和音频数据6级小波系数的比较.如果以这 错误文件 数量搜索次数 层比较作为查询结果，那么查询的准确率为71% 如果在第1层检索结果的基础上，再进入第2 第1层 6,9,10,12,13,25,26, 27,37,38,43,45,46,51 层，把塔型算法的第2层检索作为结果，即把查询数 最好基 52,56,59,62,63,66,74, 29 2582 据与音频数据的5级小波系数进行比较作检索结 塔型算法 80,85,87,89,90,94,95 果.在我们的实验中，需要519次查询数据和音频 100 数据5级小波系数的比较.由于5级小波系数的长 2,7,10,12,13,25,26, 度是6级小波的一倍，因此，如果以6级小波比较的 6级 27,34,37,38,45,46,51, 时间衡量，那么增加的比较次数为5192=1038 小波系数 52,56,59,62,63,66,69. 31 10000 次.此时查询的准确率可以达到84%. 74,79,80,85,87,89,90, 与第2层相似，如果再进入第3层比较，在第2 94,95,100 层的基础上需要增加257次查询数据和音频数据的 第2层 2,6,9,12,29,31,34. 4级小波系数比较.这相当于增加2574=1028次 最好基 37,43,51,52,56,66,80, 16 1038 的6级小波系数比较的时间.经过第3层的搜索，准 塔型算法 90,100 确率可以达到94%. 2,12,14,15,18,29,31 3.2不同方法的比较 5级 34,35,37,53,56,63,72 21 20000 对同样的100个音频数据文件用【161中的不同 小波系数 80,88,89,90,92,99,100 级小波系数检索方法进行检索.当用6级粗分辨逼 近小波系数对音频数据集合中的数据进行搜索、并 第3层 6,9,43,52,66,88 把该结果作为最终的搜索结果时，搜索准确率为 最好基 6 1028 69%,并需要进行100Ⅺ100=10000次6级粗分辨 塔型算法 逼近小波系数的相关计算；用5级粗分辨逼近小波 4级 12,13,14,15,21,46,56, 1040000 系数对音频数据集合中的数据进行检索，则准确率 小波系数72,83,90 为79%，需要进行相当于100×1002=20000次6 级粗分辨逼近小波系数的相关计算；用4级粗分辨 从表2和图6(a)中可以看出基于LS-tree的 逼近小波系数对音频数据集合中的数据进行搜索， 最好基塔型算法检索音频数据的有效性，而且，随 准确率为89%，需要进行相当于100×100×4= 着搜索塔型层数的增加，精度也逐渐提高.其检索精 40000次6级粗分辨逼近小波系数的相关计算. 度明显高于不同级小波系数方法.不管用几层塔型 基于LS-tee组织和管理索引系数、用小波包最 算法，从表2和图6(b)可以看出，它所占用的时间 佳树塔型算法的方法和不同级小波粗分辨逼近小 都远低于多级小波系数的方法，而且，随着塔型层数 波系数方法比较结果如表2所示 的增加和搜索精度的提高，花费时间的增加相对较 图6显示了基于LS-tee的最好基塔型算法和 低.也就是说，在需要进行高精度搜索时，基于L$ 不同级小波系数搜索时的检索精度及其花费的时间 tree的最好基塔型算法花费的时间远低于不同级 比率.其中： 小波粗分辨系数搜索算法.在一般情况下，这种方法 可以满足音频数据基于例子的搜索对精度和时间的 检索精度= 检索到的正确文件数 检索文件总数 要求 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net文件范围缩小. 也就是说 ,在经过小波包最佳树结构 系数和小波塔型算法检索之前 ,首先通过 LS2tree进 行搜索 ,只对这个搜索的结果文件进行小波包最佳 树结构系数的分类. 经过小波包最佳树结构系数的分类 ,如果只把 塔型算法的第一层检索作为结果 ,即把查询数据与 音频数据的 6级小波系数进行比较作检索结果. 那 么要分辩出 100个音频数据文件 ,需要 2 582次查 询数据和音频数据 6级小波系数的比较. 如果以这 层比较作为查询结果 ,那么查询的准确率为 71%. 如果在第 1层检索结果的基础上 ,再进入第 2 层 ,把塔型算法的第 2层检索作为结果 ,即把查询数 据与音频数据的 5级小波系数进行比较作检索结 果. 在我们的实验中 ,需要 519次查询数据和音频 数据 5级小波系数的比较. 由于 5级小波系数的长 度是 6级小波的一倍 ,因此 ,如果以 6级小波比较的 时间衡量 ,那么增加的比较次数为 519 ×2 = 1 038 次. 此时查询的准确率可以达到 84%. 与第 2层相似 ,如果再进入第 3层比较 ,在第 2 层的基础上需要增加 257次查询数据和音频数据的 4级小波系数比较. 这相当于增加 257 ×4 = 1 028次 的 6级小波系数比较的时间. 经过第 3层的搜索 ,准 确率可以达到 94%. 3. 2 不同方法的比较 对同样的 100个音频数据文件用 [ 16 ]中的不同 级小波系数检索方法进行检索. 当用 6级粗分辨逼 近小波系数对音频数据集合中的数据进行搜索、并 把该结果作为最终的搜索结果时 ,搜索准确率为 69% ,并需要进行 100 ×100 = 10 000次 6级粗分辨 逼近小波系数的相关计算 ;用 5级粗分辨逼近小波 系数对音频数据集合中的数据进行检索 ,则准确率 为 79% ,需要进行相当于 100 ×100 ×2 = 20 000次 6 级粗分辨逼近小波系数的相关计算 ;用 4级粗分辨 逼近小波系数对音频数据集合中的数据进行搜索 , 准确率为 89% ,需要进行相当于 100 ×100 ×4 = 40 000次 6级粗分辨逼近小波系数的相关计算. 基于 LS2tree组织和管理索引系数、用小波包最 佳树 —塔型算法的方法和不同级小波粗分辨逼近小 波系数方法比较结果如表 2所示. 图 6显示了基于 LS2tree的最好基 2塔型算法和 不同级小波系数搜索时的检索精度及其花费的时间 比率. 其中 : 检索精度 = 检索到的正确文件数 检索文件总数 , 占用时间比 = 该层检索所用单位时间 4级小波系数检索所用单位时间 . 表 2 基于 LS2tree的小波最佳树 —塔型算法和不同级小波 系数检索的结果 Table 2 Search result with wavelet packet best ba se & py2 ram ida l a lgor ithm ba se on LS2tree and d ifferen t level coeffic ien ts 错误文件 数量 搜索次数 第 1层 最好基 塔型算法 6, 9, 10, 12, 13, 25, 26, 27, 37, 38, 43, 45, 46, 51, 52, 56, 59, 62, 63, 66, 74, 80, 85, 87, 89, 90, 94, 95, 100 29 2 582 6级 小波系数 2, 7, 10, 12, 13, 25, 26, 27, 34, 37, 38, 45, 46, 51, 52, 56, 59, 62, 63, 66, 69, 74, 79, 80, 85, 87, 89, 90, 94, 95, 100 31 10 000 第 2层 最好基 塔型算法 2, 6, 9, 12, 29, 31, 34, 37, 43, 51, 52, 56, 66, 80, 90, 100 16 1 038 5级 小波系数 2, 12, 14, 15, 18, 29, 31, 34, 35, 37, 53, 56, 63, 72, 80, 88, 89, 90, 92, 99, 100 21 20 000 第 3层 最好基 塔型算法 6, 9, 43, 52, 66, 88 6 1 028 4级 小波系数 12, 13, 14, 15, 21, 46, 56, 72, 83, 90 10 40 000 从表 2和图 6 ( a) 中可以看出基于 LS2tree的 最好基 2塔型算法检索音频数据的有效性 ,而且 ,随 着搜索塔型层数的增加 ,精度也逐渐提高. 其检索精 度明显高于不同级小波系数方法. 不管用几层塔型 算法 ,从表 2和图 6 ( b)可以看出 ,它所占用的时间 都远低于多级小波系数的方法 ,而且 ,随着塔型层数 的增加和搜索精度的提高 ,花费时间的增加相对较 低. 也就是说 ,在需要进行高精度搜索时 ,基于 LS2 tree的最好基 2塔型算法花费的时间远低于不同级 小波粗分辨系数搜索算法. 在一般情况下 ,这种方法 可以满足音频数据基于例子的搜索对精度和时间的 要求. 第 3期 李 应 :基于局部搜索的音频数据检索方法 ·263·