This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development. / Ce mémoire présente un nouvel algorithme métaheuristique de recherche taboue pour trouver des solutions optimales ou sous-optimales au problème de minimisation de la longueur des dépendances d’une matrice de conception (FLMP). Ce problème comporte une fonction économique non-linéaire et il appartient à la classe NP-ardu. Il s’ensuit qu’il est très difficile à trouver une solution optimale exacte en temps réel pour les problèmes de taille moyenne ou grande. D’abord, on présente le problème et une revue de la littérature associée. Ensuite, on analyse le problème, et on présente les détails du nouvel algorithme de recherche taboue produisant des solutions au problème de réduction de l’effet de retour en utilisant deux voisinages différents, le premier basé sur l’échange des positions de deux activités ("swap"), et le second sur le déplacement d’une activité à une position différente ("shift"). Des résultats numériques permettent d’analyser le comportement de l’algorithme et de comparer les deux voisinages. La première étape consiste à déterminer de bonnes valeurs pour les paramètres en utilisant des problèmes générés aléatoirement. Ensuite nos résultats sont comparés avec ceux obtenus dans la littérature. On conclut que l’algorithme de recherche taboue proposé est très prometteur, car nos résultats sont meilleurs que ceux publiés dans la litérature. D’autant plus que la recherche taboue semble avoir été utilisée pour la première fois sur ce problème.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'objectif de cette thèse est de faciliter le diagnostic du cancer de la vessie. Durant une cystoscopie, un endoscope est introduit dans la vessie pour explorer la paroi interne de l'organe qui est visualisée sur un écran. Cependant, le faible champ de vue de l'instrument complique le diagnostic et le suivi des lésions. Cette thèse présente des algorithmes pour la création de cartes bi- et tridimensionnelles à large champ de vue à partir de vidéo-séquences cystoscopiques. En utilisant les avancées récentes dans le domaine de la minimisation d'énergies discrètes, nous proposons des fonctions coût indépendantes des transformations géométriques requises pour recaler de façon robuste et précise des paires d'images avec un faible recouvrement spatial. Ces transformations sont requises pour construire des cartes lorsque des trajectoires d'images se croisent ou se superposent. Nos algorithmes détectent automatiquement de telles trajectoires et réalisent une correction globale de la position des images dans la carte. Finalement, un algorithme de minimisation d'énergie compense les faibles discontinuités de textures restantes et atténue les fortes variations d'illuminations de la scène. Ainsi, les cartes texturées sont uniquement construites avec les meilleures informations (couleurs et textures) pouvant être extraites des données redondantes des vidéo-séquences. Les algorithmes sont évalués quantitativement et qualitativement avec des fantômes réalistes et des données cliniques. Ces tests mettent en lumière la robustesse et la précision de nos algorithmes. La cohérence visuelle des cartes obtenues dépassent celles des méthodes de cartographie de la vessie de la littérature / The aim of this thesis is to facilitate bladder cancer diagnosis. The reference clinical examination is cystoscopy, where an endoscope, inserted into the bladder, allows to visually explore the organ's internal walls on a monitor. The main restriction is the small field of view (FOV) of the instrument, which complicates lesion diagnosis, follow-up and treatment traceability.In this thesis, we propose robust and accurate algorithms to create two- and three-dimensional large FOV maps from cystoscopic video-sequences. Based on recent advances in the field of discrete energy minimization, we propose transformation-invariant cost functions, which allow to robustly register image pairs, related by large viewpoint changes, with sub-pixel accuracy. The transformations linking such image pairs, which current state-of-the-art bladder image registration techniques are unable to robustly estimate, are required to construct maps with several overlapping image trajectories. We detect such overlapping trajectories automatically and perform non-linear global map correction. Finally, the proposed energy minimization based map compositing algorithm compensates small texture misalignments and attenuates strong exposure differences. The obtained textured maps are composed by a maximum of information/quality available from the redundant data of the video-sequence. We evaluate the proposed methods both quantitatively and qualitatively on realistic phantom and clinical data sets. The results demonstrate the robustness of the algorithms, and the obtained maps outperform state-of-the-art approaches in registration accuracy and global map coherence

Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui ont été établies concernant les langages, notamment le célèbre théorème de Schützenberger-McNaughton-Papert. Dans le cadre des fonctions rationnelles sur les mots finis, nous obtenons une caractérisation à la Myhill-Nerode en termes de congruences d'indice fini. Cette caractérisation nous permet d'obtenir un résultat de transfert, à partir d'équivalences logique-algèbre pour les langages vers des équivalences pour les transductions. En particulier nous montrons comment décider si une fonction rationnelle est définissable en logique du premier ordre. Sur les mots infinis, nous pouvons également décider la définissabilité en logique du premier ordre, mais avec des résultats moins généraux.Dans la seconde partie nous introduisons une logique pour les transductions et nous résolvons le problème de synthèse régulière : étant donnée une formule de la logique, peut-on obtenir un transducteur bidirectionnel déterministe satisfaisant la formule ? Les fonctions réalisées par des transducteurs bidirectionnels déterministes sont caractérisés par plusieurs modèles différents, y compris par les transducteurs MSO, et ont ainsi été nommées transductions régulières. Plus précisément nous fournissons un algorithme qui produit toujours une fonction régulière satisfaisant une spécification donnée en entrée.Nous exposons également un lien intéressant entre les transductions et les mots avec données. Par conséquent nous obtenons une logique expressive pour les mots avec données, pour laquelle le problème de satisfiabilité est décidable. / In the first part of this manuscript we focus on the study of rational functions, functions defined by one-way transducers.Our goal is to extend to transductions the many logic-algebra correspondences that have been established for languages, such as the celebrated Schützenberger-McNaughton-Papert Theorem. In the case of rational functions over finite words, we obtain a Myhill-Nerode-like characterization in terms of congruences of finite index. This characterization allows us to obtain a transfer result from logic-algebra equivalences for languages to logic-algebra equivalences for transductions. In particular, we show that one can decide if a rational function can be defined in first-order logic.Over infinite words, we obtain weaker results but are still able to decide first-order definability.In the second part we introduce a logic for transductions and solve the regular synthesis problem: given a formula in the logic, can we obtain a two-way deterministic transducer satisfying the formula?More precisely, we give an algorithm that always produces a regular function satisfying a given specification.We also exhibit an interesting link between transductions and words with ordered data. Thus we obtain as a side result an expressive logic for data words with decidable satisfiability.

