视频故事单元语义相似度算法研究

罗 娜, 魏 维

(成都信息工程学院计算机学院,四川成都610225)

0 引言

随着计算机技术、信息数字化技术和网络技术和的发展,人类进行信息存储传播已从传统单一的文字描述发展到数字视频、音频、文字图片等在内的多种方式,其中数字视频所占据的比例越来越大。视频是文本、图像、语音等媒体综合而成的数据流,内容丰富,能记录、保留空间和时间上的各种信息和细节,成为最重要的信息载体。如何从海量的视频数据中找出需要的视频,是一件非常困难的事情。因此,对视频数据组织、管理、分类、检索等多个领域,视频相似度的有效计算都是进行信息处理的关键。

语义(Semantics)提出于20世纪70年代,主要应用在知识工程、自然语言处理和人工智能等领域。对视频数据进行分析时,借助人类更容易理解的语义能够使视频处理相关领域的成果能够更好的服务于人类生活。由于视频数据自身的复杂性和多样性,视频数据分析领域的研究者根据对视频“语义”理解的不同,对视频语义的获取经历了手工标注[1],底层特征描述[2-3],多模式融合和多层次分析[4-5]等阶段。目前对视频语义较好的定义是,用人可以描述、理解和表达的方式描述视频所包含的对象(语义物体),对象的事件,以及对象间关系等视频信息[3,6]。

图1 视频语义相似度计算流程

相似性是一个复杂的概念,在语义学、哲学和信息理论中被广泛讨论。文中的视频相似度是指通过特定的算法得出一个从人类思维角度考虑的评价两段视频是否相似的评价标准。在进行视频相似度计算前,首先要对视频进行预处理,提取出可以表征视频语义的有关信息,并对其进行表征。再根据算法计算两段视频故事单元的语义相似度,最终得到一个[0,1]的实数值,可以很好的表示两个视频故事单元间的语义相似度。图1所示即为视频语义相似度计算的整个流程。

1 语义表征

1.1 视频预处理

在整个视频相似度计算流程中,首先要对视频进行数据结构化和语义特征提取两个步骤,已提取出视频故事单元中的语义信息[7]。

视频是一组非结构化的数据流,对视频数据结构化是视频语义分析和表征的基本工作和必要步骤。首先将视频分割为帧、镜头、场景、故事单元等不同层次的逻辑单元,以便在各个层次上提取出语义信息并对其进行分析。帧是一幅静态图像,是最小的视频单元。镜头是一台摄像机从开机到关机连续拍摄的帧序列,描绘一个事件或一个场面的一部分,不具有或具有较弱的语义信息,强调构成帧的视觉内容相似性,通常用一个或多个关键帧(代表帧)来表现镜头。场景是语义相关的连续镜头,可以是相同对象的不同角度、不同技法拍摄,也可以是具有相同主题和事件的镜头组合,强调语义的相关性。故事单元包含一个完整的事件或故事,作为最高层的视频内容结构,它包括视频的组成关系以及对视频的摘要、语义和一般性描述等。及时针对视频的故事单元层次进行语义表征和相似度计算,因此文中多提到的视频均指视频的故事单元。

由于视频本身内容的复杂性和多样性,在现有的视频语义提取技术条件下不容易自动获取完整的视频文本描述。早期人们采用的人工标注的方式虽然能够用人可以理解的方式描述视频中所包含的信息,但其工作量巨大,且不可避免的带有主观偏差,所表达的语义信息往往是不准确或不完整的。视频的颜色、纹理、形状等低层视觉特征,视频的部分声音、文字其他底层特征可由计算机自动提取,这种表征方法虽然大大降低了工作量,但是所表达的信息与人类的需求存在着巨大差异。随着视频语义相关技术研究的深入,该领域的研究者们提出了采用多模式融合和多层次分析技术进行视频语义提取及表征。所谓多模式融合和多层次分析技术就是对机器自动提取的多模视频底层特征(包括视觉、声音[8]、文字[9]等底层特征),采用概率统计方法、统计学习方法、基于规则推理的方法、结合特定领域特点等方法[10],将视频的底层特征传递、映射和融合,转化为人类可以理解的,对原视频高度概括的高层语义信息的技术。虽然这些方法都取得了一定的成绩,但是它们在视频语义信息提取的正确率和可提取的种类上仍然有一定的局限性,无法实际应用中广泛使用。因此,在采用多模式融合和多层次分析技术来提取视频语义信息以降低手工工作量的同时,还需要借助“人工标注”进行补充以降低多模式融合和多层次分析技术的局限性,从而使本研究能够适用于更广泛的视频应用领域中。

