A novel lossless image compression scheme based on binary neural networks with sparse coding

1 Introduction

Image compression is designed to reduce the size of the data so that it requires less disk space for storage and less bandwidth to be transmitted on a data communication channel. Image compression techniques are often classified into two categories: lossless and lossy schemes[1]. Distinction between lossless and lossy methods is important because lossy techniques have higher compression than lossless methods. Lossless compression techniques can usually achieve a 2∶1 to 8∶1 compression ratio. Lossy compression can provide compression ratio of 100∶1 to 200∶1, depending on the type of information being compressed. In addition, higher compression ratio can be achieved if more errors are allowed to be introduced into the original data[2].

The compression algorithms recommended here are JPEG, JPEG2000 and JPEG-LS. In JPEG, both lossy and lossless modes are outlined by the notable difference between them, which is the application of discrete cosine transform(DCT) together with the corresponding quantization matrix. Both lossy and lossless forms are supported by JPEG2000 depending on the type of DWT and multi-component transforms being used. However, the computing method of JPEG2000 coding is more complex, and the computing cost is higher.In particular, for lossless image compression, the advantage of JPEG2000 is not prominent[3].

Lossless compression of images is required in many practical applications, where no information loss is allowed during compression, such as compression of satellite images[4], spectral images[5]and diagnostic images form medical sector[6-7]etc. So lossless compression of image attracts researchers’ attention[8].

The most popular methods of lossless compression are the dictionary-based schemes[9]. Dictionary compressors encode a string of data by partitioning the sting into many sub-strings and then replace each sub-string by a codeword. Communication between the compressor and decompressor is done by using messages. Each message consists of a codeword and possibly other information. The dictionary in these schemes is the set of every possible codeword.

In this paper, we propose a novel lossless image compression algorithm. The compression ratio depends on the number of the neurons and the codeword of each linearly separable structure.

2 Redundant dictionary based on linearly separable structures

For every binary neuron is equivalent to a linearly separable function and some linearly separable functions have similar logical structure and knowledge content, linearly separable structures are composed of these linearly separable functions[10]. In this section, we will establish the redundant dictionary, which is inspired by the recent progress of coding with dictionary learning[11], based on linearly separable structures. So firstly, let us introduce the known linearly separable structures in binary neural networks.

Definition 1 In binary neural networks, letwibe the weight value ofxi, denote

Definition 2[12]In the Bn2space，F(xiàn)( X) = x*s1∧ x*s2∧…∧x*sm，and m≤n，then we call spatial structure composed of F-1( 1) as norm hypercube structure， the whole norm hypercube structures as norm hypercube structure system．

Definition 3[12]In the Bn2space，F(xiàn)( X) = x*s1∧ x*s2∧…∧x*s1∧( x*t1∨*t2∨…∨*th) ，l + h≤n，and h≠0，then we call spatial structure composed of F-1( 1) as concave hypercube structure，the whole concave hypercube structures as concave hypercube structure system．

Definition 4[12]In the Bn2space，F(xiàn)( X) = x*s1∨*s2∨…∨x*s1∨( x*t1∧x*t2∧…∧x*th) ，l + h≤n，and h≠0，then we call spatial structure composed of F-1( 1) as convex hypercube structure，the whole convex hypercube structures as convex hypercube structure system．

Definition 5[13]In the Bn2space，for a sample Xc= ( xc1，xc2，…，xcn) ，if there is a set which is U( d) = { X = ( x1，x2，…，xn) ∈F-1( 1) | dH ( Xc，X) ≤d} ， subject to U( d) = F-1( 1) ，U( d) = F-1( 0) ，where ·372· 重慶郵電大學(xué)學(xué)報(bào)( 自然科學(xué)版) 第29 卷 d is the integer located in an interval [0，n]，and dH( Xc，X) is the Hamming distance between Xcand X，then we call U( d) as Hamming Sphere with the center of Xc and the radius of d．

Definition 6[14]In the Bn2space，for a sample Xc = ( xc1，xc2，…，xcn) ，if there is two sets which are U( d) = { X = ( x1，x2，…，xn ) ∈F-1( 1) | dH ( Xc，X) ≤d} and K( d + 1) = { X = ( x1，x2，…，xn) ∈F-1( 1) | dH( Xc，X) = d + 1} ，which are subject to U( d) ∪K( d + 1) = F-1( 1) ，U( d) ∪K( d + 1) = F-1( 0) ，where d is the integer located in an interval [0，n]，and card( K( d + 1) ) = m，where card ( K ( d + 1 ) ) = m means that the set K ( d + 1) is composed of m elements， then we call M( d，k) = U( d) ∪K( d + 1) as Hamming Sphere Dimple with the center of Xcand the radius of d，and call K( d + 1) as dimple set．

