Redundancy and optimization of tANS entropy encoders
Blanes Garcia, Ian (Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
Hernández Cabronero, Miguel (Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
Serra Sagristà, Joan (Universitat Autònoma de Barcelona. Departament d'Enginyeria de la Informació i de les Comunicacions)
Marcellin, Michael W. (University of Arizona. Department of Electrical and Computer Engineering)

Date:	2021
Abstract:	Nowadays entropy encoders are part of almost all data compression methods, with the Asymmetrical Numeral Systems (ANS) family of entropy encoders having recently risen in popularity. Entropy encoders based on the tabled variant of ANS are known to provide varying performances depending on their internal design. In this paper, we present a method that calculates encoder redundancies in almost linear time, which translates in practice to thousand-fold speedups in redundancy calculations for small automatons, and allows redundancy calculations for automatons with tens of millions of states that would be otherwise prohibitive. We also address the problem of improving tabled ANS encoder designs, by employing the aforementioned redundancy calculation method in conjunction with a stochastic hill climbing strategy. The proposed approach consistently outperforms state-of-the-art methods in tabled ANS encoder design. For automatons of twice the alphabet size, experimental results show redundancy reductions around 10% over the default initialization method and over 30% for random initialization.
Grants:	Ministerio de Economía y Competitividad RTI2018-095287-B-I00 Agència de Gestió d'Ajuts Universitaris i de Recerca 2018/BP-00008 Agència de Gestió d'Ajuts Universitaris i de Recerca 2017/SGR-463
Rights:	Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets.
Language:	Anglès
Document:	Article ; recerca ; Versió acceptada per publicar
Subject:	Tabled asymmetrical numeral systems ; Entropy encoder redundancy ; Optimization
Published in:	IEEE transactions on multimedia, 2021 , ISSN 1520-9210

DOI: 10.1109/TMM.2020.3040547

Postprint 11 p, 788.5 KB

The record appears in these collections:
Research literature > UAB research groups literature > Research Centres and Groups (research output) > Engineering > Group on Interactive Coding of Images (GICI)
Articles > Research articles
Articles > Published articles