PROBLEM DESCRIPTION AND PRIOR WORK

The goal is to implement an efficient algorithm so that the two highly correlated sources that cannot communicate with each other in the encoding stage can be compressed such that the total entropy of the system is equivalent to that of joint encoding-decoding. If the system is designed such that one of the still images, called Y, is transmitted completely, then it is clear that only part of the X image information needs to be transmitted to achieve the desired entropy goal. Mathematically, this can be shown as:
H(X,Y)=H(Y)+H(A(X)),            (Equation-1)
where H(X,Y) is the joint entropy of the two still images, H(Y) is the individual entropy of Y (the still image that is completely transmitted), and H(A(X)) is the entropy of the partial information about X that is transmitted. (i.e. A(X) is what the designed distributed source coding system is supposed to transmit) It is obvious that H(X,Y) and H(Y) are constants, given the image pairs, X and Y. Hence, the only variable is A(X) and it is the goal of the proposed algorithm to achieve:
H(A(X))=H(X,Y)-H(Y).            (Equation-2)

As the two images, X and Y, are highly correlated, H(Y) in the equations above contain not only the complete information of Y, but also some partial information of X. Then, Equation-2 clearly suggests that, the key to achieve the desired entropy rate would be to set A(X) so that A(X) contains only that X information, which is completely non-overlapping with the X information already contained in Y. This can be achieved by an algoritm that is able to suppress most or all of of the A(X) that is already known or shared by Y.

    The key to design an algorithm as described in the previous paragraph, is to observe the following:

Given a maximum allowable distance range, D, that represents the absolute same-location pixel by pixel gray level difference between X and Y:

• Any pixel of X received at the decoder can be at most D/2 (in modulus sense) gray level values away from the same location pixel of Y. Hence, if D=64, any transmitted pixel value of X for a given location should be +/- 32 of the same-location pixel of Y in modulus sense

• The number of all different possible variations of A(X) can be represented by (8-log2(256/D)) bits per pixel.

• The (8-log2(256/D)) bit transmitted groups, which are to be called cosets, need to be constructed such that in each coset, every member should be as distant from the other members in the same coset, as possible. This is needed to have the decoder find the correct X value. It is the coset, not the actual pixel, value that needs to be transmitted.

• The redundancy issue, involving intra and inter pixel correlations, should be exploited in an efficient coding of these cosets.

  It should be noted that given the maximum allowable distance between the individual same-location pixels of two highly correlated images X and Y (and this could be extended to any kind of highly correlated data), the first three of the bulleted observations above can be readily observed, and an algorithm satisfying them can be produced. However, the fourth bulleted observation will lead to different implementations/algorithms for different data types, and thus, will influence the real performance of the algorithm.

  The prior work by Pradhan explores possible algorithms for two highly correlated data sources which have pre-determined maximum Hamming distances between them. Hence, following the first three observations above (except that there is now data chunks instead of pixels), the data chunks are placed into cosets with each member of the same coset as distant from the other members of the same coset as possible. [2], [3]

  As an example, given that the maximum Hamming distance betweeen two 3 bit data sets, call them D1 and D2, is 1, and that D1 is completely transmitted, and that D2 is to be partially transmitted, then, the 8 possible values of D2 are transmitted through placing them into 4 cosets: Each coset is formed by grouping the two values that have a Hamming distance of 3. Since D1 and D2 have a Hamming distance of at most 1, the decoder can easily select the correct D2 value, which is the one, that is closest -in Hamming distance- to the D1 value. [2]

  ABSTRACT
  INTRODUCTION
  PROBLEM DESCRIPTION and PRIOR WORK
  DATA SET
  ALGORITHM
  RESULTS
  CONCLUSIONS
  REFERENCES