Dr Stefano Tubaro

Frédéric Dufaux D'avoir Accepté

William Puech

Luce Morin

Fabien R., Dominique, Erik Fabien D Mehmet

Matis Ronan B Merwan

Darya Fanny

Raul Simon

Jérémy Reuben

Thomas

Mathieu Jean Gilles

Thierry Merci

Yohan, Manu, Amouda Antoine David

FX Julie Richard

Clément, Maxime, Claire Di- Dier Lucie

Adèle, Charles, Seb, Maryse, Evariste, Morgane, Lucie, Karen, Didine, Max Merci Donc À Raton

Malet Gwen

Antoine Micka

Nico Christian

Alvin Merci

Seb

Charles

amis de l'INRIA comme de Technicolor pour m'avoir accueilli et pour les bons moments

Tout d'abord, je tiens vivement à remercier Christine Guillemot, Dominique Thoreau et Philippe Guillotel, pour m'avoir encadré pendant ces trois années. Vos conseils et encouragements ont été précieux, et les nombreuses conversations que nous avons pu avoir ont nourri les travaux qui ont abouti à ce manuscrit. Je garderai un excellent souvenir de ces trois années à vos côtés, durant lesquelles j'ai beaucoup appris.

Je remercie également les membres du jury pour l'intérêt porté à mes travaux, ainsi que pour les commentaires et conseils que vous m'avez apportés. Merci donc aux Pr.

Résumé en français

Introduction

Nous sommes de plus en plus demandeurs de contenus vidéos, tout en étant de plus en plus exigeants en termes de qualité de service, notamment concernant la qualité visuelle et la rapidité d'accès. Des services comme Youtube ou plus récemment Netflix sont emblématiques de cette évolution. En dépit de la loi de Moore et des puissances de calcul ainsi que des capacités de stockage croissantes qui en découlent, la compression des contenus vidéos reste cruciale pour assurer la qualité de service désirée. De plus, pour répondre à la demande d'amélioration constante de qualité visuelle de la part d'un public de plus en plus averti, de nouveaux formats voient le jour. On peut notamment citer la vidéo à haute résolution (4K -8K), à gamme de couleur ou dynamique étendues, ou encore à fréquence d'images augmentée. Ces nouveaux formats représentent un volume de données considérable, qui doit être nécessairement comprimé. Dans un livre blanc publié en 2014, Cisco a prédit qu'en 2018 le trafic vidéo représenterait 79 % du trafic sur Internet. De plus, il est estimé que 80 % à 90 % du trafic global sera du contenu vidéo sous formes diverses (télévision, Internet, vidéo à la demande, vidéo sur IP, peer to peer ). L'efficacité des services de compression est donc un enjeu essentiel, et le sera d'autant plus dans un futur proche. De ce point de vue, le standard MPEG HEVC est aujourd'hui un des schémas de compression les plus efficaces, et remplacera au fur et à mesure son prédécesseur H.264.

Les principes fondamentaux des standards modernes de compression vidéo sont la réduction des redondances spatiales et temporelles du signal en utilisant des outils de prédiction, l'utilisation d'une transformée afin de diminuer d'avantage les corrélations du signal, une quantification afin de réduire l'information non perceptible, et enfin un codage entropique pour prendre en compte les redondances statistiques du signal. Dans le cadre de la compression sans perte, la quantification n'est pas effectuée afin de pouvoir reconstruire parfaitement le signal d'origine. Ce type de compression est notamment utile dans le cadre de l'imagerie médicale, où la fidélité du signal est capitale pour établir un diagnostic. Toutefois, les travaux de cette thèse s'inscrivent dans le cadre de la compression avec perte, qui est utilisée en particulier dans les applications grand public mentionnées ci-dessus. Dans ce cas, les pertes viennent de l'étape de quantification, et le paramètre de quantification sert alors à réguler l'équilibre entre qualité visuelle et bande-passante.

Pour faire face aux multiples récepteurs existants (télévision, ordinateur, tablette, smartphone), qui requièrent de transmettre le même contenu vidéo avec différents niveaux de qualité visuelle, de définition spatiale, de fréquence d'images, ou de profondeur de bits, des schémas de compression dits scalables sont utilisés. Le but de ces schémas de compression est d'optimiser les performances de compression en réduisant les redondances entre les différentes versions du contenu vidéo. Ces différentes versions ne sont donc pas encodées séparément : une première version du contenu est d'abord encodée et considérée comme couche de base. Une autre version, de meilleure qualité visuelle, et/ou définition spatio-temporelle, et/ou profondeur de bit, est alors encodée comme couche d'amélioration, en s'appuyant sur la couche de base décodée. Plusieurs couches d'améliorations peuvent ainsi être encodées de manière récursive afin de prendre en compte les différentes versions du contenu vidéo.

Contributions et organisation du manuscrit

Le premier chapitre présente l'état de l'art en compression vidéo, notamment les standards de compression vidéo MPEG. Les chapitres suivants contiennent les contributions de la thèse, avec en début de chapitre un état de l'art des méthodes spécifiques étudiées dans le chapitre.

Chapitre 1 : état de l'art en compression vidéo

Nous présentons dans ce chapitre les principes de bases utilisés en compression vidéo: la prédiction, la transformation, la quantification, et le codage entropique. Nous décrivons ensuite l'application de ces principes dans les standards de compressions vidéo. L'étape de prédiction a pour but de réduire les redondances spatiales et temporelles d'un signal vidéo. Les deux types de prédiction correspondant sont nommés la prédiction Intra et la prédiction Inter respectivement. Le procédé de prédiction consiste à estimer un bloc de pixels à partir de pixels disponibles dans les parties déjà décodées de la vidéo. Dans le cas de la prédiction Intra, le bloc de pixel est prédit à partir des pixels spatialement voisins, tandis que pour la prédiction Inter, il est prédit à partir des images précédemment décodées de la séquence. Dans les schémas de compression récents tels que H.264 [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF] ou HEVC [START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF], la prédiction Intra consiste à propager les valeurs des pixels sur la gauche et au-dessus du bloc courant suivant une direction prédéfinie. Dans H.264, 8 modes directionnels sont disponible, 33 dans HEVC. Un mode DC est également défini, qui consiste à prendre la moyenne des pixels voisins comme prédicteur du bloc courant. La prédiction Inter s'appuie sur l'estimation/compensation de mouvement, réalisée en général avec un algorithme de type block matching (BM). A la suite de la prédiction, on obtient un résidu de prédiction, qui correspond à la différence entre le bloc original et le bloc prédit. Ce résidu est utilisé dans l'étape suivante de transformation.

L'étape de transformation permet de réduire les corrélations d'un signal en distribuant l'énergie de ce signal sur un nombre réduit de coefficients, qui correspondent à des projections sur des fonctions de base orthogonales. La transformation peut être appliquée directement sur les pixels d'un bloc, comme dans JPEG [START_REF] Wallace | The JPEG still picture compression standard[END_REF], ou sur le résidu de prédiction, comme dans H.264 et HEVC. Les principales transformées utilisées en compression d'image ou de vidéo incluent la transformée en cosinus discrète (DCT) dans les standards JPEG, H.264 et HEVC, la transformée en sinus discrète (DST) dans HEVC, par ailleurs les transformées en ondelette discrète (DWT) sont appliquées dans SPIHT [START_REF] Said | A new, fast, and efficient image codec based on set partitioning in hierarchical trees[END_REF] et JPEG2000 [START_REF] Marcellin | An overview of JPEG-2000[END_REF].

L'étape de quantification consiste à réduire la précision du signal, en convertissant l'ensemble de taille n des valeurs du signal d'entrée en un nouvel ensemble fini de valeurs, de taille m < n. Plusieurs types de quantification existent, telles que la quantification uniforme ou non uniforme, la quantification scalaire, ou la quantification vectorielle. Dans un schéma de compression, la quantification est appliquée sur les coefficients de la transformée obtenus à l'étape précédente. La quantification est irréversible, on parle alors de compression avec perte. Le pas de quantification permet de réguler le compromis débit/qualité d'image. Une forte quantification permet de grandement réduire le débit, au détriment de la qualité. Au contraire, une quantification fine permet de maintenir une bonne qualité d'image, avec un débit plus important.

Enfin, l'étape de codage entropique exploite les statistiques du signal à coder pour en réduire les redondances. Un codeur entropique utilise un code à longueurs variables (VLC) pour construire des mots de code de différentes tailles, de telle sorte que les mots de code les plus courts sont assignés aux symboles les plus fréquents, tandis que les mots de code longs sont attribués aux symboles les moins fréquents. Parmi les codeurs entropiques les plus connus, on peut citer le codage de Huffman et le codage arithmétique. Dans un schéma de compression, le codage entropique est appliqué aux coefficients de la transformée quantifiés. Les schémas de compression récents tels que H.264 et HEVC utilisent le codeur CABAC (pour Context Adaptive Binary Arithmetic Coding) pour encoder à la fois les coefficient de la transformée quantifiés et des éléments de syntaxe.

Les standards de compression s'appuient sur un découpage des images de la séquence vidéo en blocs de pixels, et les principes décrits ci-dessus s'appliquent au niveau de ces blocs. Dans le standard H.264, les images sont d'abord découpées en macrobloc, de taille 16 × 16, qui peuvent être sous-divisés en blocs de tailles inférieures. Dans le standard HEVC, un principe similaire mais optimisé est mis en place, où les images sont d'abord découpées en CTU (coding tree unit), qui peuvent atteindre une taille de 64 × 64. La CTU peut être récursivement divisée en CUs (coding unit) de tailles inférieures, dont le partitionnement forme un arbre quaternaire.

Notons enfin que la sélection d'un mode de codage (Inter ou Intra, choix du meilleur mode directionnel Intra) s'effectue également au niveau des blocs, habituellement sur la base d'un critère d'optimisation débit/distorsion, noté RDO (pour Rate Distortion Optimization).

Chapitre 2 : prédiction inter images basée LLE

Le chapitre commence par une description des méthodes de prédiction basées template matching (TM). Ces méthodes peuvent être utilisées comme alternative au BM pour l'estimation/compensation de mouvement. Le template, ou gabarit, est défini comme l'ensemble des pixels voisins reconstruits à gauche et au-dessus du bloc courant à prédire.

On peut alors chercher un gabarit similaire parmi les zones de la vidéo déjà décodées. Le bloc associé à ce plus proche gabarit est alors utilisé comme prédicteur du bloc courant. Cette méthode peut être avantageusement reproduite au décodeur, ce qui signifie qu'aucune information de mouvement n'a besoin d'être transmise entre l'encodeur et le décodeur. La technique TM a ainsi pu être utilisée efficacement pour la prédiction Inter [START_REF] Sugimoto | Inter frame coding with template matching spatio-temporal prediction[END_REF] comme Intra [START_REF] Tan | Intra Prediction by Template Matching[END_REF]. Les performances de la méthode TM ont également été améliorées en cherchant plusieurs gabarits similaires au gabarit courant, et en combinant les blocs adjacents pour obtenir le prédicteur. Initialement, un simple moyennage était utilisé [START_REF] Tan | Intra Prediction by Averaged Template Matching Predictors[END_REF] [START_REF] Suzuki | Inter Frame Coding with Template Matching Averaging[END_REF], mais il a été montré que l'utilisation d'un moyennage pondéré, par exemple basé sur des représentations parcimonieuses [START_REF] Martin | Sparse representation for image prediction[END_REF] [START_REF] Türkan | Sparse approximation with adaptive dictionary for image prediction[END_REF], améliorent d'autant plus les performances.

Dans ce chapitre, nous proposons d'utiliser un moyennage pondéré dont les poids sont calculés en utilisant une approximation LLE (pour Locally Linear Embedding). L'efficacité de la technique LLE a été démontrée pour la prédiction Intra [START_REF] Türkan | Image prediction based on neighbor embedding methods[END_REF] [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF], et nous l'étendons ici à la prédiction Inter. L'idée principale consiste dans un premier temps à obtenir K gabarits similaire au gabarit courant. La LLE permet alors d'obtenir une combinaison linéaire des K gabarits qui approxime au sens des moindres carrés le gabarit courant, avec pour contrainte que la somme des poids soit égale à 1. La combinaison linéaire obtenue peut alors être appliquée au K blocs adjacents aux K gabarits pour obtenir le prédicteur du bloc courant.

Nous proposons plusieurs stratégies pour obtenir les K gabarits similaires au gabarit courant. La plus directe consiste à chercher les K gabarits les plus proches du gabarit courant au sens de la distance Euclidienne dans une fenêtre de recherche. Cette méthode est notée TM-LLE. L'hypothèse sous-jacente est que les blocs et gabarits sont fortement corrélés, ce qui n'est pas toujours vérifié en pratique. Toutefois cette méthode à l'avantage, comme le TM, d'être reproductible au décodeur, et ne nécessite pas de transmettre d'information sur le mouvement. Une variante de TM-LLE est présentée, notée ITM-LLE, dont le but est de renforcer les corrélations entre blocs et gabarits, sans avoir à communiquer d'information de mouvement. On cherche d'abord le plus proche gabarit du gabarit courant. Le patch composé de ce gabarit et de son bloc adjacent est alors utilisé pour trouver les K -1 patchs les plus proches dans la fenêtre de recherche. Ces K -1 patchs contiennent alors les K -1 gabarits restants nécessaires pour calculer l'approximation LLE.

Dans un second temps, nous proposons une stratégie, notée BM-LLE, qui cherche également à renforcer les corrélations entre blocs et gabarits, mais cette fois en s'appuyant sur une information de mouvement, qui est transmise au décodeur. La première étape consiste à effectuer un algorithme de type BM. Dans un second temps, le patch composé du bloc obtenu par BM et de son gabarit adjacent est alors utilisé pour trouver les K -1 patchs les plus proches dans la fenêtre de recherche.

Enfin, une dernière stratégie est décrite, qui est une optimisation de la méthode ITM-LLE, et est notée oITM-LLE. La méthode consiste à obtenir L prédicteurs en répétant L fois la méthode ITM-LLE. La meilleure itération en un sens débit/distorsion est retenue, et l'index de cette itération est transmis au décodeur.

Les différentes méthodes ont été implémentées dans H.264, mais restent valides dans HEVC. Les résultats des différentes expérimentations montrent que la méthode oITM-LLE permet d'obtenir les meilleures performances de codage, au prix d'une complexité importante. Les méthodes TM-LLE et ITM-LLE permettent un meilleur compromis entre performances de codage et complexité. La complexité de BM-LLE est raisonnable mais ses performances débit/distorsion ne sont pas meilleures que l'état de l'art. Malgré l'importante complexité de oITM-LLE, son application à la prédiction Intra, combinée à une méthode moins complexe comme TM-LLE appliquée à la prédiction Inter permet d'obtenir les meilleurs performances de codage pour une complexité convenable. Nous sommes également convaincus que la complexité des méthodes pourrait être réduite, en utilisant par exemple des méthodes de recherche des plus proches voisins rapides [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF][15] [START_REF] Zhu | 2-D Dictionary Based Video Coding for Screen Contents[END_REF] [START_REF] Cherian | Efficient Nearest Neighbors via Robust Sparse Hashing[END_REF], une estimation rapide des poids [START_REF] Wige | Sample-based weighted prediction with directional template matching for HEVC lossless coding[END_REF], ou encore en parallélisant l'implémentation, par exemple sur GPU [START_REF] Garcia | Fast k nearest neighbor search using GPU[END_REF].

Chapitre 3 : techniques de réduction du bruit de quantification basées sur des épitomes

Le chapitre commence par une description des méthodes existantes pour la génération d'épitome. Un épitome est défini comme une représentation condensée d'une image ou vidéo, contenant l'essence de ses propriétés de texture. Plusieurs types de représentations épitomiques existent [START_REF] Jojic | Epitomic analysis of appearance and shape[END_REF] [START_REF] Cheung | Video epitomes[END_REF], toutefois nous basons ce travail sur un type d'épitome adapté au contexte de la compression [START_REF] Wang | Factoring repeated content within and among images[END_REF] [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF]. Pour créer ce type d'épitome, la première étape consiste à rechercher les auto-similarités de l'image, ce qui permet d'obtenir pour chaque bloc de l'image une liste d'appariements contenant des blocs similaires, c'est à dire dont la distance Euclidienne est inférieure à un certain seuil prédéfini. Dans un second temps, on peut générer de manière itérative des épitomes charts, qui contiennent les éléments de texture les plus représentatifs, et permettent de reconstruire l'image complète. L'ensemble des épitomes charts constituent l'épitome.

Nous présentons ensuite les méthodes de l'état de l'art en dé-bruitage, principalement conçues pour le cas du bruit blanc Gaussien additif. Dans un premier temps est décrit le filtre optimal de Wiener, qui opère dans le domaine transformée 2D (Fourier ou ondelettes par exemple). En admettant que le spectre du signal source est connu, le filtre de Wiener donne les coefficients de réduction qui permettent de minimiser l'erreur quadratique moyenne du signal débruité. Ce filtre optimal n'est pas utilisable en pratique, on remplace donc souvent le spectre du signal source par le spectre du signal débruité par une autre méthode [START_REF] Ghael | Improved wavelet denoising via empirical Wiener filtering[END_REF], qualifié ici d'oracle.

La deuxième méthode présentée est le seuillage dans le domaine transformée 2D [START_REF] Donoho | De-noising by soft thresholding[END_REF] [START_REF] Donoho | De-noising by soft-thresholding[END_REF], connue sous le nom de hard thresholding. La technique consiste à annuler dans le domaine transformée les coefficients inférieurs à un certain seuil défini en avance. Le but est d'annuler les coefficients qui ont un faible rapport signal à bruit. Cette méthode peut par exemple être utilisée pour produire un signal débruité qui servira d'oracle pour le filtrage de Wiener.

Nous décrivons alors des méthodes de l'état de l'art particulièrement efficaces, qui s'appuient sur les redondances naturelles des images ou vidéos au travers de techniques multi-patchs. L'algorithme NLM (pour Non Local Mean) [START_REF] Buades | A non-local algorithm for image denoising[END_REF] [START_REF] Buades | A Review of Image Denoising Algorithms, with a New One[END_REF] commence par chercher les K plus proches voisins d'un patch courant à débruiter dans une fenêtre de recherche centrée sur ce patch. Les K plus proches voisins sont alors combinés linéairement pour obtenir une version débruitée du patch courant. Les poids de la combinaison linéaire sont du type w i = e Enfin, l'algorithme BM3D est présenté [START_REF] Dabov | Image Denoising by Sparse 3-D Transform-Domain Collaborative Filtering[END_REF], qui est une des méthodes les plus performantes de l'état de l'art. Dans une première étape, pour chaque patch de l'image à débruiter, ses K plus proches voisins sont trouvés et empilés en un groupe 3D. Le groupe 3D est alors traité en utilisant le seuillage dans le domaine transformée 3D. L'image débruitée obtenue est alors utilisée dans une seconde étape, où les K plus proches voisins de chaque patch sont à nouveau trouvés, ce qui permet de construire de nouveaux groupes 3D. Les groupes 3D sont alors utilisés comme oracle du filtre de Wiener pour traiter les groupes 3D correspondant extraits de l'image bruitée.

La première contribution de ce chapitre est une méthode efficace de génération d'épitome, qui optimise la méthode décrite plus haut, présentée dans [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF]. Cette méthode s'appuie sur des listes d'appariements intermédiaires ou du partitionnement ad hoc des blocs de l'image afin d'accélérer et d'alléger l'étape de recherche des auto-similarités, qui était effectuée jusqu'à présent avec une recherche exacte de tous les appariements.

Nous proposons ensuite un schéma d'amélioration des codecs modernes, qui se situe en dehors de la boucle de codage. Ce schéma consiste à générer coté encodeur des épitomes de la séquence source, afin de les transmettre avec une bonne qualité au décodeur. Ils sont alors utilisés pour débruiter la séquence complète encodée avec une qualité inférieure. Plusieurs cas d'application sont possibles pour ce schéma. Le premier consiste à améliorer un schéma de compression mono-couche. Un seul épitome est alors transmis pour un groupe d'images, afin de limiter le surcoût en débit. La seconde application s'intègre dans un schéma scalable, où un épitome est transmis pour chaque image de la séquence, l'ensemble des épitomes étant considéré comme une couche d'amélioration. Pour chaque image, les patchs contenus dans l'épitome sont alors utilisés pour débruiter les patchs de l'image en dehors de l'épitome. Dans le cas où la couche de base est souséchantillonnée, les méthodes proposées réalisent conjointement la super-résolution et le débruitage des patchs en dehors des épitomes.

Nous décrivons plusieurs méthodes de débruitage basées épitome, qui commencent toutes par rechercher K patchs proches du patch à débruiter parmi les patchs bruités colocalisés avec des épitomes charts. La première technique est inspirée de l'algorithme NLM et des méthodes LLE présentées dans le chapitre précédent. Elle consiste à calculer des poids pour chacun des K patchs, soit de manière similaire à NLM, soit en utilisant une approximation LLE. Les K patchs de bonne qualité correspondants situés dans les épitomes charts sont alors combinés en utilisant ces poids afin d'obtenir le patch débruité.

La seconde méthode est une adaptation du BM3D. Un premier groupe 3D est constitué dans lequel sont empilés les K patchs bruités, ainsi qu'un second groupe qui contient les K patchs de bonne qualité correspondants. En s'appuyant sur ce deuxième groupe 3D, on peut déterminer un seuil optimal pour le seuillage dans le domaine transformée du premier groupe 3D bruité. De la même manière, des coefficients optimaux du filtre de Wiener peuvent être obtenus.

Enfin, un troisième procédé est décrit, qui calcule par régression une projection linéaire entre les K patchs bruités et leurs correspondants de bonne qualité situés dans les épitomes charts. La projection est ensuite appliquée au patch courant pour obtenir une version débruitée.

Les résultats montrent qu'il est difficile d'améliorer un codec mono-couche, ici HEVC, en utilisant le schéma proposé, car les coûts en débit des épitomes s'avèrent trop importants comparés aux gains de débruitage. En revanche, les performances de codage dans le cadre d'un schéma scalable sont meilleures que SHVC, l'extension scalable de HEVC, dans les deux cas testés. Dans le premier cas la couche de base est de la même résolution spatiale que la couche d'amélioration mais de qualité plus faible. Dans le second cas la couche de base est sous-échantillonnée avec un facteur 2x2 par rapport à la couche d'amélioration.

Chapitre 4 : techniques de réduction du bruit de quantification basées sur des clusters

Le chapitre commence par une description des méthodes existantes pour le partitionnement de données (clustering), ce qui est dans ce chapitre le pendant de l'épitome dans le chapitre précédent. Le schéma décrit ci-dessous s'appuie principalement sur la méthode des K-moyennes [START_REF] Macqueen | Some Methods for classification and Analysis of Multivariate Observations[END_REF]. En considérant que le nombre de partitions K est connu, l'algorithme des K-moyennes assigne un point de l'espace à partitionner à la partition qui a la moyenne la plus proche. Une procédure itérative est décrite pour résoudre ce problème. Une revue non exhaustive de l'état de l'art en classification est ensuite faite. Nous présentons notamment les machines à vecteurs supports (SVM) [START_REF] Cortes | Support-vector networks[END_REF] [START_REF] Boser | A training algorithm for optimal margin classifiers[END_REF] et les arbres de décisions [START_REF] Breiman | [END_REF] [START_REF] Breiman | Bagging predictors[END_REF]. Nous nous attachons principalement à décrire les modèles des classifieurs, sans rentrer dans le détail des algorithmes utilisés pour obtenir ces modèles.

Nous proposons dans ce chapitre un schéma d'amélioration en dehors de la boucle de codage comparable à celui proposé dans le chapitre précédent. Toutefois, nous adoptons ici un point de vue différent, car nous effectuons coté encodeur un partitionnement des blocs de l'image, et apprenons toujours coté encodeur une projection linéaire entre les patchs décodés et les patchs sources de chaque partition. C'est le résultat de cet apprentissage, les matrices de projections, qui est alors transmis au décodeur. Coté décodeur, on effectuera le même partitionnement qu'à l'encodeur, et on pourra alors appliquer les projections linéaires aux patchs des partitions correspondantes pour les débruiter. Nous espérons ainsi diminuer le surcoût en débit par rapport à la transmission des épitomes, tout en ayant de bonnes performances de débruitage, car l'apprentissage est réalisé par rapport au signal source.

Le partitionnement est effectué sur les blocs de la vidéo codée/décodée avec la méthode des K-moyennes, de manière à produire exactement les mêmes partitions à l'encodeur comme au décodeur. Le choix du nombre de partitions K devient essentiel, car il permet de réguler l'équilibre débit/distorsion du schéma d'amélioration. Nous proposons donc une procédure basée sur un partitionnement en arbre binaire avec un critère de décision RDO pour trouver de manière adaptative la valeur optimale de K. La structure de l'arbre binaire doit alors être transmise au décodeur, pour un surcoût en débit négligeable.

Les projections linéaires apprises pour ces partitions sont obtenues sous forme de matrices, qu'il faut alors transmettre au décodeur. Nous décrivons alors une méthode pour encoder ces matrices, en les considérant comme les images d'une séquence vidéo. Nous pouvons alors les compresser avec un codec tel que HEVC, en étant attentif à ne pas trop réduire la profondeur de bits des matrices, qui contiennent originellement des valeurs flottantes, afin de ne pas dégrader les performances de débruitage.

