Over the past few decades, the demand for digital information has increased drastically. This enormous demand poses serious difficulties on the storage and transmission bandwidth of the current technologies. One possible solution to overcome this approach is to compress the amount of information by discarding all the redundancies. In multimedia technology, various lossy compression techniques are used to compress the raw image data to facilitate storage and to fit the transmission bandwidth. In this thesis, we propose a new approach using algebraic integers to reduce the complexity of the Daubechies-4 (D4) and Daubechies-6 (D6) Lifting based Discrete Wavelet Transforms. The resulting architecture is completely integer based, which is free from the round-off error that is caused in floating point calculations. The filter coefficients of the two transforms of Daubechies family are individually converted to integers by multiplying it with value of 2x, where, x is a random value selected at a point where the quantity of losses is negligible. The wavelet coefficients are then quantized using the proposed iterative individual-subband coding algorithm. The proposed coding algorithm is adopted from the well-known Embedded Zerotree Wavelet (EZW) coding. The results obtained from simulation shows that the proposed coding algorithm proves to be much faster than its predecessor, and at the same time, produces good Peak Signal to Noise Ratio (PSNR) at very low bit rates. Finally, the two proposed transform architectures are implemented on Virtex-E Field Programmable Gate Array (FPGA) to test the hardware cost (in terms of multipliers, adders and registers) and throughput rate. From the synthesis results, we see that the proposed algorithm has low hardware cost and a high throughput rate.

Στόχος της παρούσας διπλωματικής εργασίας είναι η μελέτη του σχήματος ανόρθωσης (lifting) που πρότεινε ο Sweldens για την αναπαράσταση διακριτών μετασχηματισμών κυματιδίων και ειδικότερα η παρουσίαση του μαθηματικού υπόβαθρου της μεθόδου που χρησιμοποιεί γινόμενα πινάκων με συντελεστές πολυώνυμα Laurent. Ο μετασχηματισμός κυματιδίου προσφέρει μια διαφορετική προσέγγιση στο πρόβλημα της αποδόμησης ενός διακριτού σήματος στο επίπεδο χρόνου-συχνότητας, καθώς είναι βασισμένος στην πολυεπίπεδη τεχνική πολλαπλής ανάλυσης σήματος, γι’ αυτό και αποτελεί ένα ιδιαίτερα εύχρηστο και εύκολα προσαρμόσιμο εργαλείο σε πολλές εφαρμογές. Παρουσιάζουμε ένα παράδειγμα ενός διακριτού σήματος στο οποίο εφαρμόζουμε τεχνικές πρόβλεψης και διόρθωσης των συστατικών του, κάνοντας μια πολυεπίπεδη ανάλυση που ονομάζεται ανάλυση πολλαπλής ευκρίνειας. Στα διάφορα στάδια αυτής της ανάλυσης ακολουθείται η μέθοδος ανόρθωσης (lifting) που αποτελείται από μια σειρά βημάτων πρόβλεψης και διόρθωσης των συστατικών του διακριτού σήματος. Με τη χρήση αυτής της μεθόδου μπορούμε να αναλύσουμε όλους τους μετασχηματισμούς κυματιδίων τους οποίους χρησιμοποιούμε για να αποδομήσουμε ένα διακριτό σήμα στα συστατικά του. Για την εφαρμογή του σχήματος ανόρθωσης χωρίζουμε το διακριτό σήμα στα άρτια και περιττά μέρη του και στη συνέχεια εφαρμόζουμε διαδοχικούς μετασχηματισμούς πρόβλεψης και διόρθωσης για τα δύο αυτά μέρη του σήματος. Στη συνέχεια αναπαριστούμε την παραπάνω ανάλυση μέσω του z-μετασχηματισμού με χρήση πολυωνύμων Laurent. Ο μετασχηματισμός ανάλυσης κυματιδίου, στον z-μετασχηματισμό, μετατρέπεται σε πολλαπλασιασμό πινάκων με στοιχεία πολυώνυμα Laurent. Η εφαρμογή των βημάτων της μεθόδου ανόρθωσης, ουσιαστικά, οδηγεί σε μια σταδιακή απλοποίηση των παραπάνω πολυωνύμων, η οποία γίνεται με τη χρήση του αλγορίθμου διαίρεσης πολυωνύμων. Παρουσιάζουμε και αναλύουμε τα θεωρήματα στα οποία στηρίζεται η μέθοδος και δίνουμε συγκεκριμένα παραδείγματα. / -