1.2 视频语义表征

完善的视频语义表征模型是对视频进行语义相似度计算的基础,好的语义表征模型可以将语义相似度计算变得更为简单、有效;差的语义模型不仅会增加语义相似度计算的难度,更会影响最终计算结果的准确性、适用性。

在人类的思维模式中,一个完整的故事单元一般包含以下四个特定元素:事件发生的时间、地点、所涉及的人物(或对象)和事件,即4WH[11]。因此在人类理解的基础上采用一种基于时间、地点、语义对象和语义行为的视频语义表征方法,可用一个四元组表示为:

VideoSematics={Time,Place,Object,Action}

Time代表视频故事发生的时间,Place代表视频故事发生的地点,Object代表视频中包含的语义物体,Action代表视频中包含的语义行为。

对上述四元组进一步描述如下:

Time={DurationTime},故事发生的时间,一般故事单元发生的时间在一个较为接近的时间范围内,这里用时间区间集表示。

Place={Place1,Place2,…,Placen},故事发生的地点,整个故事可能发生在多个地点,一般情况下一个故事单元发生在可以认为是一个地点的一定范围内。

Object={Obj1,Obj2,…,Objn},一个故事单元中常常包含若干个语义对象,根据视频类型的不同,这些对象可以是单个具体的人或物,也可以是人或物的集合,如军队。

Action={Action1,Action2,…,Actionn},一个故事单元中包含多个语义行为,这些语义行为构成故事单元的事件信息。

在上述语义表征,Time,Place,Object,Action中的元素均为1.1节中通过多模式融合和多层次分析技术或人工标注的提取出的语义关键词,采用该视频表征模型作为后续视频语义相似度计算的输入。

2 视频语义相似度计算算法

2.1 相似度计算度量方法

相似度计算用于衡量对象之间的相似程度,相似度值越大,对象越相似,反之越小。相似度的计算方法有很多种,常用的相似度计算方法有欧氏距离,余弦相似度,皮尔森相关系数,Jaccard相似系数,调整余弦相似度等[12]。其中Jaccard相似系数和欧氏距离公式分别为:

相似度计算将用到适当改进后的Jaccard系数和欧氏距离公式,计算的最终结果是一个[0,1]的数值。在视频语义相似度计算时,这个数值并不代表明确的意义,只是数值越大,其所联系的两段视频在语义上更相似。

2.2 词语间的相似度计算

人类语言形成较早且在不断的变化,因而有其复杂性,在视频语义表征中可能出现同义不同形的情况,应建立语义词典避免由此产生的误差。自然语言理解研究领域中对语义的研究较早,相关领域的研究者已建立起较为成熟的基于本体概念的语义词典,如Wordnet[13]、Hownet[14]、同义词词林[15]等,并在此基础上形成较为成熟的词语相似度计算方法。视频相似度计算主要针对视频中的语义,其视频的表征模型使用了自然语言理解领域中的本体概念,而又有其不同于自然语言理解的特点,应借用或建立合适的语义词典建立符合视频语义表征模型特点的相似度计算方法。

(1)Object,Action语义词典

