多媒體搜索引擎

1、多媒體搜索引擎多媒體文檔檢索(2)2021年10月26日multimedia search engine2多媒體文檔索引相似性計(jì)算為什么有這么多相似性計(jì)算方法？數(shù)學(xué)公式總是不符合人的感知l一個(gè)距離在某些情況下好，但在別的情況下不好l不同情況使用不同距離？l如何確定該用哪個(gè)距離？如何解決？l把特征空間變換到“感知均勻空間”2021年10月26日multimedia search engine3多媒體文檔索引相似性計(jì)算“感知均勻空間”（perceptually uniform）歐氏距離與人的感知距離非常接近的空間cie xyz cie ugs(l*u*v*)cie l*a*b*2021年10月26

2、日multimedia search engine4多媒體文檔索引相似性計(jì)算更高維、更復(fù)雜的特征難以找到合適的變換可變距離函數(shù)l距離函數(shù)可以有一些參數(shù)l例如：加權(quán)的絕對(duì)值距離，權(quán)為參數(shù)l參數(shù)通過相關(guān)反饋計(jì)算l各種相關(guān)反饋算法l各種回歸算法2021年10月26日multimedia search engine5多媒體文檔索引視覺信息快速索引文字：倒排文件+索引結(jié)構(gòu)優(yōu)點(diǎn)：存在精確匹配華東師范大學(xué)華東師范大學(xué)上海交通大學(xué)領(lǐng)導(dǎo)視察索引索引(倒排文件倒排文件)hash/trie/b-tree2021年10月26日multimedia search engine6多媒體文檔索引視覺信息快速索引視覺信息：基

3、本不存在精確匹配必須實(shí)現(xiàn)相似性查找l查找給定數(shù)量的最相似文檔，或在某個(gè)距離閾值以內(nèi)的所有文檔l相似性索引x1x2x3xq2021年10月26日multimedia search engine7多媒體文檔索引相似性索引支持范圍查詢和/或最近鄰查詢的索引最近鄰查詢范圍查詢距離閾值等距子空間如何實(shí)現(xiàn)？2021年10月26日multimedia search engine8多媒體文檔索引相似性索引一維范圍查詢索引：b-樹查詢：15,502021年10月26日multimedia search engine9多媒體文檔索引相似性索引多維范圍查詢高維空間具有非常特殊的性質(zhì)，可能會(huì)導(dǎo)致在低維空間有效的算法在

4、高維空間失效克萊因瓶klein bottle莫比烏斯帶mbius strip2021年10月26日multimedia search engine10多媒體文檔索引相似性索引多維范圍查詢距離函數(shù)的影響l一維：l1=l2=l多維：均不相等l使用哪個(gè)距離函數(shù)？l最容易實(shí)現(xiàn)：l效率最高l其它距離函數(shù)仍然可以實(shí)現(xiàn)ll2021年10月26日multimedia search engine11多媒體文檔索引相似性索引多維范圍查詢k-d樹, k-d-b樹2021年10月26日multimedia search engine12多媒體文檔索引相似性索引多維范圍查詢k-d樹, k-d-b樹http:/donar

5、./quadtree/index.html2021年10月26日multimedia search engine13多媒體文檔索引相似性索引多維范圍查詢r(jià)-樹及其變種2021年10月26日multimedia search engine14多媒體文檔索引相似性索引多維范圍查詢更近似歐氏距離：sr-樹l使用超球形節(jié)點(diǎn)l真的有效嗎？k-d(-b-), r-, sr-樹的問題l性能與插入順序有關(guān)l大量插入、輸出等操作后性能可能下降l數(shù)據(jù)分割算法的通病l不是數(shù)據(jù)分割，使用空間分割2021年10月26日multimedia search engine15多媒體文檔索引相似性索

6、引多維范圍查詢空間分割l空間等分成等大小的格子l量化l只保留有數(shù)據(jù)的格子l高維空間：稀疏l用簡(jiǎn)單索引結(jié)構(gòu)索引格子2021年10月26日multimedia search engine16多媒體文檔索引相似性索引多維范圍查詢空間分割l格量化(lattice quantization)l致密格：更接近球形，用較少格即可填滿空間z2格a2格2021年10月26日multimedia search engine17多媒體文檔索引相似性索引多維范圍查詢空間分割l格索引lhash: 查詢時(shí)需要把鄰接格全部查一遍，無論該格是否有數(shù)據(jù)l鄰接格數(shù)量越少效率越高維數(shù)123456789致密格z1a2a3d4d5e6

7、e7e89z鄰接數(shù)(3d-1)2826802427282186656019682致密格鄰接數(shù)26122440721262402722021年10月26日multimedia search engine18多媒體文檔索引相似性索引多維范圍查詢空間分割l格索引ltrie：把每維當(dāng)作一個(gè)符號(hào)，則可用trie索引ltrie索引可以在每維上支持范圍查詢，所以無需遍歷所有鄰接格l可以處理任意高維數(shù)2021年10月26日multimedia search engine19多媒體文檔索引相似性索引多維范圍查詢數(shù)據(jù)分割l可構(gòu)造平衡數(shù)，層數(shù)淺，自適應(yīng)數(shù)據(jù)分布l插入順序影響性能，修改操作會(huì)顯著降低性能l維數(shù)越高影響

8、越大空間分割l結(jié)構(gòu)僅與所索引的數(shù)據(jù)有關(guān)l維數(shù)無關(guān)l不平衡，層數(shù)可能較大，量化步長(zhǎng)難把握2021年10月26日multimedia search engine20多媒體文檔索引相似性索引多維范圍查詢各種結(jié)構(gòu)可高效處理的維數(shù)lr-樹、sr-樹：10-15維lk-d(-b-)樹：25維l空間分割：100維更高的維數(shù)？l線性掃描可能更快2021年10月26日multimedia search engine21多媒體文檔索引相似性索引最近鄰查詢先用范圍查詢獲得候選數(shù)據(jù)，然后線性掃描候選數(shù)據(jù)利用范圍查詢的索引結(jié)構(gòu)，配以優(yōu)先級(jí)隊(duì)列l(wèi)計(jì)算節(jié)點(diǎn)和查詢矢量的最小和最大距離，據(jù)此對(duì)節(jié)點(diǎn)進(jìn)行排序處理線性掃描l維數(shù)較高時(shí)的唯一選擇2021年10月26日multimedia search engine22多媒體文檔檢索多媒體查詢輸入關(guān)鍵字查詢：文字輸入google image無法輸入視覺查詢2021年10月26日multimedia search engine23多媒體文檔檢索多媒體查詢輸入視覺查詢：qbe各種前期研究性演示系統(tǒng)難以提交合適的查詢樣本l如果已經(jīng)有精確的查詢樣本，則不再需要查詢l如果樣本不好，則查詢效果不好難以提交概念性查詢分類/隨機(jī)瀏覽+qbe找到合適樣本的時(shí)間很長(zhǎng)2021年10月26日multimedia se