Transformée de Fourier et codage de Huffman

Bonjour,

j'ai pour objectif d'utiliser le codage de Huffman pour réduire le poids d'un fichier audio wav. J'ai pour l'instant un algorithme qui réalise le codage de Huffman sur un texte. A travers mes recherches j'ai cru comprendre que pour utiliser Huffman sur un son il fallait utiliser la transformée de Fourier rapide (FFT), n'y connaissant pas grand chose j'ai trouvé un code qui semble bien fonctionner. Cependant en sortie il me renvoie la liste des fréquences mais il n'y a aucune redondance, ce qui est très problématique vu que c'est la base de Huffman. J'ai testé plusieurs échantillons sonores qui étaient pourtant assez répétitifs… Voici le code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import numpy as np
from scipy.io.wavfile import read
Fe, signal = read('oiseau.wav')

N = len(signal)
Duree = N / Fe
plt.figure(1)
plt.clf()
T = np.linspace(0,Duree, N)
plt.subplot(2,1,1)  
plt.title("Fichier Audio : signal et Spectre")
plt.xlabel("Durée (en sec.)")
plt.plot(T, signal)

from scipy.fftpack import fft, fftfreq
tfd_signal = fft(signal)    # TFD du signal
freq_signal = fftfreq(N, 1./Fe)    # Fréquences
l=int(len(freq_signal)/2-1)

plt.subplot(2,1,2)
plt.xlabel("Fréquence (en Hz)")
plt.plot(freq_signal[1:l],abs(tfd_signal[1:l]))
plt.show()

Voici le lien de l’enregistrement sonore.

J'ai pu comparer le spectre temporel en sortie avec celui que me donne le logiciel Audacity et ça colle bien, donc l'algo semble bien tourner. Du coup je me demande si je n'ai juste pas bien compris comment fonctionne la compression du son via FFT+Huffman…

Merci de m'éclairer.

Salut,

A ce que je sache, le FFT n'est pas censé servir à compresser du son, ou du moins pas sans pertes de qualité plus ou moins audibles. A partir de là il faut savoir ce que tu veux, algorithme de compression audio avec ou sans pertes.

L'algorithme de Huffman n'est clairement pas optimum pour compresser du son aussi bien qu'il peut le faire pour du texte, mais on arrive quand même à le voir fonctionner (tu vas gagner peut-être 10 ou 20% de place, pas beaucoup plus).

J'ai du mal à voir la logique selon laquelle passer à des données fréquencielles plutôt que temporelles améliorerait une compression de Huffman faite ensuite. Ton son a beau paraître répétitif, à moins que les répétitions coincident avec la taille des fenêtres utilisées dans le FFT, à mon avis, peu probable de retrouver des données répétitives qui aideraient l'algorithme de Huffman.

J'ai peut-être mal compris mais il me semble que la compression du son via Huffman passe par la FFT. Si ceci est faux, à quelle méthode penses-tu quand tu parles de Huffman pour compresser du son ?

A priori la compression avec perte ne me dérange pas vraiment tant que l'enregistrement audio reste de qualité acceptable. En fait je voudrais voir jusqu'à où on peut aller en utilisant différentes compressions tout en gardant une qualité sonore correcte. J'ai bien conscience que d'autres méthodes peuvent être meilleures ou plus adaptées mais je voudrais travailler avec Huffman principalement et une compression type MP3 en enlevant les fréquences inaudibles et autres méthodes de ce genre.

Merci pour l'aide.

Le codage MP3 utilise de la compression de Huffmann sur des samples dans le domaine fréquentiel (et non temporel), mais pas exactement avec de la FFT/DFT.

A partir du signal temporel, il y a un filtrage sur 32 sous bandes (Polyphase Quadrature Filter, et sur chacune de ces 32 sous-bandes, une transformée en cosinus discrete modifié (MDCT) - qui une soeur de la DCT-IV qui est la fille de la DCT qui est la cousine de la DFT - puis une quantification non-linéaire basé sur un modèle psychoacoustique (fait sur une analyse de la FFT du signal), et enfin un codage de Huffmann sur ces samples.

Il est clair qu'il faut faire la compression (avec ou sans pertes) dans le domaine fréquentiel et non temporel, et il est éprouvé dans plusieurs standards de compression audio (et aussi de compression d'images - oui, il y a des fréquences dans les images! -).

http://www.emc.fr/upload/resource/pdf/34.pdf

http://blog.bjrn.se/2008/10/lets-build-mp3-decoder.html

http://www-ee.stanford.edu/~osgood/Sophomore%20College/Audio%20Compression%20and%20the%20MP3%20Standard.pdf

Comprendre aussi que l'analyse du signal avec des outils d'analyse fréquentielle (FFT, DFT, MDCT,…) se fait en audio avec une fenêtre glissante : https://en.wikipedia.org/wiki/Short-time_Fourier_transform#Sliding_DFT

La compression huffman permet juste d'avoir un encodage (symbole et véritable valeur) optimal pour un contenu donné. En ce sens, c'est une compression sans perte et on l'utilise, il me semble, partout en bout de chaîne de compression.

Cela veut dire entre autre que tu peux utiliser une compression avec perte (ou sans) qui va générer un nouveau contenu et ensuite utiliser la compression huffman (donc faire une étude des fréquences d'apparition de tes symboles afin de générer un dictionnaire) et encoder ton contenu à partir de ton dictionnaire.

Merci pour vos réponses, j'ai aussi avancé de mon côté. Du coup de façon à créer de la redondance (ce qui est bien pratique pour Huffman), je fais la FFT du signal audio et je passe toutes les fréquences dont l'intensité est faible à 0. Ainsi j'ai en gros 80% de 0 en gardant les fréquences vraiment importantes pour le signal. Je n'ai pour l'instant plus de questions je repasserai peut-être si besoin, merci à vous.