基于文檔對象模型和圖像處理的網頁分割方法

賈柯禎

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

0 引言

隨著互聯網技術的發展，Web應用早已融入了人們的日常生活。從網易、搜狐等各種大型門戶網站，到京東、淘寶等熱門網上商城，再到微博、微信等流行社交平臺，都或多或少地將Web應用作為其載體。可以說，Web應用已經與我們密不可分。

Web應用是一種通過Web訪問的應用程序，它基于B/S（Browser/Server）結構。通常情況下，用戶通過Web瀏覽器訪問Web應用，并與它進行交互活動。自1990年第一款瀏覽器Nexus（原名WorldWideWeb）問世至今，瀏覽器的品牌已經達到了數十種之多。

跨瀏覽器差異的原因主要來自不同瀏覽器對于HTML、CSS以及JavaScript代碼的不同解釋。但差異并不意味著不兼容，界定何種程度的差異構成了不兼容是一件非常主觀的事情。不論是Web應用的設計者還是最終用戶，他們都希望網頁在所有瀏覽器上具有相同或相似的表現，除非存在的差異是設計者有意為之。雖然某些Web應用聲明了推薦瀏覽器及其版本，但對于用戶來說，專門為了該應用使用特定瀏覽器十分不便。因此，以檢測跨瀏覽器兼容性問題為目的的跨瀏覽器兼容性測試就顯得尤為重要。

1 相關工作

現存的跨瀏覽器兼容性測試方法大部分通過分析文檔對象模型 DOM（Document Object Model）來進行[1-5]，有些也結合一些圖像處理技術[2,4,6,7]，其中大多數都選擇使用“先分割再比較”的方法。

WebDiff[2]與CrossCheck[4]使用基于DOM的方法對網頁截圖進行分割。DOM是一個天然的樹形結構，通過對樹的遍歷，我們可以提取DOM中的每個節點的屬性。通過提取DOM節點的坐標以及尺寸信息，我們可以將其映射到網頁截圖的相應位置，并通過這些位置信息對網頁截圖進行分割，最終得到許多子圖像，每個子圖像都對應DOM中的一個節點。WebDiff的分割方法依賴于瀏覽器生成的DOM，它從根節點開始對DOM進行自底向上的遍歷，逐個比較節點對應的圖像區域。這將導致兩個問題。首先，DOM樹不盡相同，即使兩個瀏覽器產生了相同的網頁截圖，其DOM節點也不能保證一一對應，這在比較子圖時將產生問題。其次，在遍歷DOM的過程中，截圖的某些部位將會被重復比較多次，換言之，子圖之間會有重疊，這些重疊的部分將增加計算開銷。

Browserbite[6]使用基于圖像的方法對網頁截圖進行分割。它首先使用Harris角點提取算法[8]提取圖像的角點像素，使用膨脹方法對這些像素進行處理，得到若干連通區域。當連通區域面積或個數符合預設條件時，得到最終的分割結果。Browserbite的方法在減少計算開銷上明顯優于基于DOM的方法，但其分割得到的區域仍有較少重疊，并且對于部分網頁，很難解釋經過分割得到的區域有何意義。此外，網頁上不構成不兼容的差異也可能導致出現不同的分割。而Browser?bite認為如果分割得到的子塊不匹配，則網頁構成不兼容，這將產生一部分假陽性。

本文將結合基于圖像的方法和基于DOM的方法的思想，提出一種新的網頁分割方法。該方法得到的網頁分割更易于匹配，且假陽性率較低。

2 分割方法

本文提出的分割方法的主要步驟如圖1所示。

圖1 分割方法主要步驟

我們首先對待測網頁在不同瀏覽器上的渲染結果進行截圖，并獲得其相應的DOM對象。對得到的網頁截圖，我們將其進行灰度化操作，轉為灰度圖像。對灰度圖像，我們進行角點提取，使用Harris角點算法，得到圖像中的角點。通過將角點的灰度值設為255，其余點的灰度值設為0，我們將原圖像轉換為二值圖像。

