多媒體資料庫(New)3rd

多媒體資料庫(New)3rd. 1. 多媒體資料庫; 2. 提綱

• 簡介

• 多媒體資料庫的挑戰

• 多維度索引技術

• 文件資料 ... SlideShareusescookiestoimprovefunctionalityandperformance,andtoprovideyouwithrelevantadvertising.Ifyoucontinuebrowsingthesite,youagreetotheuseofcookiesonthiswebsite.SeeourUserAgreementandPrivacyPolicy. SlideShareusescookiestoimprovefunctionalityandperformance,andtoprovideyouwithrelevantadvertising.Ifyoucontinuebrowsingthesite,youagreetotheuseofcookiesonthiswebsite.SeeourPrivacyPolicyandUserAgreementfordetails. Upload Home Explore Login Signup Successfullyreportedthisslideshow. Activateyour30dayfreetrial tounlockunlimitedreading. 多媒體資料庫(New)3rd 4 Share KevingoTsai • Dec.08,2008 • 4likes • 3,898views DownloadNow Download NextSlideShares Youarereadingapreview. Activateyour30dayfreetrial tocontinuereading. ContinueforFree UpcomingSlideShare 那些年，我們一起Open的data Loadingin…3 × Facebook Twitter LinkedIn Size(px) Starton ShowrelatedSlideSharesatend Share Email     Topclippedslide 1 1of238 多媒體資料庫(New)3rd Dec.08,2008 • 4likes • 3,898views 4 Share DownloadNow Download Downloadtoreadoffline Technology Business KevingoTsai Follow SoftwareEngineer Technology Business 那些年，我們一起Open的data KevingoTsai Must-have!PMTools(Nov2010) JesseGant PhDPresentation mskayed DataPreprocessing Object-FrontierSoftwarePvt.Ltd Classification guest9099eb SpatiallyCoherentLatentTopicModelForConcurrentObjectSegmentationand... Shao-ChuanWang DefensePowepoint KasturiChatterjee Lec1-Into butest Ch9-1.MachineLearning:Symbol-based butest Lecture2 butest 那些年，我們一起Open的data KevingoTsai Must-have!PMTools(Nov2010) JesseGant PhDPresentation mskayed DataPreprocessing Object-FrontierSoftwarePvt.Ltd Classification guest9099eb SpatiallyCoherentLatentTopicModelForConcurrentObjectSegmentationand... Shao-ChuanWang DefensePowepoint KasturiChatterjee Lec1-Into butest Ch9-1.MachineLearning:Symbol-based butest Lecture2 butest MoreRelatedContent YouMightAlsoLike WALDLECTURE1 butest Slides butest IntroductiontoMachineLearning butest KnowledgebasedexpertsystemsinBioinformatics RadwenAniba 얼굴검출기법감성언어인식기법 cyberemotions Iccv2009recognitionandlearningobjectcategoriesp1c01-classicalmethods zukun Cvpr2007objectcategoryrecognitionp3-discriminativemodels zukun Cvpr2010opensourcevisionsoftware,introandtrainingpartvopencvandr... zukun Podobnostníhledánívnetextovýchdatech(PavelZezula) Národnítechnickáknihovna(NTK) ADAPTINGMETRICSFORMUSICSIMILARITYUSINGCOMPARATIVERATINGS DanielWolff Fcvbiocv_cottrell zukun Fcvbiocv_cottrell zukun ScaledEigenAppearanceandLikelihoodPrunningforLargeScaleVideoDuplica... UnitedStatesAirForceAcademy Mit6870orsulecture2 zukun Dbm630lecture05 TokyoInstituteofTechnology Semantic3DTVContentAnalysisandDescription DistinguishedLecturerSeries-LeonTheMathematician IJERD(www.ijerd.com)InternationalJournalofEngineeringResearchandDevel... IJERDEditor 1617bag_words khawarbashir Chapter-5DataMiningConceptsandTechniques2ndEdslidesHan&Kamber error007 K-Means,itsVariantsanditsApplications VaradMeru Associations1 mancnilu Preprocessing mmuthuraj Graphminingseminar_2009 HouwLiongThe bag-of-wordsmodels XiaotaoZou MiningFrequentPatterns,AssociationandCorrelations JustinCletus BasicsofMachineLearning PranavChalla DMLecture3 asad199 My3prep asad199 DataMining:ConceptsandTechniques_Chapter6:MiningFrequentPatterns,... SalahAmean AnIn-DepthEvaluationofMultimodalVideoGenreCategorization IonutMironica Lecture10mingyang-facerecognitionsystems mustafasarac DeepLearning-인공지능기계학습의새로운트랜드:김인중 datasciencekorea 1.11.associationmining3 Krish_ver2 Conceptbasedshorttextclassificationandranking 祺傑林 DMTM2015-13Naivebayes,NearestNeighboursandOtherMethods PierLucaLanzi Textclustering CEG,AnnaUniversity,Chennai gilbert_iccv11_paper AndrewGilbert Report ChrisWatts AJuliapackageforiterativeSVDswithapplicationstogenomicsdataanalysis JiahaoChen Datapreprocessing TonyNguyen RelatedBooks Freewitha30daytrialfromScribd Seeall SoYouWanttoStartaPodcast:FindingYourVoice,TellingYourStory,andBuildingaCommunityThatWillListen KristenMeinzer (3.5/5) Free Bezonomics:HowAmazonIsChangingOurLivesandWhattheWorld'sBestCompaniesAreLearningfromIt BrianDumaine (4.5/5) Free Autonomy:TheQuesttoBuildtheDriverlessCar—AndHowItWillReshapeOurWorld LawrenceD.Burns (5/5) Free NoFilter:TheInsideStoryofInstagram SarahFrier (4.5/5) Free TalktoMe:HowVoiceComputingWillTransformtheWayWeLive,Work,andThink JamesVlahos (4/5) Free SAM:OneRobot,aDozenEngineers,andtheRacetoRevolutionizetheWayWeBuild JonathanWaldman (5/5) Free FromGutenbergtoGoogle:TheHistoryofOurFuture TomWheeler (3.5/5) Free TheFutureIsFasterThanYouThink:HowConvergingTechnologiesAreTransformingBusiness,Industries,andOurLives PeterH.Diamandis (4.5/5) Free LifeAfterGoogle:TheFallofBigDataandtheRiseoftheBlockchainEconomy GeorgeGilder (4/5) Free EverybodyLies:BigData,NewData,andWhattheInternetCanTellUsAboutWhoWeReallyAre SethStephens-Davidowitz (4.5/5) Free FuturePresence:HowVirtualRealityIsChangingHumanConnection,Intimacy,andtheLimitsofOrdinaryLife PeterRubin (4/5) Free LiveWorkWorkWorkDie:AJourneyintotheSavageHeartofSiliconValley CoreyPein (4.5/5) Free Driven:TheRacetoCreatetheAutonomousCar AlexDavies (4.5/5) Free MadeinChina:APrisoner,anSOSLetter,andtheHiddenCostofAmerica'sCheapGoods AmeliaPang (4.5/5) Free HotSeat:WhatILearnedLeadingaGreatAmericanCompany JeffImmelt (5/5) Free LadiesGetPaid:TheUltimateGuidetoBreakingBarriers,OwningYourWorth,andTakingCommandofYourCareer ClaireWasserman (5/5) Free RelatedAudiobooks Freewitha30daytrialfromScribd Seeall DignityinaDigitalAge:MakingTechWorkforAllofUs RoKhanna (4/5) Free IfThen:HowtheSimulmaticsCorporationInventedtheFuture JillLepore (4.5/5) Free Liftoff:ElonMuskandtheDesperateEarlyDaysThatLaunchedSpaceX EricBerger (5/5) Free TheScienceofTimeTravel:TheSecretsBehindTimeMachines,TimeLoops,AlternateRealities,andMore! ElizabethHowell (3/5) Free TheQuietZone:UnravelingtheMysteryofaTownSuspendedinSilence StephenKurczy (4.5/5) Free TheWiresofWar:TechnologyandtheGlobalStruggleforPower JacobHelberg (4.5/5) Free SystemError:WhereBigTechWentWrongandHowWeCanReboot RobReich (4.5/5) Free AnUglyTruth:InsideFacebook’sBattleforDomination SheeraFrenkel (4.5/5) Free ABriefHistoryofMotion:FromtheWheel,totheCar,toWhatComesNext TomStandage (4.5/5) Free ThePlayersBall:AGenius,aConMan,andtheSecretHistoryoftheInternet'sRise DavidKushner (4.5/5) Free BitcoinBillionaires:ATrueStoryofGenius,Betrayal,andRedemption BenMezrich (4.5/5) Free DigitalRenaissance:WhatDataandEconomicsTellUsabouttheFutureofPopularCulture JoelWaldfogel (3.5/5) Free UserFriendly:HowtheHiddenRulesofDesignAreChangingtheWayWeLive,Work,andPlay CliffKuang (4.5/5) Free AWorldWithoutWork:Technology,Automation,andHowWeShouldRespond DanielSusskind (4.5/5) Free LeanOut:TheTruthAboutWomen,Power,andtheWorkplace MarissaOrr (4.5/5) Free Blockchain:TheNextEverything StephenPWilliams (4/5) Free 多媒體資料庫(New)3rd 1. 多媒體資料庫 2. 提綱
  • 簡介
  • 多媒體資料庫的挑戰
  • 多維度索引技術
  • 文件資料庫
  • 影像資料庫
  • 音訊資料庫
  • 視訊資料庫
  3. 簡介
  • 多媒體資料與傳統資料庫之比較
  • 資料內容
  • 傳統資料庫
  • 以文字的方式儲存，常以多個屬性描述一個實體或物件
  • 多媒體資料庫
  • 為涵義豐富的媒體，內容無法單純以多個屬性將其描述
  • 資料展示
  • 傳統資料庫
  • 文字，表單
  • 多媒體資料庫
  • 需要更豐富的視覺聽覺之展示
  4. 簡介
  • 範例
  • 將圖片以傳統資料庫的方式處理儲存
  • 可下達的查詢
  • 找出XXX所畫的圖片
  • 找出在1945~1955年，由OOO所繪製的圖片
  • 無法處理的查詢
  • 找出與此圖片相類似的圖片
  • 找出左上角有一台紅色車子的圖片
  5. 簡介
  • 多媒體資料庫必須能提供
  • 有效率之多媒體資料之儲存
  • 提供內涵式資料的查詢
  • 與媒體本身內容相關之查詢
  • 多樣性的多媒體資料之展示
  6. 多媒體資料庫的挑戰
  • 大量資料之處理
  • 多媒體資料所需之儲存空間比一般資料大得多
  • 多維資料之索引
  • 快速的搜尋技巧
  • 相似度之計算
  • 容錯式的查詢
  • 資料之展示
  7. 多維度索引技術
  • 如何將使用者查詢的結果快速正確的回傳，是很重要的問題
  • 資料量大，逐筆搜尋比對耗費過多的時間
  • 避免逐筆比對搜尋
  • 對資料建立索引加快查詢
  • 索引可視為一種分類的指標，依據索引的指示，即可找到與查詢相關的資料。
    
    
  8. 多維度索引技術
  • 在傳統資料庫中常見的索引結構
  • B+-tree
  • 最廣為使用的索引結構
  • Hash
  • Statichashing
  • Dynamichashing
  • Gridfile
  • Bitmapindex
  9. B+-Tree簡介
  • B+-Tree為一樹結構，且符合下列特性
  • 為一棵平衡樹，所有的葉節點到根節點的路徑長度皆相同
  • 對於所有的非根節點以及非葉節點，必須擁有n/2~n個子節點
  • 葉節點必須擁有(n-1)/2~n-1值
  10. B+-Tree節點結構
  • Ki為搜尋值
  • Pi為指向子節點的指標(fornonleafnodes)或為指向資料的指標(forleafnodes).
  • 節點內的搜尋值為排序過的K1
  11. 葉節點結構
  • 葉節點之特性
  • 對於i=1,2,...,n-1，i不是指向一個擁有搜尋值Ki的資料記錄就是指向一個存取單元((bucket)，而這個存取單元只包含擁有搜尋值Ki的資料
  • Pn指向下一個葉節點
  12. 非葉節點結構
  • 在被Pi指到的搜尋樹內所有的搜尋值皆小於Ki-1
  • 在被Pi指到的搜尋樹內所有的搜尋值皆大於或等於Ki
  13. 範例 14. 討論
  • B+-tree對於傳統表單資料庫的搜尋十分有效率，且廣為被使用
  • 然而
  • B+-tree為單一維度的索引結構
  • 多媒體資料的特性
  15.
  • 多媒體資料的特徵
  • 文件
  • 內容
  • 關鍵字
  • 圖片
  • 主要構成顏色
  • 包含物件
  • 物件大小
  • 顏色分佈
  • 紋理特徵…
  16.
  • 音樂
  • 節拍
  • 和絃
  • 音調…
  • 影片
  • 物體之移動軌跡
  • 包含物件
  • 顏色…
  • 可以依內涵資訊為查詢條件
  • 找出與某張圖相像的圖
  • 找出包含類似某段旋律之歌曲
  • 找出有機車飛越火車的影片片段
  17.
  • 一個多媒體資料是由多個特徵所描述，可由多維資料表示
  • 然而B-tree,B+-tree
  • 僅能對單一維度的資料做索引
  • 不適用於多維度資料
  • 如何對多維度資料建立索引加速查詢，對多媒體資料的搜尋十分重要。
    
    
  18. 多維度上的索引結構
  • k-dtree
  • 用來儲存k–dimension的資料
  • 在一個層級(level)中只比一個維度的資料
  • 在節點N所在層級比較的維度上，在節點N所指到的左子樹內所有的資料其該維度的值皆比節點N該維度的值小，而右子樹的值則皆大於或等於節點N該維度的值
  19.
  • 範例
  21.
  • 隨堂練習
  • 考慮當k>2時的k-dtree
  • 自己試試看
  • 將A(30,24,58),B(46,78,33),C(20,33,15),D(58,40,50),E(40,88,56),F(38,54,44)插入k-dtree中
  • 請利用你所建立的k-dtree，找出與X(34,50,46)距離在15以內的點
  • 刪除時如何處理?
  22.
  • 優點
  • 簡單
  • 缺點
  • 樹的高度會因資料插入順序的不同而不同
  • 很可能造成一棵歪斜樹
  • 搜尋的效率將會變得十分差
  • 資料刪除的過程較為複雜
  23. 多維度上的索引結構
  • Mx-quadtree
  • 樹的形狀與插入的點的個樹以及順序無關。
    
    
  • 設計者必須決定一個k，而k一旦決定，則無法更改。
    
    
  • 整個地圖會被切成個格子
  • 刪除與插入的步驟十分簡單
  24.
  • 範例
  • 假設k=2
  • 地圖被切成個格子
  • 將A,B,C,D四個點放入MX-quad-tree中
  26. 多維度上的索引結構
  • R-tree
  • 為一棵平衡的樹
  • 針對大量資料的儲存十分有用
  • 可減少大量的磁碟存取
  • 一個R-tree的節點有k個指標
  • 除了根節點與葉節點外，每一個節點必須包含至k個非空的指標
  • 控制磁碟存取的次數
  27.
  • 葉節點包含真正的資料
  • 中間節點包含真正資料的群組輪廓，以長方形來表示
  • 左上角以及右下角
  • 可為多維度
  • 插入與刪除包括了節點的分裂以及整合，較為複雜。
    
    
  28.
  • 範例
  • 總共有八個物件
  • 兩維空間
  • 假設k=3
  29. 插入p14R1R2R3R4R5p6p7p5p1p2Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p2p3p4p5p9p10p11p12p13R1R2p14 30. insertingp14R1R2R3R4R5p6p7p5p1p2Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p2p3p4p5p9p10p11p12p13p14p14R1R2 31.
  • 刪除p2
  p14R1R2R1R2R3R4R5p6p7p5p1p2Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p2p3p4p5p9p10p11p12p13p14 32.
  • 找出包含P2的MBR
  R1R2R1R2R3R4R5p6p7p5p1p2Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p2p3p4p5p9p10p11p12p13p14p14 33.
  • R3不滿足R-tree的定義(underflow)
  R1R2R1R2R3R4R5p6p7p5p1Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p3p4p5p9p10p11p12p13p14p14 34.
  • 與鄰近的Boundingrectangle合併
  R1R2R1R2R3R4R5p6p7p5p1Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p3p4p5p9p10p11p12p13p14p14 35.
  • 將R3和R4重新整理，修改個別的左上角以及右上角之值
  R1R2R3R4R5p6p7p5p1Pointerstodatatuplesp8p3p4p9p10p11p12p13R6R7R3R4R5R6R7p1p7p6p8p3p4p5p9p10p11p12p13p14p14R1R2 36. 另一種簡單之整合單一維度索引之多維索引結構
  • 一個多媒體物件會包含的特徵為多維的
  • 假設一張圖片我們以平均的R(紅),G(綠),B(藍)當為特徵
  • 特徵空間為三維
  • 範例
  37.
  • 假設資料庫內有十張圖
  P1P3P2P5P4 38. P6P10P9P8P7 39.
  • 有下列三個查詢
  40.
  • 我們得到下列的R,G,B的平均值
  41.
  • Case1:假設我們要找到與查詢圖片Q1相似度在0.15內的圖片
  • Q1=(0.478,0.541,0.753),r=0.15
  • 資料庫內找出個個維度與查詢最近的值
  • (0.451,0.447,0.561)
  • (|0.478-0.451|,|0.541-0.447|,|0.753-0.561|)
  • =>(0.027,0.094,0.192)
  • 所以沒有符合查詢的資料
  >0.15 42.
  • Case2:假設我們要找到與查詢圖片Q2相似度在0.02內的圖片
  • Q2=(0.302,0.310,0.416),r=0.02
  • 第一步:在資料庫內找出個個維度與查詢最近的值
  • (0.318,0.302,0.400)
  • (|0.302-0.318|,|0.310-0.302|,|0.416-0.400|)
  皆小於0.02，故必須進行第二步驟 43.
  • 第二步驟:由第一個維度開始檢查，並將容許的錯誤減掉之前已用到的額度
  • 第一維可用的誤差額度為:0.02
  • 第二維可用的誤差額度為:(0.022-0.0162)1/2
  • 第三維可用的誤差額度為:(0.022-0.0162-0.0082)1/2
  大於已知之最小誤差0.016，所以資料庫內沒有符合查詢的資料存在 44.
  • Case3:假設我們要找到與查詢圖片Q3相似度在0.05內的圖片
  • Q3=(0.302,0.223,0.161),r=0.05
  • (|0.302-0.318|,|0.223-0.200|,|0.161-0.161|)
  • =>(0.016,0.023,0)G>R>B
  • 第一步驟無法決定資料庫內沒有欲查詢的資料
  45.
  • 搜尋G上的索引,找出在0.223+-0.05=[0.173,0.273]範圍內的圖
  • {P7,P6,P2}
  • 搜尋R上的索引,找出在0.302+-(0.044)=[0.258,0.346]範圍內的圖
  • {P2,P8}
  • 搜尋B上的索引，找出在0.161+-0.041=[0.120,0.202]範圍內的圖
  • {P2,P5,P9}
  • 將結果整合，得到P2為符合查詢之資料
  46. 演算法 52. 文件資料庫
  • 導論
  • 文件內容的分析
  • 同意字(Synonymy)
  • 一辭多義(Polysemy)
  • 搜尋結果之評估
  • Precision
  • 找到的文件正確的機率
  • Recall
  • 相關的文件被找到的機率
  53. 文件資料庫
  • Precision=
  • Recall=
  所有的文件相關的文件搜尋所得之結果 54. 文件資料庫
  • Precision/recall之計算範例
  • 請探討precision/recall之關係
  所有的文件相關的文件搜尋所得之結果5015020 55. 文件資料庫
  • 文件內容之描述
  • Stoplists
  • 文件內可被忽略的字，如:a,the,he…
  • Wordstems
  • 同一個字各種不同之時態或單複數等等
  • Frequencytables
  0010boat0220slip2000connection3001videotape3101drug0001sexd4d3d2d1Term/文件 56. 文件資料庫
  • 查詢處理
  • 文件相關性之計算
  • 字詞距離
  • Cosine距離
  57. 文件資料庫
  • 查詢型態
  • 找出包含某些字詞的文件
  • 找出包含某些字詞但不包含另一些字詞的文件
  • 找出離查詢向量最近的文件
  • 找出離查詢向量最近的前k個文件
  • 找出與查詢向量距離之內的文件
  58. 文件資料庫
  • 使用索引
  • R-tree
  • 不適用於高維索引結構
  • TV-tree
  • 與R-tree類似,但在一各節點,只考慮部分維度的關係
  • Invertedlist
  • Signaturefiles
  59. 文件資料庫
  • Invertedlist(反轉串列)
  • 以字詞為主所形成的反轉表
  • 以table為例
  • Sex:d1
  • Drug:d1,d3,d4
  • Videotape:d1,d4
  • 搜尋範例以及型態
  • and,or,not
  • 無法處理相似度查詢
  • 缺點
  • Size大
  • 壓縮技巧
  60. 文件資料庫
  • Signaturefiles
  • 每個關鍵字有它所對應的code
  • 對一文件而言,該文件的signature即為將其所包含的關鍵字的codesuperimpose在一起
  • 搜尋範例
  • 可處理之查詢型態
  • And,Or
  • Not?
  61. 文件資料庫
  • 討論
  • R-tree,TV-tree可處理相似度的查詢
  • Invertedindices,Signaturefiles無法處理相似度的查詢，只能處理包含某些字詞的查詢
  • Signaturefiles不適合處理不包含某個(些)字詞的查詢
  • 請舉例說明
  • R-tree不適合高維度的資料
  62. 影像資料庫
  • 查詢範例
  • 範例一:找出與這張圖相像的圖片
  • 範例二:找出左上角有一個紅色方形，而圖形的下方為藍色的所有圖片
  • 可代表一張影像的資訊
  • 與影像內涵資訊無關之資訊
  • 作者
  • 完成時間
  • 完成地點
  • etc..
  63.
  • 與影像內涵資訊相關的特徵
  • 顏色分佈
  • 可以colorhistogram表示
  • 紋理
  • 內含物件
  • 形狀
  • 顏色
  • 大小
  • 位置
  • 主要構成顏色
  • Etc.
  64. 影像資料庫搜尋
  • 由關鍵字查詢(QueryByKeyword)
  • 以文字屬性描述每張影像，可以對個個屬性建構索引，並可以SQL的方式下查詢
  • 以範例查詢(QueryByExample(QBE)):
  • 使用者對系統展示一張範例圖，系統則根據資料庫內每張圖與這張範例圖的相似度決定回傳的答案
  • 查詢型態
  • 找出離查詢範例最近的影像
  • 找出離查詢範例最近的前k個影像
  • 找出與查詢範例距離之內的影像
  65. 影像距離與相似度
  • ColorSimilarity
  • TextureSimilarity
  • ShapeSimilarity
  • Object&Relationshipsimilarity
  66. 顏色相似度(ColorSimilarity)
  • 顏色佔的比例
  • Ex:R:20%,G:50%,B:30%
  • 顏色分布圖(Colorhistogram)
  • Dhist(I,Q)=(h(I)-h(Q))TA(h(I)-h(Q))
  • Aisasimilaritymatrixcolorsthatareverysimilarshouldhavesimilarityvaluesclosetoone.
  67. 顏色配置
  • Colorlayoutmatching:compareseachgridsquareofthequerytothecorrespondinggridsquareofapotentialmatchingimageandcombinestheresultsintoasingleimagedistance
  • whereCI(g)representsthecoloringridsquaregofadatabaseimageIandCQ(g)representsthecolorinthecorrespondinggridsquaregofthequeryimageQ.somesuitablerepresentationsofcolorare
  • Mean
  • Meanandstandarddeviation
  • Multi-binhistogram
  68. 材質相似度(TextureSimilarity)
  • Pickandclick
  • SupposeT(I)isatexturedescriptionvectorwhichisavectorofnumbersthatsummarizesthetextureinagivenimageI(forexample:Lawstextureenergymeasures),thenthetexturedistancemeasureisdefinedby
  • Texturelayout
  69. 形狀相似度(ShapeSimilarity)
  • ShapeHistogram
  • BoundaryMatching
  • SketchMatching
  70.
  • 以內容來看，三張圖相像嗎?
  • 顏色資訊
  • 位置資訊
  實作範例Image-AImage-BImage-C 71. ColormodelRGBcolorspacev.s.HSVcolorspace 72.
  • 顏色與位置資訊的取得
  • 將圖切成一個一個的格子
  • 找出每個格子的代表色
  • 相鄰格子有相同的顏色，及組合成更大的格子
  • 最後的大區塊的顏色，位置及形狀是將來比對上所使用的重大資訊。
    
    
  74. 相似度比較
  • 兩張圖要相似有哪些因素是可能被使用者考慮的?
  • 顏色配置
  • 顏色分布
  • 物件位置
  • 物件大小
  • 物件形狀
  77. 範例SIZE=13+10+5=28QueryimageA13B10C5 78.
  • 聽看看下面幾首音樂或音樂片段，你知道歌名是什麼嗎？Music12345678910
  • 你是怎麼辦識出這首歌的呢？若要讓電腦幫我們做同樣的事，要怎麼設計呢？
  音樂資料庫 79. 音樂的特徵
  • StaticMusicInformation如調號、拍號等
  • AcousticalFeature如loudness、pitch等
  • ThematicFeature如melodies、rhythms及chords例“sol-sol-sol-mi”、”0.5-0.5-0.5-2”及“C-Am-Dm-G7”
  • StructuralFeature古典音樂格式的二個基本規則hierarchicalrule及repetitionrule
  80. 特徵的取樣
  • 相對音感vs絕對音感—旋律的位移
  • 考慮以絕對音感比對所會造成的問題
  • 升key,降key所發生的問題
  • 節拍取樣也有相同的問題
  • 依完整段落取pattern
  • 多音軌的取樣問題
  81. 特徵的編碼
  • 將特徵取出後，依適當的編碼方式將特徵標碼
  • 能應付音調的升降
  • 能應付節拍的快慢
  • 要讓聽起來像的音樂，其編碼出來的code之間的距離也要近
  82. 範例
  • 利用重複出現的重要音調代表某首歌
  • Hierarchicalrulemusicobject->movements->Sentences->phrases->figures
  • Repetitionrule如“C6-Ab5-Ab5-C6”及“F6-C6-C6-Eb6”
  83. 重複出現的式樣—定義
  • ForasubstringXofasequenceofnotesS,ifXappearsmorethanonceinS,wecallXarepeatingpatternofS.TherepeatingfrequencyoftherepeatingpatternX,denotedasfreq(X),isthenumberofappearancesofXinS.ThelengthoftherepeatingpatternX,denoted|X|,isthenumberofnotesinX.
  84. 重複出現的式樣—實例
  • “C-D-E-F-C-D-E-C-D-E-F”RP:RepeatingPatternRPF:RepeatingPatternFrequency
  23332RPFFEDCE-FRP33232RPFD-EC-DD-E-FC-D-EC-D-E-FRP 85. 重複出現的式樣
  • nontrival的定義ArepeatingpatternXisnontrivialifandonlyiftheredoesnotexistanotherrepeatingpatternYsuchthatfreq(X)=freq(Y)andXisasubstringofY.
  • 實例上頁的10個RP中，只有“C-D-E-F”及”C-D-E”為nontrival
  86. TheCorrelative-Matrix(1)
  • Phrase
  • MelodystringS=“C6-Ab5-Ab5-C6-C6-Ab5-Ab5-C6-Db5-c6-Bb5-C6”
  • RepeatingPatterns
  Ab514C616C6-Ab5-Ab5-C642RPPL(PatternLength)RPF 87. TheCorrelative-Matrix(2)ConstructionofcorrelativematrixT12,12--C6--Bb51--C6--Db511--C6--Ab51--Ab5111--C61141--C631--Ab5121--Ab511111--C6C6Bb5C6Db5C6Ab5Ab5C6C6Ab5Ab5C6 88. TheCorrelative-Matrix(3)
  • FindallRPsandtheirRFs.
  • 定義candidatesetCS其格式為(pattern,rep_count,sub_count)
  • CS一開始為空集合，接下來根據T來計算及insertRP到CS內
  • 因為條件有(Ti,j=1)or(Ti,j>1)及(T(i+1),(j+1)=0)or(T(i+1),(j+1)<>0),所以有以下四種情形
  89. TheCorrelative-Matrix(4)
  • Case1:(Ti,j=1)and(T(i+1),(j+1)=0)例T1,4=1,T2,5=0insert(“C6”,1,0)intoCS
  • Case2:(Ti,j=1)and(T(i+1),(j+1)<>0)例T1,5=1,T2,6=2modify(“C6”,1,0)into(“C6”,2,1)
  • Case3:(Ti,j>1)and(T(i+1),(j+1)<>0)例T2,6=2,T3,7=3insert(“C6-Ab5”,1,1),(“Ab5”,1,1)intoCS
  • Case4:(Ti,j>1)and(T(i+1),(j+1)=0)例T4,8=4,T5,9=0insert(C6-Ab5-Ab5-C6”,1,0),(“Ab5-Ab5-C6”,1,1)and(“Ab5-C6”,1,1)intoCSandchange(“C6”,6,1)into(“C6”,7,2)
  90. TheCorrelative-Matrix(5)
  • 計算RFrep_count=0.5f(f-1)即f=((1+SQRT(1+8*rep_count))/2例如本例中(“C6”,15,1),即C6的rep_count=15,所以f=((1+SQRT(1+8x15))/2=6同理“Ab5”的RF為4,“C6-Ab5-Ab5-C6”的RF為2
  91. TheString-JoinApproach(1)
  • Melodystring“C-D-E-F-C-D-E-C-D-E-F”
  • 第一步:找出所有長度為1的RPs,並記為{X,freq(X),(position1,position2,…)}如本例可找到{“C”,3,(1,5,8)},{“D”,3,(2,6,9)},{E”,3,(3,7,10)},and{“F”,2,(4,11)}
  92. TheString-JoinApproach(2)
  • 接下來長度為2的RPs可由上面的RPs經joining(記為“∞”)而得例如若要找“C-D”,已知{“C”,3,(1,5,8)},{“D”,3,(2,6,9)}則可確定“C-D”亦出現在(1,5,8),可表示為{“C”,3,(1,5,8)}∞{“D”,3,(2,6,9)}={“C-D”,3,(1,5,8)}
  93. TheString-JoinApproach(3)
  • 同理{“D”,3,(2,6,9)}∞{“E”,3,(3,7,10)}={“D-E”,3,(2,6,9)}{“E”,3,(3,7,10)}∞{“F”,2,(4,11)}={“E-F”,2,(3,10)}
  • 而長度為4的,可由長度為2的join而得如{“C-D”,3,(1,5,8)}∞{“E-F”,2,(3,10)}={“C-D-E-F”,2,(1,8)}
  94. TheString-JoinApproach(4)
  • 長度為3的,因為freq(“C-D-E-F”)=freq(“E-F”)=2,可知不只“E-F”是trivial,”D-E-F”也是(否則freq(“E-F”)要大於2)而{“C-D”,3,(1,5,8)}∞{“D-E”,3,(2,6,9)}={“C-D-E”,3,(1,5,8)}且freq(“C-D-E”)>freq(“C-D-E-F”)所以“C-D-E”為nontrivial
  • 最後,得知此例的nontrivialrepeatingpatterns為“C-D-E-F”及“C-D-E”
  95. 討論
  • 相對音感vs絕對音感—旋律的位移
  • 依完整段落取pattern
  • 不同音樂格式的轉換
  • 問題—重要卻沒重覆的feature
  96. 視訊資料庫
  • 內容組織
  • 使用者會對哪一部分的內容感興趣
  • 如何儲存這部分的內容，使得查詢處理能很有效率的被執行
  • 如何設計查詢語言，與傳統的SQL有何不同
  • 影片的內容可自動的被取出來嗎?
  97. 影片內涵資訊
  • 物件
  • 單純形狀的描述
  • 可做到自動化
  • 有意義的物件描述
  • 人物
  • 男主角，女主角…
  • 動物
  • 豬，貓，狗…
  • 非生物
  • 皮箱，鑰匙…
  • 幾乎不可能做到自動化
  98.
  • 活動
  • 單純描述
  • 物件移動軌跡
  • 如何將軌跡編碼成電腦可比對的code為一個很重要的課題
  • 可做到自動化
  • 含有意義的行為描述
  • 車禍，甲男把皮箱交給乙女…
  • 必須用單純描述做為基礎描述
  • 不容易做到完全自動化
  99. 視訊內涵資訊之建構
  • 兩種資訊
  • 靜態
  • 將一個frame視為一張圖片
  • 利用圖片搜尋技巧
  • 動態
  • 將連續frame視為一個動作
  • 物件移動軌跡必須被考慮
  100.
  • 靜態資訊
  101.
  • 動態資訊
  102. Preface(Cont’d)
  • 移動軌跡
  103.
  • 影片分析
  • Shot
  • 單一連續的鏡頭所拍攝之影片段落
  • 組成影片的單位
  • 同一個shot內的frame內容類似
  • 可以在一個shot中找出其代表的frame，來表示整個shot
  • Shot偵測
  • 利用顏色分佈的改變偵測shot的界線(boundary)
  • 可自動化,但可能會因顏色的突然改變而誤找
  • 目前shotsegmentation工具可以達到一各十分高的正確率(>95%)
  104.
  • 場景(SCENE)
  • 由多個描述相同事件的shot所組成
  • 可當作查詢的單位
  • 物件移動軌跡
  • 找出物體移動的軌跡，可代表某一事件
  105. 涵義概念式查詢
  • 可下達語意式的查詢
  • 找出包含天空以及海的圖片
  • 找出有飛機飛過天空的影片
  • 以低階(lowlevel)特徵值的關聯,找出媒體之內涵意義
  • 半自動分類
  • Classification
  • Associationpatternmining
  • Concept與Semanticnetwork
  106. Classification
  • 目標
  • 預測資料之類別
  • 步驟
  • 建立資料分類模型
  • 根據訓練資料集(trainingset)
  • 評估資料分類模型的準確度
  • 根據測試資料集(testingdata)
  • 資料分類預測
  107. TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model) 108. ClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured? 109. Classification
  • 演算法
  • 決策樹(decisiontree)
  • BayesianBeliefNetworks
  • k-nearestneighborclassifier
  • case-basedreasoning
  • Geneticalgorithm
  • Roughsetapproach
  • Fuzzysetapproaches
  • NeuralNetwork
  110. 訓練資料集(trainingdataset) 111. 決策樹age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40 112. NaïvebayesianNetwork:exampleP(n)=5/14P(p)=9/14 113. P(true|n)=3/5P(true|p)=3/9P(false|n)=2/5P(false|p)=6/9P(high|n)=4/5P(high|p)=3/9P(normal|n)=2/5P(normal|p)=6/9P(hot|n)=2/5P(hot|p)=2/9P(mild|n)=2/5P(mild|p)=4/9P(cool|n)=1/5P(cool|p)=3/9P(rain|n)=2/5P(rain|p)=3/9P(overcast|n)=0P(overcast|p)=4/9P(sunny|n)=3/5P(sunny|p)=2/9windyhumiditytemperatureoutlook 114. Play-tennisexample:classifyingX
  • AnunseensampleX=
  • P(X|p)·P(p)=P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582
  • P(X|n)·P(n)=P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286
  • SampleXisclassifiedinclassn
  115. BayesianBeliefNetworksFamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.80.20.50.50.70.30.10.9BayesianBeliefNetworksTheconditionalprobabilitytableforthevariableLungCancer 116. BayesianBeliefNetworks 117. Thek-NearestNeighborAlgorithm._+_xq+__+__+..... 118. RoughSetApproach
  • Roughsetsareusedtoapproximatelyor“roughly”defineequivalentclasses
  • AroughsetforagivenclassCisapproximatedbytwosets:a
  • lowerapproximation(certaintobeinC)
  • upperapproximation(cannotbedescribedasnotbelongingtoC)
  119. Fuzzysetapproach 120. Associationpatternmining
  • 目標
  • 尋找項目(item)或物件間的關聯性
  • 關聯性
  • 一起出現的次數要夠多(support)
  • 伴隨出現之條件機率值要夠大(confidence)
  • 演算法
  • Apriorialgorithm
  • Latticeapproach
  • FP-tree
  121. 探勘關聯式法則:範例
  • ForruleAC:
  • support=support({AC})=50%
  • confidence=support({AC})/support({A})=66.6%
  • TheAprioriprinciple:
  • Anysubsetofafrequentitemsetmustbefrequent
  Min.support50%Min.confidence50% 122. Apriori演算法
  • JoinStep:CkisgeneratedbyjoiningLk-1withitself
  • PruneStep:Any(k-1)-itemsetthatisnotfrequentcannotbeasubsetofafrequentk-itemset
  • Pseudo-code:
  • Ck:Candidateitemsetofsizek
  • Lk:frequentitemsetofsizek
  • L1={frequentitems};
  • for(k=1;Lk!=;k++)dobegin
  • Ck+1=candidatesgeneratedfromLk;
  • foreachtransactiontindatabasedo
  • incrementthecountofallcandidatesinCk+1thatarecontainedint
  • Lk+1=candidatesinCk+1withmin_support
  • end
  • returnkLk;
  123. 範例DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD 124. FP-tree演算法
  • 把一大型資料庫壓縮至一緊實的資料結構
  • FP-tree
  • 只包含探勘關聯式樣式所需之相關資料
  • 避免花費高昂的資料庫掃描
  125. FP-tree建置過程min_support=0.5TIDItemsbought(ordered)frequentitems100{f,a,c,d,g,i,m,p}{f,c,a,m,p}200{a,b,c,f,l,m,o}{f,c,a,b,m}300{b,f,h,j,o}{f,b}400{b,c,k,s,p}{c,b,p}500{a,f,c,e,l,p,m,n}{f,c,a,m,p}
  • Steps:
  • ScanDBonce,findfrequent1-itemset(singleitempattern)
  • Orderfrequentitemsinfrequencydescendingorder
  • ScanDBagain,constructFP-tree
  126. {}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf4c4a3b3m3p3 127. FP-tree主要探勘過程
  • 對FP-tree內的每個node,建置conditionalpatternbase
  • 對每一個conditionalpattern-base建置conditionalFP-tree
  • 重複上面步驟，一直到
  • FP-tree只剩下單一路徑
  128. Step1:對FP-tree內的每個node,建置conditionalpatternbaseConditionalpatternbasesitemcond.patternbasecf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf4c4a3b3m3p3 129. Step2:對每一個conditionalpattern-base建置conditionalFP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam
  • m-conditionalpatternbase:
  • fca:2,fcab:1
  {}f:3c:3a:3m-conditionalFP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf4c4a3b3m3p3 130. MiningFrequentPatternsbyCreatingConditionalPattern-BasesEmptyEmptyf{(f:3)}|c{(f:3)}c{(f:3,c:3)}|a{(fc:3)}aEmpty{(fca:1),(f:1),(c:1)}b{(f:3,c:3,a:3)}|m{(fca:2),(fcab:1)}m{(c:3)}|p{(fcam:2),(cb:1)}pConditionalFP-treeConditionalpattern-baseItem 131. Step3:RecursivelyminetheconditionalFP-treeCond.patternbaseof“am”:(fc:3)Cond.patternbaseof“cm”:(f:3){}f:3cm-conditionalFP-treeCond.patternbaseof“cam”:(f:3){}f:3cam-conditionalFP-tree{}f:3c:3a:3m-conditionalFP-tree{}f:3c:3am-conditionalFP-tree 132. 效能分析DatasetT25I20D10K 133. Associationpatternmining
  • 傳統Associationpatternmining幾乎都是找出項目和項目間的關聯性
  • 在多媒體應用中
  • 互斥之關係亦十分重要
  • 可幫助分類的準確性
  134. Concepts與Semanticnetwork
  • 概念(concepts)
  • 知識表達之基本觀念
  • Semanticnotionsoftheobjectsintheworld
  135. Concepts與Semanticnetwork
  • 概念之間的關係
  • 多重解析度(multi-resolution)
  136. Concepts與Semanticnetwork
  • Semanticnetwork
  • 節點
  • 物件,觀念或狀態
  • 連結
  • 節點之間的關聯
  138.
  • 參考資料
  • V.S.Subrahmanian,PrinciplesofMultimediaDatabaseSystems,MorganKaufmann.
  • C.Y.Tsai,A.L.P.ChenandK.Essig,”EfficientImageRetrievalApproachesforDifferentSimilarityRequirements”,Proc.SPIEConferenceonStorageandRetrievalforImageandVideoDatabases,2000
  • JiaweiHanandMichelineKamber,DataMining:ConceptsandTechniques,MorganKaufmann,2000.
  139. Content-BasedInteractivity 141. Paperstudy:topic1ASemanticModelingApproachforVideoRetrievalbyContentEdoardoArdizzoneMohand-SaidHacidICMCS1999July 142. Introduction
  • Usingkeywordsorfreetexttodescribethenecessarysemanticobjectsisnotsufficient.
  • Theissuesthatneedtobeaddressedis
  • therepresentationofvideoinformation
  • theorganizationofthisinformation
  • user-friendlyrepresentation
  143. Introduction(cont.)
  • Weexploitthe2languages
  • Onefordefiningtheschema(i.e.the
  • structure)
  • Theotherforqueryingthroughschema
  • And2layersforrepresentingvideo`sconceptualcontent
  • Objectlayer
  • Schemalayer
  144. 2Layersforvideo`sconceptualcontent
  • Objectlayer:collectobjectsofinterest,theirdescriptionandrelationamongthem.Objectsinvideosequencearerepresentedasvisualentities.
  • Schemalayer:intendtocapturethestructureandknowledgeforvideoretrieval.Visualentitiescanbeclassifiedintohierarchicalstructure.
  145. SchemaLanguage—example1 146. QueryLanguage(QL)
  • QueryingaDBmeansretrievingstoredobjectsthatsatisfycertainconditionsorqualificationsandhenceareinterestingforauser.
  • InOODB,classesareusedtorepresentsetsofobjects.
  147. QLcont.
  • Queriesarerepresentedasconceptsinourabstractlanguage.
  • Thesyntaxandsemanticsofaconceptlanguageformakingqueries
  148. QL-Example
  • “SequencesofmoviesdirectedbyKevinCostnerinwhichheisalsoanactor”
  149. QL-Example
  • “thesetofmovieswhosedirectorsarealsoproducersofsomefilms”
  150. SemanticAnnotationofSportsVideo
  • Videosisn`tjustasequenceofimages.Itaddthetemporaldimension.
  • Anapproachforsemanticannotationofsportsvideosthatincludeseveraldifferentsportsandevennon-sportscontent
  151. Introduction--Typicalsequenceofshotsinsportsvideo 153. Classifyingvisualshotfeatures 154. Implementation--Classifyingvisualshotfeatures(cont.) 155. Conclusion
  • Thereisagrowinginterestinvideodatabaseandfordealingwithaccessproblems.
  • Oneofthecentralproblemsinthecreationofrobustandscalablesystemsformanipulatingvideoinformationliesinrepresentingvideocontent
  156. Conclusioncont.
  • Thisframeworkisappropriateforsupportingconceptualandintensionalqueries
  • Beabletoperformexactaswellaspartialorfuzzymatching
  • somephysicalfeatures:color,objects’sshape…ect.
  157. Paperstudy:topic2IndexingmethodsforapproximatestringmatchingIEEEdataengineeringbulletin,2000GonzaloNavarro,RicardoBaeza-Yates,ErkkiSutinen,JormaTarhio 158. outline
  • Introduction
  • Basicconcepts
  • Neighborhoodgeneration
  • Partitioningintoexactsearch
  • Intermediatepartitioning
  • summarization
  159. Introduction
  • Definition
  • givenalongtextT1…..noflengthnandacomparativelyshortpatternP1…..moflengthm，bothsequencesoveranalphabetΣofsizeσ,findthetextpositionsthatmatchthepatternwithatmostk“errors”.
  • Applications
  • Retrievingmusicalpassagessimilartoasample
  • FindingDNAsubsequencesafterpossiblemutations
  • Searchingtextunderthepresenceoftypingorspellingerrors
  160. outline
  • Introduction
  • Basicconcepts
  • Neighborhoodgeneration
  • Partitioningintoexactsearch
  • Intermediatepartitioning
  • summarization
  161. Suffixtrees1gaaccgacct2aaccgacct3accgacct4ccgacct5cgacct6gacct7acct8cct9ct10tWeakpoint:largespacerequirement,about9timesoftextsize. 162. SuffixarrayRequirelessspace,about4timesoftextsizea$aaaabbcdrabbcdrraarraa$caac$$c 163. Q-grams,Q-samplesTEXT123456789101112345INDEXabrabracracaacadcada182345Q-samples,unlikeq-grams,donotoverlap,andmayevenbesomespacebetweeneachpairofsamples.abracadabra 164. Editdistanceed(“SURVEY”,”SURGERY”)Finalresult22233456Y32122345E43211234V43210123R54321012U65432101S76543210YREGRUS 165. outline
  • Introduction
  • Basicconcepts
  • Neighborhoodgeneration
  • Partitioningintoexactsearch
  • Intermediatepartitioning
  • summarization
  166. NeighborhoodgenerationPattern:abcwith1error{＊bc,a＊c,ab＊}U{ab,ac,bc}U{＊abc,a＊bc,abc＊}Textabracadabra{abr},{ac},{abr},..resultsK-NeignborhoodK-neighborhood(candidate)couldbequitelarge,So,thisapproachworkswellforsmallmandk.searching 167. outline
  • Introduction
  • Basicconcepts
  • Neighborhoodgeneration
  • Partitioningintoexactsearch
  • Intermediatepartitioning
  • summarization
  168. PartitioningintoexactsearchPattern:abrwith1error{a},{br}Textabracadabra{abra},{abra}..resultsPartitionpattern1.Forlargeerrorlevelthetextareastoverifycoveralmostalmostallthetext.2.Ifsgrow,piecesgetshorter,morematchtocheck,butmakethefilterstricter.ExactsearchverificationTextabracadabrainto(K+s)piecesfiltration 169. outline
  • Introduction
  • Basicconcepts
  • Neighborhoodgeneration
  • Partitioningintoexactsearch
  • Intermediatepartitioning
  • summarization
  170. IntermediatePartitioningPattern:abrwith1error{a},{br}Textabracadabra{abra},{abra}..resultsPartitionpatternNeighborhoodgenerationallowfloorofk/jverificationTextabracadabraintoj(j=2)piecesJ=2(j=K+1;partitioningintoexactsearch)searching 171. IntermediatePartitioningPattern:abrwith1error{abr}Textabracadabra{abra},{abra}..resultsPartitionpattern1.Whichjvaluetouse?thesearchtimedecreaseswhenjmovefrom1tok+1.buttheverificationcostgrows,oppositiely.Neighborhoodgenerationallowfloorofk/jintoj(j=1)piecesJ=1(neighborhoodgeneration)searching{*abr,a*br,ab*r,abr*}U{ab,br,ar}U{ab*,*br,a*r} 172. outline
  • Introduction
  • Basicconcepts
  • Neighborhoodgeneration
  • Partitioningintoexactsearch
  • Intermediatepartitioning
  • summarization
  173. summarization 174. Paperstudy:topic3LazyUsersandautomaticVideoRetrievalToolsin(the)LowlandsTheLowlandsTeamCWI1,TNO2,UniversityofAmsterdam3,UniversityofTwente4TheNetherlandsJanBaan2,AlexvanBallegooij1,JanMarkGeusenbroek3,JurgendenHartog2,DjoerdHiemstra4,JohanList1,ThijsWesterveld4,IoannisPatras3,StephanRaaijmakers2,CeesSnoek3,LeonTodoran3,JeroenVendrig3,ArjenP.deVries1andMarcelWorring3.Proceedingofthe10thTextRetrievalConference(TREC),2001 175. Outline
  • Introduction
  • Detector-baseprocessing
  • Probabilisticmultimediaretrieval
  • Interactiveexperiment
  • Lazyusers
  • Discussion
  • Conclusion
  176. BasickeysubjectofMultimediadatabase
  • Indexing
  • K-dtree,pointquadtree,MX-quadtree,R-tree,suffix-tree,TV-tree……
  • Determinedbydatabasedesigner.
  • Similarity
  • Nostandard.
  • Howsimilarisdecidebyuser.
  177. UserisalwaysLazy!
  • Facts1:
  • Almostofenduserknownothingabout“Query”.
  • Facts2:
  • Whattheywantmayonlyaconcept,cannotclearlytodescript.
  • Facts3:
  • Userslikeselection,notquestion.
  178. Introduction
  • Usetwocomplementaryautomaticapproach:
  • Visualcontent
  • Transcript
  • Theexperimentfocusonrevealingrelationshipsbetween:
  • Differentmodalities
  • Theamountofhumanprocessing
  • Thequalityofrersults
  179. IntroductionCombined1-4,interactive,byalazyuser5Queryarticulation,interactive4Transcript-base,automatic3Combined1-3,automatic2Detector-base,automatic1DescriptionRun 180. Detector-baseprocessing
  • Architectureforautomaticsyste
  181. Detector-baseprocessing(cont)
  • Detectorforexactqueriesthatyieldyes/noanswerdependingifasetofpredicatesissatisfied.
  • Detectorforapproximatequeriesthatyieldameasurethatexpresseshowsimilaris.
  182. Detector-baseprocessing(cont)SelecteddetectorAnalysisofthetopicdescriptionQuerybyexampleFilter-outirrelevantmaterialFinalrankedresults 183. Detectors
  • Cameratechniquedetection
  • zoom,pan,tilt…….
  • Facedetector
  • noface,1-face,2-faces…5-faces,many-faces
  • Captionretrieval
  • Textsegmentation,OCR,fuzzystringmatching
  • Monologuedetection
  • Shotshouldcontainspeech
  • Shotshouldhaveastaticorunknowncameratechnique
  • Shotshouldhaveaminimumlength
  • Detectorsbaseoncolorinvariantfeatures
  • Keyframesstorewithcolorhistogram
  184. Probabilisticmultimediaretrieval
  • Weassumeourdocumentsareshotsfromvideo.
  • Modelsofdiscretesignals(i.e.text).
  • Mixtureofdiscreteprobabilitymeasures
  • Modelsofcontinuoussignals(i.e.image).
  • Mixtureofcontinuousprobabilitymeasures
  185.
  • UsingBayes’rule:
  • Ifaqueryconsistsofseveralindependentparts(e.g.atextualQtandvisualpartQv)
  Probabilisticmultimediaretrieval 186. Probabilisticmultimediaretrieval
  • Hierarchicaldatamodelofvideo
  videoshotsscenesscenesshotsframesframes 187. Probabilisticmultimediaretrieval
  • Textretrieval
  • UsingSphinx3speechrecognitionsystemfromCarnegieMellonUniversity
  • Inputquerykeyword
  • Retrievaltoshotslevel
  188. Probabilisticmultimediaretrieval
  • Imageretrieval
  • Retrievingthekeyframesofshots
  • Cutkeyframesofeachshotsintoblocksof8x8pixels
  • PerformbyDiscreteCosineTransform(DCT),whichusedintheJPEGcompressionstandard.
  189. Interactiveexperiments
  • Topiclists.
  • http://www-nlpir.nist.gov/projects/t01v/topicsoverview.html
  • Topic33:Whitefort
  • Topic19:Lunarrover
  • Topic8:Jupiter
  • Topic25:Starwar
  190. Topic33:WhitefortUsingRun1:Anycolor-basedtechniqueworkedoutwellforthisqueryExampleknown-itemkeyframe 191. Topic19:LunarroverColor-histogramExampleKnown-itemkeyframe
  • Color-basedretrievaltechniqueisnotusefulinthiscase
  • ByRun4:
  • Allowusertomakingexplicittheirownworldknowledge:inscenesonthemoon,theskyisblack.
  192. Topic8:JupiterExampleSomecorrectanswerskeyframes
  • Atfirstthough,thisquerymayseemtobeeasytosolve.
  • Butitisapparentthatcolorsindifferentphotos.
  • Usingthreecolor-histogramandtheirinterrelationships.
  Color-sets 193. Topic25:StarwarExampleSomecorrectanswerskeyframes
  • Textretrieval:(ifyouknowthename)
  • Thefirstfilterselectsonlythoseimagesthathavesufficientamountofgoldencontent.
  • Secondly,asetoffiltersreducesthedata-setbyselectingthoseimagesthatcontainthecolor-setsshown.
  R2D2,C3PO 194. Lazyusers
  • Lazyusersidentifyresultsetsinsteadofcorrectanswer.(soourinteractiveresultsarenot100%precision.)
  • Thecombinationstrategiesusedtoconstructrun5consistedof:
  ChoosetherunthatlooksbestConcatenateorinterleavetop-NfromvariousrunsContinuewithanautomatic,seededsearchstrategy 195. Discussion
  • Howvideoretrievalsystemsshouldbeevaluated.
  • Theinhomogeneityofthetopics
  • “sailboatonthebeach”vs.“yachtonthesea”
  • Thelowqualityofthedata
  • photosofJupiter
  • Theevaluationmeasuresused
  196. Conclusion
  • Ourevaluationdemonstratestheimportanceofcombiningvarioustechniquestoanalyzethemultiplemodalities.
  • theoptimaltechniquedependsalwaysonthequery.
  • Userinteractionisstillrequiredtodecideuponagoodstrategy.
  197. Paperstudy:topic4VIDEOINDEXINGBYMOTIONACTIVITYMAPSWeiZeng;WenGao;DebinZhao;ImageProcessing.2002.Proceedings.2002InternationalConferenceon,Volume:1,2002Page(s):912-915 198. Outline
  • Introduction
  • motionindexing
  • MotionActivityMap---MAM
  • DefinitionofMAM
  • GenerationofMAM
  • OrganizationofMAMs
  • Experimentalresults
  • Conclusion
  199. Introduction
  • Tofindavideoindexingtechniquewhichcouldextractcrucialinformationfromvideosforefficientvisualcontent-basedqueries.
  • Inordertofosterthecontent-basedindexingandretrieval.
  • Thevideoindexingshouldbebasedongoodfeaturerepresentationsuchasmotionfeature.
  • Motionfeaturedepictsthedynamiccontentsofvideo,andenrichthesemanticsofvideos,suchasrunningandflying.
  200. Motionindexing
  • Thosetechniquesandsystemsaboutmotionindexingcanbecategorizedintofourtypes.
  • Feature-basedapproach:
  • Trajectory-basedapproach:
  • Semantic-basedapproach
  • Image-basedapproach
  201. Feature-basedapproach:
  • Computesthemotionparametersofpredefinedmotionmodel.
  • HasbeenadoptedbyMPEG7(stilldraft)
  • example
  203. Trajectory-basedapproach:
  • Thisapproachisoftenchosenbyobject-basedsystemforindexingvideo.
  205. Semantic-basedapproach
  • Providessemanticeventsoractionsofmotion.
  • Referencepaper“ASemanticEvent-DetectionApproachandItsApplicationtoDetectingHuntsinWildlifeVideo”
  207. Image-basedapproach
  • Givessynthesizedpicturesgeneratedfrommotionofvideo.
  • MAMistheimage-basedapproach
  208. ConceptsofMAM(1)
  • Motionactivitymapisanimagethataccumulatesthemotionactivityonthespecificgridsalongthetemporalaxisofvideos.
  gridtij 209. ConceptsofMAM(2)
  • Itisanimage-basedrepresentationaboutthemagnitudeandspatialdistributionofmotion.
  • OnevideocliquecangenerateseveralMAMsandallMAMsareorganizedintoahierarchicaltreeviewaccordingtothestructureofvideo.
  210. DefinitionofMAM(1)
  • Motionactivitymapisanimagesynthesizedfrommotionvectorfield,andmotionvectorfieldcanbedefinedasfollowingtemporalfunction.X(t),wheret=t0,t1,………tk.
  • X(t)=v(i,j,t)
  (i,j)Wherevx=(i,j,t)andvy=(i,j,t)arethex-axiscomponentandy-axiscomponentofmotionvectoronthegrid(i,j). 211. DefinitionofMAM(2)
  • BaseonthemotionvectorfieldX(t),themotionactivitymap(MAM)iscomputedas
  (i,j)Wheref(v(i,j,t))isthemotionactivitymeasurefunctionongrid(i,j)andisthegridsetofvideo. 212. GenerationofMAMDemovideosegmentationHallshallMotionvectorfieldVideoVideoVideoTemporalvideoSegmentationMAMComputingMAMQuantizationMAMspatialSegmentationMAMRegion-BasedMAMs 213. OrganizationofMAMs
  • Videocanbesegmentedintodifferentshotlevelssuchasshotsandsub-shots,sotherearealotofMAMscorrespondingtoavideoshot.
  • AlltheMAMsofvideocanbeorganizedintoahierarchicaltreerepresentingthestructureofvideo.
  214. OrganizationofMAMsInteractiveVideoRetrievalVideoVideoVideoTemporalSegmentationMAMComputingLayeredspatialsegmentationMAMdisplayMAMDatabase 215. Expermentalresults(a)KeyframebasedMAM(b)MAM(c-f)Region-representationofMAM 216. Conclusion
  • VideoshotMAMsub-shot1MAM1sub-shot2MAM2
  • AlltheMAMcouldbesegmentedintoRegion-representation.
  • OptimalizeMAM-basedrepresentation,wemarkthepixelofMAMwithaspecificcoloraccordingtotherelatedintensity.
  217. Paperstudy:topic5SOM-BaseR*-TreeforSimilarityRetrievalDatabaseSystemsforAdvancedApplications,2001.Proceedings.SeventhInternationalConferenceon,2001Kun-seok.Oh,YaokaiFeng,KunihikoKaneko,AkifumiMakinouchi,Sang-hyunBae 218. Outline
  • Self-OrganizingMaps(SOM)
  • R*-Tree
  • SOM-BasedR*-Tree
  • Experiments
  • Conclusion
  219. Self-OrganizingMaps(SOM)WhatisSOM1.SOMprovidemappingfromhigh-demensionalfeaturevectorsontoatwo-dismensionalspace2.Themappingpreservesthetopologyofthefeaturevector.3.Themapiscalledtotopologicalfeaturemap,andpreservesthemutualrelationships(similarity)infeaturespaceofinputdata.4.Thevectorscontainedineachnodeofthetopologicalfeaturemapareusuallycalledcodebookvectors. 220.
  • 我們使用100個類神經元排列成10×10的二維矩陣來進行電腦模擬，用來進行測試的輸入向量的維度也是二維的資料，且其機率分佈為均勻地分佈在。
    
    
  Self-OrganizingMaps(SOM) 221. 圖：均勻分佈之資料的自我組織特徵映射圖：(a)隨機設定之初始鍵結值向量;(b)經過50次疊代後之鍵結值向量;(c)經過1,000次疊代後之鍵結值向量;(d)經過10,000次疊代後之鍵結值向量;Self-OrganizingMaps(SOM) 222.
  • 類神經元在特徵映射圖中的機率分佈，的確可以反應出輸入向量的機率分佈。
    
    這裏要強調一點的是，資料的機率分佈特性並非是線性地反應於映射圖中。
    
    
  三群高斯分佈之資料。
  
  Self-OrganizingMaps(SOM) 223. Self-OrganizingMaps(SOM)SOMAlgorithm1.InitMapneuron.2.inputfeaturevectorx.3.findwinnerneuron(BMN:Beat-MatchNode)4.adjustingallneuron’sweight5.continusstep2,untilnoadjusting. 224. R*-Tree
  • TheR*-treeimprovestheperformanceoftheR-treebymodifyingtheinsertionandsplitalgorithmsbyintroducingtheforcedreinsertionsmechanism
  • TheR*-treeisproposedasanindexstructureforspatialdatasuchasgeographicalandCADdata
  225. R*-Tree
  • Eachinternalnodecontaisanarrayof(p,)entries.Wherepisapointertoinchildnodeofthisinternalnode,andistheminimumboundingrectangle(MBR)ofherchildnodepointertobythepointerp.
  • Eachleadnodecontainsanarrayof(OID,)forspatialobjects,whereOIDisanobjectidentifer,andistheMBRoftheobjectidentifiedbyOID.
  226. R*-Tree(cont.)Spaceofpointdata 227. R*-Tree(cont.)Treeaccessstructure 228. SOM-BasedR*-Tree
  • 1、Clusteringsimilarimages
  • WefirstgeneratethetopologicalfeaturemapusingtheSOM,WegeneratetheBMILbycomputingthedistancebetweenthefeaturevectorandcodebookvectorsfromthetopologicalfeaturemap.
  • TheBMN(best-match-nodes:nodewithminimumdistance)ischosenfromthemapnodes.
  • Nexttheweigthvectorareupdated
  229. SOM-BasedR*-Tree(cont.) 230. SOM-BasedR*-Tree(cont.)
  • 2、Construction
  • InordertoconstructtheR*-tree,weselectaCBV(codebookvector)fromthetopologicalfeaturemapasanentry.
  • Ifitisanemptynode.Weselectthenextcodebookvector.Otherwisedeterminetheleafnodewhichinsertcodebookvector.
  • AleafoftheSOM-basedR*-treehasthefollowingstructure:
  231. Experiments
  • WepreformedexperimentstocomparetheSom-basewithSOMandR*-tree.
  • Imagedatabaseuse:40,000atrificial/natural(storageonlocaldisk)
  • Imagesize:128*128pixels
  • Performedon:COMPAQdeskpro(OS:FreeBSD)with128MBRAM
  232. Experiments(cont.)
  • FeatureExtraction:
  • useHaarwaveletestocomputefeaturevector
  • ThecolorspaceYIQ-space(NTSCtransmissionprimaries)
  • Eachelecmentofthisfeaturevectorrepresentsanagerageof32*32pixelsoforiginalimage.
  • Thecolorfeaturevectorhas48dimensions(4*4*3;where3istheehreechannelsofYIQ-space)
  233. Experiments(cont.)
  • ConstrucionofSOM-basedR*-tree
  234. Experiments(cont.) 235. Experiments(cont.)
  • Weexperimentedwithfourtypeofsearches:
  • (I)normalSOMincludingemptynodes
  • (II)normalSOMwitheliminatedemptynodes
  • (III)normalR*-tree
  • (IV)SOM-basedR*-treewitheliminatedemptynodes
  236. Experiments(cont.)
  • RetrievalfromSOMwithemptynodes
  • RetrievalfromSOMwithoutemptynodes
  237. Experiments(cont.) 238. Conclusion
  • Forhigh-dimensionaldata,weusingatopologicalfeaturemapandabest-matching-image-list(BMIL)obtainedviathelearningofaSOM
  • Inanexperiment,weperformedasimilaritysearchusingrealimagedataandcomparedtheperformanceoftheSOM-basedR*-treewithanormalSOMandR*-tree,baseonretrievaltimecost
  Editor'sNotes 這一章節主要探討收集回來後的多媒體資料，要如何儲存，處理以及搜尋的相關技術 4likes × AmyBrown Dec.27,2021 Didyoutry⇒www.HelpWriting.net⇐?.Theyknowhowtodoanamazingessay,researchpapersordissertations. ZaherNourredine Dec.16,2018 RebeccaHuang Dec.30,2009 JonBoutelle Dec.14,2008 DirectorofTechnology at Slideshare/Linkedin Views × Totalviews 3,898 OnSlideShare 0 FromEmbeds 0 NumberofEmbeds 17 Youhavenowunlockedunlimitedaccessto20M+documents! × UnlimitedReading Learnfasterandsmarterfromtopexperts UnlimitedDownloading Downloadtotakeyourlearningsofflineandonthego YoualsogetfreeaccesstoScribd! Instantaccesstomillionsofebooks,audiobooks,magazines,podcastsandmore. Readandlistenofflinewithanydevice. FreeaccesstopremiumserviceslikeTuneln,Mubiandmore. DiscoverMoreOnScribd × ShareClipboard × Facebook Twitter LinkedIn Link Publicclipboardsfeaturingthisslide × Nopublicclipboardsfoundforthisslide Selectanotherclipboard × Lookslikeyou’veclippedthisslidetoalready. Createaclipboard Youjustclippedyourfirstslide! Clippingisahandywaytocollectimportantslidesyouwanttogobacktolater.Nowcustomizethenameofaclipboardtostoreyourclips. Name* Description Visibility OtherscanseemyClipboard Cancel Save SharethisSlideShare SpecialOffertoSlideShareReaders × TheSlideSharefamilyjustgotbigger.Enjoyaccesstomillionsofebooks,audiobooks,magazines,andmorefromScribd. Readfreefor60days Cancelanytime.