Definition 7 For a Boolean functionF(x1,x2,…,xn), ifF(x1,x2,…,xn) can be expressed aswhere operatorOis logic operation “AND” or logic operation “OR”, then we call the Boolean functionF(x1,x2,…,xn) as SP function.

There are the necessary and sufficient conditions for the equivalence between these six linearly separable structures and the binary neurons. However, unfortunately, the known linearly separable structures cannot cover the whole binary neuron, that is to say we need to define other linearly separable structure in order to cover the whole binary neuron.

Alln-bit Boolean functions can be classified into two classes: linearly separable Boolean functions(LSBF) and non-linearly separable Boolean functions(non-LSBF). The non-LSBF can be decomposed into several LSBFs with logic operators as Theorem 1.

Theorem 1[15]Anyn-bit non-LSBFφcan be expressed as logic Θ(k)operations of a sequence of LSBF:φ=φ1Θ(1)φ2Θ(2)…Θ(m-1)φm, whereφi(i=1,2,…,m) are LSBF, Θ(k)(k=1,2,…,m-1) are 2-input and 1-ouput logic operations such as “AND”, “OR”, “NOT”, andmis the minimal number of LSBF required.

Although the known linearly separable structures cannot cover the whole binary neuron, we can decompose the whole Boolean function into several concave hypercube structures and convex hypercube structures with logic operators as Theorem 2.

Theorem 2 Anyn-bit non-LSBFφcan be expressed as logic Θ(k)operations of a sequence of LSBF:φ=φ1Θ(1)φ2Θ(2)…Θ(m-1)φm, whereφi(i=1,2,…,m) are concave hypercube structure or convex hypercube structure, Θ(k)(k=1,2,…,m-1) are 2-input and 1-ouput logic operations such as “AND”, “OR”, “NOT”, andmis the minimal number of hypercube structure required.

wheret1,t2,…,tpi,tpi+1,…,tnis arrangement of 1,2,…,n.

F(x1,x2,…,xn)=φ1∨φ2∨…∨φs,

Intheabovesituationweonlyimplyeverytruesampleasahypercubestructure,sotheminimalnumberofLSBFrequiredisequaltothenumberoftruesamples,andthedecompositionefficiencyisratherlow.However,ifthehypercubestructurewhichweimplycanexpressatleasttwotruesamples,theminimalnumberofLSBFrequiredissmallerthanthenumberoftruesamples.Thatistosay,indecompositionprocess,wetryourbesttoimplythehypercubestructureexpressesatmosttruesamples,sotheminimalnumberofLSBFrequiredissmall.

AccordingtotheTheorem2,weonlyimplythehypercubestructurecanexpressarbitraryBooleanfunction.Soifweimplymorekindsoflinearlyseparablestructure,thedecompositionefficiencycanbeimproved.Inthefollowing,weimplythewholeknownlinearlyseparablestructuretoestablisharedundantdictionaryasFig.1.

Werankthewholeknownlinearlyseparablestructuresusingthelexicographicorder.

Fig.1 Redundant dictionary based on the known linearly separable structure

3 Lossless compression algorithm based on the learning algorithm of binary neural networks

Foreachimagestoredinthecomputerwithonlycode“0”and“1”,wecantreatthestorageformatasaBooleanfunctionwhichcanbetrainedintoabinaryneuralnetworks.Forann-bit Boolean function, the number of the whole function value is 2n. So firstly we need to divide the storage format of a given image into several Boolean functions. For every gray image, the each pixel occupies 8-bit binary code, so we choose 8-bit Boolean function as the smallest unit of the decomposed for the sake of simplicity. In this case, we can deal with 32 pixels by use of only an 8-bit Boolean function. If we choose the higher dimension Boolean function, we can deal with more pixels by use of only a Boolean function.

Secondly, we need to train the 8-bit Boolean function into a binary neural network with the least hidden neurons. In this step, we employ the geometry learning method based on heuristic algorithm. After obtaining the structure of the binary neural network, we match each hidden neuron to the specific linearly separable structure. At last, we establish the coding rule according to the redundant dictionary based on the known linearly separable structure, which is the compression scheme of a given image.

We describe the steps of the whole compression process as follows:

Step 0 We need to establish the redundant dictionary based on the known linearly separable structure, and obtain index coding scheme. We need to perform this initial step only once.

Step 1 For the given image, we divide the storage format of the image into several 8-bit Boolean functions, such aslBoolean functions.

