基于Multi-probe LSH的菊花花型相似性計(jì)算

袁培森 翟肇裕 錢(qián)淑韻 徐煥良,3

(1.南京農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院， 南京 210095; 2.馬德里理工大學(xué)技術(shù)工程和電信系統(tǒng)高級(jí)學(xué)院， 馬德里 28040;3.國(guó)家信息農(nóng)業(yè)工程技術(shù)中心， 南京 210095)

0 引言

表型(Phenotype)是生物某一特定物理外觀或組成，是由基因和環(huán)境共同作用的結(jié)果[1-2]。植物表型代表了植物形態(tài)，是植物學(xué)領(lǐng)域研究的重要課題，在生態(tài)學(xué)、植物育種等領(lǐng)域應(yīng)用廣泛[3-4]。其中，表型相似性計(jì)算在植物表型[4-6]、基因組學(xué)[7]、疾病診斷[8-10]等研究中具有重要應(yīng)用。

當(dāng)前，數(shù)據(jù)挖掘技術(shù)為解決植物表型研究提供了重要支撐手段[11]。相似性計(jì)算作為數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的基礎(chǔ)問(wèn)題，又稱(chēng)為最近鄰查詢(xún)。對(duì)于海量、高維數(shù)據(jù)的相似性計(jì)算，由于“維災(zāi)難”(Curse of dimensionality)問(wèn)題，線性計(jì)算效率不高。為此，研究者提出了近似最近鄰(Approximate nearest neighbor,ANN)查找技術(shù)[12]，這是一種對(duì)查詢(xún)結(jié)果質(zhì)量和效率折中的技術(shù)。局部位置敏感哈希技術(shù)(Locality sensitive hashing，LSH)是近似最近鄰查詢(xún)計(jì)算的高效方法[13]。該方法在查詢(xún)質(zhì)量和查詢(xún)效率方面均具有理論保證?；贚SH有多種優(yōu)化查詢(xún)質(zhì)量和效率的技術(shù)，例如，基于熵的LSH[14]，多探測(cè)的LSH(Multi-probe LSH,MPLSH)[15]等，其中MPLSH在高維數(shù)據(jù)相似性計(jì)算效率和結(jié)果質(zhì)量方面具有更好的效果[16-17]。

在表型相似性計(jì)算研究方面，PENG等[6]指出，測(cè)量表型相似性在疾病診斷中發(fā)揮重要作用，提出了一種基于網(wǎng)絡(luò)的表型相似性測(cè)量方法，用于計(jì)算表型之間的相似性。在菊花表型及分類(lèi)方面，ZHANG等[18]通過(guò)簡(jiǎn)單序列重復(fù)標(biāo)記建立的獨(dú)特DNA指紋和分子身份鑒定中國(guó)傳統(tǒng)菊花品種，為基于微衛(wèi)星標(biāo)記多態(tài)性的菊花鑒定和分類(lèi)的起點(diǎn)。ROEIN等[19]研究利用擴(kuò)增片段長(zhǎng)度多態(tài)性和表型特征，評(píng)估菊花的遺傳多樣性和種群結(jié)構(gòu)。KHODAKOVSKAYA等[20]通過(guò)基因片段的控制來(lái)增強(qiáng)菊花中的開(kāi)花和分枝表型。但是，專(zhuān)門(mén)針對(duì)菊花表型的計(jì)算研究較少。YAN等[21]定義了菊花的不同花色表型，完成了菊花品種表型顏色的分布分析。

菊花是全球第二重要的觀賞植物，具有品種數(shù)量龐大、花型變異豐富的特點(diǎn)[22]。菊花花型是菊花的重要表型特征之一，其相似性計(jì)算對(duì)菊花形態(tài)分類(lèi)和表型研究具有重要作用，同時(shí)菊花花型種類(lèi)多、瓣形繁多，這些特點(diǎn)給菊花的品種分類(lèi)和表型研究帶來(lái)較大困難[18]。表型相似性計(jì)算可以為菊花分類(lèi)提供重要的參考，對(duì)于海量的菊花相似性計(jì)算，效率和質(zhì)量至關(guān)重要。

本文針對(duì)海量菊花圖像數(shù)據(jù)進(jìn)行菊花花型相似性比較，提出采用SIFT特征和視覺(jué)詞袋模型[23-24]提取菊花圖像重要特征，并使用K-means對(duì)重要特征進(jìn)行聚類(lèi)和優(yōu)化。針對(duì)菊花圖像數(shù)據(jù)的高維特性，采用多探測(cè)LSH解決海量菊花花型相似性計(jì)算的質(zhì)量和效率問(wèn)題。在查詢(xún)質(zhì)量和查詢(xún)效率方面尋求一種優(yōu)化計(jì)算方案。

