With the rapid growth of multimedia information, video coding standards have become crucial when transmitting large amount of video data. Motion estimation promises to be the key to high performance in video coding by removing the temporal redundancy of video data for storage and transmission. Video transcoding also becomes a significant scheme applied in different bandwidth transform. Due to their fundamentality, research works on motion estimation and video transcoding have been conducted extensively. In this thesis, an overview of video compression technique is presented with emphasis on motion estimation. Then, a survey of most representative motion estimation search algorithms and the proposed motion estimation algorithms are introduced. The evaluation and analysis of these algorithms based on a number of experiments on several famous test video sequences is presented. In addition, an efficient video transcoding via visual attention model with Lagrange optimization to minimum rate-distortion cost is proposed. Finally, an investigation of the future trend of video coding is discussed. Through the proposed algorithms of motion estimation, the computational complexity can be significantly reduced despite the fact that the objective quality of motion compensated images is slightly degraded. Moreover, through the proposed video transcoding method, the bit rate can be reduced to fit the requirement of bandwidth.

Multimedia on network has been an integral part of our life because of the development of network and the evolution of video transmission technology. Motion estimation algorithm is an important part of video transmission technology. If we can parallelize the calculation, the efficiency of will be raised in order to be realized on embedded system. At present, the more common estimation algorithm is Full Search, Three-Step Search, Diamond Search and so on. We will optimize the Three-Step Search and the Diamond Search. IBM Cell platform architecture with a PPE and eight SPE is a heterogeneous type multi-core system. It can be thread-level and data-level to a high degree of parallel processing, and has a rapid memory parallel system of information processing demand for data bandwidth problem. In addition, IBM provides a very convenient virtual platform, so we have chosen to explore as a means of bringing the platform. In this paper, the best way to optimize the algorithm is based on characteristics of Cell processor such as the and high-speed data channel, vector instructions, NUMA (Non-Uniform Memory Access) the heterogeneity of multi-core architecture, the design of multiple buffering of DMA (Direct Memory Access) mechanisms and using vector SIMD computer mechanism to replace the original scalar computing mechanism and to reduce the number of branch instructions to avoid causing the penalty due to branch miss. Based on the acceleration of the above mechanism, we design algorithms for motion estimation in the use of CIF image size and the use of reference images of five cases the experimental results can be achieved for each image processing speed of 13.26ms.

No description available.

In this thesis, we presented two case studies on vision-based moving objects measurement. In the first case, we used a monocular camera to perform ego-motion estimation for a robot in an urban area. We developed the algorithm based on vertical line features such as vertical edges of buildings and poles in an urban area, because vertical lines are easy to be extracted, insensitive to lighting conditions/shadows, and sensitive to camera/robot movements on the ground plane. We derived an incremental estimation algorithm based on the vertical line pairs. We analyzed how errors are introduced and propagated in the continuous estimation process by deriving the closed form representation of covariance matrix. Then, we formulated the minimum variance ego-motion estimation problem into a convex optimization problem, and solved the problem with the interior-point method. The algorithm was extensively tested in physical experiments and compared with two popular methods. Our estimation results consistently outperformed the two counterparts in robustness, speed, and accuracy. In the second case, we used a camera-mirror system to measure the swimming motion of a live fish and the extracted motion data was used to drive animation of fish behavior. The camera-mirror system captured three orthogonal views of the fish. We also built a virtual fish model to assist the measurement of the real fish. The fish model has a four-link spinal cord and meshes attached to the spinal cord. We projected the fish model into three orthogonal views and matched the projected views with the real views captured by the camera. Then, we maximized the overlapping area of the fish in the projected views and the real views. The maximization result gave us the position, orientation, and body bending angle for the fish model that was used for the fish movement measurement. Part of this algorithm is still under construction and will be updated in the future.

The performance and speed of the interframe motion estimation method for sequencial frame sequence compression are the important issues especially in networking application such as video conference and video on demand. In this paper, we proposed a new fast search algorithm for motion estimation on block matching technique called the cocktail search algorithm (CTS). This new algorithm takes advantages of prior search algorithms proposed in the literature and improves at our observations. The experiment results show that the proposed CTS algorithm can provide the better performance and require less computational costs than others. In other words, the CTS can obtain the accurate motion vector efficiently and fast. The fruitful results is achieved by not only holding the original benefit but also constructively improving the existing drawbacks.

In this paper a novel Hierarchical Sum of Double Difference metric, HSDD, was introduced. It was shown, as opposed to conventional Sum of Absolute Difference (SAD) metric, how this embedded-coding aware metric can jointly constrain the motion vector searching in both temporal and spatial (quad-tree) directions under multiresolution motion estimation (MRME) framework. The temporal-spatial co-optimization concept from HSDD brings us the motion compensation pyramid with better shape. The reward is that fewer bits are spent later for describing the isolated zeros. The compression performance of HSDD easily exceeds the performance of its competitors, especially when high compression ratios are used.

