多媒体内容分析与检索技术

1、 多媒体分析与检索技术多媒体分析与检索技术Multimedia Analysis and Retrieval Technology注：本讲内容参考了注：本讲内容参考了北京大学数字媒体研究所北京大学数字媒体研究所数字媒体技术基础数字媒体技术基础课件课件 数字媒体技术基础数字媒体技术基础第五讲（第五讲（8课时）课时）课程内容及安排课程内容及安排第一部分：数字媒体导论第一部分：数字媒体导论第二部分：数字媒体基础第二部分：数字媒体基础数字彩色图像基础图像/视频处理基础第三部分：数字媒体关键技术第三部分：数字媒体关键技术多媒体压缩编码技术多媒体分析与检索技术多媒体分析与检索技术多媒体通信技术多媒体通信技

2、术数字版权管理技术数字版权管理技术2/80教学目标教学目标通过本章的学习，掌握通过本章的学习，掌握“多媒体分析与检索多媒体分析与检索”这这一多媒体领域最活跃研究方向的基本研究问题一多媒体领域最活跃研究方向的基本研究问题和方法，及其最新进展。和方法，及其最新进展。ACM MultimediaACM ICMRICME MMM ICIMCS ICCV CVPR ICIP ICPR3/80教学内容教学内容多媒体检索概论多媒体检索概论(2)基于内容的图像分析与检索（基于内容的图像分析与检索（CBIR）(2)视频分析与检索视频分析与检索(3)音频分析与检索音频分析与检索(1)4/80一、多媒体检索概论一、

3、多媒体检索概论5/80Local Videos, Images, 如何从如此海量的多媒体数据中定位到你所感兴趣的信息？如何从如此海量的多媒体数据中定位到你所感兴趣的信息？How to effectively organize, manage, browse, retrieve?Image/Video indexing should be analogous to text document indexingMultimedia Analysis and Retrieval6/80引言引言“多媒体多媒体搜索引擎搜索引擎”可以搜索可以搜索多媒体文档多媒体文档的搜索引擎的搜索引擎l多媒体文档: 可包

4、含多种模态,如文本、图像、视频、音频等广义的：可以搜索非文字信息的搜索引擎广义的：可以搜索非文字信息的搜索引擎l“视视/听觉听觉”信息信息7/80多媒体文档的特点多媒体文档的特点多媒体文档包含丰富的非文字信息多媒体文档包含丰富的非文字信息8/80多媒体文档的特点多媒体文档的特点关键字对应的非文字信息可能过于宽泛关键字对应的非文字信息可能过于宽泛9/80麦浪滚滚麦浪滚滚多媒体检索概念多媒体检索概念提供多媒体的提供多媒体的查询输入查询输入可以方便地输入多媒体和文字查询可以方便地输入多媒体和文字查询对多媒体文档进行对多媒体文档进行多媒体索引多媒体索引特征索引：文本特征（字、词、短语）、视觉特征（颜特

5、征索引：文本特征（字、词、短语）、视觉特征（颜色直方图、色直方图、Gabor纹理、形状特征、纹理、形状特征、）、音频特征（）、音频特征（音高、音调音高、音调.）语义索引：元数据、概念、事件语义索引：元数据、概念、事件提供多媒体的提供多媒体的结果显示结果显示直观地展示多媒体和文字信息直观地展示多媒体和文字信息直观地展示深层信息直观地展示深层信息l跨文档综合（多媒体和文字信息）跨文档综合（多媒体和文字信息）方便浏览大量文档方便浏览大量文档10/80如何检索？如何检索？11/80检索方法检索方法1：基于文本：基于文本(QBT)关键问题：如何获得关键字标注？关键问题：如何获得关键字标注？方法方法1：手

6、工标注：手工标注l工作量巨大工作量巨大-不可行！不可行！l即使对同一幅图像，不同的人有不同的描述即使对同一幅图像，不同的人有不同的描述方法方法2：自动标注：自动标注l各种机器学习的算法各种机器学习的算法l性能不佳：只能提取少数概念，准确率也低性能不佳：只能提取少数概念，准确率也低(30%)12/80检索方法检索方法1：基于文本：基于文本(QBT)关键问题：如何获得关键字标注？关键问题：如何获得关键字标注？方法方法3：元数据分析：元数据分析-URL、链接文字、标题、关联、链接文字、标题、关联页面页面Meta-data元数据元数据东北虎：5老虎：3动物：2中国：1俄罗斯：1长白山：1。13/80检