1 材料與方法

1.1 菊花圖像

本文數(shù)據(jù)集共包括4 100幅菊花圖像，共5種花型：翻卷型、雛菊型、飛舞型、球型和蓮座型[25]。菊花圖像示例如圖1所示。每一種花型有800幅，共4 000幅用于訓(xùn)練，100幅圖像用于測(cè)試。

圖1 5種菊花類(lèi)型示例Fig.1 Illustration of five types of chrysanthemum images

1.2 菊花圖像SIFT特征

常用的圖像特征包括形狀、紋理等。在諸多的圖像特征提取技術(shù)中，尺度不變特征轉(zhuǎn)換 (Scale invariant feature transform，SIFT)[26]應(yīng)用最廣。SIFT通過(guò)在圖像空間中搜索關(guān)鍵點(diǎn)，并提取出其位置、尺度、旋轉(zhuǎn)不變量。因此SIFT對(duì)尺度變化、旋轉(zhuǎn)以及一定視角和光照變化等具有不變性、穩(wěn)定性及很強(qiáng)的可區(qū)分性和擴(kuò)展性[26]。鑒于SIFT良好的性質(zhì)，本文采用SIFT方法提取菊花的特征。

SIFT算法有4個(gè)計(jì)算步驟[26]：高斯差(Difference of Gaussians，DoG)空間極值檢測(cè)、關(guān)鍵點(diǎn)定位、方向確定和關(guān)鍵點(diǎn)描述。

圖2是一幅菊花圖像經(jīng)過(guò)灰化后提取SIFT特征示意圖，每個(gè)點(diǎn)代表一個(gè)定位關(guān)鍵點(diǎn)。

圖2 菊花圖像SIFT特征提取示意圖Fig.2 Illustration of SIFT features extraction of chrysanthemum image

1.3 BoVW-SIFT模型

由于SIFT特征提取之后的高維性，本文采用K-means聚類(lèi)算法對(duì)這些向量數(shù)據(jù)進(jìn)行初步聚類(lèi)，用聚類(lèi)中的簇作為詞典的詞，進(jìn)而將同一幅圖像的SIFT向量映射到視覺(jué)詞序列生成碼本，這樣菊花圖像可以使用一個(gè)碼本向量來(lái)進(jìn)行描述。本文采用了基于 SIFT的視覺(jué)詞袋(Bag of visual word，BoVW)[23-24]特征來(lái)對(duì)菊花圖像建模，菊花圖像預(yù)處理過(guò)程如圖3所示。

圖3 菊花圖像預(yù)處理過(guò)程Fig.3 Illustration of chrysanthemum image preprocessing

針對(duì)SIFT特征，構(gòu)建BoVW碼本步驟如下：①對(duì)每一幅菊花圖像提取SIFT特征， SIFT特征用一個(gè)128維描述子向量表示，假設(shè)菊花圖像數(shù)據(jù)集共提取出M個(gè)SIFT特征。②用K-means對(duì)提取的M個(gè)SIFT特征進(jìn)行聚類(lèi)，此算法把M個(gè)SIFT特征分為k個(gè)簇，表示為Ci,i=1,2,…,k，其中Ci為聚類(lèi)中心。

(1)

其中

式中μi——簇Ci的均值向量

E——平方誤差

x——由SIFT特征構(gòu)成的向量

最小化式(1)的平方誤差，以使簇內(nèi)具有較高的相似度，而簇間相似度較低[27]。

本文使用K-means聚類(lèi)返回的k個(gè)簇，計(jì)算每一幅圖像的每一個(gè)SIFT特征到這k個(gè)視覺(jué)詞的距離，并將其映射到距離最近的視覺(jué)詞中。研究表明，k太小會(huì)導(dǎo)致圖像表達(dá)能力不足，太大導(dǎo)致量化過(guò)擬合[28]，本文設(shè)置k為512。

菊花圖像數(shù)據(jù)經(jīng)過(guò)提取SIFT特征后，將這些特征映射到碼本向量。利用TF-IDF模型構(gòu)造向量，并對(duì)向量進(jìn)行歸一化。菊花向量的構(gòu)造包含兩項(xiàng)因子：詞頻(Term frequency,TF)和逆向文件頻率(Inverse document frequency,IDF)[29]。TF是給定的關(guān)鍵點(diǎn)在該菊花圖像中出現(xiàn)的頻率，IDF是一個(gè)關(guān)鍵點(diǎn)普遍重要性的度量。

