[發(fā)明專利]海量圖像特征向量中的快速聚類預(yù)處理方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610964786.8
• 申請(qǐng)日: 2016-11-04
• 公開（公告）號(hào): CN106547890B
• 公開（公告）日: 2018-04-03
• 發(fā)明（設(shè)計(jì)）人: 王健;鐘斌
• 申請(qǐng)（專利權(quán)）人: 深圳云天勵(lì)飛技術(shù)有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06K9/62
• 代理公司: 深圳市科吉華烽知識(shí)產(chǎn)權(quán)事務(wù)所(普通合伙)44248
• 代理人: 于標(biāo)

1.一種海量圖像特征向量中的快速聚類預(yù)處理方法，其特征在于：包括如下步驟：（A）兩級(jí)線程池處理；（B）兩級(jí)Map的存儲(chǔ)結(jié)構(gòu)處理；所述兩級(jí)線程池包括進(jìn)行簡(jiǎn)單預(yù)聚類的初級(jí)預(yù)處理線程池和進(jìn)行次級(jí)聚類合并的次級(jí)合并線程池；所述兩級(jí)Map的存儲(chǔ)結(jié)構(gòu)中，將大的聚類結(jié)果Map劃分成子Map,子Map的合并比較操作并行進(jìn)行; 所述步驟（A）中，初級(jí)預(yù)處理線程池按如下方式進(jìn)行處理：從任務(wù)切分調(diào)度模塊中獲取任務(wù)塊，如果沒有獲取成功，則等待，成功之后便進(jìn)行后續(xù)步驟；初始化一個(gè)兩級(jí)Map，第一級(jí)Map是第二級(jí)子Map的管理層，第二級(jí)子Map直接保存匹配結(jié)果的類，具體步驟：遍歷任務(wù)塊中指定的有限個(gè)元素，對(duì)于每一個(gè)元素，執(zhí)行如下邏輯：每取到一個(gè)特征向量，跟當(dāng)前所有子Map中的已聚類結(jié)果進(jìn)行比較；將每個(gè)子Map匹配最佳的結(jié)果返回上一級(jí)進(jìn)行處理，如果與某個(gè)子Map中的某個(gè)類達(dá)到最佳匹配，則將當(dāng)前特征值增加到已存在的這個(gè)類中；如果與所有子Map中的類都不匹配，則新建一個(gè)類，并將當(dāng)前特征值作為新建的這個(gè)類的第一個(gè)特征值，并將該類加入到空閑的子Map中進(jìn)行管理，當(dāng)指定的有限個(gè)元素都處理完畢后，向次級(jí)合并線程池發(fā)送合并請(qǐng)求。

2.根據(jù)權(quán)利要求1所述的海量圖像特征向量中的快速聚類預(yù)處理方法，其特征在于：所述初級(jí)預(yù)處理線程池進(jìn)行初級(jí)聚類任務(wù)切分調(diào)度，具體為：（A1）根據(jù)內(nèi)存資源的消耗上限，設(shè)定初級(jí)預(yù)處理線程池隊(duì)列的最大長(zhǎng)度；（A2）檢查隊(duì)列中已有的任務(wù)塊，如果隊(duì)列未達(dá)到其在步驟（A1）中設(shè)定的最大長(zhǎng)度，調(diào)度模塊從特征值數(shù)據(jù)庫(kù)中讀取一個(gè)長(zhǎng)度不大于最大長(zhǎng)度的數(shù)據(jù)，并組裝成一個(gè)任務(wù)請(qǐng)求放置到隊(duì)列中；（A3）如查到隊(duì)列長(zhǎng)度達(dá)到最大值，則等待初級(jí)預(yù)處理線程池的線程從隊(duì)列中取出任務(wù)請(qǐng)求，以便隊(duì)列不再滿為止；（A4）反復(fù)進(jìn)行步驟（A2）和步驟（A3），直到數(shù)據(jù)都處理完畢為止。

