Logo UAB
2020/2021

Data Compression Technologies

Code: 105073 ECTS Credits: 6
Degree Type Year Semester
2502441 Computer Engineering OT 4 1
The proposed teaching and assessment methodology that appear in the guide may be subject to changes as a result of the restrictions to face-to-face class attendance imposed by the health authorities.

Contact

Name:
Joan Bartrina Rapesta
Email:
Joan.Bartrina@uab.cat

Use of Languages

Principal working language:
english (eng)
Some groups entirely in English:
Yes
Some groups entirely in Catalan:
No
Some groups entirely in Spanish:
No

Teachers

Joan Serra Sagristà
Ian Blanes Garcia

Prerequisites

  • Basic concepts of Linux and bash.
  • Knowledge of basic written and oral English.

Objectives and Contextualisation

The objective of the subject of Data Compression Technologies is to acquire a specific knowledge on the compressed data systems. This allows students to have sufficient capacity to assess the features and characteristics of a compressed system for a specific scenario. This course allows us to build the underground of connections by developing the "treball final de grau" (TFG) related to this topic and / or continuing a postgraduate related studies. It is contemplates the possibility of assuming this subject and the TFG simultaneously.

Competences

  • Acquire personal work habits.
  • Acquire thinking habits.
  • Capacity to design, develop, evaluate and ensure the accessibility, ergonomics, usability and security of computer systems, services and applications, as well as of the information that they manage.
  • Capacity to design, develop, select and evaluate computer applications and systems, ensuring reliability, security and quality, in accordance with ethical principles, and applicable standards and legislation.
  • Have the capacity to conceive, draft, organise, plan, develop and sign projects in the field of computer engineering for the conception, development and exploitation of computer systems, services and applications.
  • Have the capacity to select, deploy, integrate and manage information systems that satisfy the needs of an organisation, identifying the cost and quality criteria.
  • Work in teams.

Learning Outcomes

  1. Analyse the main protocols and know about the international standards and standardisation bodies.
  2. Apply basic multimedia content processes for their transmission.
  3. Design and evaluate an integrated information system based on its cost and quality.
  4. Design, develop, select and evaluate applications, ensuring their reliability and security.
  5. Develop a capacity for analysis, synthesis and prospection.
  6. Identify performance anomalies and inefficiencies when running a uniprocessor computer program both in terms of computing and memory access, and propose modifications to the program to improve performance.
  7. Identify the criteria used to evaluate proposed solutions.
  8. Implement basic algorithms for geometrical transformation and modelling (2D and 3D).
  9. Know how to use different 1D and 2D data compression algorithms.
  10. Work cooperatively.
  11. Work independently.

Content

