Compression du son

[invite31e4232f]

Bonjour,

J'espère être dans la bonne section pour poster.

J'ai pour objectif d'utiliser le codage de Huffman sur un fichier audio wav de façon a réduire son poids. J'ai déjà mon programme qui réalise le codage de Huffman pour un texte. M'étant renseigné sur la question j'ai cru comprendre qu'il fallait, pour compresser un son, accéder à ses fréquences via une transformée de Fourier puis envoyer le tableau des fréquences dans le codage de Huffman.
J'ai réussi à faire la transformée de Fourier rapide (FFT) d'un fichier wav mais c'est à ce stade que je bloque. En effet l'algorithme me renvoie en sortie plusieurs milliers de fréquences qui sont toutes différentes. Or le principe de Huffman est de réduire le poids des entités qui reviennent le plus souvent et vice-versa. Ainsi je pense ne pas avoir compris comment fonctionne réellement le principe de compression du son via FFT+Huffman...

Merci de votre aide.
-----

[inviteb9f49292]

J'ai pour objectif d'utiliser le codage de Huffman sur un fichier audio wav de façon a réduire son poids.

Je ne sais plus si huffman c'est du dictionnaire mais en générale ce type de compression n'est pas efficace sur de la "donnée réelle" car il n'y a en général pas assez de données redondantes pour que ce soit intéressant, à l'inverse de données "synthétiques" (fichier texte, programme informatique, image avec peut de nuance de couleur...).

Je connais deux type de fonctionnements pour de la donnée "peu redondante"
- compression sans par perte réduction de la dynamique (-> augmentation de la redondance) puis compression type dictionnaire
- compression avec perte ou la compression se fait ... en enlevant de l'information

De mémoire, le FLAC est un exemple du 1er type de compression pour du signal audio, on diminue la dynamique en ne gardant les 1ers échantillons de chaque canaux, puis la différence successive des échantillons, car on considère que l'échantillon x[n] et x[n+1] est petite, donc tu passes par exemple d'un besoin de 16bits pour 1 échantillons à (par exemple) 6bits pour la différence -> gain (cette proximité est également vraie entre les canaux, l'échantillon y[n] étant très proche, en général, de l'échantillon x[n]). Autre gain de la réduction de la dynamique, tu augmentes en général la redondance car (avec les doigts) 16bits -> 1/65536 chance pour 2 échantillons d'être identiques, ça passe à 1/64 pour 6bits (2^6). Du coup, un huffman derrière à plus de chance d'être efficace.

Pour la compression avec perte, on "modélise" le signal pour virer les info qui ne nous intéresse pas. Un exemple est le MP3, on utilise la physiologie de l'oreille humaine pour virer les fréquences qu'elle n'entendra pas. En effet, l'oreille humaine n'entendra que la fréquence la plus forte par gamme de bark, on vire donc toute les autres (on met des zéro). Concrètement tu marches par fenêtre (ce n'est pas un traitement à appliquer au signal complet), tu prends la TF de quelques points, tu vires les fréquences que l'oreille n'entends pas (mettre des 0 dans la TF) et tu passes à la fenêtre suivante... 0 la fin, tu as une succession de TF avec (à priori) beaucoup de zéro -> info redondante, tu peux encoder efficacement par un dictionnaire.

As tu droit à de la perte d'info ? Si ce n'est pas le cas, pas vraiment de choix, utilises du FLAC, je ne pense pas que tu puisses faire mieux (sur du signal audio-musical en tout cas, donc avec une relative "proximité" des valeurs en temporel et en inter-canaux)

Pour la compression avec perte, la modélisation de l'oreille humaine n'est pet-être pas adapté car suivant le type d'analyse que tu veux faire, les fréquences que ton oreille n'entendraient pas (donc virées lors d'une compression type MP3) peuvent transporter des informations fondamentales pour l'analyste, si tu les lui vire il risque de ne pas être content, mais alors c'est lui qui est le mieux placé pour dire les info que tu peux virer (ça peut être un simple filtre passe-bande fonctionnant sur ta TF, où des trucs très compliqué comme l'encodage de la parole pour le GSM...).

[invite31e4232f]

Merci pour ta réponse fournie.

J'avoue avoir mal compris comment mettre en place la compression FLAC, mais tu m'as ouvert d'autres pistes que je vais explorer.

