[發(fā)明專利]基于連通圖和凸包的散點(diǎn)圖去重疊算法

有效

• 申請(qǐng)?zhí)枺?/td>: 202110315709.0
• 申請(qǐng)日: 2021-03-24
• 公開（公告）號(hào): CN113052893B
• 公開（公告）日: 2022-05-06
• 發(fā)明（設(shè)計(jì)）人: 廖志芳;孫金生;趙穎;郁松;龍軍
• 申請(qǐng)（專利權(quán)）人: 中南大學(xué)
• 主分類號(hào): G06T7/62
• 分類號(hào): G06T7/62;G06T7/64
• 代理公司: 長沙軒榮專利代理有限公司 43235
• 代理人: 李喆

本發(fā)明提供了一種基于連通圖和凸包的散點(diǎn)圖去重疊算法，包括：步驟1，選取一個(gè)以圖片為標(biāo)記點(diǎn)的圖片散點(diǎn)圖，且圖片散點(diǎn)圖中的所有圖片的四個(gè)邊長都相等，獲取圖片散點(diǎn)圖中每張圖片的坐標(biāo)和寬高；步驟2，通過碰撞檢測算法計(jì)算圖片散點(diǎn)圖中各個(gè)圖片之間的鄰接矩陣；步驟3，根據(jù)計(jì)算出的各個(gè)圖片之間的鄰接矩陣和基于寬度優(yōu)先搜索的暴力搜索方法計(jì)算圖片散點(diǎn)圖中所有圖片的連通圖；步驟4，對(duì)計(jì)算出的每個(gè)連通圖計(jì)算凸包。本發(fā)明可以大幅減少以圖片為標(biāo)記的圖片散點(diǎn)圖的視覺重疊，完全消除圖片散點(diǎn)圖中單個(gè)凸包內(nèi)的視覺重疊，為圖片數(shù)據(jù)集的可視分析提供了有效的方法，提高了分析效率，用戶可以準(zhǔn)確感知圖片散點(diǎn)圖中圖片的位置。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)挖掘和數(shù)據(jù)可視化技術(shù)領(lǐng)域，特別涉及一種基于連通圖和凸包的散點(diǎn)圖去重疊算法

背景技術(shù)

隨著大數(shù)據(jù)時(shí)代的到來，人們?cè)絹碓秸J(rèn)識(shí)到數(shù)據(jù)所能夠創(chuàng)造的價(jià)值。但是用戶很難從大量數(shù)據(jù)中直接發(fā)現(xiàn)規(guī)律，模式，知識(shí)等。數(shù)據(jù)可視化可以將數(shù)據(jù)轉(zhuǎn)化為易于感知的圖像，幫助用戶洞察數(shù)據(jù)內(nèi)涵，理解數(shù)據(jù)所蘊(yùn)含的規(guī)律，是分析、理解數(shù)據(jù)的重要工具。散點(diǎn)圖是表示二維數(shù)據(jù)的標(biāo)準(zhǔn)方法。在散點(diǎn)圖中，所有數(shù)據(jù)以點(diǎn)的形式出現(xiàn)在笛卡爾坐標(biāo)系中，每個(gè)點(diǎn)所對(duì)應(yīng)的橫縱坐標(biāo)即代表該數(shù)據(jù)在坐標(biāo)軸所表示維度上的屬性值大小。散點(diǎn)圖可以幫助用戶感知數(shù)據(jù)趨勢、相關(guān)性和和數(shù)據(jù)異常值等。以圖片為標(biāo)記的散點(diǎn)圖使用圖片代替標(biāo)準(zhǔn)散點(diǎn)圖中的點(diǎn)，經(jīng)常出現(xiàn)在對(duì)于圖片數(shù)據(jù)集的降維分析中，可以幫助用戶感知圖片數(shù)據(jù)集中的數(shù)據(jù)趨勢，圖片相似度，和異常圖片等等。但是，由于圖片相對(duì)于點(diǎn)占據(jù)了更大的面積，以圖片為標(biāo)記的散點(diǎn)圖會(huì)出現(xiàn)比較嚴(yán)重的視覺重疊，導(dǎo)致用戶無法準(zhǔn)確感知圖片的位置，從而降低了分析效率。因此如何有效地減輕以圖片為標(biāo)記的散點(diǎn)圖的視覺重疊成為了散點(diǎn)圖可視化的一個(gè)研究熱點(diǎn)。