對二值圖像，我們進行膨脹操作。對于一個在二值圖像上滑動的3×3的窗口，如果其中心是一個值為255的點，則將整個窗口覆蓋的二值圖像的像素點都標記為255。當窗口遍歷完一次二值圖像之后，將所有標記為255的點的值置為255。

經過膨脹操作，二值圖將形成若干個連通區域。我們將連通區域的個數或大小設置為終止條件，經過多次膨脹操作，得到最終的結果。我們取這些區域的最小橫坐標、最大橫坐標、最小縱坐標、最大縱坐標，得到一個包含了該區域的矩形。

接著，我們引入網頁DOM信息，對這些矩形進行合并與分割。我們遍歷DOM樹，對于每個節點，調用JavaScript的 getBoundingClientRect（）函數并計算得到其四角坐標，得到該節點對應的矩形。將節點矩形和之前得到的二值矩形進行對比，將出現下列情況：

●若節點矩形與二值矩形無交集，直接尋找下個二值矩形再進行比較，若所有二值矩形均與當前節點矩形無交集，則忽略當前節點矩形，訪問其兄弟節點。

●若節點矩形僅包含一個二值矩形，將該節點矩形作為分割的最終結果。

●若節點矩形與二值矩形相交或被二值矩形包含，將二值矩形分割為節點矩形部分與剩余部分，每個部分作為一個新的二值矩形。若節點矩形中僅包含一個新的二值矩形，則將節點矩形作為最終結果。

●若節點矩形包含了兩個及以上的二值矩形，若該節點為DOM樹的葉子結點，則將該節點矩形作為分割的最終結果。否則，遍歷該節點的下一層子節點，并進行對比。

經過以上步驟，我們將得到最終的網頁分割。

3 結語

本文提出了一種新的基于文檔對象模型和圖像處理的網頁截圖分割方法，它通過圖像處理的方法得到初步圖像分割，并使用DOM信息約束它們，得到最終的結果。

相比于Browserbite，我們的方法得到的分割結果更合理，更易于匹配。相比于WebDiff和CrossCheck，我們的方法需要對比的次數更少，計算開銷更低。

然而，本文的方法得到的結果仍有較少的假陽性出現，其主要原因來自DOM樹結構的差異。我們未來希望提出不依賴于DOM樹的新的分割方法，以杜絕這種假陽性。

參考文獻：

[1]Mesbah A,Prasad M R.Automated Cross-browser Compatibility Testing[C].International Conference on Software Engineering.IEEE,2011:561-570.

[2]Choudhary S R,Versee H,Orso A.WEBDIFF:Automated Identification of Cross-browser Issues in Web Applications[C].IEEE International Conference on Software Maintenance.IEEE Computer Society,2010:1-10.

[3]Choudhary S R,Prasad M R,Orso A.CrossCheck:Combining Crawling and Differencing to Better Detect Cross-browser Incompatibilities in Web Applications[C].IEEE Fifth International Conference on Software Testing,Verification and Validation.IEEE Computer Society,2012:171-180.

[4]Choudhary S R,Prasad M R,Orso A.X-PERT:Accurate Identification of Cross-Browser Issues in Web Applications[C].International Conference on Software Engineering.IEEE,2013:702-711.

[5]Dallmeier V,Burger M,Orth T,et al.WebMate:Generating Test Cases for Web 2.0[J].2013,133:55-69.

[6]Saar T,Dumas M,Kaljuve M,et al.Browserbite:Cross Browser Testing Via Image Processing[J].Software-Practice&Experience,2016,46（11）:1459-1477.

[7]Lu P,Fan W,Sun J,et al.Webpage Cross-browser Test From Image Level[C].IEEE International Conference on Multimedia and Expo.IEEE Computer Society,2017:349-354.

[8]Harris C.A combined Corner and Edge Detector[J].Proc Alvey Vision Conf,1988,1988（3）:147-151.