Cette thèse traite quatre sujets différents de la théorie des espaces de Banach: Le premier est une caractérisation de la propriété de Radon-Nikodym en utilisant la notion du jeu des points et tranches: Le deuxième est une évaluation de l'indice de dentabilité préfaible des espaces C(K) où K est un compact du hauteur dénombrable: Le troisième est un renormage des espaces non séparables qui est simultanément LUC, lisse et approximable par des normes d'une lissité plus élevée. Le quatrième est une approche par le théorème de Baire aux principes variationnels paramétriques. La thèse commence par une introduction qui examine le contexte de ces résultats. / The thesis deals with four topics in the theory of Banach spaces. The first of them is a characterization of the Radon-Nikodym property using the notion of point-slice games. The second is a computation of the w* dentability index of the spaces C(K), where K is a compact of countable height. The third is a renorming result in nonseparable spaces, producing norms which are differentiable, LUR and approximated by norms of higher smoothness. The fourth topic is a Baire cathegory approach to parametric smooth variational principles. The thesis features an introduction which surveys the background of these results.

Nous proposons dans cette thèse de développer une méthode de restauration aveugle d'images flouées et bruitées où aucune connaissance a priori n'est exigée. Ce manuscrit est composé de trois chapitres : le 1er chapitre est consacré aux travaux de l'état de l'art. Les approches d'optimisation pour la résolution du problème de restauration y sont d'abord discutées. Ensuite les principales méthodes de restauration, dites semi-aveugles car nécessitant un minimum de connaissance a priori sont analysées. Parmi ces méthodes, cinq sont retenues pour évaluation. Le 2ème chapitre est dédié à la comparaison des performances des méthodes retenues dans le chapitre précédent. Les principaux critères objectifs d'évaluation de la qualité des images restaurées sont présentés. Parmi ces critères, la norme L1 de l'erreur d'estimation est sélectionnée. L'étude comparative menée sur une banque d'images monochromes, dégradées artificiellement par deux fonctions floues de supports différents et trois niveaux de bruit a permis de mettre en évidence les deux méthodes les plus pertinentes. La première repose sur une approche alternée mono-échelle où la PSF et l'image sont estimées dans une seule étape. La seconde utilise une approche hybride multi-échelle qui consiste tout d'abord à estimer de manière alternée la PSF et une image latente, puis dans une étape suivante séquentielle, à restaurer l'image. Dans l'étude comparative conduite, l'avantage revient à cette dernière. Les performances de ces méthodes serviront de référence pour comparer ensuite la méthode développée. Le 3ème chapitre porte sur la méthode développée. Nous avons cherché à rendre aveugle l'approche hybride retenue dans le chapitre précédent tout en améliorant la qualité d'estimation de la PSF et de l'image restaurée. Les contributions ont porté sur plusieurs points. Une première série d'améliorations concerne la redéfinition des échelles, celle de l'initialisation de l'image latente à chaque niveau d'échelle, l'évolution des paramètres pour la sélection des contours pertinents servant de support à l'estimation de la PSF et enfin, la définition d'un critère d'arrêt aveugle. Une seconde série de contributions a porté sur l'estimation aveugle des deux paramètres de régularisation impliqués pour éviter d'avoir à les fixer empiriquement. Chaque paramètre est associé à une fonction coût distincte l'une pour l'estimation de la PSF et la seconde pour l'estimation d'une image latente. Dans l'étape séquentielle qui suit, nous avons cherché à affiner le support de la PSF estimée dans l'étape alternée, avant de l'exploiter dans le processus de restauration de l'image. A ce niveau, la seule connaissance a priori nécessaire est une borne supérieure du support de la PSF. Les différentes évaluations conduites sur des images monochromes et hyperspectrales dégradées artificiellement par plusieurs flous de type mouvement, de supports différents, montrent une nette amélioration de la qualité de restauration obtenue par l'approche développée par rapport aux deux meilleures approches de l'état de l'art retenues. / We propose in this thesis manuscript to develop a blind restoration method of single component blurred and noisy images where no prior knowledge is required. This manuscript is composed of three chapters: the first chapter focuses on state-of-art works. The optimization approaches for resolving the restoration problem are discussed first. Then, the main methods of restoration, so-called semi-blind ones because requiring a minimum of a priori knowledge are analysed. Five of these methods are selected for evaluation. The second chapter is devoted to comparing the performance of the methods selected in the previous chapter. The main objective criteria for evaluating the quality of the restored images are presented. Of these criteria, the l1 norm for the estimation error is selected. The comparative study conducted on a database of monochromatic images, artificially degraded by two blurred functions with different support size and three levels of noise, revealed the most two relevant methods. The first one is based on a single-scale alternating approach where both the PSF and the image are estimated alternatively. The second one uses a multi-scale hybrid approach, which consists first of alternatingly estimating the PSF and a latent image, then in a sequential next step, restoring the image. In the comparative study performed, the benefit goes to the latter. The performance of both these methods will be used as references to then compare the newly designed method. The third chapter deals with the developed method. We have sought to make the hybrid approach retained in the previous chapter as blind as possible while improving the quality of estimation of both the PSF and the restored image. The contributions covers a number of points. A first series concerns the redefinition of the scales that of the initialization of the latent image at each scale level, the evolution of the parameters for the selection of the relevant contours supporting the estimation of the PSF and finally the definition of a blind stop criterion. A second series of contributions concentrates on the blind estimation of the two regularization parameters involved in order to avoid having to fix them empirically. Each parameter is associated with a separate cost function either for the PSF estimation or for the estimation of a latent image. In the sequential step that follows, we refine the estimation of the support of the PSF estimated in the previous alternated step, before exploiting it in the process of restoring the image. At this level, the only a priori knowledge necessary is a higher bound of the support of the PSF. The different evaluations performed on monochromatic and hyperspectral images artificially degraded by several motion-type blurs with different support sizes, show a clear improvement in the quality of restoration obtained by the newly designed method in comparison to the best two state-of-the-art methods retained.

