[發(fā)明專利]一種基于微型計(jì)算平臺的實(shí)時(shí)響應(yīng)大媒體近鄰檢索方法

有效

• 申請?zhí)枺?/td>: 201810038892.2
• 申請日: 2018-01-16
• 公開（公告）號: CN108256058B
• 公開（公告）日: 2021-05-07
• 發(fā)明（設(shè)計(jì)）人: 王振;孫福振;王雷;李鑫鑫
• 申請（專利權(quán)）人: 山東理工大學(xué)
• 主分類號: G06F16/43
• 分類號: G06F16/43
• 代理公司: 濟(jì)南智圓行方專利代理事務(wù)所(普通合伙企業(yè)) 37231
• 代理人: 張玉琳

1.一種基于微型計(jì)算平臺的實(shí)時(shí)響應(yīng)大媒體近鄰檢索方法，其特征在于，包括如下步驟：

a：學(xué)習(xí)待查詢數(shù)據(jù)集的全局高維浮點(diǎn)特征向量集合F＝{F₁，F(xiàn)₂，…，F(xiàn)_n}，其中包含n個(gè)特征向量；

b：為了保證漢明空間內(nèi)的近鄰檢索結(jié)果與原空間內(nèi)的近鄰檢索結(jié)果之間具有較高的一致性，分別定義了序列保持約束條件R和聚類分布約束條件A；

c：采用隨機(jī)梯度下降算法尋找滿足序列保持約束條件和空間分布關(guān)系約束條件的二值編碼中心點(diǎn)時(shí)，為了使得算法能夠快速收斂到所有極小值點(diǎn)，需預(yù)先粗略判斷目標(biāo)函數(shù)中的極小值點(diǎn)，并在其附近初始化算法的輸入；由于A的定義與聚類算法的約束條件類似，因此可根據(jù)聚類中心點(diǎn)來估算目標(biāo)函數(shù)R+A的極小值點(diǎn)；

c01：均勻采樣數(shù)據(jù)點(diǎn)的分布區(qū)域，然后統(tǒng)計(jì)落在每一個(gè)采樣區(qū)域內(nèi)的高維浮點(diǎn)特征的數(shù)量，并將其作為區(qū)域的密度值；

c02：中心點(diǎn)附近一般會聚集大量的數(shù)據(jù)點(diǎn)，密度值較大；若區(qū)域的密度值低于平均值，則該區(qū)域含有聚類中心點(diǎn)的概率較小，本發(fā)明將舍棄密度值較小的區(qū)域；

c03：若兩個(gè)區(qū)域之間的距離較小，則從這兩個(gè)區(qū)域中選擇的初始點(diǎn)會使得算法收斂到相同的極值點(diǎn)；因此，將合并距離相對較近的高密度區(qū)域；

c04：經(jīng)過所述c02和c03處理之后，將區(qū)域中所有數(shù)據(jù)點(diǎn)的均值作為候選初始中心點(diǎn)集合E'＝{P₁，P₂，…，P_t}，其中含有t個(gè)候選初始中心點(diǎn)；

c05：若t2^bit(bit表示二值編碼的長度，2^bit表示編碼中心點(diǎn)的數(shù)量)，則轉(zhuǎn)步驟d；否則，所要尋找的中心點(diǎn)的數(shù)量不少于目標(biāo)函數(shù)中可能存在的極小值點(diǎn)的數(shù)量，只需從數(shù)據(jù)集中再隨機(jī)選擇2^bit-t個(gè)數(shù)據(jù)點(diǎn)與E'中的點(diǎn)共同構(gòu)成初始中心點(diǎn)集合E，并轉(zhuǎn)步驟e尋找最優(yōu)編碼中心點(diǎn)；

d：構(gòu)建多組初始中心點(diǎn)集合；

t2^bit，表明所要尋找的中心點(diǎn)的數(shù)量少于目標(biāo)函數(shù)中極小值點(diǎn)的數(shù)量；若僅根據(jù)一組中心點(diǎn)集合，將無法找到目標(biāo)函數(shù)中的所有極小值點(diǎn)；對于這種情況，進(jìn)行多組初始中心點(diǎn)集合的構(gòu)建；

e：根據(jù)步驟c或d中的初始中心點(diǎn)集合，采用隨機(jī)梯度下降算法，尋找同時(shí)滿足序列保持約束條件和聚類分布約束條件的編碼中心點(diǎn)集合；

