（计算机应用技术专业论文）基于高维索引结构的视频片断检索算法研究.pdf

摘要 随着网络和多媒体技术的发展，视频信息的检索成为非常重要的研究领域。 该领域涉及诸多方面的技术，包括对关键帧的提取，视频在时间序列上的分割， 视频片断的相似度度量以及高维数据索引结构等等。本文以快速准确的实现视频 片断检索为主要研究目标，深入探讨了各类多维索引结构的特点、视频片断的相 似度度量模型以及基于不同索引结构的视频片断检索算法。 在对现有可用于视频片断检索的索引结构和检索算法进行分析以后，本文首 先提出了一种基于v a f i l e 的视频片断相似检索算法。该算法充分利用了 v a f i l e l 7 1 压缩量化近似表示原始矢量和近似矢量按原顺序排列的特点，根据我们 提出的相似度模型，有效的支持了视频片断检索。 在v a f i l e 基础上，本文又提出一种新的索引结构用于视频片断的快速检索， 称之为0 v a - - f i l e ，其主要特点是考虑v a - - f i l e 中近似矢量的插入顺序，尽量 安排高维空间中距离相近的矢量存放在顺序近似文件中相近的位置上。我们利用 o v a - f i l e 所特有的快速查找k 近邻性质，提出了一种快速的帧图像相似的判断 方法，并以此为基础提出了基于o v a - f i l e 的快速视频片断相似检索算法。为了 进步加快查询速度，我们还将排序后的近似文件o v a f i l e 分割为一定数量的 近似矢量段。当进行查询时，仅扫描部分近似矢量段，从而有效减少磁盘的1 0 代价，大大提高了检索速度。实验结果表明，该算法可有效支持高维矢量数据序 列的相似性检索，特别符合视频镜头片段的相似检索。 关键词： 视频片断检索、视频片断相似度模型、多维索引结构、，a f i l e 、 o v a - f i l e 、相似性查询 复且大学硕士学位论文 2 a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r ka n dm u l t i m e d i at e c h n i q u e s ，v i d e op r o c e s s i n g a n dr e u i e v a lh a sb e c o m ea l la c t i v er e s e a r c h f i e l d t h er e s e a r c ht a s k si n c l u d e k e y f r a m e e x t r a c t i o n ,s i m i l a r i t yc o m p u t a t i o n b e t w e e nv i d e o c l i p s a n d 1 1 i g h d i m e n s i o n a li n d e xs t r u c r k r e se t c i nt h i st h e s i s ，w ef o c u so nh o w t or e a l i z et h e v i d e oc l i pr e t r i e v a lw i t he f f i c i e n c ya n dd i s c u s ss o m er e l a t e dt e c h n i q u e s ，i n c l u d i n g h i g h d i m e n s i o n a li n d e xs t r u c t t t r e s ，s i m i l a r i t ym o d e l a b o u tv i d e oc l i p sa n ds o m ev i d e o c l i pr e t r i e v a la l g o r i t h m sb a s e d o nd i f f e r e n ti n d e xs t r u c t u r e s a f t e r a n a l y z i n g t h es t a t e - o f - a r to fe x i s t i n gi n d e x i n gs t r u c t u r ea n dr e t r i e v a l a l g o d t h m s r e l a t e dt ov i d e o e l i pr e t r i e v a l ，af a s tv i d e oc l i pr e t r i e v a la l g o d t h r n b a s e do n v a - f i l ei sp r o p o s e d 。v a - f i l er e p r e s e n t sav e c t o ra p p r o x i m a t e l yb yc o m p r e s s i n gt h e o r i g i n a ld a t aa n di t m a i n t a i n st h eo r i g i n a lo r d e rw h e nr e p r e s e n t i n gv e c t o r si na s e q u e n c e ，w h i c hi sav e r yv a l u a b l em e r i tf o rv e c t o rs e q u e n c e sm a t c h i n g i n t e g r a t e d w i t l lan e wv i d e o c l i ps i m i l a r i t ym o d e lw ep r o p o s e d t h i sa l g o r i t h mc a ns u p p o r t v i d e o c l i pr e t r i e v a lw i t he f f i c i e n c y b a s e do nv a f i l e ，an e wh i g hd i m e n s i o n a li n d e xs t r u c t u r e ，n a m e do r d e r e d v a - f i l e ( o v a - f i l e ) ，w a sp r e s e n t e di n t h i s p a p e r , w h i c hs t o r e s t h e a p p r o x i m a t e v e c t o r si n t o p r o p e r p o s i t i o n so ff i l e t h ew o r d p r o p e r m e a n st h ea p p r o x i m a t e v e c t o r sc l o s et oe a c ho t h e ri nm e t r i cs p a c e ss h o u l dh a v ec l o s ep o s i t i o n si nv e c t o r a p p r o x i m a t i o nf i l e b yu s eo f t h ei e a rn e i 【g h b o r i n gm e r i t so f o v a f i l e ，w ep r o p o s ea n e wm e t h o dt oc o m p u t et h es i m i l a r i t yb e t w e e nt w o k e y 台a l r l e sa n dt w o v i d e oc l i p s i no r d e rt os p e e du pt h e q u e r yp r o c e s s ，t h ew h o l e o r d e r e da p p r o x i m a t ev e c t o rf i l ea r e s e g m e n t e di n t om a n y c o n s e c u t i v es l i c e s ，o fw h i c ht h ec e n t e r sa n ds t a r t - e n dp o s i t i o n s a r er e c o r d e da c c o r d i n g l y o n l yas m a l ln u m b e ro fs l i c e s ，w h i c hh a v et h eh i g h e s t p r o b a b i l i t yc o n t m n i n gt h eq u e r yr e s u l t s ，h a v et ob es c a n n e d i tm e a n sg r e a tr e d u c t i o n o fd i s ki oc o s t t h i sa p p r o a c hi sb o t he v a l u a t e di n t h e o r ya n de x p e r i m e n t s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a to a rn e wa l g o r i t h mi n c r e d i b l ys h o r t e n e dt h er e t r i e v a l t i m ea n dc a nb e a p p l i e de f f e c t i v e l y t o m a n ys i m i l a r i t yr e t r i e v a l b a s e do nh i g h d i m e n s i o n a lv e c t o rs e q u e n c e s k e y w o r d s ：v i d e oc l i pr e t r i e v a l ，v i d e oc l i ps i m i l a r i t ym o d e l ，h i 曲d i m e n s i o n a l i n d e x ，v a f i l e ，o v a f i l e ，s i m i l a r i t yq u e r y 复旦大学硕士学位论文 第一章前言 随着高速传输和高效存储技术的发展，大量信息以计算机可读的形式存在， 其中不仅包括文字和声音，更主要的是图形、图像和视频等多媒体视觉信息。只 有对这些信息进行有效的组织以便于人们快速地浏览和检索，才能更好的对它们 加以利用。为了实现对海量多媒体信息的高效访问，多媒体信息检索工具的研制 成为当务之急，其中高效的索引结构是研究的重点。 对于多媒体信息，我们采取特征提取的方法将其映射为特征数据，然后将这 些特征数据库保存在多媒体数据库中。一般而言，这些数据的维数较高，传统的 索引结构如b t r e e 等无法对其进行有效的组织和管理，因此多维索引结构在这种 情况下应运而生。在近三十年对多维数据索引的研究过程中，已经提出了大量的 索引结构和相应的检索算法，如r - t r e e 【5 j 、x - t r e e p 】、v a - f i l e t ”等等。 视频信息检索是多媒体信息检索中最困难的研究课题之一，也是目前学术界 的研究热点，利用图像和视频片断的底层物理特征实现视频片断检索是一个非常 重要的研究方向，其基本步骤为：首先将视频数据库中的视频流划分为镜头，并 从每个镜头中提取一个或多个关键帧，然后从每个关键帧中提取特征矢量，用特 征矢量表征所对应的镜头。在检索时对用户提交的查询视频作同样的处理。然后 利用特征矢量进行视频片断之间相似度的计算实现相似性查询。根据用户提交的 查询需求的不同，视频检索又可以大致分成两类：视频镜头检索和视频片断检索。 镜头检索指用户提交的查询视频片断仅包含一个镜头，可利用该镜头所对应的关 键帧的特征矢量实现快速的相似性检索，针对这一类检索方式，人们已经提出了 大量的高维索引结构和相似性查询算法，! t l r - t r e e 、x - t r e e 和v a f i l e 等。视频片 断检索则是指用户提交的查询视频可能由多个连续的镜头组成的描述同一语义 的一段视频，对于这一类查询，首先需要对查询视频进行镜头分割，利用每个镜 头的关键帧所对应的特征矢量组成的具有一定时间顺序的特征矢量序列来表征 用户的查询需求。度量两个视频片断之间的相似度往往基于各个关键帧特征矢量 之间的相似性【5 ”，如果不采用高效索引结构和快速检索算法，直接在原始数据 库上进行检索将花费高昂代价。 而在过去的研究中，人们提出的绝大多数多维索引结构( r t r e e 、r + t r e e 、 x t r e e 、s s - t r e e l l “、s r - t r e e 【”j 、v a f i l e 等等) 以及相似性检索算法，它们所考 虑的查询仅仅用于单个多维矢量的查询，也就是说只支持镜头检索，而不支持查 询对象为特征矢量序列的多镜头视频片断的检索。为了有效支持视频片断的检 索，必须在这些索引结构的基础上加以改进。 本文以快速准确实现视频片断检索为研究目标，以如何将多维索引结构引入 复旦大学硕士学位论文 视频片断检索为研究主线，结合自己的研究工作，重点介绍了各类多维索引结构 的特点、视频片断检索的基本知识和特点、基于不同索引结构的视频片断检索算 法和算法之间的性能比较。 论文第二章着重介绍多维索引结构研究的发展现状，并以度量空间和向量空 间的划分对众多的索引结构进行分类，同时介绍了其中有代表性的索引结构；第 三章介绍视频片断检索的研究现状，并重点介绍了一种引入多维索引结构的视频 片断检索算法和相似度模型；第四章介绍作者提出的一种基于v a f i l e 的视频片 断检索算法和相应的相似度模型，该算法利用v a - f i l e 对数据的量化压缩和近似 矢量按照多维数据库中矢量原始顺序排列的特点，有效的提高了视频片断检索的 性能；第五章则在v a f i l e 基础上，提出了一种新的索引结构用于视频片断的快 速检索，称之为o v a - - f i l e ，该算法的特点是检索速度快，并且能够自适应的调 整视频片断之间的相似度。实验结果证明，该算法极大地减少了视频片断相似查 询时磁盘访问代价和c p u 计算代价，具有很高的查询效率和查询精度，可以应用 在成熟的多媒体信息检索系统中实现实时的视频片断检索；本文的最后一章则 对所进行的研究工作进行了总结和展望。 复旦大学硕士学位论文 第二章多维索引结构研究现状 近年来，多维数据库的应用得到快速的发展，如海量的多媒体数据库、大规 模的文本数据以及生物信息学中庞大的d n a 数据库等，这些信息一般使用特征抽 取等方法映射为多维数据，然后通过计算这些多维数据之间距离实现相似性查 询。例如，对于图像数据，往往采用颜色直方图来表征一幅图像，当需要从数据 集查找与给定图像相似的图像时，通过计算颜色直方图之间的距离实现查询。在 这种背景之下，多维数据索引结构和适用于多维索引结构的近似查询算法得到了 人们的极大重视，而在已提出的众多多维索引结构中，有的特定工作在向量空间 中，而有的是针对度量空间而设计。在本章我们将对多维索引结构研究的现状进 行较为详细的介绍，包括：多维数据及多维索引结构的特点、多维数据库的查询 方式、向量空间与度量空间中多维索引结构的异同及它们中有代表性的索引结 构。 2 1 多维数据及多维数据索引结构的特点 所谓多维数据，是指多维空间中的数据，例如二维空间中的点、线段、矩形， 三维空间的球、立方体以及高维空间中的点数据等。一般来说，多维数据有以下 一些特点 1 4 l ： 1 ) 复杂的结构：对于多维数据，它有可能是一个多维空间的点数据，也有可 能是复杂的多边形或多面体，一般不能象传统的关系型数据库一样用固定 大小的条目来保存。 2 ) 动态的特性：在插入和删除的过程中，还往往伴随着对数据本身的修改。 3 ) 数据的海量：多维数据库往往是比较大的，例如，一般的地图大概需要几 千兆字节的存储空间。 4 ) 多样化的操作：对多维数据库而言，没有标准操作，往往要根据实际应用 的需要确定。 5 ) 时间代价大：尽管对多维数据库的操作所花费的时间各不相同，但一般远 高于传统的关系型数据库的操作。 6 ) 不能排序：无法对空间数据进行线形排序以使得那些在多维空间中相邻的 数据仍然能够相邻。 正是由于多维数据具有以上各种特点，所以要求索引结构也相应具有以下 复且大学硕士学位论文 些特征： 1 ) 动态构造：由于数据可以在数据库以任意顺序插入或删除，其索引也应该 与之保持一致，即索引结构也必须支持动态的插入和删除。 2 ) 二级三级存储管理：尽管主存容量日益增大，仍不能将一个完整的数据 库保存在主存中，因此索引结构要充分考虑到二级以及三级的存储管理。 3 ) 支持尽量多的操作：不能以牺牲其它的操作而支持某一种特定的操作。 4 ) 独立于输入数据及插入顺序：支持各种多维数据以及任意的插入顺序。 5 ) 可增长性：索引结构要能够适应数据库大小的增长。 6 ) 时间的有效性：查找速度必须是快速的。 7 ) 空间的有效性：一个索引结构相对于其原数据应是比较小的，要保证一定 的空间利用率。 8 ) 并行性及可恢复性。 2 2 多维数据库的查询方式 根据应用领域的不同，多维数据库的查询方式也各不相同。对于给定的数据 库d b ，常用的查询方式有【1 4 i ： 1 ) 精确匹配查询( e m q ：e x a c tm a t c hq u e r y ) ：对于给定的查询数据q ，从d b 中找出所有与q 相同的数据： e m q ( q ) = 0 d bj 0 = 种。 2 ) 点查询( p q ：p o i n tq u e r y ) ：给定点数据q ，从数据库中找出所有包含点q 的数据： p q ( q ) = o d b q n 0 = g 。 3 ) 窗口查询( w q ：w i n d o wq u e r y ) ：给定一个d 维的矩形查询区间 ，“= 1 z , u 1 。【，：，“： 。 1 u u a 】，从数据库中找出至少包含一个i 中的点的所 有数据： w q ( i 。) = 扣d 曰1 1 4 n d 妒) 4 ) 相交查询( i q ：i n t e r s e c t i o n q u e r y ) ：给定具有一定形状的空间数据q ，从 数据库中找出至少包含q 中一点的所有数据： 复旦大学硕士学位论文 - 7 - 坦( q ) = 0 d b l q n o 以a 5 ) 包含查询( e q ：e n c l o s u r eq u e r y ) ：给定查询数据q ，从数据库中找出所有 包含q 的数据： e 9 ( 9 ) = d d b i q n d = g ) 。 6 ) 被包含查询( c q ：c o n t a i n m e n tq u e r y ) ：给定查询数据q ，从数据库中找出 所有被q 包含的数据： c q ( q ) = o d b l q n d = o 。 7 ) 邻接查询( a q ：a d j a c e n c yq u e r y ) ：给定查询数据q ，从数据库中找出所有 同q 邻接的数据： a q ( q ) = 0 d b l q n o a g n o = 以 其中q 、o 分别表示q 和o 的内部区域。 8 ) 范围查询( r q ：r a n g eq u e r y ) ：给定查询数据q 与查询距离门限t ，从数据 库中找出所有与q 距离小于t 的数据： 8 q ( q ，丁) = d e d b 1 i o - q l l z a 9 ) k - 近邻查询( 1 ( n n q ：kn e a r e s t n e i g h b o rq u e r y ) ：给定查询数据q 及正整数 k ，从数据库中找出距离q 最近的k 个数据： k n n q ( q ，的= d 。d 。e d b i v e e d b o 。o 。一。 ，i i o ，- q 1 0 ，定义孵= w ，d ( w ，p ) = 0 ，即w i 为距离根节点为i 的所有点的集合。对于每一个非空的胛，循环为其建立b k t r e e ，直到剩余元素 数目小于一个预定义的阈值b 时停止，其中每一个被选择为子树根节点的元素称 为支点( p i v o t ) 。图2 1 0 就是一个b k t r e e 的简单例子，它反映了b k i r e e 的特 复旦大学硬士学位论文 点。 当给定一个查询q 和范围r 时，b k - t r e e 的查询算法是从根节点出发，找出 所有满足不等式d ( p ，q ) 一r f d ( p ，q ) + ，的子节点i ，递归直至到叶子节 点。对路径上所有的支点和叶子节点中的每一个元素都要与q 进行比较是否满足 不等式d ( q ，“) ，记录下所有满足不等式的点作为结果返回。在查询中，三 角不等式性质保证了所有满足查询条件的点均会被检索到。 a 纠心 fc bghde 图2 1 0 ：简单的b k - t r e e ，左边是原始数据，右边是b k t r e e 的第一层 2 5 212 b k - t r e e 类的其它几种索引结构 在b k - t r e e 提出之后，人们对它的结构进行了各种改进，以期得到更好的性 能，下面列出主要的几种： f q t r e e ( f i x e d q u e r i e st r e e ) p 】：f q t r e e 对b k t r e e 做出的改进主 要体现在两点：第一，数据库中的所有数据都是存放叶子节点上，在非 叶子节点中存放的可能是数据库中的数据，也可能是其它的关键字；第 二，位于同一高度上的所有中间节点存放的都是同一个关键字，这是 f q t r e e 最新颖的地方。由于同一层的中间节点所对应的是同一个关键 字，因此在检索时可以减少距离比较的次数，但是同时也会增加遍历的 节点数，即树的高度会增加。图2 1 l 是一个简单f q t r e e 的例子。 复旦大学硕士学位论文 q 1 = 1 0 1 0 q 2 = 1 1 0 1 图2 11 ：使用h a m m i n g 距离定义的f q t r e e ， f h q - t r e e ( f i x e d h e i g h tf q t ) 【2 7 1 ： 叶子节点所包含数据的最大数目为2 f q t r e e 在f q t r e e 的基础上又做 出了改进，即强行规定所有的叶子节点都必须在同一高度上。这样在进 行查询时对于同一层的节点可以统一考虑，而不必再分为叶子节点和中 间节点两种情况考虑。其代价为某些叶子节点不得不增加高度以满足这 一条件。图2 1 2 是f h q - t r e e 的一个例子。 图2 1 2 ：f h q t r e e f q a r r a y ( f i x e d q u e r i e sa r r a y ) 瞰j ：f q a r r a y 是一种数组查询结构， 其实质是对f h q - t r e e 的一种压缩存储格式。它的构成是将棵已有的 f h q t r e e 的叶子节点从左到右依次存放入数组的每一个元素，并且记录 下从根节点至叶子节点所历经的所有边的权值。利用f q a r r a y 进行查找 时实际是进行二分查找，相比较f h q t r e e 而言，需要多花0 ( 1 0 9n ) 的时间，但是并没有增加距离函数的计算次数。图2 1 3 是f q - a r r a y 的 个例子。 l l l l l0 0 l l0 1 l o0 1 1 1 0 0 0 10 l o o 0 1 0 1 2 223 3 34 1 222 22 2 图2 1 3 ：f q - a r r a y 复旦大学硕士学位论文 2 0 2 5 2 2b s t r e e 类 b s t r e e 类的索引结构不仅可用于离散的距离函数，也适用于连续的距离函 数，比b k t r e e 类的索引结构有更广泛的适用范围。 2 5 2 2 1b s t r e e 【3 8 i b s t r e e ( b i s e c t o rt r e e s ) 是b s t r e e 类中最早被提出的索引结构，它是 一棵二叉查找树。其构造方法为：从根节点出发，为每一节点选择两个中心数据 点c 1 和c 2 ，依照距离中心点c l 和巳谁更近的原则，依次将剩余元素分别放入节 点的左右子树中；为每一个中心点记录下它的覆盖半径，即在它的子树中离它最 远元素的距离。b s t r e e 的查找过程很简单，在每一层上对于中心点c ，如果 a ( q ，c i ) 一，小于c i 的覆盖半径，则进入c ，对应的子树进行查找，否则删除这一 分支。图2 1 4 给出了b s - t r e e 的一个例子。 2 5 2 2 2 其他几种b s t r e e 类的索引结构 v t ( v o r o n o it r e e ) p 吲：具有和b s t r e e 类似的结构，改进之处在于当 必须生成一个新的节点以容纳新插入的一个元素时，不仅把新插入的元 素放入该新节点中，而且把它父节点中所包含距离最近的元素也放入该 节点。实验证明它比b s t r e e 具有更高的查询效率和更好的平衡性。 g h t ( g e n e r a l i z e d h y p e r p l a n et r e e ) 】：在构造上与b s - t r e e 完全类 似，不同之处在于查询时不是使用中心点的覆盖半径而是两个中心点之 问的超平面来选择分支：如果a ( q ，c 1 ) 一， m ，则进入p 的右子树； 类似于b s - t r e e ，我们同样可能会查找它的所有分支。 构造v p - t r e e 的空间复杂度为0 ( 1 0 9n ) ，时间复杂度为0 ( nl o gn ) ，在 查询半径很小的条件下查询问复杂度为0 ( 1 0 9n ) 。图2 1 5 就是一个v p t r e e 的例子。 2 5 2 3 2 其它几种y p - t r e e 类的索引结构 m v p - t r e e ( m u l t i v a n t a g e p o i n tt r e e ) 【2 9 l ：m v p t r e e 对v p t r e e 的结 构做了少许改变。它将中间节点所包含元素( v a n t a g ep o i n t ) 的数目由 v p t r e e 的一个增加到两个，其中每个元素的划分份数为m ，这样提高了 每个节点的输出能力，降低了树的高度，从而减少了距离函数的计算次 数。在 4 0 中指出，构造一棵m v p t r e e 所需要的距离函数的计算次数为 o ( n l o g 。n ) ，比v p t r e e 少了l 0 9 2n ，并且查询性能上也有了很大的提 高。 复旦大学磺士学位论文 一2 2 - 一、 b b 6 ； 、羔， 0 哕弋1 b 乱3 弋，7 2 。 图2 1 5 ：选择元素1 为根节点的v p - t r e e v p f ( v a n t a g ep o i n tf o r e s t ) 【柏】：v p f 是v p t r e e 的又一个变种，它基 于v p - t r e e 的一个缺点做出改进：在v p t r e e 中，当一个查询点距离支 点很近的时候，将不得不分别进入支点的左右子树进行查询。因此v p f 的主要思想是在树的每一层上，将所有距离支点适中的元素独立的选取 出来，并用这些元素构造第二棵树，以此类推得到有多棵树构成的索引 结构。这里“适中”的具体定义为：设和分别代表距离支点最近和 最远的元素到支点的距离，如果距离m 满足 d ( p ，r o ) + j m d ( p ，) 一占，则m 被认为是适中的距离。当在进行范 围查询时，如果查询半径r ( 一r 0 2 6 ) 2 ，则避免了回溯，否则就 不得不搜索所有的树。在 4 7 中指出，在v p f 上进行查询时所需要的距 离函数计算次数为o ( n 。，l o g n ) ，其中p 依赖于查询半径，+ ，并满足 o p 跏i ( d ，d ”) 。 4 2 基于v a - f il e 的视频片断检索算法 4 2 iv a f i l e 的构造 对视频数据库中提取出的关键帧特征矢量构造v a f i l e ，实质上是近似量化 这些高维矢量并将量化以后的数据按原顺序排列存储，其详细构造过程可参考第 二章中对v a f i l e 的介绍。 在量化以后，根据视频数据库= 磊，蟊五。) 可以得到数据库的 v a f i l e 索引文件v = v o ，再一1 。 复旦大学硕士学位论文 4 2 2 查询矢量序列与近似矢量序列之间的相似度度量 在经过v a - f i l e 量化以后，根据v a f i l e 中的近似矢量已经无法精确计算两 个原矢量之间的距离，因此对于两段近似矢量序列，也无法根据公式( 4 2 ) 精 确计算原矢量序列之间的相似度，而只能估算它们之间相似度的上下界。 4 2 2 1 查询矢量与近似矢量之间的相似度度量 对于单个查询矢量香和v a - f i l e 中的近似矢量t ，我们可以定义它们之间的 最大相似度u 。( 牙，巧) 和最小相似度t 。( 玩，矿，) 如下： 蹦弛。雨丽1 4 。3 三“m 覃”9 ，2i ；j ；蒜 4 _ 4 j d 坫。( 磊，巧) 和d 西。( 或，t ) 分别表示查询矢量磊和口，所代表精确矢量孑，之间 的最小可能距离和最大可能距离，即d i s 。( 荦。，巧) 兰d 括( 牙。，弓) d 妇一( 口，q ) ， 如图4 1 所示。 1 1 1 0 0 1 0 0 d a t as p a c e i 。 d 吣8 n d i s 图4 1 ：查询矢量或和数据矢量t 距离的上下界 可以形式化的给出虿和孑之间上下界距离的计算公式：d i s 。为最小距 离，d i s 一为最大距离，f 为第i 维空间上第，个区间的起始刻度，口( 孑，- ，) 表示 点孑在第_ ，维上所在区间的序号，则： 复旦大学硕士学位论文 一3 6 d i s 。= ( z 。) 9 ) “9 d i s 。= ( 2 。( 。) 9 ) ”9 q i i 娟i m ， = o ， k 羽一g ， a q ，n 娟，穷 ，u ，= i m a x ( 日j t j , 。( 玉d ，t j ，d j j ) “ 她d 碳磊d - q j ) ， “z d = 讲i ，) ( 4 6 ) f ，羽，刖一留j ，日，嘶，d 4 2 2 2 查询矢量序列与近似矢量序列之间的相似度度量 在公式( 4 5 ) ( 4 6 ) 的基础上，我们给出了计算查询矢量序列与近似矢量序 列之间相似度公式。设对于查询矢量序列q = 磊，磊，辱_ 一。 和v r a _ f i l e 中的一 段近似矢量序列= v o ，v t 只。) ，根据公式( 4 - 2 ) 它们之间的最大相似度 s i m 一( q ，玩，) 和最小相似度曲 。( q ，p o ) 定义如下： u 。( 口，)， s i m 一( q ，) = m 埘世= 一) + _ 二一 1 m l + a + 芝k 一工r 1 k ( 玩，巳) s i m m ( q 吒。) = m i n ( 型l m + 口+ 兰 ( 4 7 ) ) + 忑 _ 杪詈 ( 4 8 ) 1 + 口，i j ，一九。一1 1 ” 4 2 3 基于v a f i l e 的k 近邻检索算法 假设视频数据库= 磊，乏一a n 一。) ，数据库的v a f i l e 索引文件 矿= ( 瓦，e 巩，) ，提交查询o = 吼，玩，哥。) ，允许结果的最大长度( 关键 帧数目) 为三，返回结果集大小为k ，当前k 近邻相似度肋”，。等于0 ，检索 算法可大致分为近似过滤和精确查询两个过程，具体描述如下： ( 近似过滤阶段* ) 1 ) 将索引文件v 的指针v p t r 定位至v 的起始位置v p t r = 0 ，近似结果集 五= 中； 复旦大学硕士学位论文 3 7 - 2 ) 将由v p t r 开始的个向量读入：p o2 ，“”矿w 一 ： 3 ) 根据公式( 9 ) 计算q 和。之间最大相似度，蜘( 9 ) ，如果 肋竹。( q ，k 。) 大于当前k 近邻相似度跏。耐，转( 4 ) ；否则转( 6 ) ； 4 ) 如果r 中所有矢量序列和都没有重叠，那么置。2r 帅+ ；否则比较l 。中与p o 有重叠的矢量序列与查询q 和。与查 询q 之间的最大相似度，r ，。中只保留它们之中相似度最大的矢量序列； 5 ) 如果五。中包含了，根据公式( 1 0 ) 计算q 和。之间最小相似度 s i r e m ( q ，) ，果s i m u ( q ，) 大于当前k 近邻相似度s 拥。且 矗。，中的元素个数大于k ，5 锄删= 砌”。( q ，f ) ：如果尺m ，中的元素 个数等于k 。s i m ，。础等于r ，所有元素的聊的最小值； 6 ) 将v p t r 定位至下一次检索开始位置：v p t r = v p t r + 1 ，如果v p t r 距离文 件结束位置小于三，转( 7 ) ；否则转( 2 ) ； ( + 精确查询阶段) 7 ) 从数据库d 中读取丑。中的所有原始矢量数据，根据公式( 4 ) 计算与 查询q 的精确相似度，返回相似度最大的前k 个结果a 从上述算法中可以看出，近似过滤阶段，算法将扫描v a f i l e ，通过计算查询 矢量序列与近似矢量序列之间的相似度上界和下界，过滤出候选视频序列凡。， 然后对r 。中的候选序列读出原始特征矢量计算精确相似度，得出精确的k 近 邻查询结果。由于扫描v a - f i l e 的代价远小于顺序扫描原始矢量的代价，如果近 似过滤阶段得到的候选集中的序列数量较少时，其查询效率必然高于顺序扫描算 法。 4 2 4 基于v a f i l e 的近似k 近邻检索 从基于v a f i l e 的k 近邻检索算法可以看出，其查询过程由近似过滤和精确 查询两个阶段组成，对于精确查询阶段，如果过滤阶段得到的候选集比较大，仍 需花费大量的时问读取原始数据进行精确相似度计算。而对于视频检索应用，相 似性检索本身就是一种“近似”的查询，并不一定要求得到精确的k 近邻，根 复旦大学硕士学位论文 - 3 8 - 据这一思想，我们对上面的算法加以修改，给出基于v a f i l e 的视频片断近似k 近邻检索算法：对近似过滤阶段得到的结果，不进行精确查询，