Le tatouage des signaux audio numériques, outre ses applications de protection de la propriété intellectuelle, révèle la possibilité d'utiliser le signal audio numérique comme un support de communication: une information peut être insérée imperceptiblement dans un signal audio et être ainsi diffusée en suivant le même canal de transmission que celui emprunté par le signal audio. Concevoir un système de tatouage performant est l'objectif de ces travaux de thèse. Cette performance relève de contraintes et d'enjeux spécifiques: l'insertion du tatouage doit (1) être transparente (inaudible), (2) offrir un débit de transmission le plus élevé possible pour une fiabilité de transmission la meilleure possible tout en étant robuste à un ensemble de perturbations (traitements licites qui peuvent être effectués sur un signal audio lors de son parcours dans un réseau de diffusion) et (3) être peu coûteux en temps de calcul pour permettre une implémentation temps réel. Pour satisfaire au mieux la contrainte de transparence, un module de contrôle d'inaudibilité innovant, adjacent au modèle psychoacoustique utilisé pour la mise en forme spectrale du tatouage, est proposé. Ce module, basé sur l'algorithme de mesure objective de la qualité sonore PEAQ, établit de façon adaptative les conditions de transparence locale du tatouage en fonction du signal audio. Atteindre une fiabilité de transmission élevée et garantir la robustesse aux perturbations (telles que la compression MPEG, les changements de format, les filtrages, etc.) constituent la majeure partie de ce travail. La prise en compte, ces dernières années, de la connaissance du bruit audio pour la construction du tatouage a permis de très nettes avancées dans ce domaine tant sur la formalisation du problème de tatouage que sur les performances à escompter des systèmes, dit informés, qui en découlent. La majorité des systèmes de l'État de l'Art s'est concentrée sur la recherche d'un tatouage robuste souvent au détriment de la contrainte d'inaudibilité. A l'inverse, nous proposons différentes stratégies d'insertion du tatouage qui établissent en premier lieu l'inaudibilité locale du tatouage et maximisent ensuite la robustesse de sa transmission aux perturbations. Les performances du système et l'efficacité des stratégies d'insertion proposées sont établies sur des signaux audio réels et comparées à des systèmes de la littérature: une transmission "audible mais non gênante" avec un TEB de 0,001 peut être obtenue pour un débit de 170 bit/s en l'absence de perturbations (contre 80 bit/s pour une insertion non informée); le débit devra être fixé à 75 bit/s pour garantir la robustesse aux perturbations non désynchronisantes et à 125 bit/s pour résister à une opération désynchronisante.

[pt] Estudaremos dinâmicas simbólicas associadas a alfabetos finitos. Consideraremos seqüências bi-infinitas e espaços com memória finita. Estudaremos propriedades invariantes por conjugação. Analisaremos a relação entre os espaços de seqüências e propriedades de matrizes não negativas. O principal exemplo desta correlação é o Teorema de Perron- Frobenius que relaciona a entropia de um espaço de seqüências e os autovalores de uma matriz não negativa associada ao espaço. Neste contexto, certos grafos e suas propriedades aparecem de forma natural. / [en] We study symbolic dynamics associated to finite alphabets. We consider bi-infinite sequences and spaces with finite memory. We pay attention to properties which are invariant by conjugations. We analyze the relation between spaces of sequences and properties of non-negative matrices. The main example is given by the Perron-Frobenius theorem relating the entropy of a space of sequences and the eigerrvalues of a non-negative matrix associated to the space. In this setting, certain graphs and their properties appear in a natural way.

