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.

Digital image data requires large compression ratio in applications like internet, communication and audio-visual environment. In this thesis, we realize the MPEG-4 codec standard on the ARM9-based platform and improve the execution performance by efficient implementations of the core operations such as Motion Estimation and DCT. In the assembly codes obtained by directly compiling the C codes, there exists a lot of redundant checking which causes a large amount of execution time waste. We rewrite some of the compiled assembly codes to improve the execution efficiency using a variety of techniques such as loop-unrolling and data-type optimization. We also analyze the experimental results using several benchmark video sequences with different modes.

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 recent years, the internet has been in widespread use and the number of internet subscribers increased quickly. Hence a lot of applications on the network have been developed, multimedia programs especially. Whereas the original video content always takes up considerable storage and transmission time which doesn¡¦t suit for network application, many video compression standards have been drawn up in the literature Due to the temporal redundancy of the video sequences, motion estimation / compensation has been widely used in many interframe video coding protocols to reduce the required bit rates for transmission and storage of video signals by eliminating it, such as the MPEG-1, MPEG-2, H.261 and H.263. The performance and speed of the interframe motion estimation method for video sequence compression are the important issues especially in networking application such as video conference and video on demand. Today all motion estimating method find out the estimating point which has minimal Mean Square Error, and motion compensation aim at estimating error to do JPEG. compression. As everyone knows, JPEG employs DCT to eliminate the correlation of spatial domain. So the best motion estimating point is the point which has the minimal compressed data size. In some alalyses show that over 50% best estimating point do not have the minimal compressed data size. So the factor which effects the compressed data size is correlation coefficient and not MSE. Hence, we try to define a new criterion for motion estimation which can get better motion compensation with less compressing bit rate. To reach this goal, we try to find out the correlation among the motion compensation as the new criterion for motion estimation.

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