Nous proposons également une variante en deux étapes, où un premier algorithme de débruitage "aveugle" (dans le sens ou il ne requiert pas de transmission d'information au décodeur) est appliqué sur la vidéo, avant d'appliquer le schéma décrit ci-dessus.

Les expérimentations montrent que le schéma proposé permet d'améliorer les performances de HEVC, notamment dans sa variante en deux étapes.

Nous présentons ensuite une procédure de partitionnement optimale pour notre application de débruitage. Les résultats obtenus permettent de définir une borne supérieur pour les performances du schéma proposé, qui montrent que des progrès peuvent encore être accomplis. Toutefois, cette méthode de partitionnement ne peut être utilisée directement dans le schéma d'amélioration. En effet le partitionnement obtenu n'est pas causale, c'est à dire qu'il ne peut être reproduit indépendamment au décodeur. Si on envisage alors de transmettre directement pour chaque patch un index indiquant la partition à laquelle il appartient, les performances de codage sont en dessous des performances de HEVC.

Le schéma d'amélioration proposé est ensuite intégré dans un schéma de compression scalable. La méthode d'apprentissage par partition est appliquée pour superrésoudre la couche de base, qui peut ensuite être utilisée pour la prédiction de la couche d'amélioration. Les résultats obtenus avec la méthode des K-moyennes dans SHVC montrent que si la super-résolution de la couche de base est bien plus efficace que le filtre de sur-échantillonnage de SHVC, les gains obtenus ne sont pas reportés sur la couche d'amélioration. L'utilisation de la procédure de partitionnement optimal permet toutefois de montrer que des progrès sont possibles, et que des gains suffisant sur la couche de base peuvent se répercuter sur la couche d'amélioration.

Enfin nous terminons ce chapitre en ouvrant sur un schéma basé classification, qui remplace alors le partitionnement. Le but est d'obtenir un compromis entre les performances du partitionnement des K-moyennes et optimal. Dans ce schéma, le partitionnement optimal est calculé coté encodeur. Un classifieur est alors appris, qui permet d'estimer la valeur de la partition optimale d'un patch à partir de la valeur de ses pixels décodées, ou d'autres caractéristiques associées au patch, telles que son mode de codage ou son débit associé. Le classifieur peut alors être transmis au décodeur, afin de retrouver, au moins partiellement, le partitionnement optimal. Une autre alternative est de transmettre au décodeur une partie des indexes du partitionnement optimal, et d'entraîner le classifieur coté décodeur où il peut être utilisé pour estimer le partitionnement des patchs pour lesquels les indexes optimaux sont inconnus.

Des expérimentations ont étés réalisées avec un schéma de codage simplifié basé sur le codec JPEG. Le schéma basé classification n'apparaît pas efficace appliqué dans un schéma mono-couche, il permet en revanche d'obtenir de meilleures performances que la méthode des K-moyennes dans un contexte scalable avec super-résolution.

Conclusion

Nous avons exploré dans cette thèse des méthodes originales ayant pour but d'améliorer les techniques existantes de compression vidéo. Un des principes de base de la compression vidéo est de réduire les redondances spatiales et temporelles du signal vidéo. Les standards de compression exploitent ce principe à travers les outils de prédictions Intra et Inter respectivement, qui sont décrits dans le Chapitre 1. La prédiction Inter s'appuie sur l'estimation/compensation de mouvement, tandis que la prédiction Intra propage l'information des pixels voisins reconstruits. Le but des travaux proposés dans ce manuscrit est d'améliorer les schémas de compression existants en exploitant d'avantage les auto-similarités intrinsèques au signal, notamment en s'appuyant sur des méthodes multi-patchs.

Dans un premier temps, nous avons cherché à améliorer les outils de prédiction des standards, en utilisant des méthodes multi-patchs basées LLE. Ces méthodes sont présentées dans le Chapitre 2, et nous prouvons leur efficacité en les implémentant dans H.264. Le principe reste toutefois valide dans HEVC. Nous montrons notamment que la combinaison des méthodes proposées pour la prédiction Inter et Intra donne les meilleures performances.

Nous nous sommes ensuite intéressés dans le Chapitre 3 à des méthodes de débruitage basées sur des épitomes, pour améliorer la qualité des vidéos décodées en post-traitement. Un épitome est une version condensée d'une image ou vidéo, contenant l'essence de ses propriétés de texture, que nous transmettons au décodeur en plus de la séquence complète, mais avec une qualité supérieure. Nous pouvons alors utiliser coté décodeur des méthodes de débruitage multi-patchs s'appuyant sur les patchs de bonne qualité contenus dans les épitomes. Nous montrons que les techniques proposées sont efficaces en comparaison du schéma scalable SHVC.

Enfin nous proposons dans le Chapitre 4 un autre schéma d'amélioration s'appuyant sur des méthodes de débruitage basée sur le partitionnement des patchs de la séquence. Ce partitionnement est effectué symétriquement à l'encodeur et au décodeur. Pour chaque partition nous apprenons coté encodeur une projection linéaire entre les patchs sources et les patchs codés/décodés. Ces projections sont transmises au décodeur, où elles peuvent être appliquées pour débruiter les patchs décodés. Une méthode de partitionnement optimale est également proposée, qui permet de définir une limite théorique supérieure pour les performances, et montre que des améliorations sont encore possibles. Le schéma d'amélioration est également intégré dans un schéma scalable avec super-résolution, et nous montrons une potentielle amélioration par rapport à SHVC en utilisant le partitionnement idéale. Enfin nous terminons en proposant un schéma original basé sur des méthodes de classification qui permet d'exploiter au moins de manière partielle le partitionnement optimal.

Ainsi, dans cette thèse, nous nous sommes attachés à exploiter les redondances naturelles d'un signal vidéo pour améliorer les performances de compression. Nous nous sommes basés pour cela sur des méthodes multi-patchs, intégrées dans un premier temps dans la boucle de codage. Nous avons ensuite proposé des schémas d'amélioration en dehors de la boucle de codage, en se basant sur des techniques exploitant les autosimilarités d'une séquence, tels que les épitomes, le partitionnement de données, le débruitage, ou la super-résolution. Nous montrons l'efficacité de ces méthodes originales pour diverses applications, soit des schémas de compression simple couche, soit des schémas scalables. De plus, nous pensons que nos méthodes peuvent être étendues à des applications supplémentaires, tels que la compression de vidéos à dynamique étendue, ou la compression dans le cloud.

Introduction

Context

We are nowadays more and more greedy for video content, and at the same time more and more demanding of a high quality of experience, both in terms of speed and visual quality. Video content providers such as Youtube or Netflix are emblematic of this growing trend. Despite Moore's law and the subsequent increasing processing power, the increasing stocking capacities and modern efficient network infrastructures, transmitting over a network or storing video content at the desired speed and quality still requires compression. To further improve the user immersion, digital videos can now be produced with high resolution (4K -8K), wide color gamut, high dynamic range, or high frame rate. These emerging formats represent a formidable volume of data, and call for very efficient compression. In a white paper published in 2014, Cisco predicted that by 2018, the Internet video traffic will be 79% of all consumer Internet traffic. Furthermore, 80% to 90% of the global consumer traffic is expected to be videos of all forms (TV, Internet, VOD, VoIP, P2P). We can see that efficient compression services are critical, and will still be in a close future. From this perspective, the MPEG standard HEVC is currently one of the most efficient video compression scheme, and is expected to gradually replace its predecessor H.264.

The main principles of modern video compression standards reside in the reduction of spatial and temporal redundancies, through prediction tools, the use of a transform to further reduce the inner correlations of the signal, followed by quantization to remove non-perceptive information, and entropy coding to remove the remaining statistical redundancies. In lossless compression, which aims at perfectly reconstructing the input signal, the quantization step is not performed. This type of compression is especially useful in medical imaging, where the image quality is crucial for efficient diagnosis. The work presented in this thesis deals with the broader scope of lossy compression, which is used in particular in consummer applications, such as the ones cited above. In this case, the quantization step act as a regulation parameter to balance the bit-rate and the visual quality.

To face the multiplicity of possible receivers (TV, computer, mobile devices), which requires transmitting the same video content with different visual qualities, spatial resolutions, frame rates, or bit-depths, scalable video compression schemes are used. To optimize the compression performances, the redundancies occurring across the different versions of the content should be taken into account. Thus, instead of encoding them separately, one version is first encoded as a base layer. Another version, usually of better quality, and/or higher spatial/temporal resolution, and/or bit-depth, is then encoded as an enhancement layer, using the base layer as prediction. Several enhancement layer can then be recursively encoded, to account for all the different versions of the video.

Motivations

The recent MPEG standard HEVC [START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF] is undeniably one of the most efficient modern codecs, and achieves a bit-rate reduction of about 50% [START_REF] Ohm | Comparison of the coding efficiency of video coding standards-including high efficiency video coding (HEVC)[END_REF] compared to its predecessor H.264 [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF]. However, the development and standardization process from H.264 to HEVC took about 10 years. Such pace is too slow to keep up with the projections of video traffic mentioned above.

In addition to the MPEG standards, many actors are now developing new codecs to address this issue. For example, Google's VP9 [START_REF]VP9 Video Codec Summary[END_REF] is already competitive with HEVC, and rely on software optimization to speed-up its development process. Next-generation royalty-free codecs are also announced, e.g. Google's VP10, Cisco's Thor project [START_REF]Thor draft[END_REF], or Daala [START_REF]Daala project[END_REF] (by the Mozilla Foundation and Xiph.org foundation). Despite this renewed interest in video compression, these codecs architectures are still close to the one of HEVC. HEVC itself can be seen as an optimization of H.264, as it primarily relies on the same tools.

As a matter of fact, the main principles of video compression presented above rely on concepts designed more than 30 years ago. The temporal prediction tool, which aims at reducing temporal redundancies, was first presented in 1972 in the form of frame differencing [START_REF] Schroeder | Transform coding of image difference signals[END_REF]. The motion compensation prediction used nowadays was presented in 1981 [START_REF] Jain | Displacement Measurement and Its Application in Interframe Image Coding[END_REF]. The discrete cosinus transform used in many modern codecs was designed in 1974 [START_REF] Ahmed | Discrete Cosine Transform[END_REF], and the first entropy coders date back to 1952 for the variable length coding [START_REF] Huffman | A Method for the Construction of Minimum-Redundancy Codes[END_REF] and 1972 for the arithmetic coding [START_REF] Rissanen | Generalized Kraft Inequality and Arithmetic Coding[END_REF].

These observations call for further improvement of the existing tools mentioned above, or proposals for disruptive techniques. For example, the PROVISION project [START_REF]PROVISION project[END_REF] proposed a change of paradigm in the form of perceptually optimized video compression, based on tools such as texture analysis/synthesis.

Contributions and structure of the thesis

We investigate in this thesis novel methods, which further exploit the natural redundancies occurring in video contents through multi-patches techniques. Note that we focus in this work on improving the compression performances, and thus allow significant complexity increase. Because of the aforementioned increasing processing capabilities, we expect the proposed methods to be acceptable in the future, and the core algorithms could already benefit from parallel implementations, e.g. on GPU.

In Chapter 1, we introduce the main principles used in video compression, and their implementation in the MPEG standards H.264 and HEVC, as well as the scalable extension of HEVC, SHVC.

In Chapter 2, we first present state-of-the-art template matching methods for prediction. The template consists in a set of known neighbor pixels on top and left of the current block of unknown pixels to be predicted. Template matching can then be used to perform motion compensation/estimation, similarly to the classical block matching algorithm. We then propose extensions of the template matching methods to multi-patches methods based on Local Linear Embedding (LLE) to improve temporal prediction. Instead of considering a single block predictor as in the motion estimation/compensation, we search for multiple similar patches, called neighbors, of the current patch (which comprises the block and its template). The known pixels of the template can then be estimated as a linear combination of its neighbors, which weights are computed with the LLE. The same weights can then be applied on the respective adjacent blocks to a obtain the block predictor. Several neighbor search strategies are proposed, and integrated in H.264. However, the concepts still hold in HEVC.

In Chapter 3, state-of-the-art techniques on epitome generation and de-noising are first described. The epitome is defined as a factorized representation of an image or video, containing the essence of its textural properties. Although it has emerged independently from standard compression methods, it is nevertheless closely related to the concept of compression, as it aims at reducing the self-similarities of an image or video. In addition, we observed that multi-patches methods were also proven effective for denoising applications, notably with the Non Local Mean (NLM) and BM3D methods. Thus, we propose epitome-based de-noising methods, where we assume that the epitomes are available at a higher quality than the image or video to be de-noised. When de-noising a patch, we can then search for multiple similar patches in the epitome, and use the higher quality patches to perform efficient de-noising. More specifically, three epitome-based de-noising methods are proposed, first by combining the epitome patches using NLM or LLE weights, second by adapting the BM3D, and finally by computing a linear mapping between the noisy patches and their corresponding high quality epitome patches. The epitome-based de-noising methods are integrated in a proposed out-ofthe-loop framework, where the epitomes are sent to the decoder along with the encoded video, but with a higher quality. The proposed de-noising methods can then be applied at the decoder side to reduce the quantization artifacts. The proposed framework is applied to a single layer scheme as well as scalable schemes.

In Chapter 4, we begin by presenting state-of-the-art clustering methods, which is in this chapter the counterpart of the epitome in the previous chapter, and classification methods. In fact we propose in this chapter an out-of-the-loop framework, with clustering-based de-noising, which is integrated in a compression scheme in order to remove the quantization noise at the decoder side. The method first clusters the coded/decoded patches at the encoder side. Then, linear mappings are learned for each cluster between the coded/decoded patches and the corresponding source patches. The linear mappings are then sent to the decoder, where the same clustering as the encoder side is performed. Finally, the linear mappings are applied to the cluster patches in order to reduce the quantization noise. Since, only the linear mappings are transmitted to the decoder, the rate of the side information is reduced compared to the previous chapter. The proposed framework is also adapted for a scalable scheme. In addition, we propose an optimal clustering algorithm in order to improve the de-noising performances for a same number of cluster. However, this method only set an upper bound on the performances, as it can not be reproduced at the decoder side. We end this chapter by proposing a novel approach based on classification, where classifiers are learned in order to predict the optimal cluster labels. The classifier can for instance be trained at the encoder side and its model sent to the decoder, where it can be used to recover the optimal clusters. Alternatively, a subset of the true optimal clusters labels can be transmitted to the decoder, where the classifier can then be trained. We thus expect to approach the upper bound set by the optimal clustering.

For Chapters 3 and 4, the experiments are performed with HEVC and SHVC, however the out-of-the-loop frameworks can be advantageously adapted to any codec cited above.

Chapter 1

State-of-the-art in video compression

In this chapter, we first present the main principles used in video compression. We then described more in details how these principles are introduced in the video compression standards H.264/AVC and HEVC. Finally, we expose the motivations for the work presented in this thesis.

Main principles in video compression

Prediction

The prediction step aims at removing spatial and/or temporal redundancies. The two types of corresponding prediction are named Intra prediction and Inter prediction respectively. The prediction consists in estimating a block of pixels from previously decoded pixels. In the case of Intra prediction, the block of pixels is predicted from spatially neighboring pixels, while in Inter prediction, it is predicted from previously decoded frames of the video. The prediction process of recent video compression standards will be described in details in the next sections. Once the prediction is obtained, the prediction error, also called prediction residue, is passed on to the transform step.

Transform

The transform reduces the correlations in a signal and compacts the energy in a limited number of coefficients. In a compression scheme, it can be applied directly on pixel blocks, such as in JPEG [START_REF] Wallace | The JPEG still picture compression standard[END_REF] or JPEG2000 [START_REF] Marcellin | An overview of JPEG-2000[END_REF], or on the prediction residue, such as in H.264/AVC [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF] or HEVC [START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF]. The main transformed used in image or video compression schemes include the Discrete Cosinus Transform (DCT) in JPEG, H.264/AVC, HEVC, the Discrete Sinus Transform (DST) in HEVC, and Discrete Wavelet Transforms (DWT) in SPIHT [START_REF] Said | A new, fast, and efficient image codec based on set partitioning in hierarchical trees[END_REF] and JPEG2000.

Quantization

The quantization consists in reducing the signal precision, by mapping the set of input values of size n to a new finite countable set of size m inferior to n. There are several types of quantization, such as uniform and non-uniform, scalar quantization and vector quantization.

In a compression scheme, the quantization is applied on the transform coefficients obtained at the previous step. Compression schemes usually apply scalar quantization, in which a quantization step q is defined and evaluates the level of precision of the quantized signal. Formally, if {y 0 , . . . , y m-1 } represents the set of target values, a signal x is quantized by a quantizer Q as follow:

Q(x) = y i if x ∈ [y i - q 2 , y i + q 2 ] (1.1)
The quantization is not a reversible step, and thus produces lossy compression. In other words, this step is not performed in lossless compression schemes. The quantization step, also called quantization parameter (QP), is used to regulate the bitrate/quality balance. A strong quantization will result in low bit-rates, but also a low quality. On the contrary, little quantization will allow to maintain a high quality, at the cost of a high bit-rate.

Entropy coding

Entropy coding takes advantage of the statistics of a signal to reduce the statistical redundancy. An entropy coder uses the Variable Length Code (VLC) for code-words, such that short binary codes represent the values with the most occurrences, while values with the lowest occurrences are represented with long binary codes. Huffman coding and arithmetic coding are popular entropy coding methods.

In a compression scheme, the entropy coding is applied on the quantized transform coefficients. Recent compression schemes such as H.264/AVC and HEVC use the Con-text Adaptive Binary Arithmetic Coding (CABAC) to encode the quantized transform coefficients, as well as syntax elements.

Standards

We describe in this section the video compression standards H.264/AVC and HEVC. In addition to the overall standard structures, we focus on the main features which are necessary to understand the work of this thesis, such as the prediction process. Other features such as transform, quantization, and additional tools like deblocking filters, are not described.

H.264/Advanced Video Coding (AVC)

The H.264/AVC standard, also known as MPEG-4 Part 10, has been introduced in 2003 as a joint project of the International Standards Organization (ISO) and the International Telecommunications Union (ITU). An overview of the standard is given in [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF].

Hierarchical syntax

A video sequence in H.264/AVC is described by the following hierarchical levels, illustrated in Fig. 1.2:

• The sequence, which comprises global parameters, such as the number of frames, the frame rate, the spatial resolution of the frames, the color format, the bit-depth.

A sequence is made of several groups of pictures.

• The group of pictures (GOP), which contains several successive frames, or pictures, and which structure defines the order and the types of these frames (see section 1.2.1.2). The GOP structure is repeated to form the sequence, and defines a coding period.

• The frame, or picture, which is the sequence unit on the temporal axis.

• The slice, which consists in a group of macroblocks, and represents either a part of a frame of the full frame.

• The Macroblock (MB), which is a luminance pixels block of size 16 × 16, with the associated chrominance pixels blocks. The chrominance blocks size depends on the color format. For example, the chrominance blocks size is 8 × 8 when using the prominent 4:2:0 format.

• The block, which is a sub-partition of a marcoblock, usually consists in a pixel block of size 8 × 8 or 4 × 4. Decisions on the prediction modes of transform can be made at this level to adapt to the local activity of the signal.

Types of frame

Three types of frame can be contained in a GOP:

• The I frame (intra coded frame), which is coded independantly of all other pictures. All its macroblocks and blocks are coded using Intra prediction.

• The P frame (predictive coded frame), which can be temporally predicted from a reference frame. Its macroblocks and blocks can be coded using either Intra or Inter prediction. It can only be predicted from a past I or P frames.

• The B frame (bipredictive coded frame), which can be temporally predicted from two reference frames, usually one past and one future reference frame. This means that the decoding order and the display order can be different, as illustrated in Fig.

Encoder structure

The encoding scheme of H.264/AVC is shown in Fig. 1.4. When encoding a sequence, the frames already encoded are decoded in the loop and stored in a buffer of reference frames to be used for Inter prediction. Inside a frame being encoded, the previously encoded macroblocks are also decoded, and then used for Intra prediction. The maroblocks in a slice or a frame are processed in a raster scan order, from top left to bottom right. Note that in MPEG standards, only the decoder is normative. Although H.264/AVC encoders rely on the structure shown in Fig. 1.4, different encoder designs can be considered, which aim at improving the coding performances, generally under some complexity constraints.

The prediction modes are described more in details in the following sections. In order to signal the best Intra mode to the decoder, only its difference with a mode predictor is sent. The mode predictor is obtained as the minimum between the Intra index modes of the blocks on top and on the left of the current block.

Inter prediction

In H.264/AVC, Iner prediction consists in a block motion estimation/compensation from a previously decoded frame. The motion estimation finds the displacement of the current block with respect to a reference frame (see Fig. 1.7). Motion estimation is usually performed using a block matching (BM) algorithm, which searches in the reference frame for the block which minimizes a measure of distance with regards to the current block. The measure of distance used is usually the sum of absolute distance (SAD) or the sum of square error (SSE). The motion estimation produces a motion vector which is sent to the decoder, where the motion compensation can be performed. The motion compensation produces the prediction block by copying the pixels from the block pointed by the motion vector in the current block. In H.264/AVC, the motion estimation can be performed at a quarter-pixel accuracy, by up-sampling the reference frames. More precisely, a 6-tap interpolation filter is used to produce half-sample positions, followed by bilinear filtering for quarter-sample positions.

To transmit the motion vector, only its difference with a motion vector predictor is sent. The motion vector predictor is obtained as the median of the motion vectors of the neighboring blocks previously decoded.

Several block sizes are defined for Inter prediction, including rectangular partitions in order to improve the motion estimation flexibility: to the decoded, i.e. no motion vector nor transform residue coefficients. In this mode, the prediction is performed by directly copying the pixels of the block pointed by the motion vector predictor. For P frames, the motion estimation is performed in past reference frames, while B frames can perform the motion estimation in both past and future reference frames. More formally, the past reference frames are stored in a list denoted L0, while the future reference frames are stored in a list L1. Furthermore, a block in a B frame can be predicted using two motion vectors, usually found in the L0 and L1 list respectively. The block predictor is obtained by combining the two compensated blocks. In Fig. 1.9, the blue block represents a bi-predicted block.

Thus, in addition to the 2D motion vector, the reference frame index and the list index must be signaled to the decoder.

Coding mode selection

In H.264/AVC, the selection of the coding modes is not normative, thus its implementation in an encoder is open. The mode selection is usually made by minimizing a cost function. The cost function is generally based on a distortion criterion, or a rate/distortion optimization (RDO) criterion. The latter criterion is the most popular, as it yields the best coding performances, and was for example implemented in the test model of H.264/AVC. In return, it usually requires an increased complexity.

In order to select the best mode among the modes available in Intra and Inter prediction, the RDO criterion aims at minimizing the distortion under a rate constraint, or minimizing the rate under a distortion constraint [START_REF] Sullivan | Rate-distortion optimization for video compression[END_REF] [START_REF] Ortego | Rate-distortion methods for image and video compression[END_REF]. For an input signal X and a mode µ, the criterion is formally defined as:

min µ D(X, µ), s.t. R(X, µ) ≤ R c (1.2)
or:

min µ R(X, µ), s.t. D(X, µ) ≤ D c (1.3)
where D refers to a distortion measure function, R refers to a rate measure function, and D c and R c are the constraint on the distortion and the rate respectively. In practice, the solution to this twofold minimization problem is found by minimizing the following Lagrangian function:

J λ (X, µ) = D(X, µ) + λR(X, µ) (1.4)
where λ is a Lagrangian parameter which allows to balance the two above criteria.

HEVC

HEVC is the latest standard developed by the Joint Collaborative Team on Video Coding (JCT-VC), finalized in January 2013. HEVC is a conceptual generalization of the design of H.264/AVC [START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF], introducing optimizations which allow to reduce about 50% of the bit-rate compared to H.264/AVC for a similar quality [START_REF] Ohm | Comparison of the coding efficiency of video coding standards-including high efficiency video coding (HEVC)[END_REF].

In particular, larger prediction and transform blocks are used, which are more efficient for modern high resolution sequences. A new flexible partitioning for the prediction and transform blocks is also introduced.

Hierarchical syntax

The high level syntax elements, sequence, frame, and slice, are not modified compared to H.264/AVC (see Fig. 1.10). One of the main change of HEVC over H.264/AVC is the replacement of the macroblock concept by the notion of coding tree unit (CTU). In HEVC, a frame is partitioned using a recursive quadtree structure, and new hierarchical levels are defined:

• the Coding Tree Unit (CTU), is the basic processing unit. A slice is thus divided into CTUs. The size of the CTU is defined at the encoder and can be either 16 × 16, 32 × 32 or 64 × 64.

• the Coding Unit (CU), is the coding element into which the CTU is divided. The CU itself can then be recursively divided into four CUs, creating a quatree structure, as shown in Fig. 1.11. The root of the quadtree partitioning is at the CTU level. The size of the CU varies between 64 × 64 and 8 × 8. The Intra or Inter prediction mode decision is made at the CU level.

• the Prediction Unit (PU), contains the information related to the prediction process (e.g. directional mode for Intra prediction or motion vector for Inter prediction). A PU can be recursively partitioned into PUs. The root of a PU partitioning is at the CU level, and the PU size can be from 64 × 64 down to 4 × 4.

• the Transform Unit (TU), is the basic unit for transform and quantization. A TU can be recursively partitioned into TUs, and the root of a TU partitioning is at the CU level. The TU size can be from 32 × 32 down to 4 × 4. The TU partitioning is independent from the PU partitioning, as illustrated in Fig. 1.11, where the PUs are represented with blue lines while the TUs are represented with red dotted lines.

Types of frame

The same types of frame are defined in HEVC as in H.264: I, P and B frames.

Encoder structure

The encoder structure of HEVC is very similar to the one of H.264/AVC, as shown in Fig. 1.12.

Intra prediction

The Intra prediction in HEVC relies on the same principle as the Intra prediction in H.264/AVC. However, the concept is optimized, as 33 directional modes are considered in addition to a DC (averaging of the neighboring pixels) mode and a planar mode (see Fig. 1.13). The Intra prediction is applied on square blocks of size 4 × 4 to 32 × 32. The coding of the best Intra mode in HEVC relies on the concept of most probable mode (MPM). Three MPMs are derived from the Intra prediction modes of the above and left PU. If the current best Intra mode is one of the three MPMs, the index of this MPM is sent to the decoder. Otherwise, the best Intra mode is directly coded using a 5 bits fixed length code.

Inter prediction

The Inter prediction in HEVC is based on motion estimation/compensation. As in H.264/AVC, the motion estimation is usually performed using a BM algorithm (see Fig. 1.7).

Motion vectors can be obtained with a quarter-pixel accuracy. In HEVC, a 8-tap filter is used to produce the half-sample position and a 7-tap filter is used to produce the quarter sample positions.

The main optimization for Inter prediction in HEVC compared to H.264/AVC relates to the prediction of the motion vector, prior to differential encoding. In HEVC, several motion vector predictors (MVP) derived from spatially/temporally neighboring PUs are in competition, and the index of the best one is signaled to the decoder. Three different modes are considered for the derivation of the list of MVP candidates: Inter, Merge, and Merge-Skip. For the Inter mode, the texture residual is coded along with MVP index and the motion vector residual. For the Merge mode, the texture residual is coded along with MVP index, and the motion data are derived from the MVP. For the Merge-Skip mode, no texture residual is coded, only the MVP index is signaled, and the motion data are derived from the MVP.

The Inter prediction is applied on blocks of size 8 × 8 to 64 × 64. In addition to square partitions, asymmetric rectangular partitions are also considered.

As in H.264/AVC, bi-prediction is also allowed for the B frames.

Coding mode selection

As for H.264/AVC, the coding mode selection in HEVC is not normative. However, it is usually based on a RDO criterion, solved in practice by the minimization of the Lagrangian function of Equation 1.4.

SHVC

HEVC has been further extended in a scalable version named SHVC [START_REF] Ye | The Scalable Extensions of HEVC for Ultra-High-Definition Video Delivery[END_REF]. SHVC support different scalability features such as temporal, spatial, SNR, bit-depth, color gamut, and hybrid codec scalability. An example of SHVC decoder is given in Fig. 1.14 for a two-layer scalable system, but SHVC supports up to height layers. The two-layer scalable system consists in a base layer (BL) and an enhancement layer (EL).

The EL codec is a modified version of HEVC, but was designed to minimize the changes in the codec architecture compared to a single layer HEVC. Thus, the reconstructed BL frames are added in the EL reference frames buffer at a specific index, after appropriate inter-layer processing. The inter-layer prediction then consists in performing Inter prediction in this specific reference frame with a zero-motion constraint. Since the inter-layer process relies on the reconstructed BL frames, the BL codec can be considered as a black box, which allows the hybrid codec scalability. In the case where the BL codec is HEVC, a motion field re-sampling is performed in order to predict the EL motion field.

Other tools for inter-layer processing include notably texture re-sampling for spatial scalability. The texture re-sampling is performed using 8-tap filters, which support arbitrary spatial ratios.

The spatial scalability feature refers to the case where the spatial resolution of the EL is greater than the one of the BL. Similarly, the temporal scalability feature refers to the case where the frame rate of the EL is greater than the one of the BL. The SNR scalibility concerns the case where both layer share the same spatial resolution, but the EL is transmitted with a higher quality than the BL, in practice by setting a lower QP for the EL than the BL. The bit-depth scalability indicates that the bit-depth of the EL is higher than the one of the BL. The color gamut scalability specifies that the color formats of the two layers are different. Finally, the hybrid codec scalability allows to encode the EL with SHVC, while the BL is encoded with a different codec, such as H.264.

Chapter 2

Inter prediction methods based on linear embedding for video compression

Video compression schemes achieve data compression by exploiting similarities within frames (i.e., the spatial redundancy), as well as between the target frame and one or several reference frames (i.e., the temporal redundancy). Intra coding techniques are used to reduce the spatial redundancy within each frame separately, whereas Inter coding techniques are used to reduce the temporal redundancy between successive frames of a video sequence.

The block matching (BM) algorithm is a popular technique to perform the motion estimation/compensation used in the standards for Inter prediction. However, alternative technique were introduced to perform motion estimation/compensation, based on a template matching (TM) technique [START_REF] Sugimoto | Inter frame coding with template matching spatio-temporal prediction[END_REF]. The methods exploits the correlation between the current block and a pre-defined set of neighboring pixels, called the template of the current block. Rather than looking for the most correlated block in the reference frames, one looks for the most correlated template. The block which is adjacent to this template is used as a predictor for the current block. The motion compensation is performed using the exact same process, so no motion information needs to be transmitted to the decoder. This technique efficiency has also been demonstrated for Intra prediction [START_REF] Tan | Intra Prediction by Template Matching[END_REF]. The RD performance of this method can be improved by using a weighted combination of multiple predictors. Initially a simple averaging of the predictors was performed [START_REF] Tan | Intra Prediction by Averaged Template Matching Predictors[END_REF][9], but methods using adaptive weights, e.g. using sparse approximation [START_REF] Martin | Sparse representation for image prediction[END_REF] [START_REF] Türkan | Sparse approximation with adaptive dictionary for image prediction[END_REF], were shown to bring significant improvements.

In this chapter, we consider an approximation method called Locally Linear Embedding (LLE), introduced in [START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF] for data dimensionality reduction, which we adapt to the problem of temporal prediction. The LLE technique has already been shown to be very efficient for Intra prediction in [START_REF] Türkan | Image prediction based on neighbor embedding methods[END_REF] [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF]. However, the derivation from Intra to Inter prediction is not trivial, mainly because the proposed techniques are now in competition with the motion estimation/compensation, which is a more efficient prediction tool than the Intra directional modes. The idea is to first search for a representation of the template as a linear combination of K nearest neighbor templates (called K-NN templates) taken from a search window denoted SW. The linear combination coefficients (or weights) are then applied on the blocks adjacent to the K-NN templates to yield the current block predictor. The LLE weights are computed using a least square formulation of the template approximation problem under the constraint that they sum to one.

The K-NN search strategy has a strong impact on the predictor quality. In fact, the TM technique efficiency rely on the hypothesis that the template and its adjacent block are well correlated. First, we proposed a direct derivation of the TM technique, where the K-NN can be found by computing distances between the template of the current block and those of candidate blocks in the reference frames. This method is denoted Template Matching LLE (TM-LLE) and, as for the TM method, no side information (i.e., no motion vector) needs to be sent to the decoder. A variant of this method is introduced where the first neighbor is searched by template matching (as in TM-LLE), but the remaining (K -1)-NN are found by computing a distance between the complete patch formed by the template and adjacent block of the first neighbor and the candidate patches in the search window. The method is denoted Improved Template Matching LLE (ITM-LLE).

Second, to further improve the K-NN search, we introduce a method enforcing the correlation between the templates and their adjacent blocks, but requiring the transmission of side information to the decoder. Thus, we propose a method where the K-NN search is initialized with a block-matching algorithm. This implies that a motion vector is sent to the decoder. We then find the remaining (K -1)-NN as in ITM-LLE. This method is named Block-Matching LLE (BM-LLE).

Finally, we propose an improved variant of the ITM-LLE method, denoted optimized ITM-LLE (oITM-LLE). In this method, we basically obtain L predictors by running L times the ITM-LLE method. The best iteration in a RD sense is retained, and its index is sent to the decoder.

The experiments and their analysis focus on RD performance evaluations of the proposed prediction methods against the standard reference techniques: directional and motion estimated/compensated prediction modes of H.264 and template matching averaging (TM-A). This analysis is carried out using a legacy H.264 implementation, but note that the proposed techniques are still applicable in HEVC, since the Inter prediction tool in HEVC follow the same principles as those used in H.264. Simulation results show that significant RD performance improvements are achieved compared to the reference prediction methods. The performed analysis includes elements of complexity in terms of execution times measured at the encoder. This chapter is organized as follows. Section 2.1 reviews background on prediction methods based on template matching. Section 2.2 describes the proposed LLE-based temporal prediction techniques. Section 2.3 explains how the proposed prediction methods have been used in an H.264 codec. We then give the PSNR-rate performance gains compared to the reference H.264 codec.

Background: Prediction based on Template Matching

In addition to the standard prediction modes presented in the previous chapter, prediction methods based on Template Matching (TM) have been considered, for both Intra [START_REF] Tan | Intra Prediction by Template Matching[END_REF] and Inter [START_REF] Sugimoto | Inter frame coding with template matching spatio-temporal prediction[END_REF] prediction. The TM method is very close to the BM method, although here the template pixels (on the top and to the left of the blocks) are used to find the best match instead of the pixels in the current block to be predicted (see Fig. The union of the template X k and of its adjacent block X u forms the patch X. The underlying basic idea of the algorithm is to take advantage of a supposed correlation between the pixels in the block and those in its template. For Inter prediction, the first step of the algorithm is to look for the nearest neighbor (NN) of the template in a search window defined in one or more reference frames. As for the BM algorithm, the metric used to find the NN can be the sum of absolute difference (SAD) or the sum of square error (SSE). Once the NN X TM k of X k is found, the adjacent block X TM u of this template is used as a predictor for the current block X u . The benefit of this method is that this prediction process can be reproduced at the decoder, hence no side information (motion vector, list index, reference frame index) needs to be sent to the decoder anymore [START_REF] Kamp | Decoder side motion vector derivation for inter frame video coding[END_REF]. Although efficient in terms of bit-rate reduction in the case of homogeneous texture, the method yields low quality predictors in image areas where the block and its template are not well correlated.

The technique has been extensively studied in H.264 [START_REF] Sugimoto | Inter frame coding with template matching spatio-temporal prediction[END_REF][7] [START_REF] Kamp | Decoder side motion vector derivation for inter frame video coding[END_REF], and was considered for Intra prediction in the early stage of HEVC [START_REF] Bossen | Video coding using a simplified block structure and advanced coding techniques[END_REF]. Even though it was not retained for the standard, it was later shown that it can improve the RD performance of HEVC, e.g. when used for Inter bi-prediction in combination with block matching [START_REF] Peng | An interframe prediction technique combining template matching prediction and block-motion compensation for high-efficiency video coding[END_REF].

In order to improve the predictor quality, a so-called template matching averaging (TM-A) method has been proposed in [START_REF] Suzuki | Inter Frame Coding with Template Matching Averaging[END_REF]. In this method, one looks for the K nearest neighbors (K-NN) of the current template and not only the first one. The predictor of the current block X u is then obtained by averaging the K blocks adjacent to the K-NN of the template. This enables to smooth the predictor, which is advantageous most of the time, and computationally reasonable.

Note that different approaches relying on K-NN combination have been explored for Intra or Inter coding, such as sparse representations [START_REF] Martin | Sparse representation for image prediction[END_REF][11] [START_REF] Shen | Motion estimation for video coding based on sparse representation[END_REF], or Nonnegative Matrix Factorization [START_REF] Türkan | Image prediction based on neighbor embedding methods[END_REF] [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF]. However, results in [START_REF] Türkan | Sparse approximation with adaptive dictionary for image prediction[END_REF] show that neighbor embedding techniques such as LLE or NMF outperform sparse representations in terms of RD performances. In [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF], results show that NMF performs slightly better than LLE in terms of RD performance, but complexity for NMF is much higher than LLE, especially at the encoder side. These conclusions motivate the use of the LLE in this chapter, described in the following section. More recently, prediction methods based on weighted template matching have been proposed to improve HEVC Intra RD performances, e.g. in [START_REF] Wige | Sample-based weighted prediction with directional template matching for HEVC lossless coding[END_REF]. The method presented in [START_REF] Wige | Sample-based weighted prediction with directional template matching for HEVC lossless coding[END_REF] demonstrates the efficiency of weighted template matching against HEVC Intra mode. However, this method is optimized to reduce complexity, e.g. by using tabulated exponential weights, while we focus on optimizing the RD performances by using optimal weights in a least square sense.

Inter prediction based on LLE

This section describes the proposed Inter prediction techniques using LLE. LLE-based prediction methods search for the linear combination of K nearest neighbors which best approximates in a least squares sense the template of the current block, under the constraint that the weights of the linear combination sum to one. The block predictor is computed by applying the found weights to the blocks which are adjacent to the K-NN templates. The section below first presents the weights computation, assuming that the K-NN are available. We then describe the proposed K-NN search strategies.

LLE-based predictor computation

The weighting coefficients are computed by formulating the template approximation problem as a least squares problem, under the constraint that the weights sum to one. The found weighting coefficients are applied in the linear combination of the adjacent block pixels in order to compute the block predictor (see Fig. 2

.2). Let A = [ A k

Au ] denote a so-called dictionary represented by a matrix of dimension N × K. The columns of the dictionary A are constructed by stacking the K candidate texture patches found after the K-NN search step. The sub-matrices A k and A u contain the pixel values of the templates and of the blocks respectively. Let X = [ X k Xu ] be the vector composed of the known pixels of the template X k and the unknown pixels of the current block X u .

The LLE-based prediction problem can be re-written as: A is available, a weighting coefficient vector V is learned using the LLE, which approximates the current template X k with the K templates in A k . The current block predictor Xu is obtained by applying the learned weights to the K blocks in A u .

min V X k -A k V 2 2 s.t. m V m = 1 (2.
where V denotes the optimal weighting coefficients vector which is computed as

V = D -1 1 1 T D -1 1 . (2.2)
The term D denotes the local covariance matrix (i.e., in reference to X k ) of the selected K-NN templates stacked in A k , and 1 is the column vector of ones. In practice, instead of an explicit inversion of the matrix D, the linear system of equations DV = 1 is solved, then the weights are rescaled so that they sum to one. The predictor of the current block Xu is then obtained as:

Xu = A u V (2.3)

Template-based K-NN search for LLE-based prediction

This section first describes two LLE-based methods in which the K-NN search is not based on real motion estimation but rather on template matching, and thus does not need to send side information to the decoder. The first K-NN search method simply looks for the K-NN of the current template (see Fig. 2.3). The K patches stacked in the dictionary A thus consist in the K templates found (A k ), along with their adjacent blocks (A u ). The current block can then be predicted as explained in section 2.2.1. This K-NN strategy is as simple as the one of the TM-A method, however it suffers from the same limitations in the sense that the candidate patches found may not lead to the best predictor. This method, referred to as Template Matching LLE (TM-LLE), does not require transmitting extra side information to the decoder which can perform the same K-NN search.

An improved variant of the previous method is to find the first NN of the current template in a first step. Then in a second step, the (K -1)-NN of the previous first patch are found in order to build the complete dictionary A. Note that these (K -1)-NN are now found with respect to the whole patch, which tends to reinforce the correlation between the templates and the blocks (inner correlation of the patch). However, if the first NN found is not well correlated with the current patch, the predictor quality will decrease. This method is referred to as Improved Template Matching LLE (ITM-LLE).

Block-based K-NN search for LLE-based prediction

To better overcome the potential lack of correlation between the blocks and their templates, we propose to use the current block to guide the K-NN search. This implies that additional information needs to be sent to the decoder, so that it can find the exact same K-NN. The following methods use the current block to find the first NN. The K -1 remaining patches are found with respect to the previous NN. To signal the NN to the decoder, a motion vector is transmitted.

The prediction first proceeds by computing the motion vector using a classical block matching algorithm. The best matching block (the first nearest neighbor)

X BM u of the current block X u is found. The patch containing this block X BM = [ X BM k X BM u
] is used as the first patch of the dictionary for the LLE. The second step is to search for the (K -1)-NN [a 1 , ..., a K-1 ] of the patch X BM . The union of these K patches A = X BM , a 1 , ..., a K-1 forms the dictionary (see Fig. 2.4) used for the LLE computation described above by equations (2.1), (2.2) and (2.3). The motion information can then be encoded as in the reference codec (e.g. H.264 or HEVC), which does not increase the corresponding rate cost.

Optimized template-based K-NN search for LLE-based prediction

To further enhance the RD performance, the ITM-LLE method was optimized. First, L nearest neighbors to the template of the current block are found. For each patch c l found by this L-NN search, a dictionary is constructed leading to a set of L dictionaries A 0 , ..., A L-1 . Each dictionary A l is formed by stacking the patch c l and its (K -1) -N N (see Fig . 2.5). Since the patches are found using only the template of the current block, the same set of dictionaries can be found by the decoder. An LLEbased predictor is computed with each dictionary and the dictionary A lopt giving the best RD performances is retained, and its index l opt is signalled to the decoder. The number of dictionaries L is taken as a power of 2, and the index is coded with a fixed length binary code. This method is referred to as optimized ITM-LLE (oITM-LLE).

The different steps of the algorithm are detailed as pseudo-code in Algorithm 1.

Simulations and results

Integration in the MPEG-4 AVC/H.264 coding scheme

The reference and proposed methods presented in sections 2.1 and 2.2 respectively have been tested in a H.264 framework. Note that only the TM-A was considered and not TM, as TMA gives higher performances. The TM-A and the LLE-based prediction methods have been introduced in the coding scheme in competition with the existing H.264 inter and intra prediction modes. This solution was chosen over a simple replacement of the existing motion compensation prediction (MCP) method by an Inter LLE-based method because they are complementary. In fact the MCP method is already quite efficient, e.g. for smooth textures with little or no motion. A typical example is a static background where the Skip mode can be used. Multi-patches methods such as the proposed ones using LLE are better at predicting high frequency pseudo-periodic textures, which are not easy to reconstruct using only one block (as shown in Fig. 2.6).

Algorithm 1 oITM-LLE prediction method

Input: X, K, L Output: current block predictor Xu Determine the L nearest neighbors of the current template X k , i.e the templates c k 0 , ...,

c k L-1 such that d0 ≤ ... ≤ dL-1 with di = ||X k -c k i ||
Retain the L patches associated with the L templates determined in the previous step: ci = [

c k i cu i ], i = 0, . . . , L -1 for l = 0 → l = L -1 do Find K -1 neighbors close to c l , i.e., the patches a l 1 , ..., a l K-1 Set A l = c l , a l 1 , ..., a l K-1 Retrieve A l k = a l k 0 , ..., a l k K-1 and A l u = a l u 0 , ..., a l u K-1 from A l . Note that here c l = [ a l k 0 a l u 0 ]
Solve the constrained least squares problem:

min V l X k -A l k V l 2 2 s.t. m V l m = 1 Get the predictor: Xl u = A l u V l Compute the corresponding RD cost RD l end for Select the optimum lopt = arg min l RD l Set Xu = A l opt u V l opt
The MCP method is used for block partitions going from size 16 × 16 to 8 × 8. Experiments using the H.264 reference software show that further sub-partitioning into 8 × 4, 4 × 8 and 4 × 4 blocks brings little improvement in terms of coding performance, while increasing the complexity. In fact, the signaling cost of the motion information usually becomes prohibitive for such small partitions. The TM-A and our LLE-based prediction methods are applied on 8 × 8 blocks.

The Skip mode is allowed for both P and B frames, as well as the additional bipredictive mode for the B frames. The Inter TM-A or LLE-based method to be tested is introduced in competition with the MCP method for 8 × 8 partitions only, and for both P and B frames. We set the template width to 3 pixels. The choice between the classical MCP method or the additional TM-A or LLE-based method is based on a RDO criterion. The syntax then needs to be modified to send a flag to the decoder indicating which method is selected. The rate is therefore increased by 1 bit for each partition that features an additional Inter prediction method (TM-A or LLE-based). The index l opt of the selected dictionary is also transmitted using a fixed length code when the oITM-LLE method is retained for predicting the current block. Experiments showed that the bit-rate corresponding to the flag for the selected method amounts in average to about two to three percents of the full bit-rate, while the bit-rate of the dictionary index reaches four to five percents. Note that this extra information bit-rate could be further reduced using the CABAC.

The search window for the Inter TM-A or Inter LLE-based prediction methods is defined in the reference frames of the L 0 list for the P frames, of the L 0 and L 1 lists for the B frames, and in the decoded part (causal part) of the current frame for both P and B frames. Note that if an LLE-based prediction method is applied to Intra prediction, the search window is only defined in the causal window. The search window is centered on the position of the current block.

Note that the solution we propose to integrate our method in the H.264 codec is still valid in HEVC. In fact, the prediction tools in HEVC follow the same principles as those used in H.264. Detailed explanations are given in the perspectives (section 2.4).

Experimental conditions

The proposed schemes have been implemented in the latest release of the JM-KTA software [START_REF][END_REF], in order to be compared with the H.264 prediction modes. Simulations have been run using 5 test sequences presenting different characteristics in terms of motion and texture (see Fig. A.1 in annex, section A), and having different resolutions (three CIF sequences and two 1280×720 sequences). The CIF sequences are respectively made of 31 frames extracted from the Foreman sequence (frames 149-179), characterized by fast motion and smooth natural texture, 31 frames extracted from the "Rushes" sequence (frames 597-627) containing high frequency texture and complex motion, and 34 frames extracted from the trailer of the Matrix movie1 (frames 1810-1843). This sequence was chosen because of its fast scene changes, occurring every 2-3 frames. The different scenes contain little motion but cover a wide range of textures. The 1280 × 720 sequences are made of 31 frames extracted from the "City" (frames 230-260) and the "Spincalendar" (frames 500-530) sequences respectively. The urban scene in the "City" sequence contains non-stochastic high frequency textures, with a slow camera motion.

The "Spincalendar" sequence contains different textures following a smooth rotation motion. The modified encoder (see section 2.3.1) has been configured with the Main profile [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF] and the parameters given in Table 2.1. The rate gains are obtained using the Bjontegaard measures [START_REF] Bjontegaard | Calculation of average PSNR differences between RD-curves[END_REF]. The complexity is measured trough the percentage of the tested encoder processing time over the one of the H.264 reference encoder.

Due to different experimental conditions, the given complexity values correspond to averaged estimates with a standard deviation of about 10 %. Note that the main goal of contribution in this chapter is to assess the coding performances of the different methods, and thus we did not focus on an optimized development. For this reason, and although we are aware that TM-based methods increase the decoder complexity, we only give some elements of complexity at the encoder side. The main complexity increase is due to the K-NN search, for which fast methods exist [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF] [START_REF] Barnes | The generalized PatchMatch correspondence algorithm[END_REF], and the LLE weights computation. However, contrary to the encoder side, at the decoder side it only affects the blocks for which the LLE-based prediction method has been selected. As an example, in section 2.3.4 the LLE-based prediction methods account for about 20 % of the selected modes.

In the following section, we first analyze the performances of the proposed methods when used for Inter prediction. The performances are analyzed as a function of the key parameters: the number K of nearest neighbors, the reference frames number and the search window size. We also give the corresponding complexity. Second, the methods are also assessed when used for Intra prediction only or when used for both Intra and Inter prediction.

RD performance analysis & elements of complexity

In this section we discuss the gains in terms of bit-rate reduction of the proposed methods against the H.264 reference, along with the execution times measured at the encoder. The values are averaged over the full panel of test sequences.

Impact of the parameter K

Fig. 2.7 shows how the bit-rate savings for each method vary as a function of the parameter K. Fig. 2.8 shows the corresponding complexity for each method, except the oITM-LLE method, which reaches significantly higher levels (about 5000 to 6000 %). In terms of RD performance, the TM-LLE, ITM-LLE and oITM-LLE methods outperform the TM-A method, which demonstrates the better adaptation of the LLE weights compared to a simple averaging, especially when K increases. In average, the highest bit-rate saving is achieved with the oITM-LLE method, reaching more than 8 %. In Table 2.2, we give, for each method, the K value tuned to obtain a satisfying trade-off between the execution time and the coding gain (from Fig. 2.7 and Fig. 2.8), which are also given. We can see that the TM-LLE and ITM-LLE methods outperform the state-of-the-art methods in terms of RD performances. The TM-LLE method is also competitive in terms of complexity. However, the BM-LLE is only competitive in terms of complexity, but not in terms of coding gains. The oITM-LLE does produce the best results in term of bit-rate reduction, but at a really high cost in terms of execution time. For the aforementioned reasons, the detailed analysis of the BM-LLE and oITM-LLE methods is not pushed further for Inter prediction. We will see however in section 2.3.4 that, when used for Intra prediction, the oITM-LLE method can be efficiently combined with less complex Inter prediction method such as TM-LLE. For the next simulations, K is set to the values presented in Table 2

Impact of the reference frames number

Fig. 2.9 shows how the bit-rate gains for each method vary as a function of the number of reference frames. Fig. 2.10 shows the corresponding complexity. In terms of RD performance, we can see that the proposed methods can outperform the TM-A and the highest bit-rate reduction is achieved with the ITM-LLE method, reaching 6.33 %.

In Table 2.3, the reference frames number is set in order to achieve a satisfying trade-off between complexity and RD performances (from Fig. 2.9 and Fig. 2.10). The corresponding execution times and bit-rate reductions are given. We can see that the TM-LLE method can perform better than the TM-A method in terms of RD performances for a similar complexity. The ITM-LLE can achieve the highest bit-rate reduction, which requires an increased complexity.

Impact of the search window size

Fig. 2.11 shows how the bit-rate reductions for each method vary as a function of the search window range. Fig. 2.12 shows the corresponding complexity. Table 2.4 gives the coding gains and corresponding execution time when the search window range is set to achieve a satisfying trade-off between RD performances and complexity. The number of reference frames is not fixed, and set depending on this range. The search window range is first set to 16, with 4 reference frames, then set to 32, with 4 reference frames, and finally set to 64, with 1 reference frame. The last configuration was chosen with only 1 reference frame in order to limit the complexity. However, the same amount of patches is available for the K-NN search for the last two configurations. We can see that the proposed methods can outperform the TM-A, reaching up to 7.20 % bit-rate savings for the ITM-LLE method. As for the previous results, the highest bit-rate reduction can be achieved by the ITM-LLE method, while the TM-LLE method allows a better trade-off between RD performances and complexity.

Combining Intra and Inter LLE-based prediction methods

In this section, we focus on the integration of both Intra and Inter prediction based on LLE. As in [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF], the LLE-based Intra prediction method uses both TM-LLE and oITM-LLE prediction techniques in competition, integrated in H.264 by replacing two of the eight directional modes. The replaced modes are the least statistically used. The statistics are obtained by first running the original H.264 software without the additional LLE-based prediction methods. The proposed Intra method is allowed for 8 × 8 and 4 × 4 partitions. The method is here denoted Intra TM/oITM-LLE. Note that this method is not only applied to I frames, but also to P and B frames. The method chosen for LLE-based Inter prediction is TM-LLE, since it allows a good trade-off between complexity and coding performances, and is here denoted Inter TM-LLE. First, the RD and complexity performances are assessed, followed by an in-depth analysis of the encoder behavior. For the Intra TM/oITM-LLE method, K is set to 32, the search range is set to 32, and L is set to 8. For the Inter TM-LLE method, K is set to 8, the search range is set to 32, with 1 reference frame. Table 2.5 shows the coding performances achieved with the Inter TM-LLE method alone, the Intra TM/oITM-LLE method alone, and the combination of both methods, against the H.264 reference. Table 2.6 shows the corresponding encoder complexity. The results demonstrate that the LLE-based Inter and Intra prediction methods are complementary, especially when evaluating the coding gains of the proposed methods for each sequence separately. We can see that the combined Inter TM-LLE alone and Intra TM/oITM-LLE methods can achieve up to 15.31 % bit-rate saving. Note that, even with the combined methods, the percentage of extra-information (flag indicating if the LLE-based method is used and the index for the oITM-LLE method) only amounts in average to two to three percents of the complete bit-rate. Fig. 2.13 shows the coding performances, averaged over all sequences, of the combined methods as a function of the frame type. For I frames, only the Intra TM/oITM-LLE method is used, and the bit-rate saving reaches 5.92 %. For the P and B frames, the bit-rate saving reaches 7.20 % and 9.27 % respectively, which shows the gain brought by the LLE-based Inter prediction. Fig. 2.14 shows the mode distribution, averaged over all sequences, as a function of the frame type. For I frames, the Intra TM/oITM-LLE method only accounts for 12.11 % of the selected modes. Paradoxically, this little amount of selection shows the method efficiency, since it still brings a significant bit-rate reduction. For the P frames, the combined LLE-based methods account for 25.98 % of the selected modes, which is more than the MCP mode (16.39 %) and the Skip mode (25.25 %). For the B frames, the combined LLE-based methods account for 19.42 % of the selected modes, which is more than the MCP mode (6.79 %), but less than the Skip mode (58.11 %). Although it is less selected than for the P frames, the combined LLE-based methods coding gains for the B frames are still significant (as shown in Fig. 2.13), since it is accumulated over more frames. Thus, we can see that the combined LLE-based methods amount for a significant part of the selected modes for the temporal frames. Fig. 2.15 shows the mode distribution for all frames, averaged over all sequences, as a function of the quantization parameter. The results show that the mode distribution strongly varies depending on the bit-rate. The Inter TM-LLE method is much more selected at high bit-rates (QP-I 22), while at low bit-rates (QP-I 37), the Skip mode is the most selected mode. As explained in section 2.3.1, the LLE-based methods are mainly effective for high-frequency pseudo-periodic textures, which are well preserved at high bit-rates, but on the contrary over-smoothed at low bit-rates, which tends to favor the skip mode. Moreover, we can see that the Inter TM-LLE is more selected than the classical MCP for all bit-rates, and in proportion much more selected than the MCP at low bit-rates. These results confirm the better efficiency of the proposed multi-patches method for reconstructing high-frequency textures compared to the single block MCP.

The City sequence is a good example to illustrate this kind of behavior. The RD curves of H.264 and the combined LLE-based methods for this sequence are displayed in Fig. 2.16, and clearly show that the RD performances of the combined LLE-based methods are better at high bit-rates.

Conclusion and perspectives

In this chapter, we have introduced new Inter prediction methods for video compression based on LLE. The proposed methods rely on the same multi-patches combination with different K-NN search strategies which are aided or not by motion information. It is shown that the methods that are not aided by the motion information give the best coding performances. This shows that our approach is an interesting alternative mode, complementary to current video compression techniques. The different methods can significantly improve the coding efficiency compared to the H.264 reference software, and the best methods outperform the state-of-the-art TM-A.

Through different experiments, we showed that the proposed methods are not extremely sensitive to the key parameters in terms of RD performances. However, the tuning of these parameters can be used to reduce the complexity. The oITM-LLE method reaches the highest bit-rate reduction, which requires in return a high computation time. Nevertheless, when applying the oITM-LLE method to Intra prediction, and combined with a less complex method such as TM-LLE for Inter prediction, we showed that significant bit-rate saving can be obtained for a reasonable complexity cost.

Furthermore, the complexity essentially comes from the K-NN search for which efficient and fast methods exist [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF][15], as well as hardware acceleration modules. In particular, matching methods based on hash functions have been recently introduced to perform efficient NN search [START_REF] Zhu | 2-D Dictionary Based Video Coding for Screen Contents[END_REF] [START_REF] Cherian | Efficient Nearest Neighbors via Robust Sparse Hashing[END_REF], and have been used to improve HEVC for screen content coding. This process is also highly parallelizable and much reduced execution times can therefore be expected, e.g. using GPU implementation [START_REF] Garcia | Fast k nearest neighbor search using GPU[END_REF]. The study instead focused on the assessment of the coding performances and not on the development of an optimized paralellized implementation. Note that such optimized implementation could also allow to refine the K-NN search to sub-pel level, so LLE-based methods could potentially be combined with up-sampling filters.

In addition, we believe that our results would still hold in HEVC. In fact, the prediction tools in HEVC follow the same principle as those used in H.264: directional propagation modes for Intra prediction and motion estimation/compensation for Inter prediction. Our results show that the proposed methods are complementary with the standard tools, and improve the RD performance. Template-based prediction methods were extensively studied in H.264, and recent work shows that they can be effectively used in HEVC [START_REF] Peng | An interframe prediction technique combining template matching prediction and block-motion compensation for high-efficiency video coding[END_REF] [START_REF] Wige | Sample-based weighted prediction with directional template matching for HEVC lossless coding[END_REF]. We expect our methods to outperform these techniques, as they yield a better prediction quality. The proposed methods are meant to be in competition with the standard Intra and Inter prediction tools, which would require applying them to different PU sizes. In fact, the numerous PU sizes, and especially the larger ones, are known to be an effective tool of HEVC [START_REF] Ohm | Comparison of the coding efficiency of video coding standards-including high efficiency video coding (HEVC)[END_REF]. This adaptation is conceptually straightforward, and can even be extended to rectangular PUs. Furthermore, additional tools providing RD gain, such as adaptive transform sizes, de-blocking filter [START_REF] Ohm | Comparison of the coding efficiency of video coding standards-including high efficiency video coding (HEVC)[END_REF], are directly compatible with the proposed methods. The overhead in the bitstream corresponding to the flag indicating if the LLE-based method is used and the index for the oITM-LLE method is low for H.264, and we do not expect an increase for HEVC, since applying the proposed methods on larger PUs would reduce the number of flags or indexes to be transmitted.

55

Chapter 3

Epitome-based quantization noise removal

In chapter 2, we studied Inter prediction methods based on Locally Linear Embedding (LLE) in order to improve coding performances. Following the work presented in [START_REF] Türkan | Image prediction based on neighbor embedding methods[END_REF][55] [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF] for Intra prediction, we showed that the proposed LLE-based multi-patches methods were an efficient Inter prediction tool. The coding performances are especially improved when the proposed methods are combined for both Intra and Inter prediction, which corroborates the interest of an in-loop implementation of such methods.

Independently from the standard video compression techniques emerged the concept of epitome, first presented in [START_REF] Jojic | Epitomic analysis of appearance and shape[END_REF] [START_REF] Cheung | Video epitomes[END_REF], which is defined as a condensed representation of an image or video containing the essence of its textural properties. An epitome thus consists in a texture epitome, which we denote E, containing texture patches representative of the whole input signal, and a mapping φ which links the texture patches to their original position in the input image/video. Multiple application of the epitomes are presented in [START_REF] Jojic | Epitomic analysis of appearance and shape[END_REF] [START_REF] Cheung | Video epitomes[END_REF], including segmentation, image editing, de-noising, super-resolution and inpainting. The concept of epitome is in addition closely related to image compression, as it relies on the reduction of similarities within an image, and was used in [START_REF] Wang | Improving intra coding in H.264\AVC by image epitome[END_REF] to improve H.264 Intra prediction. Moreover, a new epitome factorization model was presented in [START_REF] Wang | Factoring repeated content within and among images[END_REF], which presents among several applications a direct approach for epitome-based image compression, which merely consists in compressing the texture epitome and the transform map. However, the work of [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] showed that the coding performances of such approach are limited, especially at high bit-rate. Based on the work of [START_REF] Wang | Factoring repeated content within and among images[END_REF], an adapted epitome generation algorithm is proposed in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] for a novel still image compression method, which consists in coding the texture and the transform map along with a reconstruction residue. The method was proven efficient compared to H.264 Intra coding. Furthermore, an improved approach is proposed in [START_REF] Cherigui | Epitome inpainting with in-loop residue coding for image compression[END_REF] 1 which exploits the concept of epitome in combination with the efficient LLE-based multi-patches prediction methods. More precisely, the epitome is first transmitted to the decoder, then the nonepitome blocks are predicted in an inpainting manner from the epitome using LLE-based multi-patches methods, with an in-loop residue coding. Results showed that the method clearly outperforms H.264 Intra coding.

The work presented in this chapter can be seen as an extension of the work of [START_REF] Cherigui | Epitome inpainting with in-loop residue coding for image compression[END_REF] from still image to video compression. However, the approach chosen here is an out-ofthe-loop scheme, where the epitome is transmitted to the decoder with a high quality in addition to the whole encoded sequence, and used at the decoder side to perform multipatches based de-noising on the non-epitome blocks, instead of in-loop prediction. The proposed approach thus gains in genericity, as it can be applied to any existing coding scheme.

This chapter is organized as follow. Section 3.1 reviews background on epitomic models and de-noising. Section 3.2 presents a method for efficient epitome generation. Section 3.3 describes the proposed quantization noise removal out-of-the-loop scheme for video compression. Given an epitome E and the input image I, a mapping φ can be derived, which links patches from the epitome to their position in the original image (see Fig. 3.1). If the mapping and the epitome are given, the original image can thus be reconstructed. However, the main applications of this approach have been for image analysis such as segmentation, de-noising, recognition, indexing or texture synthesis. The epitome is computed from an image through Maximum Likelihood Estimation (MLE) using an Expectation Maximization (EM) algorithm. The mapping φ is then a hidden variable in the computation process. This patch based probability model was shown to be of high "completeness" in [START_REF] Simakov | Summarizing visual data using bidirectional similarity[END_REF] but introduces undesired visual artifacts, which is defined as a lack of "coherence". In fact, since the model is learned by compiling patches drawn from the input image, patches that were not in the input image can appear in the epitome (see Fig. 3.2). These artifacts can be a drawback for some applications, e.g. intra coding such as in [START_REF] Wang | Improving intra coding in H.264\AVC by image epitome[END_REF] [START_REF] Wang | Intra coding and refresh based on video epitomic analysis[END_REF][60], because they will limit the quality of the prediction. As this chapter mostly deals with epitome dedicated to image coding, this generative model approach will not be discussed in more details in the next sections.

Background

This approach was also extended into a so-called Image-Signature-Dictionary (ISD) optimized for sparse representation [START_REF] Aharon | Sparse and Redundant Modeling of Image Content Using an Image-Signature-Dictionary[END_REF]. The ISD is generated by replacing the probabilistic averaging of patches in the previous approach by their sparse representation. Thus is obtained an image (see Fig. 3.2) that can be used as a dictionary for sparse representations and has several important features such as shift and scale flexibility. For the same reasons as the previous method it will not be considered in the rest of this chapter.

Factoring similar content within an image

Wang et al. introduced in [START_REF] Wang | Factoring repeated content within and among images[END_REF] a new approach to build epitome based on self-similarity tracking within the image. This approach has been designed with in mind (lossy) image reconstruction (and more generally texture mapping) rather than image analysis applications. Thus the epitome obtained by this method is composed of image patches that are not altered.

In this approach, the input image I is factored in an epitome E and a transform map φ (corresponding to the mapping in previous section). The input image is divided into a regular grid of blocks and each block will be reconstructed from a transformed epitome patch. The epitome itself is composed of disjoint texture pieces called "epitome chart". The transform map contains all the parameters that link the patches from the epitome to the input image blocks. Wang et al. proposed a so called epitome atlas which aim is to compact the different epitome charts to obtain a smaller image.

Ideally, one seek to minimize the size of the epitome and the transform map, |E|+|φ|, as well as the image reconstruction error ||I -I|| 2 . Assuming that the block size is fixed, the transform map size |φ| is fixed as well. The problem can then be expressed as:

min E,φ |E| such that ∀B ∈ I, e(B) ≤ ε (3.1)
where e(B) represents the reconstruction error of the current block B. This minimization is solved using a greedy construction process that iteratively grows epitome charts copied from the input image. More precisely, the epitome construction procedure has the following steps:

• Find self-similarities for each block B i in I.

• Create an epitome chart EC for each repeated content, to satisfy a maximum norm on the image reconstruction error (see Eq. 3.1).

• Optimize the transform map φ, to minimize the reconstruction error given the epitome content.

• Assemble all epitome charts EC into an epitome atlas (optional).

We describe below the first two steps of the procedure.

Finding self-similarities. The first step is performed using the Kanade-Lucas-Tomasi (KLT) feature tracker [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF][64] that optimizes affine alignment of two windows. Thus for each block B i ∈ I a set of matched patches (also called matchings) M atch(B i ) = {M i,0 , M i,1 , ...} is obtained, which is found through the different transformations considered by the KLT algorithm: translation, rotation and scaling (see Fig. 3.3). In this approach mirror reflections were also considered. To be a viable matching the error between the current block B i and the candidate patch must be inferior to a threshold ε M .

Epitome chart extension. To extend an epitome chart EC one considers all the matchings overlapping a block B j included in EC. For the initialization all the block of the image are considered and not only the blocks in the current epitome chart. The region ∆EC encompassing said matchings is considered as a candidate for the extension of EC (see Fig. 3.4). The actual extent is the candidate that can reconstruct the largest region. The epitome chart growth stops when the regions reconstructed by the extent candidates ∆EC are smaller than the extent candidate itself. The process stops when the entire image is reconstructed.

Once the epitome is obtained the quality of the reconstruction image can be improved by finding potential better matching in the epitome for each block.

At this point the epitome itself is still the same size as the input image, but is filled with "empty" pixels outside the epitome chart. The authors proposed a method

Epitome dedicated to image coding

In this section, we introduce an approach first presented in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF]. The method is inspired by the previous one, but only relies on a translational model to find self-similarities, with in mind image coding applications.

Finding self-similarities. The first step of the epitome construction consists in searching, for each block in the input image, the set of patches in the image with similar content. That is, for each block B i , belonging to the block-grid, we determine the list of matchings M L(B i ) = {M i,0 , M i,1 , ...} that reconstructs B i with a given error tolerance ε M (see Fig. 3.6). The procedure of matching is performed with a block matching algorithm using an average Euclidian distance. Compared to previous method, the only transformation allowed is translation. Note that an exhaustive search is performed in the entire image. Once all the Match lists have been created for the set of image blocks in block-grid, a new list RL(M j,k ) = {B j , B l , ...} will be built indicating the set of image blocks that could be represented by a matching block M j,k . This list is used in the second step. Note that all the matching blocks M j,k found during the full search step belong to the pixel grid. Furthermore the matching search can be extended to a sub-pixel grid.

Epitome chart extension.

Here, the second step that consists in building the epitome charts differs from the previous approach. Each chart EC is initialized by the matched patch which is the most representative in the input image and whose reconstructed image blocks are not represented yet by the epitome. Formally the initialization is based on a Mean Squared Error (MSE) criterion between the original image I and the reconstructed image I , where the non reconstructed pixels of I are set to 0. where W and H are the width and the height of the image respectively, M is the set of all available matchings and E is the set of matchings that constitute the current epitome.

EC init = arg min M ( W i H j ||I i,j -I i,j || 2 W * H ) for M ∈ M\E (3.
Once initialized the epitome chart EC is extended by considering a set of candidate extension regions ∆EC m , m = 0, ..., N -1 where N is the number of candidates. The candidates considered are the matchings overlapping with the current epitome chart. The actual extension ∆EC opt should minimize the MSE between I and I . Furthermore, in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] is introduced an optimization taking into account so-called inferred blocks. The inferred blocks are the potential matchings that can overlap the current chart EC and the extension ∆EC m (see Fig. 3.7) and thus help reconstruct new blocks in I . The criterion also takes into account the extension size so that the epitome chart growth is limited. Formally the selection is conducting according to the minimization of the following Lagrangian criterion:

∆EC opt = arg min ∆ECm ( W i H j ||I i,j -I i,j || 2 W * H +λ × |EC + ∆EC m | W * H ) (3.3)
where |EC +∆EC m | represents the size of the epitome chart and its extension evaluated by the number of pixels. Note that the criterion of Eq. 3.2 is very similar but does not need the second term because all candidates have the same size. Finally the extension stops when no more matchings overlapping with the current epitome chart can be found. The global process stops when the whole image is reconstructed.

Thus is obtained the epitome E and a so-called assignation map φ (corresponding to the previous transform map), which is actually a subset of the lists RL. The epitome charts in E are originally obtained at a pixel accuracy. In order to encode the epitome efficiently, it has to be padded so it suits the block structure of the encoder used. Thus in [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF], E was padded to a 8x8 block grid to be later encoded with a H.264 encoder. The padding process adds blocks and inferred blocks in the epitome that can then be used to improve the assignation map. In [START_REF] Cherigui | Epitome-based image compression using translational sub-pel mapping[END_REF] were also conducted experiments where the matchings were found at sub-pixel accuracy, which lead to better coding performances at the price of an increased complexity.

In Fig. 3.8, we give an example of epitome obtained with this method on the Calendar image, with a threshold ε = 10.0.

De-noising

De-noising is the task of recovering an estimate of a source signal from a noisy version of this signal. Image de-noising has been a very active research topic, and we present in this section several methods among the most popular and best performing. These methods assume that the source image is corrupted with additive white Gaussian noise (AWGN). We note Y the noisy version of the source image X. For all the pixels y i and x i in Y and X respectively, we have the following relation:

y i = x i + n i (3.4)
where n i is a zero-mean Gaussian variables with variances σ 2 n . In the remaining of this section, we will note y and x patches extracted from the noisy image and the source image respectively.

More sophisticated noise models than AWGN have been proposed, such as the signaldependent noise model [START_REF] Kuan | Adaptive Noise Smoothing Filter for Images with Signal-Dependent Noise[END_REF], for which the pixels y i and x i have the following relation:

y i = x i + x γ i • u i + w i (3.5)
where γ is the exponential parameter which controls the dependence on the signal, and u and w are zero-mean Gaussian variables with variances σ 2 u and σ 2 w respectively. However, the main approaches to remove such noise rely on the assumption that the noisy image can be partitioned into segments or clusters for which the noise can be modeled by AWGN, such as in [START_REF] Liu | Automatic estimation and removal of noise from a single image[END_REF] [START_REF] Liu | Signal dependent noise removal from a single image[END_REF]. The approach thus consists in segmenting/clustering the noisy image, estimate the noise level in each segment/cluster, and finally apply a known de-noising method for AWGN on each cluster. Thus, in the next sections, we only present methods assuming AWGN.

We note that many recent successful de-noising methods relying on sparse representations have been proposed [START_REF] Elad | Image denoising via sparse and redundant representation over learned dictionaries[END_REF][69] [START_REF] Sulam | Image denoising through multi-scale learnt dictionaries[END_REF]. Efficient techniques relying on the local learning of dictionaries through clustering were also proposed [START_REF] Chatterjee | Clustering-based denoising with locally learned dictionaries[END_REF] [START_REF] Dong | Sparsity-based image denoising via dictionary learning and structural clustering[END_REF]. However, it was shown that these methods are usually outperformed by the BM3D algorithm [START_REF] Chatterjee | Is denoising dead?[END_REF]. Thus, we choose not to describe these methods in details, and focus instead on the BM3D algorithm, which is later use for comparison in the contributions of this chapter.

Optimal Wiener filter

The optimal Wiener filter for image de-noising proceeds by shrinking coefficients in a transform domain. We note T the transform, e.g. a discrete Fourier transform (DFT), a discrete cosinus transform (DCT) or a discrete wavelet transform (DWT).

The Wiener filter coefficients in the transform domain are expressed as follow:

W = |T (x)| 2 |T (x)| 2 + σ 2 n (3.6)
The de-noised estimate x of the patch x is obtained from the noisy patch y by applying the filter to the transform coefficients of y and inverse transform the result:

x = T -1 (W • T (y)) (3.7)
where • represents the element-by-element multiplication.

The Wiener filter is denoted optimal because its computation relies on the knowledge of the source signal. In practice, the filter can be used by computing a first de-noised estimate of the image, and using as "oracle" in Eq. 3.6, such as in [START_REF] Ghael | Improved wavelet denoising via empirical Wiener filtering[END_REF] or in the BM3D algorithm described below.

Transform domain thresholding

The idea of thresholding coefficients in a transform domain was introduced in [START_REF] Donoho | De-noising by soft thresholding[END_REF], and has been proved to be very efficient since. The method is conceptually similar to the Wiener filter, but instead of applying the shrinkage coefficients, a thresholding operator (which does require any knowledge on the source signal) is applied. In [START_REF] Ghael | Improved wavelet denoising via empirical Wiener filtering[END_REF], the method is used to obtain a first de-noised estimate which is then used as oracle for a Wiener filter.

If we note τ the thresholding operator, the de-noised estimate x of the patch x is obtained from the noisy patch y as:

x = T -1 (τ (T (y))) (3.8)
Two types of operators τ can be used, the soft thresholding as in [START_REF] Donoho | De-noising by soft thresholding[END_REF][26] or the hard thresholding as in [START_REF] Ghael | Improved wavelet denoising via empirical Wiener filtering[END_REF]. We give below the definition of soft and hard thresholding of a coefficient c with threshold λ > 0:

τ sof t (c, λ) = 0, if |c| < λ c -sign(c)λ, otherwise. (3.9)
τ hard (c, λ) = 0, if |c| < λ c, otherwise. (3.10)
The threshold λ is usually determined depending on the noise level σ n , as the rationale behind thresholding in the transform domain is to retain coefficients with a high signal-to-noise ratio.

Non Local Mean

Although the previous methods performing in a transform domain are very efficient, another type of methods chose to perform de-noising directly in the pixel domain, such as the bilateral filtering [START_REF] Tomasi | Bilateral filtering for gray and color images[END_REF]. This method directly estimates a pixel as weighted average of its neighboring pixels. Although a photometric distance is taken into account to compute the weights, this method often results in over smooth estimates.

The Non Local Mean (NLM) algorithm [START_REF] Buades | A non-local algorithm for image denoising[END_REF][28] relies on a similar idea, but instead searches for neighbors of the patch surrounding the pixel to be de-noised in the Euclidean space, and combines the central pixels of the neighbor patches depending on the Euclidean distance between the current patch and its neighbor. The neighbor patches can be spatially located anywhere in the image, hence the "non local" property of the method.

Formally, we note y c the central pixel of the noisy patch y of size N × N . We note K the number of neighbors, and y i , i = 0 . . . K -1 the K nearest neighbors (K-NN) of y. The distance between y and its neighbor y i is noted

d i = ||y-y i || 2 2 N 2 .
Note that y 0 is the patch y itself, as it is its closest neighbor. Originally, all the patches available in the image were considered as neighbors. To limit the complexity, only the patches in a search window around the current patch were then considered. Alternatively, a fixed number K defined by the user can be used.

The de-noised pixel xc is obtained as follow:

xc = K-1 i=0 w i * y c i K-1 i=0 w i (3.11)
The averaging weights are computed as:

w i = e - d 2 i 2σ 2 N LM (3.12)
where the parameter σ N LM act as a degree of filtering, and is set in the original NLM algorithm to σ N LM = 10 * σ n . A patch-wise version of the method can be derived from the pixel-wise NLM by directly combining the K-NN patches:

x = K-1 i=0 w i * y i K-1 i=0 w i (3.13)
The averaging weights are computed exactly as before. In this case, several estimates are obtained for each pixel, which are averaged to obtained the final de-noised version of the pixel.

BM3D

The block-matching 3D (BM3D) algorithm was presented in [START_REF] Dabov | Image Denoising by Sparse 3-D Transform-Domain Collaborative Filtering[END_REF], and is still to this day one of the best performing methods in image de-noising. The method advantageously combines the strengths of the non local approaches and transform domain de-noising, by stacking a patch and its K-NN in a 3D group, and then applying a 3D transform on the 3D group of patches.

In a first step, the 3D transformed group is processed using hard thresholding. In a second step, the first de-noised image estimate obtained at the previous step is used to compute new K-NN and the corresponding 3D transformed group is processed using Wiener filtering. In the Wiener filtering step, the 3D transformed group of the first estimate patches is used as oracle to filter the 3D transform group of the corresponding noisy patches. The 3D transform not only increases the sparsity of the transform compared to a 2D transform (and thus the efficiency of the transform domain processing), but also allows a collaborative filtering, i.e. all the patches of a 3D group are de-noised at once. Several estimates are thus obtained for a pixel, which are finally aggregated to obtain the final estimate.

The two steps of the method are described in detail below. Many notations are needed to formally describe the BM3D algorithm, which are summarized in Table 3.1 for clarity. The method processes overlapping patches of size N × N with a step of s pixels in both horizontal and vertical directions. For each patch, the K-NN search is limited to a search window of size N SW × N SW . In the original algorithm, the distance between the current patch y and one of its retained neighbor y i must not be higher than a pre-defined maximum acceptable distance ε BM :

d i = ||y -y i || 2 2 N 2 ≤ ε BM (3.14)
Thus, K refers to the maximum number of neighbors. To keep the notations tractable, we still using in the description below the term K-NN, although the actual number of neighbors could be inferior to K. Note that these parameters (denoted common parameters in Table 3.1) may vary between the two steps in practice, but we keep below the same notations for clarity purpose. Hard Thresholding In this first step, the K-NN y i , i = 0 . . . K -1 of the patch y are first found. Note that, as for the NLM, the patch y 0 is the patch y itself. The patches are stacked in a 3D group noted G HT y . A 3D transform T HT is applied on this 3D group, which is then processed using hard thresholding. The de-noised group noted G HT x is obtained after applying the inverse 3D transform:

G HT x = T -1 HT (τ (T HT (G HT y ), λ)) (3.15)
where λ is the threshold parameter, usually determined depending on the noise level. Note that all the patches of the group are thus de-noised at once. At the end of this step, several estimates can be thus obtained for a pixel, which are then aggregated to obtain the final estimate.

The hard thresholding step is represented in Fig. 3.9. . This noisy patches group can then be processed by a Wiener filter, using G x as an oracle. The Wiener filter is computed as:

W = |T W ien (G x)| 2 |T W ien (G x)| 2 + σ 2 n (3.16)
The group of de-noised patches can then be obtained as follow:

G W ien x = T -1 W ien (W • T W ien (G W ien y )) (3.17)
As in the previous step, several estimates can be obtained can be obtained for a pixel, and are aggregated to obtain the final estimate.

The Wiener filtering step is represented in Fig. 3.10. Several extensions of the BM3D have been proposed by its authors, e.g. color images de-noising [START_REF] Dabov | Color Image Denoising via Sparse 3D Collaborative Filtering with Grouping Constraint in Luminance-Chrominance Space[END_REF], de-blurring [START_REF] Danielyan | BM3D frames and variational image deblurring[END_REF], or even super-resolution [START_REF] Danielyan | Image and video superresolution via spatially adaptive blockmatching filtering[END_REF]. Applications also include a Video BM3D (VBM3D) algorithm [START_REF] Dabov | Video denoising by sparse 3D transformdomain collaborative filtering[END_REF], in which the K-nearest neighbors of a patch are also searched in the adjacent frames. More precisely, the neighbors are searched in the current frames, N F R past frames, and N F R future frames.

Clustering-based methods for fast epitome generation

In this section, we propose a novel method for fast epitome generation. We build on the approach described in section 3.1.1.3 and propose to improve the self-similarities search step.

In fact, the self-similarities search method described in section 3.1.1.3 ensures that the best matches are found since an exhaustive search is performed. However, this method is known to be expensive in terms of memory consumption and processing time, since each block in the block-grid will be associated to a list that can contain a high number of matches. Different methods have been proposed to reduce the complexity of such nearest neighbor (NN) search. Video codecs such H.264 or HEVC usually integrate approximate BM algorithm. Classical approach to accelerate a NN search is to consider a hierarchical search, where the search is first conducted in sub-sampled version of the input image and the result is used to initialize the next level search. Faster approximate method for NN search based on k-dimensional tree (kd-trees) have been proposed [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF]. State of the art concerning approximate NN (ANN) search optimization have been proposed in [START_REF] Barnes | PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing[END_REF] and generalized for K-NN search in [START_REF] Barnes | The generalized PatchMatch correspondence algorithm[END_REF]. However all these methods are designed to find only a few best NN, i.e. use a relatively small and fixed value for K. The problem we address here is different because the number of NN, K, is not determined in advance and can reach really high values (up to several thousands, depending on ε M ).

We propose to replace the exhaustive match search by an approximate approach that takes advantage of the self-similarities within the blocks in the block-grid. In a first step, "sufficiently similar" blocks are grouped together. In a second step a match list is computed for each group, with respect to a representative block from the group. Note that this self-similarities search method is still compatible with the epitome generation step described in section 3.1.1.3, but here blocks in a same group will use the same match list. This not only accelerates the process since less match lists are computed but also saves memory space.

The similarity between the blocks is assessed using the average sum of absolute difference (SAD). We define a tolerance error ε A that will be used to assign blocks to groups. The assignation threshold ε A should be smaller than the matching threshold ε M . Thus we define ε A via a coefficient α A such as :

ε A = α A * ε M , 0 ≤ α A < 1 (3.18)
Two grouping methods are presented below : first a novel list-based method, second a threshold-based clustering method adapted from [START_REF] Bhatia | Adaptive K-Means Clustering[END_REF]. We are here interested in a clustering method working without any prior information on the cluster number, which makes the use of classical methods such as K-means algorithm uneasy.

Note that the grouping is applied only for blocks in the block-grid.

List-based method for self-similarities search

This method was designed to obtain a simple grouping of similar non-overlapping blocks and follows the steps below:

• For each block B i , find all blocks whose distance is below the assignation threshold ε A . The association of B i and such blocks form a potential list P L(B i ).

• Find the potential list P L opt with the highest cardinal. This potential list is set as an actual list AL. Blocks in AL are removed from the other potential lists they may belong to. If the block B used to compute a potential list P L(B) is removed from this list, this potential list no longer exists and is simply not considered in future iterations.

• The previous step is iterated until all blocks belong to an actual list.

Finally for each actual list AL(B i ) we determine a match list M L(B i ) = {M i,0 , M i,1 , . . .} obtained through an exhaustive search in the pixel-grid. The list is computed with respect to B i but is then used by all blocks in AL(B i ) for the epitome generation step. To satisfy the constraint that all the blocks have a reconstruction error inferior to ε M , the blocks different from B i in the list AL(B i ) only use a subset of M L(B i ) defined as:

{M ∈ M L(B i )|d(B i , M ) ≤ ε M -ε A } (3.19)
This solution avoids computing the distance between blocks and all elements of a match list, which can be time consuming. On one hand, this method tends to favor the creation of a few actual lists with large sizes, which is interesting since less match lists are computed. On the other hand, the blocks B i used to compute the match lists are not necessarily the most representative blocks of the actual lists, which can limit the matches quality for the blocks in the actual list different from B i . The method described in the subsection 3.2.2 addresses this issue.

In the example of Fig. 3.11, the size of AL(B j ) is superior to the one of AL(B i ) or AL(B k ), so B 0 = B j , and B j and its associated blocks form the cluster C 0 . Here A j,4 = A k,0 , but since it belongs to C 0 , it is removed from the list AL(B k ). The next cluster C 1 is thus formed by B i and its associated blocks since it has now more associated blocks than B k .

At the end of the process each block B in the block-grid is linked to a list of matchings M L that can be used to build an epitome, e.g. using the method described in section 3.1.1.3. Contrary to the approach presented in section 3.1.1.3, we do not need to actually compute the list of matchings for each block B, but only for a subset of blocks corresponding to the different clusters. This process thus reduces computing time and memory occupation.

Threshold-based clustering for self-similarities search

This method is derived from the threshold-based clustering algorithm presented in [START_REF] Bhatia | Adaptive K-Means Clustering[END_REF], and proceeds as follow:

• A block B 0 is randomly selected and used to initialize the first cluster C 0 .

• For every block B not assigned to a cluster, compute its distance to the centroid of all existing clusters. If all distances are higher than the assignation threshold ε A , initialize a new cluster with B as a seed. Otherwise assign B to the closest cluster and recompute the centroid of this cluster as the average of all blocks in the cluster.

• As a result, all blocks are assigned to a cluster. For every cluster, recompute the distances between the cluster blocks and the centroid. If a block B is found to have a distance to the centroid superior to ε A , it is considered as a singularity and remove from the cluster. B is then used as a seed to initialize a new cluster.

We thus obtain clusters whose blocks are consistent with each other, and thus for each cluster C i a match list M L(B i ) is computed through an exhaustive search in the pixel-grid, with respect to the block B i closest to the centroid. We choose not to use the centroid itself, as it is computed as the average of all blocks in the cluster, and as result can contain artifacts not suited for the match search. Thus except for the block B i , all blocks in C i will use approximate matches. As for the previous grouping method, we want to ensure that all blocks have a reconstruction error inferior to ε M . The blocks different from B i thus only use a subset of M L(B i ), defined as in Eq. 3.19.

Contrary to the method described in subsection 3.2.1, this method does not favor groups of large sizes and thus may produce more groups. However, the blocks B i are better representative for their groups, which improves the quality of the matches.

Trade-off between complexity and quality

The trade-off between the complexity reduction and the matching approximations is set using the parameter α A . When α A = 0 the self-similarities search is performed for each block as in section 3.1.1.3 and the complexity is not reduced. When α A → 1, on one hand groups of higher size are built and therefore we achieve higher complexity reduction, but on the other hand the approximation between the group blocks and the matches can lead to lower epitome quality. Furthermore the subset of matches used for the group blocks defined in Eq. 3.19 can be really small since ε A → ε M , which can degrade the efficiency of the epitome generation step. In practice a good trade-off is obtained when α A = 0.5 (see section 3.2.4).

Simulations and results

Experiments were conducted on a set of 4 images : a frame extracted from the Foreman sequence (CIF), Lena (512 × 512), City (1280 × 720) and Calendar (1280 × 720). The size of the blocks is set to 8 × 8, and the epitome is padded with blocks of the same size. The epitomes were computed on a processor Intel core i7 @2.1 GHz.

First tests were carried out with ε M = {3.0, 5.0, 10.0, 15.0}. The parameter α A was here set to 0.5. Results are displayed in Table 3.2. Best results between listbased or cluster-based methods are displayed in bold font. The complexity reduction is assessed by the percentage of the optimized memory occupation over the original one, and the optimized method processing time over the original one. (Note that the maximum absolute processing time for the original method to generate an epitome ranges from a few seconds for CIF resolution, to several ten minutes for SD resolution). Two processing times are displayed : the self-similarities search time, which is the algorithm step actually optimized, and the complete epitome generation time. For all images, the complexity decreases when ε M increases, because higher approximations are allowed. Thus the more interesting results are obtained when ε M = 10.0 or ε M = 15.0. The cluster-based method is overall faster than the list-based method for the self-similarities search, but is overall slower for the complete epitome generation. On average, the memory occupation reduction is better with the cluster-based method, but the lowest memory occupation is achieved with the list-based method. The memory occupation is prohibitive for images City and Calendar when ε M = 15.00 with the original method. This shows a very important limitation of the full search method for high resolution images. Note that because of this, comparative results can not be displayed, but the epitome can be still generated when using optimized methods.

The quality of the epitome produced is assessed by the reconstructed image quality. The graphs representing the reconstructed image PSNR as a function of the epitome size are displayed in Fig. 3.13. The epitome size approximately ranges from 10% to 80% of the input image size, and is inversely proportional to the matching threshold ε M . The reconstruction PSNR approximately ranges from 30 dB to 45 dB. For all images, whatever the epitome generation method, the curves are almost identical. The two methods presented in this section can thus reduce complexity while keeping the Visual results are given in Fig 3 .12 for the Calendar image with threshold ε M = 10.0 for the full search, list-based method and threshold-based clustering respectively. For the last two methods, we set α A = 0.5. We can see that the epitomes are different, but their sizes and corresponding reconstructed images are overall similar. Note the exhaustive visual results for the different test images, self-similarities search methods and thresholds are given in annex, section B.1.

Despite some disparities in the complexity results presented in Table 3.2, the performances between the two methods remain overall close. Complexity results for different values of α A are displayed in Table 3.3, with ε M = 10. As expected, the complexity decreases as α A increases. For α A = 0.25 and α A = 0.5, performances of the two methods remain similar, despite some disparities. However when α A = 0.75, the complexity reduction is more important for the list-based method. This illustrates the behavior of this method, which can reduce drastically the complexity when allowing important approximations. However, when evaluating average reconstruction performances (see Fig. 3.14), we can see that it has a negative impact, as it is the only point which increases the epitome size while decreasing the reconstruction PSNR. Note that, as for the previous experiment, the reconstruction performances are very similar for all images, but for clarity reasons we only show the average results. For the cluster-based method, the complexity gain when α A = 0.75 is limited compared to α A = 0.5, and the reconstruction PSNR seems low compared to the epitome size, even though it is not as evident as for the previous method. Therefore α A = 0.5 seems to be, for both methods, a good trade-off value between complexity and epitome quality.

Conclusion

This section presents efficient algorithms for epitome generation, based on list or cluster methods. The grouping of non-overlapping blocks limits the number of subsequent exhaustive searches over all overlapping blocks, and thus reduces the memory occupation as well as the processing time. Experiments show that interesting complexity results can be obtained without degrading the epitome quality.

In the next section, the proposed methods are implemented in an out-of-the-loop de-noising scheme for video compression.

Average reconstruction performances

List-based method (depending on ) Cluster-based method (depending on ) Original method (depending on ) List-based method (depending on ) Cluster-based method (depending on )

𝛼

Epitome-based quantization noise removal

In this section, we use an epitome as a compact representation of the image/sequence. The epitome is sent to the decoder at a high bit-rate, in order to provide high quality patches which are used to restore the decoded sequence.

Overview of the proposed method

Here, we described the proposed approach in a compression context. Formally, we consider the following notations: the source image/sequence is denoted X, the corresponding coded/decoded image/sequence is denoted Y , and X the de-noised image/sequence.

We note E a texture epitome extracted from the source signal X. We will consider patches of size M × N . The main idea of the proposed method is represented in Fig. 3.15 and consists in the following steps:

• At the encoder side:

learn a set of texture epitomes {E} from the source sequence X (see section 3.3.2)

encode the set of epitomes at high quality (see section 3.3.3)

• At the decoder side:

decode the set of texture epitomes {E } -de-noise the decoded sequence Y using the set of high quality epitomes {E } (see section 3.3.4)

The specific epitome-based de-noising methods are described in details in the section 3.3.4. Based on the proposed scheme, three applications are considered: first, we consider our method as an improvement of the traditional single layer coding scheme such as HEVC, and compare our performances directly against those of the single layer coding scheme. Second, the proposed improvement is considered as an enhancement layer for SNR scalability, and compared to a two-layer scalable coding scheme such as SHVC (see section 1.2.3). Finally, the proposed scheme is considered as an enhancement layer for spatial scalability. In this last application, the base layer is a down-sampled version of the original sequence. At the decoder side, the proposed epitome-base denoising methods are applied on an up-sampled version of the decoded base layer, and thus perform joint de-noising and super-resolution. The specific configurations of the two applications are described in the following sections.

Epitome generation

For the first application, the epitomes are generated using the method described in section 3.2.2, with a set of three matching thresholds ε M = 15.0, 10.0, 7.0, and the corresponding association thresholds ε A = 0.5 * ε M , which generates epitomes of different sizes. The decoded sequence Y is processed by GOP, and the epitome are generated from the first frame of the GOP only, called key frames (KFs), in order to limit the additional bit-rate. In the experiments, the source sequence is encoded using HEVC with the random access configuration, thus a GOP consists in 8 frames. A GOP can thus be processed using two epitomes, the one generated from the first frame of the current GOP, and the one from the first frame of the following GOP (see Fig. 3.16).

In Table 3.4, we show the different sizes of epitomes obtained for the two KFs surrounding the first GOP of the test sequences. All the corresponding epitomes can be seen in annex in section B.2. Table 3.4: Epitomes sizes for the key frames surrounding the first GOP of the test sequences. The sizes are evaluated as the percentage of pixels of each epitome over the total number of pixels in the key frame, and then over the total number of pixels in the GOP (GOP columns). For the second and third applications, an epitome is generated from each frame of the decoded sequence Y , using the method described in section 3.2.2. The matching thresholds ε M = 7.0 and ε M = 3.0 are used for the SNR scalability and spatial scalability respectively, and the corresponding association thresholds is set to ε A = 0.5 * ε M . The non-epitome blocks of a frame are then processed using using three epitome, the one generate from the current frame and the ones from the two surrounding frames. In Tables 3.5 and 3.6, we show the different sizes of epitomes obtained for each frame of the first GOP of the test sequences, with ε M = 7.0 and ε M = 3.0 respectively. Figure 3.16: Epitomes are generated from the first frame of each GOP. A GOP i can then be processed using the two surrounding epitomes E i and E i+1 . Note that the GOP structure depends on the random access coding structure of HEVC. Table 3.5: Epitomes sizes for the frames of the first GOP of the test sequences, with ε M = 7.0. The sizes are evaluated as the percentage of pixels of each epitome over the total number of pixels in the key frame, and then over the total number of pixels in the GOP (GOP columns).

Epitome-based de-noising

We describe here the proposed epitome-based de-noising techniques. To perform the denoising, the frames are divided in N × N overlapping patches. To limit the complexity, not all the overlapping patches are processed, but instead we define a step s in both rows and columns between two processed patches. In the end, when several estimates are obtained for a pixel, they are averaged in order to obtain the final estimate. The main idea consists in the following steps:

• Search for the K-NN of the current patch among the overlapping coded/decoded patches colocated with the epitome patches

• Derive a de-noising method between the noisy K-NN patches and the corresponding high quality patches in the epitome

• Apply the previous de-noising method on the current patch to obtain the de-noised patch

In the case of the first application, the K-NN search is performed in the epitomes from the two closest key-frames. For the second and third applications, the K-NN search is performed in the epitome from the current frame and the closest past and future frames. The aforementioned "de-noising method" expression is to be defined, as many can be derived to solve this problem. Below, we propose several methods. First, we propose a method that we denote "epitome-based Local Linear Combination" (LLC). Let y be the current patch to be de-noised. We note y i , i = 1 . . . K the K-NN of y. The corresponding high quality patches from the epitome are denoted x i , i = 1 . . . K.

Epitome-based Local Linear Combination

From y and its K-NN, we compute a set of weights w i , i = 1 . . . K. This step is detailed below.

The de-noised estimated patch x is obtained as the linear combination of the K high quality patches:

x = K i=1 w i * x i K i=1 w i (3.20)
The method is illustrated in Fig. 3.18. Two variants are proposed to estimate the weights of the linear combination. First, we adapt the well-known NLM algorithm and use exponential weights depending on the distance between y and its K-NN. We note

d i = ||y-y i || 2 2
N 2 , and the weights are then computed as:

w i = e - d i 2σ 2 N LM (3.21)
where σ N LM is a parameter that acts as a degree of filtering. As in the original NLM algorithm it is set to σ N LM = 10 * σ n . The noise level σ n is estimated as the square root of the MSE between the epitome patches and the corresponding coded/decoded patches. This method is named "Epitome-based NLM". In a second variant, the weights are computed using Locally Linear Embedding (LLE), which was presented in the previous chapter for in-loop prediction. Here, the assumption is that the noise preserves the local geometry of the manifold. Thus, for each noisy patch, we can learn its embedding into the noisy patches colocated with the epitome patches, and then apply the weights of the embedding on the corresponding high quality patches from the epitome to obtain the de-noised patch.

The LLE finds the best estimate of y, in a least square sense, from a weighted combination of its K-NN, under the constraints that the weights sum to one. Let M y be a matrix whose columns contain the vectorized K-NN of y, y i , i = 1 . . . K. Let W be a vector containing the weights w i , i = 1 . . . K. The LLE weights are obtained by solving the following equation:

min W ||υ -M y W || 2 2 s.t. K i=1 w i = 1 (3.22)
where υ is the vectorized version of y. The weights vector W is computed as

W = D -1 1 1 T D -1 1 . (3.23)
The term D denotes the local covariance matrix (i.e., in reference to υ) of the K-NN stacked in M y , and 1 is the column vector of ones. In practice, instead of an explicit inversion of the matrix D, the linear system of equations DW = 1 is solved, then the weights are rescaled so that they sum to one. This method is named "Epitome-based LLE".

Epitome-based BM3D

We propose here an adaptation of the very popular BM3D algorithm. Note that the proposed technique can be generalized to any de-noising technique based on the thresholding/shrinkage of transformed coefficients. We explain below how the two steps of the BM3D algorithm, hard thresholding and Wiener filtering, can be adapted for epitomebased de-noising.

For clarity purpose, we group in Table 3.7 the numerous notations necessary to describe this method. First step: Hard Thresholding. One of the key and challenging point of such techniques is to choose the value of the threshold, that we note here τ . In the case of AWGN de-noising, the value of τ is usually set depending on the noise level. For example, the threshold in [START_REF] Dabov | Image Denoising by Sparse 3-D Transform-Domain Collaborative Filtering[END_REF] is set to τ = 2.7 * σ n . However, an optimal de-noising rule for the thresholding is proposed in [START_REF] Guleryuz | A nonlinear loop filter for quantization noise removal in hybrid video compression[END_REF]. In general, this rule can not be applied as it requires the knowledge of the source signal, but it gives an upper bound on the performances of such transform-thresholding techniques. According to this rule, if we note c x a coefficient from the transformed source signal and c y the corresponding transform coefficient from the noisy signal, the corresponding de-noised transform coefficient c x is obtained as follow: In other words, the coefficients with a SNR lower than a 1:1 ratio are canceled.

Here, we propose to use this rule in a epitome-based BM3D method, as the high quality patches from the epitome can be used to implement the above rule. More precisely, the K-NN patches and their corresponding high quality patches from the epitome are stacked in 3D groups that we note G y and G HT x respectively. We then apply a 3D transform T HT on both groups. From the two transformed groups and using the rule of Eq. 3.24, we can obtain a de-noising rule in the form of a binary 3D mask M τ which contains 0 where the coefficients are put to 0 and 1 otherwise:

M τ (ξ) = 0, |T HT (G HT x )(ξ) -T HT (G y )(ξ)| > |T HT (G HT x )(ξ)| 1, otherwise. (3.25)
To de-noise the current patch y, we replace in G y the closest NN of y by the patch y itself, to obtain a 3D group noted G y . We can then apply the transform T HT to G y followed by the thresholding rule M τ , and finally the inverse transform to obtain the de-noised group G HT x : Second step: Wiener filtering. The second step of the original BM3D algorithm consists in a Wiener filtering of the 3D transform group where the first de-noised estimate obtained at the previous step is used as oracle. Here, we propose to adapt this step by using the high quality patches from the epitome as oracle for the Wiener filtering. Note that this step is performed on the de-noised estimate obtained at the previous step and not directly on the noisy frames. We first search for the K-NN of the current patch x among the first estimate patches colocated with the epitome patches from the two closest key-frames. The K-NN patches and their corresponding high quality patches from the epitome are stacked in 3D groups that we note G x and G W ien x . Note that these groups are different from the previous step groups G HT x and G HT x respectively because the K-NN patches are different. We also compute a third 3D group containing the corresponding noise patches:

G HT x = T -1 HT (M τ • T HT (G y )) (3
G n = G W ien x -G x (3.27)
We then apply a 3D transform T W ien on both groups. We can then compute the Wiener filter coefficients:

M W ien = |T W ien (G W ien x )| 2 |T W ien (G W ien x )| 2 + |T W ien (G n )| 2 (3.28)
To de-noise the current patch x, we replace in G x the closest NN of x by the patch x itself, to obtain a 3D group noted G x. We can then apply the transform T W ien to G x followed by the Wiener filtering, and finally apply the inverse transform to obtain the de-noised group G W ien x :

G W ien x = T -1 W ien (M W ien • T W ien (G x)) (3.29)
The final de-noised patch xW ien is then extracted from G W ien

x at the same position as the one of x in G x. This step is illustrated in Fig. 3.20. In this section, we proposed a novel method based on linear mappings that we call "epitome-based Local Linear Mapping (LLM)". Let y be the current patch to be de-noised. We note y i , i = 1 . . . K the K-NN of y. The corresponding high quality patches from the epitome are denoted x i , i = 1 . . . K. Let M y and M x be the matrices containing in their columns the vectorized y i and x i respectively. We can then learn a function, more precisely here a linear mapping, estimating M x from M y . and LLM methods perform in general better than the epitome-based NLM and LLE methods. In facts, for the former, the de-noising rule learning is directly made between the source and the noisy patches, while for the latter, it is only learned on the noisy patches, and then applied to the source patches. The previous results are averaged for the frames of the GOP, but do not necessarily reflect the temporal performances. Results indicate that the de-noising performances are not homogeneous for all the frames of the GOP. In facts, the PSNR gain is much more important for the key frames, where the high quality epitomes are known. An example of such behavior is given in the graph of Fig. 3.22, which corresponds to the de-noising performances for the City sequence encoded at QP = 27, with an epitome obtained with ε M = 7.0 We can see that the epitome-based BM3D and LLM yield an important PSNR gain for the key frames (indexes 279 and 287). However, for the intermediates frames, the epitome-based BM3D has similar performances to the original BM3D, and the epitome-based LLM PSNR is sometimes below the PSNR of the decoded frames.

Epitome-based Local Linear Mapping

Tests were also performed using "random epitomes", which are constructed by randomly selecting patches in the KFs, with the same number of patches as in the actual epitome. Results showed that the "random epitomes" perform poorly compared to the actual epitomes, which demonstrates the interest of the concept of epitome to obtain representative textures for a GOP, and their use in the proposed methods. An example of such result is given in Table 3.9. An example of "random epitomes" is given in comparison with the actual epitomes for the key frames of the City sequence in Fig. 3

RD performances in a single layer coding scheme

The results given in Table 3.8 correspond to the case where the epitomes are lossless encoded, which allows to evaluate the de-noising performances. However, in terms of RD performances, the lossless encoding of the epitomes might no be suitable, as the bitrate associated to the epitomes becomes prohibitive. Thus in this section, in addition to the lossless case, we consider epitomes encoded as described in section 3.3.3. Different QP values are used depending on the QP used to encode the GOP, summarized in Table 3.10. An example of RD curves is given for the City sequence in Fig. 3.24. Results in Table 3.8 show that the epitome-based NLM and LLE methods reach very similar performances. Thus in this section, we only give the results for the epitome-based LLE method. Due to the numerous parameters, many points corresponding to our methods are obtained, and represented as scatter plots in Fig. 3.24. To limit the number of points, we only kept the one whose PSNR values are above the corresponding PSNR values of the decoded sequence (similar to the bold numbers in Table 3.8. The best RD performances obtained with the epitome-based de-noising methods (purple curve in the figure) are obtained with the biggest epitomes (ε M = 7.0) encoded with the highest of the proposed QP values. However, we can see that even the best RD performances are outperformed by HEVC.

The RD performances shown in the figures above are not as good as expected, as the de-noising improvement of the proposed methods are not sufficient to justify the additional rate cost. This limited average PSNR improvement is partly due to the fact that the proposed methods are mainly efficient for the key frames from which the epitomes are extracted, but have little to no de-noising effect on the intermediate frames.

A typical example of such phenomenon is shown in Fig. 3.25 for the Macleans sequence, encoded at QP = 22, de-noised with the epitome-based BM3D (ε M = 7.0). This can be explained by the GOP structure used in the common test conditions of HEVC, which defines different QP values for the frames of the GOP. This can be seen in Fig. 3.25, where the PSNR varies depending on the frame index, which also means that the noise properties vary as well. Consequently, the texture information contain in the epitome of the key frames might not be adapted to efficiently de-noised the intermediate frames.

In addition, quantization artifacts removal is a very challenging problem, as many of the assumptions usually made for additive white Gaussian noise (AWGN) are violated.

In fact, we show in Fig. 3.26 the performances of the epitome-based de-noising methods ( M = 7.0) for the City sequence corrupted with AWGN with σ n = 10. We can see that, even if the de-noising is more effective on the key frames, the intermediate are efficiently de-noised as well.

RD performances in a SNR scalable coding scheme

For this application, we compare our results to the enhancement layer (EL) of SHVC, encoded with QP = 18, 23, 28, 33. The epitomes are encoded with the same QP values.

As for the first applications, the epitome-based de-noising methods used are LLE, BM3D and LLM.

The RD curves for the four sequences are given in Fig. 3.27. Here, since an epitome is transmitted for each frame, the limitations of the first application in terms of denoising are overcome.

We can see that our methods, notably the epitome-based BM3D, can outperform SHVC.

RD performances in a spatial scalable coding scheme

For this application, we compare our results to the enhancement layer (EL) of SHVC, encoded with QP = 22, 27, 32, 37, with a base layer down-sampled with a factor 2 × 2.

The epitomes are encoded with the same QP values.

The RD curves for the four sequences are given in Fig. 3.28.

Here, the proposed methods jointly perform de-noising and super-resolution, and we can see that they can still outperform SHVC. However, contrary to the previous application, the best performing method is not necessarily the epitome-based BM3D, but rather the epitome-based LLM.

Conclusions and perspectives

In this chapter, we first presented efficient epitome generation methods, based on list or cluster approaches. By grouping non-overlapping blocks before performing exhaustive matching searches among overlapping blocks, the memory occupation and the processing time are reduced. Second, the epitome generation method was used in an epitome-based quantization noise removal scheme. The proposed out-of-the-loop framework aims at improving the performances of a video compression scheme by sending high-quality epitomes to the decoder, where the they are used to de-noise the non-epitome patches of the video sequence.

The epitome patches being representative of the textural content of the video sequence, the non-epitome patches can be de-noised using similar patches from the epitome. In the proposed epitome-based de-noising methods, a patch is thus de-noised by first looking for its K-NN among the coded/decoded patches colocated with the epitome. We then propose three method to exploit the pairs of coded/decoded K-NN patches and their corresponding high quality patches from the epitome. The epitome-based local linear combination (LLC) computes weights for each nearest neighbor, and then linearly combines the corresponding high quality patches using the previous weights to obtain the de-noised patch. The weights can be obtained similarly to the NLM algorithm, or using an LLE-based approach. The epitome-based BM3D adapts the original BM3D algorithm by inferring the thresholds for the hard thresholding and Wiener filter coefficients from the high quality patches. Finally, the epitome-based local linear mapping (LLM) method learns a linear mapping projection between the K-NN coded/decoded patches and their corresponding high quality patches, and then apply the projection on the patch being de-noised.

Three applications of the scheme were considered. We first evaluated the performances when epitomes are sent only for key frames of the video sequence, in order to improve a single layer scheme. By limiting the number of epitomes transmitted to the decoder, we want to limit the associated bit-rate while improving the overall quality of the decoded sequence, and thus the encoding performances. However, the results showed that, except for the key frames, the de-noising performances were limited, and consequently the RD performances as well.

In a second application, the epitomes are considered as an enhancement layer in a SNR scalable scheme, and an epitome is generated for each frame of the video sequence. Finally, the proposed methods are used as an enhancement layer for spatial scalability. The results show that for both scalable applications, the proposed methods could outperform the standard SHVC.

We believe that several approaches can be considered to further improve the performances of the proposed scheme.

First, we could consider applying a first pass "blind" de-noising algorithm to the decoded sequence. The term "blind" is used to characterize a method for which no side information needs to be transmitted to the decoder. Any state-of-the-art method, such as the one presented in section 3.1.2, is eligible. The first pass de-noising is likely to improve the K-NN search precision for our epitome-based de-noising method, which is expected to further improve the de-noising performances of our methods.

A second aspect would be to optimize the epitome generation algorithm. First, by taking into account the temporal redundancies, the epitome could be further compacted, which is expected to reduce the bit-rate associated with the epitome while maintaining similar de-noising performances. A direct implementation from existing algorithms would be to generate an epitome of the frame epitomes. In another approach, a sprite [START_REF] Lu | Sprite generation for frame-based video coding[END_REF][85] of the GOP would be created, and an epitome of the sprite would be then generated. Such improvement would be especially interesting for the second application, where epitomes are currently generated independently for each frame. Second, the epitome model used here is generic, and has been used for different applications. However, an application-driven epitomic model could improve the performances of said application. In particular, an optimized epitome generation technique was presented in [START_REF] Turkan | Epitomic image factorization via neighbor-embedding[END_REF] 2 for a LLE-based multi-patches super-resolution application. The results show that the epitomes obtained are more compact than the ones used here for a similar reconstruction quality.

Finally, the scheme could be extended to other scalable applications. In the experiments, we showed that the spatial and SNR scalability were efficient, but extensions to color gamut scalability, or compression of hygh dynamic range (HDR) videos from a low dynamic range base layer, are straightforward.

99

Chapter 4

Clustering-based quantization noise removal

In chapter 3, we proposed an epitome-based quantization noise removal method to improve coding performances of existing compression schemes. The out-of-the-loop proposed scheme was proven efficient for a scalable application, however, the single layer application was outperformed by the standard compression scheme because the PSNR gains could not compensate the cost of the epitomes in terms of bit-rate.

In this chapter, we propose a comparable out-of-the-loop quantization noise removal scheme for video compression. However, we adopt here a different perspective: instead of deriving a de-noising method between the noisy patches and their corresponding high quality patches in the epitome at the decoder side, we derive the parameters of the denoising method at the encoder side between the noisy patches and their corresponding source signal. The derived parameters are then sent to the decoder to perform the denoising. To take into account the redundancies of the signal, we perform clustering on the patches, and learn parameters for each cluster. The Local Linear Mapping (LLM) based multi-patches technique presented in the previous chapter is especially suited for the scheme presented in this chapter. In fact, a linear mapping can be learned for each cluster, and transmitted in a matrix form.

In comparison, the Local Linear Combination presented in the previous chapter could not be adapted here. The BM3D may be adapted to the new scheme, but would require the transmission of many parameters, namely all the 3D transform thresholds and Wiener filter coefficients.

Thus, on one hand, we expect the additional bit-rate to be limited, in particular compared to the bit-rate associated to the epitomes. On the other hand, the linear mappings are learned between noisy patches and the corresponding source patches, which we expect to be efficient in terms of de-noising. This idea is also corroborated by the proven efficiency of de-noising methods based on clustering [71][72][67].

This chapter is organized as follow. Section 4.1 reviews background on clustering and classification methods. Section 4.2 describes the proposed scheme based on clustering for quantization noise removal. Section 4.3 introduces an optimal clustering algorithm for the clustering-based linear mapping de-noising. Section 4.4 presents an adaptation of the proposed scheme for super-resolution in a scalable compression scheme. Finally, we propose in section 4.5 a classification-based scheme which aims at reaching a compromise between the clustering approach described in section 4.2 and the optimal clustering presented in 4.3.

Background

Note that the contributions of this chapter also rely on the de-noising background, described in section 3.1.2. In this section, we present two machine learning tasks, unsupervised and supervised learning.

Un-supervised learning

Un-supervised learning, also called clustering, aims at partitioning a set of points of a p-dimensional space into several subsets, called clusters, so that points in a same cluster are similar according to a pre-defined criterion, while points belonging to different cluster are dissimilar.

In this section, we consider n data points to be clustered, noted x i , i = 1 . . . n. The number K of clusters is a pre-defined parameter.

Below, we present several popular clustering algorithms.

K-means algorithm

The K-means algorithm is among the most known clustering algorithm and was first described in [START_REF] Macqueen | Some Methods for classification and Analysis of Multivariate Observations[END_REF]. This algorithm assigns a data point to the cluster with the nearest mean. Formally, the K-means algorithm solves the following equation:

min C K i=1 x∈C i ||x -µ i || 2 (4.1)
where µ i is the mean of the cluster C i and C = {C i } i=1...K . The standard algorithm to solve this problem is given in Algorithm 2, where the initial set of centroids µ (1)

1 . . . µ (1)
K is considered known. This initial set can be obtained by different methods. A popular method randomly select K vectors from the data set and used them as initial centroids. Another method perform the K-means algorithm on a small subset of the data with a random initialization. The outcome is then used to initialize the centroids to cluster the full data set.

This two steps algorithm can be seen as a variant of the Expectation-Maximization algorithm, presented in the following section.

Gaussian Mixture Model (GMM)

The Gaussian Mixture Model (GMM) assumes that the data points are drawn from a mixture of K Gaussian distributions, which form the latent clusters.

1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 𝑥 1 𝑥 2 𝐻
w • x i -b ≥ 1 if y i = 1, ∀(x i , y i ) ∈ D T w • x i -b ≤ -1 if y i = -1, ∀(x i , y i ) ∈ D T (4.6)
which can be summarized as: This condition was modified into the so-called soft margin method, which allows for mislabeled data. The method introduces non-negative slack variables ξ i which measures the degree of misclassification of a point x i :

y i (w • x i -b) ≥ 1, ∀(x i , y i ) ∈ D T (4.7) 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 𝑥 1 𝑥 2

𝐻

Support vectors

𝐰

y i (w • x i -b) ≥ 1 -ξ i , ∀(x i , y i ) ∈ D T (4.8)
The solutions for this optimization problem are well-known and will not be discussed here. Eventually, the vector w can be expressed as a combination of its support vectors:

w = n i=1 α i y i x i (4.9)
where the x i corresponding to non-zero α i are the support vector. The support vectors lie on the margin and satisfy y i (w

• x i -b) = 1.
The scalar b can then be obtained from a support vector as:

b = w • x i -y i (4.10)
Once such hyperplane has been found, a new data point x is assigned a label y using the following rule:

y = 1 if w • x -b ≥ 1 y = -1 if w • x -b ≤ -1 (4.11)
Alternatively, the computation of the dot product w • x can be expressed using the support vectors:

w • x = n i=1 α i y i x i • x (4.12)
Non-linear SVM For many problems, the classes are not necessarily linearly separable in the input space. In [START_REF] Boser | A training algorithm for optimal margin classifiers[END_REF], the authors propose a non-linear version of SVM based on the kernel trick.

- Conceptually, the finite-dimensional input space is mapped into a higher-dimensional feature space using a transform ϕ. In the feature space, the classes are expected to be linearly separable, and thus the SVM can be applied efficiently (see Fig. 4.3). Using the kernel trick, no computation is explicitly performed in the feature space. The kernel k is related to the transform ϕ by the following equation:

1 -1 -1 -1 -1 1 1 1 1 1 𝐰 𝐻 1 -1 -1 1 1 1 1 -1 -1 -1 𝜑
k(x i , x j ) = ϕ(x i ) • ϕ(x j ) (4.13)
In other words, every dot product in the feature space is replace by a non-linear kernel function. Widely used kernels include the polynomial kernel, k(x i , x j ) = (x i •x j ) d , sigmoid functions k(x i , x j ) = tanh(κx i • x j + c), or Gaussian radial basis functions k(x i , x j ) = exp(-

||x i -x j || 2 2σ 2
). The vector w describing the hyperplane in the feature space is expressed as:

w = n i=1 α i y i ϕ(x i ) (4.14)
corresponding to equation 4.9. However, w is never computed explicitly, thanks to the kernel trick. In fact, a new point x is classified by computing w • ϕ(x ), which can be expressed as follow:

w • ϕ(x ) = n i=1 α i y i ϕ(x i ) • ϕ(x ) = n i=1 α i y i k(x i , x ) (4.15)
Similarly, the scalar b can be computed as:

b = n i=1 α i y i k(x i , x j ) -y j (4.16)
Extension to multiclass Although SVM was initially designed for binary classification, it can be extended to the multiclass problem. The main approach consist in reducing the multiclass problem in multiple binary classification problems. In the "one-vs-all' approach, binary SVM classifiers are built between one class and the all the remaining classes. In the "one-vs-one' approach, a binary SVM classifier is built between every pair of classes.

Decision Tree

Decision trees are methods which build prediction models from data [START_REF] Breiman | [END_REF]. The models are obtained by recursively partitioning the training data space and fitting a simple prediction model within each partition [START_REF] Quinlan | Induction of decision trees[END_REF]. This partitioning can be represented as a tree, called a decision tree. In this section, we focus on describing the use of decision trees for classification problems, however, we will not discuss the well known algorithm for obtaining such trees.

Here, we will only consider binary tree for classification, i.e. for each node of the tree, a binary condition is evaluated on a component of the input vector. More precisely, at a node i, the component c i of the input vector is compared to some threshold value t i , and we can express the condition as:

x c i < t i (4.17)
Each leaf of the tree represents a label.

To classify a new input point x , the conditions at the nodes are recursively evaluated, going from a node to its left child if the condition is validated, to the right one otherwise. The recursive process is repeated until a path is defined from the root to a leaf. The label associated with the leaf is then assigned to the input point.

In the example of Fig. 4.4, the training points are partitioned into two classes, labeled 1 and -1. Although this classification example can not be solved with a linear SVM, it can be simply modeled by the classification tree shown in Fig. 4.5. The new un-labeled point shown as a red question mark in Fig. 4.4 defines the path shown in red in Fig. 4.5, and is assigned the label -1. Bagging. Bagging is the contraction of Bootstrap Aggregating, an ensemble method designed to improve the performances of machine learning algorithms [START_REF] Breiman | Bagging predictors[END_REF]. This meta algorithm is mainly used to reduce the overfitting issue of decision trees, but can be applied to any classification method.

1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 𝑥 1 𝑥 2 1 1 -1 -1 -1 -1 -1 1 𝑎 𝑏 𝑐 1

Clustering-based linear mapping learning for quantization noise removal

In this section, we propose a quantization noise removal method using multiple linear mappings, learned at the encoder side between the decoded sequence and the source sequence. As in the previous chapter, we rely on the grouping of the coded/decoded patches. Here we choose to perform clustering, and a linear mapping is then learned for each cluster.

Main idea and preliminary results with additive noise

To demonstrate the potential of the proposed approach in terms of de-noising, we first tested it on images corrupted with Additive White Gaussian Noise (AWGN) or Signal Dependent Noise (SDN) (see section 3.1.2). We briefly describe our method below, which will be more formally explained in the following section. The noisy image is divided into non-overlapping blocks of size M ×N . In a first step, the blocks are clustered into K partitions using the K-means algorithm (see section 4.1.1.1). For each cluster, a linear mapping is learned between the noisy blocks and the corresponding source blocks (see Eqs. 3.30 and 3.31 in section 3.3.4.3). The linear mapping is then applied on all the noisy blocks of the cluster to obtain the de-noised ones.

The tests were performed on single images (first frame of the test sequences described in Table 4.5), using 4 × 4 non-overlapping blocks and K = 10 clusters. For the AWGN, four values of the standard deviation were used, σ = 10, 20, 30, 40. For the SDN, four sets of noise parameters were also used, γ = 0.5, σ u = 1.5, σ w = 10, γ = 0.5, σ u = 3, σ w = 10, γ = 0.6, σ u = 1.5, σ w = 5, γ = 0.7, σ u = 0.5, σ w = 5. The proposed method is compared to the NLM and BM3D algorithms. In Tables 4.1 and 4.2, we give the results for the AWGN and the SDN respectively, averaged over all the test images. The complete results are given in Tables C. [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF] and C.2, in annex (section C.1.1). We can see that our method is competitive with the NLM, even though it can not reach the performances of BM3D. Especially for high noise level of AWGN or SDN, our methods clearly outperforms NLM. To the best of our knowledge, methods using linear mapping have not been studied for de-noising. Given these promising preliminary results, we propose in the next section a scheme to address the more challenging task of quantization noise removal using this technique. In addition, the proposed following application needs to take into account the transmission of the linear mappings to the decoder, which was not considered here. In this section we describe the proposed compression scheme improvement using clustering-based linear mapping learning for de-noising. We note M d and M s the matrices containing in their columns the vectorized M × N patches extracted from the coded/decoded sequence Y and the source sequence X respectively.

Proposed scheme for quantization noise removal

The main idea of the proposed method is represented in Fig. 4.6, and consists in the following steps:

• At the encoder side:

cluster the coded/decoded patches M d (see section 4.2) -for each cluster c, learn a linear mapping P c between the coded/decoded sequence patches M c d and the source patches M c s :

P c = M c s M c d T (M c d M c d T ) -1 (4.18)
encode the corresponding linear mappings (in matrix form) and transmit them to the decoder (see section 4.2.4)

• At the decoder side:

decode the linear mappings cluster the coded/decoded sequence M d , as it is performed at the encoder side for each cluster c, apply the corresponding linear mapping P c to the decoded sequence patches M c d to obtain the de-noised patches M c r :

M c r = P c M c d (4.19)
In the following sections, we first analyze the clustering process in section 4.2.3. We then detail the linear mappings encoding in section 4.2.4. In section 4.2.5 we propose improvements for the algorithm. Finally we present the results in section 4.2.6.

Clustering

To perform the clustering, we divide the frames in M × N non-overlapping patches. Empirical results show that the de-noising performances are better for small patches. Thus, 4 × 4 patches perform better than 8 × 8 patches, as their local structures are better estimated. However, the patches should be big enough to contain structures. For example, 2 × 2 patches performances are worst than 4 × 4 patches. In practice, 4 × 4 patches were used to obtain our results.

Choice of a clustering algorithm

Any clustering algorithm is eligible for the proposed method, as long as it can be performed similarly at the encoder and the decoder side. We choose the popular Kmeans algorithm, described in section 4.1.1.1. In order to obtain the same clustering at the encoder and the decoder sides, the same initialization should be used on both sides (which excludes the widely used random initialization). The choice of a number of cluster K is discussed in details in section 4.2.3.2.

Note that other clustering methods can be used, such as Gaussian Mixture Models (GMM), described in section 4.1.1.2, or the more recent spectral clustering, described in 4.1.1.3. However, tests showed that even if the clusters obtained are not exactly the same, the final de-noising performances are similar. In fact, all these clustering methods tend to regroup in each cluster patches which are close in terms of Euclidean distance.

To illustrate this behavior, the three clustering methods were performed on a 200 × 200 crop of the first frame of the Kimono sequence encoded with HEVC at QP = 37. The image was divided in 4 × 4 patches, and K was set to 10. The source image and the compressed version along with the different clusters obtained are shown in Fig. 4.7. The clustering results obtained are overall similar, with obvious differences. However, the de-noising performances are in the end very similar, as the de-noised PSNR are 38.4586 dB, 38.3860 dB and 38.4297 dB for the K-means, GMM and spectral clustering respectively. The K-means algorithm was thus preferred for its simplicity and reduced complexity compared to GMM or spectral clustering.

Choice of a number of clusters K

Generally speaking, the parameters should not only be tuned according to the de-noising performance, but the overall RD performance. Concerning the patch size, no compromise needs to be made, as small patches both improve the de-noising performances while reducing the linear mapping rate cost (see section 4.2.4). On the contrary, the number of clusters K should be chosen carefully. In fact, increasing K improves the de-noising performances, but also the number of linear mappings to send to the decoder, and their associated rate cost. Ultimately, learning one mapping per patch can produce almost perfect de-noising, but then a M 2 × N 2 linear mapping should be sent to the decoder for each M × N patch. This is obviously not acceptable in terms of RD performance. Experimental results show that 10 is a good order of magnitude for K. Such value also limits the complexity of the clustering.

The RD performances presented in section 4.2.6.1 were obtained with a fixed K set to 10. The corresponding results presented in Table 4.11 show that this value might be too high at low bit-rates, as it increases the bit-rate for a small increase in PSNR. For example, the bit-rate allocated to the linear mappings for the Kimono and Tennis sequences at QP = 37 accounts for about 7% of the whole bit-rate. On the contrary, at high bit-rates, the cost of the linear mappings can become negligible, e.g. for the Terrace and Ducks sequence, where it only accounts for less than 0.1% of the whole bit-rate. In this case, K could be increased to improve the de-noising performances. Manually tuning the parameter K for each sequence and each QP to obtain the best performance is a tedious task. To address this problem, we present in this section an adaptive method for selecting K based on an RDO criterion.

Instead of explicitly partitioning the data into K clusters, we use a recursive binary partitioning. The procedure is detailed below:

• At initialization, the full data set is considered as a cluster.

• Each cluster is then recursively split in 2 clusters if the RDO criterion (explained below) is satisfied, creating a binary tree structure.

• The procedure stops when no RDO criterion is satisfied, or a certain maximum tree depth is reached.

The RDO criterion used to decide to further split or not a cluster is designed to balance the de-noising performances and the linear mappings rate cost. Given a cluster C n and its corresponding mapping P n , we can allocate a RD cost to it computed as:

RD n = D n + λR n (4.20)
The distortion D n is computed as the Sum of Squared Error (SSE) between the patches of C n de-noised with P n and the corresponding source patches. The rate R n is estimated as the number of bits of the encoded mapping P n (see section 4.2.4). The lagrangian parameter is computed as in the test model of HEVC:

λ = QP f actor × 2 ((QP -12)/3) (4.21)
where QP is the quantization parameter and QP f actor is an adjustment factor, set to 1 in our experiments. Thus, to decide if C n is further divided in two clusters C n+1 and C n+2 , we just verify the condition RD n+1 + RD n+2 < RD n . Note that this method is independent from the clustering algorithm, and could be performed with any clustering algorithm presented in section 4.2.3. An example of binary tree structure obtained after the recursive partitioning is given in Fig. 4.8.

To perform the exact same partitioning at the decoder, we then need to transmit the binary tree structure. If we note the maximum binary tree depth d, then the maximum number of bits needed to describe the tree structure is:

R BT max = d-1 i=0 2 i (4.22)
In our experiments we set d = 4, so the maximum number of clusters is K max = 16 and R BT max = 15 bits. Thus, the bit-rate allocated to the binary tree structure is negligible compared to the bit-rate of a full GOP. The full results obtained with the adaptive RDO selection of K are detailed in section 4.2.6.2, and show its efficiency in terms of RD performance.

Linear mappings encoding

Once the clustering and linear mapping learning steps are performed, the linear mappings need to be encoded and sent to the decoder.

For M ×N patches, the size of a linear mapping matrix P is (M * N )×(M * N ). Thus, in order to limit the rate cost of the linear mappings encoding, the size of the patches should be small, which is also profitable for the de-noising performances. Typically, in section 4.2.6, 4 × 4 patches are used. As explained in section 4.2.3.2, the number of clusters K should be carefully selected, as increasing K improves the de-noising performances but also increases the rate associated to the linear mappings. When using the method described in section 4.2.3.2, the K value ranges from 2 to 16.

For such values, the linear mapping matrices usually exhibit strong redundancies, both inside each matrix and between the different matrices (e.g. in Figs. 4.9 and 4.10). Therefore we choose to stack the linear mapping matrices in a 3-dimensional group, and encode them as an image sequence using a video codec.

The linear mappings matrices consist originally in floating points values, thus they need to be quantized to integer values before encoding. To avoid a loss in terms of de-noising performance due to the quantization, the matrices are quantized on 16 bits integer values (e.g. in Table 4.3). To illustrate this claim, we performed the method on the first frame of the Kimono sequence encoded at QP = 22 and QP = 37 and using the Table 4.3: Impact of the quantization of the linear mapping matrices on the de-noising performances. The de-noising is performed on the first frame of the Kimono sequence, clustered with the K-means algorithm, K = 10. K-means algorithm (K = 10). In Table 4.3, we show the PSNR values of the de-noised frame with or without quantization of the linear mappings. We can see that when the matrices are quantized on 16 bits, there are no effects on the de-noising performances.

The encoding of the matrices is then performed with the Range Extension (RExt) of HEVC [START_REF] Sullivan | Standardized extensions of high efficiency video coding (HEVC)[END_REF][91], which supports 16 bits input. The quantization parameter of HEVC was chosen very low (QP = -30) to limit the loss on the de-noising performances. Finally, in order to recover the floating point matrices, the minimum and maximum values of the original floating points matrices need to be sent to the decoder without loss. In Table 4.3 we show the rate obtained after encoding of the matrices.

The rate of the linear mappings is slightly higher when the frame is encoded at QP = 37 because the matrices are less correlated than at QP = 22, as it can be seen in Figs. 4.9 and 4.10.

Two steps scheme with first pass blind de-noising

Several methods in de-noising use a first de-noising pass in order to improve their performances. First, the BM3D algorithm itself is a two steps algorithm [START_REF] Dabov | Image Denoising by Sparse 3-D Transform-Domain Collaborative Filtering[END_REF], where the first de-noising output, obtained from the sparse 3D transform spectrum shrinkage, is used as input for a Wiener filter. More recently, [START_REF] Pierazzo | Non-local dual image denoising[END_REF] proposed a two steps algorithm, where the noisy input is first de-noised with the NL-Bayes algorithm [START_REF] Lebrun | Implementation of the "Non-Local Bayes" (NL-Bayes) Image Denoising Algorithm[END_REF]. This first pass de-noised image is used as a clean guide for a dual-domain de-noising algorithm [START_REF] Knaus | Dual-domain image denoising[END_REF]. In [START_REF] Liu | Signal dependent noise removal from a single image[END_REF], the authors tackle the less studied Signal Dependent Noise (SDN) removal problem. Their clustering-based method estimates the noise level for each cluster (which is supposed constant). Each cluster is then de-noised by applying an AWGN de-noising algorithm with its corresponding noise level. The performance is improved by first applying a BM3D algorithm using the average noise level.

In this section, we propose a similar improvement of our method by first applying a "blind" de-noising algorithm. Our method is then applied on this first de-noised sequence. This idea is represented in Fig. 4.11. At the encoder side the linear mapping learning is made between the source and this first estimate. Thus, at the decoder side, the same de-noising has to be performed. We qualify this first pass de-noising as "blind" because no parameters should be transmitted between the encoder and the decoder side, so that there is no bit-rate increase. In practice, some parameters that have a negligible rate cost are send. The first pass de-noising is performed using the Video BM3D (VBM3D) algorithm [START_REF] Dabov | Video denoising by sparse 3D transformdomain collaborative filtering[END_REF]. The noise standard deviation σ n is estimated as the square root of the MSE computed on a GOP. This parameter can only be computed at the encoder side and has to be sent to the decoder. However, its rate cost is negligible compare to the bit-rate of the whole GOP. The other VBM3D parameters, shown in Table 4.4, are fixed and considered known at both encoder and decoder side. On top of this first de-noising pass, we apply our method using K-means clustering, with the adaptive K selection method described in section 4.2.3.2.

The results given in section 4.2.6.3 show that a significant improvement is brought by the first pass de-noising compared to the proposed clustering-based method. This also proves that our de-noising method relying on linear mapping can be complementary to the de-noising method relying on shrinkage in a transform domain.

Simulations and results

The sequences used in the experiment are presented in Table 4.5. The test sequences are processed per Group Of Pictures (GOP), and a GOP contains a number of frames equal to the frame rate (i.e., we have one GOP per second). The sequences are encoded with the HEVC test model HM (ver 15.0) [START_REF][END_REF] using the Main profile in Random Access, with 4 values for the Quantization Parameter, QP = 22, 27, 32, 37. For all the experiments, the linear mappings are encoded for each GOP as described in section 4.2.4 using the range extension of HEVC (HM 15.0 RExt 8.1) [91] with a fixed QP = -30.

RD performances using the K-means clustering

In this experiment, the GOPs are divided in non-overlapping patches of size 4 × 4, which are clustered using the K-means algorithm with K = 10 clusters. Rate-distortion performances for each GOP are presented in Table 4.6, computed using the Bjontegaard Here the video is first de-noised with the VBM3D algorithm, with the parameters described in section 4.2.5. Results are given for 1 GOP. In Table 4.9, we see that substantial bit-rate reduction are achieved when combining the proposed method with the BM3D. From Tables 4.8 and 4.10 we can see that the number of clusters selected is higher when using the first pass de-noising. In fact, in the RDO decision, the improvement brought by the first pass de-noising reduces the distortion, and thus allows for a higher bit-rate cost, i.e. more linear mappings can be sent to the decoder.

Optimal clustering for de-noising based on linear mappings

Results from the previous section show that the proposed method using K-means clustering achieves convincing bit-rate reduction compared to HEVC. We give in Table 4.11 the de-noising performances corresponding to the results using K-means clustering with K = 10 (see section 4.2.6.1). We can see that the PSNR improvement is unexpectedly limited. In this section, we first analyze the limitations of the K-means clustering for de-noising using linear mappings. Second, we propose a new clustering algorithm that optimizes the de-noising performances. Note that with the proposed clustering algorithm, we define an upper theoretical bound on the de-noising performances. However, its application as such in the proposed compression scheme is not straightforward, as it relies on the knowledge of the source patches.

K-means limitations for linear mappings learning

First, we notice that the linear mapping used to de-noise a patch implicitly estimates the residue. Let x s be a source patch, x d the corresponding decoded patch and q the patch residue, we have the following relation:

x s = x d + q (4.23)
We call P the linear mapping used to estimate the source patch:

xs = Px d (4.24)
The residue can then be directly estimated using the linear mapping P' = P -I, where I is the identity matrix with the same size as P:

P'x d = Px d -x d = xs -x d = q (4.25)
This (trivial) observation suggests that the use of linear mappings for de-noising will perform better for clusters which contain similar patches residue. When using the K-means algorithm, an implicit assumption is made that the similar decoded patches (belonging to the same cluster) correspond to similar source patches, and thus similar patches residue. However, this hypothesis does not hold for quantization noise, where similar decoded patches can correspond to different patches residue, and vice versa. For example, in Table 4.12, the two noisy patches on the left are similar, but their corresponding source patches (hence the patches residue) are different. On the contrary, the two dissimilar noisy patches on the right would be efficiently de-noised using the same linear mapping, because they correspond to similar patches residue. Table 4.12: Left: Comparison of patches in the same cluster (using K-means). Although the decoded patches are similar, different linear mapping should be used to efficiently approximate their corresponding source patches. Right: Comparison of patches in the different clusters. Although the decoded patches are dissimilar, an unique linear mapping would efficiently de-noise the patches. Another way to represent the clusters is to visualize the patches as points in the Euclidean space. For this purpose we work on the first full frame of the Kimono sequence, encoded with HEVC at QP = 37. Fig. 4.12 shows the coded/decoded frame, which PSNR is 37.95 dB. The proposed de-noising method using the K-means algorithm (K = 10) performed on the 4 × 4 decoded patches reaches a PSNR of 38.07 dB, which corresponds to a PSNR gain of 0.12 dB. The patches are points in a 16 dimensions Euclidean space. In order to obtain a visual representation, we project the patches on 2 dimensions using the Linear Discriminant Analysis (LDA). The LDA was chosen over the popular Principal Component Analysis (PCA) because of its better ability to discriminate between the different classes [START_REF] Martinez | PCA versus LDA[END_REF].

In Table 4.13, we show different visual representations of the clusters obtained with the K-means algorithm performed in the decoded patches. In the first row, each patch of the first frame of Kimono is colored depending on its cluster label. In the second row, we show the 2D representation of the patch Euclidean space. On the left, each point represents a decoded patch projected with the LDA and colored depending on its cluster label. On the right, the same representation is shown, but applied on the patches residue. From these representations, we can verify that the K-means groups similar patches (close in the Euclidean space) together. However, we can see that the clusters completely overlap in the residue space, which means that similar patches residue belong to different clusters, while different patches residue belong to the same cluster, as exhibited in Table 4.12. To further explore this idea, we perform the K-means clustering (with K = 10) directly on the patches residue of the same previous decoded frame of Kimono. The proposed de-noising methods applied with these clusters reaches a PSNR of 40.68 dB, which corresponds to a PSNR gain of 2.73 dB. This result supports the idea that the linear mapping learning is much more efficient for clusters with homogeneous residue patches. In Table 4.14, we show the different visual representations of the clusters, as in Table 4. [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF]. We can see that in the Euclidean spaces, we obtain the inverse representations of Table 4.13. The clusters are well separated in the residue space, but completely overlap in the decoded patches space. Thus, contrary to the K-means performed on the decoded patches, similar decoded patches belong to different clusters, while dissimilar decoded patches belong to the same cluster. This observation appears clearly in the representation of the first row of Table 4.14.

We can see that, in terms of de-noising, significant improvement can be reached compared to the K-means clustering of the decoded patches. Thus, in the next section, we propose a clustering algorithm designed to maximize the de-noising gains.

Optimal clustering for linear mapping learning

We proposed here a new clustering method denoted optimal clustering. For each cluster, we learn a linear mapping, and minimize the overall reconstruction error between the source patches and the coded/decoded patches de-noised with the linear mappings.

Formally, the problem corresponding to the optimal clustering is formulated as follows: with C = {C i } i=1...K . As for the K-means clustering, the problem of Eq. (4.26) can be solved using a greedy algorithm, described in Algorithm 5.

The initial set of linear mappings P

1 . . . P

K is supposed known, e.g. obtained by first performing the K-means clustering on the coded/decoded patches and learning a linear mapping for each cluster.

P (t) i x d || 2 ≤ ||xs -P (t) j x d || 2 ∀j, 1 ≤ j ≤ K} Update step: ∀i = 1 . . . K, P (t+1) i = M i s M i d T (M i d M i d T ) -1
In order to estimate the potential of the optimal clustering in terms of de-noising, preliminary experiments were performed on AWGN and SDN, with the same parameters as in 4.2.1. Here, the results are averaged over all test images. The complete results are given in Tables C. [START_REF] Wallace | The JPEG still picture compression standard[END_REF] and C.4, in annex (section C.1.1). The results given in Tables 4.15 and 4.16 for AWGN and SDN respectively show a dramatic increase of the PSNR for the images de-noised with optimal clustering-based linear mapping learning compared to the K-means clustering (see corresponding Tables 4.1 and 4.2). We can see that the new clustering method is now competitive with BM3D for AWGN and even outperforms BM3D for SDN. When performed on the first frame of the Kimono sequence encoded with HEVC at QP = 37, the de-noised frame PSNR reaches 41.26 dB, which corresponds to a PSNR gain of 3.31 dB. We can see that the optimal cluster does outperform the clustering of the residue patches in terms of de-noising performance. In Table 4.17, we show the different visual representations of the clusters, as in Tables 4. [START_REF] Cherigui | Correspondence Map-Aided Neighbor Embedding for Image Intra Prediction[END_REF] does not appear as clearly as in Table 4.14, the same conclusions can be drawn from the visual representations: the clusters are well separated in the residue space, but overlap in the decoded patches space. Once again, it means that similar decoded patches will belong to different clusters, while dissimilar decoded patches will belong to the same cluster. This observation also appears clearly in the representation of the first row of Table 4.17, which is very similar to the one of Table 4.14.

Although very efficient in terms of de-noising, the optimal clustering and its approximation by clustering the patches residue can not be used as such in the proposed scheme (described in Fig. 4.6). In fact, this method relies on the knowledge of the source patches, which is only available at the encoder side. Furthermore, from the previous observation, it seems difficult to approach the optimal clustering by directly performing clustering on the coded/decoded patches (whatever clustering algorithm is used). Even if information is sent about the clusters shape (such as the centroid and the covariance matrix), it is clear that there is too much overlap between the optimal clusters in the decoded patches space to effectively separate them. Thus, to benefit from the optimal clustering at the decoder side, one should signal to the decoder the cluster label for each patch. The signaling of the cluster labels is studied in the next section.

Potential RD performances using optimal clustering

In this section, we present the potential RD performances obtained when using the optimal clustering described in section 4.3. We also give the actual performances when taking into account the raw cost of the direct transmission cluster indexes. This cost is estimated using the following equation:

R indexes = W M × H N × T × log 2 (K) (4.27)
where W × H is the spatial resolution of the sequence, T is the number of frames, M × N is the patch size, and K is the number of clusters. The only way to decrease this cost is to increase the patch size M × N and/or decrease the number of clusters K, which is known to disadvantage the de-noising performances. Thus, we adapted these parameters depending on the QP used to encode the sequence. In Table 4.18, we give these parameters along with the de-noising performances. Compared to the results using the K-means algorithm given in Table 4.11, the PSNR gains show the efficiency of the optimal clustering for the removal of quantization noise.

In order to visualize the RD performances, we show the RD curves for the "City" and "Ducks" sequences, which are representative of the worst and best cases respectively, in Fig. 4.13. The curves for the remaining test sequences can be seen in annex in section C.1.2. The gray dash lines represent the cluster indexes bit-rates depending on the different patch sizes and cluster numbers (which are function of the QP ). Note that the rate cost of the linear mappings also depends on these parameters, and thus varies as a function of QP . This sometimes results in unexpected RD curve shapes when the cluster indexes bit-rate is not taken into account (green curves). For the same reason, the Bjontegaard measures can not be computed.

The results show that potential huge improvement can be achieved using the optimal clustering in terms of RD performance. However, we can see that the direct transmission (without coding) of the cluster indexes is obviously unrealistic, and yields far worst performances than the standard HEVC. Note that, the indexes exhibit no correlation, neither spatially nor temporally, which excludes compression using predictive model, such as differential pulse-code modulation (DPCM). A statistical analysis of the indexes shows that the histogram is flat, which excludes the use of arithmetic or entropy coding (e.g. Huffman coding). .13: RD performances using the optimal clustering, with and without the cluster indexes rate-cost. The performance upper bound of the optimal clustering (green curve) are clearly above the performance of HEVC, especially at high bit-rate. However, when taking into account the cluster indexes raw bit-rate, the performance drop below the HEVC performances.

Conclusion

It is well known in de-noising that exploiting the self-similarities of an image, by grouping or clustering patches, is an efficient tool. The underlying assumption, for white Gaussian noise as well as signal-dependent noise, is that grouped patches will promote sparsity and share a similar noise level. Therefore, a pruning of the coefficients of a sparse representation below this noise level provides significant de-noising performance. We showed in this section that the proposed linear mapping based method also reaches high PSNR gains on clusters which gather patches with similar noise properties. However, we showed experimentally that the assumption that similar noisy patches will share a similar noise level does not hold in the case of compression noise.

The study of the optimal clustering shows that, even if the K-means algorithm yields some interesting results in terms of RD performances, significant improvements can be expected. Even though its use is not mature in the proposed compression scheme (see Fig. 4.6), it sets an upper bound on the RD performances. We show in section 4.5 a new perspective based on classification which could allow to reach a compromise between the K-means and the optimal clustering on the RD performances.

Application to super-resolution for scalable video compression

In this section we described a clustering-based linear mapping learning method for the super-resolution that we introduce in a scalable compression scheme. The method is adapted from the de-noising method described in the previous chapter. Here, after clustering, the linear mappings are learned between the low-resolution and high-resolution patches, and then applied to perform super-resolution. If the low-resolution sequence is also corrupted with noise, our method jointly performs super-resolution and de-noising, which makes it suitable for the up-sampling of a decoded base layer sequence in a scalable compression scheme such as SHVC.

Preliminary super-resolution results

We first evaluate the potential of the method purely in terms of super-resolution performances, without encoding the sequences. Below, we briefly explain how the method can be adapted for super-resolution. More details will be given in the next section. Here, the clustering is performed on the low-resolution (LR) sequence up-sampled to the size of the HR sequence using a simple up-sampling filter. The linear mappings are then learned between the up-sampled LR patches and the corresponding high-resolution (HR) patches for each cluster. The process is thus very similar to the de-noising method proposed in section 4.2, except that here the linear mapping only performs high frequencies reconstruction.

The tests were performed on single images (first frame of the test sequences described in Table 4.5), the LR images were obtained from the source images by down-sampling with a factor 2 using the SHVC filter [START_REF] Ye | The Scalable Extensions of HEVC for Ultra-High-Definition Video Delivery[END_REF]. The LR image was up-sampled using the SHVC up-sampling filter, so that LR and HR patches share the same 4 × 4 size. The number of clusters was fixed to K = 10.

As for the de-noising application, the optimal clustering formulation (see section 4.3) can be used to define an upper bound on the performances. The tests were performed with K-means and the optimal clustering methods for comparison, and results are given in Table 4. [START_REF] Garcia | Fast k nearest neighbor search using GPU[END_REF]. We can see that the proposed method improves the performances compared to the SHVC up-sampling filter, especially using the optimal clustering. Given these promising preliminary results, we propose in the next section a scheme integrating this method in a scalable compression framework. The results shown in section 4.4.5 also take into account the transmission of the linear mappings to the decoder, which was not considered here.

Proposed scheme for salable compression

In this section, we describe the proposed compression scheme improvement using clusteringbased linear mapping learning for super-resolution. The method is applied in a scalable scheme such as SHVC, in which the LR sequence is encoded as a base layer (BL), and the coded/decoded BL is then used to predict the HR sequence, also denoted enhancement layer (EL). Note that SHVC scalable features also include temporal resolution, SNR, bit depth and color gamut [START_REF] Ye | The Scalable Extensions of HEVC for Ultra-High-Definition Video Delivery[END_REF]. Here, we only focus on the scalability of the spatial resolution. Below, we first describe the proposed method to super-resolve the BL. Then, we explain how the method can be introduced in a scalable coding scheme.

Super-resolution of the base layer

The different steps of the proposed super-resolution method are the same as for the de-noising, with an additional step to up-sample the coded/decoded LR sequence. We use here the same formalism as in section 4.2.2. The matrices M d and M s contain in their columns the vectorized M × N patches from the up-sampled LR coded/decoded sequence Y HR and the HR source sequence X respectively. The main idea of the proposed method is represented in Fig. 4.14, and consists in the following steps:

• At the encoder side:

cluster the up-sampled coded/decoded patches M d (see section 4.4.3) -for each cluster c, learn a linear mapping P c between the up-sampled coded/decoded sequence patches M c d and the source patches M c s :

P c = M c s M c d T (M c d M c d T ) -1 (4.28)
encode the corresponding linear mappings (in matrix form) and transmit them to the decoder (see section 4.4.4)

• At the decoder side:

decode the linear mappings Note that here, applying the linear mappings does not only super-resolve the upsampled coded/decoded patches, but also jointly de-noises them.

Super-resolution in a scalable scheme

Traditional scalable coding schemes, such as SHVC, first encode the BL, which is then used to encode the EL. More precisely, the coded/decoded BL is first processed during a so-called inter-layer processing step. The outcome of the inter-layer process can then be used for the prediction during the EL coding. Note that the inter-layer prediction comes in addition to the standard prediction modes. Here, the inter-layer processing only consists in up-sampling the coded/decoded BL (see section 1.2.3). A simple example of such scheme is presented in Fig. 4.15.

To improve the compression performances of the scalable scheme, we propose to replace the up-sampling filter by our super-resolution method, as presented in Fig. clustering on the BL are huge, and therefore have an impact on the coding of the EL, which also reaches significant bit-rate reduction compared to the SHVC filter. This shows that the proposed scheme (Fig. 4.16) is valid, and as for the de-noising, the upper bound on the performances set by the optimal clustering is substantial. However, the K-means clustering could only improve the performance of the BL. Below, in order to better visualize the above conclusions, we show in Fig 4 .17 the RD curves for the City sequence, with the K-means and the optimal clustering. We can see that when using the K-means, the gain obtained on the BL is slightly reported on the EL at low bit-rates. However at high bit-rates, the quality of the BL is not sufficient (PSNR below 32) to provide an inter-layer prediction competitive with the inter-frame prediction (PSNR above 38). Thus, no difference is visible between the EL encoded with the BL up-sampled with the SHVC filter and the EL encoded with the BL up-sampled with the super-resolution.

The RD curves of the remaining sequences can be seen in annex (section C. .17: RD performance of the City sequence using the K-means and the optimal clustering for super-resolution. The obvious improvement in the performance on the BL are not reported on the EL for the K-means.

From clustering to classification

The optimal clustering algorithm described in section 4.3 sets an upper bound on the de-noising and corresponding RD performances, which shows that the results using the K-means clustering presented in section 4.2.6 can be further improved. Unfortunately, in practice, this upper bound is not reached, because the optimal clustering algorithm relies on the knowledge of the source patches, which are not available at the decoder side.

Experiments showed that the direct transmission of the cluster indexes to the decoder is not worthwhile in a RD sense, especially since this information is very difficult to compress. The analysis of section 4.3.1 indicates that recovering the optimal clusters using only clustering (un-supervised learning) of the coded/decoded patches is not worth considering. One could consider introducing in the clustering process priors relative to a quantization noise model, which would provide an explicit relation between the decoded signal and the source one. To the best of our knowledge, the quantization noise in modern video codecs, such as HEVC, is too complex to be modeled.

However, the problem can be formulated as a supervised learning (classification) problem. Such machine learning techniques are known to be efficient to obtain a model which links input and output data for which an explicit mathematical equation is unknown. In our context, we can use the labels of the optimal clustering to train a classifier on data which are available at the decoder side. Such classifier can then be used at the decoder side to recover the optimal clusters labels.

Two solutions can be considered to train the classifier:

• The classifier is trained at the encoder side, where all the optimal clusters labels are known, using only training data which are also available at the decoder side.

The classifier model has then to be sent to the decoder.

• A subset of the optimal clusters labels is sent to the decoder. The classifier is then directly trained at the decoder side on this subset of data. It is then used on the full data set to predict the optimal clusters labels. The feature vectors on which we perform the classification can obviously contain the (vectorized) coded/decoded patch. However, additional information available at the decoder can help to improve the classifier performance, by adding new dimensions in order to maximize inter-class separability. Among others, the feature vector could for example contain: The choice of the features for classification is usually critical, and one should be careful when selecting them. For example, selecting the first three features in the above list might be redundant, as the decoded patches are reconstructed from the prediction and the inverse transformed quantized coefficients. Instead, one could select only the coded/decoded patches and their corresponding prediction.

Note that there is no guarantee that we can recover perfectly all the cluster labels without knowledge of the source patches. In the next section, we evaluate several classification algorithms performances, notably depending on the features choice.

Preliminary results: classification performances

In this section, we aim to evaluate the ability of several classification algorithms to recover the optimal clusters labels.

We consider the scheme shown in Fig. 4.18, where the classifier is learned on the full data set. Even with this configuration, the optimal clusters labels might not be completely recovered. Thus, after the classification step, the linear mappings are reevaluated.

The optimal cluster labels are obtained using the optimal clustering algorithm with K = 10. The test images are coded with a modified version of a JPEG encoder in which a prediction is performed using the intra coding modes of H.264. Three quality factor (QF ) values are used: 75 (high quality), 50, and 25 (low quality). The block size in the codec is modified to use 4 × 4 blocks. This simple codec architecture was preferred over more complex H.264 or HEVC codecs to have easier access to the decoder data.

Thus, the following features can be used in the classification algorithm:

• The coded/decoded block . Although the resolution is small, the images cover a wide range of textures. Nevertheless, the results are consistent over the different images, so we only give the average results.

Below, we give the average classification results over all the test images, using 4 popular classification algorithms: linear SVM, non-linear Gaussian SVM, decision tree and bagged decision tree, described in section 4.1.2. Note that in this section we are only concerned with the classification and following de-noising performances of the algorithms, and do not take into account the cost of the models in terms of bit-rate.

Choice of the features

We first evaluate the classification performances depending on the selected features and the corresponding de-noising performances evaluated as the PSNR gain over the coded/decoded image with QF = 50. The results are shown in Fig. 4.20. The denoising performances obtained with the K-means algorithm are indicated by a red line, the performances of the optimal clustering with a green line (upper bound).

Not surprisingly, the H.264 intra modes and the block bit-rates alone do not provide enough information to discriminate the classes, and perform poorly with all the algorithms (always under 20 % of the right labels recovered). However, when using the prediction or the coded/decoded blocks, a significant amount of the right labels can be recovered. The performance can be even improved when combining the different features.

The de-noising performance corresponds directly to the classification performance. The best performing algorithms are the Gaussian SVM, which get close to the optimal performances, and the bagged trees, which clearly outperform the K-means performances. We can see that a PSNR gain is always obtained. However, these gains are not always better than the gain of the K-means algorithm. These results should be considered carefully, since the de-noising gains do not directly translate into RD gains. In fact, the best de-noising performances usually correspond to complex classifier models, as shown in the next section.

The corresponding results for QF = 25 and QF = 75 are very similar and given in annex, in section C.3.2.

Dimensionality reduction using PCA

In Fig. 4.21, we show the classification performances obtained before and after performing a PCA on the combined features and the corresponding de-noising performances, with QF = 50. The PCA dimension is gradually reduced.

In general, compared to the raw features, the PCA (with all 34 dimensions) can slightly improve the performances, both in terms of classification and de-noising. More interestingly, the dimension of the PCA can be reduced from 34 to 10 with very little loss in the performances. Reducing the dimension can be advantageous because it can reduce the complexity as well as the rate-cost of the classification model (see section 4.5.2). When the dimension is reduced to 3, there can be a slight loss in the performances, acceptable for most classification algorithms. However, when reduced to 1, we notice a dramatic loss in the performances which is not acceptable.

The best performing algorithms are still the Gaussian SVM and the bagged trees.

The corresponding results for QF = 25 and QF = 75 are very similar and given in annex, in section C.3.2.

From these results, we can conclude that:

• Non negligible proportion of the optimal clusters labels can be retrieved using only data available at the decoder side (i.e. without any knowledge of the source signal). Significant de-noising gains can thus be obtained, leading to a compromise between the K-means clustering performances and the upper bound of the optimal clustering.

• Combining the different features available results in better performances.

• Reducing the dimension of the combined features, e.g. using PCA, results in very little loss in the performances. This can be interesting in order to obtain compact classifier models, as explained in the following section. Decision Tree Here, the classifier model to be sent to the decoder is the decision tree itself. In the case bagging is performed, several trees are transmitted.

As for the Gaussian SVM, increasing the complexity of the model increases the de-noising performances as well as the bit-rate. Here, the complexity of the model is defined by the number of nodes in the tree. For each node, we need to send the index of the component being evaluated, as well as the threshold value against which the component is compared (see Eq. 4.17 in section 4.1.2.2).

If we note d the dimension of the feature space, we can roughly evaluate the rate of a node as R N = log 2 (d) + 16, where the left side of the addition represents the rate of the component and the right side the rate of the threshold, estimated as a 16 bits floating point value. In addition, the values of the class labels for each leaf need to be transmitted. If we note N L the number of leaves, this rate can be evaluated as R L = N L * log 2 (K). This particular rate could be even compressed using entropy or arithmetic coding. If we note N N the number of nodes in a tree, and N T the number of trees to be transmitted, the total rate associated to this classifier model can be evaluated as:

R DT = N T * (N N * R N + R L ) (4.30)
In Fig. 4.23, we compare the performances of different decision trees models. For all models, a PCA is performed on the features vectors. For the decision tree, we first consider using all the dimensions, d = 34, and then reduce the dimension to 1. We then vary the number of nodes, N N = 1, 5, 20, 50, 100, 200, 1000, which gives the different points of the curves. For the bagged decision trees, the dimension is reduced to 1, and we consider different number of nodes, N N = 1, 200, 1000. We then vary the number of trees to obtain the points of the curves N T = 1, 5, 20, 50, 100, 200. The number next to each points of the curves indicate the percentage of the right optimal labels recovered.

We can see that it is more advantageous in a RD sense to send one complex tree rather than several (bagged) simpler trees. The results for QF = 25 and QF = 75 are similar to the one above, and given in annex in section C.3.3.

Learning on a subset of data

In the second scheme of Fig. 4.19, we propose to send only a subset of the optimal class labels, so that the classifier is learned at the decoder side.

The subset of blocks for which the optimal class labels are transmitted can be selected by computing epitomes of each frame. At the decoder side, the classifier is learned on the feature vectors corresponding to the blocks of the epitomes, and then used to obtain the labels of the non-epitome blocks. The scheme is very similar to the Gaussian SVM described above, where the feature vectors corresponding to the epitome blocks act as support vectors.

To estimate the corresponding rate, we can consider that the value 0 is a associated with the non-epitome blocks, while the class label is associated with the epitome blocks. The distribution of these values is not expected to be homogeneous, we can thus compress this additional information using entropy or arithmetic coding.

In Fig. 4.24, we show the performances when transmitting the class labels of epitomes of different sizes. The epitomes are obtained using the method described in section 3.2, with ε M = 2.0, 3.0, 5.0, 7.0, 10.0, 15.0, and ε A = 0.5. We used a bagged decision trees classifier, with a PCA performed on the feature vectors, d = 34, N N = 100 and N T = 1000. The number next to each points of the curves indicate the percentage of the right optimal labels recovered. For comparison, we show the corresponding results using "random epitomes" of the same size. We can see that the choice of the epitome is more relevant that the random epitome. As expected, bigger epitomes allow better de-noising performances, but will require a larger cost in terms of bit-rate. The results for QF = 25 and QF = 75 are similar to the one above, and given in annex in section C.3.3.

RD performances

De-noising of a single layer scheme. Preliminary tests to evaluate the RD performances were performed using the same test conditions as in section 4.5.1, but using here sequences of 10 frames. Here, the scheme described in section 4.5.2.2 is used, where a subset of the optimal class labels is transmitted for blocks of the frames epitomes. The epitomes are obtained using the method described in section 3.2, with ε M = 2.0, and ε A = 0.5. The classifier model, learned at the decoder side, is a bagged decision trees classifier, with a PCA performed on the feature vectors, with d = 34, N N = 100 and N T = 1000.

Results are shown for the Ducks sequence in Fig. 4.25. We can see that the even though the classification allows to recover a PSNR close to the optimal clustering, the cost of the subset of labels transmitted to the decoder is still too high to outperform the K-means clustering in terms of RD performances.

Additional results for the other test sequences are given in annex in section C.3.4.1. Super-resolution in a scalable scheme. We evaluate here the RD performance in a spatial scalable scheme, using the same sequence as in the previous section. The base layer is first down-sampled with a factor 2, and encoded using the same modified JPEG encoder as in section 4.5.1, using QF = 80, 60, 40, 20. The enhancement layer is encoded using a modified JPEG encoder where the up-sampled of super-resolved decoded base layer is used as prediction, with the same QF values as the base layer. A subset of the optimal class labels is transmitted as described in section 4.5.2.2. The epitomes are obtained using the method described in section 3.2, with ε M = 2.0, and ε A = 0.5. The classifier model, learned at the decoder side, is a bagged decision trees classifier, with a PCA performed on the feature vectors, with d = 34, N N = 100 and N T = 1000.

Results are shown for the Basketball and Traffic sequence in Fig. 4.26. We can see that in this case the proposed classification-based scheme can benefit both the base layer and the enhancement layer in terms of RD performances. However, these results do not necessarily hold for the other sequences, which are given in annex in section C. [START_REF] Wallace | The JPEG still picture compression standard[END_REF]

Conclusion

We propose in this section a strategy to obtain a compromise between the performances of the K-means and the optimal clustering algorithms. The preliminary classification results show an interesting potential, and the RD results showed that it is possible to outperform the performances of the K-means clustering in a scalable scheme. Nevertheless, we believe that several means could be considered to further improve the approach. Indeed, only two types of classification algorithms were considered, SVM and decision trees. However, many classification models could be investigated, such as naive Bayes [96], discriminant analysis [START_REF] Fisher | The use of multiple measurements in taxonomic problems[END_REF][98] [START_REF] Mclachlan | Discriminant analysis and statistical pattern recognition[END_REF], nearest neighbors [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF] or deep neural networks [101] classifiers. In our context, we could investigate classifiers with compact models which could perform similarly to the studied models while reducing the rate cost of the model if it is transmitted to the decoder.

Alternatively, we could also investigate classifiers with higher classification performances for a given subset of optimal class labels. The RD performances could thus be improved by a better de-noising efficiency for a similar bit-rate.

Conclusion and perspectives

In this chapter, we proposed a clustering-based scheme with linear mappings learning for quantization noise removal. The proposed out-of-the-loop framework aims at improving the performances of a video compression scheme by sending to the decoder linear mappings learned at the encoder between the clustered coded/decoded patches and the corresponding source patches. At the decoded side, the same clustering as the encoder side is performed, and the corresponding linear mappings received are used to de-noise the decoded video sequence.

First, the K-means algorithm is used to partition the video sequence. A binary tree partitioning technique based on a RDO criterion is also proposed to adaptively select the number of clusters.

Results show that the proposed scheme can improve the coding efficiency of HEVC, and is especially efficient when combined with a first pass de-noising algorithm.

We also proposed an optimal clustering algorithm which sets an upper bound on the performances, and show that further improvement can be reached.

The clustering-based scheme is then used for super-resolution in a scalable video compression context. When using the K-means algorithm, we observed that the gains brought to the base layer are not reported on the enhancement layer. Experiments performed with the optimal clustering showed that the proposed scalable scheme could outperform SHVC, but requires an important improvement of the base layer.

Finally, a classification-based scheme is presented which aims at reaching a compromise between the K-means and the optimal clustering in terms of RD performances. Some promising preliminary results are obtained, and the experiments showed that it is possible to outperform the K-means in terms of RD performances in a simple JPEGbased spatial scalable scheme.

Several approaches can be considered to further extend the proposed scheme. First, all the experiments were performed on the luminance channel, nevertheless, the proposed scheme could be applied to color sequences as well. The proposed method can be adapted to color sequences simply by stacking all the color components of the vectorized patches in the matrices M d and M s . In addition to the extension of the method to color components, the proposed method could be applied in a scalable scheme to color gamut scalability, e.g. to predict a 4:4:4 or RGB enhancement layer from a 4:2:0 base layer. The adaptation of the proposed scalable scheme to the encoding of a high dynamic range enhancement layer from a low dynamic range base layer is also straightforward.

Second, we observed that the optimal clustering approach was not efficient in terms of RD performances when taking into account the bit-rate of the cluster indexes. A promising alternative scheme based on classification is proposed in order to reach a compromise between the K-means performances and the optimal performances. The technique could be further improved by considering more efficient or more compact classifiers, notably in order to be applied in modern scalable coding schemes.

Finally, we believe that our method would be particularly suited for cloud-based compression. Cloud-based compression has gained interest recently [START_REF] Yue | Cloud-Based Image Coding for Mobile Devices-Toward Thousands to One Compression[END_REF], as well as applications such as de-noising based on external images [START_REF] Luo | Image denoising by targeted external databases[END_REF][104], or super-resolution [START_REF] Sun | Super-resolution from internet-scale scene matching[END_REF] [START_REF] Yue | Landmark Image Super-Resolution by Retrieving Web Images[END_REF]. By introducing our method in such framework, e.g. using the scheme of Fig. 4.27, we can assume that the linear mapping matrices are available in an external database, which means that no bit-rate overhead is needed. Thus, we could purely benefit from the de-noising improvement without any additional cost in terms of bitrate.

The learning of the linear mappings, performed in an off-line training phase, thus becomes critical. During the on-line processing phase, the decoded patch being processed would query the database to retrieve an appropriate linear mapping, with which it could then be de-noised.

For example, if the linear mappings are learned on clusters found with the K-means algorithm, the centroids of the clusters would be stored in the database along with the corresponding linear mappings. When a patch is processed, one would search for the closest centroid in the database, and use the associated linear mapping to de-noise the current patch. Such scheme has been for example considered for super-resolution in [START_REF] Zhang | Learning Multiple Linear Mappings for Efficient Single Image Super-Resolution[END_REF]. The scheme of Fig. 4.27 is also especially suitable to be combined with the proposed classification-based approach, where the classifiers would be learned during the off-line training phase and then stored in the database to be later used on-line.

Conclusion

In this thesis, we explored novel approaches in order to improve existing video compression schemes. One of the main principle of video compression is to reduce the temporal and spatial redundancies occurring in natural images/videos. Video compression standards exploit this principle through Inter and Intra prediction tools respectively, which we described in details in Chapter 1. Inter prediction thus rely on motion estimation/compensation while Intra prediction propagate the information from the spatially neighboring pixels previously decoded. The goal of the work presented in this manuscript was to improve the existing compression schemes by further exploiting the intrinsic redundancies in natural images and videos, notably through the use of multi-patches methods. This first lead us to improve the current standard prediction tools, using multipatches methods based on Locally Linear Embedding (LLE). In Chapter 2, we presented methods which consist in a first step in approximating the current template, by linearly combining K templates found in the previously decoded part of the video. The linear weights are obtained with the LLE, and then applied on the blocks adjacent to the templates in order to obtain the predictor of the current block. Different strategies are proposed to find the K patches necessary to perform the prediction. First, we proposed to search for the K nearest neighbors (K-NN) of the template only. This technique can be reproduced at the decoder side, and thus we spare the syntax usually associated with motion estimation (list index, reference frame index, motion vector). Then, we proposed to search for the K-NN of the full patch comprising the current block and template, which enforces the correlation between the templates and their adjacent blocks, which in return improves the quality of the predictor. Such methods were already proven efficient for the reduction of spatial redundancies through Intra prediction, and we showed that they can be valuable to improve Inter prediction as well. Moreover, we demonstrated that combining the proposed methods for both Intra and Inter prediction greatly benefits the coding performances.

Independently from the standard video compression techniques emerged the concept of epitome, which is defined as a condensed representation of an image or video containing the essence of its textural properties. Due to its proximity to the compression principle of reducing the self-similarities within an image or video signal, several in-loop approaches exploiting epitomes have been proposed. In particular, one method combined the epitomic concept and the LLE-based multi-patches methods discussed above. At the same time, we observed that many applications such as de-noising and super-resolution exploit redundancies in natural images and videos. We thus decided to propose an epitome-based methods for compression with an out-of-the-loop perspective, where the epitome containing high quality patches is used at the decoder to improve the decoded video, using multi-patches image restoration methods such as de-noising or super-resolution. This work is presented in Chapter 3, where we first described an efficient method for epitome generation, based on list or cluster approaches. We then implemented this epitome generation method in an epitome-based quantization noise removal scheme, where high-quality epitomes are sent to the decoder and used to denoise the non-epitome patches of the video sequence. Three epitome-based de-noising methods are proposed, which first consists in looking for the K-NN of the patch being processed among the coded/decoded patches colocated with the epitome. The pairs of coded/decoded K-NN patches and their corresponding high quality patches from the epitome are then exploited to perform the de-noising. A local linear combination (LLC) method is proposed, which linearly combines the K high quality patches with weights computed from the corresponding noisy patches using the Non Local Mean (NLM) or LLE approach. An epitome-based method adapted from the BM3D algorithm is also introduced, which infer the thresholds for the hard thresholding and Wiener filter coefficients from the high quality patches. Finally, an epitome-based local linear mapping (LLM) method is described, where a linear mapping projection is learned between the K-NN coded/decoded patches and their corresponding high quality patches, and then applied on the patch being de-noised. The scheme was shown efficient to improve the performances of the scalable video compression scheme SHVC. However, the scheme described above was not able to outperform the performances of the single layer codec HEVC. We thus proposed in Chapter 4 an out-of-the-loop scheme based on a different paradigm: instead of transmitting an additional layer containing high quality patches, we learn at the encoder side linear mappings between the coded/decoded patches and their corresponding source patches, and send the projection matrices to the decoder. In order to take into account the self-similarities of the signal, the patches are clustered, and a linear mapping is learned for each cluster. The same clustering is then performed at the decoder side, and the corresponding linear mappings are then applied on the patches of the cluster to obtain a de-noised version. The results show that the proposed scheme outperforms HEVC. In addition, we proposed an optimal clustering formulation, which defines an upper bound on the performances, and demonstrates that potential further improvement could be reached. We also proposed to adapt the scheme for scalable video compression, notably using super-resolution for spatial scalability. However, if the improvement on the base layer are indubitable compared to SHVC, they are not reported on the enhancement layer. We observed that potential improvement can be obtained on the enhancement layer when using the optimal clustering. Finally, a novel classification-based scheme is presented which aims at reaching a compromise between the K-means and the optimal clustering in terms of RD performances. The results obtained are promising, and show that the K-means can be outperformed in terms of RD performances in a JPEG-based spatial scalable scheme.

Thus, in this thesis, we focused on exploiting the natural self-similarities of an image or video signal to improve compression performances. First, we improved the existing prediction tools which already exploit the texture redundancies of a video. Then, we introduced in an out-of-the-loop compression framework different methods exploiting texturing redundancies, originally designed for epitome generation, clustering, de-noising or super-resolution. We proposed novel and disruptive approaches, and we demonstrated their efficiency for different applications, either single layer or scalable compression schemes. Furthermore, we believe that this work can be extended to additional applications such as high dynamic range (HDR) image compression, or cloud-based compression, as discussed below.

Future work

Several approaches can be considered to further extend the work of this thesis.

First, we have considered this work as an upstream investigation, with a focus on the improvement of the RD performances, which in return requires a high processing complexity. For all the contributions, the complexity mainly comes from the self-similarities search, such as the nearest neighbors search, for which efficient and fast methods exist [14][15]. This process is also highly parallelizable, and could be for example implemented on GPU [START_REF] Garcia | Fast k nearest neighbor search using GPU[END_REF]. Similarly, fast clustering methods could be considered [START_REF] Douze | The Yael Library[END_REF]. Finally, the LLE or NLM weights computations could be fasten with approximate methods [START_REF] Wige | Sample-based weighted prediction with directional template matching for HEVC lossless coding[END_REF].

Second, although we proposed in Chapter 3 an epitome generation method optimized in terms of complexity, the performances of the compression scheme proposed in this chapter could be improved by adapting the epitomic model so that it takes into account the temporal redundancies. A direct approach would be to create an epitome of the frame epitomes. Alternatively, a sprite of the GOP could be generated [START_REF] Lu | Sprite generation for frame-based video coding[END_REF] [START_REF] Lu | Efficient background video coding with static sprite generation and arbitrary-shape spatial prediction techniques[END_REF], and the epitome would be extracted from the sprite. Furthermore, the epitomic model used in this work are optimized to reconstruct the original image. We could therefore adapt the model so that it takes into account the final application, which is here multi-patches de-noising or super-resolution. Such method has been proposed in [START_REF] Turkan | Epitomic image factorization via neighbor-embedding[END_REF] for a LLE-based multi-patches super-resolution application.

Third, the optimal clustering algorithm proposed in Chapter 4 remains at the time of writing a theoretical upper bound on the performances. Indeed, we observed that the optimal clustering could not be used directly in the proposed scheme, as it requires the transmission of the cluster indexes to the decoder, which is not efficient in terms of RD performances. However, given this upper bound, it is clear that the results that we obtained with K-means clustering can be improved. We postulate that a compromise could be reached between the K-means and the optimal clustering performances by using an alternative scheme based on classification. In this scheme, only a subset of the optimal cluster indexes would be signaled to the decoder, where a classifier model could be learned and then used to derive the unknown cluster indexes. Alternatively, the classifier could be learned at the encoder side and transmitted to the decoder.

Finally, the proposed schemes could be adapted for other applications. For example, the methods were only tested on the luminance channel, but could be adapted to color videos as well. Notably in scalable schemes, the proposed methods could be extended to color gamut scalablity, and bit-depth scalability, in particular for the encoding of a high dynamic range enhancement layer from a low dynamic range base layer. In addition to HDR compression, the proposed scheme could be adapted to other trending topics such as cloud-based compression [START_REF] Yue | Cloud-Based Image Coding for Mobile Devices-Toward Thousands to One Compression[END_REF], or plenoptic imaging compression [START_REF] Conti | Inter-layer prediction scheme for scalable 3-D holoscopic video coding[END_REF][110] [START_REF] Li | Efficient intra prediction scheme for light field image compression[END_REF], which contain many redundancies.

- d 2 i 2σ 2 N

 2 LM , où d i est la distance entre le patch courant et son i-ème voisin, et σ N LM est un paramètre qui règle le degré de filtrage.

AFigure 1 . 1 :

 11 Figure 1.1: Main operations in a compression scheme.

Figure 1 . 2 :

 12 Figure 1.2: Hierarchical levels of a sequence in H.264/AVC.

Figure 1 . 4 :

 14 Figure 1.4: Basic coding structure for H.264/AVC for a macroblock. Source: [1].

Figure 1 . 5 :Figure 1 . 6 :

 1516 Figure 1.5: Intra prediction modes for 16 × 16 blocks.

Figure 1 . 7 :

 17 Figure 1.7: Motion estimation with block matching. The motion vector obtained v is shown in red.

Figure 1 . 9 :

 19 Figure 1.9: Multiple reference frames for inter prediction.

Figure 1 . 10 :

 110 Figure 1.10: Hierarchical levels of a sequence in HEVC.

Figure 1 . 11 :

 111 Figure 1.11: Recursive partitioning of a CTU based on a quadtree structure.

Figure 1 .

 1 Figure1.12: Typical HEVC video encoder (with decoder modeling elements shaded in light grey). Source:[START_REF] Sullivan | Overview of the high efficiency video coding (HEVC) standard[END_REF]

Figure 1 . 13 :

 113 Figure 1.13: Modes and directional orientations for Intra prediction. Source: [2].

Figure 1 .

 1 Figure 1.14: SHVC decoder architecture. The modified EL decoder is indicated as HEVC * . Source: [47].

  2.1).

Figure 2 . 1 :

 21 Figure 2.1: Template Matching for Inter prediction.

Figure 2 . 2 :

 22 Figure 2.2: Predictor computation technique based on LLE. Assuming the dictionaryA is available, a weighting coefficient vector V is learned using the LLE, which approximates the current template X k with the K templates in A k . The current block predictor Xu is obtained by applying the learned weights to the K blocks in A u .

Figure 2 . 3 :

 23 Figure 2.3: Search for the K-NN of the current template in the TM-LLE method.

Figure 2 . 4 :

 24 Figure 2.4: Illustration of the first two steps of the BM-LLE method.

Figure 2 . 5 :

 25 Figure 2.5: Example of construction of A 0 and A L-1 dictionaries from candidate patches c 0 and c L-1 (oITM-LLE method).

Figure 2 . 6 :

 26 Figure 2.6: Left: close-up of a building from the City source sequence. Middle: H.264 prediction. Right: oITM-LLE prediction.

Figure 2 . 7 :

 27 Figure 2.7: Coding performances obtained with the different proposed prediction methods as a function of the number K of nearest neighbors.

Figure 2 . 8 :

 28 Figure 2.8: Encoder complexity obtained with the different proposed prediction methods as a function of the number K of nearest neighbors.

Figure 2 . 9 :

 29 Figure 2.9: Coding performances obtained with the different proposed Inter prediction methods as a function of the number of reference frames.

Figure 2 . 10 :

 210 Figure 2.10: Encoder complexity obtained with the different proposed Inter prediction methods as a function of the number of reference frames.

Figure 2 . 11 :Figure 2 . 12 :

 211212 Figure 2.11: Coding performances obtained with the different proposed prediction methods as a function of the SW range and the number of reference frames.

Figure 2 . 13 :Figure 2 . 14 :

 213214 Figure 2.13: Coding performances of the combination of both Inter TM-LLE and Intra TM/oITM-LLE as a function of the frame type.

Figure 2 . 15 :

 215 Figure 2.15: Distribution of the selected prediction modes as a function of the quantization parameter.

53

 53

Figure 2 . 16 :

 216 Figure 2.16: Rate-Distortion performances of the City sequence.

  3.1.1 Epitome generation 3.1.1.1 Generative models N. Jojic and V. Cheung first introduced the notion of epitome in [20][21]. An epitome is defined as the condensed representation (meaning its size is only a fraction of the original size) of an image (or a video) signal containing the essence of the textural properties of this image.

Figure 3 . 1 :

 31 Figure 3.1: Epitome (right) generated from a frame of the Foreman sequence (left) and part of the mapping (in red). Source: [58].

Figure 3 . 2 :

 32 Figure 3.2: Epitome (middle) and ISD (right) generated from Barbara (left). Input image is 512x512, ISD and epitome are 75x75 (figure is not at scale). Source: [61].

Figure 3 . 3 :

 33 Figure 3.3: Find self-similarities within an image. Source: [62].

Figure 3 . 4 :

 34 Figure 3.4: Candidate region ∆EC for epitome growth, formed as the union of matchings that overlap the block B j . Source: [62].

Figure 3 . 5 :

 35 Figure 3.5: Example of factor image. In the center is the epitome obtained from the input image on the left. On the right is the epitome atlas obtained from the epitome. Source: [62].

Figure 3 . 7 :

 37 Figure 3.7: Epitome chart extension process. On the right, in red is presented a finished epitome chart, while in blue is presented the current epitome chart being extended. The inferred blocks are in purple.

Figure 3 . 8 :

 38 Figure 3.8: Epitome (left) extracted from Calendar and the corresponding reconstructed image (right). The epitome was obtained using the full search method for the selfsimilarities search with the threshold ε = 10.0.

Table 3 . 1 :

 31 Notations used for the BM3D Common parameters N × N Size of the patches s Sliding step between the overlapping patches NSW × NSW Size of the search window for the K-NN search K Maximum number of neighbors εBM Maximum acceptable distance between the current patch an its neighbors First step: Hard Thresholding THT 3D transform used for the Hard Thresholding step λ threshold parameter for the hard thresholding G HT y 3D group containing the K-NN of the current patch to be de-noised y G HT x 3D group containing the de-noised estimates of the patches in G HT y Second step: Wiener filtering This step is performed on the de-noised frames obtained at the previous step. TW ien 3D transform used for the Wiener filtering step G x 3D group containing the K-NN of the first estimate of current patch x G W ien y 3D group containing the noisy patches corresponding to the patches in G W ien x G W ien x 3D group containing the de-noised estimates of the patches in G W ien y

1 )De-noised patches 4 )Figure 3 . 9 :

 1439 Figure 3.9: First step of BM3D: hard thresholding.

