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

1、 多媒体分析与检索技术Multimedia Analysis and Retrieval Technology注：本讲内容参考了北京大学数字媒体研究所数字媒体技术基础课件 数字媒体技术基础第五讲（8课时）课程内容及安排第一部分：数字媒体导论第二部分：数字媒体基础数字彩色图像基础图像/视频处理基础第三部分：数字媒体关键技术多媒体压缩编码技术多媒体分析与检索技术多媒体通信技术数字版权管理技术2/80教学目标通过本章的学习，掌握“多媒体分析与检索”这一多媒体领域最活跃研究方向的基本研究问题和方法，及其最新进展。ACM MultimediaACM ICMRICME MMM ICIMCS ICCV CV

2、PR ICIP ICPR3/80教学内容多媒体检索概论(2)基于内容的图像分析与检索（CBIR）(2)视频分析与检索(3)音频分析与检索(1)4/80一、多媒体检索概论5/80Internet Videos, Images, Audio, Flash, Aminations,Local Videos, Images, 如何从如此海量的多媒体数据中定位到你所感兴趣的信息？How to effectively organize, manage, browse, retrieve?Image/Video indexing should be analogous to text document in

3、dexingMultimedia Analysis and Retrieval6/80引言“多媒体搜索引擎”可以搜索多媒体文档的搜索引擎多媒体文档: 可包含多种模态,如文本、图像、视频、音频等广义的：可以搜索非文字信息的搜索引擎“视/听觉”信息7/80多媒体文档的特点多媒体文档包含丰富的非文字信息8/80多媒体文档的特点关键字对应的非文字信息可能过于宽泛9/80麦浪滚滚多媒体检索概念提供多媒体的查询输入可以方便地输入多媒体和文字查询对多媒体文档进行多媒体索引特征索引：文本特征（字、词、短语）、视觉特征（颜色直方图、Gabor纹理、形状特征、）、音频特征（音高、音调.）语义索引：元数据、概念、事

4、件提供多媒体的结果显示直观地展示多媒体和文字信息直观地展示深层信息跨文档综合（多媒体和文字信息）方便浏览大量文档10/80如何检索？11/80检索方法1：基于文本(QBT)关键问题：如何获得关键字标注？方法1：手工标注工作量巨大-不可行！即使对同一幅图像，不同的人有不同的描述方法2：自动标注各种机器学习的算法性能不佳：只能提取少数概念，准确率也低(30%)12/80检索方法1：基于文本(QBT)关键问题：如何获得关键字标注？方法3：元数据分析-URL、链接文字、标题、关联页面Meta-data元数据东北虎：5老虎：3动物：2中国：1俄罗斯：1长白山：1。13/80检索方法1：基于文本(QBT)

5、关键问题：如何获得关键字标注？方法3：元数据分析-URL、链接文字、标题、关联页面问题：元数据不一定与多媒体文档内容相关没有元数据或不完整！元数据与图像内容不相关！14/80检索方法1：基于文本(QBT)关键问题：如何获得关键字标注？方法4：网络标注（Social tagging/Folksonomy）向普通用户提供上载和分享平台鼓励所有用户对上载的文档进行评论和标注这些评论和标注是直接针对文档作出的15/80 16/80QBT的难题需求难以用文字精确描述非文字需求用户不愿意输入很多文字用户需求不是特别具体大多数人的想象力是不够丰富的系统提供的结果会极大地影响用户的需求需要浏览更多的文档才能发

6、现需要的结果最重要：图像/视频/音频往往难以用文字准确描述一图胜千言各种文字标注方法普遍准确率不高18/80视觉信息描述的复杂性19检索方法2：基于内容/样例基于内容的图像/视频检索Content-based image/video retrieval (CBIR/CBVR)Query-by-Example (QBE)什么是“内容”（Content）？图像和视频的视觉特性如何描述？(数学模型)如何匹配？(相似度计算方法)如何索引？(快速找到相似文档)如何提交查询？20/80基于内容的图像/视频检索“内容”的数学模型文本文档：向量模型多媒体文档：特征提取表示视觉的多个物理量组成描述文档内容的特征

