This thesis investigates possibilities to perform image interpolation on an FPGA instead of on a graphics card. The images will be used for 3D display on Setred AB’s screen and an implementation in firmware will hopefully give two major advantages over the existing rendering methods. First, an FPGA can handle big amounts of data and perform a lot of calculations in parallel. Secondly, the amount of data to transfer is drastically increased after the interpolation and with this, a higher bandwith is required to transfer the data at a high speed. By moving the interpolation as close to the projector as possible, the bandwidth requirements can be lowered. Both these points will hopefully be improved, giving a higher frame rate on the screen. The thesis consists of three major parts, where the first handles methods to increase the resolution of images. Especially nearest neighbour, bilinear and bicubic interpolation is investigated. Bilinear interpolation was considered to give a good trade off between image quality and calculation cost and was therefore implemented. The second part discusses how a number of perspectives can be interpolated from one or a few captured images and the corresponding depth or disparity maps. Two methods were tested and one was chosen for a final implementation. The last part of the thesis handles Multi Video, a method that can be used to slice the perspectives into a form that is needed for the Scanning Slit display to show them correctly. The quality of the images scaled with bilinear interpolation is satisfactory if the scale factor is kept reasonably low. The perspectives interpolated in the second part show good quality with lots of details but suffers from some empty areas. Further improvements of this function is not necessary but would increase the image quality further. An acceptable frame rate has been achieved but further improvements of the speed can be performed. The most important continuation of this thesis is to integrate the implemented parts with the existing firmware and with that enable a real test of the performance.

No description available.

Mannheim, Univ., Diss., 2006.

La modélisation numérique via la méthode des éléments finis utilise classiquement des fonctions de forme polynomiale qui de par leur régularité représentent difficilement des évolutions singulières telles que celles observées dans les phénomènes de localisation en mécanique. Pour pallier cette difficulté, ces travaux de thèse ont eu pour objectif de proposer un nouveau support d'approximation adaptatif couplant la méthode de représentation par ondelettes à la méthode des éléments finis classique. Dans le domaine du traitement du signal, la méthode des ondelettes montre un réel potentiel pour traiter les phénomènes singuliers. L'étude porte sur la création d'un support de discrétisation hybride, associant une interpolation polynomiale et une interpolation en ondelettes exprimée via la fonction d'échelle de l'ondelette de Daubechies. Ce couplage permet de représenter la partie régulière de la réponse via le support polynomial et les éventuelles singularités à l'aide du support en ondelettes. L'adaptation du support hybride est effectuée via l'apport multirésolution, qui ajuste le support en fonction de l'importance des singularités observées. Une méthodologie de détection et d'enrichissement automatique est réalisée ayant pour objectif d'obtenir le support optimum. L'ondelette de Daubechies n'étant connue qu'en des points discrets, une méthode d'intégration particulière est proposée. Une modification de l'interpolation naturellement non nodale de l'ondelette est également introduite, de manière à pouvoir imposer des conditions limites classiques nodales. Une illustration de la méthode et de son implémentation informatique est présentée via une étude académique 1D. / The numerical modelling with the finite element method conventionally uses functions of polynomial form which, by their regularity, hardly represent singular evolutions such as those observed in the phenomena of localization in mechanics. To solve the issue, the aim of this thesis was to propose a new adaptive approximation support coupling the wavelet representation with the classical finite element method. In the field of signal processing, the wavelet method shows a real capacity to treat singular phenomena. This research study deals with the creation of a hybrid discretisation support, including a polynomial interpolation and a wavelet interpolation formulated with the scaling function of the Daubechies wavelet. The regular part of the solution is represented with the polynomial support and the singularities are visualised with the wavelet support. The adaptation of the hybrid support is carried out with the multiresolution contribution, which adjusts the support according to the importance of observed singularities. An automatic detection and enrichment method is carried out in order to obtain the optimum support. The Daubechies wavelet being known only in discrete points, a particular integration method is proposed. A modification of the not nodal naturally interpolated wavelet interpolation is also introduced, in order to impose classical nodal boundary conditions. An illustration of the method and its computer implementation is presented via a 1D academic study.