Huffman n'est peut-être pas le plus adapté pour un fichier audio mais j'en ai justement pris un qui se répète pour voir ce que cela peut donner.
Concernant la FFT, mon échantillon sonore est des bruits d'oiseau assez répétitifs, c'est pour cela que je m'étonne de voir que toutes les fréquences données par la FFT ont le même nombre d'occurrence. Voici mon code:

 Cliquez pour afficher

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

Le son a été téléchargé ici: http://lasonotheque.org/detail-0431-...illements.html

Si quelqu'un a une idée du pourquoi aucune fréquence ne se dégage après FFT merci de m'aider.

EDIT: je crois avoir une piste: en fait c'est normal que toutes les fréquences soient présentes mais seules certaines correspondent à une intensité élevée. Ca serait donc comme cela que je vais pouvoir enlever les "moins importantes" ?

[inviteb9f49292]

J'avoue avoir mal compris comment mettre en place la compression FLAC

Il ne faut pas le prendre au pieds de la lettre, mais plutôt comme un schéma directeur, et si tu veux faire du flac, aucun intérêt de le faire soi-même (à part dans un but éducatif), il existe es encodeurs - decodeurs flac libres.

j'en ai justement pris un qui se répète pour voir ce que cela peut donner.

Soit bien sûr que ton son soit représentatif de ce que tu veux compresser, et qu'il soit générer de la même manière, en effet il marchera probablement bien sur un son synthétique (généré par un algo -> redondance), mais plus du tout sur un son enregistré à cause du bruit d'ambiance, d'acquisition, électronique (plus de redondance)...

assez répétitifs

Ce n'est pas parce que c'est répétitif à l'oreille que ça l'est suffisament pour huffman

Dit autrement, ton oreille+ton cerveau compressent un signal complexe grâce à un travail d'analyse: l'oreille vire des sons, le cerveau augmente le signal d'intérêt (l'oiseau) et diminue les bruits parasites (vent, voitures...), il lisse les différences d'intonation de l'oiseau du coup le piou-piou-piou-piou devient 4xpiou, tu as compressé d'un facteur 4 au prix de l'élimination de l'information non-pertinente dans _CE_ contexte (la perception du bruit des oiseaux par l'homme). Change de contexte en étudiant la perception des oiseaux par les oiseaux par exemple, et les informations éliminées risquent de manquer: si l'oreille de l'oiseau n'élimine pas de la même manière que celle de l'homme, et son cerveau ne focalise peut être pas les même types de sons, de la même manière.

