Soutenance mémoire
Codage de source par transformée
Un signal est décomposé en N composantes au moyen d’une transformée inversible ; Ces composantes sont ensuite quantifiées (scalairement ou vectoriellement) et peuvent éventuellement subir un codage entropique ; la transformée inversible est appliquée à la reconstruction (e.g. codage en sous-bandes, codage en ondelettes ou paquets d’ondelettes d’un signal 1D ou d’images 2D). Le taux global est le nombre moyen de bits codés par échantillons, et se trouve être toujours additif : R =Xiαiri (1.7) où ri est le nombre moyen de bits codés par échantillons de la ième composante. Par conséquent, le facteur αi est le nombre moyen d’échantillon dans une composante par échantillon du signal. Les valeurs des αi peuvent être différentes, puisque la transformée peut introduire des taux d’échantillonnage différents sur chaque composante.
Corpus de test
Pour illustrer, valider et comparer nos algorithmes, nous avons besoin d’effectuer des simulations sur des fonctions représentatives des différents type de problèmes rencontrés en allocation de ressources. Nous avons donc créé plusieurs ensembles de fonctions de simulation Di(Ri) en essayant de couvrir la plupart des situations. Pour ce faire, nous avons mis en place des ensembles Di(Ri) comprenant Mi = 25 points par composantes dans l’intervalle 0 6 Ri 6 6. Nous avons créé N = 8 composantes de formes différentes. La création s’est faite à partir d’un contexte de codage de source où différents types de quantificateurs se sont vus appliqués à une source gaussienne sans mémoire de variance σ2 = 1. En choisissant différents coefficients σ2i qui représentent la variance de chaque composante i, on obtient un nombre virtuellement infini d’ensembles possibles (Ri, σ2i Di). Les taux uniformément espacés (e.g. entiers) ont été obtenus par des quantificateurs scalaires de type Lloyd-Max et un ensemble de quantificateurs vectoriels optimisés de dimension 2, 4 ou 8. Nous avons obtenu des taux non-uniformément espacés en utilisant des codeurs entropiques. Notons qu’après selection des points d’enveloppe (par l’algorithme RDPE) d’un ensemble de points régulièrement espacés, mais non convexe, Di(Ri) , nous obtenons un ensemble convexe à taux non régulièrement espacés. Dans ce cas, nous parlons de taux “uniformément espacé à trous”. En résumé, nous avons classé nos ensembles de fonctions de simulations selon le caractère convexe (ou pas) des fonctions Di(Ri), et la régularité des taux Ri (à savoir : taux uniformément espacés avec ou sans “trous” ou taux non-uniformément espacés). Nous considérerons donc les cinq types de fonctions :
– Convexe à taux Uniformément répartis (CU),
– Convexe à taux Uniformément répartis avec trous (CUT),
– Non-Convexe à taux Uniformément répartis (NCU),
– Convexe à taux Non-Uniformément répartis (CNU),
– Non-Convexe à taux Non-Uniformément répartis (NCU).
Des exemples sont illustrés aux figures B.1–B.8, regroupées en annexe B. Nous observons que pour B.4 et B.7 les courbes optimales R-D sont non-convexes même si tous les Di(Ri) sont convexes. Cela est dû à la répartition non uniforme des taux Ri . On peut ainsi remarquer un nombre important de points optimaux n’appartenant pas à l’enveloppe convexe : ce sont les points cachés.
Approches suivant le domaine considéré
Approche taux-distorsion Le problème d’allocation de ressources sous contrainte est, en codage de source, un problème classique depuis longtemps mis en évidence et étudié. Initialement, Huang et Schultheiss [HS63] l’abordèrent dans le cadre de leurs travaux prouvant l’optimalité de la transformée de KarhunenLoeve, et depuis, le problème a été abondamment traité, sous différentes formes et hypothèses, dans des conditions diverses. De par la définition que nous avons faite du problème d’allocation de ressources, inspirée du monde du codage de source, l’ensemble des éléments théoriques et des méthodes de cette thèse s’appliquent pratiquement de manière directe. Nous avons essayé de rendre l’écriture des algorithmes présentés la plus générale possible en gardant un contexte et des notations unifiés.
Approche taux-puissance Les systèmes de modulation discrète multi-tons, Discrete Multi-Tone modulation (DMT) en anglais, furent les premiers à introduire cette notion d’allocation de ressources en codage de canal. C’est Hughes-Hartogs [Huga] qui, au travers d’un patent, mis le premier en œuvre ce genre de méthode. Plus généralement, les systèmes de modulation multi-porteuses sont aujourd’hui à l’origine d’une conséquente bibliographie sur le problème d’allouer une puissance (ou un taux) sous une contrainte de budget. Cela est essentiellement dû au succès du domaine d’application : systèmes de communication xDSL et systèmes de transmission sans fil sont en développement constant et représentent des enjeux commerciaux considérables. Il est important de noter que le taux a été très souvent considéré comme entier (on y fait référence comme des bits). Cela n’est pourtant pas une obligation. Cette hypothèse permet de grandement simplifier les méthodes de résolution du problème d’allocation de ressource mais elle n’est pas forcément exclusive. D’autre part, les fonctions considérées sont toujours implicitement supposées convexes. Si cette hypothèse paraît vraisemblable, elle ne suffit pas à elle seule à garantir l’optimalité de certaines méthodes.
Autres approches Nous avons essentiellement étudié les problèmes issus des communications numériques. Il existe toutefois des articles plus généraux [Eve63, Fox66] ou provenant de domaines différents qui tentent de résoudre le même problème. On l’utilise ainsi pour modéliser des situations (quelquefois en tant que sous-problème) telles que :
– dans des systèmes d’aide à la gestion de portefeuille : on souhaite alors équilibrer sélectivité et diversification afin de trouver le meilleur rapport entre rendement et risque pour un capital placé sur plusieurs actifs financiers ;
– dans le chargement de bateau ou d’avion : tous les bagages à destination doivent être amenés, sans être en surcharge ;
– dans la découpe de matériaux : pour minimiser les chutes lors de la découpe de sections de longueurs diverses dans des barres en fer ;
– …
Autant de problèmes plus ou moins originaux qui, de par leur modélisation, se ramènent à la description faite dans ce manuscrit du problème d’allocation de ressource. Une autre raison de s’intéresser à ce type de problème d’allocation est son apparition dans certaines utilisations de méthodes de génération de colonnes (ainsi pour le problème de « bin packing »). Les variables ont alors une réalité toute autre, et les contraintes de fonctions sont parfois différentes. Nous citerons à titre d’exemple le problème bien connu du sac à dos à variables binaires qui est un cas particulier de notre étude pour laquelle les Mi = 2 (N quelconque) et où les fonctions employées sont de taux régulièrement espacés à trous. Nous pourrons de toute manière toujours ramener ces problèmes à la définition initiale faite au premier chapitre du problème d’allocation de ressources.
Principes de recherche de points optimaux
De la découverte d’un point optimal dans un triangle ∇h par la relation ≺ découle une modification de la zone de recherche des points optimaux. En effet si on trouve par la relation d’ordre un point P1 = (R1, D1) dans le triangle caché, il est alors optimal (par le théorème 4.2.2). Dans ce cas, tout point P = (R, D) appartenant à la région rectangulaire entre P1 et Q0 ne peut être optimal, puisque R1 < R et D1 < D. Ce résultat permet de réduire grandement la zone de recherche de points optimaux cachés. En effet, la zone de recherche exclut désormais la partie hachurée dans 4.1 (car déjà étudiée) et le rectangle entre Q0 et P1. Celle-ci se résume à la réunion de deux triangles rectangles. Ces traingles sont illustrés figure 4.2 et sont définis à partir des points Q1 et Q2 déduits de P1. Ces deux nouveaux points fictifs Q1 et Q2 reprennent le rôle de Q0 dans leur triangle respectif. Ainsi, si Q0 = (R0, D0) et P1 = (R1, D1), les valeurs de ces points sont : Q1 = (R1, D0) et Q2 = (R0, D1). Les points cachés recherchés dans le triangle associé à Q1 seront donc majorés (au sens de la relation d’ordre ≺) par Q1 et les points cachés recherchés dans le triangle associé à Q2 majorés par Q2. Nous noterons que la caractérisation du triangle initial de recherche de points optimaux {D <D0, R < R0, P ≺ (R0, D0)} peut simplement s’adapter à la caractérisation d’un des deux triangles en remplaçant R0 par R1 pour le triangle de Q1 et et D0 par D1 pour le triangle de triangle de Q2. Ainsi nous avons un procédé d’implémentation particulièrement simple et efficace. Au fur et à mesure que nous trouverons des points cachés {P1, P2, . . . , Pj, . . .}, nous définirons autant de nouveaux couples de points fictifs dont les taux et distortions dépendront des {Rj} et {Dj} et de leurs positions respectives. Nous aurons alors autant de triangles à étudier, la recherche se finissant lorsque le dernier triangle étudié est complètement parcouru. Ainsi décrit, nous noterons que le principe de tri peut s’appliquer à la recherche de tous les points optimaux. Les zones de recherche sont alors les triangles cachés ∇h successifs, caractérisés par des multiplicateurs critiques qui nous sont donnés par l’algorithme D. L’ensemble des points trouvés au final permet de résoudre le problème de la courbe optimale R-D.
Description d’un algorithme sous-optimal de recherche par omission d’index
L’algorithme L s’applique sur une unique composante i par l’intermédiaire de l’opération d’omission d’index Eκ. En appliquant l’opération Eκ sur chacune des composantes i avec des κ différents quelconques pour chacune d’elle, on obtient autant d’enveloppes convexes. Ces enveloppes diffèrent de l’enveloppe convexe initiale dans une région définie par les points d’enveloppe dont les multiplicateurs critiques correspondent aux points retirés par Eκ. Si nous appliquons Eκ à un point d’enveloppe ke en prenant successivement κ = kei avec i = {1, . . . , N}, nous génèrons alors un ensemble de points autour de la zone de ke. En particulier, nous trouvons un certain nombre de points dans le triangle caché situé entre ke et son successeur. Ainsi, lorsque que nous recherchons une solution au problème d’allocation de ressources pour un budget Rb, nous nous intéressons à un triangle particulier défini par un point d’enveloppe ke et son successeur (le triangle ∇hb), et l’application successive de Ekei sur chaque composante i permet de générer un certain nombre de points cachés, et donc de solutions potentielles. Il ne restera plus qu’à faire un tri sur l’ensemble de ces points dont le nombre est relativement restreint. Nous pouvons donc décrire une procédure efficace de recherche sous la forme de l’algorithme M.
Considérations pratiques d’adaptation de la recherche par chemins convexes
Prenons le problème d’allocation de ressources contraint par un budget Rb où les fonctions Di(Ri) sont convexes. Comme mentionné précédemment, nous allons modifier l’algorithme J pour ne parcourir que les chemins convexes issus de la solution de Shoham-Gersho pour le budget Rb. Dans la procédure décrite au chapitre 3, il faut alors modifier l’étape d’initialisation en ne prenant dans P que le point solution de l’algorithme D. Ce choix de restreindre les points de départ à un unique vecteur d’allocation nous permet d’aller encore plus loin, car la zone d’étude s’en trouve immédiatement très réduite. Nous savons que les points candidats à la résolution du problème sont forcément situés dans le triangle ∇hb . La zone de recherche de points cachés R initiale correspond donc ici à ∇hb . Or, notre algorithme va successivement appliquer des opérations élémentaires ∆~ en partant du point (R(k SG), D(kSG)) solution de Shoham-Gersho. On n’aura aucun intérêt à appliquer des opérations élémentaires ∆~ telle que ∆( ~ kSG) = k′ ∈ ∇/hb : celles-ci ne sont donc pas à considérer pour la construction des chemins convexes employés dans l’algorithme.
|
Table des matières
Remerciements
Résumé
Abstract
Table des figures
Liste des tableaux
Liste des algorithmes
Liste des abréviations et notations
Introduction
1 Le problème d’allocation de ressources
1.1 Introduction
1.2 Présentation du problème
1.3 Problèmes duaux
1.4 Applications
1.4.1 Codage de source par transformée
1.4.2 Codage multi-canaux
1.5 Définitions et propriétés fondamentales
1.5.1 Points optimaux
1.5.2 Points d’enveloppe
1.5.3 Considérations autour des alignements
1.5.4 L’opération élémentaire ∆~
1.5.5 Points cachés
1.6 Corpus de test
1.7 Critères de comparaison
1.7.1 Critères théoriques
Complexité
Coût mémoire
1.7.2 Critères expérimentaux
Temps de calcul moyen
Pourcentage de points optimaux
Perte en distorsion moyenne
1.8 Conclusions
2 L’état de l’art
2.1 Introduction
2.2 Approches envisagées
2.2.1 Approches suivant le domaine considéré
Approche taux-distorsion
Approche taux-puissance
Autres approches
2.2.2 Approches suivant la méthode considérée
Approche continue
Approche lagrangienne
Autres approches
2.3 Méthodes de recherche de points d’enveloppe du plan global
2.4 Méthodes de recherche de points cachés du plan global
2.5 Performances
2.6 Conclusions
3 Recherche optimale par chemins convexes
3.1 Introduction
3.2 Définition du concept de chemin convexe
3.3 Mise en place d’un critère de recherche efficace
3.4 Description d’un algorithme optimal de recherche par chemins convexes
3.5 Performances
3.6 Conclusions
4 Recherche optimale par ordonnancement
4.1 Introduction
4.2 Définition d’une nouvelle relation d’ordre
4.3 Principes de recherche de points optimaux
4.4 Méthode efficace de parcours des points ordonnés du plan global
4.5 Description d’un algorithme optimal de recherche par ordonnancement
4.6 Performances
4.7 Conclusions
5 Recherche sous-optimale par omission d’index
5.1 Introduction
5.2 Définition de l’opération d’omission d’index
5.3 Nouvelle enveloppe convexe par omission d’index
5.4 Description d’un algorithme sous-optimal de recherche par omission d’index
5.5 Performances
5.6 Conclusions
6 Recherche sous-optimale par chemins convexes
6.1 Introduction
6.2 Considérations pratiques d’adaptation de la recherche par chemins convexes
6.3 Description d’un algorithme sous-optimal de recherche par chemins convexes
6.4 Performances
6.5 Conclusions
Conclusions et perspectives
A Equivalence des courbes optimales réciproques
B Corpus de test
C Calculs de complexité et de coût mémoire d’algorithmes
C.1 Algorithme A
C.2 Algorithme B
C.3 Algorithme D
C.4 Algorithme E
C.5 Algorithme G
C.6 Algorithme H
Bibliographie
Télécharger le rapport complet