Ce travail de thèse en Mathématiques Appliquées a été effectué au sein du service Capteurs et Systèmes Electroniques (SCSE) au CEA-Leti, organisme majeur de la recherche publique française implanté à Grenoble. Il s'inscrit dans le cadre d'une collaboration avec le laboratoire de mathématiques appliquées Jean Kuntzmann (LJK) de l'Université Joseph Fourier (UJF). Le Leti développe des systèmes de capteurs de données terrestres (magnétomètres, accéléromètres...) capables de se géoréférencer de manière autonome. Placés sur des objets, ces dispositifs de capteursfournissent leur orientation propre dans l'espace, et ouvrent donc un vaste champ d'applications dans le domaine de l'acquisition et la reconstruction de formes.Le problème de la reconstruction de surfaces à partir de données d'orientation non structurées est par essence un problème mal posé. Cependant, des travaux précédents effectués au Leti ont permis de dégager un protocole fournissant un cadre valide pour le processus de reconstruction. Les capteurs ont été intégrés dans les rubans Morphosense : ces rubans souples équipés de noeuds de capteurs selon unegéométrie connue permettent ainsi le développement d'algorithmes de reconstruction de la courbe suivie par le ruban. L'application de rubans Morphosense sur une surface physique permet alors d'acquérir la famille des courbes suivies par les rubans et tracées sur la surface. Il s'agit ensuite d'exploiter le réseau des courbes ainsi obtenues pour reconstruire la surface. Dans un premier temps, nous revisitons la question de la reconstruction du ruban. Nous proposons des algorithmes de reconstruction de la courbe 3D suivie par le ruban Morphosense prenant maintenant en compte l'intégralité des données fournies par les capteurs d'orientation, ainsi que les propriétés méca-niques du ruban qui le conduisent à suivre des courbes géodésiques sur une surface. De ce point de vue, la reconstruction peut être considérée comme optimale.On étudie ensuite un ensemble de méthodes pour la reconstruction de surfaces à partir d'un réseau de courbes rubans. Dans le cas général, un tel type de réseau conduit à des problèmes de fermeture et d'estimation de données manquantes. La question de la fermeture, d'ordre essentiellement numérique et liée à des contraintes différentielles, concerne le réseau des courbes et la difficulté d'obtenir des contoursfermés. La question cruciale de l'estimation des données manquantes traduit le fait qu'aucune information sur la surface n'est connue et accessible en dehors du réseau des courbes rubans.Afin de s'affranchir de ces problèmes et de proposer des solutions pratiques pour la reconstruction, il est nécessaire de faire des hypothèses sur le modèle de surfaces à reconstruire ou sur la topologie de réseau de courbes acquises. Les méthodes développées s'inscrivent donc dans l'une des deux approchessuivantes.– D'une part des méthodes de reconstruction de surfaces développables et quasi-développables, qui modélisent de manière satisfaisante les surfaces étudiées dans le cadre de nombreuses applications.– D'autre part des méthodes de reconstruction à partir d'une topologie spécifique de réseaux de courbes (courbes quasi-planaires, contour ouvert), permettant de résoudre le problème de fermeture.L'ensemble des méthodes proposées dans ces travaux permet ainsi de formuler un processus global de reconstruction de surfaces, qu'il est possible d'adapter aux problèmes étudiés en pratique, afin de proposer une solution à la fois simple et précise dans chaque cas. La validation des résultats dans le cadre des données réelles fournies par les rubans Morphosense nous a conduit à développer des dispositifs métrologiques. Enfin, notons que le contexte général des données d'orientation étudié ici soulève des problématiques peu classiques, voire nouvelles, auxquelles nous avons essayé d'apporter des solutions originales, en particulier au travers d'algorithmes d'interpolation et d'optimisation. / This PhD thesis in applied mathematics was conducted within the Electronic Systems andSensors department of the CEA-Leti (Atomic Energy and Alternative Energies Commission - Laboratory for Electronics and Information Technologies), a major organism for technological research located in Grenoble, France. This work originated from a partnership with the applied mathematics laboratory (LJK) of the Joseph Fourier university (UJF). The Leti develops embedded systems equiped with micro-sensors (magnetometers, accelerometers...) from which it is possible to retrieve informations about their spatial orientation. These systems allow for innovative applications in the field of shape acquisition and reconstruction. The problem of reconstructing surfaces from unstructured orientation data is ill-posed. However, previous work done within the Leti came up with a valid reconstruction protocol. The micro-sensors were integrated into the Morphosense ribbon : this flexible ribbon instrumented with sensor knots according to a known geometry is at the core of a number of reconstruction algorithms for the curves followed by the ribbon. When lied on a physical surface, Morphosense ribbons then allow the acquisition and reconstruction of a network of curves on the surface, that are then used for the reconstruction of the entire surface. We first propose new algorithms for curve reconstruction thanks to the Morphosense ribbon. Those new methods now integrate the orientation informations provided by the sensors in their entirety, as well as the mechanical properties of the ribbon that force it to follow geodesic curves on a surface. From this point of view, the curve reconstruction can be considered optimal, as it integrates all the information embedded in the ribbons' structure. We then study a set of methods for the reconstruction of surfaces using a network of ribbon curves. Such a network generally leads to problems linked to the closure of the network and missing data estimation. The closure of the network is essentially a numerical problem related to differential constraints. The missing data corresponds to the lack of information on the surface outside the network of curves. In order to deal with these problems and propose practical solutions for the reconstruction, hypotheses either on the surface models or the topology of the network of curves are required. Therefore, the developed methods fall within the two following approaches.– On the one hand, reconstruction methods for developable and quasi-developable surfaces, which are a good approximation for the surfaces considered in numerous applications.– On the other hand, reconstruction methods from networks of curves with specific topologies (quasi-planar curves, open network) so as to deal with the closure problem.The set of methods developed in this work allow to formulate a global process for the reconstruction of surfaces, with flexible algorithms adapting to the different practical situations, so as to propose a solution both simple and precise in each case. The validation of our results in the case of real sensors data provided by the Morphosense ribbons also led us to develop metrological device. Finally, notice that the general context of reconstruction from orientation data studied here raises original theorical problems, to which we tried to answer with innovative solutions through interpolation and optimization algorithms.