7、索方法检索方法1：基于文本：基于文本(QBT)关键问题：如何获得关键字标注？关键问题：如何获得关键字标注？方法方法3：元数据分析：元数据分析-URL、链接文字、标题、关联、链接文字、标题、关联页面页面问题：元数据不一定与多媒体文档内容相关问题：元数据不一定与多媒体文档内容相关没有元数据或不完整！没有元数据或不完整！元数据与图像内容不相关！元数据与图像内容不相关！14/80检索方法检索方法1：基于文本：基于文本(QBT)关键问题：如何获得关键字标注？关键问题：如何获得关键字标注？方法方法4：网络标注（：网络标注（Social tagging/Folksonomy）l向普通用户提供上载和分享平台向

8、普通用户提供上载和分享平台l鼓励所有用户对上载的文档进行评论和标注鼓励所有用户对上载的文档进行评论和标注这些评论和标注是直接针对文档作出的这些评论和标注是直接针对文档作出的15/80http:/ 16/80QBT的难题的难题需求难以用文字精确描述需求难以用文字精确描述非文字需求非文字需求用户不愿意输入很多文字用户不愿意输入很多文字用户需求不是特别具体用户需求不是特别具体大多数人的想象力是不够丰富的大多数人的想象力是不够丰富的系统提供的结果会极大地影响用户的需求系统提供的结果会极大地影响用户的需求需要浏览更多的文档才能发现需要的结果需要浏览更多的文档才能发现需要的结果最重要：图像最重要：图像/视

9、频视频/音频往往难以用文字准确音频往往难以用文字准确描述描述一图胜千言一图胜千言各种文字标注方法普遍准确率不高各种文字标注方法普遍准确率不高18/80 Still region SR1: Creation inform a tion Text annotation Still region SR2: Text annotation Color structure Still region SR3: Text annotation Matching hint Color structure Spatial segment decompos i tion: No overlap, gap Dire

10、ctional spatial segment relation: left Content Structure Agent object AO1: Label Person Agent object AO2: Label Person Event EV1: Label Semantic time Semantic place Concept C1: Label Property Property Comradeship Shake hands Alex Ana Object-event relation: hasAccompanierOf Concept-semantic base rel

11、a tion: hasPropertyOf Content Semantics Object-event relation: hasAgentOf 视觉信息描述的复杂性视觉信息描述的复杂性 Segment-semantic base relation: hasMediaPerceptionOf Segment-semantic base relation: hasMediaSymbolOf Photographer: Seungyup Place: Columbia University Time: 19 September 1998 704x480 pixels True color RGB

12、 http:/www.alex&ana.jpg Columbia University, All rights reserved Creation information: Creation Creator Creation corrdinates Creation location Creation date Media information: Media profile Media format Media instance Usage unformation: Rights Content Management 19检索方法检索方法2：基于内容：基于内容/样例样例基于内容的图像基于内容

13、的图像/视频检索视频检索Content-based image/video retrieval (CBIR/CBVR)Query-by-Example (QBE)什么是什么是“内容内容”（Content）？）？图像和视频的视觉特性图像和视频的视觉特性如何描述？如何描述？(数学模型数学模型)如何匹配？如何匹配？(相似度计算方法相似度计算方法)如何索引？如何索引？(快速找到相似文档快速找到相似文档)如何提交查询？如何提交查询？20/80基于内容的图像基于内容的图像/视频检索视频检索“内容内容”的数学模型的数学模型文本文档：向量模型文本文档：向量模型多媒体文档：特征多媒体文档：特征l提取表示视觉的多

14、个物理量组成描述文档内容的特征提取表示视觉的多个物理量组成描述文档内容的特征l视觉特征：颜色、纹理、形状、运动视觉特征：颜色、纹理、形状、运动l音频特征：音频、音质、音调音频特征：音频、音质、音调.维数特性布尔运算语义文字超高(10万级)稀疏可离散多媒体高(几千以内)致密不可连续21/80 Color Camera motion Motion activity Mosaic Color Motion trajectory Parametric motion Spatio-temporal shape Color Shape Position TextureVideo segmentsStill

