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

有效

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

本公開提供了一種基于遞歸劃分的多類散點圖采樣方法、系統、存儲介質及設備，通過將接收多類散點圖轉換為多類密度圖；根據多類密度圖上各鄰近區域的密度差異將空間遞歸，劃分為KD樹結構；基于KD樹結構，從所有葉子節點出發回溯，找到能同時保持稀少類的點和相對類密度的節點，由該節點開始遞歸分配類標簽，保證每類至少一點且類密度順序與采樣前一致，最終從每個葉子節點選取具有分配到的類標簽的一個點，作為采樣結果輸出，能夠快速地計算出同時忠實地保持相對數據密度和相對類密度，并顯示主要離群點和稀少類的點的采樣結果，有助于提升分析以多類散點圖可視化的數據的效率。

技術領域

本公開屬于圖像信息處理領域，具體涉及一種基于遞歸劃分的多類散點圖采樣方法、系統、存儲介質及設備。

背景技術

本部分的陳述僅僅是提供了與本公開相關的背景技術信息，不必然構成在先技術。

散點圖(scatter plot)在回歸分析中是指數據點在直角坐標系平面上的分布圖，散點圖通過將數據點編碼為視覺標記(例如，點)，可以有效地呈現變量，數據集群之間的相關性和離群點，以及數據中的其他模式。同時，通過基于類標簽對視覺標記進行顏色編碼，多類散點圖在可視化帶有類標簽的數據方面并觀察多個類間的相關性則是有效的。此外，很多時候，降維到2D空間的高維數據也是用散點圖進行可視化的。綜上，散點圖現已被廣泛用于可視化定量變量之間的關系。

然而，散點圖常常會面臨過度繪制(也就是高密度區域視覺標記間的相互重合)的問題，人們已經提出了很多方法來減輕該問題，例如改變標記尺寸、顏色、透明度、位置、密度等參數或通過動畫展現數據。

具體發明人了解，現存的方法大體上能夠被分成以下幾種：

外觀優化：這類方法是緩解過度繪制的一種直觀方法，例如，減少標記大小、改變標記形狀、并使標記半透明。前兩種策略適合處理中等情況的過度繪制，但不能處理標記已經非常小的情況，最后一種策略同樣要面臨重疊標記難以辨認的問題。因此，上述方法都具有一定的局限性。

進行數據抖動：此類方法通過稍微移位重疊標記的位置來緩解過度繪制以顯示它們。由于大的抖動可能會引入不存在的假模式，可能導致觀察者的錯誤認知，具有很大的局限性，并且此類方法不能處理嚴重過度繪制的情況。

進行密度估計：該類方法是一種散點圖的替代方法，它將離散的散點圖顯示為顏色編碼的密度圖或一組輪廓線，以這種方式，可以更好地表征密集區域，但可能遺漏離群點和稀疏區域；而且，由于顏色混合，難以可視化的觀察以顏色編碼的多類密度場，特別是對于重疊區域，就更難實現了。

采樣優化，該類技術主要是通過優化采樣過程來解決過度繪制的問題，主要包括隨機采樣、非均勻采樣、藍噪聲采樣等，隨機采樣能保留密集區域和相對密度差異，卻很容易丟失離群點和稀疏區域；非均勻采樣容易忽略不同密度區域的差異；藍噪聲采樣導入特殊的局部模式，同時在原始數據點數非常多時處理速度較慢，而且在構建的密度場不好時會產生不合理的結果。

綜上所述，目前處理過度繪制問題的幾種方式都各有局限性。

發明內容

本公開為了解決上述問題，提出了一種基于遞歸劃分的多類散點圖采樣方法、系統、存儲介質及設備，本公開通過對采樣過程的優化，對于給定的多類散點圖和屏幕空間，能夠快速地計算出同時忠實地保持相對數據密度和相對類密度，并顯示主要離群點和稀少類的點的采樣結果，有助于提升分析以多類散點圖可視化的數據的效率。

根據一些實施例，本公開采用如下技術方案：

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

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

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