In oil industry, it is essential to have the knowledge of the stratified rocksâ lithology and, as consequence, where are placed the oil and the natural gases reserves, in order to efficiently drill the soil, without a major expense. In this context, the analysis of seismological data is highly relevant for the extraction of such hydrocarbons, producing predictions of profiles through reflection of mechanical waves in the soil. The image of the seismic mapping produced by wave refraction and reflection into the soil can be analysed to find geological formations of interest. In 1978, H. Sakoe et al. defined a model called Dynamic Time Warping (DTW)[23] for the local detection of similarity between two time series. We apply the Dynamic Time Warping Interpolation (DTWI) strategy to interpolate and simulate a seismic landscape formed by 129 depth-dependent sequences of length 201 using different values of known sequences m, where m = 2, 3, 5, 9, 17, 33, 65. For comparison, we done the same operation of interpolation using a Standard Linear Interpolation (SLI). Results show that the DTWI strategy works better than the SLI when m = 3, 5, 9, 17, or rather when distance between the known series has the same order size of the soil layers.

Nous étudions des problèmes d'interpolation dans des espaces de fonctions analytiques et notamment les espaces de Paley-Wiener.Nous démontrons que l'opérateur de restriction associé à une suite de nombres complexes supposée a priori N-Carleson dans tout demi-plan, définit un isomorphisme entre l'espace de Paley-Wiener et un certain espace de suites (construit à l'aide de différences divisées) si et seulement si la suite en question vérifie certaines conditions, notamment la condition de Muckenhoupt. Ce résultat généralise un résultat de Lyubarskii et Seip de 1997.Nous montrons également que toute suite minimale dans l'espace de Paley-Wiener et telle que l'intersection avec tout demi-plan vérifie la condition de Carleson, est une suite d'interpolation dans tout espace de Paley-Wiener "plus grand", au sens du type exponentiel. Ce dernier résultat s'étend à l'interpolation pondérée et s'applique à la Théorie du contrôle. / We study interpolation problems in spaces of analytic functions and in particular in Paley-Wiener spaces.We show that the restriction operator associated to some N-Carleson sequence is an isomorphism between the Paley-Wiener space and a certain space of sequences (contructed with the help of divided differences) if and only if the sequence satisfies some conditions, in particular the Muckenhoupt condition. This result is a generalization of a theorem of Lyubarskii and Seip obtained in 1997.We also show that every minimal sequence in PW such that the intersection with every half-plane satisfies the Carleson condition is actually an interpolating sequence in every “bigger” space in the sense of the exponential type. This result can be extended to weighted interpolation and has an application in Control Theory.

