Binary Arithmetic Coding System with Adaptive Probability Estimation by “Virtual Sliding Window”

The Presentation inside:

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