高維索引技術介紹大規模圖像檢索面臨一個最主要的問題就是數據的高維性系統索引機制應對高維數據時性能會退化。圖像庫中的圖像特征向量通常是高維向量其維數從幾十維到上百維不等。在高維空間中進行檢索的算法其性能跟維數息息相關。在圖像數據庫中如何降低算法的時間開銷使之成為實時性算法成為最近研究的熱點。為達目的對索引機制進行改進是圖像檢索系統滿足實時性要求的一個必要手段。假如沒有索引結構的幫助要檢索某一圖像就需要掃描所有的圖像其時間復雜度是O。索引結構的目的就是要減少對不必要圖片的訪問從而加速數據庫的檢索速度也就是說在不用訪問到所有圖片的情況下就可以查詢到正確的圖片。因此如果要達到實時性要求在大規模圖像庫中就必須使用有效的高維索引方法來提高查詢速度。之前的研究和實驗結果證明傳統的基于樹型的索引結構在處理維數很高的圖片特征向量時會遇到“維數災難”問題24。性能大大折扣最終會退化到掃描整個圖像數據庫的地步時間還遠不及順序掃描的少。因此研究高效的索引結構克服“維數災難”問題成為多媒體研究的熱點和難點。索引機制不僅在數據庫和多媒體領域有著重要的研究價值在除此之外的數據挖掘決策支持等領域也發揮重要作用。
但是索引機制必須建立在對象數字化的基礎之上還有相似性度量方法的支持。目前的的度量方法主要支持一些簡單的度量模型如歐氏距離、范數距離、二次距離等。對于復雜的相似距離表示模型目前還沒有有效的結合方式如基于虛擬測度空間和基于變換距離的距離模型。虛擬測度空間是指在某些特定的場合下定義視覺模型的特征向量可能比較難。在這種狀況下判斷一副圖片是否屬于某個模型就必須定義一個視覺模型相似概念。根據知識專家的建議可以將視覺特征數據變換到nd空間中。其中一個典型的例子就是形狀的檢索算法的基本思路是為了比較形狀間的相思性需要將某一種圖像經過處理變換成另外一種這樣再比較兩種形狀間的相似性其相似性用這種形狀變換成其他形狀所需要的變換形狀的數目來表示。研究者提出了很多基于向量的高維索引方法來加速檢索過程。其中成果最好是當屬基于樹型結構的索引方法。基本思想是數據空間的層次化劃分用某些方法把原始數據集合中的點分類或者分區然后用某種區域表示結構來近似的表示每個分區或者聚類空間分區表示方法有4近似最優最近鄰高維局部線性掃描算法研究超矩形方法和超球體方法。
所有的分區通過樹型的結構加以組合和表示。在檢索這些分區空間的時候通過分區表示方法計算出分區到查詢點的距離的下界分區表示方法下分區中所有數據點到查詢點的距離的最小值作為查詢點到分區的下界。利用這種下界可以過濾掉不必要的分區從而加速檢索。數據點的劃分有三種策略一種是基于空間的劃分一種是基于數據的劃分還有一種基于聚類的劃分。每種數據點劃分策略將會產生不同的索引結構和索引方法。基于空間劃分的方法有14樹等。這些方法在預先設定的方向上對數據空間進行劃分。基于聚類的劃分采用自下而上的的思想將數據點進行聚類對相似點可能出現的聚類或者鄰近聚類進行詳細查詢。總觀這些規則根據數據的空間分布情況采用不同的劃分策略。特征向量維數較低情況下10維以下這些方法在具有不錯的表現基本滿足需要性能變差后續大量實驗和研究都證實了這一點。這些傳統的方法在高維情況下性能退化甚至不如原始的順序掃描查詢。這就是所謂的“維數災難2”現象。有的研究學者認為造成這一現象的原因在于高維空間中數據分布的極端稀疏性。而傳統的索引結構在高維空間中遇到了三個主要的問題第一點數據劃分傳統索引結構在做索引時候只是用到了其中一小部分維數這就將絕大部分的維數空間忽略造成了較大的損失。
一個信息的完整性表示是需要很多維的信息的因此傳統算法在高維空間下的數據劃分效率很差。第二點覆蓋對象一般傳統方法對于表示某個空間覆蓋對象的表示方法如超球、超立方體等會存在誤差或者不精確的問題這種不緊致的表示方法在高維空間下會產生大量的重疊現象。第三點精確檢索在精確查詢情況下為了得到結果所有與查詢區間有交集的的覆蓋區間都要檢索但由于高維空間的數據分布的極度稀疏性所有高維空間覆蓋對象將會與查詢區間相交這樣查詢效率大大降低性能退化變成順序查找。究其原因是固定形狀的覆蓋對象表示方法不能滿足真實的高維空間下的數據的分布特性和分布規律這種稀疏性最終導致了檢索算法的退化。最近的研究學者首先分析了復雜模型下的檢索機制然后分析傳統算法在復雜模型上的性能提出新的高維索引結構應該具有的特點。這些特點成為新的索引結構戰勝傳統索引結構的必要因素。近幾年的最有影響力的方法有向量近似表示方法、降維方法、一維映射表示方法回顧以往文獻很多資料對高維索引提出了大量不同見解和應對之法主要思路是對數據進行分區或者對空間進行劃分然后在此基礎之上建立索引。
最近幾年的研究熱點是高維空間向量的壓縮表示用相對較小的近似文件來簡化高維向量或者將高維的數據壓縮成一維的的數據這樣會減少維數增加帶來的負面影響。在降維后的空間中利用多維索引結構。其中的單維向量表示方法通過一定的方式將高維數據壓縮成單維數據然后構建Btree索引結構進行管理。方法把點到聚類參考點的距離值做索引。本質上是將高維向量進行壓縮在整個相似性查詢過程中需要判斷查詢球體與聚類分區球體的相交情況確定需要檢索的區間由于算法采用了聚類的思想和良好的參考點選擇策略使得在中低維數上有比較好的表現。近似向量VA表示方法用體積非常小的近似向量來表示原始向量查詢時計算查詢點到每個近似向量的上下邊界通過上下邊界的關系過濾掉大部分的點。代表算法是1998年提出的算法它能降低隨機IO的開銷。該算法是唯一在高維空間上優于順序掃描的算法。被評為近十年最優算法。后續對VA的改進較有名的是提出的它解決了數據集非均勻分布的問題具體處理過程是首先使用KL變換建立新的坐標系消除各維之間的相關性。數據點之間的相關性不因坐標的變換而發生變化所以KL變換不影響數據點之間的相似性。
根據各維上方差能量的大小不均勻分配位數在總位串長度不變的情況下能量大的維上分配的位數多。在這些處理下能更精確的描述數據集的真實分布在性能上也有了明顯提升。對VA的改進還有這種方法結合了樹型索引結構跟VA的結構在壓縮向量中計算出來的模糊距離代替精確距離 達到簡化計算過程的目的。降維算法對數據集進行降維處理 數據集容量會變小 在此基礎之上建立傳統多維索引結構數據檢索系統最主要功能。對于“維數災難”現象 降維是一個有效的方法 但同時它也有局限性。第一 降維必然會失去數據表示的精確性 降維后的數據越小 精致性越差。第二 對于各維之間相關性較強的數據集合 降維效果較好 反之 效果較差。如果某種應用能夠接受較大精度的損失 則可以采用降維策略。 高維索引遇到的問題應用在大規模數據庫中的檢索算法遇到的一個瓶頸問題就是數據的高維性 為了使索引算法達到實用性的要求 高維索引機制需要解決幾個問題。 第一點 數據的維數 要對數據進行簡化表示 也就是說用盡量少的維數表示盡量多的信息 這樣就是可以降低索引樹的表示寬度 提高樹的扇出值 同時最重要的是充分利用了索引結構的空間 降低內存與外存之間的I O開銷。值得一提的的是 簡化向量并不是簡單的降低數據表示的維數。
為了保證索引樹的有效性 必須要求簡化后的向量能夠保持原向量在空間內的數據相關性 即在原來空6 近似最優最近鄰高維局部線性掃描算法研究 間中相互鄰近的點 在簡化后的空間中 其位置關系仍然是相鄰的 這樣才保證算法的有效性 也就是說不會差生錯誤的過濾。 第二點 過濾策略 利用某種過濾原理 過濾掉某些不滿足過濾條件的候選點 檢索候選點可能出現的空間位置。過濾原理直接影響了算法的有效性和檢索的效率 這是判斷一個算法性能的重要參考。通常情況下 檢索過程分成兩個階段 第一階段利用過濾原理 簡單的過濾掉不匹配的點。這一階段主要受到過濾算法的限制。第二階段是細過濾 主要是對候選點進行距離計算 并把真正的近鄰點存入數組中 第三點 高效的近鄰檢測算法 一般的檢索算法不能發揮本身最佳的優勢 因此降低了近鄰查詢的效率。在具體的真實數據集上做具體的研究 提出充分利用索引結構特點的查詢算法。通過合理的向量表示法 在不需要計算全部距離的情況下 就可以實現查詢。 本文貢獻本論文從改進維索引技術這一角度來研究如何提高大規模圖像數據庫的檢索效率。研究的方法包括一維映射、向量聚類、向量近似等。具體研究內容如下 一維映射方法基于距離的一維映射 引入聚類、參考點的概念 計算數據點到相應參考點的距離 以此一維距離值做為索引 構建索引結構B tree。
當查詢數據點時 利用當前查詢半徑、查詢點到參考點距離和候選點到參考點距離這三者之間的三角不等式關系 過濾掉部分候選點。 基于投影的一維映射 引入矢量投影和主分量的概念。先將整個數據集合內的點做K L變換 找到第一主分量 根據第一主分量對原始數據集進行排序。然后向主分量做投影 取投影值。當查詢點投影值與參考點的投影值的差值大于當前第K個近鄰值時候 算法結束 從而提高掃描速率。 L變換后的數據集上不平均分配每維的比特數目 構建碼書 一個高維向量可以壓縮表示成一個只有幾bit的近似向量。在不失去太多信息情況下大大降低了數據的I O開銷。采用順序掃描策略 訪問整個數據集。此方法是唯一能在高維空間下優于線性掃描的方法。 GMM聚類方法和聚類方法 傳統的硬分類方法如K means雖然收斂快 方法簡單 但它不能很好的反映數據的內部特性。本文用GMM聚類方式替代K means聚類方式 用貝葉斯決策準則劃分數據點的聚類歸屬。通過概率的形式更好的表達數據內部分布特性。實 驗測試證明GMM的聚類結果方差更小 數據更緊致。 論文安排本論文主要工作是針對目前高維索引技術進行研究 討論目前存在的問題 在對算法進行分析和總結之后 提出我們的工作內容。
本文的其他章節的內容具體安排如下 第二章 近鄰搜索問題定義。系統詳細論述了基于高維數據的索引結構研究現狀與意義 包括高維空間數據分布特點、樹型索引結構、矢量和向量空間索引結構、主分量分析以及聚類相關內容。 第三章 局部線性掃描算法。介紹兩種基于一維映射的索引方法 為實現最佳查詢性能 探討兩種映射的結合方式和最佳參數設置原則。 第四章PLS VA索引結構。探討了一種基于一維映射和向量近似結構相集合的高效索引結構。在章節中 給出算法流程圖。 第五章 探討聚類模式下算法性能的提升。 第六章 總結與展望。給出工作總結和展望 指出算法中仍然需要改進的地方 并介紹目前關注的新問題。 高維數據索引技術綜述隨著多媒體數據數量的急劇增加 獲取多媒體數據存儲 瀏覽 索引和查找等技術來發掘更多的效益成為一種強烈的需求。大量的應用程序如數字博物館 網絡娛樂和購物以及多媒體圖像檢索應用程序的存在 主動查詢已經更為關注于圖像數據庫的索引和檢索。同時對圖像數據的檢索也是多媒體信息管理的一個重要構成部分。對于可被檢索的圖像需要能夠通過其內容進行索引 這通常通過被標注的關鍵字或自動檢測出的視覺提示 Cues 或視覺詞匯特征來實現。
通過關鍵詞實施的基于語義的圖像檢索是一種較為簡單的方法 但是對于大型的圖像數據庫 這種方法的性能會隨著數據規模的擴大急劇的下滑。 高維空間下的精確KNN查詢 存在著三種主要類型的高維索引方法 它們是降維 DR 、數據近似 VA 和一維映射。一個著名的能提高索引性能的思路是在降維后的數據空間內進行數據索引 13 17 。該算法最重要的一步是通過主分量分析 PCA 12 或者其他線性DR方法把大部分的信息壓縮到只有一小部分維數的空間中 其中用到的兩種降維方法包括全局DR或者局部DR 是基于向量近似結構里的代表性高維索引結構 它表明通過數據壓縮方式和特征向量 21 過濾方式可以加速線性掃描。VA file自提出以來 許多學著做了改進 比如IQ tree 通過把樹型結構跟相結合的方式來實現更好的查詢。VA file用把數據點轉換到PCA 空間中的方式提高了VA的近似能力。本文列舉的算法都是基于精確查找的最經典算法。表2 1給出一個多維索引方法的歷史發展表。 1多維索引方法發展表索引樹結構名稱 作者及發表會議 發表日期 1981 1984 1987 LSD Tree 1989 1990 TV Tree 1994 SS Tree 1990 1996 SR Tree ’ 1997 VA File 1998 Tree ’ 1998 Tree 1998 2000 IQ Tree ICDE 2000 10 近似最優最近鄰高維局部線性掃描算法研究 相似性判斷在多媒體對象 如視頻、圖像、聲音、文本等 的數據庫中 索引機制發揮著重要的作用。
通過特征表述 多媒體對象以特征向量的形式存儲在多媒體數據庫中 從這些特征向量集中選取距離值較小的對象集合被定義為相似性檢索。特征檢測的過程需要索引結構的支持來加速這一過程。為了便于以后的理解 在本章節對基礎應用進行規范和說明。 多媒體特征向量表示將數據庫中的某一幅圖片進行特征提取 特征值是 用d維的向量表示這幅圖片然后將這d維向量存入特征圖像數據庫。一個數據庫DB其實就是一個含有海量d維數據點的集合。由這些數據點構成一個數據空間DB 在這個DB中 其大小是 dDS數據庫中數據點個數是n。 在DB中 對于數據庫中第i條d維的向量的第j維表示為 多媒體特征的相似性度量何種計算方法可以算出對象之間的相似性 這種計算方法算出的結果必須要跟實際對象之間的相似度相一致 通過數值來表征對象之間的關系。 具體的應用背景不同 采用的度量方式也不一樣 每種度量方式都有其最佳的應用環境 本論文為方便起見 統一采用 dist來代替距離計算方式。常見的度量方式是pL 主要包括二種類型距離1L 2L。 定義2 1L絕對值距離其公式 11 2L歐幾里德距離是較普遍的距離公式 定義為 21 二次距離 解釋A是相似正定矩陣 它還有其他變種 叫加權歐氏距離 公式如下 21 比較以上距離計算公式的優劣性有文獻證明 二次距離和絕對值距離要比第2章 高維數據索引技術綜述 11 歐氏距離要好 但歐氏距離因為簡單而廣泛應用。
由于相似性檢索的應用場合不一樣 對相似性查詢的要求也不一樣 主要的應用包括兩方面 一是范圍查詢 二是K近鄰查詢。 范圍查詢 假設有查詢點q 查詢半徑大小為r 根據某種距離計算方式 范圍查詢的目的在于找出與q點距離小于等于給定半徑r的所有點的集合。 pr 此種類型的查詢需要設定半徑r 并不能確定查詢結果集合中含有多少個數據點 也就是說預先不知道集合的大小。這樣算法性能受到參數的影響很大 如果r太大 則會得到太多的點 反之 得不到任何結果。因此 必須根據實際情況設定r的大小。 KNN 查詢 K近鄰查詢 是從數據庫中查詢到滿足條件的K個最小距離值。 11 數據檢索的基本應用中基于K近鄰的應用是最常用的 如果不加說明 本文設計的方法都是基于KNN的。 相似性查詢分為精確查詢和近似查詢。在給定特征向量集和距離計算標準前提下 為得到精確的結果而進行的查詢叫做精確查詢。在滿足一定準確率前提下 為搜索結果而進行的查詢叫做近似查詢。近似查詢得到的結果中并不都是正確的 但有一定的準確率保證。采用近似查詢的好處是可以去掉那些作用不大 但較復雜的索引結構 從而大大提升查詢性能。
這些年 近似近鄰查詢已慢慢取代了精確近鄰查詢 成為新的研究趨勢 這查詢方法為克服“維數災難”提供了新的思路和方法 它兼顧查詢結果的精確性和查詢時間的開銷 是兩者折中的一個方案。目前對于這種查詢方法還沒有形成統一的定論和評價體系。本節介紹一個簡單的 近似近鄰查詢 q為給定的查詢向量 為給定近似系數 如果滿足如下公式 的幾率鄰近向量q數據檢索系統最主要功能。在數據庫的高維檢索中 許多參數或者公式的選擇都帶有試探性和隨機性 并且特征向量是實物空間內的近似表示 由于多媒體信息內容的豐富性和用戶主觀視覺的隨意性決 這種近似是不精確的 在數學意義上并不進行嚴格的定義 所以很難找到一種精確的圖像向量表示方法和基于相似度計算的計算方法。 度量空間與向量空間有方向有大小的量叫做向量 向量組成的空間叫做向量空間 在d維的向量空間中 可以進行加法、乘法、內積運算等 這樣方便了空間向量進行幾何度量。在內積運算幫助下 d維向量空間可以轉換成d維歐氏空間。 12 近似最優最近鄰高維局部線性掃描算法研究 度量空間 space 又叫尺度空間、距離空間等 其公式定義 D代表特征值范圍 dist是距離計算函數。對象集合中的任意三個數據點 其相似性函數dist有這樣的一層關系 度量空間中數據點不具有坐標信息 但數據點之間有距離意義。
給出一個與對象相似度成正比的度量公式 根據這個公式建立索引結構。通過索引結構可以直接進行度量空間的k近鄰查詢 范圍查詢與KNN查詢假設DB是d維數據空間中的點集。k近鄰查詢目的在于給定一個查詢對象q情況下 找到數據庫中最近的k個對象。KNN問題定義成如下 d維空間DS中 一個查詢點qDS 找到一個數據集合S 它包含DB中的k個點 對于每個pS 同時對應于每個 以q為圓心r為半徑 范圍查詢問題定義成如下 10范圍查詢不能確定結果集合中的數據點數目 但數目會隨著查詢半徑的增長而增加。 “分而治之”歷來是人類處理復雜問題的重要手段也是處理海量數據的有效模式。如何將數據集分而治之 即將一個數據集劃分成一些子數據集 是值得研究的基礎性問題。人們通常期望數據劃分后形成的子集內樣本具有同質性 即類內的樣本是相似的 不同類之間的樣本是不相似的。這就是所謂的聚類分析或分群技術。該名詞出自中國的一句老話“物以類聚 人以群分”。 聚類算法聚類自從誕生起 就一直是計算機視覺、數據挖掘研究的熱點。本節介紹兩種聚類算法 Means算法的主要步驟如下1、在給定聚類數據集后 初始化k個類簇 然后按照一定的規則選擇每個類簇的質心 如采用隨機選擇的方法。初始質心的選擇會對聚類的運算效率和聚類結果產生很大的影響。