No description available.

Data-dependent triangulation (DDT) based mesh-generation schemes for image representation are studied. A flexible mesh-generation framework and a highly effective mesh-generation method that employs this framework are proposed. The proposed framework is derived from frameworks proposed by Rippa and Garland and Heckbert by making a number of key modifications to facilitate the development of much more effective mesh-generation methods. As the proposed framework has several free parameters, the effects of different choices of these parameters on mesh quality (both in terms of squared error and subjectively) are studied, leading to the recommendation of a particular set of choices for these parameters. A new mesh-generation method is then introduced that employs the proposed framework with these best parameter choices. Experimental results show our proposed mesh-generation method outperforms several competing approaches, namely, the DDT-based incremental scheme proposed by Garland and Heckbert, the COMPRESS scheme proposed by Rippa, and the adaptive thinning scheme proposed by Demaret and Iske. More specifically, in terms of PSNR, our proposed method was found to outperform these three schemes by median margins of 4.1 dB, 10.76 dB, and 0.83 dB, respectively. The subjective qualities of reconstructed images were also found to be correspondingly better. In terms of computational cost, our proposed method was found to be comparable to the schemes proposed by Garland and Heckbert and Rippa. Moreover, our proposed method requires only about 5 to 10% of the time of the scheme proposed by Demaret and Iske. In terms of memory cost, our proposed method was shown to require essentially same amount of memory as the schemes proposed by Garland and Heckbert and Rippa, and orders of magnitude (33 to 800 times) less memory than the scheme proposed by Demaret and Iske. / Graduate

Triangle mesh models of images are studied. Through exploration, a computational framework for mesh generation based on data-dependent triangulations (DDTs) and two specific mesh-generation methods derived from this framework are proposed. In earlier work, Yang et al. proposed a highly-effective technique for generating triangle-mesh models of images, known as the error diffusion (ED) method. Unfortunately, the ED method, which chooses triangulation connectivity via a Delaunay triangulation, typically yields triangulations in which many (triangulation) edges crosscut image edges (i.e., discontinuities in the image), leading to increased approximation error. In this thesis, we propose a computational framework for mesh generation that modifies the ED method to use DDTs in conjunction with the Lawson local optimization procedure (LOP) and has several free parameters. Based on experimentation, we recommend two particular choices for these parameters, yielding two specific mesh-generation methods, known as MED1 and MED2, which make different trade offs between approximation quality and computational cost. Through the use of DDTs and the LOP, triangulation connectivity can be chosen optimally so as to minimize approximation error. As part of our work, two novel optimality criteria for the LOP are proposed, both of which are shown to outperform other well known criteria from the literature. Through experimental results, our MED1 and MED2 methods are shown to yield image approximations of substantially higher quality than those obtained with the ED method, at a relatively modest computational cost. For example, in terms of peak-signal-to-noise ratio, our MED1 and MED2 methods outperform the ED method, on average, by 3.26 and 3.81 dB, respectively. / Graduate

Sampling and reconstruction is used as a fundamental signal processing operation since the history of signal theory. Classically uniform sampling is treated so that the resulting mathematics is simple. However there are various instances that nonuniform sampling and reconstruction of signals from their nonuniform samples are required. There exist two broad classes of reconstruction methods. They are the reconstruction according to a deterministic, and according to a stochastic model. In this thesis, the most fundamental aspects of nonuniform sampling and reconstruction, according to a deterministic model, is analyzed, implemented and tested by considering specific nonuniform reconstruction algorithms. Accuracy of reconstruction, computational efficiency and noise stability are the three criteria that nonuniform reconstruction algorithms are tested for. Specifically, four classical closed form interpolation algorithms proposed by Yen are discussed and implemented. These algorithms are tested, according to the proposed criteria, in a variety of conditions in order to identify their performances for reconstruction quality and robustness to noise and signal conditions. Furthermore, a filter bank approach is discussed for the interpolation from nonuniform samples in a computationally efficient manner. This approach is implemented and the efficiency as well as resulting filter characteristics is observed. In addition to Yen&#039 / s classical algorithms, a trade off algorithm, which claims to find an optimal balance between reconstruction accuracy and noise stability is analyzed and simulated for comparison between all discussed interpolators. At the end of the stability tests, Yen&#039 / s third algorithm, known as the classical recurrent nonuniform sampling, is found to be superior over the remaining interpolators, from both an accuracy and stability point of view.