对于语义表征模型中的Object,Action集合中的词语主要来自于自然语言理解领域中本体概念,因此可选取该领域中较为成熟的语义词典来衡量Object,Action集合中词语间的相似度。与Wordnet和Hownet相比,同义词词林有可以人工增加或编辑,计算简单、高效等好处,因此采用《同义词词林》作为语义词典来计算 Object,Action集合中词语间的相似度。

设有两个词 w1和 w2,分别为:

w1={x1,x2,x3,x4,x5,x6,x7,x8}

w2={y1,y2,y3,y4,y5,y6,y7,y8}

其中 xi,yi分别为两个词在同义词词林中的编码。

则w1和 w2的相似度计算公式表示为:

(2)地点语义词典

由于空间地点语义并无收录词条,且地理位置间也存在层次包含关系,并不是简单的相同或不相同可以衡量的。应引入地理知识来建立地点语义词典,并在此语义词典基础上计算地点的语义相似度。

语义词典共分5层:第一层表示各大洲各大洋;第二层为各国家、地区;第三层为各省、直辖市和各大河流、湖泊、山脉等;第四层为个城市、山峰等;第五层为各县等。树种的一个节点代表一个地点,如果比较两地点的相似度,只需计算它们的共同路径与总路径的长度比。

2.3 时间相似性度量

视频故事单元发生的时间通常是隐含的,仅仅通过故事发生的日期是不能判定两段视频故事单元语义上是否相似。采用类似文献[16]中的方法获取视频故事单元的时间区间序列集。文献[17]对时间区间进行了各种研究,借鉴它们的方法,采用两个时间区间集的Jaccard相似系数作为视频故事单元的时间相似度。则两段视频故事单元的时间相似度可表示为:

2.4 视频语义相似度计算算法

视频相似度计算可应用于多个领域。在视频分类中,相同类别的视频相似度高,不同类别的视频度低。在视频检索中,对检索的结果按照与样本视频的相似度按照从高到低排序,有助于用户快速找到需要的视频。

视频相似度计算以语义表征模型为输入,对四元组的各分量分别进行相似度计算,整个算法描述如下:

输入:视频故事单元A和视频故事单元B

输出:一个[0,1]的数值。

第1步:分别对视频故事单元A和视频故事单元B进行视频预处理,生成各自对应的语义表征模型。

第2步:读取视频故事单元A和视频故事单元B的 Time信息并进行比较,根据公式(1)计算视频故事单元A和视频故事单元B的时间语义相似度,记为Sim(Time)。

第3步:读取视频故事单元A和视频故事单元B的Place信息,根据地点语义词典计算视频故事单元A和视频故事单元B的地点语义相似度,记为Sim(Place)。

第4步:读取视频故事单元A和视频故事单元B的Object信息,并计算计算视频故事单元A和视频故事单元B的Object元素的数目,记为

第5步:分别对视频故事单元A和视频故事单元B中Object元素进行遍历,两两进行比较,使用公式

第6步:读取视频故事单元A和视频故事单元B的 Action信息,并计算计算视频故事单元A和视频故事单元B的Action元素的数目,记为

第7步:分别对视频故事单元A和视频故事单元B中Action元素进行遍历,两两进行比较,计算视频故事单元A和视频故事单元B的 Action相似度,使用计算公式

第8步:视频故事单元的总相似度用欧氏距离综合 Time,Place,Object,Act各分量的相似度计算得出,并通过除数4使相似度范围保持在[0,1],即

3 实验和结果分析

实验数据分别选取篮球、新闻、电影、综艺等4类视频故事单元作为测试样本,这些样本数据主要通过互联网下载并手工分割为视频故事单元,得到各类视频样本数目如表1所示。

表1 实验样本数据

为了验证文中视频语义表征模型及相似度计算算法的效果,采用语义表征模型对每个实验样本进行语义表征。由于同一类别的视频镜头在高层语义结构具有较大的相似性,实验采用语义相似度算法对同一类型的视频两两进行相似度计算。且目前视频语义相似度计算研究领域尚无评判标准,故以“人的视觉判断”为标准依据,对实验结果进行对比和测试,得到图2所示的结果。