1. Introduction
1.1. Digital Images
1.2. Gray, Color, Multicomponent images, video, frame
1.3. Samples, pixels, resolution, bit-depth and Dynamic Range
1.4. Compute Size of Images (KBits, Kbytes, Megabytes, bits per sample
1.5. The Principle of Image Compression: Redundancy
1.6. Entropy
1.7. Lossless, Lossy and Near-lossless compression

2. Distortion Measures
2.1. Motivation and Objective
2.2. Perceptual
2.2.1. SSIM
2.3. Analytical
2.3.1. PAE
2.3.2. MSE
2.3.3. PSNR

3. Decorrelation
3.1. Motivation and Objective
3.2. Spatial and Spectral
3.3. Transform based
3.4. Prediction based
3.5. Color Transform

4. Quantization
4.1. Motivation and Objective
4.2. Quantization // Dequantization process
4.3. Transform based
4.4. Prediction based

5. Coding
5.1. Shannon-Fano Coding
5.2. Huffman Coding
5.3. Elias Coding
5.4. Arithmetic Coding
5.5. Golomb Coding
5.6. LZ77
5.7. Asymmetric Numeral Systems

6. Current Image Compression
6.1. JPEG
6.2. JPEG-LS
6.3. JPEG2000
6.4. CCSDS-122
6.5. CCSDS-123
6.6. HEIC

7. Current Video Compression and Streaming
7.1. AVC and HEVC
7.2. VP9 and AV1
7.3. Dynamic Adaptive Streaming

8. Data Compression State-of-the-Art
8.1. Compressed Data Structures
8.2. Graph wavelet Transforms
8.3. Point Cloud Compression
8.4. Variable-to-fixed codes
8.5. Social network data compression
8.6. Rate control for prediction-based compression
8.7. High Performance Computing on Image and Video Data Compression

Methodology

The content of this subject will be taught to students through a combination of lectures and practicum. During the sessions, different concepts of digital data compression will be introduced. For each concept, students will be encouraged to actively participate in the resolution of examples. In addition, for a small set of concepts, a guided practicum will be provided, for which students will have to answer some questions. Campus Virtual will be used for communication between lecturers and students (material, updates, announcements, etc.)

Different activities will be conducted during the course:

Training activities
• Type: Teacher-directed activities
  o Theoretical classes / lectures
  o Practicum classes / lectures
• Type: Supervised activities
  o Practicum supervising activities
  o Oral presentation supervising
  o Tutoring and consultations
• Type: Autonomous
  o Preparing practicum activity
  o Preparing oral presentation activity

During the theoretical and practical classes / lectures the contents of the subject will be presented and discussed. The student will be provided with digital materials, impressions, and bibliographical references. They will be active discussion in which progress will be made in a constructive manner through the identification of the main objectives. Exercises complementing the theoretical explanation will be proposed and solved by the students.

During the practicum classes / lectures exercises to be solved with computer will be proposed. To validate the acquired knowledge some questions will need to be answered (oral or written) during these sessions.

Activities

Title Hours ECTS Learning Outcomes
Type: Directed      
Practicum 12 0.48 1, 2, 9, 5, 3, 4, 6, 7, 8, 10, 11
Theoretical and practical classes / lectures 38 1.52 1, 2, 9, 3, 4, 6, 7, 8
Type: Supervised      
Oral presentation supervising 6 0.24 1, 9, 4, 6, 8, 11
Practicum supervising 6 0.24 1, 2, 9, 4, 6, 7, 8, 10
Tutoring and consultation 6 0.24 1, 9, 4, 6, 8, 11
Type: Autonomous      
Preparing exercices and practicum 40 1.6 1, 2, 9, 4, 7, 8, 10, 11
Preparing oral presentation 36 1.44 1, 2, 9, 7, 10

Assessment

Continuous-assessment dates will be published on Campus Virtual. Specific deadlines might change, only when necessary. Any such modification will always be communicated to students through Campus Virtual.

Subject assessment (out of 10 points) will be carried out as follows:

• Practical activities, 3 points. Developed in group of 2. As part of continuous assessment, these activities consist in a set on small practicums, with the purpose to apply the theoretical compression concepts presented by the faculty during the lectures. These exercises will take place during the sessions. All practical activities will have the same weight. Minimum mark to pass subject 1.5 points.

• Exercise resolutions, 3 points. This is and individual task. As part of continuous assessment, short exercises must be solved. All exercises will have the ssame weight. Minimum mark to pass subject 1.5 points.

• Oral presentation, 4 points. This is an individual task. It consists of delivering an oral presentation about a specific topic. The choice of the topic will be discussed and agreed upon in the class, selecting topics from a list provided by the faculty staff or by the students themselves. In addition, the presenter will have propose an exercise that the other students will have to answer. The presenter will also have to correct and grade the answers. On the other hand, the audience must ask 3 questions (at least) during the presentations. A preliminary list of tentative topics includes:

  o Shannon Fano Coding
  o Huffman Coding
  o Elias Coding
  o Arithmetic Coding
  o Golomb Coding
  o Asymmetric Numeral System Coding
  o JPEG
  o Wavelet Transform. Haar Wavelet Transform
  o Index Coding
  o Embedded encoding of zero-tree wavelet coefficients (EZW)
  o Set partitioning in hierarchical trees (SPIHT)
  o Set partitioning embedded block coder (SPECK)
  o Lower-Tree Wavelet (LTW)
  o JPEG-2000
  o CCSDS-122.0
  o Context-Adaptive Lossless Image Coder (CALIC)
  o Low Complexity Lossless Compression for Images (LOCO-I)
  o Multi-component CALIC (M-CALIC)
  o CCSDS-123.0
  o CCSDS-123.1
  o Dynamic Adaptive Streaming over HTTP
  o Audio Compression FLAC

Minimum mark to pass subject 2 points and minimum assistance of 80% in this activity.

• Recovery test, 6 points. Those students that will not have a final mark (Practical activities + Exercise Resolutions + Oral Presentation) equal or greater than 5 they will have the opportunity to recover (get a 5 or higher) through a recovery test. Recovery test covers material from the practical activities and exercise resolutions. It will consist mainly of exercises in the style of those worked on during the course; a smaller part will consist of more theoretical questions. If the recovery test + oral presentation mark is not equal or superior than 5 will not pass the subject.

An overall grade of 5 or higher is required to pass the subject. A "non-assessable" grade cannot be assigned to students who have participated in any of the individual partial tests or the final exam. In order to pass the course with honors, the final grade must be a 9.0 or higher. Because the number of students with this distinction cannot exceed 5% of the number of students enrolled in the course, this distinction will be awarded to whoever has the highest final grade. In case of a tie, partial-test results will be taken into consideration. No special treatment will be given to students who have completed the course in the previous academic year.

During the sessions, the solved exercises will be reviewed, which will allow the students to review the grades.

It is important to bear in mind that no assessment activities will be permitted for any student ata different date or time to that established, unless for justified causes duly advised before the activity and with the lecturer’s previous consent. In all other cases, if an activity has not been carried out, this cannot be re-assessed.

Students who do not pass the grade for not achieving at least one of the minimum grades will be graded with a 4.

Without prejudice to other disciplinary measures deemed appropriate, and in accordance with current academic regulations, irregularities committed by a student that may lead to a variation of the grade will be scored with a zero (0). For example, plagiarizing, copying, letting copy, etc., an evaluation activity, will imply suspending this evaluation activity with a zero (0). The evaluation activities qualified in this way and by this procedure will not be recoverable. If it is necessary to pass any of these evaluation activities to pass the subject, this subject will be suspended directly, without the opportunity to recover it in the same course.

 

Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Exercise resolution 30% 2 0.08 2, 9, 6, 7, 11
Oral presentation 40% 2 0.08 1, 9, 5, 3, 4, 7, 11
Practical Activities 30% 2 0.08 2, 9, 5, 3, 4, 6, 7, 8, 10

Bibliography

  • Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory, John Wiley & Sons, Inc
  • Mark Nelson (1991). The Data Compression Book, Prentice Hall.
  • D.S.Taubman and M.W.Marcellin (2002). JPEG 2000. Kluwer Academic Publishers.
  • David Salomon (2006, 4th Edition). Data Compression: The Complete Reference(Hardcover), Springer. ISBN 1-84628-602-5.
  • Several documentation will be provided to the students according their election of the oral presentation topic