O presente trabalho aborda o Problema de Coleta Domiciliar Urbana (PCDU) de resíduos sólidos, tratado no nível tático de planejamento, em que zonas de coleta são definidas para cada dia da semana e designadas aos veículos coletores, cuja frota deve ser dimensionada. O problema estudado é baseado em um caso real, o qual possui como particularidades: cada zona de coleta é formada por regiões adjacentes e será representada por um nó-semente; a demanda de cada zona deverá ser atendida dentro do período de uma semana, conforme múltiplos programas possíveis de coleta; em um turno de um dia de trabalho um veículo poderá realizar múltiplas viagens; e há uma garagem para a frota e uma estação de transbordo, a qual possibilita que o veículo seja esvaziado para realizar outras viagens. A literatura apresenta alguns métodos heurísticos para a resolução de variantes deste problema, sendo os métodos exatos utilizados somente na resolução de instâncias pequenas, dado que o problema de VRP (Vehicle Routing Problem) é classificado como NP-hard. A imposição de adjacência é uma característica particular, a qual é justificada pela possível melhoria na utilização dos veículos em posterior planejamento operacional. São propostos um modelo matemático e um método heurístico para resolver o problema, sobre os quais são realizados experimentos computacionais. O método heurístico é aplicado sobre um estudo de caso de um problema de escala real, sendo obtida solução heurística como resultado. / The present work addresses the Urban Household Solid Waste Problem (UHSWP) on a tactical planning level, wherein collection zones are assigned to every week daywork and collection vehicles, which fleet is to be sized. The studied problem is based on a real case, such peculiarities as: each collection zone is a set of adjacent areas and a seed node represents it; the demand each zone must attended within a week, according to the several possible collection schedule; on a work day shift a vehicle can be assigned to multiple trips; and there is a base depot for the fleet and a transfer station, where the vehicles are unloaded, restoring their load capacity for the next trips. Literature presents heuristic methods for the solving of its problem variants, in which exact methos are only applied to small instances, due to the VRP (Vehicle Routing Problem) NP-hard property. The adjacency imposition is a peculiar feature, which is justified by the potential improvement on vehicle usage considering a posterior operational planning. A mathematical model and a heuristic method are proposed for the problem solving and evaluated by computational experiments. A real scale problem case study is solved by the heuristic method and the results are presented.

Dans cette thèse, nous nous sommes intéressés au problème de codage de sources avec information adjacente au décodeur seulement. Plus précisément, nous avons considéré le cas où la distribution jointe entre la source et l'information adjacente n'est pas bien connue. Dans ce contexte, pour un problème de codage sans pertes, nous avons d'abord effectué une analyse de performance à l'aide d'outils de la théorie de l'information. Nous avons ensuite proposé un schéma de codage pratique efficace malgré le manque de connaissance sur la distribution de probabilité jointe. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur un algorithme de type Espérance-Maximisation. Le problème du schéma de codage proposé, c'est que les codes LDPC non-binaires utilisés doivent être performants. C'est à dire qu'ils doivent être construits à partir de distributions de degrés qui permettent d'atteindre un débit proche des performances théoriques. Nous avons donc proposé une méthode d'optimisation des distributions de degrés des codes LDPC. Enfin, nous nous sommes intéressés à un cas de codage avec pertes. Nous avons supposé que le modèle de corrélation entre la source et l'information adjacente était décrit par un modèle de Markov caché à émissions Gaussiennes. Pour ce modèle, nous avons également effectué une analyse de performance, puis nous avons proposé un schéma de codage pratique. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur une reconstruction MMSE. Ces deux composantes exploitent la structure avec mémoire du modèle de Markov caché.

Le problème de codage avec information adjacente (CCSI) est une technique récente d'annulation d'interférences en transmission et en compression de données. Ceci concerne les situations où l'émetteur est informé (par une voie retour par exemple) d'une partie de l'interférence canal. L'objectif est alors d' utiliser cette connaissance afin de concevoir un codage efficace. Une application étroitement liée à la transmission et à la compression de données est le "marquage de l'information" (information embedding). Potentiellement prometteur, le marquage d'information pose de nombreux défis dans différents domaines de recherche, allant de l'étude des limites théoriques de performance d'un point de vue théorie de l'information aux aspects liés à leurs implémentation d'un point de vue traitement de signal, en passant par la conception de code d'un point de vue communication numérique et codage. Dans cette thèse nous considérons la problématique de marquage de l'information sous ses trois aspects: de théorie de l'information, de codage et communication et de traitement de signal. Le travail effectué dans le cadre de cette thèse peut être structurée en quatre parties. Dans la première partie, nous formalisons le problème de construction de dictionnaire comme un problème de conception de constellation. En particulier, nous montrons que le problème de codage avec information adjacente disponible à l'encodeur est fondamentalement un problème de codage conjoint source-canal. Ensuite, nous nous basons sur les réseaux de points imbriquées (nested lattices) pour la construction de bons codes algebriques à complexité réduite. Dans la deuxième partie, nous considérons le problème de marquage multiple comme un problème de communication multi-utilisateurs et nous construisons des stratégies de codage qui permettent d'approcher au mieux les limites théoriques de performances. La troisième partie traite le problème de sensibilité à l'information adjacente. Nous y évaluons la dégradation des performances due à une petite perturbation additive de l'information adjacente et nous y montrons que, dans certaines conditions, l'encodeur doit s'adapter à la perturbation en, éventuellement, changer sa stratégie de codage. La quatrième partie traite les performances du CCSI sur un canal AWGN avec jitter (AWGN\&J) d'un point de vue théorie de jeux.

