袁培森 翟肇裕 錢淑韻 徐煥良,3

(1.南京農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院， 南京 210095; 2.馬德里理工大學(xué)技術(shù)工程和電信系統(tǒng)高級學(xué)院， 馬德里 28040;3.國家信息農(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]。其中，表型相似性計算在植物表型[4-6]、基因組學(xué)[7]、疾病診斷[8-10]等研究中具有重要應(yīng)用。

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

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

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

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

1 材料與方法

1.1 菊花圖像

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

圖1 5種菊花類型示例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ān)鍵點，并提取出其位置、尺度、旋轉(zhuǎn)不變量。因此SIFT對尺度變化、旋轉(zhuǎn)以及一定視角和光照變化等具有不變性、穩(wěn)定性及很強(qiáng)的可區(qū)分性和擴(kuò)展性[26]。鑒于SIFT良好的性質(zhì)，本文采用SIFT方法提取菊花的特征。

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

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

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

1.3 BoVW-SIFT模型

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

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

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

(1)

其中

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

E——平方誤差

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

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

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

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

(2)

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

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

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

(3)

其中

Ti={j:ti∈dj}

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

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

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

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

(4)

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

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

(5)

式中ui、vi——歸一化后的向量

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

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

1.4.1LSH基本原理

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

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

圖5 LSH過濾-驗證計算過程Fig.5 LSH filtering-verification evaluation procedure

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

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

LSH的基本原理為

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

(6)

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

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

P——概率

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

1.4.2LSH結(jié)果放大

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

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

P=1-(1-st)L

(7)

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

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

1.5 查詢計算過程

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

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

(8)

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

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

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

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

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

圖9 哈希探測過程Fig.9 Probing procedure of hash

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

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

(9)

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

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

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

(10)

2 結(jié)果

2.1 試驗環(huán)境

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

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

2.2 查詢計算效率

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

表1 平均查詢時間Tab.1 Average query time ms

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

根據(jù)加速比評價查詢效率，加速比是相對于線性掃描式查找的比例因子，計算公式為

(11)

式中TA——近似查詢時間

TL——線性掃描時間

加速比越大，說明本文方法相對于線性掃描式計算越快。

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

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

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

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

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

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

(12)

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

(13)

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

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

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

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

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

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

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

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

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

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

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

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

2.5 試驗對比

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

圖15 查詢平均成功概率對比Fig.15 Average success rate comparison

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

圖16 查詢時間對比Fig.16 Query time comparison

3 討論

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

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

4 結(jié)束語

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