Final 2 ) 1 𝑊𝑖𝑒𝑛Figure 3 . 10 :

 21310 Figure 3.10: Second step of BM3D: Wiener filtering.

Figure 3 . 11 :

 311 Figure 3.11: Example of self-similarities search using the associated lists.

Figure 3 .

 3 Figure 3.12: Epitomes (left) extracted from Calendar and the corresponding reconstructed images (right). The epitome was obtained using the full search method (top), the list-based method (middle), and the threshold-based clustering (bottom) for the self-similarities search with the threshold ε M = 10.0 and the parameter α A = 0.5.

Figure 3 . 13 :

 313 Figure 3.13: Reconstruction performances for the test sequences depending on the epitome size.

Figure 3 . 14 :

 314 Figure 3.14: Reconstructed average PSNR vs epitome size.

Figure 3 . 15 :

 315 Figure 3.15: Proposed de-noising scheme for coding noise using epitomes.

εM = 15

 15 .0 εM = 10.0 εM = 7.0 Sequence KF 0 KF 1 GOP KF 0 KF 1 GOP KF 0

1 ) 3 )Figure 3 . 18 :

 13318 Figure 3.18: Epitome-based de-noising of coded/decoded patches using Local Linear Combination.

1 ) 1 Figure 3 . 19 :

 11319 Figure 3.19: Epitome-based de-noising -first step of the adapted BM3D.

  .26) where • represents an element-by-element multiplication.The first step de-noised patch xHT is then extracted from G HTx at the same position as the one of y in G y . This step is illustrated in Fig.3.19.

