Brevet FR3018385A1 — publié le 20150911

- 1 - La présente invention concerne l'ajout de la quantification vectorielle à un codec vocal (méthode de compression et décompression audio pour la voix) utilisant FFT (la transformation de Fourier rapide, Fast Fourier Transform en Anglais) et les pics locaux. Ce codec ignore les phases et ne nécessite pas de recouvrement des trames. Enfin, ce codec qui ne prend en compte que les points de plus grande magnitude et les bandes les plus énergétiques, a donné des taux de compression très élevés avec peu de calculs (brevet Français numéro 06 07091 délivré en 2008). Les méthodes les plus répandues actuellement utilisent le codage prédictif linéaire (LPC, Linear Predictive Coding en Anglais) dans le domaine temps pour la voix. Ces méthodes utilisent les coefficients LPC et/ou LSF (Line Spectral Frequencies en Anglais), et beaucoup utilisent la compression par quantification vectorielle. Nous allons parler dans ce document de magnitudes et de positions (fréquences), notions liées à FFT. Cette étude vise particulièrement les téléphones portables et tous les appareils utilisant les rayonnements électro-magnétiques pour transmettre les données audio contenant la voix. Moins il y a de données à émettre, plus ces appareils pourront réduire leurs rayonnements électro-magnétiques. Moins il y a de calculs et de données à transmettre, moins il y a de consommation batterie. Elle concerne aussi les communications via Internet où le bas débit, la qualité et la robustesse vis-à-vis des pertes de trames sont des qualités recherchées. Il s'agit donc de méthodes de compression et décompression audio additionnelles pour les méthodes utilisant la transformation de Fourier rapide (FFT), les pics locaux et négligeant les phases, caractérisées en ce qu'on utilise un ou plusieurs dictionnaires statiques pour les positions (fréquences) et les magnitudes, la quantification vectorielle et la recherche exacte ou approximative du plus proche voisin dans ce ou ces dictionnaires Avec l'ajout de la compression par quantification vectorielle, la recherche du plus proche voisin par des méthodes approximatives (ANN, Approximate Near Neighbor en Anglais) et l'ajout de dictionnaires statiques, toujours avec peu de calculs, on peut communiquer facilement à des débits de 1250 bits par seconde à 500 bits par seconde (sans compter les silences non éventuellement transmis), avec une grande qualité. - 2 - On peut améliorer les taux de compression en ajoutant une compression sans perte comme le codage de Huffman et la compression arithmétique. Utilisées seules, ces méthodes ne vont pas assez loin. On peut aussi améliorer les taux de compression en ajoutant une compression sans perte avec un dictionnaire dynamique comme par exemple LZW, LZ77 et Deflate (LZ77 puis Huffman). Mais ces méthodes sont lentes à démarrer, les dictionnaires utilisés sont non partageables et peuvent devenir très volumineux. Le principal obstacle à leur utilisation dans les communications vocales concernent la perte des données : les dictionnaires côté émetteur et côté récepteur deviennent incohérents. La taille d'un dictionnaire statique contenant tous les codes est trop grande pour être utile. Ces méthodes sont à utiliser pour les fichiers et les média sûrs. Pour les média sûrs, on peut utiliser un groupe de trames pour la construction du dictionnaire et effectuer un vidage des données compressées à la fin de chaque trame. Le codec sur lequel on va appliquer la compression vectorielle utilise FFT et les pics locaux sans les phases. La sortie est caractérisée par un champ de positions (fréquences) et un champ de magnitudes. Nous utilisons un dictionnaire (codebook en Anglais), statique (qui ne change pas après le chargement et qui est éventuellement partageable sur un serveur), ne contenant pas toutes les combinaisons (mais qui est relativement peu volumineux), et la recherche du plus proche voisin par des méthodes exactes ou approximatives très rapides (ANN). On peut utiliser un dictionnaire pour les positions et un autre pour les magnitudes ; on peut aussi utiliser un seul dictionnaire où les vecteurs sont composés, pour chaque trame, des positions puis des magnitudes, ou des magnitudes puis des positions ou encore des paires (magnitudes, positions) ou (positions, magnitudes). Sans la compression vectorielle, suivant le nombre total des pics locaux à utiliser, on peut choisir les positions relatives ou les positions absolues. Avec une fréquence d'échantillonnage de 8 kHz et des tailles de tampon FFT de 256, les positions absolues sont comprises entre 0 et 128 (ces nombres représentent des fréquences et sont aussi appelés des 30 bins). Les positions relatives sont obtenues en comptant le nombre de bins ignorés entre deux pics locaux successifs pris en compte. - 3 - Si deux pics locaux sont trop éloignés les uns des autres, on intercale des points de magnitude nulle ayant comme position relative le nombre maximum utilisé pour le codage des positions. Les positions sont très sensibles, surtout les quatre premières (on ne peut pas changer la position de ces points sans déformer la voix). Vers les hautes fréquences, la sensibilité diminue nettement. Le champ des positions relatives est très redondant et convient bien à la compression sans perte. Cependant, pour des raisons que nous expliquerons plus loin, nous utilisons les positions absolues avec l'utilisation de la compression vectorielle. Le logarithme simple est utilisé pour le codage des magnitudes. Les magnitudes sont moins sensibles que les positions. Avec l'utilisation de la compression vectorielle, nous utilisons le logarithme simple à base b, par exemple b=2 (base 2), b= e (base e) ou b=10 (base 10). Avec l'usage du logarithme à base b et une précision de n bits, les magnitudes sont codées à l'aide de la formule suivante : Code = 0 pour les points nuls, sinon : Code = (ValeurMaximum * logb (Magnitude)) / logb (MagnitudeMaximum). ValeurMaximum = valeur maximum dépendant de la précision n (ValeurMaximum = 2h-1, par exemple 15 en 4 bits, 255 en 8 bits, 4096 en 12 bits, 65536 en 16 bits). MagnitudeMaximum = 32767 * Nombre de points par trame. Magnitude = magnitude du point. Nous n'envoyons pas directement ces codes, mais la différence avec la plus grande magnitude de la trame. Les vecteurs des magnitudes sont constitués de la différence avec la plus grande magnitude, pour chaque trame. Cette plus grande magnitude peut être ajoutée aux vecteurs des magnitudes dans le dictionnaire et / ou peut être envoyée avec l'en-tête de la trame. L'utilisation du logarithme simple et de la différence de logarithmes rend le codec moins sensible aux changements de volume (niveau d'enregistrement) car une différence des logarithmes est équivalente à un logarithme du quotient : - 4 - logb(A/B) = logb(A) - logb(B) logb(A/B) = logb((kA)/(kB)) = logb(kA) - logb(kB) où k représente un changement de volume. Il est nécessaire d'ajouter la plus grande magnitude de la trame au vecteur des magnitudes pour la retrouver lors de la décompression. On reçoit le volume général utilisé lors de la génération du dictionnaire. Si on veut avoir son propre volume, il faut transmettre la plus grande magnitude dans l'en-tête de la trame. Dans ce cas, on n'est pas obligé d'ajouter la plus grande magnitude au vecteur des magnitudes. Avec deux dictionnaires, s'il y a 16 pics locaux par trame, chaque vecteur de positions sera composé de 16 positions absolues. Chaque vecteur de magnitudes sera composé de 17 magnitudes. Avec un seul dictionnaire, chaque vecteur sera composé de 33 éléments (16+17). Le codec utilise un avant-plan constitué des points de plus grande magnitude et un arrière-plan constitué des bandes les plus énergétiques. Si on prend des bandes de deux points , chaque bande n'ayant qu'un pic local au maximum, on peut ne considérer que l'avant plan. Néanmoins, à bas débit, il faut tenir compte des bandes de plus de deux points, au moins de manière logique (points de bandes prioritaires), pour compresser davantage sans bruits de clics. Pour la recherche du plus proche voisin, plusieurs types de distance (distances classiques) sont utilisés dans la littérature et dans les logiciels. Par exemple : - la distance Manhattan ou distance L1, - la distance euclidienne ou distance L_2, - la distance Minkowski ou distance L_p, - la distance Tchebychev ou distance L_infini. Les deux premiers types sont les plus utilisés. Les dictionnaires sont générés à l'aide de l'algorithme des k-moyennes ou de l'algorithme LBG ou d'un algorithme équivalent, et d'un nombre significatif d'échantillons. - 5 - - Algorithme des k-moyennes (k-means en Anglais) ou algorithme de Lloyd : il s'agit d'un algorithme de partitionnement de données relevant des statistiques et de l'apprentissage automatique non supervisé. C'est une méthode dont le but est de diviser des observations en k partitions (clusters en Anglais) dans lesquelles chaque observation appartient à la partition avec la moyenne la plus proche. - Algorithme LBG (Linde-Buzo-Gray) : cet algorithme est semblable à celui des k-moyennes, mais avec une initialisation plus soignée. Les algorithmes des k-moyennes et LBG conviennent à la compression vectorielle des magnitudes (même si elles sont déjà codées à l'aide du logarithme simple). Leurs utilisations sans traitements ultérieurs peuvent poser un problème pour les positions s'il y a beaucoup de points par partition: les positions doivent rester des pics locaux (il ne doit pas y avoir deux positions contiguës). A condition de veiller à ce qu'il n'y ait que des pics locaux dans une trame, les centres des partitions peuvent être pris pour la construction du dictionnaire des positions et du dictionnaire des magnitudes, ou du dictionnaire des positions et magnitudes. Les points les plus proches des centres des partitions peuvent être pris pour la construction du dictionnaire des positions et du dictionnaire des magnitudes, ou du dictionnaire des positions et magnitudes. On peut donc utiliser pour la compression des positions et des magnitudes une variante des algorithmes des k-moyennes et LBG où on prend, à la convergence ou à la fin des itérations, le vecteur le plus proche du centre de la partition au lieu de prendre le centre lui même. Avec la recherche du plus proche voisin, tous les membres d'un vecteur sont équivalents et ont le même poids. l'ordre dans les vecteurs des magnitudes n'est pas très important. L'ordre dans les vecteurs des positions est très important, surtout pour les premières valeurs. Si on utilise deux dictionnaires, on recherche les vecteurs des magnitudes avec une distance classique, notamment la distance Manhattan ou la distance euclidienne ; on recherche les vecteurs des positions avec une distance classique, notamment la distance Manhattan ou la distance euclidienne, en appliquant des coefficients de pondération au chargement du dictionnaire et lors des recherches dans le dictionnaire. - 6 - Par exemple, les premiers membres des vecteurs sont multipliés respectivement par : 65536, 4096, 256 et 16 avec la distance Manhattan, 1024, 256, 64, 16 et 4 avec distance euclidienne. L'ordre des positions étant important, il vaut mieux par exemple deux premières positions identiques que toutes les positions identiques sauf les deux premières. Les positions absolues sont utilisées car la compression par quantification vectorielle étant avec perte, les erreurs liées aux positions relatives se cumulent. S'il y a toutes les combinaisons de positions probables dans la base, il n'y a pas de problème. Sinon, la qualité se dégrade vite avec juste une distance classique. Avec l'ajout de la pondération, la qualité se dégrade moins vite. Si on utilise un seul dictionnaire, on recherche les vecteurs des positions et des magnitudes avec une distance classique, notamment la distance Manhattan ou la distance euclidienne, en appliquant des coefficients de pondération aux positions au chargement du dictionnaire et lors des recherches dans le dictionnaire. Il faut signaler que plusieurs algorithmes existent pour la construction des index en vue d'une recherche rapide dans le dictionnaire. On peut citer : les index linéaires (pour une recherche par force brute), l' arbre kd (kd-tree ou k-dimensional tree en Anglais), l'arbre k-moyennes hierarchique et le hachage LSH (Locality-Sensitive Hashing en Anglais). Il faut signaler aussi qu'avec une recherche exacte du plus proche voisin ou des k plus proches voisins, les calculs sont rapides si la dimension des vecteurs n'est pas trop grande . Pour les grandes dimensions, les calculs ne sont pas plus efficaces qu'une recherche brute. Les recherches approximatives (on interrompt les recherches au bout d'un certain nombre d'itérations ou d'une certaine précision) permettent d'aller plus vite. Les solutions ne sont pas théoriquement exactes mais elles sont pratiquement satisfaisantes. On peut générer un dictionnaire avec un nombre donné de pics locaux (par exemple 12, 16, 24 ou 32 pics) et faire une recherche de code avec juste les premiers pics (par exemple avec les 4 à 8 premiers pics). Ceci permet d'interrompre prématurément les recherches de pics locaux. Il faut optimiser les bibliothèques de recherche pour tenir compte de nombreuses valeurs nulles insérées dans les vecteurs. Toutes ces opérations permettent d'alléger les calculs tout en conservant une grande qualité. - 7 - Lors de la génération d'un dictionnaire à l'aide des k-moyennes, les résultats du partitionnement dépendent fortement des valeurs d'initialisation (centres initiaux). A chaque initialisation correspond une solution différente (optimum local) qui peut être loin de la solution optimale (optimum global). En se mettant d'accord sur des valeurs d'initialisation (dépendant de la taille du dictionnaire), on peut permettre de personnaliser ou d'améliorer un dictionnaire (pour une langue ou pour un besoin spécifique par exemple) tout en restant compatible avec des versions différentes du dictionnaire. Nous allons donner les débits obtenus dans une réalisation pratique faite avec les paramètres suivants : Fréquence d'échantillonnage : 8 kHz Nombre de pics locaux : 16 Précision des positions sans dictionnaire : positions relatives sur 4 bits. Précision des positions avec dictionnaire: positions absolues sur 16 bits Précision des magnitudes sans dictionnaire : 4 bits Précision des magnitudes avec dictionnaire : 16 bits Taille des tampons FFT : 256 Nombre de trames par seconde : 31,25 Il faut un nombre significatif d'échantillons pour construire un dictionnaire. Par exemple, on peut partir de 25 minutes d'enregistrements à partir de 50 radios différentes, avec 100 voix de femme et 100 voix d'hommes. Pour un total de 1500 secondes (25x60), il y aura 46875 (1500x31,25) vecteurs au maximum, dont plus de la moitié est constituée de silences et de répétions à enlever. On peut envoyer un en-tête d'un octet par trame (contenant des informations complémentaires) ou ne pas inclure d'en-tête . - 8 - Exemple de vecteurs de positions (sans lien avec les magnitudes ci-dessous) : 4 8 12 17 19 21 25 29 33 38 40 42 80 84 114 117 4 8 12 16 20 24 28 31 35 39 44 46 50 80 83 114 1 4 8 12 15 19 23 27 30 34 38 42 45 84 87 114 2 67 72 75 80 83 86 90 92 95 103 105 109 112 116 121 1 67 72 74 77 81 86 89 94 96 101 107 110 112 115 120 1 15 28 44 61 76 86 102 119 127 0 0 0 0 0 0 5 7 9 14 18 21 24 26 28 30 33 35 39 43 47 56 3 7 10 13 16 19 52 55 59 62 65 68 71 74 78 81 Exemple de vecteurs de magnitudes (sans lien avec les positions ci-dessus): 0 6094 7551 7114 3523 578 8697 4314 4290 4443 3430 12359 12735 12555 11821 12291 50492 0 5464 5463 6468 4976 2928 11767 5728 5850 6606 11997 12842 9065 10185 12517 10819 53207 7623 0 4444 5392 7436 10784 9022 10843 10679 9362 9847 13817 15312 13807 16620 14733 51427 7608 0 3330 4884 4472 5383 9670 5671 7105 6861 14037 16158 15702 10387 16721 16703 53420 5670 800 6313 2689 1456 0 676 2620 1421 825 2202 5637 9153 9044 7209 6948 47840 0 2554 6204 7291 1782 245 8431 3597 3672 4847 4744 7753 9217 9930 7946 9457 53970 1938 0 3350 5455 6757 7527 8629 7453 9038 7904 8170 7468 8235 7961 8238 8456 42854 3248 0 6832 7766 7949 10171 9893 8927 10873 0437 11969 10993 11334 11707 10569 10699 45296 Débit sans compression additionnelle avec dictionnaire : Avec un en-tête d'un octet : (8 + 16x8)x31,25 = 4240 bits par seconde. Sans en-tête : (0 + 16x8)x31,25 = 4000 bits par seconde. - 9 - Taille du dictionnaire des positions : 65536 vecteurs de 16 éléments par vecteur. Taille du dictionnaire des magnitudes : 65536 vecteurs de 17 éléments par vecteur. Avec un en-tête d'un octet : (8 + 4x8)x31,25 = 1250 bits par seconde. Sans en-tête : (0 + 4x8)x31,25 = 1000 bits par seconde. Taille du dictionnaire des positions : 4096 vecteurs de 16 éléments par vecteur. Taille du dictionnaire des magnitudes : 4096 vecteurs de 17 éléments par vecteur. Avec un en-tête d'un octet : (8 + 3x8)x31,25 = 1000 bits par seconde. Sans en-tête : (0 + 3x8)x31,25 = 750 bits par seconde. Taille du dictionnaire des positions : 256 vecteurs de 16 éléments par vecteur. Taille du dictionnaire des magnitudes : 256 vecteurs de 17 éléments par vecteur. Avec un en-tête d'un octet : (8 + 2x8)x31,25 = 750 bits par seconde. Sans en-tête : (0 + 2x8)x31,25 = 500 bits par seconde. Taille du dictionnaire des positions et des magnitudes: jusqu'à 16777216 vecteurs (24 bits) de 33 éléments par vecteur. Avec un en-tête d'un octet : (8 + 3x8)x31,25 = 1000 bits par seconde. Sans en-tête : (0 + 3x8)x31,25 = 750 bits par seconde. Taille du dictionnaire des positions et des magnitudes: 65536 vecteurs (16 bits) de 33 éléments par vecteur. Avec un en-tête d'un octet : (8 + 2x8)x31,25 = 750 bits par seconde. Sans en-tête : (0 + 2x8)x31,25 = 500 bits par seconde. Ces méthodes sont destinées à toutes les communications vocales (via Internet ou les téléphones portables par exemple) et au stockage des données vocales (comme les fichiers sur disque dur ou sur carte mémoire par exemple). Les très bas débits obtenus vont permettre de réduire les bandes passantes et les espaces de stockage nécessaires de manière significative. En outre, les appareils utilisant les ondes électro-magnétiques pour transmettre les données (comme les téléphones portables) pourront tirer profit de ces très bas débits pour réduire sensiblement leurs émissions d'ondes et leur consommation de batterie. REVENDICATIONS1) Méthodes de compression et décompression audio additionnelles pour les méthodes utilisant la transformation de Fourier rapide (FFT), les pics locaux et négligeant les phases, caractérisées en ce qu'on utilise un ou plusieurs dictionnaires statiques pour les positions (fréquences) et les magnitudes, la quantification vectorielle et la recherche exacte ou approximative du plus proche voisin dans ce ou ces dictionnaires. Ces méthodes sont destinées à toutes les communications vocales (via Internet ou les téléphones portables par exemple) et au stockage des données vocales (comme les fichiers sur disque dur ou sur carte mémoire par exemple). 2) Méthode selon la revendication 1, caractérisée en ce qu'on peut utiliser un dictionnaire pour les positions et un autre pour les magnitudes ; on peut aussi utiliser un seul dictionnaire où les vecteurs sont composés, pour chaque trame, des positions puis des magnitudes, ou des magnitudes puis des positions ou encore des paires (magnitudes, positions) ou (positions, magnitudes). 3) Méthode selon la revendication 1, caractérisée en ce que les dictionnaires sont générés à l'aide de l'algorithme des k-moyennes ou de l'algorithme LBG ou d'un algorithme équivalent, et d'un nombre significatif d'échantillons. 4) Méthode selon la revendication 1, caractérisée en ce qu'a condition de veiller à ce qu'il n'y ait que des pics locaux dans une trame, les centres des partitions peuvent être pris pour la construction du dictionnaire des positions et du dictionnaire des magnitudes, ou du dictionnaire des positions et magnitudes. 5) Méthode selon la revendication 1, caractérisée en ce que les points les plus proches des centres des partitions peuvent être pris pour la construction du dictionnaire des positions et du dictionnaire des magnitudes, ou du dictionnaire des positions et magnitudes. 6) Méthode selon la revendication 1, caractérisée en ce que le logarithme simple est utilisé pour le codage des magnitudes ; les positions absolues sont utilisées car la compression par quantification vectorielle étant avec perte, les erreurs liées aux positions relatives se cumulent.) Méthode selon la revendication 1, caractérisée en ce que si on utilise deux dictionnaires, on recherche les vecteurs des magnitudes avec une distance classique, notamment la distance Manhattan ou la distance euclidienne ; on recherche les vecteurs des positions avec une distance classique, notamment la distance Manhattan ou la distance euclidienne, en appliquant des coefficients de pondération au chargement du dictionnaire et lors des recherches dans le dictionnaire ; si on utilise un seul dictionnaire, on recherche les vecteurs des positions et des magnitudes avec une distance classique, notamment la distance Manhattan ou la distance euclidienne, en appliquant des coefficients de pondération aux positions au chargement du dictionnaire et lors des recherches dans le dictionnaire. 8) Méthode selon la revendication 1, caractérisée en ce que les vecteurs des magnitudes sont constitués de la différence avec la plus grande magnitude, pour chaque trame. Cette plus grande magnitude peut être ajoutée aux vecteurs des magnitudes dans le dictionnaire et / ou peut être envoyée avec l'en-tête de la trame. L'utilisation du logarithme simple et de la différence de logarithmes rend le codec moins sensible aux changements de volume (niveau d'enregistrement) car une différence des logarithmes est équivalente à un logarithme du quotient. 9) Méthode selon la revendication 1, caractérisée en ce qu'on peut générer un dictionnaire avec un nombre donné de pics locaux (par exemple 12, 16, 24 ou 32 pics) et faire une recherche de code avec juste les premiers pics (par exemple avec les 4 à 8 premiers pics). 10) Méthode selon la revendication 1, caractérisée en ce qu'en se mettant d'accord sur des valeurs d'initialisation (dépendant de la taille du dictionnaire), on peut permettre de personnaliser ou d'améliorer un dictionnaire (pour une langue ou pour un besoin spécifique par exemple) tout en restant compatible avec des versions différentes du dictionnaire.