Quadtree representation and compression of spatial data

Spatial data representation and compression has become a focus issue in computer graphics and image processing applications. Quadtrees, as one of hierarchical data structures, basing on the principle of recursive decomposition of space, always offer a compact and efficient representation of an image. For a given image, the choice of quadtree root node plays an important role in its quadtree representation and final data compression. The goal of this thesis is to present a heuristic algorithm for finding a root node of a region quadtree, which is able to reduce the number of leaf nodes when compared with the standard quadtree decomposition. The empirical results indicate that, this proposed algorithm has quadtree representation and data compression improvement when in comparison with the traditional method.

Improving Short DNA Sequence Alignment with Parallel Computing

Variations in different types of genomes have been found to be responsible for a large degree of physical diversity such as appearance and susceptibility to disease. Identification of genomic variations is difficult and can be facilitated through computational analysis of DNA sequences. Newly available technologies are able to sequence billions of DNA base pairs relatively quickly. These sequences can be used to identify variations within their specific genome but must be mapped to a reference sequence first. In order to align these sequences to a reference sequence, we require mapping algorithms that make use of approximate string matching and string indexing methods. To date, few mapping algorithms have been tailored to handle the massive amounts of output generated by newly available sequencing technologies. In otrder to handle this large amount of data, we modified the popular mapping software BWA to run in parallel using OpenMPI. Parallel BWA matches the efficiency of multithreaded BWA functions while providing efficient parallelism for BWA functions that do not currently support multithreading. Parallel BWA shows significant wall time speedup in comparison to multithreaded BWA on high-performance computing clusters, and will thus facilitate the analysis of genome sequencing data.

Bundling under the Threat of Parallel Trade

This paper examines the use of bundling by a firm that sells in two national markets and faces entry by parallel traders. The firm can bundle its main product, - a tradable good- with a non-traded service. It chooses between the strategies of pure bundling, mixed bundling and no bundling. The paper shows that in the low-price country the threat of grey trade elicits a move from mixed bundling, or no bundling, towards pure bundling. It encourages a move from pure bundling towards mixes bundling or no bundling in the high-price country. The set of parameter values for which the profit maximizing strategy is not to supply the low price country is smaller than in the absence of bundling. The welfare effects of deterrence of grey trade are not those found in conventional models of price arbitrage. Some consumers in the low-price country may gain from the threat of entry by parallel traders although they pay a higher price. This is due to the fact that the firm responds to the threat of arbitrageurs by increasing the amount of services it puts in the bundle targeted at consumers in that country. Similarly, the threat of parallel trade may affect some consumers in the hight-price country adversely.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Nanopatterning and functionalization of phospholipid-based Langmuir-Blodgett and Langmuir-Schaefer films