Στη σημερινή εποχή οι μεταγλωττιστές κατέχουν έναν σημαντικό ρόλο στην υψηλή απόδοση των υπολογιστικών συστημάτων είτε επιτραπέζιων, είτε εξυπηρετητών, είτε ενσωματωμένων. Ο λόγος είναι ότι στη σημερινή εποχή όλες σχεδόν οι εφαρμογές γράφονται σε γλώσσες υψηλού επιπέδου και συνεπώς απαιτείται μεταγλώττιση ώστε τα προγράμματα να τρέξουν σε γλωσσά μηχανής. Η ραγδαία όμως αύξηση της απόδοσης των υπολογιστικών συστημάτων όμως έχει δημιουργήσει την απαίτηση για αποδοτικές εφαρμογές. Έτσι ποιότητα του παραγομένου κώδικα που προκύπτει είναι κρίσιμη για την ορθή και γρήγορη εκτέλεση τους για αυτό το λόγω γίνεται σημαντική ερευνά στη συγγραφή μεταγλωττιστών που θα ικανοποιεί τις παραπάνω απαιτήσεις. Αν και σήμερα υπάρχει μέλλον στην ανάπτυξη των μεταγλωττιστών υπάρχει ζήτημα για τα ενσωματωμένα συστήματα. Λόγω του ότι πρέπει να είναι έχουν χαμηλό κόστος, χαμηλή κατανάλωση ισχύος χρησιμοποιούν υποτυπώδεις μεταγλωττιστές. Επειδή όμως τα ενσωματωμένα συστήματα είναι μεγάλος κλάδος των υπολογιστικών συστημάτων με εφαρμογές σε πληθώρα θεμάτων πρέπει οι εφαρμογές αυτές να είναι σωστές και να «τρέχουν» γρήγορα. Αυτό έχει ωθήσει τους προγραμματιστές στην μελέτη των compilers και των μετασχηματισμών που κάνουν και έχει δώσει μια νέα κατεύθυνση στη βελτιστοποίηση προγραμμάτων με το χέρι με χρήση τεχνικών μεταγλωττιστών αλλά και με υψηλοτέρου επιπέδου βελτιστοποιήσεις που δεν γίνονται ακόμα από μεταγλωττιστές. Σκοπός αυτής της εργασίας είναι η μελέτη και βελτιστοποίηση της εφαρμογής για πολυμέσα motion estimation by 4 με στόχο την αύξηση της ταχύτητας εκτέλεσης σε ένα πλήθος αρχιτεκτονικών διατάξεων λαμβάνοντας υπόψη το πλήθος των πράξεων και την ιεραρχία μνήμης. Η εξομοίωση των βελτιωμένων προγραμμάτων έδειξε ότι μπορούμε να επιτύχουμε σημαντική μείωση του χρόνου εκτέλεσης ακόμα και σε αρχιτεκτονικές που δεν αξιοποιούν στο μέγιστο δυνατό τις απαιτήσεις που έχουν αυτά. / In our days compilers play a crucial role in the performance of computer systems (desktop PCs, servers, embedded systems). The reason is that almost every application is created in high level programming languages and compilation is required so that the program will eventually run in machine language. However the rapid increase of computer systems’ performance demands more efficient applications. The quality of the code that is created is critical for fast and correct execution of the applications. For this reason much research is done in the area of creating compilers that fulfill the above requirements. Although there is much future in the development of compilers, important issues arise about the embedded systems. Such systems should be characterized by low cost and low power. For this reason the compilers used are quite simple. However, the embedded systems are a very important branch of computer systems with a variety of applications, which should be executed fast and correctly. These requirements are a motivation for the programmers to study the compilers and the transformations they use and lead to program optimization “by hand” using compiler techniques, as well as higher level optimization techniques that are not used by compilers yet. The purpose of this thesis is the study and optimization of the multimedia application “motion estimation by 4”. Our main goal is to increase the execution speed in a variety of different architectural designs taking into account the amount of computation and the memory hierarchy. The simulation of the improved programs proved that we can accomplish important reduction of the execution time even in architectures that are not suitable for these specific programs.

Les architectures mixtes contenant des composants programmables et d'autres reconfigurables peuvent fournir les performances de calcul nécessaires pour satisfaire les contraintes imposées aux applications temps réel. Mais l'implantation et d'optimisation de ces applications temps réel sur ce type d'architectures est une tâche complexe qui prend un temps énorme. Dans ce contexte, nous proposons un outil de prototypage rapide visant ce type d'architectures. Cet outil se base sur une extension que nous proposons de la méthodologie Adéquation Algorithme Architecture (AAA). Il permet d'effectuer automatiquement le partitionnement et l'ordonnancement optimisés des opérations de l'application sur les composants de l'architecture cible et la génération automatique des codes correspondants. Nous avons utilisé cet outil pour l'implantation de l'estimateur de mouvement de la norme H.264/AVC sur une architecture composée d'un processeur NIOS II d'Altera et d'un FPGA Stratix III. Ainsi nous avons pu vérifier le bon fonctionnement de notre outil et validé notre générateur automatique de code mixte / Mixed architectures containing programmable devices and reconfigurable ones can provide calculation performance necessary to meet constraints of real-time applications. But the implementation and optimization of these applications on this kind of architectures is a complex task that takes a lot of time. In this context, we propose a rapid prototyping tool for this type of architectures. This tool is based on our extension of the Adequacy Algorithm Architecture methodology (AAA). It allows to automatically perform optimized partitioning and scheduling of the application operations on the target architecture components and generation of correspondent codes. We used this tool for the implementation of the motion estimator of the H.264/AVC on an architecture composed of a Nios II processor and Altera Stratix III FPGA. So we were able to verify the correct running of our tool and validate our automatic generator of mixed code

