[發明專利]基于遞歸劃分的多類散點圖采樣方法、系統、存儲介質及設備

有效

• 申請號: 201910485786.3
• 申請日: 2019-06-05
• 公開（公告）號: CN110211031B
• 公開（公告）日: 2020-10-02
• 發明（設計）人: 汪云海;陳昕;葛彤;陳寶權
• 申請（專利權）人: 山東大學
• 主分類號: G06T3/00
• 分類號: G06T3/00;G06T7/90
• 代理公司: 濟南圣達知識產權代理有限公司 37221
• 代理人: 李琳

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

接收多類散點圖，并將其轉換為多類密度圖；

根據多類密度圖上各鄰近區域的密度差異將空間遞歸劃分為KD樹結構；

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

所述遞歸劃分為KD樹結構的具體過程包括：

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

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

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

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

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

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

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

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

檢查節點是否是葉子節點，如果節點不是葉子節點，則對其兩個子節點調用同樣的遞歸劃分過程，根據父節點給當前節點的遞歸劃分方式和兩個子節點的采樣率差值是否小于設定值同時決定是否給出進行進一步劃分的方式；

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

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

或，節點的采樣率為以該節點為根的子樹中的葉子個數與該節點所覆蓋的區域中所有網格的總密度之和的比值；

或，若某節點的含有點的網格數量與該節點所覆蓋的區域的網格總數的比值小于設定閾值，則認為該節點內部含有離群點；

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

將所有網格的位置用密度加權平均，求出該節點覆蓋的區域的質心；

在與x軸平行和與y軸平行的距質心最近的網格邊界線中選擇使將要生成的兩個子節點的內部密度和之差最小的那一條作為劃分線；

按選中的劃分線劃分當前節點的密度圖，分配給兩個子節點，并更新當前節點的葉子數量。

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

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

將在該節點求得的類標簽數量用遞歸方式分配給其子樹里的葉子節點；

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

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

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