圖像檢索系統(tǒng)中高維數(shù)據(jù)索引技術(shù)研究.pdf

1、隨著互聯(lián)網(wǎng)和信息技術(shù)的快速發(fā)展，圖像等多媒體信息的應(yīng)用越來越普遍，它們廣泛應(yīng)用于社會的各個領(lǐng)域，而且信息量也越來越大。如何對這些圖像信息進行高效存儲和快速的基于內(nèi)容相似性檢索，越來越受到學(xué)術(shù)界人士的普遍關(guān)注。由于圖像信息的高維性，它需要不同于普通數(shù)據(jù)信息的處理技術(shù)，而高維索引技術(shù)正是加速圖像信息檢索的有效手段。因此，設(shè)計更加有效的高維索引結(jié)構(gòu)，以支持高效的基于內(nèi)容的相似性檢索成為迫切需要解決的關(guān)鍵問題。在這種研究背景下，我們深入研究了與

2、高維信息相關(guān)的一些問題，以及已經(jīng)存在的一些高維索引技術(shù)，提出了三種新的索引技術(shù)，并通過廣泛的實驗，驗證了我們提出的索引技術(shù)的高效性。下面對本文的主要工作和貢獻總結(jié)如下： (1)提出了關(guān)鍵維和孿生兄弟節(jié)點的概念，以及關(guān)鍵維轉(zhuǎn)移的思想，并在此基礎(chǔ)上提出了高維數(shù)據(jù)空間中基于距離和關(guān)鍵維的兩步分割策略和索引技術(shù)M+-tree。在索引結(jié)構(gòu)上，M+-tree的每個入口項包含兩個指針，分別指向一對孿生兄弟節(jié)點的左節(jié)點和右節(jié)點。在查詢中，M+-

3、tree采用兩遍過濾方法，即普通兄弟節(jié)點間基于距離的過濾和孿生兄弟節(jié)點間基于關(guān)鍵維的過濾，其中基于關(guān)鍵維的過濾不需要高維距離計算，只需要進行關(guān)鍵維的比較，代價非常低。孿生兄弟節(jié)點間的分割屬于無重疊分割，因此，在一定的查詢范圍內(nèi)，關(guān)鍵維的過濾能力非常強。針對M+-tree的近鄰查詢，M+-tree首次提出了基于度量的索引中優(yōu)先隊列訪問對查詢性能的極大影響，并提出將孿生兄弟節(jié)點作為整體進行隊列訪問，極大地降低了對優(yōu)先隊列的訪問。基于這些思想

4、，本文給出了M+-tree的構(gòu)建、分裂、范圍查詢以及近鄰查詢的算法。 (2)提出了兩種批量構(gòu)建M+-tree的方法：基于單步聚類的批量構(gòu)建技術(shù)和基于多步聚類的批量構(gòu)建技術(shù)。其中基于單步聚類的批量構(gòu)建技術(shù)能夠?qū)崿F(xiàn)索引的快速構(gòu)建，而基于多步聚類的批量構(gòu)建技術(shù)不僅考慮快速構(gòu)建索引結(jié)構(gòu)，而且把快速的相似性查詢作為其另一個重要目標(biāo)，在充分利用索引空間并快速構(gòu)建索引結(jié)構(gòu)的前提下，保證了索引空間良好的聚類特性，以及索引相似性查詢的有效性。由于

5、我們的批量構(gòu)建技術(shù)是建立在靜態(tài)構(gòu)建索引結(jié)構(gòu)基礎(chǔ)上的，索引的空間利用率可以達(dá)100％。同普通的索引構(gòu)建方法相比，我們提出的批量構(gòu)建技術(shù)不僅極大地加快了索引的構(gòu)建速度，而且保證了索引的高效查詢性能。 (3)提出了高維數(shù)據(jù)空間中基于距離和可旋轉(zhuǎn)二元超平面的兩步分割策略和索引技術(shù)BM+-tree。BM+-tree是在M+-tree的基礎(chǔ)上提出的一種改進索引技術(shù)。它的提出一方面改進了孿生兄弟節(jié)點間的數(shù)據(jù)分布，使得孿生兄弟節(jié)點中包含的數(shù)據(jù)信

6、息具有更好的聚類特性，另一方面，可旋轉(zhuǎn)的二元超平面使得我們的考察對象能夠保留更多的信息，因此，可旋轉(zhuǎn)的二元超平面比關(guān)鍵維具有更強的過濾能力，而且，在某種程度上，避免了關(guān)鍵維過濾中當(dāng)查詢半徑增大，過濾能力迅速下降的不足。從而達(dá)到進一步提高高維數(shù)據(jù)查詢效率的目的。本文給出了可旋轉(zhuǎn)二元超平面的構(gòu)建算法以及BM+-tree的構(gòu)建和查詢算法。 (4)提出了假活動子空間的概念，并分析了傳統(tǒng)索引技術(shù)在進行相似性查詢時對假活動子空間訪問的極大代

7、價，以及在低維空間中精煉查詢空間的可行性。提出了通過空間投影，在低維空間中精煉過濾查詢空間的思想。提出了基于最大間隔的空間投影策略，該投影策略能夠保證精煉過程的高效性。最后，基于這種思想構(gòu)建了索引結(jié)構(gòu)MS-tree，以驗證這種精煉過濾策略的高效性。我們通過對范圍查詢的實驗，證明了這種精煉過濾策略的高效性。 (5)最后，本文設(shè)計并實現(xiàn)了一個基于內(nèi)容的圖像檢索系統(tǒng)IBASE。IBASE提供信息的特征提取、索引創(chuàng)建、數(shù)據(jù)存儲以及相似性