Le "problème" d'une compression type huffman (ou dictionaire...) est qu'elle ne tient pas compte de ce que veut dire la donnée que tu compresses, elle ne cherche qu'a optimiser des suites de 0 et de 1 pour trouver les séquences les plus grandes qui se répêtent le plus. Tu es donc obligé de créer de la redondance avant, en modélisant ton signal ça te permet de faire le tri entre ce qui t'intéresse, et le reste te permet de créer de la redondance (en éliminant l'information). Pousser à l'extrême, le FLAC c'est la même chose, mais au lieu de se baser sur la "sémantique" (piou-piou), il se base sur la physique: les sons sont "continus" et les voies droites et gauches entendent quasiment la même chose, et au lieu d'éliminer l'information pour créer de la redondance, il met en évidence la redondance...
Mais il doit être possible de fabriquer un son où le FLAC ne marche pas (+max -max 1 ech sur 2, et droite et gauche en opposition de phase ?).

Si quelqu'un a une idée du pourquoi aucune fréquence ne se dégage après FFT merci de m'aider.

La FFT ne s'utilise pas brut, c'est un signal complexe, en général on regarde la psd, la distribution de puissance en fonction de la freq, c'est tout simplement la valeur abs fft x fft* de la fft, plus rarement la phase arg (fft). De plus, regarder le signal complet c'est un peu manger entré, plat, dessert, pin et vin mélanger dans un mixeur, il faut que tu découpes les zones d'intérêt de ton signal, sur des durées plus ou moins longue. Un seul "piou" pour le regarder en psd, et tu peux dire sur 300ms de piou, j'ai tel puissance à 1760Hz etc... Audacity peut être utile, pour entendre le piou et voir son enveloppe.

[A voir en vidéo sur Futura]

[invite31e4232f]

Merci je commence à comprendre un peu mieux tout ça

Comme tu me l'a proposé je crée des redondances pour pouvoir utiliser Huffman. Du coup pour l'instant j'ai pris un échantillon de 200ms en gros et je fais la FFT dessus. Je mets à 0 toutes les valeurs du signal qui sont en dessous d'un seuil et le reste est conservé. Après ça, pour testé j'ai balancé le tableau dans la Transformée de Fourier Inverse et j'ai obtenu un nouveau fichier son. Le soucis est que j'obtiens pas mal de grésillements. J'ai pas l'impression que ce soit du au fait que pas mal de fréquences soient annulées puisque j'ai le même soucis en faisant FFT puis IFFT sur un enregistrement sans même toucher aux fréquences... Une idée ?

De plus ce fameux seuil à partir duquel je mets la valeur du pic correspondant à une fréquence à 0, je sais pas vraiment comment le choisir, pour l'instant j'ai pris la moyenne de tous les pics ce qui m'a viré environ 80% des pics.

Merci pour ton aide.

[inviteb9f49292]

Je mets à 0 toutes les valeurs du signal qui sont en dessous d'un seuil et le reste est conservé

Bien vu! Petit conseil, ajoute un seuil en fréquence, avec élimination ssi niveau < seuil de niveau _ET_ freq > seuil fréquence (un peu comme le jpeg), en général les hautes fréquences sont moins audibles.

J'ai pas l'impression que ce soit du au fait que pas mal de fréquences soient annulées puisque j'ai le même soucis en faisant FFT puis IFFT sur un enregistrement sans même toucher aux fréquences... Une idée ?

1er problème, la normalisation. En audio, on a l'habitude de travailler en flottants, avec pour amplitude max 1 (le niveau se balade entre +1 strictement et -1 inclu), suivant l'implémentation
- de la lecture du ficiher WAV (en général, entiers de 8, 16 ou 24 bits, plus rarement 32 bits ou flottants)
- de la FFT, tu gardes le niveau ou tu le multiplie par le nb de points utilisés dans ta fft
- de l'écriture du ficiher WAV, il peut convertir la pleine échelle (+1 -> 32767, -1 -> -32768 en 16bits signé), ou pas, alors effet de saturation
Ajoute à tout ça que tu calcules très certainement en flottant, et que si le fichier WAV écrit l'est en flottants, assez peu de lecteurs l'acceptent
Ca dépends vraiment de ce que tu utilises, je ne peux pas plus t'aider j'utilise OCTAVE pour ce genre de truc.

De plus ce fameux seuil à partir duquel je mets la valeur du pic correspondant à une fréquence à 0, je sais pas vraiment comment le choisir, pour l'instant j'ai pris la moyenne de tous les pics ce qui m'a viré environ 80% des pics.

Ce n'est pas forcément qu'une histoire de niveau, tu peux travailler par rapport aux fréquences (quelque soient leurs niveaux), si tu sais que tu as un bruit parasite situé autour des 50Hz se manifestant par une raie, tu peux filtrer en amont ou "effacer" le pic sur la fft. Encore plus radical, si tu es sûr que ton signal d'intérêt se situe entre 400 et 4000 Hz, tu peux tout virer en dehors. Bref ça commence à devenir du métier.

Trouve-toi un cours de dégrossissage en traitement du signal, de mémoire j'ai "dsp guru", il faut que je pense à regarder si j'ai d'autres au boulot.

[invite31e4232f]

Ok merci je vais essayer d'améliorer cela.
J'ai à peu près fini de relier la FFT à Huffman, j'ai fait des petites stats histoire de voir ce que cela donne sur un enregistrement de 200ms soit 8509 fréquences.

longueur codage normal: 93599 bits
longueur codage Huffman: 19301 bits
Le taux de compression est de 79.38 %

La longueur du code normal correspond à la longueur en codant toutes les valeurs sur le même nombre de bits. Mais en fait je me demande si les valeurs sont vraiment codées comme cela avant compression ou s'il y a déjà quelque chose d’optimisé ? Pour pouvoir essayer d'approcher ce qui serait un taux de compression réaliste il faudrait que j'ajoute à cela le tableau des fréquences qui sera légèrement compressé et aussi bien-sûr l'arbre de Huffman.

[invite31e4232f]

Un petit up

[inviteb9f49292]

La longueur du code normal correspond à la longueur en codant toutes les valeurs sur le même nombre de bits. Mais en fait je me demande si les valeurs sont vraiment codées comme cela avant compression

Effectivement, certain compresseurs utilisent des mots de tailles différentes: le motif se répétant le plus étant encodé par le motif de bit le plus court et ainsi de suite.

Pour pouvoir essayer d'approcher ce qui serait un taux de compression réaliste il faudrait que j'ajoute à cela le tableau des fréquences qui sera légèrement compressé et aussi bien-sûr l'arbre de Huffman.

A mon avis, tu as plus vite fait de créer ta redondance, puis de tester différents compresseurs tel que, ce que tu devrais de toute façon faire dans ton projet réel (ne _JAMAIS_ réécrire de briques de bases quand l'existant convient). Une petite remarque, si il est peut-être plus pertinent dans ton cas de tester le compresseur sur un signal brut, un WAV c'est un signal brut avec une entête de 44 octets, qui pourraient perturber tes redondances, c'est d'autant plus vrai que le ratio entête / données et important.

il faudrait que j'ajoute à cela le tableau des fréquences qui sera légèrement compressé et aussi bien-sûr l'arbre de Huffman.

Je ne te suis plus d'aucune utilité maintenant car je ne sais pas quel format transporte le dictionnaire dans le fichier compresser ou pas, et autres détails. Ceci dit, si tu penses qu'en créant un format explicite tu gagneras radicalement de la place, pourquoi pas (un code par fréquence par exemple, un peu comme le BMP à palette de couleur...), mais c'est à mon avis quelque chose à faire une fois que tu es à peu prêt sûr des blocs de ta chaîne, donc trop tôt. Mais je doute de la pertinence d'une telle approche, à part pour de l'embarqué, du "big data" (où 10% de gain d'espace représente 1To d'économisé), ou du "hautement distribué" où il faut grapiller sur les échanges entre machine...

[invite31e4232f]

Bonjour, j'aurais besoin de quelques précisions :

Si je regarde d'un point de vue globale, quelles sont les étapes de la compression du son ?
On prend un enregistrement, on lui applique la FFT puis on réalise nos modifications sur les intensité (par exemple). Mais par la suite comment se déroule le chemin jusqu'à retrouver mon fichier audio compressé ? (Notamment sur la place de la iFFT et du codage de Huffman)

Merci.

[inviteb9f49292]

Ta brique FFT n'est pas une brique de compression à proprement parlé. Le découpages en étapes serait plutôt:
- trouver une représentation qui facilite les redondances et passer ton signal dans cette représentation
- virer de l'information la moins pertinente possible pour créer tes redondances
- appliquer un algorithme sur les redondances, permettant d'encoder tes redondances dans un minimum d'espace

application à l'exemple type MP3 (je pense mais à vérifier):
- passer dans le domaine fréquentiel (FFT ou DCT par morceau de ton signal)
- dans chaque fenêtre on vire les composantes fréquentielles peu pertinentes (sur des critères psycho-acoustique), on remplace par des 0
- on se retrouve avec des données (fréquentielles) avec beaucoup de zéro -> on applique un algo type huffman

Le côté décompression c'est simplement remettre les 0 au bon endroit dans tes données (toujours fréquentiels). C'est lorsque toi, tu veux interpréter les données que tu vas repasser dans la représentation qui t'arrange, donc pour écouter de la musique je pense que c'est plus audible en représentation temporelle que fréquentielle (encore que pour du David Guetta peut-être pas), donc tu fais ta iFFT avant d'envoyer le signal décompressé dans ta carte son.

En résumé la FFT ne fait pas à proprement parlé du processus de compression, elle se place "avant", car il est plus facile de créer des redondances dans le domaine fréquentiel que dans le domaine temporel. C'est vrai pour ce type de redondance, mais pour du FLAC par exemple, ça n'est plus le cas, tu restes en temporel.

J'espère que j'ai clarifié ta lanterne, et que tu n'écouteras plus de David Guetta...

[invite31e4232f]

D'accord c'est plus clair. Merci pour cette explication.