Библиотека

Binary Signal Compression using DCT Signs

Abstract

Binary Signal Compression using DCT (Discrete Cosine Transform) signs is presented. This is quite new technique for signal compression. Even a random binary signal utilized in a computer is included in our aim. The presented method enables us to make more compact signal from an usual compressed and coded binary signal for the computer. This method is a complete reversible compression (coding) one for the signal reconstruction. The simulation confirms that the compression rate becomes much better even in a random binary signal.
Keywords: Binary signal compression, DCT, Random sequence

1 Introduction

In recent computer society many random binary sequences are utilized in various fields. Usually such random sequences are compressed and coded meaning signals through like JBIG or JPEG coding method [1]-[8]. Most such binary random sequences are not actually completely uncorrelated but has some correlation. We would like to present that such random sequences are able to be compressed more compactly in this paper. Here an interesting property of DCT signs is used. The inverse transform of the DCT signs is called as a Sign-only synthesis (SOS) and has nature like Laplacian filter [9] [10]. Then the discontinuous point from 1 to 0 or from 0 to 1 of the binary signal can be detected clearly. Actually in this SOS case it is not needed to use all DCT signs for reconstruction of the binary sequence. About a half number of DCT signs are usually enough for it because of its strong high pass nature. Then the compression rate is about 1/2. This means the total compression rate of the original signal (not binary one) becomes much higher. The presented method is just quite new one for the signal compression. In section2 nature of DCT is introduced and the relation between DCT signs and binary random signal is also shown in this section. Section2.2.1 shows the main theme of this paper. The simulation examples are shown in Section3. Section4 includes the concluding remarks.

2 Nature of DCT signs

Discrete cosine transform called DCT is one for frequency analysis. This is well known orthogonal transform in image compression technique as JPEG and/or MPEG method. Unlike Fourier transform DCT is real number transform then the DCT coefficient has a plus or minus sign and the amplitude. DCT coefficient sign has important mean as shown in next section. DCT is defined as:

where x(n) is the object sequence with length N. Actually the pattern of the sign of X(k) is unique for the object sequence although it is not in strict sense. Inverse DCT is also defined as
Inverse DCT has a similar form of DCT and they are very fast transforms. ия.

2.1 Sign-only synthesis

DCT coefficient signs include important information about the image edges when the DCT is applied to an image. The inverse DCT of only these signs is called Sign-only Synthesis (SOS) and is defined as follows:

That is to say, SOS is equivalent to the equation that each amplitude of DCT coefficient is set to be 1 in Eq.2.

By using SOS the discontinuous points and/or indifferential points in the signal we can be detected. For example Fig.1 and Fig.2 show the original image and its SOS respectively. We can see from Fig.2 that the image edge lines are detected clearly. In this case all DCT signs are not generally needed. Usually about half numbers of all the signs are enough for such SOS. This is because SOS has an extremely high pass filtering nature. For the presented compression method we utilize this nature of the SOS. Discarded signs are set to be zero. These zeros are not needed to be sent to a receiver side because we can make up at the receiver side with almost no additional information.

2.2 One Dimensional Signal and it’s Compression

Almost all computer signals are binary signals like Fig.3-a. These signals has been usually compressed and coded, and hence these are somewhat like random sequences. Consequently it looks hard to compress anymore. Our presented method, however, makes it possible. Even in such random sequences when the succeeding finite samples are taken the finite sample sequences have usually some correlation in a time averaging sense. Then the possibility of far more compression come appears. As described above the sign-only synthesis has a strong nature for a discontinuous point detection. Then at the discontinuous point we get spikes as shown in Fig.3-b.

Figure3-c shows a processed pulse sequence shown as follows: Figure4 –a is assumed to be a discontinuous point of the original signal. The sign-only synthesis is shown in Fig.4 –b. At the discontinuous point both plus and minus impulse appears in the sign-only synthesis Fig.4 –b. Hence taking a multiplication of the succeeding two samples the sign-only synthesis we can get the big impulse with minus sign at the discontinuous point like Fig.4 – c. Here we call such a big impulse a giant pulse. Consequently we can find all discontinuous points of the original sequence. In this case we employ threshold value processing because of the noise cutting. Then the original signal is completely reconstructed with the signal initial (first) sign (+1 or -1) as an initial condition.

