基于自適應四叉樹的網頁分塊技術

邢益陽

（四川大學計算機學院，成都 610065）

0 引言

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

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

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

圖1 圖像的四叉樹例子

圖2 四叉樹的數據結構圖

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

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

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

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

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

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

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

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

1 自適應四叉樹

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

定義一棵四叉樹：

本文提出的自適應四叉樹算法的實現步驟為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 結語

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

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

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