<p>Nonuniform sampling occurs in many practical applications either intentionally or unintentionally. This thesis deals with the reconstruction of two-periodic nonuniform signals which is of great importance in two-channel time-interleaved analog-to-digital converters. In a two-channel time-interleaved ADC, aperture delay mismatch between the channels gives rise to a two-periodic nonuniform sampling pattern, resulting in distortion and severely affecting the linearity of the converter. The problem is solved by digitally recovering a uniformly sampled sequence from a two-periodic nonuniformly sampled set. For this purpose, a time-varying FIR filter is employed. If the sampling pattern is known and fixed, this filter can be designed in an optimal way using least-squares or minimax design. When the sampling pattern changes now and then as during the normal operation of time-interleaved ADC, these filters have to be redesigned. This has implications on the implementation cost as general on-line design is cumbersome. To overcome this problem, a novel time-varying FIR filter with polynomial impulse response is developed and characterized in this thesis. The main advantage with these filters is that on-line design is no longer needed. It now suffices to perform only one design before implementation and in the implementation it is enough to adjust only one variable parameter when the sampling pattern changes. Thus the high implementation cost is decreased substantially.</p><p>Filter design and the associated performance metrics have been validated using MATLAB. The design space has been explored to limits imposed by machine precision on matrix inversions. Studies related to finite wordlength effects in practical filter realisations have also been carried out. These formulations can also be extended to the general M - periodic nonuniform sampling case.</p>

Nonuniform sampling occurs in many practical applications either intentionally or unintentionally. This thesis deals with the reconstruction of two-periodic nonuniform signals which is of great importance in two-channel time-interleaved analog-to-digital converters. In a two-channel time-interleaved ADC, aperture delay mismatch between the channels gives rise to a two-periodic nonuniform sampling pattern, resulting in distortion and severely affecting the linearity of the converter. The problem is solved by digitally recovering a uniformly sampled sequence from a two-periodic nonuniformly sampled set. For this purpose, a time-varying FIR filter is employed. If the sampling pattern is known and fixed, this filter can be designed in an optimal way using least-squares or minimax design. When the sampling pattern changes now and then as during the normal operation of time-interleaved ADC, these filters have to be redesigned. This has implications on the implementation cost as general on-line design is cumbersome. To overcome this problem, a novel time-varying FIR filter with polynomial impulse response is developed and characterized in this thesis. The main advantage with these filters is that on-line design is no longer needed. It now suffices to perform only one design before implementation and in the implementation it is enough to adjust only one variable parameter when the sampling pattern changes. Thus the high implementation cost is decreased substantially. Filter design and the associated performance metrics have been validated using MATLAB. The design space has been explored to limits imposed by machine precision on matrix inversions. Studies related to finite wordlength effects in practical filter realisations have also been carried out. These formulations can also be extended to the general M - periodic nonuniform sampling case.