15、 regionsMoving regionsAudio segments Spoken content Spectral characterization Music: timbre, melody, pitch视音频特征示例视音频特征示例22基于内容的图像检索基于内容的图像检索 Query by content:Color,texture&ObjectSearchEngineRetrievalImageDB/WWW23基于内容的图像基于内容的图像/视频检索视频检索相似度计算相似度计算文字文档：余弦距离文字文档：余弦距离多媒体文档：欧氏距离及其改进多媒体文档：欧氏距离及其改进索引索引文字文档：

16、倒排文件文字文档：倒排文件l稀疏的文档向量稀疏的文档向量多媒体文档：高维索引或不索引多媒体文档：高维索引或不索引l紧致的文档向量紧致的文档向量24/80基于内容的图像基于内容的图像/视频检索视频检索查询提交手段查询提交手段如何让系统获得一个好的如何让系统获得一个好的“特征向量特征向量”？l可以较好地描述用户的需求可以较好地描述用户的需求文本查询文本查询(QBT: Query By Text)l关键字：难以准确描述用户需求关键字：难以准确描述用户需求l自然语言：自然语言：NLP仍是仍是open issue样例查询样例查询(QBE: Query By Example)l用户提交一个图像用户提交一个

17、图像/视频作为样例，查询与样例相似的其它图像视频作为样例，查询与样例相似的其它图像/视频视频概要图查询概要图查询(QBS: Query By Sketch)l要求用户都是优秀的画家要求用户都是优秀的画家l也有系统提供手绘界面也有系统提供手绘界面25/80基于文本基于文本 vs. 基于内容基于内容基于文本基于文本查询输入方便，在有准确的文字信息描述时很方便查询输入方便，在有准确的文字信息描述时很方便公开难题：如何提取图像公开难题：如何提取图像/视音频的语义描述视音频的语义描述目前商业搜索引擎常用目前商业搜索引擎常用基于内容基于内容从信号处理角度入手，试图使检索过程符合人的视听觉从信号处理角度入手

18、，试图使检索过程符合人的视听觉特性（所见即所得）特性（所见即所得）查询输入不符合人的习惯查询输入不符合人的习惯公开难题：语义鸿沟公开难题：语义鸿沟 (Semantic Gap)仍停留在研究阶段仍停留在研究阶段26/80多媒体检索框架多媒体检索框架StorageBrowseAV DescriptionFeature extractionManual / automaticTransmissionEncoding(for transmission)Decoding(for transmission)RecommendationPushSearch / queryPullHuman or machi

19、ne27多媒体搜索引擎需要的技术多媒体搜索引擎需要的技术多媒体内容分析技术多媒体内容分析技术理解多媒体文档的内容，提取语义理解多媒体文档的内容，提取语义多媒体查询输入技术多媒体查询输入技术方便地提交多媒体查询方便地提交多媒体查询多媒体结果显示和浏览技术多媒体结果显示和浏览技术直观、方便地浏览结果直观、方便地浏览结果多媒体特征的高维索引技术多媒体特征的高维索引技术28/80多媒体检索分类多媒体检索分类图像检索图像检索CBIR语义分类、标注语义分类、标注相关反馈相关反馈音频检索音频检索音频特征提取音频特征提取自动语音识别（自动语音识别（ASR）哼唱找歌哼唱找歌视频检索视频检索视频分割与分类视频分割

20、与分类特定对象检测特定对象检测事件检测与摘要事件检测与摘要跨媒体检索跨媒体检索跨媒体融合跨媒体融合29/80图像搜索技术的应用图像搜索技术的应用风景图像的替换与补图风景图像的替换与补图A. Efros , CVPR, 200730/80图像搜索技术的应用图像搜索技术的应用Sketch2Photo：互联网图像蒙太奇：互联网图像蒙太奇Chen, SIGGraph 2009技术难点：技术难点： 自动找到高质量的、包含正确对象的图片自动找到高质量的、包含正确对象的图片1.无缝的对这些子图像进行合成无缝的对这些子图像进行合成31/80图像搜索技术的应用图像搜索技术的应用Image2Gps: 通过图像搜索

21、推理出图像的拍摄位通过图像搜索推理出图像的拍摄位置置A. Efros, CVPR 200832/80图像搜索技术的应用图像搜索技术的应用Panoramio： http:/ 所指即所见所指即所见Luo, ACM MM200934/80图像搜索技术的应用图像搜索技术的应用广告搜索：广告搜索：Trademark，Logo，Patent商业图像的数据挖掘商业图像的数据挖掘版权保护版权保护商品搜索商品搜索获取商品信息获取商品信息: 用商品图像进行搜索得到相关信息用商品图像进行搜索得到相关信息网上购物，货比三家网上购物，货比三家 医学图像检索医学图像检索35/80图像搜索技术的应用图像搜索技术的应用htt