Ο κυματιδικός μετασχηματισμός αποτελεί το πλέον σύγχρονο μαθηματικό εργαλείο για την ανάλυση σήματος σε βάση συναρτήσεων. Σε σχέση με άλλες παρόμοιες τεχνικές (π.χ. Fourier) παρουσιάζει εμφανή πλεονεκτήματα με κυρίοτερο την τοπικότητα στο χρόνο των συναρτήσεων βάσης. Η δύναμη του κυματιδιακού μετασχηματισμού βρίσκεται στη διακριτή του έκδοση (Discrete Wavelet Transform), που υπολογίζεται με τη βοήθεια διατάξεων FIR φίλτρων ακολουθούμενων από υποδειγματοληψία. Η ταχύτερη και πιο σύγχρονη τεχνική υπολογισμού του DWT ονομάζεται σχήμα lifting και βασίζεται στην παραγοντοποίηση των πινάκων μετασχηματισμού σε γινόμενο αραιών πινάκων. Στο πλαίσιο της εργασίας σχεδιάστηκε και υλοποιήθηκε σε γλώσσα VHDL μία VLSI αρχιτεκτονική ικανή να εκτελεί οποiοδήποτε φίλτρο (ευθύ και αντίστροφο) του DWT τροποποιημένο με τη μέθοδο lifting. Τα φίλτρα είναι αποθηκευμένα σαν μικροπρογράμματα σε μνήμη ελέγχου για ευκολία στη σχεδίαση και δυνατότητα επαναπροσδιορισμού του συστήματος. Το σύστημα εξομοιώθηκε για ορθή λειτουργία κατά την εκτέλεση των φίλτρων του προτύπου JPEG2000, ενώ έγινε και σύνθεση σε FPGA. / The wavelet transform is the most powerful mathematical tool for analysing signals into function bases. Comparing with other such technics (e.g. Fourier transform), wavelets show obvious advantages, with the most important being the spatial locality of the basis functions. The real power of wavelet transform is the Discrete Wavelet Tranfsorm (DWT), which is a filtering operation followed by downsampling. Recently, a new, fast approach for calculating these filter banks has been developed, named the lifting scheme. This method is based on the factorization of the transform matrices into a product of some sparse matrices. Α VLSI architecture that executes wavelet filters (forward and inverse) modified by the lifting scheme is designed and implemented in VHDL code. The filters are considered as microprogramms placed in the system

This diploma thesis deals with digital image lossy compression. Lossy compression in general inserts some kind of distorsion to the resulting image. The distorsion should not be interupting or even noticable in the better case. For image analysis there is used process called transformation and for choosing relevant coefficients process called coding. Evaluation of image quallity can be done by objective or subjective method. There is encoder introduced and realized in this work. Encoder utilizes two-dimension wavelet transform and SPIHT algortihm for coefficient coding. It was made use of accelerated method of wavelet transform computation by lifting scheme. Coder can proccess color information of images using modificated original SPIHT algorithm. For implementation the JAVA programming language was employed. The object-oriented design principes was made use of and thus the program is easy to extended. At demonstaration pictures there are shown effectiveness and characteristic way of distorsion of the proposed coder at high compression rates.

Le tatouage d’images (ou watermarking) consiste à insérer de l’information de copyright, ou d’autres messages de vérification, invisible à l’oeil humain. Parmi toutes les approches possibles, le tatouage psychovisuel est le plus performant. Il consiste à utiliser les connaissances du Système Visuel Humain (SVH) pour en déduire la force du tatouage de manière optimale. Dans cette étude, nous avons proposé une nouvelle méthode de tatouage d'image psychovisuel qui combine les avantages des ondelettes à celle du domaine spatial par l’utilisation d'une représentation en ondelettes à échelle mixée (JNDEM). En considérant la densité des coefficients d'ondelettes dominants, notre système est capable de différencier les zones uniformes, celles incluant des contours, et enfin celles texturées. Nous avons sélectionné les méthodes efficaces de tatouage psychovisuel adaptée à chaque zone, à savoir celle de Chou pour les zones uniformes, de nouveau celle de Chou pour les contours, et finalement celle de Qi pour les textures. Nous avons aussi pris en compte la sensibilité du SVH qui varie avec l’orientation locale de l’image. Nous avons comparé notre JNDEM à quatre autres méthodes de tatouage de la littérature en termes de qualité visuelle et de robustesse. La méthode JNDEM conduit à une grande qualité visuelle mesurée par des tests objectifs et subjectifs. De plus elle est robuste aux attaques. Ce dernier point est d'une grande importance pour les applications réelles. En conclusion, la méthode proposée est le meilleur compromis entre la qualité visuelle et la résistance aux attaques comparée aux quatre autres méthodes testées. / Watermarking consists in inserting copyright information, or other verification messages, invisible to the human eye. Among all the possible approaches, perceptual watermarking is the most efficient. Perceptual image watermarking consists in using knowledge of the Human Visual System (HVS) to choose the strength of the watermark. In this study, we propose a new perceptual image watermarking method (JNDEM ) that combines the advantages of both the wavelet domain and the spatial domain since a mixed-scale wavelet representation is applied. By considering the density of the dominant wavelet coefficients, our scheme is able to differentiate uniform, edge and texture areas. We selected effective Just Noticeable Difference (JND) models from the literature, i.e. luminance and edge masking developed by Chou, and texture masking developed by Qi. We also took into account the HVS sensitivity which varies with the orientation of the image activity. We have compared our JNDEM to four other JND models from the literature in terms of visual quality and of robustness to attacks. Results show that the proposed method yields a high visual quality and is very robust against attacks. This last point is of great importance for real applications. In conclusion, the proposed method is the best trade-off between visual quality and resistance to attacks among the four other tested methods.

