Data and Image Compression: InClassLabs
S. Xambó
In this page (WiP) each section corresponde to an
InClassLab for the Data and Image Compression class
of the Spring Semestrer 2014-2015 at the
FIB
of the UPC.
The L2 to L6 denote labs in the period February to June. In each case,
the next two digits denote the day of the month in which the lab is scheduled.
L217
Main programming environment:
pyzo.
The first step for this lab is to install this environment and understand how it works.
The second step is to study and understand the basic features of
the Python programming language and experiment with them:
L219
Let X stand for a set/list/tuple/range with
n = len(X) > 1. Let W
be a list of n positive numbers. Define a function
select(X,W) that returns an element of X
with probability proportional to the corresponding weight.
Solution:
L219.py
Mentions:
Boixaderas,
Llueca,
Mingorance,
Puente.
L224
Solve the first problem on page T0.2.
Solution: L224.py
L303
Consider the following binary encoding of the alphabet
A = {'a', 'b', 'c', 'd', 'e'}:
'a' → '0', 'b' → '11', 'c'→100, 'd' → '1010', 'e' → '1011'.
- Define a function E(X) that yields, given a message
X in the alphabet A,
the encoded message. For example, E("aac") should yield
'001011'.
-
Generate a random message X of length 50 (say) in the alphabet A
with expected frequences 50, 20, 15, 10 and 5 for the characters 'a', 'b', 'c', 'd', 'e'
and find C = E(X).
-
In an ASCII-like encoding the message X requires at least 3 bits per character.
Find how many bits per character are needed for the encoding C.
What is the compression ratio?
-
Define a function D(C) that yields, given an
encoded message C, the original message
X. Test it with the C
obtained in the previous point.
Kick off file: L303_x.
Supplement: L303_y
Solution:
L303
L305
Inclass work on entropy.
Solution: L305
L310
Study cdi15-graphics-305,
which generates the graphics on pages 3 and 10 of
T2. This is a prerequisite for A310.
Read pages T2.21 and T2.23. The daring might also like to read T2.24 and T2.25.
L312
Inclass lab: Study the functions in the section 'Prefix codes' of
cdi and relate them
to the corresponding results in
T3.
Include examples.
L317
An exercise about Kraft's inequality:
L317_x.
L319
Finding the average length of en encoding:
L319_x.
cdi_huffman.
L324
In class lab on the functions IE(M,P)
(arithmetic interval encoding) and dec2bin(x,nb=58)
(binary string of nb bits
representing the float x in the
inteval [0,1)).
These functions, together with those defined in L326, will be part
of the module cdi_ACD
(arithmetic coding and decoding).
L326
In class lab devoted to define funtions
BE(a,b,nb=58)
(bit encoding of the interval [a,b),
up to the machine precision) and
AE(M, P, nb=58)
(bit arithmetic encoding of a message M
emited by the source P) and
AD(C,P)
(arithmetic decoder of the encoded message
C = A(M,P),
so that AD(C,P) = M).
These, together with the functions defined in L324, will be part
of the module cdi_ACD
(arithmetic coding and decoding).
L407
In class lab devoted to define funtions
SAE(M,P) and
SAD(C,P)
that implement the scaled arithmetic encoder
and decoder, respectively, and to test them
in examples. These functions will also be included
in the module cdi_ACD.
Kickoff: L407_x.py.
cdi_ACD.
Mentions:
Bertran,
Christakopoulos,
Gines,
Llueca,
Mingorance,
Puente,
Sanchez,
Velisek.
L409
This and the next few labs are devoted to Haar wavelets algorithms. The results will be
integrated into the module cdi_wavelets.py.
Today's lab takes the first steps.
Solution: Ginés.
Mentions:
Lafita,
Mingorance,
Puente,
Rodríguez,
Sánchez,
Velisek.
L414
Haar wavelets algorithms: High level Haar transforms.
Mentions:
Domínguez,
Ginés,
Lafita,
Mateo,
Mingorance,
Puente,
Rodríguez,
Sanchez,
Velisek.
L416
Haar wavelets algorithms: High level trend and fluctuation functions.
Iterative form of the high level Haar transforms.
Kickoff: L416_x.py.
Sample solutions:
Martin,
Rodríguez.
L421
Haar wavelets algorithms: Computing the arrays of
scaling and wavelet vectors.
Kickoff: L421_x.py.
Mentions:
Domíguez,
Martin,
Mingorance.
L423
Haar wavelets algorithms: work on several
aspects of multiresolution.
Kickoff: L423_x.py.
L428
Check the identities satisfied by the Daub4 coefficients
(T7.2). Define functions D4trend(f) and
D4fluct(f) that compute the
Daubechies trend and fluctuation of f.
L505
Define functions D4trend(f,r=1),
D4fluct(f,r=1) and
D4(f,r=1) that compute the
Daub4 trend, fluctuation and transform off
for any level r.
Kickoff: L505_x.py.
Mentions:
Ginés,
Mingorance,
Puente,
Sanchez,
Velisek.
L507
Compute the scaling and wavelet arrays for the Daub4 wavelets.
Kickoff: L507_x.py.
L512
Define functions that implement the method of filters for computing
the Daub4 multiresolution of a signal.
Kickoff: L512_x.py.
L514
Work on Daub6 wavelets: checking the coefficient identities
explained in class; studying the cdi_daub6 by comparing it to
cdi_daub4 and cdi_haar; and showing graphics of D6 transforms
of different levels.
Selected solutions:
Mingorance,
Sánchez.
L519
In class lab to consolidate theory and practice of wavelet theory.
Work in pairs, as indicated by the teacher, and help each other
to make sure that you understand the main concepts of T6 and T7,
the main algorithms, and all the functions in the module
cdi_wavelets.
As a practical exercise, work out the tasks in
L519_x.
L521
With the same class pairing as in L519, the process of solving that lab
will be explained in detail. Teams will be asked to append some
conclusions at the end.
L526
- Quantitative appendix to A519.
-
Work on 1D DCT.
cdi_dct.
CDI15
| SXD