Step 2 For thelBoolean functions, we train every Boolean function into the binary neural networks by using the algorithm proposed in literature [16].

Step 3 For the getting binary neural networks, we match the hidden neuron to the linearly separable structure with the aid of pattern matching method proposed in literature [17].

Step 4 According to the hidden neurons matching the linearly separable structure to the wholelbinary neural networks, we obtain the compression coding by the Step 0.

4 Experiments and results

To test the efficiency of the proposed algorithm for lossless image compression in this paper, we apply the compression ratio as evaluation criterion. The images being tested are 6 images from classic test images shown in Fig.2. Each image(8 bit/pixel, dimensions 256×256 pixels) is stored in the jpg format.

Fig.2 Test images

In Tab.1, we obtain the comparison of experimental results.

Tab.1 Comparison of experimental results(bpp)

5 Conclusions and future works

In this paper, a novel lossless image compression method is proposed. By using our redundant dictionary based on linearly separable structure and learning algorithm of binary neural networks, the compression ratio can be effectively increased, at the same time the size of the additional indexing data keeps small. It has demonstrated that our method outperforms traditional compression tools.

In this work, we focus on developing a method for lossless image compression. As to the characteristics of the gray image, every pixel occupies 8 bit, we employ 8-dimension binary neural networks and their linearly separable structures to establish redundant dictionary and learning algorithm for lossless compression. However, if we deal with lossless data compression, which is used in compressing text files, executable codes, word processing files, database files, tabulation files, and whenever the original and the decompressed files must be identical, we can employ arbitrary dimension binary neural networks and corresponding linearly separable structures to obtain better compression ratio. As for the higher dimension of binary neural networks, the higher computing cost, the higher dimension of binary neural networks and the higher compression ratio, we should balance the computing cost and the compression ratio. As a future work, we would like to explore lossless data compression.

[1] SEPEHRBAND F, MORTAZAVI M, GHORSHI S, et al. Simple lossless and near-lossless medical image compression based on enhanced DPCM transformation[C]//2011 IEEE Pacific Rim Conference on Communication Computers and Signal Processing. New York: IEEE,2011: 66-72.

[2] CHENG Kaijen, DILL Jeffery. Lossless to lossy dual-tree BEZW compression for hyper spectral images[J]. IEEE Transactions on Geoscience and Remote Sensing, 2014, 52(9): 5765-5770.

[3] JI Xiaoyong, BAI Sen, GUO Yu. A new security solution to JPEG using hyper-chaotic system and modified zigzag scan coding[J]. Communications in Nonlinear Science and Numerical Simulation, 2015, 22(5): 1-3.

[4] WU Jiaji, LIANG Chong, HAN Jianxiang, et al. A two-stage lossless compression algorithm for aurora image using weighted motion compensation and context-based model[J].Optics Communications,2013,290(1):19-27.

[5] WEN Jia, MA Caiwen, SHUI Penglang. An adaptive VQ method used on interferential multi-spectral image lossless compression[J]. Optics Communications, 2011, 284(1): 64-73.

[6] KARIMI N, SAMAVI S, SHIRANI S, et al. Real-time lossless compression of microarray image by separate compaction of foreground and background[J]. Computer Standards and Interfaces, 2015, 39(3): 34-43.

[7] STARONOLSKI R. Simple fast and adaptive lossless image compression algorithm[J]. Software Practice and Experience, 2007, 37(1) :65-91.

[8] ROMAN S. New simple and efficient color space transformations for lossless image compression[J]. Journal of Visual Communication and Image Representation, 2014, 25(5): 1056-1063.

[9] HUSSEIN A B. A novel lossless data compression scheme based on the error correcting Hamming codes[J]. Computers and Mathematics with Applications, 2008(56): 143-150.

[10] LU Yang, YANG Juan, WANG Qiang, et al. The upper bound of the minimal number of hidden neurons for the parity problem in binary neural networks[J]. Science China Information Sciences, 2012, 55(7): 1-9.

[11] SONG Xiangfa, JIAO L C, YANG Shuyuan, et al. Sparse coding and classifier ensemble based multi-instance learning for image categorization[J]. Signal Processing, 2013, 93(1): 1-11.

[12] 陸陽,韓江洪,張維勇.二進(jìn)神經(jīng)網(wǎng)絡(luò)邏輯關(guān)系判據(jù)及等價(jià)性規(guī)則提取[J].模式識(shí)別與人工智能,2001, 14(2): 171-176. LU Yang, HAN Jianghong, ZHANG Weiyong. Logical relation determination criteria and equivalence rule extraction on Binary Neural Networks[J]. Patten Recognition and Artificial Intelligence, 2001, 14(2): 171-176.

