一種基于LBT的分布式圖像壓縮算法

董卓亞

（商丘師范學(xué)院 計算機(jī)與信息技術(shù)學(xué)院，河南 商丘 476000）

無線傳感網(wǎng)絡(luò)（WSNs）[1]由于其巨大的實際應(yīng)用價值，近年來引起了國內(nèi)外學(xué)術(shù)界的密切關(guān)注，正廣泛的應(yīng)用于軍事、農(nóng)業(yè)、醫(yī)療業(yè)等各個領(lǐng)域，已經(jīng)在只能采集到單一環(huán)境數(shù)據(jù)的基礎(chǔ)上，延伸到了能采集和處理音頻、視頻、圖像等大數(shù)據(jù)量多媒體信息的一種新型的傳感器網(wǎng)絡(luò)——無線多媒體傳感器網(wǎng)絡(luò)（WMSNs）[2]。大量裝備有微型傳感器的傳感器節(jié)點隨機(jī)的布置在監(jiān)測區(qū)域內(nèi)構(gòu)成了無線多媒體傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)，這些節(jié)點一般具有以下特點：一是能量嚴(yán)重受限；二是處理能力一般不強(qiáng)；三是存儲能力受限。因此這些單節(jié)點就很難完成大尺寸、高分辨率圖像的壓縮處理，這就給給WMSNs的研究和應(yīng)用提出了巨大的挑戰(zhàn)，WMSNs相關(guān)理論和技術(shù)還非常不成熟，尤其是如何在低能耗、低復(fù)雜度的情況下獲得高質(zhì)量的圖片、視頻等多媒體信息成為制約WMSN發(fā)展的首要問題。

針對這些問題，大量學(xué)者做了相關(guān)研究，最廣泛的即分布式視頻編碼[3]，但是我們知道無線多媒體傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)往往是未知的，而這些分布式編碼大部分要求傳感器節(jié)點間的關(guān)聯(lián)結(jié)構(gòu)已知，然而在這種不固定多變的應(yīng)用環(huán)境下，各個節(jié)點間的關(guān)聯(lián)和分布很難確定。因此，一些學(xué)者提出了一種可行的方法就是利用傳感器節(jié)點部署較為密集的特點，采用大量節(jié)點同時監(jiān)測目標(biāo)區(qū)域，從不同角度采集大尺寸、高分辨率的圖像，并且通過“在網(wǎng)計算”的思想[4]，將單個節(jié)點的計算能耗壓力均衡地分配到其他多個節(jié)點上，由多個節(jié)點分布并行的完成多媒體信息的處理和傳輸。那么這種方法就有效的降低了單個節(jié)點的計算復(fù)雜度，從而降低了能耗，并且使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點的處理能力和存儲資源有效的得到了整合。

由此，文中提出了一種基于雙正交重疊變換（Lapped Biorthogonal Trans form，LBT）的分布式圖像壓縮算法。首先采用一種分簇方法，選取能量較大的節(jié)點為簇頭，剩余節(jié)點仍以此方法為簇，再在以此為簇的網(wǎng)絡(luò)結(jié)構(gòu)中；其次，基于LBT圖像壓縮算法將散布到檢測環(huán)境中的傳感器節(jié)點采集到的數(shù)據(jù)信息分塊發(fā)送給簇內(nèi)節(jié)點進(jìn)行壓縮，再由簇內(nèi)節(jié)點發(fā)送給簇頭，實現(xiàn)了數(shù)據(jù)處理的低復(fù)雜度、高壓縮效能；最后采用多個節(jié)點相互協(xié)作的分布式壓縮算法，多個節(jié)點共同完成圖像的壓縮編碼和轉(zhuǎn)發(fā)任務(wù)，從而極大地均衡緩解了各個節(jié)點的能耗壓力。由實驗得出，在節(jié)點部署不均且較為密集時，此算法均衡了網(wǎng)絡(luò)能耗，從而降低了單個節(jié)點的能耗壓力，使網(wǎng)絡(luò)生存周期得到了延長。

