Slide 0

Binary Arithmetic Coding System with Adaptive Probability Estimation by “Virtual Sliding Window”
Eugeniy Belyaev
Marat Gilmutdinov
Andrey Turlikov

Slide 1

Arithmetic Coding with Context Modeling
Encoder
Context Modeler
Arithmetic Encoder
Decoder
Context Modeler
Arithmetic Decoder
Bitstream
Probability
estimation
Probability
estimation
xt
xt
D

Slide 2

Sliding Window (Main Properties)
W last processed symbols are used for probability estimation
Buffer with W cells is used for keeping W last processed symbols. W is window length
Frequencies of symbols are calculated basing on buffer content

Slide 3

Work of Encoder with Sliding Window Adaptation (Binary Case)
W
xt
xt-1
xt-2
xt-3
xt-W+1
xt-W
Step 1: Probability estimation for xt encoding
Estimation by Krichevsky-Trofimov formula:
…

Slide 4

Work of Encoder with Sliding Window Adaptation (Binary Case)
Step 2: Current symbol xt encoding by arithmetic encoder
Step 3: Modification of sliding window content
xt
xt-W
Finite State Machine with 2W states
xt-2
xt-3
xt-W+2
xt-W+1
…

Slide 5

Main Disadvantage of Sliding Window Method
Using large size additional memory required for buffer of sliding window
Necessity to store individual buffers with W cells for each context model
Frequent context model changing is critical for memory cache
Critical for DSP application

Slide 6

Chronology of Sliding Window Analysis
1986 – F.T.Leighton, R.L.Rivest
Proposal of Probabilistic n-state finite-state estimation procedure
1996 – B.Y.Ryabko
Randomization procedure;
Imaginary Sliding Window (ISW)
Non-binary case
1996 – A.Zandi, G.G.Langdon
Randomization procedure;
Binary case
2004 – E.Meron, M.Feder
Avoiding randomization procedure in
Imaginary Sliding Window (ISW)

Slide 7

Imaginary Sliding Window (Main Properties)
Using Randomized Finite State Machine with (W+1) states
Method does not require to store buffer for previously processed data
Random variable is used to estimate value of symbol xt-w removed from the sliding window

Slide 8

ISW (Main Algorithm)
Step 1 and Step 2 are similar to classical sliding window algorithm (exception: ISW uses evaluation of St for probability estimation)
Step 3: Modification of St evaluation.
yt – random binary value
Randomized Finite State Machine with W+1 states

Slide 9

Features of ISW
Advantage
Avoiding buffer usage
Disadvantage
Using generator of random values, synchronized on the encoder and decoder sizes

Slide 10

Avoiding Random Variable Usage
– average number of ones in the single cell (removed from sliding window)
Disadvantage – float point operation with St
E.Meron, M.Feder (2004)

Slide 11

Integer Implementation of Virtual Sliding Window (VSW)
c – parameter of algorithm

Slide 12

Advantages of VSW
Virtual Sliding window method avoids
buffer storage in memory;
generation of random values;
float-point operations with St calculation

Slide 13

Using VSW in H.264 Standard
Binarization
Context Modeling
CABAC – Context-based Adaptive Binary Arithmetic Coding
Non-binary
data
Arithmetic Coding
bitstream
Binarization of value Q (simplified scheme):

Slide 14

Bitrate Savings for some Testing Video Sequences (in percent)
Regular Initialization of P-frames
Non-Regular Initialization of P-frames