Les travaux développés dans cette thèse portent sur les décompositions multirésolution dans un cadre de lifting scheme, appliquées à la compression d'images. Pour commencer, une structure de décomposition consistant en un “lifting scheme généralisé” est proposée. Ce schéma permet d'exploiter toute l'information disponible au décodage dans l'étape de prédiction. Cela est rendu possible par l'ajout d'un filtre de prédiction supplémentaire par rapport à la structure classique de lifting scheme. Le schéma proposé est ensuite associé à deux méthodes d'adaptation. La première, appelée GAE, suppose une stationnarité globale de l'image, tandis que la seconde, LAE ne suppose qu'une stationnarité locale de l'image. Dans ce dernier cas, les filtres prédicteurs sont adaptatifs. Trois applications de ces méthodes en compression d'images sont ensuite proposées. Dans un premier temps, une comparaison des performances en compression sans perte sur des images de textures, synthétiques, gaussiennes, à stationnarités locale et globale (vérifiant les hypothèses plus haut), est réalisée. Sur ces signaux, les mesures d'entropie d'ordre 1 ont montré que les méthodes proposées offrent en moyenne un gain en codage de 0,5 bpp (GAE) et 0,8 bpp (LAE) par rapport à la décomposition en ondelette (9,7), de 0,8 bpp (GAE) et 1,11 bpp (LAE) par rapport à la (5,3) et de 0,41 bpp (GAE) et 0,65 bpp (LAE) par rapport à la méthode de Gerek et Çetin. La deuxième application concerne le codage sans perte d'images réelles de natures variées. Les gains par rapport à l'état de l'art se sont révélés plus faibles que ceux obtenus pour les images synthétiques. Enfin, la dernière application traite les cas du codage progressif et du codage avec perte. Pour la compression avec pertes, nous avons modifié la méthode LAE pour palier aux problèmes de divergence dus à l'impossibilité au niveau du décodeur de reconstruire les filtres prédicteurs à partir d'échantillons quantifiés. Elle se révèle plus efficace que lorsque l'on utilise les filtres usuels de longueur fixe (9,7) et (5,3).

Dizertační práce se zabývá algoritmy SegDWT pro segmentový výpočet Diskrétní Waveletové Transformace – DWT jedno i vícedimenzionálních dat. Segmentovým výpočtem se rozumí způsob výpočtu waveletové analýzy a syntézy po nezávislých segmentech (blocích) s určitým překryvem tak, že nevznikají blokové artefakty. Analyzující část algoritmu pracuje na principu odstranění přesahu a produkuje vždy část waveletových koeficientů z waveletové transformace celého signálu, které mohou být následně libovolně zpracovány a podrobeny zpětné transformaci. Rekonstruované segmenty jsou pak skládány podle principu přičtení přesahu. Algoritmus SegDWT, ze kterého tato práce vychází, není v současné podobně přímo použitelný pro vícerozměrné signály. Tato práce obsahuje několik jeho modifikací a následné zobecnění pro vícerozměrné signály pomocí principu separability. Kromě toho je v práci představen algoritmus SegLWT, který myšlenku SegDWT přenáší na výpočet waveletové transformace pomocí nekauzálních struktur filtrů typu lifting.