f：建立距離表，為保證高區(qū)分性，根據(jù)所述c04中的候選初始中心點(diǎn)集合E'建立距離表；

f01：計(jì)算并比較候選初始中心點(diǎn)P₁，P₂，…，P_t與集合{C₁，C₂，...，C_l}中的中心點(diǎn)之間的距離值，賦予候選初始中心點(diǎn)與其距離最近的編碼中心點(diǎn)相同的二值編碼，候選初始中心點(diǎn)的二進(jìn)制編碼集合為{B₁，B₂，…，B_t}，其中B_i＝{b_i1，b_i2，…，b_il}表示P_i的多組二進(jìn)制編碼，1≤i≤t，b_ij(1≤j≤l)表示P_i根據(jù)編碼中心點(diǎn)集合C_j生成的二進(jìn)制編碼；

f02：計(jì)算距離表的每一個(gè)位置中的值，若距離表的位置索引為(b，b')，則將{B₁，B₂，…，B_t}中能構(gòu)成二值編碼對(b，b')的數(shù)據(jù)點(diǎn)之間的距離值存儲在該位置中；

g：在微型計(jì)算平臺上生成查詢多媒體數(shù)據(jù)的全局浮點(diǎn)特征F_q，并根據(jù){C₁，C₂，...，C_l}生成F_q的多組二值編碼b_q1，b_q2，…，b_ql；

h：計(jì)算F_q的多組二值編碼與待查詢數(shù)據(jù)點(diǎn)的多組二值編碼之間的平均漢明距離，并按照從小到大的順序排列待查詢數(shù)據(jù)庫中的數(shù)據(jù)點(diǎn)；若僅有少量數(shù)據(jù)點(diǎn)共享同一較小的漢明距離值，則將這些數(shù)據(jù)點(diǎn)作為最終的近鄰檢索結(jié)果，并轉(zhuǎn)步驟j；否則，返回平均漢明距離值較小的數(shù)據(jù)點(diǎn)作為備選查詢結(jié)果，并轉(zhuǎn)步驟i；

i：根據(jù)后驗(yàn)證距離表，重新判斷備選查詢結(jié)果中的數(shù)據(jù)點(diǎn)與查詢數(shù)據(jù)點(diǎn)之間的相似性，并對其重排序；

j：返回查詢結(jié)果中排名較靠前的二值編碼特征所對應(yīng)的多媒體數(shù)據(jù)，作為最終的多媒體近鄰查詢結(jié)果；

所述步驟b中，

所述序列保持約束條件定義為：在歐式空間內(nèi)，根據(jù)F_m(1≤m≤n，F(xiàn)_m表示F中的第m個(gè)高維浮點(diǎn)向量)與F中其余特征向量之間的歐式距離，對F中的浮點(diǎn)向量進(jìn)行排序，得到結(jié)果為：將F中的浮點(diǎn)向量映射為二進(jìn)制編碼后，根據(jù)它們之間的漢明距離關(guān)系，可得到另一種排序結(jié)果：序列保持約束條件要求兩種不同排序之間具有較高的一致性，即在不同排序中的同一位置上具有相同的元素，其定義如下式所示：

表示在歐式空間內(nèi)序列號為m的特征向量，P_h(·)返回該特征向量在漢明空間內(nèi)的位置序列號，I(·)是判斷函數(shù)，若特征向量在漢明空間和歐式空間內(nèi)的序列號不一致，則目標(biāo)函數(shù)的值將被增加；通過最小化上述目標(biāo)函數(shù)的值，可使得特征向量在不同空間內(nèi)的序列號具有一致性，從而在漢明空間內(nèi)得到準(zhǔn)確率較高的近鄰檢索結(jié)果；

所述聚類分布約束條件定義為：

若浮點(diǎn)向量被映射成長度為bit的二進(jìn)制編碼，則共存在2^bit種二進(jìn)制編碼；對于海量數(shù)據(jù)庫而言，數(shù)據(jù)點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)大于2^bit，將有多個(gè)數(shù)據(jù)點(diǎn)被映射為相同編碼；擁有相同二進(jìn)制編碼的數(shù)據(jù)點(diǎn)應(yīng)符合聚類分布特性，其約束條件的定義如下式所示：

其中C(F_m)表示與F_m具有相同二值編碼的中心點(diǎn)。