Binary Arithmetic Coding System with Adaptive Probability Estimation by Virtual Sliding Window Eugeniy Belyaev Marat Gilmutdinov Andrey Turlikov. - презентация

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

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

3 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

4 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: …

5 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 …

6 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

7 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)

8 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

9 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

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

11 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)

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

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

14 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 …… …

15 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