phdslides

View Github Repository Open presentation in a new window

zenathark

See all presentation from zenathark

phdslides

0 0

phdslides

On Github zenathark / phdslides

Universidad de las Américas Puebla

Models and algorithms for Image and Video Compression

Doctoral Thesis Defense

Juan C. Galan Hernández

Supervisor: Dr. Vicente Alarcón Aquino
December 9, 2014

Outline

Introduction Review of Compression Algorithms Proposed Model: Fovea Hierarchical Trees Proposed Approach Results Summary Proposed Models: SP-Codec/AFV-Codec Proposed Approach Results Summary Conclusions and Future Work This is the agenda for my speech. First i will

1. Introduction

Compression

  • Data Stream: Sequence of digitally encoded signals.
  • Compression: Create a smaller representation of a given data stream. This new smaller data stream referred as compressed data stream.
  • Decompression: Recover the original data stream using the compressed data stream.
Let me define first what is a data stream. A data stream is a sequence of digitally encoded signals. This meaans that a data stream is a set of discrete values. Such values are usually the magnitude of a signal on a given moment, but can be something else such a string of symbols.

Usage

  • Reduces storage space
  • Improves communications speed and network usage
  • Impacts on all kind of communication: Wired, wireless, satellite
The main uses for data compression are to, this allows to improve. The imapct os on all.

Challenges of compression

  • Find a pattern inside the data that allows to compress the data stream
  • Select data to be discarded without affecting the quality of the reconstructed data stream
What are the challenges for compression?. Finding an indeal patter allows to low compression ratios, however each data stream can has a different pattern. For lossy compression, select.. is extremly importan in order to reach good quality and small compressed data streams.

Contributions

  • Proposed image compression method: Fovea Hierarchical Trees
    • Increase the compression ratio over classic methods
    • Improves image quality over classic methods
    • Based on Wavelet compression and fovea compression
  • Proposed video compression methods: SP-Codec and AFV-Codec
    • Based on Wavelet compression and fovea compression
    • Both methods increase the compression ratio over classic methods
    • Improve frame quality over classic methods
    In this work, two models for compression are proposed . The first oone is FVHT aimed to image compression The second proposal is two video compression models, SPECK codec and Adaptive Fovea Codec

Publications

J.C. Galan-Hernandez, V. Alarcon-Aquino, O. Starostenko and J.M. Ramirez-Cortes, Wavelet-Based Foveated Compression Algorithm for Real-Time Video Processing, CERMA 2010, September, 2010. J.C. Galan-Hernandez, V. Alarcon-Aquino, O. Starostenko and J.M. Ramirez-Cortes, DWT Foveation-Based Multi Resolution Compression Algorithm, Resarch in Computing Science, October, 2010. J.C. Galan-Hernandez, V. Alarcon-Aquino, O. Starostenko and J.M. Ramirez-Cortes, SPIHT Based Foveated Multi resolution Compression, MCPR2011, June, 2011. J.C. Galan-Hernandez, V. Alarcon-Aquino, O. Starostenko and J.M. Ramirez-Cortes, Fovea Window for Wavelet-based Compression, Innovations and Advances in Computer, Information, System Sciences, and Engineering, 2013. J.C. Galan-Hernandez, V. Alarcon-Aquino, O. Starostenko and J.M. Ramirez-Cortes, Region-of-Interest Coding based on Fovea and Hierarchical Trees, Information Technology and Control, September, 2013. J.C. Galan-Hernandez, V. Alarcon-Aquino, O. Starostenko and J.M. Ramirez-Cortes, Foveated Wavelet Based Intra Frame and Inter frame Encoding, To be submitted. The proposed methods were reported on the followng papers

2. Review of Compression Algorithms

Types of compression

  • Lossless compression: The original data stream is fully recovered
  • Lossy compression: The original data stream cannot be recovered. However, a new data stream is created that closely resembles the original.

Lossless compression

  • Exploits patterns on the data stream
  • Each pattern found is expressed with a symbol (Dictionary) or a magnitude (Statistical, Arithmetic)
  • It has a lower limit, lossless compression cannot go beyond certain ratio.

Classic lossy compression algorithms

  • Sound: FLAC (Statistical)
  • Image: PNG (Dictionary)
  • Video: VP9

