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

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

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

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

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

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

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)

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 x t-w removed from the sliding window

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

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

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

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

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

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): QBinary Sequence Ctx. Num …… …

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