With the emergence of large-scale distributed computing applications semistructured data models have gained significant importance. Current practical semistructured data management systems can often not provide the performance required by practical applications. This work describes a model for the optimisation of semistructured data processing based on data groupings. Such groupings are of fundamental importance for efficient querying of semistructured data. The semistructured model does not imply the natural organisation of data that characterises rigidly structured representations. Instead, data groupings in the semistructured case must be derived from the data itself or its applications. This thesis presents a number of such possible data groupings and formalises them into a concept of domains. Different classes of domains are identified and the impact on different data sources is evaluated. A particular definition is then used to implement an efficient physical representation using an approach based on dictionary compression adapted from relational data management. Finally this approach is combined with a data grouping aimed at the efficient resolution of structural constraints.

No description available.

No description available.

No description available.

In this thesis we present an overview of sparse approximations of grey level images. The sparse representations are realized by classic, Matching Pursuit (MP) based, greedy selection strategies. One such technique, termed Orthogonal Matching Pursuit (OMP), is shown to be suitable for producing sparse approximations of images, if they are processed in small blocks. When the blocks are enlarged, the proposed Self Projected Matching Pursuit (SPMP) algorithm, successfully renders equivalent results to OMP. A simple coding algorithm is then proposed to store these sparse approximations. This is shown, under certain conditions, to be competitive with JPEG2000 image compression standard. An application termed image folding, which partially secures the approximated images is then proposed. This is extended to produce a self contained folded image, containing all the information required to perform image recovery. Finally a modified OMP selection technique is applied to produce sparse approximations of Red Green Blue (RGB) images. These RGB approximations are then folded with the self contained approach.

In the recent several years, the popularity of High Definition and Three-Dimensional (3D) videos are creating significant challenge for the video compression techniques. There is an increasing demand for video coding tools with higher efficiency and lower complexity. Using advanced inter prediction technique the state-of-the-art video coding standard H.264/ A VC has achieved significant compression gains. However, the complexity of the inter prediction is extremely high, which limits the application of real-time video service. When applying H.264/ A VC to colour plus depth represented 3D videos, the inter prediction designed for Two-Dimensional (2D) videos is not efficient enough for depth map coding, since the depth map is only a 2D signal to aid virtual view rendering. The work described in this thesis speeds up the inter prediction by proposing several fast approaches. A novel inter prediction scheme for 3D video coding is developed to maximise rate distortion performance of rendering image and depth map bit rates. The thesis proposes four methods to reduce complexity of inter prediction. Firstly, the motion estimation searching points are reduced by proposing a novel Adaptive Direction Search algorithm. In this algorithm, the intensive search and coarse search regions are adaptively detected using predicted motion vector direction as an indicator. Secondly, an Adaptive Simulated Annealing Search algorithm is developed to further adjust the search pattern not only in directional regions but also in different distances. Thirdly, the thesis presents a hybrid fast mode decision algorithm, which is mainly based on Coded Block Pattern to infer block's homogeneity characteristic so that the unnecessary inter modes can be eliminated. Fourthly, an improved residual homogeneous based fast mode decision algorithm is proposed. Computational complexity can be further reduced at low Quantisation Parameter conditions. Experimental results indicate that using the proposed algorithms up to 70% of encoding time can be saved with negligible Rate Distortion performance losses. For depth map coding, a novel inter prediction scheme is proposed in this thesis. By employing rendered view distortion in Rate-Distortion Optimisation, the optimal motion vector and inter mode are determined to maximise the quality of the rendered views. An effective Lagrange multiplier is also derived. Finally, fast approaches have been implemented to reduce the complexity. Experimental results illustrate that up to 61 % of bitrate can be saved for depth map coding.

The current increases in silicon logic densities have made feasible the implementation of multiprocessor systems onto a single chip able to meet the intensive data processing demands of highly concurrent systems. This thesis describes research into a hardware implementation of a high performance parallel multi compressor chip. In order to fully explore the design space, several models are created at various levels of abstraction to capture the full characteristics of the architecture. A detailed investigation into the performances of alternative input and output routing strategies for realistic data sets demonstrate that the design of parallel compression devices involves important trade-offs that affect compression performance, latency, and throughput. The most promising approach is written in a hardware description language and synthesised for FPGA hardware as proof of concept. It is shown that a multi compressor architecture can be a scalable solution with the ability to operate at throughputs to cope with the demands of modern high-bandwidth applications whilst retaining good compression performance.