Práce se zaměřuje na efektivní výpočet dvourozměrné diskrétní vlnkové transformace. Současné metody jsou v práci rozšířeny v několika směrech a to tak, aby spočetly tuto transformaci v jediném průchodu, a to případně víceúrovňově, použitím kompaktního jádra. Tohle jádro dále může být vhodně přeorganizováno za účelem minimalizace užití některých prostředků. Představený přístup krásně zapadá do běžně používaných rozšíření SIMD, využívá hierarchii cache pamětí moderních procesorů a je vhodný k paralelnímu výpočtu. Prezentovaný přístup je nakonec začleněn do kompresního řetězce formátu JPEG 2000, ve kterém se ukázal být zásadně rychlejší než široce používané implementace.

Dans ce travail, nous proposons de suivre une approche multi-échelles pour simuler des propriétés spatiales des réservoirs, permettant d'intégrer des données directes (observation de puits) ou indirectes (sismique et données de production) de résolutions différentes. Deux paramétrisations sont utilisées pour résoudre ce problème: les ondelettes et les pyramides gaussiennes. A l'aide de ces paramétrisations, nous démontrons les avantages de l'approche multi-échelles sur deux types de problèmes d'estimations des incertitudes basés sur la minimisation d'une distance. Le premier problème traite de la simulation de propriétés à partir d'un algorithme de géostatistique multipoints. Il est montré que l'approche multi-échelles basée sur les pyramides gaussiennes améliore la qualité des réalisations générées, respecte davantage les données et réduit les temps de calculs par rapport à l'approche standard. Le second problème traite de la préservation des modèles a priori lors de l'assimilation des données d'historique de production. Pour re-paramétriser le problème, nous développons une transformée en ondelette 3D applicable à des grilles stratigraphiques complexes de réservoir, possédant des cellules mortes ou de volume négligeable. Afin d'estimer les incertitudes liées à l'aspect mal posé du problème inverse, une méthode d'optimisation basée ensemble est intégrée dans l'approche multi-échelles de calage historique. A l'aide de plusieurs exemples d'applications, nous montrons que l'inversion multi-échelles permet de mieux préserver les modèles a priori et est moins assujettie au bruit que les approches standards, tout en respectant aussi bien les données de conditionnement. / In this work, we propose to follow a multi-scale approach for spatial reservoir properties characterization using direct (well observations) and indirect (seismic and production history) data at different resolutions. Two decompositions are used to parameterize the problem: the wavelets and the Gaussian pyramids. Using these parameterizations, we show the advantages of the multi-scale approach with two uncertainty quantification problems based on minimization. The first one concerns the simulation of property fields from a multiple points geostatistics algorithm. It is shown that the multi-scale approach based on Gaussian pyramids improves the quality of the output realizations, the match of the conditioning data and the computational time compared to the standard approach. The second problem concerns the preservation of the prior models during the assimilation of the production history. In order to re-parameterize the problem, we develop a new 3D grid adaptive wavelet transform, which can be used on complex reservoir grids containing dead or zero volume cells. An ensemble-based optimization method is integrated in the multi-scale history matching approach, so that an estimation of the uncertainty is obtained at the end of the optimization. This method is applied on several application examples where we observe that the final realizations better preserve the spatial distribution of the prior models and are less noisy than the realizations updated using a standard approach, while matching the production data equally well.

Image compression is of great importance in multimedia systems and applications because it drastically reduces bandwidth requirements for transmission and memory requirements for storage. Although earlier standards for image compression were based on the Discrete Cosine Transform (DCT), a recently developed mathematical technique, called Discrete Wavelet Transform (DWT), has been found to be more efficient for image coding. Despite improvements in compression efficiency, wavelet image coders significantly increase memory usage and complexity when compared with DCT-based coders. A major reason for the high memory requirements is that the usual algorithm to compute the wavelet transform requires the entire image to be in memory. Although some proposals reduce the memory usage, they present problems that hinder their implementation. In addition, some wavelet image coders, like SPIHT (which has become a benchmark for wavelet coding), always need to hold the entire image in memory. Regarding the complexity of the coders, SPIHT can be considered quite complex because it performs bit-plane coding with multiple image scans. The wavelet-based JPEG 2000 standard is still more complex because it improves coding efficiency through time-consuming methods, such as an iterative optimization algorithm based on the Lagrange multiplier method, and high-order context modeling. In this thesis, we aim to reduce memory usage and complexity in wavelet-based image coding, while preserving compression efficiency. To this end, a run-length encoder and a tree-based wavelet encoder are proposed. In addition, a new algorithm to efficiently compute the wavelet transform is presented. This algorithm achieves low memory consumption using line-by-line processing, and it employs recursion to automatically place the order in which the wavelet transform is computed, solving some synchronization problems that have not been tackled by previous proposals. The proposed encode / Oliver Gil, JS. (2006). On the design of fast and efficient wavelet image coders with reduced memory usage [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1826