1 )Figure 3 . 20 :

 1320 Figure 3.20: Epitome-based de-noising -second step of the adapted BM3D.

1 ) 3 )Figure 3 . 21 :

 13321 Figure 3.21: Epitome based de-noising of coded/decoded patches using Local Linear Mapping.

Figure 3 . 22 :

 322 Figure 3.22: De-noising performances on the first GOP of the City sequence encoded with HEVC with QP = 27.

Figure 3 . 23 :

 323 Figure 3.23: Epitomes (left) extracted from the first (top) and last (bottom) frames of the City (crop) GOP. The epitome was obtained with the threshold ε M = 7.0, and the epitomes account for 53.6616 % and 59.596 % of the original frames size respectively. On the right are shown "random epitomes" of the same size.

Figure 3 . 24 :

 324 Figure 3.24: RD performances for City when encoding epitomes of several sizes using different QP values in a single layer scheme.

Figure 3 . 25 :

 325 Figure 3.25: De-noising performances on the first GOP of the Macleans sequence encoded with HEVC with QP = 22.

Figure 3 . 26 :

 326 Figure 3.26: City sequence corrupted with AWGN (σ n = 10), de-noised with the epitome-based methods. The information contained in the KF epitomes was sufficient to de-noise the remaining frames of the GOP.

