Codage RLE
Le système de codage RLE (Run Length Encoding ou codage par longueur des plages), est certes ancien, mais a longtemps été utilisé dans les transmissions par fax.
L’image ci-contre est codée par les nombres figurant à sa droite.
Expliciter le codage employé
Quel est le taux de compression de cette image ?
S’agit-il d’un système de compression avec ou sans pertes ?
Algorithme
Soit l’image implémentée en Python à l’aide d’une liste de listes :
img = [[0,1,1,1,0], [0,0,0,0,1], [0,1,1,1,1], [1,0,0,0,1], [1,0,0,0,1], [0,1,1,1,1], ]
On se propose de coder cette image sous la forme d’une autre liste de listes, nommée rle et qui aura après exécution de l’algorithme la valeur suivante :
[[1, 3, 1], [4, 1], [1, 4], [0, 1, 3, 1], [0, 1, 3, 1], [1, 4]]
Implémenter cet algorithme de codage en Python.
Calculer l’ordre de complexité de cet algorithme.