Distributed Compression For Still ImagesIntroductionProblem DescriptionInformation Theory BackgroundSlide 5Slide 6General Solution StrategyUnderlying ApproachSlide 9Slide 10A Possible Scheme?Slide 12Slide 13A Possible Scheme?Proposed SolutionSlide 16Slide 17Slide 18Slide 19ConclusionsDistributed Compression For Still Images1Distributed CompressionFor Still Images Kivanc OzonatDistributed Compression For Still Images2Introduction•Description of the Problem•Related Concepts from Information Theory•Application of Bit-Plane Encoding as a Possible Solution Strategy•Proposed Solution: Using Transform Coding - Basic Scheme - Relation to the Information Theory ConceptsDistributed Compression For Still Images3Problem Description•Given two still images, a noisy version, X, at the decoder and the original, Y, at the encoder, how to transmit Y with the best coding efficiency? •No communication of X and Y at the encoderEncoder DecoderYXDistributed Compression For Still Images4Information Theory Background•Slepian-Wolf : Given the following scheme,(X,Y)(X,Y)Encode XEncode YR1R2Distributed Compression For Still Images5Information Theory Background•Can transmit X and Y, if: - R1 > H(X|Y) , R2 > H(Y|X), and - R1+ R2 > H(X,Y). R1R2H(Y)H(Y|X)H(X|Y) H(X)Distributed Compression For Still Images6Information Theory Background•Our problem is a special case of this: R1R2H(Y)H(Y|X)H(X|Y) H(X)H(X)H(Y|X)Distributed Compression For Still Images7General Solution Strategy•Form cosets with 3 requirements: - Members of the same coset should be maximally separated. - Members of the same coset should have the same (or very close) probabilities of occurrence. - Coset construction should be practically implementable.Distributed Compression For Still Images8Underlying Approach•Use the Idea of Jointly Typical Sets: - Encode a long sequence (length n) of i.i.d. sources together, and form the typical set. - As n gets large, the typical set contains almost all of the probability of occurrence. - Further, the typical set has its members uniformly distributed.Distributed Compression For Still Images9Underlying Approach•The typical set contains most of the probability of occurrence, but it has only power (of 2) nH elements.Typical SetDistributed Compression For Still Images10Underlying Approach•Given i.i.d. X and i.i.d. Y, can form long sequences to get the typical X and typical Y sequences.•Then, there are power (of 2) H(X,Y) jointly typical sequences. Typical Y Typical XDistributed Compression For Still Images11A Possible Scheme?•Use bit-plane encoding (followed by gray coding) to divide the image at the encoder into bit-planes.•Exploit the correlation between the adjacent pixels through the upper bit planes.•The lower bit planes contain i.i.d. (or almost i.i.d) distribution of 0’s and 1’s.Distributed Compression For Still Images12A Possible Scheme?Example: A lower bit-plane, with i.i.d 0’s and 1’s:01010.70.70.30.3Distributed Compression For Still Images13A Possible Scheme?•Given X , the noisy version, the jointly typical set is (X,Y) such that X is as given, and Y is the set with a Hamming distance of (0.3)n from X. •As n increases, Pr(X, Y=(X-0.3n)) will approach 1, with each (X,Y) pair having the same distribution.•Hence, can perform an efficient coset constructionDistributed Compression For Still Images14A Possible Scheme? •Problems: -The lower bit-planes, which are of interest, have error probabilities of close to 0.5, even with moderate noise variances.- Cannot compete with transform domain methods in terms of bit rates.Distributed Compression For Still Images15Proposed Solution•Using transform coding is better because: - Energy compaction, resulting in lower bit rates for PSNR’s of around 38-40 dB. - The addition / averaging process involved in transform coding reduces the effect of noise through the central limit theorem. - The coded sequences of coefficients are de-correlated to a significant extent.Distributed Compression For Still Images16Proposed Solution•Schematically,YDCTZonalCoderQuantizerBit-PlaneEncoderCosetConstructerModifiedHuffmanCoderDistributed Compression For Still Images17Proposed Solution•The coefficients can be grouped in pairs with almost equal probabilities of occurrence. (because they are Laplacian)•One member from each pair is selected and Huffman-coded.•The other member of the pair is to have exactly the reverse (0’s and 1’s switched) code.• The coded coefficients are placed in bit-planes.Distributed Compression For Still Images18Proposed Solution• 1, 2, 3, 4, 5 •01, 10, 11, 000, 111 (w.p. 0.125, 0.125, 0.10 , 0.075, 0.075)• -1, -2, -3, -4, -5 •10, 01, 00, 111, 000 (w.p. 0.125, 0.125, 0.10 , 0.075, 0.075) Assume: need to code 1,-4,-2, 2, -3,-1,5,2,3•100100111•010000100•010101111•111000101Distributed Compression For Still Images19Proposed Solution•Advantages: - Equal likelihood of 0’s and 1’s. This makes the use of the error coding simple. - Essentially Huffman coding. Not a significant increase, if the upper bit-planes are run-length coded. - Maximal distribution of cosets possible, due to the uniformity and equality of probabilities.Distributed Compression For Still Images20Conclusions•Asymptotic Equipartition Property is essential in forming the typical sets.•Having equal probabilities of occurrences make the error-coding simpler.•Decorrelation is maintained through DCT.•The Laplacian Distribution of the DCT coefficients is important in getting equally probable