22、p:/www.robots.ox.ac.uk/james/交互式视频技术交互式视频技术用户在观看视频时，能够选择视频中出现的各种对象（人物、地用户在观看视频时，能够选择视频中出现的各种对象（人物、地点、物品等）；点、物品等）；在屏幕上展现被选中对象的信息，例如名称等；在屏幕上展现被选中对象的信息，例如名称等； 展现与上述对象相关的业务提供者（例如服装店）链接；展现与上述对象相关的业务提供者（例如服装店）链接； 用户可以通过用户可以通过IM或者电话进一步与业务提供者联系或者电话进一步与业务提供者联系36/80Video Google: A Text Retrieval Approach to O

23、bject Matching in Videoshttp:/www.robots.ox.ac.uk/vgg/research/vgoogle/二、图像分析与检索二、图像分析与检索38/80图像检索概论图像检索概论Datta, ACM CSUR, 200839/80Semantic Gap40/80KeywordsDescriptionsClassificationOntologiesHumanIntelligenceDataA Typical Image Search SystemQueryUserIndexDataQuery FormationRankingIndexingResult Pr

24、esentationIntention Intention GapGapIntention/Intention/Semantic Semantic GapGapSemantic Semantic GapGapUI and query suggestionUI and query suggestionSearch result organizationSearch result organizationInteractiveInteractiveFeedbackFeedbackImage Image annotationannotation41/80Designing a real-world

25、image search engine： From a user perspectiveDotta, et al., Image retrieval: Ideas, influences, and trends of the new age, ACM Computing Survey, 2008(1) clarity of the user about what she wants,(2) where she wants to search, and (3) the form in which the user has her query42/80Designing a real-world

26、image search engine: From a system perspectiveDotta, et al., Image retrieval: Ideas, influences, and trends of the new age, ACM Computing Survey, 2008(1) how does the user wish the results to be presented,(2) where does the u s e r d e s i r e t o search, and( 3 ) w h a t i s t h e n a t u r e o f u

27、 s e r input/interaction.43/80CBIR框架框架Smeulders, PARMI, 200244/80图像特征与表示图像特征与表示Dotta, et al., Image retrieval: Ideas, influences, and trends of the new age, ACM Computing Survey, 2008An overview of image signature formulation45/80图像特征类型图像特征类型颜色、纹理、形状关键点SIFT位置对象/区域Smeulders, PARMI, 200246/80图像特征汇总图像特

28、征汇总ColorColor Histogram“Sensitive to noise and sparse”- Cumulative Histograms Color MomentsColor Sets: Map RGB Color space to Hue Saturation Value, & quantizeColor layout- local color features by dividing image into regionsColor AutocorrelogramsTextureCo-occurrence matrixOrientation and distance on

29、gray-scale pixelsContrast, inverse deference moment, and entropy Human visual texture properties: coarseness, contrast, directionality, likeliness, regularity and roughnessWavelet Transformsextracted mean and variance from wavelet subbandsGabor Filters47图像特征汇总图像特征汇总ShapeOuter Boundary based vs. regi

30、on basedFourier descriptorsMoment invariantsFinite Element Method (Stiffness matrix- how each point is connected to others; Eigen vectors of matrix)Turing function based (similar to Fourier descriptor) convex/concave polygonsWavelet transforms leverages multiresolution Chamfer matching for comparing

31、 2 shapes (linear dimension rather than area)3-D object representations using similar invariant featuresWell-known edge detection algorithms48/80特征举例：颜色特征特征举例：颜色特征Colour histograms (CH)Global CH generated directly from RGB space, with 125 (5x5x5) bins.49/80Bosch, IVC, 200650/80特征举例：边特征特征举例：边特征Edge h

32、istogram (EHD) Captures the spatial distribution of the edge in six statues: 0, 45, 90, 135, non direction and no edge.Global EHD of an image: Concatenating 16 sub EHDs into a 96 binsLocal EHD of a segmentlGrouping the edge histogram of the image-blocks fallen into the segment51/80特征举例：点特征特征举例：点特征De