1 算法引入

從目前研究情況來看，JPEG2000壓縮算法[5]在高壓縮比情況下矩形片會出現(xiàn)邊緣，并且劃分的片越小，其塊邊緣效應(yīng)越明顯，導(dǎo)致圖像質(zhì)量較差，若用幀間壓縮（預(yù)測編碼或運動估計）方法來克服此問題，但由于幀間壓縮計算復(fù)雜度高，能耗高；而離散余弦變換（DCT）雖然具有良好的去除數(shù)據(jù)相關(guān)效果及低計算復(fù)雜性的特點，但是同樣存在嚴(yán)重的塊邊緣效應(yīng)現(xiàn)象，從而圖像質(zhì)量很差。所以均不適合于無線多媒體傳感器網(wǎng)絡(luò)。

針對存在的這些塊邊緣效應(yīng)問題，研究人員在圖像壓縮中又引入了以實現(xiàn)信號的部分重疊處理為原理的LBT技術(shù)。它通常具有在DCT變換后的頻域進(jìn)行重疊變換和在DCT變換前直接在時域進(jìn)行重疊變換這兩類典型的變換過程，這兩類過程被稱為后處理和預(yù)處理[6]。該LBT技術(shù)不僅使塊邊緣效應(yīng)有了明顯的消除，而且此算法計算簡單，有效的減小了節(jié)點的能耗壓力。在為了保持其較低的塊邊緣效應(yīng)的同時，進(jìn)一步降低對節(jié)點計算能力的要求，提出了一種基于雙正交重疊變換LBT的快速整數(shù)實現(xiàn)算法[7]。在變換過程中所有系數(shù)均以分母為2的冪、分子為整數(shù)的分?jǐn)?shù)來近似得到，所以只存在整數(shù)的加法及位移運算。

在此基礎(chǔ)上，提出了一種基于LBT的無線多 媒體傳感器網(wǎng)絡(luò)分布式壓縮算法。由于WMSNs是以多節(jié)點協(xié)同的方式來實現(xiàn)圖像處理，所以在二維時域，傳統(tǒng)上的LBT因其以先行后列的順序?qū)K之間的信號分別進(jìn)行一維變換的方法明顯不適合。那么該算法就可以利用LBT變換可并行計算的特點，將圖像不同塊的變換在不同節(jié)點上并行進(jìn)行，就需要對處理過程進(jìn)行重新排列。先對塊信號做列預(yù)處理，然后以每8行為一個單位，獨立進(jìn)行列DCT處理，并且對每行都進(jìn)行LBT處理，最后再分別對這每個獨立單位的8×8的LBT系數(shù)塊進(jìn)行編碼。

假設(shè)相機(jī)節(jié)點采集到的圖像寬度為W，首先對獨立單位的8行數(shù)據(jù)進(jìn)行列預(yù)處理后，將這8行數(shù)據(jù)的前4行和以此8行數(shù)據(jù)為獨立單元上面的4行數(shù)據(jù)傳輸給中繼節(jié)點，然后再選擇后面的8行數(shù)據(jù)繼續(xù)進(jìn)行列預(yù)處理。那么中繼節(jié)點每次則只需要同步緩存8 W個像素，相機(jī)節(jié)點只需同步緩存12 W個像素。而對于5層小波變換，采用基于基于行變換的方法，則需要同步緩存大約183 W個點。

2 基于LBT的多節(jié)點協(xié)同分布式算法描述