Cette thèse de doctorat introduit un modèle et un algorithme six-dimensions pour la reconstruction des orientations cristallines locales dans les matériaux polycristallins. Le modèle s’applique actuellement aux données obtenues avec un rayonnement synchrotron (faisceau parallèle et monochromatique), mais il est également possible d’envisager des extensions aux instruments et sources de laboratoire (polychromatique et divergent). Le travail présenté est principalement une extension de la technique connue sous le nom de “Diffraction Contrast Tomography” (DCT) qui permet la reconstruction de la forme et de l’orientation cristalline des grains dans des matériaux polycristallins (avec certaines restrictions concernant la taille et le nombre total de grains ainsi que la mosaicité intragranulaire). / This Ph.D. thesis is about the development and formalization of a six-dimensional tomography method, for the reconstruction of local orientation in poly-crystalline materials. This method is based on a technique known as diffraction contract tomography (DCT), mainly used in synchrotrons, with a monochromatic and parallel high energy X-ray beam. DCT exists since over a decade now, but it was always employed to analyze undeformed or nearly undeformed materials, described by “grains” with a certain average orientation. Because an orientation can be parametrized by the used of only three num- bers, the local orientation in the grains is modelled by a six-dimensional space X6 = R3 ⊗ O3, that is the outer product between a three-dimensional real- space and another three-dimensional orientation-space. This means that for each point of the real-space, there could be a full three-dimensional orientation- space, which however in practice is restricted to a smaller region of interest called “local orientation-space”. The reconstruction problem is then formulated as a global minimisation prob- lem, where the reconstruction of a single grain is the solution that minimizes a functional. There can be different choices for the functionals to use, and they depend on the type of reconstructions one is looking for, and on the type of a priori knowledge is available. All the functionals used include a data fidelity term which ensures that the reconstruction is consistent with the measured diffraction data, and then an additional regularization term is added, like the l1-norm minimization of the solution vector, that tries to limit the number of orientations per real-space voxel, or a Total Variation operator over the sum of the orientation part of the six-dimensional voxels, in order to enforce the homogeneity of the grain volume. When first published, the results on synthetic data from the third chapter high- lighted some key features of the proposed framework, and showed that it was in principle possible to extend DCT to the reconstruction of moderately de- formed materials, but it was unclear whether it could work in practice. The following chapters instead confirm that the proposed framework is viable for reconstructing moderately deformed materials, and that in conjunction with other techniques, it could also overcome the limitations imposed by the grain indexing, and be applied to more challenging textured materials.