O presente trabalho aborda o Problema de Coleta Domiciliar Urbana (PCDU) de resíduos sólidos, tratado no nível tático de planejamento, em que zonas de coleta são definidas para cada dia da semana e designadas aos veículos coletores, cuja frota deve ser dimensionada. O problema estudado é baseado em um caso real, o qual possui como particularidades: cada zona de coleta é formada por regiões adjacentes e será representada por um nó-semente; a demanda de cada zona deverá ser atendida dentro do período de uma semana, conforme múltiplos programas possíveis de coleta; em um turno de um dia de trabalho um veículo poderá realizar múltiplas viagens; e há uma garagem para a frota e uma estação de transbordo, a qual possibilita que o veículo seja esvaziado para realizar outras viagens. A literatura apresenta alguns métodos heurísticos para a resolução de variantes deste problema, sendo os métodos exatos utilizados somente na resolução de instâncias pequenas, dado que o problema de VRP (Vehicle Routing Problem) é classificado como NP-hard. A imposição de adjacência é uma característica particular, a qual é justificada pela possível melhoria na utilização dos veículos em posterior planejamento operacional. São propostos um modelo matemático e um método heurístico para resolver o problema, sobre os quais são realizados experimentos computacionais. O método heurístico é aplicado sobre um estudo de caso de um problema de escala real, sendo obtida solução heurística como resultado. / The present work addresses the Urban Household Solid Waste Problem (UHSWP) on a tactical planning level, wherein collection zones are assigned to every week daywork and collection vehicles, which fleet is to be sized. The studied problem is based on a real case, such peculiarities as: each collection zone is a set of adjacent areas and a seed node represents it; the demand each zone must attended within a week, according to the several possible collection schedule; on a work day shift a vehicle can be assigned to multiple trips; and there is a base depot for the fleet and a transfer station, where the vehicles are unloaded, restoring their load capacity for the next trips. Literature presents heuristic methods for the solving of its problem variants, in which exact methos are only applied to small instances, due to the VRP (Vehicle Routing Problem) NP-hard property. The adjacency imposition is a peculiar feature, which is justified by the potential improvement on vehicle usage considering a posterior operational planning. A mathematical model and a heuristic method are proposed for the problem solving and evaluated by computational experiments. A real scale problem case study is solved by the heuristic method and the results are presented.

Dans cette thèse, nous nous sommes intéressés au problème de codage de sources avec information adjacente au décodeur seulement. Plus précisément, nous avons considéré le cas où la distribution jointe entre la source et l'information adjacente n'est pas bien connue. Dans ce contexte, pour un problème de codage sans pertes, nous avons d'abord effectué une analyse de performance à l'aide d'outils de la théorie de l'information. Nous avons ensuite proposé un schéma de codage pratique efficace malgré le manque de connaissance sur la distribution de probabilité jointe. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur un algorithme de type Espérance-Maximisation. Le problème du schéma de codage proposé, c'est que les codes LDPC non-binaires utilisés doivent être performants. C'est à dire qu'ils doivent être construits à partir de distributions de degrés qui permettent d'atteindre un débit proche des performances théoriques. Nous avons donc proposé une méthode d'optimisation des distributions de degrés des codes LDPC. Enfin, nous nous sommes intéressés à un cas de codage avec pertes. Nous avons supposé que le modèle de corrélation entre la source et l'information adjacente était décrit par un modèle de Markov caché à émissions Gaussiennes. Pour ce modèle, nous avons également effectué une analyse de performance, puis nous avons proposé un schéma de codage pratique. Ce schéma de codage s'appuie sur des codes LDPC non-binaires et sur une reconstruction MMSE. Ces deux composantes exploitent la structure avec mémoire du modèle de Markov caché. / In this thesis, we considered the problem of source coding with side information available at the decoder only. More in details, we considered the case where the joint distribution between the source and the side information is not perfectly known. In this context, we performed a performance analysis of the lossless source coding scheme. This performance analysis was realized from information theory tools. Then, we proposed a practical coding scheme able to deal with the uncertainty on the joint probability distribution. This coding scheme is based on non-binary LDPC codes and on an Expectation-Maximization algorithm. For this problem, a key issue is to design efficient LDPC codes. In particular, good code degree distributions have to be selected. Consequently, we proposed an optimization method for the selection of good degree distributions. To finish, we considered a lossy coding scheme. In this case, we assumed that the correlation channel between the source and the side information is described by a Hidden Markov Model with Gaussian emissions. For this model, we performed again some performance analysis and proposed a practical coding scheme. The proposed scheme is based on non-binary LDPC codes and on MMSE reconstruction using an MCMC method. In our solution, these two components are able to exploit the memory induced by the Hidden Markov model.