(2)

式中TFij——關(guān)鍵點(diǎn)j在圖像i中的頻率歸一化值

nij——關(guān)鍵點(diǎn)j在圖像i中出現(xiàn)的次數(shù)

nkj——圖像k中關(guān)鍵點(diǎn)j出現(xiàn)的次數(shù)

(3)

其中

Ti={j:ti∈dj}

式中IDFi——關(guān)鍵點(diǎn)i在圖像中的逆向文件頻率

D——菊花圖像數(shù)量

Ti——包含關(guān)鍵點(diǎn)j的圖像數(shù)量

圖像向量采用TFijIDFi進(jìn)行計(jì)算，最后對(duì)圖像向量進(jìn)行數(shù)據(jù)歸一化

(4)

式中μ——均值σ——標(biāo)準(zhǔn)差

采用歐氏距離作為圖像距離度量。距離最小的菊花圖像作為相似性查詢(xún)結(jié)果。

(5)

式中ui、vi——?dú)w一化后的向量

N——向量維度d——距離

1.4 局部位置敏感哈希技術(shù)

1.4.1LSH基本原理

相似性查詢(xún)又稱(chēng)為最近鄰查詢(xún)(Nearest neighbor search,NNS)，給定N維向量O={x1,x2,…,xn}∈RN，查詢(xún)向量q?O，返回元素x*∈O，x*與查詢(xún)向量q在某種距離度量上最近。為解決高維數(shù)據(jù)最近鄰查詢(xún)計(jì)算效率問(wèn)題，研究者提出了近似最近鄰查詢(xún)技術(shù)來(lái)折衷查詢(xún)的效率和質(zhì)量[12]。近似最近鄰查詢(xún)返回滿(mǎn)足d(x,q)≤(1+ε)d(x*,q)的結(jié)果，其中ε>0，x*是查詢(xún)向量q的精確最近鄰，該查詢(xún)稱(chēng)為(1+ε)-近似最近鄰[30]。圖4是(1+ε)-近似最近鄰查詢(xún)示意圖，查詢(xún)向量q真實(shí)的最近鄰是o1，距離為r，該圖中的o2和o4都可作為該查詢(xún)的近似結(jié)果。

圖4 (1+ε)-近似最近鄰查詢(xún)示意圖Fig.4 Illustration of (1+ε)-approximate nearest neighbor query

圖5 LSH過(guò)濾-驗(yàn)證計(jì)算過(guò)程Fig.5 LSH filtering-verification evaluation procedure

LSH[12]是一種基于過(guò)濾-驗(yàn)證框架的計(jì)算高維數(shù)據(jù)近似最近鄰的高效查詢(xún)技術(shù)，過(guò)濾-驗(yàn)證框架計(jì)算過(guò)程如圖5所示。LSH能夠理論上在次線性(Sub-linear)時(shí)間內(nèi)近似求解高維數(shù)據(jù)的最近鄰問(wèn)題。

給定距離r、近似因子ε(ε>0)和概率p1、p2，其中p1>p2，哈希函數(shù)h把N維空間的向量映射為整數(shù)集合Z，記為h:RN→Z，x1、x2同時(shí)滿(mǎn)足：若d(x1,x2)≤r，則P[h(x1)=h(x2)]≥p1；若d(x1,x2)≥(1+ε)r，則P[h(x1)=h(x2)]≤p2，則稱(chēng)為(r,(1+ε)r,p1,p2)-sensitive的LSH。

LSH的基本原理為

P[h(xi)=h(xj)]=sim(xi,xj)

(6)

式中 sim()——相似性度量函數(shù)

xi、xj——數(shù)據(jù)向量

P——概率

即把兩個(gè)高維向量的相似性計(jì)算轉(zhuǎn)變?yōu)橛?jì)算兩個(gè)哈希值相等的概率。

1.4.2LSH結(jié)果放大

為了提升查詢(xún)成功概率，通常使用多個(gè)獨(dú)立的哈希表[31]。設(shè)局部敏感哈希函數(shù)族H，每個(gè)哈希表由k個(gè)哈希函數(shù)h∈H創(chuàng)建。

通過(guò)以下3種操作來(lái)提高成功概率： AND操作；OR操作；級(jí)聯(lián)AND和OR操作。

P=1-(1-st)L

(7)

