王琪， 崔榮一

( 延邊大學(xué) 工學(xué)院， 吉林 延吉 133002 )

0 引言

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展和文檔數(shù)據(jù)的日益增加，如何有效管理和使用文檔逐漸成為人們關(guān)注的問(wèn)題.版面文檔內(nèi)容復(fù)雜度是評(píng)價(jià)版面內(nèi)容組成情況的主要指標(biāo)之一，它有助于人們了解文檔的本質(zhì)屬性[1-2]以及分析和處理文檔[3]130.傳統(tǒng)的版面分析是將版面內(nèi)容作為一個(gè)完整的圖像，并通過(guò)對(duì)版面圖像進(jìn)行劃分等處理將文檔分割成文字、表格以及圖像等元素，以此為后續(xù)的純文本版面分析以及字符識(shí)別做準(zhǔn)備[4].評(píng)估版面圖像復(fù)雜度時(shí),因所關(guān)注的內(nèi)容不同，其評(píng)價(jià)方法也有所不同.例如: Peters等利用邊緣與灰度級(jí)對(duì)圖像的復(fù)雜度進(jìn)行了評(píng)價(jià)[5].基于文獻(xiàn)[5]，高振宇等利用圖像的信息熵、紋理以及邊緣信息等特征對(duì)圖像的復(fù)雜度進(jìn)行了分析，并采用等權(quán)重系數(shù)加權(quán)求和的方法對(duì)圖像的復(fù)雜度進(jìn)行了定量的評(píng)估[3]132.Zou等利用圖像的紋理特征研究了圖像的復(fù)雜度，并利用灰度共生矩陣對(duì)紋理特征進(jìn)行了分析[6].上述方法中，研究者或只是對(duì)圖像進(jìn)行了定性的描述，或沒(méi)有考慮各指標(biāo)間的權(quán)重，即沒(méi)有給出準(zhǔn)確、定量的描述方法.

計(jì)算機(jī)存儲(chǔ)的版面文檔信息中，包含圖像空間分布的像素信息(灰度值或彩色數(shù)字化編碼)和文字部分的文字編碼，即文檔的二進(jìn)制字節(jié)流中含有圖像和文本的原本信息(像素和字符)；因此，對(duì)文件字節(jié)流的復(fù)雜度進(jìn)行分析可判定版面的全局復(fù)雜度.基于此，本文以圖文要素構(gòu)成的word 2003版面存儲(chǔ)文檔為研究對(duì)象，提出一種基于文件字節(jié)流信息熵的版面全局復(fù)雜度的度量方法，并通過(guò)實(shí)驗(yàn)驗(yàn)證本文方法的有效性.

1 基于字節(jié)流信息熵的版面內(nèi)容復(fù)雜度評(píng)估

1.1 文件字節(jié)流的信息熵

研究表明，信息熵可用于描述信源平均不確定性[7].本文采取二進(jìn)制方式讀取文件，把不同的字節(jié)值視為不同的信源符號(hào)(稱之為字節(jié)符號(hào))，然后通過(guò)統(tǒng)計(jì)文件中各字節(jié)符號(hào)出現(xiàn)的次數(shù)，確定信源符號(hào)的概率分布，進(jìn)而計(jì)算出該文件的字節(jié)流信息熵H(X).信息熵的計(jì)算公式為：

(1)

其中P(ai) (i=1,2,…,q)為字節(jié)值為i的字節(jié)符號(hào)ai(i=1,2,…,q)的先驗(yàn)概率，q為不同字節(jié)符號(hào)的個(gè)數(shù).因1個(gè)字節(jié)為8位二進(jìn)制數(shù)，故q的值為28=256.式(1)中，字節(jié)符號(hào)之間是相互獨(dú)立的，而在實(shí)際文檔中，因文檔內(nèi)容之間具有一定的依賴性，所以字節(jié)之間存在關(guān)聯(lián)性.為了真實(shí)地反映字節(jié)流信息熵，本文采用二維離散平穩(wěn)信源的信息熵.在二維離散平穩(wěn)信源的隨機(jī)序列(X1,X2,…,Xi,…，Xn)中，只有相鄰的兩個(gè)符號(hào)之間具有依賴關(guān)系.考慮到相鄰字節(jié)之間的相關(guān)性，將上述隨機(jī)序列分成每?jī)蓚€(gè)符號(hào)為一組，以此構(gòu)成2次擴(kuò)展信源，其形式為X’=XiXi+1.該信源信息熵的計(jì)算公式為：