Motion planning consists of finding a feasible path of an object between an initial state and a goal state, and commonly constitutes a sub-system of a larger autonomous system. Motion planners that utilize sampling-based algorithms create an implicit representation of the search space via sampling said search space. Autonomous systems that rely on real-time motion planning benefit from the ability of these algorithms to quickly compute paths that are optimal or near optimal. For sampling-based motion planning algorithms, the sampling strategy greatly affects the convergence speed of finding these paths, i.e., how the sampling distribution is shaped within the search space. In baseline approaches, the samples may be drawn with uniform probability over this space. This thesis project explores a learning-based approach that can utilize experience from previous successful motion plans to provide useful information in novel planning scenarios, as a means of improvement over conventional motion planning methods. Specifically, the focus has been on learning the sampling distributions in both the state space and the control space of an autonomous ground vehicle. The innovatory parts of this work consist of (i) learning the control space sampling distributions, and (ii) learning said distributions for a tractor-trailer system. At the core of the method is an artificial neural network consisting of a conditional variational autoencoder. This artificial neural network is capable of learning suitable sampling distributions in both the state space and control space of a vehicle in different planning scenarios. The method is tested in four different environments and for two kinds of vehicles. Evaluation is partly done by comparison of results with a conventional motion planning algorithm. These evaluations indicates that the artificial neural network can produce valuable information in novel planning scenarios. Future work, primarily on how the artificial neural network may be applied to motion planning algorithms, is necessary to draw further conclusions. / Rörelseplanering består av att hitta en genomförbar bana för ett objekt mellan ett initialtillstånd och ett måltillstånd, och utgör vanligtvis ett delsystem av ett större autonomt system. Rörelseplanerare som använder provtagningssbaserade algoritmer skapar en implicit representation av sökutrymmet via provtagning av sökutrymmet. Autonoma system som förlitar sig på rörelseplanering i realtid drar nytta av dessa algoritmers förmåga att snabbt beräkna banor som är optimala eller nästan optimala. För provtagningssbaserade rörelseplaneringsalgoritmer påverkar provtagningsstrategin i hög grad konvergenshastigheten för att hitta dessa vägar, dvs. hur provtagningsfördelningen är formad inom sökutrymmet. I standardmetoder kan stickproven dras med jämn sannolikhet över detta utrymme. Detta examensarbete utforskar en lärande-baserat metod som kan utnyttja erfarenheter från tidigare lyckade rörelseplaner för att tillhandahålla användbar information i nya planeringsscenarier, som ett medel för förbättring jämfört med konventionella rörelseplaneringsmetoder. Specifikt har fokus legat på att lära sig provtagningssfördelningarna i både tillståndsrummet och styrsignals-rummet för ett autonomt markfordon. De nyskapande delarna av detta arbete består av att (i) lära sig kontrollutrymmessamplingsfördelningarna, och (ii) inlärning av nämnda provtagningsfördelningarna för ett traktor-släpsystem. Kärnan i metoden är ett artificiellt neuralt nätverk bestående av en conditional variational autoencoder. Detta artificiella neurala nätverk är kapabelt att lära sig lämpliga provtagningsfördelningar i både tillståndsrummet och kontrollrummet för ett fordon i olika planeringsscenarier. Metoden testas i fyra olika miljöer och för två olika av fordon. Utvärdering görs delvis genom jämförelse av resultat med en konventionell rörelseplaneringsalgoritm. Dessa utvärderingar tyder på att det artificiella neurala nätverket kan producera värdefull information i nya planeringsscenarier. Mer forskning, i första hand med hur det artificiella neurala nätverket kan tillämpas på rörelseplaneringsalgoritmer, är nödvändigt för att dra ytterligare slutsatser.