式(7)的可視化如圖6所示，圖6是L為10時(shí)，被檢出的概率與t、s的關(guān)系，AND操作時(shí)，增大t能提高過(guò)濾掉相似度小的對(duì)象的概率。通過(guò)連接t個(gè)哈希函數(shù)構(gòu)造哈希關(guān)鍵字，降低了相似對(duì)象之間的沖突概率。為了提高查詢(xún)的召回率，LSH一般使用L個(gè)函數(shù)g1,g2，…,gL，共L個(gè)哈希表。

圖6 公式(7)的成功概率與相似度及參數(shù)(L=10)Fig.6 Success ratio with similarity s and parameter t of formula (7) (L=10)

1.5 查詢(xún)計(jì)算過(guò)程

基于LSH的查詢(xún)計(jì)算處理框架如圖7所示。給定一個(gè)菊花查詢(xún)x，計(jì)算gi(x)(1

g(x)=(h1(x),h2(x),…,ht(x))

(8)

函數(shù)g(x)通過(guò)連接t個(gè)哈希函數(shù)構(gòu)造哈希關(guān)鍵字，該關(guān)鍵字作為索引桶識(shí)別號(hào)，降低了相似對(duì)象之間的沖突概率。為了提高查詢(xún)的召回率，LSH一般使用L個(gè)函數(shù)g1,g2，…,gL，形成L個(gè)哈希表。

圖7 LSH計(jì)算處理框架Fig.7 Basic processing framework of locality sensitive hashing

根據(jù)LSH的性質(zhì)，與查詢(xún)向量q相近的菊花沒(méi)有被哈希到同一個(gè)桶中，它很有可能以很高的概率哈希到周?chē)耐爸校樵?xún)向量q的近鄰點(diǎn)落在其相鄰區(qū)域的概率分布如圖8所示[15]。圖8是某一查詢(xún)向量q在菊花圖像集上的相鄰區(qū)域映射概率分布，該圖以0為中心，落在x=0兩側(cè)的概率基本呈現(xiàn)正態(tài)分布。由圖8可以看出通過(guò)檢查查詢(xún)向量q附近的桶，可以增加查找近鄰數(shù)據(jù)的概率。本文方法通過(guò)仔細(xì)推導(dǎo)出的探測(cè)序列，探測(cè)可能包含查詢(xún)結(jié)果的哈希桶來(lái)提高查詢(xún)的效率，極大地降低了哈希表所需的數(shù)量，提高菊花花型相似性的查詢(xún)質(zhì)量和查詢(xún)效率。

圖8 查詢(xún)向量q的近鄰點(diǎn)落在其相鄰區(qū)域的概率分布圖Fig.8 Illustration of probability distribution of query points q in adjacent buckets

采用文獻(xiàn)[15]的方法，定義哈希擾動(dòng)向量Δ=(δ1,δ2，…,δT)，其中δi∈{-1,0,1}。給定菊花查詢(xún)向量q，基本的LSH檢索g(q)=(h1(q),h2(q)，…，hL(q))的桶中元素作為候選對(duì)象，順序地探測(cè)哈希桶g(q)+Δ，探測(cè)過(guò)程如圖9所示。給定哈希桶探尋序列Δ1,Δ2,…，gi(q)+Δ1是應(yīng)用擾動(dòng)向量Δ1后產(chǎn)生的新哈希值，它指向表中一個(gè)新的哈希桶，通過(guò)使用擾動(dòng)向量，可以獲得多個(gè)與查詢(xún)向量q指向的哈希桶鄰近的桶，這些桶中含有與q鄰近的元素的概率較高。

圖9 哈希探測(cè)過(guò)程Fig.9 Probing procedure of hash

圖9中點(diǎn)p落在hi(q)+δ的概率[15]估計(jì)為

P[hi(p)=hi(q)+δ]≈exp(-ηxi(δ)2)

(9)

式中η——取決于‖p-q‖2的常量

xi(δ)——查詢(xún)向量q與橫邊界hi(q)+δ的距離

假設(shè)擾動(dòng)向量Δ=(δ1,δ2，…,δT)，則經(jīng)過(guò)t個(gè)哈希函數(shù)，得到p與q相鄰的概率為

(10)

2 結(jié)果

2.1 試驗(yàn)環(huán)境

試驗(yàn)運(yùn)行環(huán)境為Intel Core i5 1.6 GHz，8 GB內(nèi)存，128 GB固態(tài)硬盤(pán)；操作系統(tǒng)為MacOS 10.13.3。開(kāi)發(fā)環(huán)境為OpenCV 3.4和C++。

