Codage par troncature de blocs

Le codage par troncature de blocs ( BTC ) est un type de technique de compression d'image avec perte pour les images en niveaux de gris . Il divise les images originales en blocs, puis utilise un quantificateur pour réduire le nombre de niveaux de gris dans chaque bloc tout en conservant la même moyenne et le même écart type . Il s'agit d'un précurseur de la technique matérielle DXTC populaire , bien que la méthode de compression BTC ait d'abord été adaptée à la couleur bien avant DXTC en utilisant une approche très similaire appelée Color Cell Compression . Le BTC a également été adapté à la compression vidéo.

Le BTC a été proposé pour la première fois par les professeurs Mitchell et Delp de l'université Purdue. Une autre variante du BTC est le codage absolu de troncature de blocs de moments ou AMBTC , dans lequel au lieu d'utiliser l'écart type, le premier moment absolu est conservé avec la moyenne. L'AMBTC est plus simple à calculer que le BTC et produit généralement une erreur quadratique moyenne (MSE) plus faible. L'AMBTC a été proposé par Maximo Lema et Robert Mitchell.

L'utilisation de sous-blocs de 4×4 pixels donne un taux de compression de 4:1 en supposant que des valeurs entières de 8 bits sont utilisées pendant la transmission ou le stockage. Des blocs plus grands permettent une compression plus importante (valeurs « a » et « b » réparties sur plus de pixels), mais la qualité diminue également avec l'augmentation de la taille du bloc en raison de la nature de l'algorithme.

L'algorithme BTC a été utilisé pour compresser les images du rover Mars Pathfinder .

Une image en pixels est divisée en blocs de 4×4 pixels en général. Pour chaque bloc, la moyenne et l'écart type des valeurs de pixels sont calculés ; ces statistiques changent généralement d'un bloc à l'autre. Les valeurs de pixels sélectionnées pour chaque bloc reconstruit ou nouveau sont choisies de manière à ce que chaque bloc de l'image compressée BTC ait (approximativement) la même moyenne et le même écart type que le bloc correspondant de l'image d'origine. Une quantification à deux niveaux sur le bloc permet d'obtenir la compression et est effectuée comme suit :

{\bar {x}}\\0,&x(i,j)\leq {\bar {x}}\end{cases}}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/05aab8efbc83a69b1fe6649e5d5a3690401bd7d8">

Voici les éléments de pixel du bloc d'origine et les éléments du bloc compressé. En d'autres termes, cela peut s'expliquer ainsi : si une valeur de pixel est supérieure à la moyenne, la valeur « 1 » lui est attribuée, sinon « 0 ». Les valeurs égales à la moyenne peuvent avoir soit un « 1 » soit un « 0 » selon la préférence de la personne ou de l'organisation qui met en œuvre l'algorithme.

Ce bloc de 16 bits est stocké ou transmis avec les valeurs de moyenne et d'écart type. La reconstruction est effectuée avec deux valeurs « a » et « b » qui préservent la moyenne et l'écart type. Les valeurs de « a » et « b » peuvent être calculées comme suit :

Où est l'écart type, m est le nombre total de pixels dans le bloc et q est le nombre de pixels supérieurs à la moyenne ( )

Pour reconstruire l'image, ou créer son approximation, les éléments attribués à 0 sont remplacés par la valeur « a » et les éléments attribués à 1 sont remplacés par la valeur « b ».

Cela démontre que l'algorithme est asymétrique dans le sens où l'encodeur a beaucoup plus de travail à faire que le décodeur. En effet, le décodeur remplace simplement les 1 et les 0 par la valeur estimée alors que l'encodeur doit également calculer la moyenne, l'écart type et les deux valeurs à utiliser.

Prenez un bloc 4×4 à partir d’une image, dans ce cas l’image de test de la montagne :

Comme tout petit bloc d'une image, cela semble plutôt ennuyeux à travailler car les nombres sont tous assez similaires, c'est la nature de la compression avec perte et comment elle peut si bien fonctionner pour les images. Maintenant, nous devons calculer deux valeurs à partir de ces données, à savoir la moyenne et l'écart type. La moyenne peut être calculée à 241,875, c'est un calcul simple qui ne devrait pas nécessiter d'explication supplémentaire. L'écart type est facilement calculé à 4,36. À partir de cela, les valeurs de "a" et "b" peuvent être calculées en utilisant les équations précédentes. Elles sont respectivement de 236,935 et 245,718. Le dernier calcul qui doit être effectué côté codage consiste à définir la matrice pour qu'elle transmette des 1 et des 0 afin que chaque pixel puisse être transmis sous forme de bit unique.

Maintenant, du côté du décodeur, il ne nous reste plus qu'à réaffecter les valeurs « a » et « b » aux pixels 1 et 0. Cela nous donnera le bloc suivant :

Comme on peut le voir, le bloc a été reconstruit avec les deux valeurs de « a » et « b » comme entiers (car les images ne sont pas définies pour stocker des nombres à virgule flottante). Lorsque vous travaillez sur la théorie, c'est un bon moment pour calculer la moyenne et l'écart type du bloc reconstruit. Ils doivent être égaux à la moyenne et à l'écart type d'origine. N'oubliez pas d'utiliser des entiers, sinon de nombreuses erreurs de quantification seront impliquées, car nous avons précédemment quantifié tout en entiers dans l'encodeur.