We consider the problem of optimizing the choice of interpolation nodes such that the interpolation error is minimized, given the constraint that none of the nodes may be placed inside a forbidden region. Restricting the problem to using one-dimensional polynomial interpolants, we explore different ways of quantifying the interpolation error; such as the integral of the absolute/squared difference between the interpolated function and the interpolant, or the Lebesgue constant, which compares the interpolant with the best possible approximating polynomial of a given degree. The interpolation error then serves as a cost function that we intend to minimize using gradient-based optimization algorithms. The results are compared with existing theory about the optimal choice of interpolation nodes in the absence of a forbidden region (mainly due to Chebyshev) and indicate that the Chebyshev points of the second kind are near-optimal as interpolation nodes for optimizing the Lebesgue constant, whereas placing the points as close as possible to the forbidden region seems optimal for minimizing the integral of the difference between the interpolated function and the interpolant. We conclude that the Chebyshev points of the second kind serve as a great choice of interpolation nodes, even with the constraint on the placement of the nodes explored in this paper, and that the interpolation nodes should be placed as close as possible to the forbidden region in order to minimize the interpolation error.

Groundwater water resources must be accurately characterized in order to be managed sustainably. Due to the cost to install monitoring wells and challenges in collecting and managing in-situ data, groundwater data is sparse in space and time especially in developing countries. In this study we analyzed long-term groundwater storage changes with limited times-series data where each well had only one groundwater measurement in time. We developed methods to synthetically create times-series groundwater table elevation (WTE) by clustering wells with uniform grid and k-means-constrained clustering and creating pseudo wells. Pseudo wells with the WTE values from the cluster-member wells were temporally and spatially interpolated to analyze groundwater changes. We used the methods for the Beryl-Enterprise aquifer in Utah where other researchers quantified the groundwater storage depletion rate in the past, and the methods yielded a similar storage depletion rate. The method was then applied to the southern region in Niger and the result showed a ground water storage change that partially matched with the trend calculated by the GRACE data. With a limited data set that regressions or machine learning did not work, our method captured the groundwater storage trend correctly and can be used for the area where in-situ data is highly limited in time and space.

Video frame rate up-conversion is an important issue for multimedia systems in achieving better video quality and motion portrayal. Motion-compensated methods offer better quality interpolated frames since the interpolation is performed along the motion trajectory. In addition, computational complexity, regularity, and memory bandwidth are important for a real-time implementation. Motion-compensated frame rate up-conversion (MC-FRC) is composed of two main parts: motion estimation (ME) and motion-compensated frame interpolation (MCFI). Since ME is an essential part of MC-FRC, a new fast motion estimation (FME) algorithm capable of producing sub-sample motion vectors at low computational-complexity has been developed. Unlike existing FME algorithms, the developed algorithm considers the low complexity sub-sample accuracy in designing the search pattern for FME. The developed FME algorithm is designed in such a way that the block distortion measure (BDM) is modeled as a parametric surface in the vicinity of the integer-sample motion vector; this modeling enables low computational-complexity sub-sample motion estimation without pixel interpolation. MC-FRC needs more accurate motion trajectories for better video quality; hence, a novel true-motion estimation (TME) algorithm targeting to track the projected object motion has been developed for video processing applications, such as motion-compensated frame interpolation (MCFI), deinterlacing, and denoising. Developed TME algorithm considers not only the computational complexity and regularity but also memory bandwidth. TME is obtained by imposing implicit and explicit smoothness constraints on block matching algorithm (BMA). In addition, it employs a novel adaptive clustering algorithm to keep the low-complexity at reasonable levels yet enable exploiting more spatiotemporal neighbors. To produce better quality interpolated frames, dense motion field at the interpolation instants are obtained for both forward and backward motion vectors (MVs); then, bidirectional motion compensation using forward and backward MVs is applied by mixing both elegantly.