[13] 陸陽,魏臻,高雋,等.二進(jìn)神經(jīng)網(wǎng)絡(luò)中漢明球的邏輯意義及一般判別方法[J].計(jì)算機(jī)研究與發(fā)展, 2002, 39(1): 79-86. LU Yang, WEI Zhen, GAO Jun, et al. Logical meaning of Hamming Sphere and its general judgement method in Binary Neural Networks[J]. Journal of Computer Research and Development, 2002, 39(1): 79-86.

[14] 楊娟,陸陽,黃振謹(jǐn),等.二進(jìn)神經(jīng)網(wǎng)絡(luò)中的漢明球突及其線性可分性[J].自動(dòng)化學(xué)報(bào),2011,37(6):737-745. YANG Juan, LU Yang, HUANG Zhenjin, et al. Hamming Sphere Dimple in Binary Neural Networks and its linear separability[J]. Acta Automatica Sinica, 2011, 37(6): 737-745.

[15] CHEN Fangyue, CHEN Guanrong, HE Qinbing, et al. Universal perceptron and DNA-Like learning algorithm for binary neural networks: LSBF and PBF implementations[J]. IEEE Transactions on Neural Networks, 2009, 20(8) :1293-1301.

[16] 楊娟,陸陽,方歡,等.基于蟻群算法的二進(jìn)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法[J].電路與系統(tǒng)學(xué)報(bào), 17(6): 49-55. YANG Juan, LU Yang, FANG Huan, et al. An ant colony-based learning algorithm for binary neural networks[J]. Journal of Circuits and Systems, 17(6): 49-55.

[17] 陸陽,魏臻,韓江洪,等.二進(jìn)神經(jīng)網(wǎng)絡(luò)的模式匹配學(xué)習(xí).電子與信息學(xué)報(bào), 2003, 25(1): 74-79. LU Yang, WEI Zhen, HAN Jianghong, et al. The pattern match learning of binary neural networks[J]. Journal of electronics and information technology, 2003, 25(1): 74-79.

Biographies:

WANG Zuocheng(1973-),male, Sichuan Bazhong, Doctor, Senior engineer, His research interests include smart city and digital image processing and pattern recognition. E-mail: cswangzc@163.com.

YANG Juan(1983-),female, Liaoning, Shenyang, Postdoctor. His research interests include image processing and intelligent visual surveillance.

XUE Lixia(1976-),female,Sichuan Xichang, Doctor, Associate professor. Her research interests include digital image processing and pattern recognition.

(編輯：魏琴芳)

王佐成1,2,楊 娟3，薛麗霞3

(1.中國電子科技集團(tuán)公司 第三十八研究所,合肥 230088；2.安徽四創(chuàng)電子股份有限公司,合肥 230088；3.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院,合肥 230009)

視頻圖像的高效無損壓縮在海量的航空和遙感圖像傳輸、珍貴的文物信息的保存等方面具有重要的應(yīng)用價(jià)值，而目前的研究熱點(diǎn)主要針對(duì)有損壓縮，為此通過對(duì)現(xiàn)有的無損壓縮方法的分析和研究，提出一種在稀疏編碼與二進(jìn)神經(jīng)網(wǎng)絡(luò)相結(jié)合的框架下建立新的圖像無損壓縮方法。首先借助二進(jìn)神經(jīng)網(wǎng)絡(luò)中的線性可分結(jié)構(gòu)系建立冗余字典，獲得有效的稀疏分解基；再借助二進(jìn)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法將圖像映射為以線性可分結(jié)構(gòu)系為神經(jīng)元的二進(jìn)制神經(jīng)網(wǎng)絡(luò)，在此基礎(chǔ)上建立相應(yīng)的模式匹配算法將每個(gè)神經(jīng)元與冗余字典簡歷映射關(guān)系，通過稀疏系數(shù)建立原始圖像的編碼形式，進(jìn)而實(shí)現(xiàn)了圖像的無損壓縮，并從理論上分析了該方法可以有效地提高壓縮比，最后通過實(shí)驗(yàn)驗(yàn)證了該算法的有效性和通用性。

無損壓縮; 二進(jìn)神經(jīng)網(wǎng)絡(luò); 線性可分結(jié)構(gòu)系; 冗余字典; 壓縮比

2017-04-31 通訊作者：王佐成 cswangzc@163.com

The Fundamental Research Funds for the Central Universities of China(JZ2014HGBZ0059)

date：2017-04-30