[發(fā)明專利]基于遞歸劃分的多類散點圖采樣方法、系統(tǒng)、存儲介質(zhì)及設(shè)備

有效

• 申請?zhí)枺?/td>: 201910485786.3
• 申請日: 2019-06-05
• 公開（公告）號: CN110211031B
• 公開（公告）日: 2020-10-02
• 發(fā)明（設(shè)計）人: 汪云海;陳昕;葛彤;陳寶權(quán)
• 申請（專利權(quán)）人: 山東大學(xué)
• 主分類號: G06T3/00
• 分類號: G06T3/00;G06T7/90
• 代理公司: 濟南圣達(dá)知識產(chǎn)權(quán)代理有限公司 37221
• 代理人: 李琳

1.一種基于遞歸劃分的多類散點圖采樣方法，其特征是：包括以下步驟：

接收多類散點圖，并將其轉(zhuǎn)換為多類密度圖；

根據(jù)多類密度圖上各鄰近區(qū)域的密度差異將空間遞歸劃分為KD樹結(jié)構(gòu)；

基于KD樹結(jié)構(gòu)，從所有葉子節(jié)點出發(fā)回溯，找到能同時保持稀少類的點和相對類密度的節(jié)點，由該節(jié)點開始遞歸分配類標(biāo)簽，保證每類至少一點且類密度順序與采樣前一致，最終從每個葉子節(jié)點選取具有分配到的類標(biāo)簽的一個點，作為采樣結(jié)果輸出；

所述遞歸劃分為KD樹結(jié)構(gòu)的具體過程包括：

(2-1)將覆蓋整個密度圖的區(qū)域作為根節(jié)點；

(2-2)從根節(jié)點執(zhí)行遞歸劃分，確定各子樹、葉子節(jié)點，構(gòu)建KD樹，直到所有的葉子節(jié)點都無法繼續(xù)劃分時，迭代停止。

2.如權(quán)利要求1所述的一種基于遞歸劃分的多類散點圖采樣方法，其特征是：多類散點圖轉(zhuǎn)化為多類密度圖的具體過程包括：

(1-1)按輸入的網(wǎng)格大小將給定的屏幕空間劃分為一系列等大小的網(wǎng)格；

(1-2)將輸入多類散點圖映射到該屏幕空間；

(1-3)統(tǒng)計落在每個網(wǎng)格中的每個類的散點個數(shù)，并將各類的點個數(shù)相加得到總點數(shù)，每個網(wǎng)格內(nèi)各類點個數(shù)為各類密度，從網(wǎng)格位置到各類密度的映射即為多類密度圖。

3.如權(quán)利要求1所述的一種基于遞歸劃分的多類散點圖采樣方法，其特征是：

所述步驟(2-2)包括以下步驟：

檢查節(jié)點是否是葉子節(jié)點，如果節(jié)點不是葉子節(jié)點，則對其兩個子節(jié)點調(diào)用同樣的遞歸劃分過程，根據(jù)父節(jié)點給當(dāng)前節(jié)點的遞歸劃分方式和兩個子節(jié)點的采樣率差值是否小于設(shè)定值同時決定是否給出進行進一步劃分的方式；

如果節(jié)點是葉子節(jié)點，在其內(nèi)部含有點的網(wǎng)格數(shù)量大于1，并且滿足父節(jié)點的遞歸劃分方式或內(nèi)部含有離群點這兩個條件中的任何一個時，劃分葉子節(jié)點為兩個子節(jié)點并返回一個成功進行了劃分的結(jié)果，否則返回一個沒有劃分的結(jié)果。

4.如權(quán)利要求3所述的一種基于遞歸劃分的多類散點圖采樣方法，其特征是：在子節(jié)點劃分完成后，將兩子節(jié)點的子樹的葉子數(shù)量相加得到當(dāng)前節(jié)點子樹的葉子數(shù)量；將是否有某個子節(jié)點成功進行了劃分的結(jié)果回傳給調(diào)用節(jié)點；

或，節(jié)點的采樣率為以該節(jié)點為根的子樹中的葉子個數(shù)與該節(jié)點所覆蓋的區(qū)域中所有網(wǎng)格的總密度之和的比值；

或，若某節(jié)點的含有點的網(wǎng)格數(shù)量與該節(jié)點所覆蓋的區(qū)域的網(wǎng)格總數(shù)的比值小于設(shè)定閾值，則認(rèn)為該節(jié)點內(nèi)部含有離群點；

或，劃分葉子節(jié)點為兩個子節(jié)點的具體過程包括：

將所有網(wǎng)格的位置用密度加權(quán)平均，求出該節(jié)點覆蓋的區(qū)域的質(zhì)心；

在與x軸平行和與y軸平行的距質(zhì)心最近的網(wǎng)格邊界線中選擇使將要生成的兩個子節(jié)點的內(nèi)部密度和之差最小的那一條作為劃分線；

按選中的劃分線劃分當(dāng)前節(jié)點的密度圖，分配給兩個子節(jié)點，并更新當(dāng)前節(jié)點的葉子數(shù)量。

5.如權(quán)利要求1所述的一種基于遞歸劃分的多類散點圖采樣方法，其特征是：從所有葉子節(jié)點出發(fā)回溯，找到能同時保持稀少類的點和相對類密度的節(jié)點的具體過程包括：

找到所有葉子節(jié)點，從每個葉子節(jié)點出發(fā)回溯到一個能同時保持稀少類的點和相對類密度的祖先節(jié)點；

將在該節(jié)點求得的類標(biāo)簽數(shù)量用遞歸方式分配給其子樹里的葉子節(jié)點；

各個葉子節(jié)點根據(jù)分配到的類標(biāo)簽，在所有該類點中進行隨機采樣，選出一個點作為最終采樣結(jié)果輸出。

6.如權(quán)利要求5所述的一種基于遞歸劃分的多類散點圖采樣方法，其特征是：每個葉子節(jié)點出發(fā)回溯到一個能同時保持稀少類的點和相對類密度的祖先節(jié)點的具體過程包括：

從內(nèi)部包含類數(shù)量超過1的葉子節(jié)點開始，回溯到包含葉子數(shù)量超過其中的類數(shù)量的祖先節(jié)點；對符合要求的祖先節(jié)點求一個類分配數(shù)組，其記錄了每個類應(yīng)該由幾個葉子節(jié)點表示，繼續(xù)回溯，找類分配數(shù)組的值與相對類密度最一致的節(jié)點。