多媒体检索使用时间序列表示.doc

多媒体检索使用时间序列表示 及相关反馈 Chotirat安Ratanamahatana1和Eamonn Keogh2 一系计算机工程，朱拉隆功大学，泰国曼谷10330 anncp.eng.chula.ac.th 二系计算机科学与工程，大学。美国加州河滨，加州92521美国 抽象。多媒体数据是无处不在，几乎涉及各个方面 我们的生活。同样，世界的大部分数据是一系列的形式，时间， 作为将显示，如视频，图像和数据，还有许多其他类型 手写输入，可以转化为时间序列。这一事实引发巨大 在时间关系在数据库和数据挖掘社区系列检索。 然而，这项工作的效率和可扩展性大大缩小了重点 以牺牲可用性和效益。在这项工作中，我们探索公用事业 多媒体的数据转换成一个更简单的一维 时间序列的代表性。有了这个时间序列数据，我们可以利用的能力 动态时间弯曲，这更准确的检索结果。 我们也可以使用一个总体框架，学习与任意一个距离度量 限制的前提下计算的动态时间弯曲变形路径 为分类和查询检索任务。此外，装有 相关反馈制度和查询检索任务细化到可以进一步 提高精度/召回在很大程度上。 1简介 一个时间序列数据库可以被定义为任何数据库序列的组成 命令的事件，有或没有具体的时间概念。有了这个定义，一些 对多媒体数据或较少直观域可以转化为一个或 二维时间序列数据。对时间序列检索以前的大部分工作 利用相似性度量作为欧氏距离，因为它是非常适合进行 索引1，2。然而，越来越多的证据表明，欧氏度量的 在时间敏感轴偏差使得它不适合大多数现实世界 问题。在这项工作中，我们提出一个基于众所周知的距离测度 动态时间规整（大田），并显示其与全面的实验工具。 虽然它的潜在的弱点，这需要一些训练，以实现其 优异的业绩，我们可以利用相关反馈技术来达到这一目的。 2时间表示数据的多媒体系列 我们希望扩大读者的时间序列数据的普及表示赞赏。我们 会考虑一些不那么明显的应用程序，可以受益于高效率和有效 多媒体检索使用时间序列表示与相关反馈401 视频检索。视频检索是多媒体最重要领域之一 数据库管理系统。一般而言，研究基于内容的视频检索 代表作为一个框架集视频内容，而忽略了时空特征 在拍摄的帧。然而，对于一些领域，包括动作捕捉 编辑，步态分析，视频监控，它可能是卓有成效的，以提取时间序列 从视频和指数只是时间序列的指针回（原 视频）。图。 1显示了一个时间序列转换成一个视频序列的例子 跟踪右手（我们感兴趣的对象重心）均X和Yaxes。 0 10 20 30 40 50 60 70 80 90 针对枪 手走向 肩平 抓枪 移动手 上述皮套 手在休息 图。 1。从剧照 视频序列;权利 手追踪， 转换成时间 系列（只有X轴的值 列在这里） 为什么有使用时间序列的代表性可能会更好一些原因 比原来的视频序列数据。其中一个明显的一点是，大量 减少维度，从而提高了存储，传输，分析缓和， 和索引。此外，它更容易使时间序列的代表性 不变的扭曲的数据，如时间尺度和时间弯曲。 图像检索。图像检索已成为日益重要的informationbased 社区。大型分布式集合科学，艺术，技术， 和商业形象已成为越来越普遍，因此需要更复杂 而精确的方法来执行或语义相似度的查询。对于一些 专门领域，它可以转换成有用的“伪时间序列的图像。”对于 例如，考虑图。 2，一个枫叶图像转换成一个时间序列 跟踪测量其周长（边缘局部角度）。在这样一个转换工具 类似的视频检索这一点;在时域的工作也使得 规模，偏移和旋转不变性微不足道的处理。一个不同的图像大小（缩放 /退出）也是微不足道的插值处理时间序列的长度相同。 图。 2。许多图像索引/分类 任务可以更有效地解决 后改建为“伪时间序列的形象” 手写检索。虽然在线手写识别4，可 基本上被视为解决问题，他们的转换和索引存在的问题 历史档案仍然是一个挑战。历史的索引问题 档案是困难的，因为不像线上手写的问题，有没有笔402 C.A. Ratanamahatana和E.基奥 此外，该档案可能会下降或染色，而人类学会适应 他们的笔迹进行网上手写识别更加容易，档案笔迹 往往是高度风格化的，只有与被清晰的作家书面意向。 许多脱机手写笔的图像处理算法，最近已 建议在认字和索引5的兴趣。虽然笔迹 不是一个时间序列，存在几种技术转换手写时间序列; 这些变化很多是由Manmatha和学生率先6，作为 如图3所示。最近的工作表明这种表示仍可能使高 精密索引历史档案，同时简化问题，从2 - 1 - 维域6。 甲） 乙） 三） 甲） 丁） 0 50 100 150 200 250 300 350 400 450 0 0.5 一 图。 3。甲）乔治华盛顿 手写 文本。 B）一个放大式上 单词“亚历山大”。 丙）甲投影轮廓。 四）上下 配置文件。 3 Ratanamahatana -基奥乐队（的R - K波段） 尽管在爆炸时的兴趣在过去十年系列索引中，大部分 工作的重点是欧氏距离，假定线性 映射之间的查询和候选人的时间序列。然而，最近工作 已经证明，这种相似性模型通常并不好很多 现实世界的问题，凡在时间轴变异是始终存在。此问题 在时间的扭曲轴可以解决动态时间弯曲 （DTW的）7。这种方法允许两个时间序列之间的非直线 容纳序列相似但出于阶段。我们的方法需要 这对大田最近的工作为出发点，然后微调的算法，对于一 特定的域，甚至是特定的查询，可有选择地限制数量 让我们一起翘曲各地的查询，使用新的代表， Ratanamahatana -基奥乐队（的R - K波段）。正如将被显示，有选择性地限制 翘曲允许的金额，我们实际上可以提高大田准确性 和它的索引性能。在对大田全局约束几乎已被 普遍适用于大田，主要是为了防止不合理的扭曲和 加快运算。最近，我们提出了一个新代表，Ratanamahatana - 基奥乐队（RK乐队）8，它可以表示任意形状的限制， 事实证明，改善和准确度和精密度/召回。由于空间限制， 请参阅关于大田更多细节9。 我们既可以利用的分类和索引/查询检索采用RK乐队 的问题，于手头的任务而定，使用启发式搜索。由于空间 的限制，只能索引的学习或查询检索包含一个RK乐队 在这里。乐队的RK的全部细节已广泛在9所示。多媒体检索使用时间序列表示与相关反馈403 甲） Q Q 乙） Q 三） 图。 4。与R - K波段，我们 可以创建任意的全局 限制。 A）我们可以 指定所有现有的全球 限制因素，包括 Sakoe -千叶带B）及 平行四边形的板仓丙）。 3.1学习一个索引RK带（由内容查询） 除了创造分类的R - Kc的乐队，我们可以学到一个单一的RK 为索引或查询检索乐队使用通用启发式爬山搜索技巧， 但我们只保持一个单一波段代表整个问题 而我们测量精度/召回，而不是准确性。这种方法是reillustrated 通过下面的实验，测量精度和索引召回。 10例子取自枪数据集和数据库放在一个包含另一 10000序列的形状类似，但不属于该类。另一 30（不相交）由枪与其他970其他序列数据集的例子中使用 的R - K波段的训练过程。然后，就有10个不同的（不相交）例子从 枪数据集，用来制作的k -近邻查询使用，10次迭代 各种从一物体精确到10的水平和远程对象召回措施 当时采取的测量。结果显示在图。 5。由此产生的精度 提高到0.46只使用3.24秒。 图。 5。 （左）的一些例子 从枪 数据集。 （中）所产生的 单一的R - K波段 教训和 精密/召回阴谋 比较各 距离测量（右） 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.2 0.4 0.6 0.8 一 记得 精确 欧几里德 大田：10翘曲 大田：的R - K波段 图。 6。精密/召回从10到100曲线 记得水平不同距离的措施：欧几里德， DTW的10，窗口的大小，所提出的方法 - RK乐队，它为各级完美的精确度都记得 图。 6显示了另一个实验结果，数据查询气缸10从集合 万随机行走序列。 很明显，利用此问题一RK带显着提高 既精确度和召回，而欧氏和大田10翘曲。404 C.A. Ratanamahatana和E.基奥 然而，RK乐队需要吸取的训练数据，这些数据可能不会 实际或可在很多情况下。要解决这个问题，我们可以建立一个 通过相关反馈系统训练数据来提高查询性能， 与一些在确定的积极和消极的实例，以帮助用户 系统。 4相关反馈与R - K波段 相关反馈方法，试图以提高性能为特定的信息 需要通过优化查询，根据用户的最初反应 检索文件/对象。在这个时间序列检索系统，用户将提供 示例图像或视频作为初始查询。然后系统查询转换 图像/视频转换为时间序列，利用前面讨论的方法。转换后 时间序列，然后用从多媒体查询10近邻 时间序列数据库。用户然后要求每一个职级的形象造成4点 规模，然后将查询到的细化适当重量转换 过程（平均与当前查询的积极成果）。一旦用户行列 结果，每一个查询细化执行，这样一个质量更好的查询 产生下一个检索轮。不过，平均的时间收集 系列，是不完全的时间对齐是不平凡和大田需要11。在 我们的实验中，我们考虑3多媒体数据集，利用我们的相关反馈 技术（详细完整的数据集，可在9）。为了评估我们的架构， 我们衡量每一轮的相关反馈的精度和召回 检索。然后，我们衡量我们的相关反馈系统性能 从每一轮迭代精度召回阴谋。图。 7显示precisionrecall 曲线的第一个五年相关反馈迭代三个数据集。 我们的实验表明，在显着改善每次迭代结果 既精确度和召回。 图。 7。在精密 记得图谋 5 3数据集 迭代相关 反馈 5结论 我们已经展示了代表作为时间序列的多媒体数据的替代方式。 然后，我们介绍了两种分类和时间序列检索框架。该 RK乐队允许任何在大田计算任意形状翘曲窗口。 凭借我们广泛的评估，我们已经表明，我们的架构纳入 相关反馈可以减少在分类错误率，提高精度 在视频和图像检索都记得水平。 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 一 记得 精确 迭代1 迭代2 迭代3 迭代4 迭代5 WordSpotting 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 一 记得 精确 迭代1 迭代2 迭代3 迭代4 迭代5 叶 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 一 记得 精确 迭代1 迭代2 迭代3 迭代4 迭代5 枪多媒体检索使用时间序列表示与相关反馈405 参考资料 1。阿格拉瓦尔，河，林，碘化钾，桑尼，房协及垫片，光（1995）。快速的相似性搜索 存在噪声，缩放，和翻译在时间系列数据库。的VLDB，页。490-501。 2。 Faloutsos角，阮冈纳赞，米和马诺洛普洛斯，士元（94年）。快速子序列匹配 在时间序列数据库。在进程内。 ACM SIGMOD机密档案。，明尼阿波利斯。页。419-429。 3。基奥，E.和Kasetty，第（2002）。在时间序列数据挖掘基准的需要： 实证调查与论证。 SIGKDD在第八含石棉材料。页。102-111。 4。耆那教，A.K. Namboodiri，上午（2003年）。索引和Retrie -的在线手写缬氨酸 文件。 ICDAR：655-659。 5。 Kavallieratou，大肠杆菌，Dromazou，北路，Fakotakis，北路和Kokkinakis，克（2003年）。一种集成 系统的手写文件图像处理。 IJPRAI，（17）4，页。617-36。 6。拉斯，吨及Manmatha河（2003年）。字图像匹配使用动态时间规整。 CVPR：二，521-27。 7。 Sakoe，阁下及千叶，第（1978）。动态规划算法优化发言 认字。 IEEE期刊。 Acous。，语音和信号触发。，ASSP的- 26：43-49。 8。 Ratanamahatana，C.A. 基奥，