圖像碼本長(zhǎng)度k為512，ε設(shè)置為0.02。查詢(xún)次數(shù)設(shè)置為100，哈希探測(cè)次數(shù)默認(rèn)設(shè)置為2 000。試驗(yàn)中參數(shù)t為每個(gè)哈希表的哈希函數(shù)個(gè)數(shù)，L為哈希表個(gè)數(shù)。試驗(yàn)中參數(shù)t的取值范圍為14～18，L的范圍為3～18。探測(cè)數(shù)量T分別為500、1 000、2 000和3 000。

2.2 查詢(xún)計(jì)算效率

為了測(cè)試計(jì)算效率，對(duì)數(shù)據(jù)集采用了增加隨機(jī)高斯噪聲進(jìn)行擴(kuò)充，使得數(shù)據(jù)集的總量為100 000，查詢(xún)質(zhì)量的測(cè)試仍然采用原始數(shù)據(jù)集。查詢(xún)計(jì)算效率使用平均查詢(xún)時(shí)間和加速比兩個(gè)指標(biāo)進(jìn)行評(píng)價(jià)。平均查詢(xún)時(shí)間結(jié)果如表1所示。其中線性式掃描的平均查詢(xún)時(shí)間為12.31 ms。

表1 平均查詢(xún)時(shí)間Tab.1 Average query time ms

表1中，隨著參數(shù)t和L的增加，平均查詢(xún)時(shí)間在減小，從3.823 ms降低到0.590 ms。每個(gè)哈希表的哈希函數(shù)越多，其查詢(xún)時(shí)間越短，表明AND操作過(guò)濾后的結(jié)果越少，表1結(jié)果表明哈希表個(gè)數(shù)對(duì)查詢(xún)時(shí)間影響不大。

根據(jù)加速比評(píng)價(jià)查詢(xún)效率，加速比是相對(duì)于線性掃描式查找的比例因子，計(jì)算公式為

(11)

式中TA——近似查詢(xún)時(shí)間

TL——線性掃描時(shí)間

加速比越大，說(shuō)明本文方法相對(duì)于線性掃描式計(jì)算越快。

圖10顯示隨著參數(shù)t和L的增加，平均加速比從3.3左右增加到19.8。哈希函數(shù)數(shù)量越多，加速比越大，哈希表個(gè)數(shù)對(duì)查詢(xún)時(shí)間影響不明顯。

圖10 相對(duì)線性掃描加速比Fig.10 Speedup ratio compared with linear scanning

2.3 查詢(xún)結(jié)果及質(zhì)量

查詢(xún)結(jié)果示例如圖11所示，輸入一幅飛舞型菊花圖像，右側(cè)輸出查詢(xún)到的相似圖像。

圖11 查詢(xún)結(jié)果示例Fig.11 Illustration of query results

為了度量查詢(xún)結(jié)果質(zhì)量，采用平均成功概率來(lái)計(jì)算。

(12)

對(duì)查詢(xún)集合Q，平均成功概率(Average success ratio，ASR)為

(13)

式中 |Q|——查詢(xún)數(shù)量

ASR值越大，表明查詢(xún)結(jié)果越好。

圖12為平均成功概率試驗(yàn)結(jié)果，由圖12可知，t為14、15時(shí)，平均成功概率在0.91以上，L大于6、t為14時(shí)平均成功概率大于0.95，查詢(xún)結(jié)果的質(zhì)量較好；t從15增加到18時(shí)，平均成功概率從0.95降到0.63左右；t一定時(shí)，L從3增加到18，平均成功概率呈上升趨勢(shì)，增加了11.9%～19%。

圖12 查詢(xún)平均成功概率結(jié)果Fig.12 Average success rate of query

從圖10、12可以得出，t為14～16、L>6時(shí)，平均加速比從3.3上升到9.3，此時(shí)平均查詢(xún)時(shí)間為1.31 ms，平均成功概率在0.8以上。

2.4 探測(cè)次數(shù)的影響

在t=14、L=6時(shí)，測(cè)試了探測(cè)次數(shù)對(duì)查詢(xún)質(zhì)量的影響，如圖13和圖14所示。探測(cè)次數(shù)設(shè)置為500、1 000、2 000和3 000。

圖13 查詢(xún)平均成功概率與探測(cè)次數(shù)關(guān)系Fig.13 Relationship of average success rate with probe number

圖14 加速比與探測(cè)次數(shù)關(guān)系Fig.14 Relationship of speedup ratio with probe number