Figure 3 . 27 :

 327 Figure 3.27: RD performances of the proposed methods in a SNR scalable scheme.

Figure 3 . 28 :

 328 Figure 3.28: RD performances of the proposed methods in a spatial scalable scheme.

Figure 4 . 2 :

 42 Figure 4.2: Example of linear SVM.

Figure 4 . 3 :

 43 Figure 4.3: Example of non-linear SVM.

Figure 4 . 4 :Figure 4 . 5 :

 4445 Figure 4.4: Binary labeled training data points in a 2D space, which can not be separated by an hyperplane.

  The main idea of ensemble methods is to create several training subset from the training data. Formally, m training subsets D i T of size n are generated by sampling uniformly and with replacement (bootstrap sample) from the main training set D T . It is then possible to learn a classifier model from each training subset. When classifying a new test point, m predicted labels are thus obtain. The label which is the more represented among these m labels is assigned to the test point.

Figure 4 . 6 :

 46 Figure 4.6: Proposed de-noising scheme for coding noise based on clustering and linear mappings.

Source

  Compressed with HEVC at QP = 37 PSNR = 37.7105 dB K-means GMM Spectral clustering De-noised PSNR = 38.4586 dB De-noised PSNR = 38.3860 dB De-noised PSNR = 38.4297 dB