Lossy compression

  • Requires a mathematical transform that takes the data form the spatial domain to another one like frequency domain or wavelet domain.
  • The search for patterns are done on the transform domain.
  • Data is drop on the transform domain by truncating the coefficients (quantization).

Classic lossy compression algorithms

  • Sound: MP3 (DCT)
  • Image: JPEG (DCT)
  • Video: H.264 (iDCT)

Proposed Model: Fovea Hierarchical Trees

Lossy image compression

  • Most common transform is the Discrete Cosine Transform (DCT)
  • The image is split on squares of 8x8 pixels.
  • The transform is applied to each square and the coefficient matrix is multiplied by a quantization matrix.
  • The quantized coefficients are sorted and compressed using Huffman encoding.

Wavelet Transform

Compact Support Good reconstruction quality

Compression using wavelets

Fovea Compression

  • Exploits the structure of the human eye.
  • The human eye perceive less detail from areas further away from the fixation point
  • The sensibility to details decreases logarithmically

Fovea Hierarchical Trees

Fovea Window

  • Proposed fovea window
$$w^l(n_{x,y}) = \begin{cases} L, & \text{if } 0 \leq n < \alpha \\ d\left(\frac{n^l_{x,y}-\alpha^l}{1-\alpha^l}\right)(L-b)+b,& \text{if } \alpha \leq n \leq 1\\ b,& \text{otherwise.} \end{cases} $$

FVHT

  • Based on SPIHT
  • Wavelet/Fovea based method
  • SPIHT reaches optimal compression
Sorting Algorithm
  • Sorting from the highest level to the lowest
  • From the center of the fovea to the outside
  • From the most significant bit plane to the less significant bit plane
  • All zero trees are encoded as one zero

Results

SPIHT 1bpp

FVHT 0.06-1bpp

Results

SPIHT 1bpp

FVHT 0.06-1bpp

Summary

  • The algorithm shows good performance on image reconstruction
  • The results obtained showed an increasing on visual quality of up to 60 psnr
  • The algorithm is dependent of a good choice of the focal point
  • The computational complexity of the algorithm is O(n)
  • The memory usage complexity is also O(n)

4. Proposed method: SP-CODEC / AFV-CODEC

Video Compression

Video Compression

  • Spatial Transform
  • Variable Length Encoder
  • Decompression
  • Motion Estimation
  • Motion Compensation

Adaptive Binary Arithmetic Coding

  • Arithmetic coding using integers
  • Creates a model on the fly
  • Used on H.264 (CABAC)

SP-CODEC

SPECK

  • Wavelet Based Compression Method
  • Easier to implement, less resources needed
  • Results with lower quality than SPIHT

AFV-CODEC

AWFV-SPECK

  • Based on SP-CODEC
  • Proposed compression for spatial transform AWFV-SPECK
  • Sorts coefficients using fovea
  • Results with higher quality than SP-CODEC inside the fovea
Sorting Algorithm
  • Sorting on zig-zag order from highest level to lowest
  • From the center of the fovea to the outside
  • From the most significant bit plane to the less significant bit plane
  • All sets where its bits are 0 are encoded using only one 0

Results

Original Frame

H.264 Compression (1bpp)

Results

H.264 Compression

SP-Codec Compression (1bpp)

Results

SP-Codec Compression (1bpp)

AFV-Codec Compression (0.06 - 1 bpp)

Results

SP-Codec Compression (1bpp)

AFV-Codec Compression (0.06 - 1 bpp)

Summary

  • Both codecs implement a wavelet based spatial transform
  • The quality of the reconstruction of single frames increases the quality of the reconstructed video overall when such frames are key frames.
  • The use of fovea further increases the quality on selected areas of key frames
  • The use of fovea will yield on a perfect reconstruction when the fixation point and the fovea cover the area where the motion is located

5. Conclusions

  • Two wavelet based image compression models are proposed: FVHT and AWFV-SPECK
  • Both algorithms exploits the fovea aliasing for increasing image quality
  • The proposed algorithms show better reconstruction quality that classic methods
  • Two video compression models are proposed: SP-Coded and AFV-Codec
  • Both proposed models show better quality reconstruction than classic models (H.264)

Future Work

  • The proposed models will be optimized for speed and memory usage
  • It will be investigated methods for in-place quantization using wavelets
  • Other variable length encoders will be tested
  • New metrics will be investigated

Thank you

0