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

董卓亞

（商丘師范學院 計算機與信息技術學院，河南 商丘 476000）

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

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

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

1 算法引入

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

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

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

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

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

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

圖1 網絡拓撲結構Fig.1 Network topological structure

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

則算法實施步驟設計如下：

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

3 仿真實驗

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

圖2 網絡生存周期對比圖Fig.2 Network life cycle contrast

4 結 論

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

[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]杜向黨，李亦洋，石秀華.無線傳感器網絡基于類的簇頭選擇算法改進[J].傳惑技術學報，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]魯琴，羅武勝，張勇.多媒體傳感器網絡中基于兩跳簇結構的圖像傳輸方案[J].傳感技術學報，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.