基于自適應(yīng)四叉樹的網(wǎng)頁分塊技術(shù)

邢益陽

（四川大學(xué)計算機學(xué)院，成都 610065）

0 引言

最近幾年人工智能非?；馃?，其中使用的深度學(xué)習(xí)技術(shù)需要收集大量的數(shù)據(jù)，在足夠多的數(shù)據(jù)支撐下才能訓(xùn)練出完美的模型。圖像處理技術(shù)是深度學(xué)習(xí)的主要技術(shù)之一，為了獲取豐富的圖像特征信息，通常需要將圖像灰度化、二值化和角點檢測，等等[1]。圖像分割是圖像識別和計算機視覺至關(guān)重要的預(yù)處理，現(xiàn)有的圖像分割方法主要有以下幾類：基于閾值的分割方法、基于區(qū)域的分割方法、基于邊緣的分割方法以及基于特定理論的分割方法等[2]。

面向網(wǎng)頁的分塊通常采用基于DOM樹的方法或基于圖像處理的方法，對于基于DOM（Document Object Model）樹的網(wǎng)頁分塊，兩個DOM節(jié)點雖然不相同，但呈現(xiàn)的視覺效果可能一樣，而且DOM父子節(jié)點之間存在覆蓋關(guān)系，一個節(jié)點的屬性可能會影響另一個節(jié)點，導(dǎo)致網(wǎng)頁分塊誤判。本文采用圖像處理的方法，因為網(wǎng)頁截圖是網(wǎng)頁的最終渲染結(jié)果，符合人的視覺感知[3]，而基于四叉樹的方法能快速分割圖像，并保持圖像的邊緣細節(jié)，能獲得層次化的分塊節(jié)點和個數(shù)，本文提出的自適應(yīng)的四叉樹是基于閾值的分塊方法，通過遍歷像素點找到精準的分割坐標，使得圖像能被正確地分塊，提高兩個圖像差異的識別率。

四叉樹是一種樹狀的數(shù)據(jù)結(jié)構(gòu)，常用于二維空間數(shù)據(jù)的分析與分類，它將數(shù)據(jù)分成了四個象限，四叉樹常用于地圖的空間索引、稀疏數(shù)據(jù)、2D中的快速碰撞檢測[4-5]。通過四叉樹可以把圖像按一定規(guī)則切割成四個部分，如圖1、2所示，每一個節(jié)點下面又可以繼續(xù)分成四個節(jié)點，依次迭代即可得到切割后的圖像四叉樹。

圖1 圖像的四叉樹例子

圖2 四叉樹的數(shù)據(jù)結(jié)構(gòu)圖

此類四叉樹是均等切分的，不適用于網(wǎng)頁分塊，因為網(wǎng)頁是由各個大小不一的區(qū)塊組成，所以本文提出了自適應(yīng)四叉樹，切分后得到的四個子圖的大小與圖像屬性均方誤差和有關(guān)。

對圖像進行分割就需要給出分割的標準，本文分別采用了三種分割標準：“GBR顏色均方誤差”、“HSV顏色均方誤差”、“圖片信息熵”。

顏色是圖像的重要特征，也是人識別圖像的主要感知特征之一，圖像的RGB顏色均方誤差或HSV顏色均方誤差越大，圖像的顏色越豐富，圖像就不純，當誤差大于某一個閾值時，就認為圖像是應(yīng)該被切割的。對像素顏色特征出現(xiàn)的頻率進行統(tǒng)計可以直觀地表示圖像內(nèi)容：

RGB顏色均方誤差公式如下：

HSV顏色均方誤差的公式如下：

HSV模型是針對用戶觀感的一種顏色模型，側(cè)重于色彩表示，是統(tǒng)計 HSV 模型中的色調(diào)（H）、飽和度（S）、明度（V）得到的平均值。

信息熵是對信息的量化度量，信息熵越大，不確定性越大，那么對于圖像的信息熵來說它就越不純，說明圖像應(yīng)該被切割。計算圖像信息熵均方誤差的公式如下：

其中x表示像素的RGB中的某一個屬性，屬性的取值為（x1，x2，x3），p(xi)表示屬性值 xi出現(xiàn)的頻率，且有∑p(xi)=1，本文取的RGB模型的3個分量，采用RGB顏色均方誤差的好處是計算相似度時與圖像的旋轉(zhuǎn)平移和尺寸大小無關(guān)。

1 自適應(yīng)四叉樹