Σ΄αυτή τη διπλωματική εργασία μελετάμε κάποιους αλγορίθμους συμπίεσης δεδομένων και τους υλοποιούμε. Αρχικά, αναφέρονται βασικές αρχές της κωδικοποίησης και παρουσιάζεται το μαθηματικό υπόβαθρο της Θεωρίας Πληροφορίας. Παρουσιάζονται, επίσης διάφορα είδη κωδικών. Εν συνεχεία αναλύονται διεξοδικά η κωδικοποίηση Huffman και η αριθμητική κωδικοποίηση. Τέλος, οι δύο προαναφερθείσες κωδικοποιήσεις υλοποιούνται σε υπολογιστή με χρήση γλώσσας προγραμματισμού C και χρησιμοποιούνται για τη συμπίεση αρχείων κειμένου. Τα αρχεία που προκύπτουν συγκρίνονται με αρχεία που έχουν συμπιεστεί με χρήση προγραμμάτων του εμπορίου, αναλύονται τα αίτια των διαφορών στην αποδοτικότητα και εξάγονται χρήσιμα συμπεράσματα. / In this thesis we study some data compression algorithms and implement them. The basic principles of coding are mentioned and the mathematical foundation of information theory is presented. Also different types of codes are presented. Then the Huffman coding and arithmetic coding are analyzed in detail. Finally, the two codings are implemented on a computer using the C programming language in order to compress text files. The resulting files are compared with files that are compressed using commercial programmes, the causes of differences in the efficiency are analyzed and useful conclusions are drawn.

Les réseaux de capteurs sans fil d'images sont utilisés aujourd'hui dans de nombreuses applications qui diffèrent par leurs objectifs et leurs contraintes individuelles. Toutefois, le dénominateur commun de toutes les applications de réseaux de capteurs reste la vulnérabilité des noeuds-capteurs en raison de leurs ressources matérielles limitées dont la plus contraignante est l'énergie. En effet, les technologies sans fil disponibles dans ce type de réseaux sont généralement à faible portée, et les ressources matérielles (CPU, batterie) sont également de faible puissance. Il faut donc répondre à un double objectif : l'efficacité d'une solution tout en offrant une bonne qualité d'image à la réception. La contribution de cette thèse porte principalement sur l'étude des méthodes de traitement et de compression d'images au noeud-caméra, nous avons proposé une nouvelle méthode de compression d'images qui permet d'améliorer l'efficacité énergétique des réseaux de capteurs sans fil. Des expérimentations sur une plate-forme réelle de réseau de capteurs d'images ont été réalisées afin de démontrer la validité de nos propositions, en mesurant des aspects telles que la quantité de mémoire requise pour l'implantation logicielle de nos algorithmes, leur consommation d'énergie et leur temps d'exécution. Nous présentons aussi, les résultats de synthèse de la chaine de compression proposée sur des systèmes à puce FPGA et ASIC / The increasing development of Wireless Camera Sensor Networks today allows a wide variety of applications with different objectives and constraints. However, the common problem of all the applications of sensor networks remains the vulnerability of sensors nodes because of their limitation in material resources, the most restricting being energy. Indeed, the available wireless technologies in this type of networks are usually a low-power, short-range wireless technology and low power hardware resources (CPU, battery). So we should meet a twofold objective: an efficient solution while delivering outstanding image quality on reception. This thesis concentrates mainly on the study and evaluation of compression methods dedicated to transmission over wireless camera sensor networks. We have suggested a new image compression method which decreases the energy consumption of sensors and thus maintains a long network lifetime. We evaluate its hardware implementation using experiments on real camera sensor platforms in order to show the validity of our propositions, by measuring aspects such as the quantity of memory required for the implantation program of our algorithms, the energy consumption and the execution time. We then focus on the study of the hardware features of our proposed method of synthesis of the compression circuit when implemented on a FPGA and ASIC chip prototype

Στην εργασία, αυτή, εξετάζονται οι μέθοδοι συμπίεσης του συνόλου δοκιμής με τη χρήση πινάκων που έχουν ήδη προταθεί και προτείνεται μία νέα μέθοδος συμπίεσης δεδομένων δοκιμής για πυρήνες που ο έλεγχος ορθής λειτουργίας υλοποιείται μέσω μονοπατιών ολίσθησης. Η νέα μέθοδος επαναχρησιμοποιεί μπλοκ του πίνακα για τη σύνθεση διανυσμάτων δοκιμής. Δύο νέοι αλγόριθμοι παρουσιάζονται για επιλεκτική και πλήρη καταχώρηση τμημάτων του συνόλου δοκιμής σε πίνακα. Η προτεινόμενη μέθοδος συγκρίνεται με τις υπάρχουσες μεθόδους ως προς το ποσοστό συμπίεσης αλλά και ως προς το κόστος υλοποίησης. Για την αξιολόγηση της μεθόδου λαμβάνονται υπόψη σύνολα δοκιμής που έχουν παραχθεί για την ανίχνευση απλών σφαλμάτων μόνιμης τιμής, απλών σφαλμάτων μόνιμης τιμής με πολλαπλότητα ανίχνευσης Ν (Ν-detect) και σφαλμάτων καθυστέρησης μετάβασης. / In this work we refer to dictionary based test data compression methods. At first the already known dictionary based test data compression methods are comparably presented. Then we propose a new method and we show that the test data compression achieved by a dictionary based method can be improved significantly by suitably reusing parts of the dictionary entries. To this end two new algorithms are proposed, suitable for partial and complete dictionary coding respectively. For the evaluation of the proposed method, test sets have been generated and used based on the stuck-at fault model for single and N detection of each fault as well as on the transition fault model.