Signal acquisition, signal reconstruction and analysis of spectrum of the signal are the three most important steps in signal processing and they are found in almost all of the modern day hardware. In most of the signal processing hardware, the signal of interest is sampled at uniform intervals satisfying some conditions like Nyquist rate. However, in some cases the privilege of having uniformly sampled data is lost due to some constraints on the hardware resources. In this thesis an important problem of signal reconstruction and spectral analysis from nonuniformly sampled data is addressed and a variety of methods are presented. The proposed methods are tested via numerical experiments on both artificial and real-life data sets. The thesis starts with a brief review of methods available in the literature for signal reconstruction and spectral analysis from non uniformly sampled data. The methods discussed in the thesis are classified into two broad categories - dense and sparse methods, the classification is based on the kind of spectra for which they are applicable. Under dense spectral methods the main contribution of the thesis is a non-parametric approach named LIMES, which recovers the smooth spectrum from non uniformly sampled data. Apart from recovering the spectrum, LIMES also gives an estimate of the covariance matrix. Under sparse methods the two main contributions are methods named SPICE and LIKES - both of them are user parameter free sparse estimation methods applicable for line spectral estimation. The other important contributions are extensions of SPICE and LIKES to multivariate time series and array processing models, and a solution to the grid selection problem in sparse estimation of spectral-line parameters. The third and final part of the thesis contains applications of the methods discussed in the thesis to the problem of radial velocity data analysis for exoplanet detection. Apart from the exoplanet application, an application based on Sudoku, which is related to sparse parameter estimation, is also discussed.

Le secteur de communications sécurisés et portables connait une véritable révolution avec l’apparition des plateformes dites radios logiciels (Software Defined Radios, SDRs). Les performances exceptionnelles de ces systèmes sont les résultats d’une interaction assez complexe et souvent peu évidente entre le logiciel embarqué, le circuit de traitement numérique et les blocs mixtes analogiques/RF. Cette complexité limite la testabilité du produit fini. La méthodologie de test utilisée actuellement a atteint ses limites dues au cout élevé, le long temps de test et le bas degré de généralisation. De plus, les plateformes SDRs peuvent évoluer sur le terrain et elles vont supporter des standards et des scénarios qui n’ont pas été considérés pendant le la phase de conception. Donc, une stratégie de test sur le terrain (en ligne) n’est plus une caractéristique optionnelle mais une nécessité. Dans ce contexte, le but de notre recherche est d’inventer et développer une méthodologie de test capable de garantir le bon fonctionnement d’une plateforme SDR après la production et pendant sa vie. Notre objectif final est de réduire le coût du test en profitant de la reconfigurabilité de la plateforme. Pour les radios tactiques qui doivent être mises à jour sur le terrain sans équipement spécial, les stratégies Built-In Self-Test (BIST) sont, sans doute, la seule moyenne de garantir la conformité aux spécifications. Dans cette mémoire, nous introduisons une nouvelle architecture de test RF BIST qui utilise la technique de de sous-échantillonnage nonuniform à la sortie de l’émetteur (TX) d’une SDR afin d’évaluer la conformité de la masque spectrale. Notre solution s’appuie sur une implémentation autonome, est modulable et peut être appliquée pour le test sur le terrain avec des modifications minimes. Par rapport aux autres techniques de test analogiques/RF, cet approche ne dépends pas de la architecture du TX, ni d’un modèle ad-hoc, ce qui est idéale pour le test des SDRs. / The advent of increasingly powerful Integrated Circuits (IC) has led to the emergence of the Software Defined Radio (SDR) concept, which brought the sector of secured mobile communications into a new era. The outstanding performance of these systems results from optimal trade-offs among advanced analog/Radio Frequency (RF) circuitry, high-speed reconfigurable digital hardware and sophisticated real-time software. The inherent sophistication of such platforms poses a challenging problem for product testing. Currently deployed industrial test strategies face rising obstacles due to the costlier RF test equipment, longer test time and lack of flexibility. Moreover, an SDR platform is field-upgradeable, which means it will support standards and scenarii not considered during the design phase. Therefore, an in-field test strategy is not anymore 'a nice to have' feature but a mandatory requirement. In this context, our research aims to invent and develop a new test methodology able to guarantee the correct functioning of the SDR platform post-fabrication and over its operational lifetime. The overall aim of our efforts is to reduce post-manufacture test cost of SDR transceivers by leveraging the reconfigurability of the platform.For tactical radio units that must be field-upgradeable without specialized equipment, Built-in Self-Test (BIST) schemes are arguably the only way to ensure continued compliance to specifications. In this study we introduce a novel RF BIST architecture which uses Periodically Nonuniform Sampling (PNS2) of the transmitter (TX) output to evaluate compliance to spectral mask specifications. Our solution supports a stand-alone implementation, is scalable across a wide set of complex specifications and can be easily applied for in-field testing with small added hardware. Compared to existing analog/RF test techniques, this approach is not limited to a given TX architecture and does not rely on an ad-hoc TX model, which makes it ideal for SDR testing.