四叉樹被認為是二叉樹的高維變體，通常的四叉樹是直接均等切分，而采用自適應(yīng)的四叉樹需要找到最佳切割點，目標是使得4個小分塊的均方誤差和最小。

定義一棵四叉樹：

本文提出的自適應(yīng)四叉樹算法的實現(xiàn)步驟為：

（1）打開圖像并初始化圖片左上角坐標為（0，0）和第一個root節(jié)點，把圖片轉(zhuǎn)變成一棵四叉樹；

（2）分別從橫向和縱向遍歷圖片的像素點，計算切割圖像后得到的4個子圖的最小均方誤差和的切割點。計算像素點與像素平均值的歐氏距離：

①計算橫向切割圖像得到的2個子圖的均方誤差和最小的縱坐標yi；

②計算縱向切割圖像得到的2個子圖的均方誤差和最小的橫坐標xi；

（3）根據(jù)切割點的坐標(xi,yi)把一個圖像切割成4塊，以坐標為中點畫兩條線；

（4）把4個子圖實例化為樹的節(jié)點，并賦值給父圖；

（5）采用先序遍歷的方式，從左至右遍歷每一個節(jié)點，判斷切割后的4個子圖是否是葉子節(jié)點，如果已經(jīng)達到最大切割次數(shù)或節(jié)點的均方誤差小于閾值，則停止切割跳到步驟5，否則跳到步驟2，繼續(xù)迭代切割。

（6）結(jié)束切割，得到原圖的四叉樹分割圖像。

為了找到最佳切割點，如果從頭到尾遍歷每一個像素點[6]，效率會比較慢，時間復(fù)雜度為m*n。為了提升效率，只需要分別遍歷橫坐標和縱坐標，時間復(fù)雜度為m+n。先橫向遍歷橫坐標，使用一條直線將圖像豎直切割成兩個子圖，計算兩個子圖的均方誤差和，找到橫坐標xi，使得均方誤差和最小，然后再縱向遍歷縱坐標得到目標yi。

實驗用到的圖片的分辨率為512×512，選用的是騰訊NBA一個網(wǎng)頁的部分截圖，分別使用三種切割標準將圖像切割，選擇Python編程語言實現(xiàn)該算法（Python 3.6），主要使用的類庫是scikit-image，最終得到的實驗結(jié)果如圖3-5。

圖3 基于GBR顏色均方誤差的切割結(jié)果截圖

圖4 基于HSV顏色均方誤差的切割結(jié)果截圖

圖5 基于圖片信息熵均方誤差的切割結(jié)果截圖

將兩個網(wǎng)頁截圖分割后得到的4個小區(qū)塊一一對比，計算兩個區(qū)塊之間的相似度，低于某一閾值時說明兩個區(qū)塊有明顯的差異，從而找到網(wǎng)頁之間的不兼容性。把一個大的問題分割成各個小的問題并一一查找，可以提高網(wǎng)頁對比的效率。

使用均值哈希計算兩個圖像的相似度（距離越小圖片越相似，距離越大圖片差異性越大）[7]，設(shè)定閾值，從葉子節(jié)點開始遍歷并且只遍歷葉子節(jié)點，逆先序遍歷，兩張圖的相似度計算若大于閾值，則標記兩個子圖不相似，然后返回所有不相似的結(jié)果并標記于原圖，溯源可以幫助網(wǎng)頁維護人員做兼容性的修復(fù)。

2 結(jié)語

本文給出了基于自適應(yīng)四叉樹的網(wǎng)頁分塊算法，并分別對三種切割標準（RGB、HSV、信息熵的均方誤差）做了實驗，觀察實驗結(jié)果可以看出該算法可以得到滿意的分塊結(jié)果，但是距離整個網(wǎng)頁的精確分塊還有一定差距。

未來工作，將基于四叉樹的網(wǎng)頁分塊技術(shù)應(yīng)用到測試跨瀏覽器的網(wǎng)頁兼容性上，應(yīng)用到網(wǎng)絡(luò)主題爬蟲的網(wǎng)頁去噪上，可以迅速找到網(wǎng)頁中的正文，去除無關(guān)簡要的廣告之類的信息，具有一定的實際意義。

目前只能做到切割自適應(yīng)，無法做到閾值自適應(yīng)，因為不同的圖像顏色有所差異，所以后面的研究是結(jié)合深度學(xué)習(xí)訓(xùn)練出模型來做閾值自適應(yīng)的四叉樹。