Durant les dernières décennies, la technique Langmuir-Blodgett (LB) s’est beaucoup développée dans l’approche « bottom-up » pour la création de couches ultra minces nanostructurées. Des patrons constitués de stries parallèles d’environ 100 à 200 nm de largeur ont été générés avec la technique de déposition LB de monocouches mixtes de 1,2-dilauroyl-sn-glycéro-3-phosphatidylcholine (DLPC) et de 1,2-dipalmitoyl-sn-glycéro-3-phosphatidylcholine (DPPC) sur des substrats de silicium et de mica. Afin d’amplifier la fonctionnalité de ces patrons, la 1-palmitoyl-2-(16-(S-methyldithio)hexadécanoyl)-sn-glycéro-3-phosphatidylcholine (DSDPPC) et la 1-lauroyl-2-(12-(S-methyldithio)dodédecanoyl)-sn-glycéro-3-phosphatidylcholine (DSDLPC) ont été employées pour la préparation de monocouches chimiquement hétérogènes. Ces analogues de phospholipide possèdent un groupement fonctionnel méthyldisulfide qui est attaché à la fin de l’une des chaînes alkyles. Une étude exhaustive sur la structure de la phase des monocouches Langmuir, Langmuir-Schaefer (LS) et LB de la DSDPPC et de la DSDLPC et leurs différents mélanges avec la DPPC ou la DLPC est présentée dans cette thèse. Tout d’abord, un contrôle limité de la périodicité et de la taille des motifs des stries parallèles de DPPC/DLPC a été obtenu en variant la composition lipidique, la pression de surface et la vitesse de déposition. Dans un mélange binaire de fraction molaire plus grande de lipide condensé que de lipide étendu, une vitesse de déposition plus lente et une plus basse pression de surface ont généré des stries plus continues et larges. L’addition d’un tensioactif, le cholestérol, au mélange binaire équimolaire de la DPPC/DLPC a permis la formation de stries parallèles à de plus hautes pressions de surface. La caractérisation des propriétés physiques des analogues de phospholipides a été nécessaire. La température de transition de phase de la DSDPPC de 44.5 ± 1.5 °C comparativement à 41.5 ± 0.3 °C pour la DPPC. L’isotherme de la DSDPPC est semblable à celui de la DPPC. La monocouche subit une transition de phase liquide-étendue-à-condensée (LE-C) à une pression de surface légèrement supérieure à celle de la DPPC (6 mN m-1 vs. 4 mN m-1) Tout comme la DLPC, la DSDLPC demeure dans la phase LE jusqu’à la rupture de la monocouche. Ces analogues de phospholipide existent dans un état plus étendu tout au long de la compression de la monocouche et montrent des pressions de surface de rupture plus basses que les phospholipides non-modifiés. La morphologie des domaines de monocouches Langmuir de la DPPC et de la DSDPPC à l’interface eau/air a été comparée par la microscopie à angle de Brewster (BAM). La DPPC forme une monocouche homogène à une pression de surface (π) > 10 mN/m, alors que des domaines en forme de fleurs sont formés dans la monocouche de DSDPPC jusqu’à une π ~ 30 mN m-1. La caractérisation de monocouches sur substrat solide a permis de démontrer que le patron de stries parallèles préalablement obtenu avec la DPPC/DLPC était reproduit en utilisant des mélanges de la DSDPPC/DLPC ou de la DPPC/DSDLPC donnant ainsi lieu à des patrons chimiquement hétérogènes. En général, pour obtenir le même état de phase que la DPPC, la monocouche de DSDPPC doit être comprimée à de plus hautes pressions de surface. Le groupement disulfide de ces analogues de phospholipide a été exploité, afin de (i) former des monocouches auto-assemblées sur l’or et de (ii) démontrer la métallisation sélective des terminaisons fonctionnalisées des stries. La spectrométrie de photoélectrons induits par rayons X (XPS) a confirmé que la monocouche modifiée réagit avec la vapeur d’or pour former des thiolates d’or. L’adsorption de l’Au, de l’Ag et du Cu thermiquement évaporé démontre une adsorption préférentielle de la vapeur de métal sur la phase fonctionnalisée de disulfide seulement à des recouvrements sub-monocouche.

Compression de données d'animation acquises par capture de mouvements

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Our Lady of Ocotlán and our Lady of Guadalupe : investigation into the origins of parallel virgins

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Parallel metaheuristics for stochastic capacitated multicommodity network design

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Uncovering parallel ribosome biogenesis pathways during pre-60S subunit maturation

Paralogs are present during ribosome biogenesis as well as in mature ribosomes in form of ribosomal proteins, and are commonly believed to play redundant functions within the cell. Two previously identified paralogs are the protein pair Ssf1 and Ssf2 (94% homologous). Ssf2 is believed to replace Ssf1 in case of its absence from cells, and depletion of both proteins leads to severely impaired cell growth. Results reveal that, under normal conditions, the Ssf paralogs associate with similar sets of proteins but with varying stabilities. Moreover, disruption of their pre-rRNP particles using high stringency buffers revealed that at least three proteins, possibly Dbp9, Drs1 and Nog1, are strongly associated with each Ssf protein under these conditions, and most likely represent a distinct subcomplex. In this study, depletion phenotypes obtained upon altering Nop7, Ssf1 and/or Ssf2 protein levels revealed that the Ssf paralogs cannot fully compensate for the depletion of one another because they are both, independently, required along parallel pathways that are dependent on the levels of availability of specific ribosome biogenesis proteins. Finally, this work provides evidence that, in yeast, Nop7 is genetically linked with both Ssf proteins.