目前，散點(diǎn)圖的去重疊方法多采用的是減少圖中數(shù)據(jù)點(diǎn)的方法，根據(jù)數(shù)據(jù)的相似性使用單個(gè)半徑較大點(diǎn)代表原始圖形中若干個(gè)臨近的點(diǎn)。現(xiàn)有的方法需要減少散點(diǎn)圖中點(diǎn)的數(shù)量，難以保持散點(diǎn)圖原有的趨勢，而針對(duì)以圖片為標(biāo)記的散點(diǎn)圖的去重疊方法幾乎沒有。另外，以圖片為標(biāo)記的散點(diǎn)圖在對(duì)圖片數(shù)據(jù)集的可視分析中幾乎必不可少。尤其是在圖片數(shù)據(jù)集的無監(jiān)督聚類任務(wù)中，研究人員往往需要首先使用以圖片為標(biāo)記的散點(diǎn)圖來分析整個(gè)數(shù)據(jù)集中的數(shù)據(jù)分布規(guī)律。但是以圖片為標(biāo)記的散點(diǎn)圖的視覺重疊往往比較嚴(yán)重，難以有效地支撐研究人員的可視分析需求。目前，以圖片為標(biāo)記的散點(diǎn)圖的去重疊方法已成為散點(diǎn)圖可視化的研究熱點(diǎn)，針對(duì)相關(guān)技術(shù)中的問題，目前尚未提出有效的解決方案。

發(fā)明內(nèi)容

本發(fā)明提供了一種基于連通圖和凸包的散點(diǎn)圖去重疊算法，其目的是為了解決以圖片為標(biāo)記的散點(diǎn)圖會(huì)出現(xiàn)比較嚴(yán)重的視覺重疊，導(dǎo)致用戶無法準(zhǔn)確感知圖片的位置，從而降低了分析效率的問題

為了達(dá)到上述目的，本發(fā)明的實(shí)施例提供了一種基于連通圖和凸包的散點(diǎn)圖去重疊算法，包括：

步驟1，選取一個(gè)以圖片為標(biāo)記點(diǎn)的圖片散點(diǎn)圖，且圖片散點(diǎn)圖中的所有圖片的四個(gè)邊長都相等，獲取圖片散點(diǎn)圖中每張圖片的坐標(biāo)和寬高；

步驟2，通過碰撞檢測算法計(jì)算圖片散點(diǎn)圖中各個(gè)圖片之間的鄰接矩陣；

步驟3，根據(jù)計(jì)算出的各個(gè)圖片之間的鄰接矩陣和基于寬度優(yōu)先搜索的暴力搜索方法計(jì)算圖片散點(diǎn)圖中所有圖片的連通圖；

步驟4，對(duì)計(jì)算出的每個(gè)連通圖計(jì)算凸包；

步驟5，采用基于網(wǎng)格布局的搜索算法分別將計(jì)算出的每個(gè)凸包所包圍的面積劃分為多個(gè)寬高相同的小正方形；

步驟6，將每個(gè)凸包中的圖片按照?qǐng)D片到相對(duì)應(yīng)的凸包中心的距離升序排列，將每個(gè)凸包中劃分出小正方形按照小正方形到相對(duì)應(yīng)的凸包中心的距離升序排列，獲取每個(gè)凸包中的小正方形的坐標(biāo)和寬高，將每個(gè)凸包中的小正方形的坐標(biāo)和寬高分配到相對(duì)應(yīng)的凸包中的圖片，得到每個(gè)凸包中的每張圖片新坐標(biāo)和新寬高。

其中，所述步驟1具體包括：