楊冠澤，單維鋒

(防災(zāi)科技學(xué)院 應(yīng)急管理學(xué)院,河北 三河 065201)

0 引言

經(jīng)過(guò)幾十年的記錄，地震前兆臺(tái)網(wǎng)中心已經(jīng)積累了大量的觀測(cè)數(shù)據(jù)，此類觀測(cè)數(shù)據(jù)是一種二維時(shí)間序列值，因地震預(yù)報(bào)的需要，研究人員時(shí)常需要了解一段時(shí)間的數(shù)據(jù)變化趨勢(shì)[1,2]。折線圖使用點(diǎn)在橫軸和縱軸的位置代表某個(gè)時(shí)間和數(shù)據(jù)值，是地震前兆觀測(cè)數(shù)據(jù)可視化中最常用的方法。在可視化繪圖的過(guò)程中，尤其在大數(shù)據(jù)時(shí)代下的web環(huán)境中，高采樣、長(zhǎng)時(shí)間的數(shù)據(jù)一方面會(huì)加重?cái)?shù)據(jù)傳輸負(fù)擔(dān)，增加網(wǎng)絡(luò)延遲，降低用戶體驗(yàn)度[3]；另一方面超量的數(shù)據(jù)顯示極其密集，無(wú)法體現(xiàn)數(shù)據(jù)形態(tài)，從而無(wú)法為科研人員提供有效的價(jià)值。因此，對(duì)地震前兆觀測(cè)數(shù)據(jù)進(jìn)行降采樣，消除冗余信息的同時(shí)保持?jǐn)?shù)據(jù)整體形態(tài)不變是可視化的首要任務(wù)[4]。

常用降采樣方法一般有均值、中位數(shù)、最小標(biāo)準(zhǔn)誤差(Minimum Standard Error, MSE)，最大值最小值、隨機(jī)數(shù)采樣法，但是這些方法都會(huì)平滑折線圖的峰谷，不能突出細(xì)節(jié)；基于MSE變形的低時(shí)效性的最長(zhǎng)線算法(Longest-Line-Bucket, LLB)能有效保留細(xì)節(jié)部分，但是LLB算法的時(shí)間復(fù)雜度高；基于有效區(qū)域的最大三角形三桶算法LTTB(Largest-Triangle-Three-Buckets)[5]，能在有效保留細(xì)節(jié)部分的同時(shí)保持原始數(shù)據(jù)的形態(tài)，其時(shí)間復(fù)雜度為O(n)。

降采樣前后折線的相似度度量問(wèn)題一直未得到有效的解決[6-9]。歐氏距離和動(dòng)態(tài)時(shí)間規(guī)整(DTW)距離是常用的相似性度量距離方法。歐氏距離需要相同維度[10,11]，在此基礎(chǔ)上提出了基于歐氏距離的離散Fréchet距離的曲線相似判別算法，雖然對(duì)比的曲線維度是不一致的，但是維度差距也不能太大。前兆數(shù)據(jù)采樣前后的維度差距通常在一個(gè)數(shù)量級(jí)以上，利用此方法判別的結(jié)論不夠嚴(yán)謹(jǐn)。而在語(yǔ)音識(shí)別領(lǐng)域提出的DTW雖然也可以計(jì)算不同維度曲線的相似度，但是由于時(shí)間復(fù)雜度高，其應(yīng)用范圍受到了極大的限制[8]；針對(duì)DTW時(shí)間復(fù)雜度高的問(wèn)題，學(xué)者們使用了基于編輯距離(edit distance)的時(shí)間序列度量方法，但是依舊存在O(n2)的高復(fù)雜度[12-14]，無(wú)法直接用于評(píng)估前兆數(shù)據(jù)的降采樣前后折線的相似度。

綜上所述，研究人員在基于歐氏距離和DTW距離上的相似性度量方面提出了較多的思路和方法，但是度量效果并不理想。而在圖像搜索領(lǐng)域，相似圖像的檢索方式有多種，并以哈希算法衍生出多種算法[15-17]。本文提出一種基于最大三角形采樣算法的地震大數(shù)據(jù)可視化解決方案。為了評(píng)價(jià)采樣算法質(zhì)量，還提出一種基于圖像哈希算法的相似度評(píng)價(jià)算法。將地震前兆大數(shù)據(jù)可視化采樣前后的折線圖轉(zhuǎn)為2張圖像，并使用感知哈希算法得到2張圖像的指紋，然后將其量化為漢明距離，最后通過(guò)比較2張圖像的漢明距離來(lái)評(píng)價(jià)采樣前后2張圖片的相似度。

1 降采樣方法