首先是針對能量的改進(jìn)。選取簇頭的一個重要衡量標(biāo)準(zhǔn)就是節(jié)點的剩余能量的多少，那么我們就選取剩余能量較多的節(jié)點為相機(jī)節(jié)點，即簇頭；其次，針對節(jié)點地理分布不均的改進(jìn)。為了保證所有簇頭能覆蓋整個網(wǎng)絡(luò)，那么根據(jù)能量大小的不同這個標(biāo)準(zhǔn)每個節(jié)點都有機(jī)會競選為簇頭；最后，優(yōu)化負(fù)載均衡度。簇頭內(nèi)的普通節(jié)點數(shù)由于節(jié)點的隨機(jī)分布不均必不相同，從而導(dǎo)致簇頭負(fù)載出現(xiàn)不均衡。那么就可以將原來的網(wǎng)絡(luò)分割成幾個網(wǎng)絡(luò)，以便于在簇內(nèi)節(jié)點數(shù)大于平均數(shù)的網(wǎng)絡(luò)中重新選取幾個簇頭，以提高簇頭的負(fù)載均衡度[8]。其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.1 Network topological structure

假設(shè)：網(wǎng)絡(luò)節(jié)點的密度足夠大，目的是為了在無線網(wǎng)絡(luò)的連通區(qū)域內(nèi)相機(jī)節(jié)點的鄰居節(jié)點不為空。并且讓簇頭周圍的多個節(jié)點以共同協(xié)作分布式的方式完成圖像壓縮與傳輸任務(wù)[9]，從而減輕簇頭節(jié)點的能耗壓力。

則算法實施步驟設(shè)計如下：

將N個節(jié)點隨機(jī)地布置在r×r的方形區(qū)域內(nèi)，假設(shè)每個簇內(nèi)的最大節(jié)點個數(shù)為n，簇頭覆蓋半徑為R。那么就把所有節(jié)點以剩余能量的大小為標(biāo)準(zhǔn)，按照從大到小的順序進(jìn)行排列，得到一個{1，2，…，N}中的序號i。同時所有節(jié)點在同一時間以i個時間單位為期限開始倒計時來競選簇頭，并且為了明確其簇頭身份，在i個時間單位結(jié)束時，由簇頭向該區(qū)域內(nèi)周圍節(jié)點發(fā)送撤消命令。收到某簇頭命令的節(jié)點向簇頭發(fā)送加入該簇頭的命令。如果已經(jīng)加入到某簇頭的節(jié)點，即使再接收到其他簇頭的消息命令，也不會加入到其他簇頭；但是如果某個節(jié)點在倒計時還未結(jié)束就收到撤消命令，則停止倒計時，并且此節(jié)點將不不再參與簇頭的競爭。此時，除了有限的幾個孤立節(jié)點，其他節(jié)點基本都能加入與其臨近的簇頭。如果最后確實出現(xiàn)幾個孤立節(jié)點，而且其覆蓋半徑內(nèi)存在簇頭節(jié)點，那么將其加入到臨近的簇頭。由于開始的簇頭對網(wǎng)絡(luò)中的任何節(jié)點均是可達(dá)的，那么簇內(nèi)的剩余節(jié)點加入原始簇頭。不過對節(jié)點過多的簇還需要進(jìn)行網(wǎng)絡(luò)分割，在簇內(nèi)根據(jù)能量大小這個標(biāo)準(zhǔn)再競選出幾個簇頭，要盡量做到簇頭負(fù)載平均。其中，圖像采集以及塊數(shù)據(jù)的列時域預(yù)處理工作主要由簇頭節(jié)點負(fù)責(zé)，然后以每8行為一個獨立的數(shù)據(jù)單元，并將數(shù)據(jù)傳送給中繼節(jié)點；再由中繼節(jié)點對數(shù)據(jù)進(jìn)行包括列DCT變換、行時域預(yù)處理、行DCT變換以及8×8LBT系數(shù)塊的編碼在內(nèi)的數(shù)據(jù)壓縮處理，最后將壓縮處理好的數(shù)據(jù)匯聚到簇頭節(jié)點。

3 仿真實驗