33、tect patchesMikojaczyk and Schmid 02Sivic et al. 03Compute SIFT descriptor Lowe9952全局全局 vs. 局部特征局部特征54/80区域分割区域分割计算机视觉领域的公开难题计算机视觉领域的公开难题55/80相似度度量相似度度量Dotta, et al., Image retrieval: Ideas, influences, and trends of the new age, ACM Computing Survey, 200856/80相似度度量相似度度量Dotta, et al., Image retrieva

34、l: Ideas, influences, and trends of the new age, ACM Computing Survey, 2008CBIR不是为了进行精确的匹配，而是计算查询图像和数据库中的图像之间的视觉相似度，不是为了进行精确的匹配，而是计算查询图像和数据库中的图像之间的视觉相似度，相应的，检索结果不是单一的一副图像，而是按照与查询图像的相似度排序的一系列相应的，检索结果不是单一的一副图像，而是按照与查询图像的相似度排序的一系列图像。不同的相似度度量显著影响图像。不同的相似度度量显著影响CBIR系统的性能。系统的性能。57/80基于样例的查询基于样例的查询Query by

35、 ExamplePick query examples and ask the system to retrieve “similar” images.Query SampleResultsCBIR“Get similar images”58/80相关反馈相关反馈Relevance FeedbackUser gives a feedback to the query resultsSystem recalculates feature weightsInitialsample1st ResultQuery2nd ResultFeedbackFeedback59/80相关反馈相关反馈Online

36、 Feature WeightingFrom Query Examples, the system determines feature weighting (k x k) matrix WResultQueryCBIRCalculate W distance (r x ,r y ) (r x r y )TW (r x r y )60/80基于相关反馈的检索界面基于相关反馈的检索界面User selects relevant imagesIf good images are found, add themWhen no more images to add, the search conver

37、gesSlider or Checkbox61/80基于相关反馈的检索界面基于相关反馈的检索界面62/80评价指标：评价指标：Average Precision只对返回的相关文档进行计算只对返回的相关文档进行计算系统检索出来的相关文档越靠前系统检索出来的相关文档越靠前(rank 越高越高)，AP就越高就越高63评价指标：评价指标：Average PrecisionMAP(Mean Average Precision) is the average AP for all queries例如：假设有两个例如：假设有两个queries，query 1有有4个相关个相关images，query2有有5

38、个相关个相关image。某系统对于某系统对于query1检索出检索出4个相关个相关image，其，其rank分别为分别为1, 2, 4, 7；对于对于query2检索出检索出3个相关个相关query，其，其rank分别为分别为1,3,5。对于对于query1，AP为为(1/1+2/2+3/4+4/7)/4=0.83。对于对于query2，AP为为(1/1+2/3+3/5+0+0)/5=0.45。则则MAP= (0.83+0.45)/2=0.64。64现实中的现实中的CBIR系统示例系统示例http:/Visual similarity search in Specific Domain：a p

39、hoto-sharing community with more than a million airplane-related pictures65/80现实中的现实中的CBIR系统示例系统示例http:/a public-domain search engine which incorporates image retrieval and face recognition for searching pictures of people and products on the Web.66/80Image Annotation/Tagging：面向图像语义检索ShipWaterTreesk

40、yUse for keyword-based image retrieval67Image Annotation/TaggingJ Jeon, et al., Automatic image annotation and retrieval using cross-media relevance models, Sigir, 2003w1, w2, w3,.wnI68/80Annotation Examples 69/80Bridge User Intention Gap User queries are usually short, ambiguousHow to capture user

41、search intent?70/80Visual Query SuggestionZheng-Jun Zha, et al., Visual Query Suggestion, ACM MM, 2009 71/80Visual Query SuggestionTo help users specify and deliver their search intentsZheng-Jun Zha, et al., Visual Query Suggestion, ACM MM, 2009 72/80IGroup: presenting web image search results in se

42、mantic clustersThe result of “tiger” in MSN image search:mixed with “tiger woods” and “tiger animal”.73/80IGroup: presenting web image search results in semantic clustersThe screen of IGroup: the general view74/80IGroup: presenting web image search results in semantic clustersThe screen of IGroup: the cluster view75/80IGroup: presenting web image search results in semantic clusters76/803D MARS: 图像检索的图像检索的3D展示展示Image retrieval and browsing