2.2.1 Compression

Generally sign-only synthesis is defined in Eq.3, but actually it is not needed to use all signs of DCT coefficients for getting impulses at the discontinuous points of a binary signal. It is enough to keep about half signs of all. Usually the signs where the DCT coefficient magnitude is big should be taken. But in fact we can take it from the DC component to the higher frequency:

where L is the upper limit of K. Usually L=N/2 which comes from many tests and trials. Then sending only these signs (about N/2 bits) we can reconstruct the original signal at the receiving side. In this case it is not needed to snd the additive zeros. On the contrary the original signal needs N bits for transmitting. The procedure is as follows:

(Procedure)

• DCT of the original binary signal.
• Sign-only synthesis with the half signs shown in Eq.6 and reconstructing the original signal as described above.
• After confirming that the reconstruct signal is just the same as the original one we can send the DCT signs. If the reconstruct signal is not the same one then the L in Fig.(6) should be bigger.
• At the receiving side the SOS is implemented and we can reconstruct the signal.

In this presented method the compression rate is about 1/2.

3 Simulations

Figure.5 shows simulation examples. Figure.5-a is an original signal with 128 sample points. And its correlation length is relatively long (13 samples). Then our proposed method is able to detect all the discontinuous points of the original signal. Consequently we can reconstruct the original signal completely at the receiver side. In this case 64 bits are required to send the needed DCT-signs. On the other hand if we employ a traditional run length coding method then 96 bits are needed. Hence our method is much preferable. But for the Fig.5-c whose correlation length is short (3 samples) it is hard to detect several discontinuous points as shown in Fig.5- d. From these figures it looks like that our presented method cannot compress a binary signal with short correlation. Actually it looks no use to utilize such a method because the original signal looks like a white random noise. But an appropriate transform from uncorrelated signal to correlated signal may enable us to compress more.

4 Conclusions

We have presented an interesting compression method for a binary signal. Here the DCT Sign-only synthesis is utilized to detect a discontinuous point of the original signal. Hence the presented method is quite different with traditional ones from the view point of a compression. Consequently it is found that even random binary sequence can be compressed into half bits of the original signal if the correlation length of signal has relatively long correlation. The compression rate is better than that of the traditional run length method. Even in the sequence which like a white random one there is such a case that we can get relatively long correlation sequences by dividing the original one into several short length sequences. Then our presented method can be applied in such a case. When the presented method is built in a mobile system the efficiency of the date communication will be much better.

5 References

[1] ISO/IEC 11544:1993, Information technology -- Coded representation of picture and audio information -- Progressive bi-level image compression
[2] Amer PD, Iren S, Sezen GE, Conrad PT, Taube M, Caro A: “Network-conscious GIF image transmission over the Internet”, COMPUTER NETWORKS - THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNIATIONS NETWORKING 31(7) : 693-708 APR 8 1999.
[3] Ohmachi, Ono,: “Survey of JPEG for color images”, Journal of IJEIA, vol.20, No.1, pp 50- 58 (1991).
[4] Ohmachi, Ono: “Survey of JPEG for color images”, Journal of IJEIA, vol.20, No.2, pp 113- 120 (1991).
[5] Yasuda,: “The view and the history of MPEG” , Journal of IJTV, vol.49, No.4, pp 409-415 (1995).
[6] ISO/IEC, “Digital Compression Coding of Continuous-tone Still Images Part I: Requirements and Guide-lines”, DIS 10918-1 (1992).
[7] CCITT SG VIII, “Draft Rec. T, 83:Digital Compression Coding of Continuous-tone Images Part :Compliance Testing” , COM VIII-172 (1992).
[8] W.H. Chen and H.Smith, “Adaptive coding of Monochrome and Color Images” , IEEE Trans. Communication, Vol.COM-25, No.11, (1977). [9] H.Kondo: “Application of DCT Sign Signal for Human face Recognition”, Proc.IEEE.M2VIPO1, Hong Kong, 2001.
[10] H.Kondo: “The Importance of the phase in Spectral Analysis of Images”, Journal of IIITE, vol.45, No.10, pp 1164-1171 (1991).