本文選擇了5種降采樣算法：均值、最大值、最小值、中位數(shù)、LTTB。這五種算法的第一步均是把原始時(shí)間序列數(shù)據(jù)均等劃分為N個(gè)時(shí)間窗口，N為降采樣后點(diǎn)的個(gè)數(shù)，其中第1塊和最后1塊內(nèi)只有一個(gè)點(diǎn)，接下來(lái)第二步遍歷N-2個(gè)塊。不同的是：均值采樣，塊內(nèi)計(jì)算平均值作為采樣點(diǎn)；LTTB算法，從第一個(gè)點(diǎn)A開(kāi)始，以第三個(gè)塊的均值當(dāng)作支點(diǎn)C，遍歷第2個(gè)塊的所有點(diǎn)B′，三點(diǎn)可以組成一個(gè)三角形AB′C，使得三角形面積最大的B′點(diǎn)即作為當(dāng)前塊的采樣點(diǎn)；最大值算法，使用每個(gè)塊內(nèi)的最大值作為當(dāng)前塊的采樣點(diǎn)；最小值算法，使用每個(gè)塊內(nèi)的最小值作為當(dāng)前塊的采樣點(diǎn)；中位數(shù)，使用每個(gè)塊內(nèi)的中間位置的值作為當(dāng)前塊的采樣點(diǎn)。

5種算法對(duì)比分析：均值采樣算法的優(yōu)點(diǎn)是處理速度快，能保留部分趨勢(shì)，缺點(diǎn)在于不能保留最值細(xì)節(jié)，平滑了原始數(shù)據(jù)的峰谷，使得細(xì)節(jié)不突出；LTTB算法的優(yōu)點(diǎn)是加強(qiáng)了峰谷細(xì)節(jié)表現(xiàn)的同時(shí)又保留了整體的趨勢(shì)；最大值能突出峰值但是丟失谷值；最小值能突出谷值但是丟失峰值；中位數(shù)較為隨機(jī)，很容易丟失峰谷值。

2 相似度評(píng)價(jià)

時(shí)間序列數(shù)據(jù)作為自然界中最基礎(chǔ)、最普遍的一種數(shù)據(jù)。通常在二維平面上以折線圖的形式存在。比較降采樣前后2個(gè)時(shí)間序列數(shù)據(jù)的相似度可以轉(zhuǎn)化為比較2個(gè)折線圖的相似度。事實(shí)上，利用數(shù)學(xué)方法對(duì)圖像形態(tài)進(jìn)行描述的方法還不成熟[8]。如果從視覺(jué)角度出發(fā)，比較折線形態(tài)實(shí)際上就是比較兩張圖像的相似度,進(jìn)而把降采樣的相似度評(píng)估轉(zhuǎn)化為降采樣前后圖像的相似度評(píng)估。其中計(jì)算圖像相似度評(píng)估廣泛用于圖像領(lǐng)域內(nèi)縮略圖和重復(fù)圖像檢索。

2.1 圖像相似度

某個(gè)測(cè)項(xiàng)的觀測(cè)數(shù)據(jù)在二維平面上是由觀測(cè)時(shí)間和觀測(cè)值組成的坐標(biāo)軸上的點(diǎn)X[i，j]，這個(gè)測(cè)項(xiàng)的趨勢(shì)即是將這些離散點(diǎn)依次連接起來(lái)的形成的形態(tài)S。如果將這個(gè)二維坐標(biāo)看做圖像，形態(tài)S就是圖像的內(nèi)容，點(diǎn)X就是部分圖像的像素點(diǎn)。把降采樣前后的折線看做兩張不同的圖像，評(píng)價(jià)降采樣相似度問(wèn)題便轉(zhuǎn)化成比較兩張圖像的相似度，進(jìn)而轉(zhuǎn)化為計(jì)算兩張圖像的漢明距離。對(duì)于兩張像素點(diǎn)相同的圖像，漢明距離為圖像對(duì)應(yīng)像素點(diǎn)的值不相等的總個(gè)數(shù)，距離越小，即2張圖像越相似。

比較兩張圖像的相似度，最簡(jiǎn)單的想法是遍歷圖像的像素點(diǎn)。但是這種方法時(shí)間復(fù)雜度為O(n2)，并且對(duì)圖像的旋轉(zhuǎn)、縮小、放大等變化很敏感，實(shí)用性較低。感知哈希算法常用來(lái)檢測(cè)重復(fù)圖像，它比傳統(tǒng)的加密哈希如MD5,SHA-1等容錯(cuò)率更高，精確度也更高。

2.2 感知哈希算法

感知哈希算法是一類算法的總稱，包括均值哈希(aHash)、感知哈希(pHash)、差異值哈希(dHash)[18]。其中pHash精確度高，實(shí)際應(yīng)用廣泛。pHash使用離散余弦變換(DCT)來(lái)降低頻率，把圖像分離成分率的集合，再得到信息指紋即哈希值。

離散余弦變換是圖像處理中常用的一種正交變換，一維正變換如下:

(1)

(2)

式中，F(xiàn)(u)是第u個(gè)余弦變換系數(shù)，u是廣義頻率變量，u=1，2，3……N-1；f(x)是時(shí)域N點(diǎn)序列，x=0，1，2……N-1。

(3)

(4)

(5)

(6)

二維離散余弦變換可寫(xiě)成矩陣式:

[F(u,v)]=[A][f(x,y)][A]T

(7)

式中，f(x,y)是空間域二維向量之元素，x,y=0,1,2,……,N-1；F(u,v)是變換系數(shù)陣列之元素。式中表示的陣列為N×N。

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)來(lái)源

本文選取的前兆預(yù)處理數(shù)據(jù)：天津臺(tái)測(cè)點(diǎn)2北西向長(zhǎng)極距地電場(chǎng)觀測(cè)秒采值數(shù)據(jù)，自2018年1月6日零時(shí)至2018年1月8日1時(shí)一共172800個(gè)點(diǎn)。

3.2 實(shí)驗(yàn)分析

以地電場(chǎng)觀測(cè)數(shù)據(jù)為例，設(shè)置不同的降采樣率,選取不同壓縮大小的圖像、不同的降采樣方式進(jìn)行實(shí)驗(yàn)比較。以pHash計(jì)算漢(海)明距離為核心的實(shí)驗(yàn)流程圖如圖1所示。

先將降采樣前后的折線保存為圖像格式，再通過(guò)感知哈希算法計(jì)算哈希值，最后哈希值轉(zhuǎn)化為漢明距離，通過(guò)漢明距離來(lái)量化采樣前后的折線相似度。得到哈希值的兩個(gè)圖像之間的漢明距離是兩個(gè)哈希值對(duì)應(yīng)位置的不同字符的個(gè)數(shù)，不同字符個(gè)數(shù)越少，即相似度越高。

17萬(wàn)余條數(shù)據(jù)繪制成圖像后得到的原始數(shù)據(jù)圖、LTTB降采樣圖、均值降采樣圖、最大最小降采樣圖、中位數(shù)降采樣圖形態(tài)如圖2、圖3所示。

從圖2和圖3能發(fā)現(xiàn)均值等傳統(tǒng)降采樣方法的細(xì)節(jié)沒(méi)有LTTB明顯，并且整體趨勢(shì)也是LTTB保持得更完整,特別是采樣率設(shè)置的為0.001的時(shí)候，只有LTTB算法還能保持原始數(shù)據(jù)趨勢(shì)。按照?qǐng)D1的算法流程圖，分別計(jì)算LTTB、AVG降采樣后的形態(tài)圖與原始形態(tài)圖的漢明距離。

由圖2可以看出，經(jīng)過(guò)LTTB算法降采樣后的折線形狀與原始圖像最為相似。本文使用pHash作為評(píng)價(jià)指標(biāo)，不同的采樣率實(shí)驗(yàn)結(jié)果如表1。

前文提到，2張圖像的漢明距離越小代表圖像越相似。從圖2可以看出，使用了LTTB算法降采樣后同時(shí)保留了細(xì)節(jié)體現(xiàn)和整體趨勢(shì)。由表1可以看出，在不同采樣率下，使用pHash算法判定LTTB算法降采樣后的折線圖與原折線圖的漢明距離均是最小，佐證了圖2的結(jié)果。

而且當(dāng)圖像壓縮尺寸越大時(shí)，不同降采樣算法的差距越明顯，當(dāng)采樣率為0.1時(shí)，不同的圖像尺寸評(píng)價(jià)結(jié)果如圖4所示。

從圖4中可觀察到，降采樣算法的效果是可以量化分析的，LTTB算法降采樣后的折線圖與原折圖的距離均小于其他常用降采樣后的折線圖與原折圖的距離，并且隨著圖像尺寸的增加，這兩種距離值的差距越來(lái)越明顯。

實(shí)驗(yàn)結(jié)果說(shuō)明，從效果上，LTTB算法的降采樣和常用降采樣算法相比，LTTB能在保持整體趨勢(shì)的同時(shí)保留細(xì)節(jié)。從算法運(yùn)行效率上分析，LTTB算法的是時(shí)間復(fù)雜度為O(n)，隨著原始數(shù)據(jù)量的增加，LTTB算法運(yùn)行效率并不會(huì)出現(xiàn)指數(shù)型增長(zhǎng)。因此在web環(huán)境下，服務(wù)器端可以使用LTTB算法進(jìn)行降采樣，再將少量的數(shù)據(jù)傳輸回用戶，縮小耗時(shí)會(huì)極大地提升用戶體驗(yàn)度。

4 結(jié)論

以前兆觀測(cè)數(shù)據(jù)中的17萬(wàn)余條地電場(chǎng)觀測(cè)秒采值數(shù)據(jù)進(jìn)行降采樣實(shí)驗(yàn)，分別使用均值、最大值,最小值，中位數(shù)等常用降采樣算法和LTTB降采樣算法，同時(shí)使用pHash算法計(jì)算出的漢明距離對(duì)降采樣效果進(jìn)行量化評(píng)估。相比于均值等常用降采樣算法，LTTB算法能在保留原有數(shù)據(jù)形態(tài)的同時(shí)保留數(shù)據(jù)變化細(xì)節(jié)，更適合用于前兆觀測(cè)數(shù)據(jù)降采樣。