基于文檔對(duì)象模型和圖像處理的網(wǎng)頁(yè)分割方法

賈柯禎

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

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，Web應(yīng)用早已融入了人們的日常生活。從網(wǎng)易、搜狐等各種大型門戶網(wǎng)站，到京東、淘寶等熱門網(wǎng)上商城，再到微博、微信等流行社交平臺(tái)，都或多或少地將Web應(yīng)用作為其載體?？梢哉f(shuō)，Web應(yīng)用已經(jīng)與我們密不可分。

Web應(yīng)用是一種通過(guò)Web訪問(wèn)的應(yīng)用程序，它基于B/S（Browser/Server）結(jié)構(gòu)。通常情況下，用戶通過(guò)Web瀏覽器訪問(wèn)Web應(yīng)用，并與它進(jìn)行交互活動(dòng)。自1990年第一款瀏覽器Nexus（原名WorldWideWeb）問(wèn)世至今，瀏覽器的品牌已經(jīng)達(dá)到了數(shù)十種之多。

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

1 相關(guān)工作

現(xiàn)存的跨瀏覽器兼容性測(cè)試方法大部分通過(guò)分析文檔對(duì)象模型 DOM（Document Object Model）來(lái)進(jìn)行[1-5]，有些也結(jié)合一些圖像處理技術(shù)[2,4,6,7]，其中大多數(shù)都選擇使用“先分割再比較”的方法。

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

Browserbite[6]使用基于圖像的方法對(duì)網(wǎng)頁(yè)截圖進(jìn)行分割。它首先使用Harris角點(diǎn)提取算法[8]提取圖像的角點(diǎn)像素，使用膨脹方法對(duì)這些像素進(jìn)行處理，得到若干連通區(qū)域。當(dāng)連通區(qū)域面積或個(gè)數(shù)符合預(yù)設(shè)條件時(shí)，得到最終的分割結(jié)果。Browserbite的方法在減少計(jì)算開(kāi)銷上明顯優(yōu)于基于DOM的方法，但其分割得到的區(qū)域仍有較少重疊，并且對(duì)于部分網(wǎng)頁(yè)，很難解釋經(jīng)過(guò)分割得到的區(qū)域有何意義。此外，網(wǎng)頁(yè)上不構(gòu)成不兼容的差異也可能導(dǎo)致出現(xiàn)不同的分割。而Browser?bite認(rèn)為如果分割得到的子塊不匹配，則網(wǎng)頁(yè)構(gòu)成不兼容，這將產(chǎn)生一部分假陽(yáng)性。

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

2 分割方法

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

圖1 分割方法主要步驟

我們首先對(duì)待測(cè)網(wǎng)頁(yè)在不同瀏覽器上的渲染結(jié)果進(jìn)行截圖，并獲得其相應(yīng)的DOM對(duì)象。對(duì)得到的網(wǎng)頁(yè)截圖，我們將其進(jìn)行灰度化操作，轉(zhuǎn)為灰度圖像。對(duì)灰度圖像，我們進(jìn)行角點(diǎn)提取，使用Harris角點(diǎn)算法，得到圖像中的角點(diǎn)。通過(guò)將角點(diǎn)的灰度值設(shè)為255，其余點(diǎn)的灰度值設(shè)為0，我們將原圖像轉(zhuǎn)換為二值圖像。

對(duì)二值圖像，我們進(jìn)行膨脹操作。對(duì)于一個(gè)在二值圖像上滑動(dòng)的3×3的窗口，如果其中心是一個(gè)值為255的點(diǎn)，則將整個(gè)窗口覆蓋的二值圖像的像素點(diǎn)都標(biāo)記為255。當(dāng)窗口遍歷完一次二值圖像之后，將所有標(biāo)記為255的點(diǎn)的值置為255。

經(jīng)過(guò)膨脹操作，二值圖將形成若干個(gè)連通區(qū)域。我們將連通區(qū)域的個(gè)數(shù)或大小設(shè)置為終止條件，經(jīng)過(guò)多次膨脹操作，得到最終的結(jié)果。我們?nèi)∵@些區(qū)域的最小橫坐標(biāo)、最大橫坐標(biāo)、最小縱坐標(biāo)、最大縱坐標(biāo)，得到一個(gè)包含了該區(qū)域的矩形。

接著，我們引入網(wǎng)頁(yè)DOM信息，對(duì)這些矩形進(jìn)行合并與分割。我們遍歷DOM樹(shù)，對(duì)于每個(gè)節(jié)點(diǎn)，調(diào)用JavaScript的 getBoundingClientRect（）函數(shù)并計(jì)算得到其四角坐標(biāo)，得到該節(jié)點(diǎn)對(duì)應(yīng)的矩形。將節(jié)點(diǎn)矩形和之前得到的二值矩形進(jìn)行對(duì)比，將出現(xiàn)下列情況：

●若節(jié)點(diǎn)矩形與二值矩形無(wú)交集，直接尋找下個(gè)二值矩形再進(jìn)行比較，若所有二值矩形均與當(dāng)前節(jié)點(diǎn)矩形無(wú)交集，則忽略當(dāng)前節(jié)點(diǎn)矩形，訪問(wèn)其兄弟節(jié)點(diǎn)。

●若節(jié)點(diǎn)矩形僅包含一個(gè)二值矩形，將該節(jié)點(diǎn)矩形作為分割的最終結(jié)果。

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

●若節(jié)點(diǎn)矩形包含了兩個(gè)及以上的二值矩形，若該節(jié)點(diǎn)為DOM樹(shù)的葉子結(jié)點(diǎn)，則將該節(jié)點(diǎn)矩形作為分割的最終結(jié)果。否則，遍歷該節(jié)點(diǎn)的下一層子節(jié)點(diǎn)，并進(jìn)行對(duì)比。

經(jīng)過(guò)以上步驟，我們將得到最終的網(wǎng)頁(yè)分割。

3 結(jié)語(yǔ)

本文提出了一種新的基于文檔對(duì)象模型和圖像處理的網(wǎng)頁(yè)截圖分割方法，它通過(guò)圖像處理的方法得到初步圖像分割，并使用DOM信息約束它們，得到最終的結(jié)果。

相比于Browserbite，我們的方法得到的分割結(jié)果更合理，更易于匹配。相比于WebDiff和CrossCheck，我們的方法需要對(duì)比的次數(shù)更少，計(jì)算開(kāi)銷更低。

然而，本文的方法得到的結(jié)果仍有較少的假陽(yáng)性出現(xiàn)，其主要原因來(lái)自DOM樹(shù)結(jié)構(gòu)的差異。我們未來(lái)希望提出不依賴于DOM樹(shù)的新的分割方法，以杜絕這種假陽(yáng)性。

參考文獻(xiàn)：

[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.