Supporting Parallel Legal Systems as a Means of Improving Access to Justice in Guatemala

Parallel legal systems can and do exist within a single sovereign nation, and rural Guatemala offers one example. Such parallel systems are generally viewed as failures of legal penetration which compromise the rule of law. The question addressed in this paper is whether the de facto existence of parallel systems in Guatemala benefits the indigenous population, or whether the ultimate goal of attaining access to justice requires a complete overhaul of the official legal system. Ultimately, the author concludes that while the official justice system needs a lot of work in order to expand access to justice, especially for the rural poor, the existence of a parallel legal system can be a vehicle for, rather than a hindrance to, expanding such access.

Hopf bifurcation in parallel polarized Nd:YAG laser

Dynamics of Nd:YAG laser with intracavity KTP crystal operating in two parallel polarized modes is investigated analytically and numerically. System equilibrium points were found out and the stability of each of them was checked using Routh–Hurwitz criteria and also by calculating the eigen values of the Jacobian. It is found that the system possesses three equilibrium points for (Ij, Gj), where j = 1, 2. One of these equilibrium points undergoes Hopf bifurcation in output dynamics as the control parameter is increased. The other two remain unstable throughout the entire region of the parameter space. Our numerical analysis of the Hopf bifurcation phenomena is found to be in good agreement with the analytical results. Nature of energy transfer between the two modes is also studied numerically.

A novel Sigma–Delta based parallel analogue-to-residue converter

Animportant step in the residue number system(RNS) based signal processing is the conversion of signal into residue domain. Many implementations of this conversion have been proposed for various goals, and one of the implementations is by a direct conversion from an analogue input. A novel approach for analogue-to-residue conversion is proposed in this research using the most popular Sigma–Delta analogue-to-digital converter (SD-ADC). In this approach, the front end is the same as in traditional SD-ADC that uses Sigma–Delta (SD) modulator with appropriate dynamic range, but the filtering is doneby a filter implemented usingRNSarithmetic. Hence, the natural output of the filter is an RNS representation of the input signal. The resolution, conversion speed, hardware complexity and cost of implementation of the proposed SD based analogue-to-residue converter are compared with the existing analogue-to-residue converters based on Nyquist rate ADCs

Implementation and Evaluation of an Improved Header Compression for 6LoWPAN

Extending IPv6 to IEEE 802.15.4-based Low power Wireless Personal Area Networks requires efficient header compression mechanisms to adapt to their limited bandwidth, memory and energy constraints. This paper presents an experimental evaluation of an improved header compression scheme which provides better compression of IPv6 multicast addresses and UDP port numbers compared to existing mechanisms. This scheme outperforms the existing compression mechanism in terms of data throughput of the network and energy consumption of nodes. It enhances throughput by up to 8% and reduces transmission energy of nodes by about 5%.

An Improved Technique for Evolving Wavelet Coefficients for Fingerprint Image Compression

In this paper, an improved technique for evolving wavelet coefficients refined for compression and reconstruction of fingerprint images is presented. The FBI fingerprint compression standard [1, 2] uses the cdf 9/7 wavelet filter coefficients. Lifting scheme is an efficient way to represent classical wavelets with fewer filter coefficients [3, 4]. Here Genetic algorithm (GA) is used to evolve better lifting filter coefficients for cdf 9/7 wavelet to compress and reconstruct fingerprint images with better quality. Since the lifting filter coefficients are few in numbers compared to the corresponding classical wavelet filter coefficients, they are evolved at a faster rate using GA. A better reconstructed image quality in terms of Peak-Signal-to-Noise-Ratio (PSNR) is achieved with the best lifting filter coefficients evolved for a compression ratio 16:1. These evolved coefficients perform well for other compression ratios also.