圖13中，查詢(xún)平均成功概率隨著探測(cè)次數(shù)的增加呈現(xiàn)上升趨勢(shì)，從0.71提高到0.97，提高了36.6%。

圖14中，加速比隨著探測(cè)次數(shù)的增加呈下降趨勢(shì)，從13降到2.4。

圖13、14的結(jié)果表明，探測(cè)次數(shù)對(duì)查詢(xún)性能有較大的影響，探測(cè)次數(shù)的增加可以提高查詢(xún)結(jié)果的平均成功概率。探測(cè)次數(shù)在1 000～2 000范圍可以獲得較好的查詢(xún)質(zhì)量，但是如果要提高查詢(xún)的效率，可以適當(dāng)?shù)販p少探測(cè)次數(shù)。

2.5 試驗(yàn)對(duì)比

在查詢(xún)質(zhì)量和性能方面，設(shè)置哈希函數(shù)個(gè)數(shù)t為14，將本文方法與基于熵的ELSH[14]進(jìn)行了對(duì)比試驗(yàn)。試驗(yàn)結(jié)果如圖15、16所示。圖15結(jié)果表明，隨著參數(shù)L的增加，兩種方法的平均成功概率都在增加，而基于熵的ELSH從0.82緩慢增加到0.92左右，本文方法從0.88增加到0.94左右，表明本文方法優(yōu)于基于熵的ELSH。

圖15 查詢(xún)平均成功概率對(duì)比Fig.15 Average success rate comparison

圖16表明，在查詢(xún)性能方面，隨著參數(shù)增加，本文方法的查詢(xún)時(shí)間在2.1 ms左右，比較穩(wěn)定，而ELSH的平均查詢(xún)時(shí)間是本文方法的兩倍左右。以上試驗(yàn)結(jié)果表明，本文方法具有較好的平均查詢(xún)成功概率和查詢(xún)性能。

圖16 查詢(xún)時(shí)間對(duì)比Fig.16 Query time comparison

3 討論

本文使用多探測(cè)局部位置敏感哈希技術(shù)，對(duì)菊花表型相似性進(jìn)行了初步研究。植物的表型重要表現(xiàn)是外觀，其相似性研究對(duì)菊花形態(tài)的變化、不同菊花品種之間的演變等具有重要作用。通過(guò)提取菊花的SIFT特征并對(duì)特征進(jìn)行K-means聚類(lèi)，構(gòu)建了菊花圖像的BoVW-SIFT模型。鑒于高維性質(zhì)對(duì)菊花圖像計(jì)算性能的影響，提出采用近似查詢(xún)方案，其中基于多探測(cè)的局部位置敏感哈希針對(duì)LSH特點(diǎn)進(jìn)一步查詢(xún)優(yōu)化，在提升查詢(xún)效率和查詢(xún)質(zhì)量方面提供理論保證。

系統(tǒng)中多探測(cè)LSH通過(guò)哈希表個(gè)數(shù)L、哈希函數(shù)個(gè)數(shù)t和探測(cè)數(shù)量T這3個(gè)參數(shù)來(lái)靈活地調(diào)整質(zhì)量和查詢(xún)效率。為了尋找最佳參數(shù)設(shè)置，首先根據(jù)內(nèi)存容量選擇哈希表個(gè)數(shù)L，然后在哈希函數(shù)個(gè)數(shù)t和探測(cè)數(shù)量T之間進(jìn)行權(quán)衡。結(jié)果表明，t為14～16、L為6～12、探測(cè)次數(shù)在1 000～2 000范圍內(nèi)可以取得較好的結(jié)果。

4 結(jié)束語(yǔ)

為了提升菊花表型相似性計(jì)算的質(zhì)量和效率，采用多探測(cè)局部位置敏感哈希技術(shù)，提取菊花的SIFT特征，并對(duì)特征進(jìn)行K-means聚類(lèi)，構(gòu)建了菊花圖像的BoVW-SIFT模型。在菊花數(shù)據(jù)集上進(jìn)行了系統(tǒng)性試驗(yàn)測(cè)試，結(jié)果表明，查詢(xún)平均成功概率可以達(dá)到0.90以上，系統(tǒng)的平均加速比在3.3～19.8之間。通過(guò)試驗(yàn)測(cè)試得出了相關(guān)參數(shù)優(yōu)化選擇范圍。與基于熵的ELSH近似查詢(xún)方法相比，本文方法在查詢(xún)質(zhì)量和效率方面具有明顯的優(yōu)勢(shì)。