Le secteur de communications sécurisés et portables connait une véritable révolution avec l’apparition des plateformes dites radios logiciels (Software Defined Radios, SDRs). Les performances exceptionnelles de ces systèmes sont les résultats d’une interaction assez complexe et souvent peu évidente entre le logiciel embarqué, le circuit de traitement numérique et les blocs mixtes analogiques/RF. Cette complexité limite la testabilité du produit fini. La méthodologie de test utilisée actuellement a atteint ses limites dues au cout élevé, le long temps de test et le bas degré de généralisation. De plus, les plateformes SDRs peuvent évoluer sur le terrain et elles vont supporter des standards et des scénarios qui n’ont pas été considérés pendant le la phase de conception. Donc, une stratégie de test sur le terrain (en ligne) n’est plus une caractéristique optionnelle mais une nécessité. Dans ce contexte, le but de notre recherche est d’inventer et développer une méthodologie de test capable de garantir le bon fonctionnement d’une plateforme SDR après la production et pendant sa vie. Notre objectif final est de réduire le coût du test en profitant de la reconfigurabilité de la plateforme. Pour les radios tactiques qui doivent être mises à jour sur le terrain sans équipement spécial, les stratégies Built-In Self-Test (BIST) sont, sans doute, la seule moyenne de garantir la conformité aux spécifications. Dans cette mémoire, nous introduisons une nouvelle architecture de test RF BIST qui utilise la technique de de sous-échantillonnage nonuniform à la sortie de l’émetteur (TX) d’une SDR afin d’évaluer la conformité de la masque spectrale. Notre solution s’appuie sur une implémentation autonome, est modulable et peut être appliquée pour le test sur le terrain avec des modifications minimes. Par rapport aux autres techniques de test analogiques/RF, cet approche ne dépends pas de la architecture du TX, ni d’un modèle ad-hoc, ce qui est idéale pour le test des SDRs. / The advent of increasingly powerful Integrated Circuits (IC) has led to the emergence of the Software Defined Radio (SDR) concept, which brought the sector of secured mobile communications into a new era. The outstanding performance of these systems results from optimal trade-offs among advanced analog/Radio Frequency (RF) circuitry, high-speed reconfigurable digital hardware and sophisticated real-time software. The inherent sophistication of such platforms poses a challenging problem for product testing. Currently deployed industrial test strategies face rising obstacles due to the costlier RF test equipment, longer test time and lack of flexibility. Moreover, an SDR platform is field-upgradeable, which means it will support standards and scenarii not considered during the design phase. Therefore, an in-field test strategy is not anymore 'a nice to have' feature but a mandatory requirement. In this context, our research aims to invent and develop a new test methodology able to guarantee the correct functioning of the SDR platform post-fabrication and over its operational lifetime. The overall aim of our efforts is to reduce post-manufacture test cost of SDR transceivers by leveraging the reconfigurability of the platform.For tactical radio units that must be field-upgradeable without specialized equipment, Built-in Self-Test (BIST) schemes are arguably the only way to ensure continued compliance to specifications. In this study we introduce a novel RF BIST architecture which uses Periodically Nonuniform Sampling (PNS2) of the transmitter (TX) output to evaluate compliance to spectral mask specifications. Our solution supports a stand-alone implementation, is scalable across a wide set of complex specifications and can be easily applied for in-field testing with small added hardware. Compared to existing analog/RF test techniques, this approach is not limited to a given TX architecture and does not rely on an ad-hoc TX model, which makes it ideal for SDR testing.