Figure 4 . 7 :

 47 Figure 4.7: 200 × 200 crop of the first frame of Kimono, and the comparison between the different clustering methods with K = 10. (Each color corresponds to a cluster label.)

Figure 4 . 8 :

 48 Figure 4.8: Example of a cluster partition based on a binary tree structure and an RDO criterion. The clusters are recursively split to reach 4 clusters. The tree structure is described by only 5 bits.

Figure 4 . 9 :

 49 Figure 4.9: Linear mapping matrices obtained on the first frame of the Kimono sequence encoded with HEVC at QP=22. The clusters were obtained with the K-means algorithm, with K = 10. With this configuration, the source and coded/decoded patches are similar, thus the energy of the mappings is mainly concentrated on the diagonal.

Figure 4 . 10 :

 410 Figure 4.10: Linear mapping matrices obtained on the first frame of the Kimono sequence encoded with HEVC at QP=37. The clusters were obtained with the K-means algorithm, with K = 10. With this configuration, the coded/decoded patches are more degraded than in Fig. 4.9, thus the mappings are less structured.

Figure 4 . 11 :

 411 Figure 4.11: Proposed de-noising scheme for coding noise based on clustering and linear mappings with first pass "blind" de-noising.

Patch 1 ,

 1 cluster 1 Patch 2, cluster 1 Patch 1, cluster 1 Patch 2, cluster 2 Decoded Source