L'objectif de cette thèse est l'élaboration de modèles de contours actifs basés régions pour la segmentation d'images et de vidéos.<br />Nous proposons de segmenter les régions ou objets en minimisant une fonctionnelle composée d'intégrales de régions et d'intégrales de contours. Dans ce cadre de travail, les fonctions caractérisant les régions ou les contours sont appelées "descripteurs''. La recherche du minimum se fait via la propagation d'un contour actif dit basé régions. L'équation d'évolution associée est calculée en utilisant les outils de dérivation de domaines. Par ailleurs, nous prenons en compte le cas des descripteurs dépendant de la région qui évoluent au cours de la propagation du contour. Nous montrons que cette dépendance induit des termes supplémentaires dans l'équation d'évolution.<br /><br />Le cadre de travail développé est ensuite mis en oeuvre pour des applications variées de segmentation. Tout d'abord, des descripteurs statistiques basés sur le déterminant de la matrice de covariance sont étudiés pour la segmentation du visage. L'estimation des paramètres statistiques se fait conjointement à la segmentation. Nous proposons ensuite des descripteurs statistiques utilisant une distance à un histogramme de référence. Enfin, la détection des objets en mouvement dans les séquences à caméra fixe et mobile est opérée via l'utilisation hierarchique de descripteurs basés mouvement et de descripteurs spatiaux.