假設(shè)在150 m×150 m的區(qū)域內(nèi)隨機(jī)分布有300個能量為1 J的節(jié)點，以網(wǎng)絡(luò)能采集到的512×512的灰度圖像進(jìn)行實驗。圖2為在基于LBT的分布式和DCT兩種方式下，網(wǎng)絡(luò)生命周期隨節(jié)點數(shù)目變化的曲線圖。不難看出，節(jié)點分布越密集越多，節(jié)點間距離就越小，基于LBT的分布式圖像壓縮算法的網(wǎng)絡(luò)生存周期就越長，從而優(yōu)勢就越明顯。

圖2 網(wǎng)絡(luò)生存周期對比圖Fig.2 Network life cycle contrast

4 結(jié) 論

在圖像壓縮LBT算法基礎(chǔ)上，文中提出了一種分布式無線多媒體傳感器網(wǎng)絡(luò)圖像壓縮算法。首先分析了無線多媒體傳感器網(wǎng)絡(luò)中現(xiàn)有的JPEG2000和DCT所存在的問題，由此提出采用LBT圖像壓縮算法來實現(xiàn)低復(fù)雜度、高質(zhì)量。并在此基礎(chǔ)上為了降低網(wǎng)絡(luò)中各節(jié)點的能耗壓力，提出一種分布式圖像壓縮算法，由傳感器節(jié)點把數(shù)據(jù)分配給區(qū)域中簇內(nèi)其他節(jié)點，多節(jié)點協(xié)同共同完成數(shù)據(jù)處理任務(wù)。實驗結(jié)果表明，在節(jié)點分布不均且節(jié)點部署密集的環(huán)境中，與DCT方式相比，采用該方案極大地緩解了各節(jié)點的能耗壓力，成倍地延長了網(wǎng)絡(luò)生存周期。

[1]Akyildiz I F，Melodia T.Chowdhury KRA Survey on wireless multimedia sensor networks[J].ScienceDirect，2007：921-960.

[2]Sharif A，Potdar V，Chang E.Wireless multimedia sensor network technology:A survey[C]//Proc of the 7th IEEE Int Conf on Industrial Informatics.Piscataway，NJ:IEEE Press，2009:606-613.

[3]Pradhan S，kusuma J.Ramchandran K，Disrcibuted Compression in a Dence Microsensor Network[J].IEEE Signal Process，Mag，2002（19）:51-6.

[4]Chiasserini C F，On the Concept of Distributed Digital Signal Processing in Wireless Sensor Networks[C]//Proc of IEEE Military Communications Conference （MILCOM’02），2009:260-264.

[5]Eder P，Engel D，Uhl A.JPEG2000-based Scalable Video Coding with MCTF[J].Department of Computer Sciences，2007.

[6]Tran T D.Liang J，TuCJ，Lapped Transform via time-domain pre and post-filtering[J].IEEE Trans，Signal Processing，2003（51）:1557-1571.

[7]Zeng Y H，Cheng L Z，Bi G A，Kot A C，Integer DCTs and fast algorithms[J].IEEE Trans，Signal Processing，2001（49）:2774-2782.

[8]杜向黨，李亦洋，石秀華.無線傳感器網(wǎng)絡(luò)基于類的簇頭選擇算法改進(jìn)[J].傳惑技術(shù)學(xué)報，2008，7（21）：1202-1206.DU Xiang-dang，LI Yi-yang，SHI Xiu-hua.Improved arithmetic in choice of head-note based on clustering of WSN，Chinese journal of sensors and actuators，2008，7（21）:1202-1206.

[9]魯琴，羅武勝，張勇.多媒體傳感器網(wǎng)絡(luò)中基于兩跳簇結(jié)構(gòu)的圖像傳輸方案[J].傳感技術(shù)學(xué)報，2007，11（20）：2476-2480.LU Qin，LUO Wu-sheng，ZHANG Yong.Two-hop clustered image transmission scheme in multimedia sensor networks[J].Chinese journal of sensors and actuators，2007，11 （20）:2476-2480.