Mise en œuvre rapide d'un DCT 1d à 8 points pour le décodeur JPEG modifié

Question

J'ai travaillé sur un codec vidéo personnalisé pour une utilisation sur le Web. Le codec personnalisé sera alimenté par javascript et l'élément Canvas html5.

Il y a plusieurs raisons pour lesquelles je veux faire cela que je vais énumérer au bas de cette question, mais je veux d'abord expliquer ce que j'ai fait jusqu'à présent et pourquoi je cherche une transformation DCT rapide.

L'idée principale derrière toute compression vidéo est que les images les unes à côté des autres partagent une grande quantité de similitudes. Donc ce que je fais, c'est que j'envoie la première image compressée en jpg. Ensuite, j'envoie une autre image Jpeg qui est 8 fois plus large que la première image contenant les "différences" entre la première image et les 8 images suivantes.

Cette grande image Jpeg contenant les "différences" est beaucoup plus facile à compresser car elle ne possède que des différences. J'ai fait beaucoup d'expériences avec ce grand format JPEG et j'ai découvert que lorsqu'ils sont convertis en un espace colorimétrique YCbCr, les canaux "chroma" sont presque complètement à plat, avec quelques exceptions notables. En d'autres termes, il y a peu de parties de la vidéo qui changent beaucoup dans les canaux de chrominance, mais certaines des parties qui changent sont assez significatives. Avec cette connaissance, j'ai cherché comment la compression JPEG fonctionne et j'ai vu que, entre autres, elle utilise la DCT pour compresser chaque bloc 8x8. Cela m'intéressait vraiment parce que je pensais que si je pouvais le modifier pour qu'il comprime non seulement "chaque" bloc 8x8, mais il vérifie aussi si le "prochain" bloc 8x8 est similaire au premier. Si c'est assez proche, envoyez simplement le premier bloc et utilisez les mêmes données pour les deux blocs. Cela augmenterait à la fois la vitesse de décodage et améliorerait le transfert de débit car il y aurait moins de données à exploiter. Je pensais que cela devrait être une tâche simple à accomplir. J'ai donc essayé de construire mon propre encodeur/décodeur jpeg "modifié". J'ai construit le convertisseur RGB en YCbCr, j'ai laissé la compression "gzip" pour faire le codage de huffman et maintenant la seule partie principale qui me reste est de faire les transformations DCT.

Cependant, cela m'a bloqué. Je n'arrive pas à trouver une transformation rapide en 8 points 1d dct. Je suis à la recherche de cette transformation spécifique car selon de nombreux articles que j'ai lus, la transformation 2d 8x8 dct peut être séparée en plusieurs transformations d'identifiants 1x8. C'est l'approche de nombreuses implémentations de l'utilisation de jpeg car il est plus rapide à traiter. J'ai pensé que Jpeg étant un vieux standard bien connu, un ddt 1d rapide de 8 points devrait juste me sauter dessus, mais après des semaines de recherche, je n'ai pas encore trouvé un.

J'ai trouvé beaucoup d'algorithmes qui utilisent l'approche de complexité O (N^2). Cependant, c'est incroyablement lent. J'ai également trouvé des algorithmes qui utilisent la transformée de Fourier rapide et je les ai modifiés pour calculer le DCT. Tels que celui de ce lien ci-dessous:

https://www.nayuki.io/page/free-small-fft-in-multiple-languages

En théorie, cela devrait avoir la « rapide » complexité de O (Nlog2 (n)), mais quand je le lance, il prend mon ordinateur Core i7 environ 12 secondes encoder/décoder le jpeg "modifié".

Je ne comprends pas pourquoi c'est si lent? Il existe d'autres décodeurs jpeg javig qui peuvent le faire beaucoup plus rapidement, mais quand j'essaie de regarder à travers leur code source, je ne peux pas savoir quelle partie est en train de faire les transformations DCT/IDCT.

https://github.com/notmasteryet/jpgjs

La seule chose que je peux penser est peut-être les mathématiques derrière le TCD a déjà été précalculée et stockée dans une table de recherche ou quelque chose. Cependant j'ai regardé dur sur google et je ne peux rien trouver (que je comprends au moins) qui parle de ceci. Donc, ma question est où puis-je trouver/comment puis-je construire un moyen rapide de calculer une transformation ddt 1d de 8 points pour ce codeur/décodeur jpeg "modifié". Toute l'aide pouvant etre apportée serait très appréciée.