3.根據(jù)權(quán)利要求1所述的海量圖像特征向量中的快速聚類預(yù)處理方法，其特征在于：所述步驟（B）中，兩級(jí)Map存儲(chǔ)結(jié)構(gòu)中，按固定的切換粒度n將所有的聚類結(jié)果劃分成m份，其中每一份都生成為一個(gè)子Map，以所有子Map為元素組合成一個(gè)大Map。

4.根據(jù)權(quán)利要求1所述的海量圖像特征向量中的快速聚類預(yù)處理方法，其特征在于：子Map的每一個(gè)元素為一個(gè)聚類過程形成的最終結(jié)果類，每個(gè)類包含以下兩個(gè)關(guān)鍵信息：所有聚類成這個(gè)類的原始特征值存儲(chǔ)ID和這個(gè)類的代表特征值向量；當(dāng)向當(dāng)前類中新增加特征值向量時(shí)，如果新增加特征值向量是第一個(gè)特征值向量，則將此向量作為這個(gè)類的代表特征向量；如果新增加特征向量時(shí)，是第x個(gè)特征向量（x!=1）,設(shè)原始的代表特征向量為y(org),則新的代表特征向量y(new) = ((n-1)x + y(org)) / n。

5.根據(jù)權(quán)利要求1所述的海量圖像特征向量中的快速聚類預(yù)處理方法，其特征在于：所述步驟（A）中，次級(jí)合并線程池按如下步驟進(jìn)行處理：（A21）每一個(gè)合并線程都獨(dú)立運(yùn)行，每個(gè)線程不斷的嘗試獲取合并請(qǐng)求，如果請(qǐng)求隊(duì)列為空，則進(jìn)行等待，如果不為空，則進(jìn)行下一步處理；（A22）對(duì)于每一個(gè)合并請(qǐng)求，先并行且獨(dú)立進(jìn)行與每個(gè)子Map的比較操作；（A23）當(dāng)一個(gè)合并請(qǐng)求的子Map都比較完成后，進(jìn)行比較結(jié)果的合并，選取所有比較結(jié)果最大的匹配分值；（A24）如果這個(gè)最大的匹配值大于設(shè)定門限，則表明與現(xiàn)有的類匹配，進(jìn)行現(xiàn)有類的更新操作，并將新的特征值ID附加到匹配的類中；當(dāng)前元素處理完畢后跳轉(zhuǎn)到步驟（A21），否則進(jìn)行步驟（A25）；（A25）新建類，首先檢查是否達(dá)到最大的Map容量，如果沒有達(dá)到，直接進(jìn)行步驟（A27），否則進(jìn)行步驟（A26）；（A26）選擇當(dāng)前已存在的類中聚類結(jié)果集合特征值記錄個(gè)數(shù)最少，且小于當(dāng)前新加類的特征記錄個(gè)數(shù)的類，將其刪除以空出新的存儲(chǔ)空間；（A27）新建立聚類結(jié)果元素，并將當(dāng)前特征值ID集合及代表特征向量賦值給這個(gè)新的聚類結(jié)果。

6.根據(jù)權(quán)利要求1所述的海量圖像特征向量中的快速聚類預(yù)處理方法，其特征在于：還包括動(dòng)態(tài)備份存儲(chǔ)與恢復(fù)處理，其具體為：在聚類開始時(shí)，從數(shù)據(jù)庫(kù)中讀取初級(jí)任務(wù)切分的結(jié)果及狀態(tài)，進(jìn)行初級(jí)預(yù)聚類狀態(tài)的恢復(fù)；從數(shù)據(jù)庫(kù)中讀取聚類合并的狀態(tài)和數(shù)據(jù)，進(jìn)行聚類合并狀態(tài)的恢復(fù)；在聚類的處理過程中，每完成一次聚類預(yù)處理及每完成一次合并，向數(shù)據(jù)庫(kù)中存入當(dāng)前的中間結(jié)果信息。