从图中实验数据可知,人与人之间的判断标准基本一致,实验的整体的测试结果与“人的视觉判断”比较相符。但不同类型的视频故事单元对文中算法的适应性具有差异性,如“篮球类”和“电影类”的视频的语义相似度判断较为准确,主要原因是这类视频故事逻辑性强,语义表征模型较适应这类视频故事单元,而对“综艺类”视频故事单元的语义表征不够完善,因此对应的视频相似度计算准确度要差一些。因此提出的视频相似度算法对特定种类的视频数据的组织、管理、分类、检索等研究和应用具有参考性。

图2 实验结果

4 结束语

建立以时间、地点、语义对象和语义行为的四元组表征模型,用改进后Jaccard系数和欧氏距离公式加权计算得到两视频故事归一化的语义相似度。该方法实现了两视频故事单元间定量语义相似性计算,与现有的相关研究方法相比,文中建立的四元组表征模型和计算算法全面综合考虑了故事场景具有丰富时间空间信息的特性,更适合场景间语义相似性度量计算,是基于语义视频组织、管理、传播和应用的关键技术,也为进一步提取视频高层语义奠定了基础。

该算法还存在的不足是在不同应用领域中对不同语义分量的需求可能不同,这是后续工作中需要加以完善并实现的地方。

[1] 孔英会,刘淑荣,张少明,等.基于语义的视频检索关键技术综述[J].电子科技,2012,25(8):150-153.

[2] 张永华,冯文辉,郭成,等.基于内容的检索中视频相似度度量方法研究[J].电脑知识与技术,2009,5(9):2188-2189.

[3] 胡振兴.基于内容的视频检索技术研究[D].长沙:中南大学,2009.

[4] 吕丽.多层次语义视频对象描述模型及提取技术研究[D].上海:上海交通大学,2007.

[5] 魏维,邹书蓉,刘凤玉.多层次视频语义概念分析与理解[J].计算机辅助设计与图形学学报,2008,20(1),85-92.

[6] 周生,胡晓峰.视频语义相似度网络研究[J].计算机应用,2010,30(7):1963-1966.

[7] 余卫宇,谢胜利.语义视频检索的现状和研究进展[J].计算机应用研究,2005,(5):1-7.

[8] Wei W,Liu W Q,Huang M.Quantitative similarity computing for audio effect semantic in video content analy-sis[C].Proc of 2th International Conference on Computer Engineering and Technology(ICCET),2010:123-127.

[9] Jae-Chang Shim,Chitra Dorai,Ruud Bolle.Automatic Text Extraction from Video for Content-Based Annotation and Retrieval[C].Proc of 14th International conference on Pattern Recognition,1998:618-620.

[10] 李德山.基于语义的视频检索[D].青岛:中国石油大学,2009.

[11] 徐新文.基于内容的新闻视频挖掘方法研究[D].长沙:国防科技大学,2009.

[12] Mihalcea R F,Mihalcea S I.Word sematic for information retrieval:moving one step closer to the semantic web[C].Proc of 13th International conference on Tools with Artificial Intelligence,2001:280-287.

[13] Resnik,P.Using information content to evaluate semantic similarity in a taxonomy[C].Proc of 14th International Joint conference on Artificial Intelligence,1995:448-453.

[14] 葛斌,李芳芳,郭思路,等.基于知网的词汇语义相似度计算方法研究[J].计算机应用研究,2010,27(9):3329-3333.

[15] 程传鹏.网络评价倾向性研究[J].计算机工程与应用,2011,47(25):156-159.

[16] F,S,C.From temporal expressions to temporal information:Semantic tagging of news message[C].Proceedings of the workshop on Temporal and spatioal information processing(ACL),Toulouse,France.2001:65-72.

[17] K,K.On the reliability of unitizing continous data[C].Sociological Methodology,1995:47-76.