D'accord quant à pourquoi je veux faire cela, la raison principale est que je veux avoir une vidéo "interactive" pour les téléphones mobiles sur mon site. Cela ne peut pas être fait à cause de choses comme iOS charger son lecteur de temps rapide "natif" chaque fois qu'il commence à lire une vidéo. En outre, il est difficile de faire en sorte que la transition vers un autre moment de la vidéo semble "douce" lorsque vous avez si peu de contrôle sur la façon dont les vidéos sont rendues en particulier sur les appareils mobiles.

Merci encore pour votre aide!

Answer 1

Donc ma question est où puis-je trouver/comment puis-je construire un moyen rapide de calculer un 8 points 1d transformée TCD pour cette « modifié » encodeur jpeg/décodeur. Toute l'aide pouvant etre apportée serait très appréciée.

un coup d'oeil dans le flash-monde et le codeur JPEG là (avant qu'il ne soit inegrated dans le moteur).
Ici par exemple: http://www.bytearray.org/?p=1089 (sources fournies) ce code contient une fonction appelée fDCTQuant() qui fait le DCT, d'abord pour les lignes, puis pour les colonnes, puis il quantifie le bloc (donc là bas vous avez votre DCT 8x1).

donc ce que je fais est que j'envoie la première image compressée en format JPG. Puis-je envoyer une autre image Jpeg ...

un coup d'oeil à JPEG progressif. Je pense que certaines des choses comment cela fonctionne, et comment le flux de données est construit retentira sorte de familier avec cette description (pas la même chose, mais ils vont tous les deux dans les différents sens. Imo)

ce si je pouvais le modifier pour qu'il ne comprime pas seulement "chaque" bloc 8x8, mais il vérifie aussi si le "prochain" bloc 8x8 est similaire au premier. Si c'est assez proche, envoyez simplement le premier bloc et utilisez les mêmes données pour les deux blocs.

Les expressions "similaires" et "assez proche" a attiré mon attention ici. jetez un oeil aux tables de quantification habituellement utilisées. vous savez, qu'une modification de la valeur de 1 pourrait facilement entraîner une variation de valeur de 15% de luminosité (pour les canaux de chrominance en général encore plus) de ce point en fonction de la position dans le bloc 8x8 et donc du quantificateur appliqué.

calculation with quantifier 40 
(may be included in the set even at the lowest compression rates 
at lower compression rates some quantifier can go up to 100 and beyond) 

change the input by 1 changes the output by 40. 
since we are working on 1byte value-range it's a change of 40/255 
that is about 15% of the total possible range 

Alors vous devriez être vraiment réfléchi ce que vous appelez « suffisamment proche ».

---

Pour résumer cela: Eh bien un codec vidéo basé sur jpeg qui utilise les différences entre les cadres pour réduire la quantité de données. Cela m'a aussi semblé familier.

Got it: MPEG https://github.com/phoboslab/jsmpeg
* aucun lien avec les codes référencés ou le codeur

Answer 2

Ce livre montre comment la matrice TCD peut être pris gaussienne forme normale. Ce serait le moyen le plus rapide de faire un DCT.

http://www.amazon.com/Compressed-Image-File-Formats-JPEG/dp/0201604434/ref=pd_sim_14_1?ie=UTF8&dpID=41XJBED6RCL&dpSrc=sims&preST=_AC_UL160_SR127%2C160_&refRID=1Q0G2H5EFYCQW2TJCCJN

Answer 3

I mis en œuvre entier séparables 2D TCD de différentes tailles (ainsi que d'autres transformations) ici: https://github.com/flanglet/kanzi/tree/master/java/src/kanzi/transform. Le code est en Java mais vraiment pour ce genre d'algorithme, c'est à peu près la même chose dans n'importe quel langage. La partie la plus intéressante de l'IMO est la mise à l'échelle que vous faites après avoir calculé chaque direction. En fonction de vos objectifs (précision maximale, calcul 16 bits, pas de mise à l'échelle, ...), vous pouvez modifier les facteurs d'échelle pour chaque étape. L'utilisation de gros blocs dans les zones où l'image est très uniforme permet d'économiser des bits.