(2)

其中P(aiaj) (i,j=1,2,…,q)為2次擴(kuò)展信源輸出符號(hào)X1X2的聯(lián)合概率.

在離散平穩(wěn)有記憶信源中，多個(gè)符號(hào)間具有相互依賴關(guān)系，因此可通過(guò)N次擴(kuò)展信源來(lái)計(jì)算信源的信息熵，并以此獲得平均符號(hào)熵.平均符號(hào)熵的計(jì)算公式為：

(3)

當(dāng)式(3)中的N足夠大時(shí)，平均符號(hào)熵趨于極限熵.

因式(3)計(jì)算出的二進(jìn)制字節(jié)流信息熵能夠真實(shí)地反映文檔(含圖像和文字)的統(tǒng)計(jì)特性，因此式(3)可以用來(lái)度量版面文檔的總體復(fù)雜度.另外，從香農(nóng)第一定理可知，該信息熵也能夠反映文檔可壓縮的理論界限.

1.2 基于N次擴(kuò)展字節(jié)符號(hào)的字節(jié)流信息熵的計(jì)算

圖1 數(shù)據(jù)處理示意圖

計(jì)算字節(jié)流信息熵時(shí)，首先把文件看成二進(jìn)制字節(jié)流，并設(shè)置N個(gè)字節(jié)緩沖區(qū)，用于保存文件中的N個(gè)字節(jié).將字節(jié)的內(nèi)容轉(zhuǎn)換為整數(shù)，即可獲得字節(jié)符號(hào)的索引值.讀取新字節(jié)時(shí)，首先將緩沖區(qū)的內(nèi)容左移一個(gè)字節(jié)(如圖1所示)，然后把新字節(jié)存放至緩沖區(qū)的末尾字節(jié)處，并計(jì)算字節(jié)符號(hào)的新索引值.根據(jù)每個(gè)索引值，統(tǒng)計(jì)字節(jié)符號(hào)出現(xiàn)的概率，再由公式(3)計(jì)算出該文件字節(jié)流N次擴(kuò)展的平均信息熵.

基于N次擴(kuò)展字節(jié)符號(hào)的平均信息熵的計(jì)算算法如下：

AlgorithmN-BYTE COMENTROPY

Input 版面文檔文件

Output 該文件的字節(jié)流信息熵entropy

Step 1 測(cè)量文件長(zhǎng)度并保存至fsize

Step 2 計(jì)算N次擴(kuò)展字節(jié)符號(hào)集合元素個(gè)數(shù)：n=28N

Step 3n個(gè)字節(jié)符號(hào)個(gè)數(shù)計(jì)數(shù)器symbol[0～n-1]清零：

fori=0 ton-1 do

symbol[i]=0

endfor

Step 4 讀入文件前N字節(jié)至字節(jié)符號(hào)緩沖區(qū)Nbyte[0～N-1]中

Step 5 計(jì)算N次擴(kuò)展首字節(jié)符號(hào)的索引index：

index=0

fori=0 toN-1 do

index=index*256+Nbyte[i]

endfor

Step 6N次擴(kuò)展首字節(jié)符號(hào)個(gè)數(shù)增1：

symbol[index]=symbol[index]+1

Step 7 對(duì)后續(xù)字節(jié)統(tǒng)計(jì)每一個(gè)N次擴(kuò)展字節(jié)符號(hào)的出現(xiàn)次數(shù)：

while (未遇到文件尾) do

Step 7.1 緩沖區(qū)Nbyte內(nèi)容左移一個(gè)字節(jié)：

fori=0 toN-1 do

Nbyte[i]=Nbyte[i+1]

endfor

Step 7.2 讀入新的字節(jié)到緩沖區(qū)元素Nbyte[N-1]中

Step 7.3 計(jì)算新的N次擴(kuò)展首字節(jié)符號(hào)的索引index：

index=0

fori=0 toN-1 do

index=index*256+Nbyte[i]

endfor

Step 7.4N次擴(kuò)展字節(jié)符號(hào)個(gè)數(shù)增1：

symbol[index]=symbol[index]+1

endwhile

Step 8 計(jì)算各字節(jié)符號(hào)出現(xiàn)的概率p[0～n-1]：

fori=0 ton-1 do

p[i]=symbol[i]/(fsize-N+1)

endfor

Step 9 計(jì)算并返回信息熵entropy：

entropy=0

fori=0 ton-1 do

entropy=entropy+(-p[i]*logp[i])