7、视觉特征：颜色、纹理、形状、运动音频特征：音频、音质、音调.维数特性布尔运算语义文字超高(10万级)稀疏可离散多媒体高(几千以内)致密不可连续21/80Color Camera motionMotion activityMosaicColor Motion trajectoryParametric motionSpatio-temporal shapeColor ShapePositionTextureVideo segmentsStill regionsMoving regionsAudio segmentsSpoken content Spectral characterizationMu

8、sic: timbre, melody, pitch视音频特征示例22基于内容的图像检索 Query by content:Color,texture&ObjectSearchEngineRetrievalImageDB/WWW23基于内容的图像/视频检索相似度计算文字文档：余弦距离多媒体文档：欧氏距离及其改进索引文字文档：倒排文件稀疏的文档向量多媒体文档：高维索引或不索引紧致的文档向量24/80基于内容的图像/视频检索查询提交手段如何让系统获得一个好的“特征向量”？可以较好地描述用户的需求文本查询(QBT: Query By Text)关键字：难以准确描述用户需求自然语言：NLP仍是open

9、 issue样例查询(QBE: Query By Example)用户提交一个图像/视频作为样例，查询与样例相似的其它图像/视频概要图查询(QBS: Query By Sketch)要求用户都是优秀的画家也有系统提供手绘界面25/80基于文本 vs. 基于内容基于文本查询输入方便，在有准确的文字信息描述时很方便公开难题：如何提取图像/视音频的语义描述目前商业搜索引擎常用基于内容从信号处理角度入手，试图使检索过程符合人的视听觉特性（所见即所得）查询输入不符合人的习惯公开难题：语义鸿沟 (Semantic Gap)仍停留在研究阶段26/80多媒体检索框架StorageBrowseAV Descri

10、ptionFeature extractionManual / automaticTransmissionEncoding(for transmission)Decoding(for transmission)RecommendationPushSearch / queryPullHuman or machine27多媒体搜索引擎需要的技术多媒体内容分析技术理解多媒体文档的内容，提取语义多媒体查询输入技术方便地提交多媒体查询多媒体结果显示和浏览技术直观、方便地浏览结果多媒体特征的高维索引技术28/80多媒体检索分类图像检索CBIR语义分类、标注相关反馈音频检索音频特征提取自动语音识别（ASR）

11、哼唱找歌视频检索视频分割与分类特定对象检测事件检测与摘要跨媒体检索跨媒体融合29/80图像搜索技术的应用风景图像的替换与补图A. Efros , CVPR, 200730/80图像搜索技术的应用Sketch2Photo：互联网图像蒙太奇Chen, SIGGraph 2009技术难点：自动找到高质量的、包含正确对象的图片无缝的对这些子图像进行合成31/80图像搜索技术的应用Image2Gps: 通过图像搜索推理出图像的拍摄位置A. Efros, CVPR 200832/80图像搜索技术的应用Panoramio： /借助图像匹配搜索技术，从远近不同角度观察同一景点33/80图像搜索技术的应用Vie

12、wFocus: 所指即所见Luo, ACM MM200934/80图像搜索技术的应用广告搜索：Trademark，Logo，Patent商业图像的数据挖掘版权保护商品搜索获取商品信息: 用商品图像进行搜索得到相关信息网上购物，货比三家 医学图像检索35/80图像搜索技术的应用http:/www.robots.ox.ac.uk/james/交互式视频技术用户在观看视频时，能够选择视频中出现的各种对象（人物、地点、物品等）；在屏幕上展现被选中对象的信息，例如名称等； 展现与上述对象相关的业务提供者（例如服装店）链接； 用户可以通过IM或者电话进一步与业务提供者联系36/80Video Google

13、: A Text Retrieval Approach to Object Matching in Videoshttp:/www.robots.ox.ac.uk/vgg/research/vgoogle/二、图像分析与检索38/80图像检索概论Datta, ACM CSUR, 200839/80Semantic Gap40/80KeywordsDescriptionsClassificationOntologiesHumanIntelligenceDataA Typical Image Search SystemQueryUserIndexDataQuery FormationRanking