Figure 4 . 12 :

 412 Figure 4.12: First frame of the Kimono sequence encoded with HEVC at QP=37. PSNR = 37.95 dB.

Table 4 . 13 :

 413 Visual representations of the K-means clustering performed on the decoded patches, K = 10. (Each color corresponds to a cluster label.) K-means clustering on decoded patches. De-noised PSNR = 38.07 dB.LDA projection of the coded/decoded patches. the residue patches.

Table 4 . 14 :

 414 Visual representations of the K-means clustering performed on the residue patches, K = 10. (Each color corresponds to a cluster label.) K-means clustering on residue patches. De-noised PSNR = 40.68 dB. LDA projection of the coded/decoded patches. .K x d ,xs∈C i ||x s -P i x d || 2 (4.26)

Algorithm 5

 5 Optimal clustering for linear mapping learning Input: cluster number K, d × n coded/decoded patches matrix M d = {x d }, corresponding source patches matrix Ms = {xs} Output: cluster set C = {Ci, 1 ≤ i ≤ K}, corresponding mapping matrices P = {Pi, 1 ≤ i ≤ K} Repeat the two following steps until convergence: Assignment step: ∀i = 1 . . . K, C (t) i = {x d , xs : ||xs -

Table 4 . 17 :

 417 Visual representations of the optimal clustering, K = 10. (Each color corresponds to a cluster label.) Optimal clustering. De-noised PSNR = 41.26 dB.LDA projection of the coded/decoded patches. the residue patches.

Figure 4

 4 Figure 4.13: RD performances using the optimal clustering, with and without the cluster indexes rate-cost. The performance upper bound of the optimal clustering (green curve) are clearly above the performance of HEVC, especially at high bit-rate. However, when taking into account the cluster indexes raw bit-rate, the performance drop below the HEVC performances.

-Figure 4 . 14 :

 414 Figure 4.14: Proposed super-resolution scheme for low resolution coded/decoded sequences based on clustering and linear mappings.

Figure 4 . 15 :Figure 4 . 16 :

 415416 Figure 4.15: Traditional scalable scheme for video compression (e.g. SHVC).

Figure 4

 4 Figure 4.17: RD performance of the City sequence using the K-means and the optimal clustering for super-resolution. The obvious improvement in the performance on the BL are not reported on the EL for the K-means.

  These two schemes are represented in Figs. 4.18 and 4.19 respectively.

Figure 4 . 1 Step 2 Figure 4 . 19 :

 412419 Figure 4.18: Classification-based scheme to recover the optimal cluster labels at the decoder, with transmission of the classifier model.

•

  The coded/decoded patch • The prediction patch • The transform • The quantized transform coefficients • The prediction mode: intra or inter • In case the prediction is intra: the directional mode • In case the prediction is inter: the motion vector • The frame type (I-P-B) • The quantization parameter • The bit-rate associated to the patch

Figure 4 . 21 :Figure 4 . 22 :

 421422 Figure 4.21: Average classification (top) and de-noising (bottom) performances with different dimensions of a PCA performed on the combination of features, with images encoded at QF = 50.

Figure 4 . 23 :

 423 Figure 4.23: Average RD performances of the decision trees, QF = 50.

Figure 4 . 24 :

 424 Figure 4.24: Average performances of the bagged decision tree depending on the size of the epitome, QF = 50.

Figure 4 . 25 :

 425 Figure 4.25: RD performances for the Ducks sequence with recovering of the optimal class labels using classification.

  training dataset 𝐶: centroids 𝑃: projections 𝑋: source sequence 𝑌: decoded sequence 𝑋: enhanced decoded sequence

Figure 4 . 27 :

 427 Figure 4.27: Off-line linear mappings learning for quantization noise removal.

Figure B. 2 :

 2 Figure B.2: Reconstructed images corresponding to the epitomes from the previous Figure.

Figure B. 3 :

 3 Figure B.3: Epitomes extracted from Lena. The epitome was obtained using the full search method (top), the list-based method (middle) and the threshold-based clustering (bottom) for the self-similarities search with, from left to right, the thresholds ε M = 3.0, 5.0, 10.0, 15.0 and the parameter α A = 0.5.

Figure B. 4 :

 4 Figure B.4: Reconstructed images corresponding to the epitomes from the previous Figure.

Figure B. 5 :

 5 Figure B.5: Epitomes extracted from City. The epitome was obtained using the full search method (top), the list-based method (middle) and the threshold-based clustering (bottom) for the self-similarities search with, from left to right, the thresholds ε M = 3.0, 5.0, 10.0, 15.0 and the parameter α A = 0.5. (Full search with ε M = 15.0 could not be produced).

Figure B. 6 :

 6 Figure B.6: Reconstructed images corresponding to the epitomes from the previous Figure.

Figure B. 7 :

 7 Figure B.7: Epitomes extracted from Calendar. The epitome was obtained using the full search method (top), the list-based method (middle) and the threshold-based clustering (bottom) for the self-similarities search with, from left to right, the thresholds ε M = 3.0, 5.0, 10.0, 15.0 and the parameter α A = 0.5. (Full search with ε M = 15.0 could not be produced).

Figure B. 8 :

 8 Figure B.8: Reconstructed images corresponding to the epitomes from the previous Figure.

B. 2

 2 Figure B.9: Epitomes extracted from the first frame (top) of the City first GOP, and first frame (bottom) of the following GOP. The epitomes were obtained, from left to right, with the thresholds ε M = 7.0, 10.0, 15.0.

Figure B. 10 :

 10 Figure B.10: Epitomes extracted from the first frame (top) of the Foreman first GOP, and first frame (bottom) of the following GOP. The epitomes were obtained, from left to right, with the thresholds ε M = 7.0, 10.0, 15.0.

Figure B. 11 :

 11 Figure B.11: Epitomes extracted from the first frame (top) of the Macleans first GOP, and first frame (bottom) of the following GOP. The epitomes were obtained, from left to right, with the thresholds ε M = 7.0, 10.0, 15.0.

Figure B. 12 :

 12 Figure B.12: Epitomes extracted from the first frame (top) of the Mobile first GOP, and first frame (bottom) of the following GOP. The epitomes were obtained, from left to right, with the thresholds ε M = 7.0, 10.0, 15.0.

Figure C. 2 :Figure C. 5 :Figure C. 6 :

 256 Figure C.2: RD performance of the test sequences using the K-means and optimal clustering for super-resolution

1 Figure C. 7 :

 17 Figure C.7: Average performances of the decision trees, with QF = 75 (left) and QF = 25 (right).

Figure C. 8 :Figure C. 9 :Figure C. 10 :

 8910 Figure C.8: Average performances of the bagged decision trees depending on the size of the epitome, with QF = 75 (left) and QF = 25 (right).

  1.3.Figure 1.3: GOP structure for inter prediction in H.264/AVC. The frames are decoded in the order I 0 , P 4 , B 2 , B 1 , B 3 , but displayed in the order I 0 , B 1 , B 2 , B 3 , P 4 .

	I 0	B 1	B 2	B 3	P 4	B 5	B 6	B 7	P 8

  16 × 16, 16 × 8, 8 × 16 and 8 × 8. The 8 × 8 blocks can be further divided into 8 × 4, 4 × 8 and 4 × 4 blocks (see Fig. 1.8). For 16 × 16 blocks, a Skip mode is also defined, for which no side information is sent

16 x 16 16 x 8 8 x 16 8 x 8 8 x 8 8 x 4 4 x 8 4 x 4

	Figure 1.8: Block partitions for Inter prediction in H.264/AVC.

Table 2 .

 2 1: Simulations parameters

	Parameter	Setting
	Sequence type:	IBBPBBP
	Number of encoded frames:	31 (Matrix: 34)
	Number of reference frames:
	-for BM:	4
	-for K-NN:	4 (& causal part)
	Search-range:
	-for BM:	32 pel for CIF
		64 pel for 720p
	-for K-NN:	32 pel for all
	Search method:
	-for BM:	Fast Full Search
	-for K-NN:	Full Search
	Search accuracy:
	-for BM:	Quarter Pel
	-for K-NN:	Full Pel
	Block sizes for intra:	all 16x16 to 4x4
	Block sizes for MCP:	all 16x16 to 8x8
	Block sizes for LLE:	8x8
	Template size:	+3 pel on width and height
	Quantization parameter (I/P/B):	22/23/24, 27/28/29,
		32/33/34, 37/38/39
	Number L of dictionaries for oITM-LLE 32

Table 2 .

 2 .2. 2: K values set to achieve a trade-off between RD performances and complexity.

	Method	K value Execution time in % Bit-rate gain in %
	TM-A	8	213	-5.30
	TM-LLE	8	249	-5.89
	BM-LLE	16	204	-1.80
	ITM-LLE	64	362	-5.85
	oITM-LLE	32	5077	-7.79

Table 2 .

 2 3: Reference frames number set to achieve a trade-off between RD performances and complexity.

	Method	Reference frames Execution time in % Bit-rate gain in %
		number
	TM-A	3	157	-5.14
	TM-LLE	3	156	-5.83
	ITM-LLE	1	276	-6.33

Table 2 .

 2 4: Search window size set to achieve a trade-off between RD performances and complexity.

	Method	SW range Execution time in % Bit-rate gain in %
	TM-A	32	213	-5.30
	TM-LLE	32	249	-5.89
	ITM-LLE	16	207	-4.94

Table 2 .

 2 5: Coding gains (in %) for the Inter TM-LLE, Intra TM/oITM-LLE and combined methods for each sequence.

	Sequence	Inter TM-LLE Intra TM/oITM-LLE Inter TM-LLE and
				Intra TM/oITM-LLE
	Foreman	-2.73	-1.68	-4.40
	Rushes	-5.15	-2.90	-7.27
	Matrix	-2.43	-6.53	-6.47
	City	-6.57	-3.60	-8.80
	Spincalendar	-7.95	-6.60	-15.31
	Average	-4.97	-4.26	-8.45

Table 2 .

 2

	Foreman	101.34	154.81	210.73
	Rushes	98.89	148.47	202.59
	Matrix	89.85	187.80	171.14
	City	94.38	119.13	233.52
	Spincalendar	93.39	167.93	426.61
	Average	95.57	155.63	248.92

6: Encoder complexity (in %) for the Inter TM-LLE, Intra TM/oITM-LLE and combined methods for each sequence. Sequence Inter TM-LLE Intra TM/oITM-LLE Inter TM-LLE and Intra TM/oITM-LLE

Table 3 .

 3 2: Memory occupation and computation time % with respect to original method, depending on ε M , with α A = 0.5.

			List-based method	Cluster-based method
	I	εM	Memory	Search	Total	Memory	Search	Total
			load (%) time (%) time (%)	load (%) time (%) time (%)
	Foreman	3.0 5.0 10.0 15.0	50.18 49.54 25.00 18.08	68.62 60.72 32.65 21.61	73.93 60.12 41.39 42.37	47.85 45.22 19.06 14.59	67.31 55.80 28.58 18.00	70.15 61.88 50.36 55.25
		3.0	98.18	75.54	78.92	96.81	69.05	70.13
	Lena	5.0 10.0	63.61 29.98	61.00 37.49	65.24 51.92	48.28 23.66	56.12 31.60	66.19 55.74
		15.0	19.96	23.09	59.69	21.64	23.56	64.48
	City	3.0 5.0 10.0	60.54 60.71 51.47	66.75 64.165 48.07	65.27 64.160 60.07	55.85 56.47 48.18	68.62 62.48 47.06	69.25 62.80 59.75
	Calendar	3.0 5.0 10.0	84.66 48.43 28.33	68.36 54.76 32.58	66.44 58.83 52.97	80.69 42.08 53.98	70.36 53.25 42.43	68.02 59.94 57.91
	same epitome quality.

Table 3 .

 3 3: Memory occupation and computation time % with respect to original method, depending on α A , with ε M = 10.0.

			List-based method	Cluster-based method
	I	αA	Memory	Search	Total	Memory	Search	Total
			load (%) time (%) time (%)	load (%) time (%) time (%)
	Foreman	0.25 0.50 0.75	70.66 25.00 9.58	53.17 32.65 21.94	61.51 41.39 24.74	67.86 19.06 7.32	51.42 28.58 19.96	58.41 50.36 46.74
	Lena	0.25 0.50 0.75	79.99 29.98 9.03	60.93 37.49 23.27	72.73 51.92 26.57	70.13 23.66 15.91	56.41 31.60 25.48	65.69 55.74 53.73
	City	0.25 0.50 0.75	86.30 51.47 19.46	64.06 48.07 33.84	67.54 60.07 42.41	84.09 48.18 38.17	63.30 47.06 40.90	66.99 59.75 58.83
	Calendar	0.25 0.50 0.75	69.76 28.33 10.13	51.43 32.58 22.69	65.30 52.97 29.61	65.85 53.98 48.35	49.95 42.43 36.86	66.65 57.91 57.94

dB] Epitome size / Input image size [%] City reconstruction performances

		44.00	Foreman reconstruction performances	𝜖𝑀 = 3.0		44.00	Lena reconstruction performances	𝜖𝑀 = 3.0
		42.00											42.00
	Reconstruction PSNR [dB]	32.00 34.00 36.00 38.00 40.00	𝜖𝑀 = 10.0				Original method List-based method Cluster-based method 𝜖𝑀 = 5.0	Reconstruction PSNR [dB]	32.00 34.00 36.00 38.00 40.00		𝜖𝑀 = 10.0			Original method List-based method 𝜖𝑀 = 5.0 Cluster-based method
		30.00	𝜖𝑀 = 15.0										30.00	𝜖𝑀 = 15.0
		10.00	20.00	30.00	40.00	50.00		60.00	70.00	10.00	20.00	30.00	40.00		50.00	60.00	70.00
				Epitome size / Input image size [%]							Epitome size / Input image size [%]
		48.00									𝜖𝑀 = 3.0	44.00
		46.00
													42.00
	𝜖𝑀 = 10.0 Reconstruction PSNR [Original method 32.00 34.00 36.00 38.00 40.00 42.00 44.00 List-based method Cluster-based method 𝜖𝑀 = 5.0	Reconstruction PSNR [	32.00 34.00 36.00 38.00 40.00
		30.00
		28.00	𝜖𝑀 = 15.0									30.00
		0.00	10.00	20.00	30.00	40.00	50.00	60.00	70.00	80.00	90.00	0.00	10.00	20.00	30.00	40.00	50.00	60.00	70.00

dB] Epitome size / Input image size [%] Calendar reconstruction performances

	Original method
	List-based method
	Cluster-based method

Reconstruction PSNR [dB] Epitome size/ Input image size [%]

	33.00
	32.80
	32.60
	32.40
	32.20
	32.00
	31.80
	31.60
	31.40
	20.00	21.00	22.00	23.00	24.00	25.00	26.00

Table 3 .

 3 6: Epitomes sizes for the frames of the first GOP of the test sequences, with ε M = 3.0. The sizes are evaluated as the percentage of pixels of each epitome over the total number of pixels in the key frame, and then over the total number of pixels in the GOP (GOP columns).

	εM = 3.0

Table 3 .

 3 7: Notations used for the epitome-based BM3D This step is performed on the de-noised frames obtained at the previous step.

		First step: Hard Thresholding
	THT	3D transform used for the Hard Thresholding step
	Gy	3D group containing the K-NN of the current patch to be de-noised y
	G HT
	TW ien	3D transform used for the Wiener filtering step
	G x	3D group containing the K-NN of the current patch	x
	G W ien x	3D group containing the K high quality patches corresponding to the K-NN contained in G x
	Gn	3D group containing the noise patches G W ien x	-G x
	G x	3D group containing the same patches as G x,
		except for the closest NN of x which is replaces by x itself
	G W ien x	3D group containing the de-noised estimates of the patches in G x
	xW

x 3D group containing the K high quality patches corresponding to the noisy K-NN contained in Gy G y 3D group containing the same patches as Gy, except for the closest NN of y which is replaces by y itself G HT x 3D group containing the de-noised estimates of the patches in G y xHT estimate of y at the end of the Hard Thresholding step Second step: Wiener filtering ien final de-noise estimate of y at the end of the Wiener filtering step

Table 3 .

 3 8: De-noising performances (PSNR in dB) of epitome-based methods for coding noise averaged over the test sequences. The bold values indicate a PSNR above the corresponding PSNR of the decoded sequence.

				Original	Epitome-based methods
		Coded /	methods		εM = 15.0
	QP	Decoded	NLM	BM3D	NLM	LLE	BM3D	LLM
	22	40.354	36.390	40.328	32.460	32.351	39.669	34.422
	27	36.920	34.348	36.941	32.064	32.049	36.575	33.375
	32	33.788	32.425	33.859	31.460	31.479	33.802	32.078
	37	30.793	30.226	30.875	30.489	30.528	31.126 30.929
				Epitome-based methods
			εM = 10.0			εM = 7.0
	QP	NLM	LLE	BM3D	LLM	NLM	LLE	BM3D	LLM
	22	33.532	33.394	40.110	36.345	34.041	33.897	40.331	36.915
	27	33.075	33.045	36.981	35.281	33.553	33.525	37.200	35.804
	32	32.405	32.426	34.185 33.951	32.863	32.894	34.378 34.453
	37	31.378 31.418 31.440 31.951 31.809 31.869 31.587 32.886

  .23.

		40.9
			De-noising performances for City at QP=27
	PSNR [dB]	38.9 39.9			HEVC Original NLM Original BM3D Epitome-based NLM Epitome-based LLE
		37.9			Epitome-based BM3D Epitome-based LLM
		36.9
		35.9
		34.9
		279	280	281	282	283	284	285	286	287
						Frame index

Table 3 .

 3

		Epitome Random epitome
	NLM	31.809	29.045
	LLE	31.869	28.836
	BM3D	31.587	31.204
	LLM	32.886	29.856

9: Comparison of de-noising performances (PSNR in dB) between the epitome and a "random epitome" (ε M = 7.0) averaged over the test sequences encoded at QP = 37

Table 3 .

 3 10: Choice of the quantization parameter to encode the epitome.

		QP BL
		22 27 32 37
		lossless
	QP EL	6 12 16 18 22 8 9 11 18 23 28 33

  Figure 4.1: Binary labeled data points in a 2D space separated by hyperplanes. The hyperplane H 1 can not separate the two classes. Both H 2 and H 3 can separate the classes, but H 3 separates them with the maximum margin.

	1	𝐻 2	𝐻 3

Table 4 .

 4 1: De-noising performances of K-means (K = 10) clustering-based linear mapping learning compared to NLM and BM3D for AWGN

			PSNR (dB)
	σ	Noisy	K-means LM	NLM	BM3D
	10 28.1393	33.5882	34.1586 36.3768
	20 22.2159	29.8034	30.0121 33.2105
	30 18.8622	27.6393	27.0592 31.2358
	40 16.5635	26.0502	24.8694 29.5960

Table 4 .

 4 2: De-noising performances of K-means (K = 10) clustering-based linear mapping learning compared to NLM and BM3D for SDN

					PSNR (dB)
	γ	σu σw	Noisy	K-means LM	NLM	BM3D
	0.5	1.5 10 23.1242	30.3219	25.7377 33.2564
	0.5	3	10 18.4487	27.3471	22.6082 30.0192
	0.6	1.5	5	20.5998	28.7132	27.8899 30.9156
	0.57 0.5	5	25.1191	31.5671	32.5274 33.7646

Table 4 .

 4 4: Fixed parameters for the BM3D algorithm. See section 3.1.2.4 for details on the parameters.

	Parameters	THT	2D-Bior 1.5 + 1D-Haar
	for	λ	2.7σn
	Step 1
	(HT )	ε HT BM	3000
	Parameters TW ien	2D-DCT + 1D-Haar
	for
	Step 2	ε W ien BM	1500
	(W ien)
	Common	K	8
	parameters	N	8
		NSW	7
		s	8
		NF R	4

Table 4 .

 4 5: Test sequences

	Sequence	Resolution Frames count Frame rate
		W × H	T
	City	1280 × 720	600	60
	Park Scene	1920 × 1080	240	24
	Tennis	1920 × 1080	240	24
	Kimono	1920 × 1080	240	24
	Cactus	1920 × 1080	500	50
	Terrace	1920 × 1080	600	60
	Basket	1920 × 1080	500	50
	Ducks	1920 × 1080	500	50
	People On Street 2560 × 1600	150	30
	Traffic	2560 × 1600	150	30

Table 4 .

 4 7: RD performances per GOP of K-means clustering with RDO adaptive K selection (Bjontegaard bit-rate gain with respect to HEVC)

	GOP	City	Park Scene	Tennis	Kimono	Cactus	Terrace	Basket	Ducks	People On Street	Traffic	Average
	1	-2.763 -0.692 -0.900 -1.317 -1.125	-5.253	-1.104 -2.393 -2.570 -1.439 -1.956
	2	-2.309 -0.672 -0.720 -1.348 -1.285	-6.830	-0.405 -1.819 -2.576 -1.387 -1.935
	3	-2.447 -0.632 -0.775 -1.358 -0.892	-8.855	-0.977 -1.078 -2.589 -1.352 -2.096
	4	-1.657 -0.536 -0.824 -1.308 -0.979 -11.579 -0.622 -1.245 -2.612 -1.351 -2.271
	5	-1.844 -0.517 -0.717 -0.888 -1.112 -11.947 -0.761 -1.266 -2.631 -1.528 -2.321
	6	-2.217 -0.476 -1.077 -0.853 -1.370	-9.900	-0.766 -1.707			-2.296
	7	-1.898 -0.479 -1.907 -0.585 -1.248	-8.203	-0.679 -2.130			-2.141
	8	-1.861 -0.396 -2.389 -0.582 -1.295	-7.233	-1.089 -2.469			-2.164
	9	-2.515 -0.309 -1.773 -0.428 -1.188	-6.354	-0.880 -2.577			-2.003
	10	-2.743	0.017	-2.518	0.286	-0.999	-6.471	-0.691 -2.836			-1.994
	Average -2.236 -0.472 -1.415 -0.938 -1.153	-8.083	-0.795 -1.957 -2.600 -1.425 -2.107

Table 4 .

 4

	QP	City	Park Scene	Tennis	Kimono	Cactus	Terrace	Basket	Ducks	People On Street	Traffic	Average
	22	10.8 8.5 7.6 8.2 14.9 15.4 12.0 15.9 16.0 14.0 12.33
	27	11.3 6.8 5.7 6.4 11.7 15.0	9.7	15.8 16.0 12.6 11.10
	32	7.4	4.0 3.4 4.5	9.0	14.1	7.8	15.8 16.0	7.6	8.96
	37	5.9	4.0 2.8 4.0	7.1	13.1	5.8	15.5 15.8	5.8	7.98
	4.2.6.3 RD performances with first pass blind de-noising

8: K values for K-means with RDO adaptive K selection (Averaged over all GOPs)

Table 4 .

 4 9: RD performances of K-means clustering with RDO adaptive K selection and VBM3D de-noising (Bjontegaard bit-rate gain with respect to HEVC)

		K-means	VBM3D	VBM3D and
		clustering		K-means clustering
	City	-2.763	-1.498	-3.237
	Park Scene	-0.692	-0.882	-1.072
	Tennis	-0.900	-7.837	-7.766
	Kimono	-1.317	-4.266	-4.317
	Cactus	-1.125	-4.037	-6.188
	Terrace	-5.253	-1.145	-7.240
	Basket	-1.104	-2.977	-3.803
	Ducks	-2.393	-1.602	-4.127
	People On Street	-2.570	-7.881	-9.627
	Traffic	-1.439	-4.326	-5.428
	Average	-1.956	-3.645	-5.281

Table 4 .

 4 10: K values for K-means with RDO adaptive K selection and VBM3D denoising

	QP	City	Park Scene	Tennis	Kimono	Cactus	Terrace	Basket	Ducks	People On Street	Traffic	Average

Table 4 .

 4 11: De-noising performances of K-means clustering with K = 10 (∆PNSR)

	QP	City	Park Scene	Tennis	Kimono	Cactus	Terrace	Basket	Ducks	People On Street	Traffic	Average
	22	0.125 0.044 0.104 0.089 0.042 0.088 0.028 0.028 0.170 0.077 0.080
	27	0.118 0.047 0.092 0.081 0.048 0.141 0.034 0.048 0.136 0.083 0.083
	32	0.099 0.048 0.080 0.071 0.052 0.158 0.042 0.076 0.119 0.080 0.083
	37	0.083 0.047 0.078 0.069 0.058 0.188 0.049 0.110 0.115 0.076 0.087

Table 4 .

 4

	15: De-noising performances of optimal clustering-based linear mapping learn-
	ing and BM3D for AWGN
			PSNR (dB)
	σ	Noisy	Optimal clustering LM	BM3D
	10 28.1393	36.2814	36.3768
	20 22.2159	33.3756	33.2105
	30 18.8622	31.8393	31.2358
	40 16.5635	30.8744	29.5960

Table 4 .

 4 and 4.14. Although it 16: De-noising performances of optimal clustering-based linear mapping learning and BM3D for SDN

					PSNR (dB)
	γ	σu σw	Noisy	Optimal clustering LM	BM3D
	0.5	1.5 10 23.1242	33.8326	33.2564
	0.5	3	10 18.4487	31.7479	30.0192
	0.6	1.5	5	20.5998	32.7183	30.9156
	0.57 0.5	5	25.1191	34.9877	33.7646

Table 4 .

 4 18: De-noising performances of optimal clustering (∆PNSR)

	QP K M × N	City	Park Scene	Tennis	Kimono	Cactus	Terrace		Basket	Ducks	People On Street	Traffic	Average
	22	16	4 × 4	1.36 1.08 1.49 1.28 0.79 0.85 0.91 0.79 1.58 1.35 1.15
	27	8	4 × 4	1.20 1.04 1.76 1.55 0.74 0.80 0.90 0.85 1.45 1.28 1.16
	32	16	8 × 8	0.76 0.67 1.63 1.38 0.62 0.59 0.80 0.62 1.08 0.88 0.90
	37	4	8 × 8	0.49 0.46 1.34 1.09 0.48 0.49 0.66 0.51 0.76 0.62 0.69
		41		City								Ducks
		40							37
	PSNR [dB]	37 38 39 36			HEVC Optimal clustering w/ indexes cost	PSNR [dB]	35 33			HEVC
		35			Optimal clustering w/o indexes cost Indexes cost, K=4, MxN=8x8		31			Optimal clustering w/ indexes cost Optimal clustering w/o indexes cost
		34			Indexes cost, K=16, MxN=8x8						Indexes cost, K=4, MxN=8x8
		33			Indexes cost, K=8, MxN=4x4			29			Indexes cost, K=16, MxN=8x8 Indexes cost, K=8, MxN=4x4
		32			Indexes cost, K=16, MxN=4x4						Indexes cost, K=16, MxN=4x4
		31							27
		0	5000	10000	15000	20000	25000		0	20000	40000	60000	80000	100000	120000
				Bitrate [kbps]							Bitrate [kbps]

Table 4 .

 4 19: Super-resolution performances of clustering-based linear mapping on nonencoded low resolutions images

	Sequence	SHVC Filter K-means Optimal clustering
	City	30.9836	32.3000	35.3865
	Park Scene	36.3585	36.9171	38.8824
	Tennis	40.9845	41.3829	43.0397
	Kimono	44.4866	44.6471	45.7041
	Cactus	34.1444	34.7399	36.9079
	Terrace	28.7704	29.6783	32.3759
	Basket	34.9184	35.6637	39.2549
	Ducks	33.4748	34.0972	35.9034
	People On Street	38.0490	39.1701	41.6081
	Traffic	38.4106	39.1342	41.7834
	Average	36.0581	36.7731	39.0847

Table 4 .

 4 20: RD performances computed on the BL and EL using K-means clustering with K = 10 for super-resolution (Bjontegaard measures with respect to the up-sampled BL with SHVC filter and corresponding SHVC EL respectively)

		BL gain		EL gain
		bit-rate % gain PSNR gain bit-rate % gain PSNR gain
	City	-20.36	0.501	-0.50	0.004
	Park Scene	0.91	-0.007	-0.40	-0.093
	Tennis	2.03	-0.059	0.92	-0.049
	Kimono	2.87	-0.088	-0.02	0.062
	Cactus	-7.74	0.174	0.56	-0.050
	Terrace	-39.24	0.560	-0.20	0.090
	Basket	-18.53	0.374	2.34	-0.114
	Ducks	-8.66	0.194	-0.59	-0.016
	Average	-11.09	0.206	0.26	-0.021

Table 4 .

 4 [START_REF] Cheung | Video epitomes[END_REF]: RD performances computed on the BL and EL using optimal clustering with K = 10 for super-resolution (Bjontegaard measures with respect to the up-sampled BL with SHVC filter and corresponding SHVC EL respectively)

		BL gain		EL gain
		bit-rate % gain PSNR gain bit-rate % gain PSNR gain
	City	-80.66	2.864	-15.70	0.307
	Park Scene	-64.29	2.025	-23.87	0.102
	Tennis	-62.52	2.584	-19.90	0.934
	Kimono	-73.98	3.638	-18.08	1.291
	Cactus	-68.02	2.135	-16.99	0.520
	Terrace	-96.03	2.887	-11.50	0.470
	Basket	-90.49	3.338	-16.64	0.564
	Ducks	-73.94	2.318	-16.88	1.682
	Average	-76.24	2.724	-17.45	0.734

  When all the features are combined, the feature vector has a dimension of 34: 4 × 4 vectorized coded/decoded block, 4 × 4 vectorized prediction block, one directional mode (scalar) and one bit-rate (scalar).In order to reduce the complexity, the tests are performed on nine images of resolution 200 × 200, cropped from the first frame of the following test sequences: City, Park Scene, Kimono, Cactus, Terrace, Basketball, Ducks, People On Street, and Traffic (shown in Fig. C.3 in annex, section C.3.1)

	• The prediction block
	• The H.264 intra directional mode
	• The bit-rate associated to the block

  .4.2.

		44				Basketball					45			Traffic
		42									43
	PSNR [dB]	38 40					Upsampling filter BL K-means + SR BL	PSNR [dB]	37 39 41				Upsampling filter BL
		34 36					Clustering optimal + SR BL Classification BL Upsampling filter EL		35 33				K-means + SR BL Clustering optimal + SR BL Classification BL Upsampling filter EL
							K-means + SR EL			31				K-means + SR EL
		32					Clustering optimal + SR EL		29				Clustering optimal + SR EL
							Classification EL							Classification EL
		30									27
		0	500	1000	1500	2000 bit-rate [kbits/s] 2500	3000	3500	4000	4500	0	500	1000	1500 bit-rate [kbits/s]	2000	2500
	Figure 4.26: RD performances with recovering of the optimal class labels using classi-
	fication for super-resolution in a scalable scheme
											151

Table C .

 C 2: De-noising performances of K-means (K = 10) clustering-based linear mapping learning and BM3D for SDN

	Table C.3: De-noising performances of optimal clustering-based linear mapping learning
	and BM3D for AWGN
			PSNR (dB)	PSNR (dB)		PSNR (dB)	PSNR (dB)
	Image	Noisy Image	K-means LM Noisy Optimal clustering LM NLM BM3D	Noisy BM3D	K-means LM Noisy Optimal clustering LM NLM BM3D	BM3D
			γ = 0.5, σu = 1.5, σw = 10 σ = 10		γ = 0.5, σu = 3, σw = 10 σ = 20
	City	22.6268 City	28.6189 28.1328	24.5089 30.9236 34.4698	17.6666 34.5002	25.7233 22.1142	21.2923 27.9811 31.1448	30.7206
	Park Scene 24.1703 Park Scene 28.1322 31.2408	27.5703 33.0157 36.0456	19.7954 35.6443	28.6291 22.2235	24.8378 30.0556 33.2929	32.4186
	Tennis	24.3593 Tennis	32.8574 28.1395	28.3005 35.6816 38.2799	20.1024 38.7244	30.0329 22.3378	25.3632 31.6169 35.8716	35.8702
	Kimono	24.0531 Kimono	33.4449 28.1327	28.0428 36.1713 39.4760	19.6640 39.3243	30.3713 22.1961	25.1521 32.5319 37.0670	36.0030
	Cactus	22.8072 Cactus	29.3197 28.1585	25.0625 32.5979 35.4238	18.0620 35.6019	26.5843 22.2537	21.8379 29.4978 32.5053	32.6742
	Terrace	22.1833 Terrace	27.6801 28.1504	23.6599 30.6325 33.8943	17.5481 34.3474	24.6939 22.3295	20.8275 27.1673 30.3751	30.9289
	Basket	22.3065 Basket	30.5848 28.1327	24.7466 35.3905 37.8205	17.2799 37.9416	27.4412 22.1257	21.0410 32.7217 35.3943	35.3918
	Ducks	22.5534 Ducks	29.2010 28.1313	24.2460 31.2006 34.3445	17.6747 34.0325	26.1324 22.1235	20.9908 28.4948 31.6280	31.2881
	People	People
	On Street	22.8686 On Street	29.9248 28.1428	25.1835 33.2473 36.3971	18.0969 36.6175	26.5102 22.2364	21.9365 29.7624 33.0578	33.3369
	Traffic	23.3136 Traffic	30.3467 28.1397	26.0561 33.7029 36.6627	18.5966 37.0335	27.3527 22.2184	22.8029 30.3626 33.4188	33.4725
	Average	23.1242 Average	30.3219 28.1393	25.7377 33.2564 36.2814	18.4487 36.3768	27.3471 22.2159	22.6082 30.0192 33.3756	33.2105
			γ = 0.6, σu = 1.5, σw = 5 σ = 30		γ = 0.7, σu = 0.5, σw = 5 σ = 40
	City	19.7707 City	26.8971	26.6070 29.1116	24.7772	29.9194	30.8604 32.0709
	Park Scene 22.3302	30.0600	29.3638 30.9035	27.3272	32.9692	33.2040 33.9047
	Tennis	22.6288	31.6209	30.4743 32.1414	27.5478	34.6473	35.4521 35.5719
	Kimono	22.1677	32.1307	30.0747 32.9185	27.1288	35.3970	35.3214 36.0787
	Cactus	20.0310	27.7356	27.1652 30.4155	24.7616	30.5537	31.7316 32.9300
	Terrace	19.2221	25.8385	25.6659 28.3450	23.5627	28.7434	29.2466 31.2265
	Basket	19.2660	28.6660	26.9527 33.6864	24.2184	31.9881	32.4408 36.0480
	Ducks	19.6658	27.4106	26.7592 29.3765	24.5538	30.4115	31.4003 31.7627
	People
	On Street	20.1125	28.0206	27.5219 30.8932	21.5625	29.1066	32.3965 33.6299
	Traffic	20.8035	28.7525	28.3148 31.3647	25.7511	31.9347	33.2198 34.4228
	Average	20.5998	28.7132	27.8899 30.9156	25.1191	31.5671	32.5274 33.7646

Table C .

 C 4: De-noising performances of optimal clustering-based linear mapping learning and BM3D for SDN

	C.1.2 RD curves for optimal clustering C.2 Super-resolution
					Park Scene		Park Scene					41				44	Tennis	Tennis
		39														40				43
	PSNR [dB]	37 35	PSNR [dB]										HEVC Optimal clustering w/ indexes cost 37 38 39 PSNR [dB] 36			PSNR [dB]	40 41 42	SHVC BL	HEVC Optimal clustering w/ indexes cost Optimal clustering w/o indexes
		33 31					SHVC BL K-means + SR BL Optimal clustering + SR BL SHVC EL K-means + SR EL Optimal clustering + SR EL		Optimal clustering w/o indexes cost Indexes cost, K=4, MxN=8x8 Indexes cost, K=16, MxN=8x8 35 34 33 Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4 32			39 38 37 36	K-means + SR BL Optimal clustering + SR BL SHVC EL K-means + SR EL Optimal clustering + SR EL	cost Indexes cost, K=4, MxN=8x8 Indexes cost, K=16, MxN=8x8 Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4
		29														31				35
		0	1000	0	2000		5000 3000		4000	10000 5000		15000 6000		20000	0	1000	0	2000	5000 3000	4000	10000	5000	15000 6000	20000
							Bitrate [kbps]	PSNR (dB) Bitrate [kbps]							PSNR (dB) Bitrate [kbps] Bitrate [kbps]
	Image		Noisy	Optimal clustering LM Kimono Kimono	BM3D 38		Noisy 40	Optimal clustering LM Cactus Cactus	BM3D
		42					γ = 0.5, σu = 1.5, σw = 10	37				39	γ = 0.5, σu = 3, σw = 10
	City Park Scene 24.1703 22.6268 Tennis 24.3593 Kimono 24.0531 Cactus 22.8072 Terrace 22.1833 Basket 22.3065 Ducks 22.5534 PSNR [dB] 38 40 PSNR [dB] 36 34 0 32 0 1000 2000 People On Street 22.8686 Bitrate [kbps] SHVC BL K-means + SR BL Optimal clustering + SR BL 31.3827 34.0137 36.5447 37.8658 32.9804 30.4575 35.6551 31.8332 SHVC EL K-means + SR EL Optimal clustering + SR EL 5000 10000 3000 4000 33.4185 Bitrate [kbps] Traffic 23.3136 34.1739 Terrace 38 Terrace	30.9236 33.0157 35.6816 36.1713 32.5979 30.6325 35.3905 31.2006 Optimal clustering w/ indexes cost HEVC Optimal clustering w/o indexes cost Indexes cost, K=4, MxN=8x8 Indexes cost, K=16, MxN=8x8 Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4 34 35 36 PSNR [dB] 33 32 31 30 15000 20000 5000 29 0 33.2473 33.7029 40	2000	17.6666 19.7954 20.1024 19.6640 18.0620 17.5481 17.2799 17.6747 33 34 35 37 38 PSNR [dB] 36 32 0 5000 4000 6000 18.0969 Bitrate [kbps] SHVC BL 29.1100 32.2189 34.8505 36.1711 30.8396 27.9752 33.6653 29.8164 K-means + SR BL Optimal clustering + SR BL SHVC EL K-means + SR EL Optimal clustering + SR EL 10000 15000 20000 25000 30000 35000 40000 45000 27.9811 30.0556 31.6169 32.5319 29.4978 27.1673 32.7217 HEVC Optimal clustering w/ indexes cost Optimal clustering w/o indexes cost Indexes cost, K=4, MxN=8x8 Indexes cost, K=16, MxN=8x8 Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4 28.4948 8000 10000 12000 14000 30.9121 Bitrate [kbps] 29.7624 18.5966 31.9198 30.3626 41 Basket Basket
	Average 36		23.1242					33.8326			33.2564 39		18.4487 40	31.7479	30.0192
	City Park Scene 22.3302 19.7707 Tennis 22.6288 Kimono 22.1677 PSNR [dB] 32 34 PSNR [dB] 30 Cactus 20.0310 Terrace 19.2221 28	γ = 0.6, σu = 1.5, σw = 5 30.0145 33.1917 35.8497 37.1747 HEVC Optimal clustering w/ indexes cost 29.1116 30.9035 32.1414 32.9185 Optimal clustering w/o indexes cost SHVC BL 36 37 38 PSNR [dB] K-means + SR BL 35 Optimal clustering + SR BL SHVC EL 34 31.7938 30.4155 28.9016 28.3450 Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4 32 Optimal clustering + SR EL Indexes cost, K=4, MxN=8x8 Indexes cost, K=16, MxN=8x8 K-means + SR EL 33		24.7772 27.3272 27.5478 27.1288 37 38 39 PSNR [dB] 36 24.7616 23.5627 34 35	γ = 0.7, σu = 0.5, σw = 5 32.5389 35.3929 37.8144 39.1840 HEVC Optimal clustering w/ indexes cost 32.0709 33.9047 35.5719 SHVC BL K-means + SR BL Optimal clustering + SR BL Optimal clustering w/o indexes cost SHVC EL 36.0787 34.0870 31.4077 31.2265 Indexes cost, K=16, MxN=4x4 Indexes cost, K=8, MxN=4x4 32.9300 Indexes cost, K=4, MxN=8x8 Indexes cost, K=16, MxN=8x8 K-means + SR EL Optimal clustering + SR EL
	Basket 26 Ducks 0	5000	19.2660 19.6658 0 10000 10000 Bit-rate [kbps] 20000 15000		34.5423 30.6962 30000 40000 20000 25000 Bitrate [kbps]	50000	33.6864 31 29.3765 60000 70000 0	24.2184 33 24.5538 0 5000 2000 4000	36.4812 32.7761 15000 20000 25000 6000 10000 8000 Bitrate [kbps] Bitrate [kbps]	30000 10000	36.0480 35000 40000 31.7627
	People							36		People on Street	Ducks				Traffic
	On Street		20.1125			35		31.9777			30.8932		21.5625 43	34.5815	33.6299
	Traffic Average	PSNR [dB]	20.8035 20.5998		PSNR [dB]	33 34 32 31		33.0412 32.7183	31.3647 30.9156 SHVC BL K-means + SR BL Optimal clustering w/ indexes cost HEVC Optimal clustering + SR BL 25.7511 25.1191 39 41 PSNR [dB]	35.6138 34.9877	34.4228 33.7646 Optimal clustering w/ indexes cost HEVC
									30				Optimal clustering w/o indexes cost SHVC EL			37	Optimal clustering w/o indexes cost
													Indexes cost, K=4, MxN=8x8 K-means + SR EL			Indexes cost, K=4, MxN=8x8
									29				Indexes cost, K=16, MxN=8x8 Optimal clustering + SR EL	35	Indexes cost, K=16, MxN=8x8
									28				Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4				Indexes cost, K=8, MxN=4x4 Indexes cost, K=16, MxN=4x4
									27											33
				0	10000	20000	0	30000 5000	40000 10000	50000 15000 20000	60000 25000	30000	35000	0 40000	10000	20000	30000	40000	50000
											Bitrate [kbps]		Bitrate [kbps]				Bitrate [kbps]
		Figure C.1: RD performance of the test sequences using the optimal clustering, with
		and without the cluster indexes rate-cost

©1999-2015 Warner Bros.

Co-authored publication

Co-authored publication

L'efficacité des services de compression vidéo est de nos jours un enjeu essentiel, et est appelé à le devenir d'autant plus dans le futur, comme l'indique la croissance constante du trafic vidéo et la production de nouveaux formats tels que la vidéo à haute résolution, à gamme de couleur ou dynamique étendues, ou encore à fréquence d'images augmentée. Le standard MPEG HEVC est aujourd'hui un des schémas de compression les plus efficaces, toutefois, il devient nécessaire de proposer de nouvelles méthodes originales pour faire face aux nouveaux besoins de compression.En effet, les principes de bases des codecs modernes ont été conçus il y a plus de 30 ans : la réduction des redondances spatiales et temporelles du signal en utilisant des outils de prédiction, l'utilisation d'une transformée afin de diminuer d'avantage les corrélations du signal, une quantification afin de réduire l'information non perceptible, et enfin un codage entropique pour prendre en compte les redondances statistiques du signal. Dans cette thèse, nous explorons de nouvelles méthodes ayant pour but d'exploiter d'avantage les redondances du signal vidéo, notamment à travers des techniques multipatchs. Dans un premier temps, nous présentons des méthodes multi-patchs basées LLE pour améliorer la prédiction Inter, qui sont ensuite combinées pour les prédiction Intra et Inter. Nous montrons leur efficacité comparée à H.264. La seconde contribution de cette thèse est un schéma d'amélioration en dehors de la boucle de codage, basé sur des méthodes de débruitage avec épitome. Des épitomes de bonne qualité sont transmis au décodeur en plus de la vidéo encodée, et nous pouvons alors utiliser coté décodeur des méthodes de débruitage multi-patchs qui s'appuient sur les patchs de bonne qualité contenus dans les épitomes, afin d'améliorer la qualité de la vidéo décodée. Nous montrons que le schéma est efficace en comparaison de SHVC. Enfin, nous proposons un autre schéma d'amélioration en dehors de la boucle de codage, qui s'appuie sur un partitionnement des patchs symétrique à l'encodeur et au décodeur. Coté encodeur, on peut alors apprendre des projections linéaires pour chaque partition entre les patchs codés/décodés et les patchs sources. Les projections linéaires sont alors envoyées au décodeur et appliquées aux patchs décodés afin d'en améliorer la qualité. Le schéma proposé est efficace comparé à HEVC, et prometteur pour des schémas scalables comme SHVC.

Remerciements

Epitome encoding

The texture epitomes are sent in addition to the complete sequence with a higher quality. Much information of the epitome texture is actually contained in the lower quality decoded frame from which it is extracted. We only need to encode the residue between the source epitome patches and the corresponding patches in the decoded frame.

For this task, we use the scalable extension of HEVC, SHVC (see section 1.2.3). For all applications, the encoded frames are used as base layer (BL), and the texture epitome are considered as the enhancement layer (EL). The non-epitome blocks of the EL are directly copied from the BL, thus their rate-cost is practically non-existent.

In Fig. 3.17, we show an example of epitomes encoding for the first application.

Inter-layer prediction

Inter-frame prediction Figure 3.17: Epitomes are encoded using a scalable scheme. The encoded sequence is used as the base layer, while the epitome is considered as the enhancement layer. Note that the epitomes can then be predicted from the base layer as well as previously encoded epitomes.

For the first application, the quantization parameter (QP) for the EL has to be selected carefully, since a trade-off must be achieved between the quality of the epitomes received at the decoder, which will impact the de-noising performance, and the additional bit-rate associated with the epitomes. The QP value of the EL will also depend on the QP value of the BL, in order to limit the bit-rate of the epitomes with respect to the bit-rate of the BL (see section 3.3.5.2).

For the second and third applications, the QP value of the EL is the same as the EL of the scalable scheme to which we compare our performances.

Considering multivariate linear regression, the problem is of searching for the function P minimizing:

which is of the form ||Y -XB|| 2 (corresponding to the linear regression model Y = XB + E). The minimization of Eq. (3.30) gives the least squares estimator

We finally obtain the de-noised patch by applying the learned mapping to the current patch:

The method is illustrated in Fig. 3.21.

Simulation and results

In this section, the epitome-based methods described in the previous section are applied in the proposed schemes described in section 3.3.1. Four test sequences of resolution 352 × 288 are used: City, Foreman, Macleans, and Mobile. For each sequence, one GOP of 8 frames is processed. In the case of the first application in a single layer scheme, the epitome of the first key frame of the following GOP is also used. The sequences are encoded with the HEVC test model HM (ver 15.0) [START_REF][END_REF] using the Main profile in Random Access, with 4 values for the Quantization Parameter, QP = 22, 27, 32, 37.

For the second and third applications, SNR and spatial scalablity, we compare our performance with the SHVC scalable scheme. For SNR scalability, the sequences encoded with HEVC as described above are used as base layer, and the enhancement layer is encoded with the SHVC test model SHM (ver. 9.0) [83], with QP = 18, 23, 28, 33. For spatial scalability, the base layer is down-sampled with a factor 2, and encoded with the HEVC test model HM (ver 15.0) using the Main profile in Random Access, with 4 values for the Quantization Parameter, QP = 22, 27, 32, 37. The enhancement layer is encoded with the SHVC test model SHM (ver. 9.0), with QP = 22, 27, 32, 37.

De-noising with source epitome

In this section we evaluate the epitome-based de-noising performances for the first application. In order to obtain the full potential of the method, the epitome is considered known without any loss. In practice, this means the epitome would be encoded using lossless coding.

Average results for the GOP of the test sequences are given in Table 3.8. Overall, the proposed methods are more efficient at low bit-rates, i.e. for stronger quantization noise. The proposed methods also benefit from bigger epitomes (lower ε M ), since more information on the source signal is available. We can see that the epitome-based BM3D

Algorithm 2 K-means algorithm

Input: clusters number K, p × n data matrix X = {xi}i=1...n Output: cluster set C = {Ci|i = 1 . . . K} Repeat the two following steps until convergence: Assignment step:

Let us first formally define the problem. The underlying density p(x) can be formally expressed as:

where p k (x|z k , θ k ) is a mixture component, with z = (z 1 , . . . , z K ) is a vector of binary indicator, with only one component equal to 1, and the others are 0. For each point x i , z i is a random variable which represents the mixture component which generated x i . Each component is a multivariate Gaussian density, expressed as:

and

The mixture weights α k = p(z k ) represent the probability that a random point x was generated by the component k, and

The complete set of parameters for the mixture model is Θ = {α 1 , . . . , α K , θ 1 , . . . , θ K }.

Given the set of points X = {x i } i=1...n , the problem in hand is to estimate the n×K latent variables matrix Z = {z i } i=1...n and the model parameters Θ. The estimates are obtained using the Expectation -Maximization (EM) algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], a generic iterative method to find maximum likelihood estimates of the latent variables and parameters of a model. The EM algorithm to estimate the GMM is given in Algorithm 3, where the initial parameters Θ (0) are considered known. The initial parameters are usually obtained by randomly selecting K points from the data set to initialize the means, and set the covariance of the whole data set for each of the K covariance matrices. The mixture weight α k are set homogeneously with the value 1 K . Note that the EM algorithm does not produce directly the latent variables matrix Z, but instead a n × K "membership probability" matrix W. The latent variable z i can be obtained from W by taking the i-th row and set the maximum value to 1 and the other values to 0.