endfor

entropy=entropy/N

返回entropy

2 實(shí)驗(yàn)結(jié)果及分析

2.1 實(shí)驗(yàn)文檔的構(gòu)成

實(shí)驗(yàn)中，純圖片文檔由像素為32×32、640×480、1 024×768、1 280×960、1 600×1 200的圖像插入到word 2003文檔中構(gòu)成；純文本文檔由空白頁(yè)以及2、4、6、8、10、12頁(yè)的文本構(gòu)成；混合文檔由圖文混合的1頁(yè)文檔構(gòu)成.

2.2 字節(jié)流信息熵與復(fù)雜度的相關(guān)實(shí)驗(yàn)

1)擴(kuò)展級(jí)數(shù)N的確定.根據(jù)香農(nóng)信息理論，當(dāng)擴(kuò)展到一定程度時(shí)，平均信息熵將趨近于極限熵，并基本保持不變[7].編程實(shí)現(xiàn)上述算法，并通過(guò)實(shí)驗(yàn)取字節(jié)信息熵穩(wěn)定的N值作為擴(kuò)展級(jí)數(shù).由圖2可以看出,采用4,5-byte方式讀取文檔時(shí)，信息熵最小，且通過(guò)4,5-byte可以確定圖像的信息熵，因此本文取N=4.

2)圖像復(fù)雜程度與信息熵的關(guān)系.圖像復(fù)雜程度與信息熵的關(guān)系實(shí)驗(yàn)結(jié)果如3圖所示,圖3中不同的線型表示不同復(fù)雜程度的圖像.將不同大小的簡(jiǎn)單圖像與真實(shí)場(chǎng)景圖像(圖4)進(jìn)行對(duì)比，結(jié)果表明，復(fù)雜圖像的信息熵明顯大于簡(jiǎn)單圖像的信息熵，因此可通過(guò)計(jì)算信息熵的方法來(lái)判斷文檔中圖像的復(fù)雜程度.

圖2 圖像像素大小與信息熵的關(guān)系

圖3 4-byte讀取時(shí)圖像復(fù)雜程度與信息熵的關(guān)系

(a)畫(huà)面較為復(fù)雜的圖像 (b)畫(huà)面較為簡(jiǎn)單的圖像圖4 實(shí)驗(yàn)圖像

3)文檔大小與信息熵的關(guān)系.由圖5可以看出，文檔長(zhǎng)度越長(zhǎng)，信息熵越大；因此，可采用基于信息熵的方法來(lái)評(píng)估不同長(zhǎng)度文檔的復(fù)雜程度.采用同一種讀取方式時(shí)，信息熵越大，說(shuō)明文檔長(zhǎng)度越長(zhǎng).

4)文檔內(nèi)容與信息熵的關(guān)系.由圖6可以看出，采用4-byte方式讀取文檔時(shí)，圖文混合文檔的信息熵最大，其次為僅含圖片的文檔，最小的為僅包含文字的文檔；因此，在文檔篇幅一樣的情況下，可以利用信息熵來(lái)評(píng)估文檔的復(fù)雜程度.

圖5 文檔大小與信息熵的關(guān)系

圖6 文檔內(nèi)容與信息熵的關(guān)系

上述實(shí)驗(yàn)表明：對(duì)于同樣篇幅的文檔，圖文混合文檔的信息熵最大；文檔的長(zhǎng)度越長(zhǎng)，文檔的信息熵越大；對(duì)于純圖像文檔，畫(huà)面內(nèi)容豐富的圖像文檔的信息熵大于畫(huà)面簡(jiǎn)單的圖像文檔的信息熵.該結(jié)果與實(shí)際情況相符.

3 結(jié)論

本文采用文件字節(jié)流信息熵的方法對(duì)文檔內(nèi)容進(jìn)行了復(fù)雜度評(píng)估，該方法不用對(duì)文檔中圖文進(jìn)行細(xì)節(jié)劃分即可實(shí)現(xiàn)對(duì)文檔內(nèi)容復(fù)雜程度的評(píng)估；因此，本文提出的方法優(yōu)于傳統(tǒng)的版面分析方法，且能夠提高文檔的分析效率.同時(shí)，本文方法也可為文檔的可壓縮性提供度量.本文在研究中僅考慮了以word 2003為存儲(chǔ)格式的文檔內(nèi)容復(fù)雜度，今后我們將采用不同的文檔格式(如PDF、RTF、TXT等)來(lái)測(cè)試本文方法的適用性.