14、IndexingResult PresentationIntention GapIntention/Semantic GapSemantic GapUI and query suggestionSearch result organizationInteractiveFeedbackImage annotation41/80Designing a real-world image search engine： From a user perspectiveDotta, et al., Image retrieval:Ideas, influences, and trends of the ne

15、w 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 image search engine: From a system perspectiveDotta, et al., Image retrieval:Ideas, influences, and trends of the n

16、ew age, ACM Computing Survey, 2008(1) how does the user wish the results to be presented,(2) where does the user desire to search, and(3) what is the nature of user input/interaction.43/80CBIR框架Smeulders, PARMI, 200244/80图像特征与表示Dotta, et al., Image retrieval:Ideas, influences, and trends of the new

17、age, ACM Computing Survey, 2008An overview of image signature formulation45/80图像特征类型颜色、纹理、形状关键点SIFT位置对象/区域Smeulders, PARMI, 200246/80图像特征汇总ColorColor Histogram“Sensitive to noise and sparse”- Cumulative Histograms Color MomentsColor Sets: Map RGB Color space to Hue Saturation Value, & quantizeColor

18、layout- local color features by dividing image into regionsColor AutocorrelogramsTextureCo-occurrence matrixOrientation and distance on gray-scale pixelsContrast, inverse deference moment, and entropy Human visual texture properties: coarseness, contrast, directionality, likeliness, regularity and r

19、oughnessWavelet Transformsextracted mean and variance from wavelet subbandsGabor Filters47图像特征汇总ShapeOuter Boundary based vs. region basedFourier descriptorsMoment invariantsFinite Element Method (Stiffness matrix- how each point is connected to others; Eigen vectors of matrix)Turing function based

20、(similar to Fourier descriptor) convex/concave polygonsWavelet transforms leverages multiresolution Chamfer matching for comparing 2 shapes (linear dimension rather than area)3-D object representations using similar invariant featuresWell-known edge detection algorithms48/80特征举例：颜色特征Colour histogram

21、s (CH)Global CH generated directly from RGB space, with 125 (5x5x5) bins.49/80Bosch, IVC, 200650/80特征举例：边特征Edge histogram (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 binsLoca

22、l EHD of a segmentGrouping the edge histogram of the image-blocks fallen into the segment51/80特征举例：点特征Detect 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

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

24、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 Feature WeightingFrom Query Examples, t

25、he system determines feature weighting (k x k) matrix WResultQueryCBIRCalculate W60/80基于相关反馈的检索界面User selects relevant imagesIf good images are found, add themWhen no more images to add, the search convergesSlider or Checkbox61/80基于相关反馈的检索界面62/80评价指标：Average Precision只对返回的相关文档进行计算系统检索出来的相关文档越靠前(rank

26、 越高)，AP就越高63评价指标：Average PrecisionMAP(Mean Average Precision) is the average AP for all queries例如：假设有两个queries，query 1有4个相关images，query2有5个相关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。则

27、MAP= (0.83+0.45)/2=0.64。64现实中的CBIR系统示例Visual similarity search in Specific Domain：a photo-sharing community with more than a million airplane-related pictures65/80现实中的CBIR系统示例a public-domain search engine which incorporates image retrieval and face recognition for searching pictures of people and pr

28、oducts on the Web.66/80Image Annotation/Tagging：面向图像语义检索ShipWaterTreeskyUse for keyword-based image retrieval67Image Annotation/TaggingJ Jeon, et al., Automatic image annotation and retrieval using cross-media relevance models, Sigir, 2003Relevance Modelsw1, w2, w3,.wnI68/80Annotation Examples 69/80

29、Bridge User Intention Gap User queries are usually short, ambiguousHow to capture user 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., Visua

30、l Query Suggestion, ACM MM, 2009 72/80IGroup: presenting web image search results in semantic 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/80

31、IGroup: 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 in 3D Virtual RealityThe user can see more images without occlusionQuery results can be displayed in various criteriaResu