Algorithm 3 EM algorithm for GMM

Input: clusters number K, p × n data matrix X = {xi}i=1...n Output: n × K "membership probability" matrix W, parameters Θ Repeat the two following steps until convergence: Expectation step: For each point xi, compute its membership probability with respect to each cluster k, given the parameters Θ (t) :

Spectral clustering

Spectral clustering is one of the most popular modern clustering algorithms [START_REF] Uw | On spectral clustering: Analysis and an algorithm[END_REF], and usually outperforms the K-means algorithm. The main idea of spectral clustering is to defines a similarity graph, in which each vertex represents a data point, and each edge between two vertices is weighted with the similarity between these two vertices. The clusters are obtained by grouping the vertices of the graph which have strong connections, i.e. strong weights on their edges. Formally, the spectrum (eigenvalues) of the similarity matrix is used to perform dimensionality reduction, to finally perform clustering (e.g. K-means) in the reduceddimensions space. A detailed algorithm is given in Algorithm 4.

Supervised learning

Supervised learning is a field of machine learning which aims at learning a predictive model linking input data to a target signal. Here we are interested in the specific task of classification, where the signal to be learned consists in class labels, contrary to regression which consists in learning a continuous signal. In this case, the predictive model is also called a classifier.

The usual workflow of supervised learning consists in a first training phase, where the model is learned, followed by a prediction phase, where new data points will be assigned to a class using the predictive model.

We consider that the data points, noted x, belong to a p dimensional space. Their corresponding class labels will be noted y. The corresponding class labels belong to a for i = j, and Ai,i = 0 Define the diagonal matrix D, such that Di,i = j Ai,j, and compute the graph Laplacian matrix:

Compute the K first eigenvectors of L, u1, . . . , uK and form the n × K matrix U whose columns are the eigenvectors u1, . . . , uK Form the matrix V from U by re-normalizing its rows:

Considering each row of V as a point in a K-dimensional space, cluster them into K clusters C = {C i |i = 1 . . . K} using the K-means algorithm Assign a point xi to a cluster Cj if and only the i-th row of V was assigned to the cluster C j limited set of integer values S c . A training set D T contains n pair of input point / label:

In this section, we present two popular methods for supervised learning: Support Vector Machine (SVM) and decision trees. Note that we are only interested in presenting the classifier models associated with these two methods, and the algorithm using these models to predict the class of new data points. However, we will not explore the algorithms used to learn these classifiers.

Support Vector Machine

The Support Vector Machine (SVM) was introduced in [START_REF] Cortes | Support-vector networks[END_REF] for binary classification.

Linear SVM Considering that the training data are labeled into two classes, S c = {-1, 1}, the SVM aims at constructing an hyperplane which will separate the two classes with a maximum margin (see Fig. 4.1).

An hyperplane is formally described by the set of points x satisfying the following equation:

where w is a vector orthogonal to the hyperplane and b is a scalar. The SVM searches for the maximum-margin hyperplane described by (w, b), which satisfies the following binary classification constraints: metric [START_REF] Bjontegaard | Calculation of average PSNR differences between RD-curves[END_REF] with respect to the sequences encoded with HEVC.

In average over all the sequences and all the GOPs, the bit-rate is reduced by 1.662 %. We can see that except for 3 sequences (ParkScene, Tennis, Kimono), we obtain a bit-rate saving of about 1-2 %, and we reach about 8 % for the Terrace sequence. For the fifth GOP of this sequence, we even reach about 12 % bit-rate reduction. In this section, the number of clusters K is adaptive and selected using the binary tree RDO method described in section 4.2.3.2. Experiments were performed using the K-means clustering and the same sequences and parameters as in section 4.2.6.1. RD performances are shown in Table 4.7. Comparison with performances using a fixed K = 10 presented in Table 4.6 show that we now obtain better performance for most of the sequences. We report in Table 4.8 the selected values of K, averaged over all the GOPs. We can see that the K values adapt to the sequence, reaching higher values for sequences with a higher resolution and/or frame rate. The K values depend on QP , and lower values are selected at low bit-rate (high QP value).

Clustering

The clustering is performed either with the K-means algorithm or the optimal clustering, as preliminary results from section 4.4.1 showed their efficiency. Note that the optimal clustering represents an upper bound on the performances, but as in the previous chapter, would require the transmission of the cluster indexes to be used at the decoder side. The results in section 4.4.5 are obtained with a fixed K = 10 clusters, but the method described in section 4.2.3.2 to adaptively select K is still valid.

Linear mappings encoding

The proposed method for super-resolution does not imply any changes to encode the linear mappings compared to the de-noising method. Therefore, the linear mappings are encoded as described in section 4.2.4.

Simulations and results

The test sequences are presented in Table 4.5. Here, only the first GOP of the sequences was processed.

The BL sequences are obtained by down-sampling the source sequences by a factor 2 using the SHVC filter. The BL sequences are then encoded with the HEVC test model HM (ver 15.0) [START_REF][END_REF] using the Main profile in Random Access, with 4 values for the Quantization Parameter, QP = 22, 27, 32, 37. The decoded BL sequences are upsampled with the SHVC filter or with our super-resolution method. The up-sampled versions (SHVC filter or super-resolution) of the BL encoded at QP = 22 is then used to encode the EL with the SHVC test model SHM (ver. 9.0), with QP = 24, 29, 34, 39. Note that the two up-sampled BL sequences are used as external base layer thanks to the hybrid codec scalability feature of SHVC.

For all the experiments, the linear mappings are encoded as described in section 4.2.4 using the range extension of HEVC [START_REF] Sullivan | Standardized extensions of high efficiency video coding (HEVC)[END_REF][91] (HM 15.0 RExt 8.1) with a fixed QP = -30.

First, the super-resolution was performed using the K-means clustering. The RD performances of both the BL and the EL are given in Table 4.20, evaluated with the Bjontegaard measures compared to the SHVC filter. We can see that even if significant bit-rate reduction can be achieved with the super-resolved BL compared to the SHVC filter (up to 40% for the Terrace sequence), these gains are not reported on the EL. In fact, the inter-layer reference frames used for the prediction of the EL are in competition with the other reference frames previously decoded from the EL. The latter are usually of better quality than the former, and the gains obtained with the super-resolution are not enough to make a difference when encoding the EL.

In the second experiment, the super-resolution was performed with the optimal clustering. Note that here the cost of the cluster indexes was not taken into account, thus the results we give are an upper bound. The RD performances of both the BL and the EL are given in Table 4.21. Here, we can see that the gains brought by the optimal

Application in the compression context

Transmission of a classifier model

The results above demonstrate that the proposed scheme based on classification can be useful to recover the optimal cluster labels. These results correspond to the scheme of Fig. 4. [START_REF] Wige | Sample-based weighted prediction with directional template matching for HEVC lossless coding[END_REF], where the classifier model C has to be sent to the decoder. Here, we analyze the different classifier models, given their description in section 4.1.2, and give an estimation of their rate cost. Results assessing the de-noising performances depending on the models complexity are also given. These results are obtained with K = 2 classes.

Support Vector Machine (SVM)

The results from the previous section show that the classification performances of the linear SVM are limited. Thus, in this section, we only consider the case of the non-linear Gaussian SVM. The classifier model for the SVM consists in a set of hyperplanes, which have to be sent to the decoder in our context. However, in the case of the non-linear SVM, the hyperplanes can not be computed explicitly. Instead, the classification relies on the knowledge of the support vectors and their labels (see Eq. 4.15 in section 4.1.2.1). The support vectors belong to the training set, and are in our case feature vectors, which will have in practice to be signaled to the decoder, along with their class labels. To estimate the corresponding rate, we can consider that the value 0 is associated with the non-support vectors, while the class label is associated with the support vectors. The distribution of these values is not expected to be homogeneous, we can thus consider compressing this additional information using entropy or arithmetic coding.

As shown in Fig. 4.22, increasing the number of support vectors increases the denoising performances, but will require a larger cost in terms of bit-rate. The number next to each point of the curves indicates the percentage of the right optimal labels recovered. The results for QF = 25 and QF = 75 are similar to the one below, and given in annex in section C.3.3.

Author's publications

Abstract

Efficient video compression is nowadays a critical issue, and is expected to be more and more crucial in the future, with the ever increasing video traffic and the production of new digital video formats with high resolution, wide color gamut, high dynamic range, or high frame rate. The MPEG standard HEVC is currently one of the most efficient video compression scheme, however, addressing the future needs calls for novel and disruptive methods.

In fact, the main principles of modern video compression standards rely on concepts designed more than 30 years ago: the reduction of spatial and temporal redundancies, through prediction tools, the use of a transform to further reduce the inner correlations of the signal, followed by quantization to remove non-perceptive information, and entropy coding to remove the remaining statistical redundancies. In this thesis, we explore novel methods which aims at further exploiting the natural redundancies occurring in video signals, notably through the use of multi-patches techniques. First, we introduce LLE-based multi-patches methods in order to improve Inter prediction, which are then combined for both Intra and Inter predictions, and are proven efficient over H.264. We then propose epitome-based de-noising methods to improve the performances of existing codecs in a out-of-the-loop scheme. High quality epitomes are transmitted to the decoder in addition to the coded sequence, and we can then use at the decoder side multi-patches de-noising methods relying on the high quality patches from the epitomes, in order to improve the quality of the decoded sequence. This scheme is shown efficient compared to SHVC. Finally, we proposed another out-of-the-loop scheme relying on a symmetric clustering of the patches performed at both encoder and decoder sides. At the encoder side, linear mappings are learned for each cluster between the coded/decoded patches and the corresponding source patches. The linear mappings are then sent to the decoder and applied to the decoded patches in order to improve the quality of the decoded sequence. The proposed scheme improves the performances of HEVC, and is shown promising for scalable schemes such as SHVC.

Résumé