Made available in DSpace on 2016-01-26T12:51:47Z (GMT). No. of bitstreams: 1 fernandofilipe_dissert.pdf: 443784 bytes, checksum: bb6328cd8296f1c4b222d0c43cdafda1 (MD5) Previous issue date: 2006-02-13 / Adjacent segment disease is defined as an abnormal process developing in the adjacent level above and/or bellow the arthrodesis of the segment. It is considered a late complication of lumbar spine arthrodesis. It has been very important due to the procedures in the last years. Objective: To evaluate the risk factors associated with the disease at adjacent level as well as its relationship with the natural history of degenerative disease of the lumbar spine. Material and Methods: This was a retrospective study, from January 2000 to December 2002.Thirty-eight patients undergoing arthrodesis in the lumbosacral spine using the pedicle screw fixation participated in the study. Results: These patients had a mean follow-up of 30 months; 10 patients presented adjacent segment disease, 7 disc degeneration, 2 spinal stenosis and one discal spine hernia. The patients´ mean age was 48.5 years; female sex was the majority. Degeneration occurred in 4 patients with stenosis; 4 with spondylolisthesis, and 1 with post disc hernia; all these had been submitted to arthrodesis of lumbosacral spine. The majority was asymptomatic, after being treated by arthrodesis in multiple levels. There was no statistical difference when the above factors were related. Conclusion: Adjacent segment disease is a late complication in the arthrodesis of lumbosacral spine with no relationship of risk factors presented in this study. Therefore, its origin could be related with the natural history of the degenerative disease of lumbar spine. / A doença do nível adjacente é definida como um processo anormal que se desenvolve no nível adjacente, acima e/ou abaixo do segmento artrodesado. Considerada como uma complicação tardia da artrodese da coluna vertebral, tem-se tornado muito importante em decorrência do aumento dos procedimentos nos últimos anos. Objetivo: Avaliar os fatores de risco associados à ocorrência da doença do nível adjacente e sua relação com a história natural da doença degenerativa da coluna vertebral. Material e métodos: Análise retrospectiva de janeiro de 2000 a dezembro de 2002, realizada em 38 pacientes submetidos a artrodese de coluna lombosacra com a utilização de parafuso pedicular. Resultado: Os pacientes analisados apresentavam follow up médio de 30 meses, com a presença de 10 pacientes com doença do nível adjacente; sendo 7 com degeneração discal, 2 com estenose de canal vertebral e 1 com hérnia de disco. A idade média dos pacientes foi 48,5 anos, com predomínio no sexo feminino. A degeneração ocorreu em 4 pacientes com estenose de canal, em 4 pacientes com espondilolistese, em 1 paciente com escoliose e em 1 paciente pós hérnia de disco, os quais tinham sido submetidos a artrodese da coluna lombosacra. A maioria dos pacientes foram submetidos a artrodese em múltiplos níveis e apresentavam-se assintomáticos. Nenhuma diferença estatística foi evidenciada quando relacionados os fatores acima. Conclusão: A doença do nível adjacente é uma complicação tardia existente na artrodese de coluna lombosacra, não relacionada aos fatores de risco apresentados; portanto o seu aparecimento estaria relacionado à história natural da doença degenerativa da coluna lombar.