This study contributes to the domain of application specific adaptive hardware architectures with a design approach on processing element array, interconnect structure and memory interface concurrently. As summarized below, our architectural design choices push the limits of on-chip data reuse and avoid redundant computations that are essential for the high throughput, small area, and low power demands of the consumer market.Motion estimation (ME) is a key component in the H.264/AVC standard. Full Search (FS) based ME achieves optimal peak signal-to-noise-ratio (PSNR), and is the most adopted algorithm for developing hardware motion estimators. In this study, we first design a variable block size motion estimation (VBSME) engine based on hybrid grained processing elements (PEs) and a 2D programmable interconnect structure, which is adaptive to all block size configurations of H.264. PEs operate in bit-serial manner using MSB-first arithmetic for early termination to reduce the amount of computations, and the 2D architecture enables on-chip data reuse between neighboring PEs in a bit-by-bit pipelined fashion. Our design reduces the gate count by 7x compared to its ASIC counterpart, operates at a comparable frequency while sustaining 30 and 60 frames per second (fps); and outperforms bit parallel and bit serial architectures in terms of throughput and performance per gate.Numerous fast search algorithms (diamond, hexagon, three-step, etc.) have been developed to reduce the computation burden and the excessive amount of memory transactions required by FS, with a compromise in compression quality. We improve our VBSME engine and introduce the first adaptive ME architecture that provides the end user with the flexibility of choosing between the high quality video service during power-rich state (FS mode), and extended video service (fast search mode). We resolve the irregular indexing scheme challenge of three-step search (3SS) by introducing an on-chip buffer structure with a memory interface, which is adaptive to data access patterns of the FS and 3SS methods. The architecture sustains the real time CIF format (352x288) video encoding at 30fps with an operational frequency as low as 17.6MHz, and consumes 1.98mW based on the 45nm technology, outperforming all other FS and 3SS architectures.

abstract: Medical ultrasound imaging is widely used today because of it being non-invasive and cost-effective. Flow estimation helps in accurate diagnosis of vascular diseases and adds an important dimension to medical ultrasound imaging. Traditionally flow estimation is done using Doppler-based methods which only estimate velocity in the beam direction. Thus when blood vessels are close to being orthogonal to the beam direction, there are large errors in the estimation results. In this dissertation, a low cost blood flow estimation method that does not have the angle dependency of Doppler-based methods, is presented. First, a velocity estimator based on speckle tracking and synthetic lateral phase is proposed for clutter-free blood flow. Speckle tracking is based on kernel matching and does not have any angle dependency. While velocity estimation in axial dimension is accurate, lateral velocity estimation is challenging due to reduced resolution and lack of phase information. This work presents a two tiered method which estimates the pixel level movement using sum-of-absolute difference, and then estimates the sub-pixel level using synthetic phase information in the lateral dimension. Such a method achieves highly accurate velocity estimation with reduced complexity compared to a cross correlation based method. The average bias of the proposed estimation method is less than 2% for plug flow and less than 7% for parabolic flow. Blood is always accompanied by clutter which originates from vessel wall and surrounding tissues. As magnitude of the blood signal is usually 40-60 dB lower than magnitude of the clutter signal, clutter filtering is necessary before blood flow estimation. Clutter filters utilize the high magnitude and low frequency features of clutter signal to effectively remove them from the compound (blood + clutter) signal. Instead of low complexity FIR filter or high complexity SVD-based filters, here a power/subspace iteration based method is proposed for clutter filtering. Excellent clutter filtering performance is achieved for both slow and fast moving clutters with lower complexity compared to SVD-based filters. For instance, use of the proposed method results in the bias being less than 8% and standard deviation being less than 12% for fast moving clutter when the beam-to-flow-angle is $90^o$. Third, a flow rate estimation method based on kernel power weighting is proposed. As the velocity estimator is a kernel-based method, the estimation accuracy degrades near the vessel boundary. In order to account for kernels that are not fully inside the vessel, fractional weights are given to these kernels based on their signal power. The proposed method achieves excellent flow rate estimation results with less than 8% bias for both slow and fast moving clutters. The performance of the velocity estimator is also evaluated for challenging models. A 2D version of our two-tiered method is able to accurately estimate velocity vectors in a spinning disk as well as in a carotid bifurcation model, both of which are part of the synthetic aperture vector flow imaging (SA-VFI) challenge of 2018. In fact, the proposed method ranked 3rd in the challenge for testing dataset with carotid bifurcation. The flow estimation method is also evaluated for blood flow in vessels with stenosis. Simulation results show that the proposed method is able to estimate the flow rate with less than 9% bias. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2018