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

2、a*b*,2020年9月7日,Multimedia Search Engine,4,多媒體文檔索引,相似性計(jì)算 更高維、更復(fù)雜的特征 難以找到合適的變換 可變距離函數(shù) 距離函數(shù)可以有一些參數(shù) 例如：加權(quán)的絕對(duì)值距離，權(quán)為參數(shù) 參數(shù)通過(guò)相關(guān)反饋計(jì)算 各種相關(guān)反饋算法 各種回歸算法,2020年9月7日,Multimedia Search Engine,5,多媒體文檔索引,視覺(jué)信息快速索引 文字：倒排文件+索引結(jié)構(gòu) 優(yōu)點(diǎn)：存在精確匹配,華東師范大學(xué),2020年9月7日,Multimedia Search Engine,6,多媒體文檔索引,視覺(jué)信息快速索引 視覺(jué)信息：基本不存在精確匹配 必須實(shí)現(xiàn)相似性

3、查找 查找給定數(shù)量的最相似文檔，或在某個(gè)距離閾值以內(nèi)的所有文檔 相似性索引,X1,X2,X3,Xq,2020年9月7日,Multimedia Search Engine,7,多媒體文檔索引,相似性索引 支持范圍查詢和/或最近鄰查詢的索引,如何實(shí)現(xiàn)？,2020年9月7日,Multimedia Search Engine,8,多媒體文檔索引,相似性索引 一維范圍查詢索引：B-樹(shù),查詢：15,50,2020年9月7日,Multimedia Search Engine,9,多媒體文檔索引,相似性索引 多維范圍查詢 高維空間具有非常特殊的性質(zhì)，可能會(huì)導(dǎo)致在低維空間有效的算法在高維空間失效,克萊因瓶 Kl

4、ein bottle,莫比烏斯帶 Mbius strip,2020年9月7日,Multimedia Search Engine,10,多媒體文檔索引,相似性索引 多維范圍查詢 距離函數(shù)的影響 一維：L1=L2= 多維：均不相等 使用哪個(gè)距離函數(shù)？ 最容易實(shí)現(xiàn)： 效率最高 其它距離函數(shù)仍然可以實(shí)現(xiàn),2020年9月7日,Multimedia Search Engine,11,多媒體文檔索引,相似性索引 多維范圍查詢 K-d樹(shù), k-d-b樹(shù),2020年9月7日,Multimedia Search Engine,12,多媒體文檔索引,相似性索引 多維范圍查詢 K-d樹(shù), k-d-b樹(shù),http:/d

5、/quadtree/index.html,2020年9月7日,Multimedia Search Engine,13,多媒體文檔索引,相似性索引 多維范圍查詢 R-樹(shù)及其變種,2020年9月7日,Multimedia Search Engine,14,多媒體文檔索引,相似性索引 多維范圍查詢 更近似歐氏距離：SR-樹(shù) 使用超球形節(jié)點(diǎn) 真的有效嗎？ K-d(-b-), R-, SR-樹(shù)的問(wèn)題 性能與插入順序有關(guān) 大量插入、輸出等操作后性能可能下降 數(shù)據(jù)分割算法的通病 不是數(shù)據(jù)分割，使用空間分割,2020年9月7日,Multimedia Search Engi

6、ne,15,多媒體文檔索引,相似性索引 多維范圍查詢 空間分割 空間等分成等大小的格子 量化 只保留有數(shù)據(jù)的格子 高維空間：稀疏 用簡(jiǎn)單索引結(jié)構(gòu)索引格子,2020年9月7日,Multimedia Search Engine,16,多媒體文檔索引,相似性索引 多維范圍查詢 空間分割 格量化(Lattice Quantization) 致密格：更接近球形，用較少格即可填滿空間,Z2格,A2格,2020年9月7日,Multimedia Search Engine,17,多媒體文檔索引,相似性索引 多維范圍查詢 空間分割 格索引 Hash: 查詢時(shí)需要把鄰接格全部查一遍，無(wú)論該格是否有數(shù)據(jù) 鄰接格數(shù)量

7、越少效率越高,2020年9月7日,Multimedia Search Engine,18,多媒體文檔索引,相似性索引 多維范圍查詢 空間分割 格索引 Trie：把每維當(dāng)作一個(gè)符號(hào)，則可用Trie索引 Trie索引可以在每維上支持范圍查詢，所以無(wú)需遍歷所有鄰接格 可以處理任意高維數(shù),2020年9月7日,Multimedia Search Engine,19,多媒體文檔索引,相似性索引 多維范圍查詢 數(shù)據(jù)分割 可構(gòu)造平衡數(shù)，層數(shù)淺，自適應(yīng)數(shù)據(jù)分布 插入順序影響性能，修改操作會(huì)顯著降低性能 維數(shù)越高影響越大 空間分割 結(jié)構(gòu)僅與所索引的數(shù)據(jù)有關(guān) 維數(shù)無(wú)關(guān) 不平衡，層數(shù)可能較大，量化步長(zhǎng)難把握,2020

8、年9月7日,Multimedia Search Engine,20,多媒體文檔索引,相似性索引 多維范圍查詢 各種結(jié)構(gòu)可高效處理的維數(shù) R-樹(shù)、SR-樹(shù)：10-15維 K-d(-b-)樹(shù)：25維 空間分割：100維 更高的維數(shù)？ 線性掃描可能更快,2020年9月7日,Multimedia Search Engine,21,多媒體文檔索引,相似性索引 最近鄰查詢 先用范圍查詢獲得候選數(shù)據(jù)，然后線性掃描候選數(shù)據(jù) 利用范圍查詢的索引結(jié)構(gòu)，配以優(yōu)先級(jí)隊(duì)列 計(jì)算節(jié)點(diǎn)和查詢矢量的最小和最大距離，據(jù)此對(duì)節(jié)點(diǎn)進(jìn)行排序處理 線性掃描 維數(shù)較高時(shí)的唯一選擇,2020年9月7日,Multimedia Search Engine,22,多媒體文檔檢索,多媒體查詢輸入 關(guān)鍵字查詢：文字輸入 Google Image 無(wú)法輸入視覺(jué)查詢,2020年9月7日,Multimedia Search Engine,23,多媒體文檔檢索,多媒體查詢輸入 視覺(jué)查詢：QBE 各種前期研究性演示系統(tǒng) 難以提交合適的查詢樣本 如果已經(jīng)有精確的查詢樣本，則不再需要查詢 如果樣本不好，則查詢效果不好 難以提交概念性查詢 分類(lèi)/隨機(jī)瀏覽+QBE 找到合適樣本的時(shí)間很長(zhǎng),2020年9月7日,Multimedia Search Engi