La technologie numérique rend la transmission, le stockage et la modification de documents multimedia beaucoup plus aisés qu'auparavant. Mais du fait de cette facilité, l'authentification et la gestion des droits d'auteur deviennent difficiles. Le tatouage robuste est une solution qui s'est beaucoup développée depuis une dizaine d'années. Il permet d'insérer au sein d'un document multimedia (document hôte) un message (identifiant d'auteur, signature numérique, . . .). Cette modification est peu perceptible afin de ne pas gêner l'exploitation normale du document marqué. De plus, l'algorithme d'extraction doit pouvoir retrouver le message malgré d'éventuelles modifications de l'hôte (attaques). Alors que les premières études sur ce domaine étaient empiriques, il est apparu rapidement que le tatouage était assimilable à un problème de communication. Nous faisons le choix d'utiliser une technique de transmission particulièrement adaptée aux canaux fortement bruités, appelée étalement de spectre, et nous considérons des attaques SAWGN (scaling and additive white Gaussian noise). L'interaction entre tatouage et attaques est modélisée par un jeu entre un attaquant et un défenseur. Une optimisation de type max-min donne la forme de l'attaque optimale, qui va le plus réduire la performance de la transmission, et de la stratégie qui permet de s'en protéger au mieux. L'application de ces résultats sur des signaux issus de la transformée en ondelettes d'images confirme le bien-fondé de notre approche : l'attaque obtenue est la plus efficace, et la stratégie d'insertion est bien plus performante que les techniques testées issues de l'état de l'art. Le canal de tatouage est un canal avec information adjacente : une partie du bruit (le signal hôte) est connue au moment de l'insertion de la marque. Les travaux sur ces canaux promettent des performances théoriques bien supérieures aux canaux gaussiens classiques. Dans la troisième partie de ce manuscrit, nous reprenons l'optimisation par théorie des jeux en incluant une mesure de performance prenant en compte l'information adjacente. Nous détaillons ensuite la construction d'un dictionnaire structuré adapté à ces canaux. Les expérimentations nous indiquent de forts gains de performance. Enfin, le dernier chapitre améliore le jeu : l'étude de l'influence de désynchronisations géométriques sur les performances, et la définition d'une attaque informée prenant en compte la réalisation du signal reçu.

Le codage vidéo distribué est un paradigme qui consiste en encoder indépendamment deux sources corrélées mais à les décoder conjointement. Wyner and Ziv ont montré que le codage de source distribué peut atteindre les mêmes performances débit-distorsion du codage de source conjoint sous quelques contraintes. Cette caractéristique rend le codage de source distribué très attractif pour applications qui demandent un encodeur à bas complexité (comme par example des réseaux des senseurs sans fil) ou pour éviter tout sorte de communication entre les source (comme dans les systèmes multi-vues). Dans le cadre du codage vidéo distribué, les trames corrélées sont encodées séparément mais elles sont encodées conjointement. Dans l'architecture de Stanford, la flux vidéo est séparée en trames clés (TC) et Wyner-Ziv (TWZ). Seulement les trames clés sont envoyées au décodeur. Les trames Wyner-Ziv sont donné en entrée à un codeur systématique de canal et les bits de parité sont envoyés au décodeur. Au décodeur, on produit une estimation de la trame Wyner-Ziv, appelé information adjacente, en interpolant les trames déjà disponibles au décodeur. L'information adjacente, qui peut être considérée comme une version bruitée de la vraie trame Wyner-Ziv, est corrigées par les bits de parité envoyées par l'encodeur. Dans cette thèse, on a étudié plusieurs algorithmes pour la génération de l'information adjacente dans le cadre du codage vidéo distribué multi-vues pour ce qui concerne et interpolation temporelle et l'interpolation inter-vue. Tous les algorithmes proposés donne des résultats meilleurs par rapport à l'état de l'art en termes de performance débit-distorsion. Une deuxième contribution concerne le format vidéo multi-vues plus profondeur. Dans le cadre du paradigme du streaming interactive pour la vidéo multi-vues, le codage vidéo distribué assure la continuité de la reproduction pendant le streaming, puisque les trames Wyner-Ziv dont décodées indépendamment des trames de référence qui sont disponibles au décodeur. On a proposé plusieurs algorithmes pour l'estimation de la trame Wyner-Ziv dans ce contexte-là.