Cette thèse s'inscrit dans le cadre d'une collaboration entre le CRAN (UMR 7039) et le LCPME (UMR 7564) dont l'objectif est de développer des méthodes d'analyse de signaux spectroscopiques.<br /><br />Dans un premier temps est proposée une méthode déterministe qui permet d'estimer la ligne de base des spectres par le polynôme qui minimise une fonction-coût non quadratique (fonction de Huber ou parabole tronquée). En particulier, les versions asymétriques sont particulièrement bien adaptées pour les spectres dont les raies sont positives. Pour la minimisation, on utilise l'algorithme de minimisation semi-quadratique LEGEND.<br /><br />Dans un deuxième temps, on souhaite estimer le spectre de raies : l'approche bayésienne couplée aux techniques MCMC fournit un cadre d'étude très efficace. Une première approche formalise le problème en tant que déconvolution impulsionnelle myope non supervisée. En particulier, le signal impulsionnel est modélisé par un processus Bernoulli-gaussien à support positif ; un algorithme d'acceptation-rejet mixte permet la simulation de lois normales tronquées. Une alternative intéressante à cette approche est de considérer le problème comme une décomposition en motifs élémentaires. Un modèle original est alors introduit ; il a l'intérêt de conserver l'ordre du système fixe. Le problème de permutation d'indices est également étudié et un algorithme de ré-indexage est proposé.<br /><br />Les algorithmes sont validés sur des spectres simulés puis sur des spectres infrarouge et Raman réels.

La thèse se place dans le cadre de l'apprentissage statistique. Elle apporte<br />des contributions à la communauté du machine learning en utilisant des<br />techniques de statistiques modernes basées sur des avancées dans l'étude<br />des processus empiriques. Dans une première partie, les propriétés statistiques de<br />l'analyse en composantes principales à noyau (KPCA) sont explorées. Le<br />comportement de l'erreur de reconstruction est étudié avec un point de vue<br />non-asymptotique et des inégalités de concentration des valeurs propres de la matrice de<br />Gram sont données. Tous ces résultats impliquent des vitesses de<br />convergence rapides. Des propriétés <br />non-asymptotiques concernant les espaces propres de la KPCA eux-mêmes sont également<br />proposées. Dans une deuxième partie, un nouvel <br />algorithme de classification a été<br />conçu : la Kernel Projection Machine (KPM). <br />Tout en s'inspirant des Support Vector Machines (SVM), il met en lumière que la sélection d'un espace vectoriel par une méthode de<br />réduction de la dimension telle que la KPCA régularise <br />convenablement. Le choix de l'espace vectoriel utilisé par la KPM est guidé par des études statistiques de sélection de modéle par minimisation pénalisée de la perte empirique. Ce<br />principe de régularisation est étroitement relié à la projection fini-dimensionnelle étudiée dans les travaux statistiques de <br />Birgé et Massart. Les performances de la KPM et de la SVM sont ensuite comparées sur différents jeux de données. Chaque thème abordé dans cette thèse soulève de nouvelles questions d'ordre théorique et pratique.