Ο όρος μορφοκλασματικό σύνολο παρουσιάστηκε για πρώτη φορά από τον Barnsley, το 1975. Ουσιαστικά ονόμασε έτσι το όριο μιας επαναληπτικής διαδικασίας, όταν ο αριθμός των επαναλήψεων τείνει στο άπειρο. Μέσα από τη μηχανή πολλαπλών αντιγράφων ορίζουμε το μορφοκλασματικό σύνολο και τις ιδιότητές του. Τα μορφοκλασματικά σύνολα έχουν εφαρμογές σε πολλά επιστημονικά πεδία, αλλά η κυριότερη είναι ως μέσο στη συμπίεση εικόνων. Ξεκινώντας από τη συμπίεση εικόνων οδηγούμαστε στον ορισμό του επαναληπτικού συστήματος συναρτήσεων και την ανάλυση της θεωρίας του, μέσω των οποίων επιτυγχάνουμε συμπίεση εικόνων. Η ανάγκη για εξοικονόμηση μνήμης, λόγω του μεγάλου όγκου δεδομένων, έκανε τον Barnsley να σκεφτεί αντί να αποθηκεύουμε ολόκληρη την εικόνα να αποθηκεύουμε μόνο το κατάλληλο επαναληπτικό σύστημα συναρτήσεων. Η διαδικασία της συμπίεσης εικόνων με μορφοκλασματικά σύνολα συντίθεται από δύο φάσεις. Την κωδικοποίηση και την αποκωδικοποίηση. Στην πρώτη φάση, προσπαθούμε να λύσουμε ένα αντίστροφο πρόβλημα και συγκεκριμένα να βρούμε το κατάλληλο επαναληπτικό σύστημα συναρτήσεων που αν το εφαρμόσουμε σε μια αρχική εικόνα θα συγκλίνουμε στον ελκυστή. Στη δεύετρη φάση, τη φάση της αποκωδικοποίησης, με χρήση του επαναληπτικού συστήματος συναρτήσεων, προσεγγίζουμε τον ελκυστή μετά από έναν πεπερασμένο αριθμό επαναλήψεων.Η υλοποίηση αυτών των φάσεων καθώς και οι δυνατοί τρόποι μείωσης της πολυπλοκότητας που απαιτείται κατά τη φάση της κωδικοποίησης είναι και το αντικείμενο της παρούσας εργασίας, στα πλαίσια της οποίας παρουσιάζονται και υλοποιούνται παραλλαγές γνωστών τεχνικών οι οποίες παρουσιάζουν βελτίωση στο PSNR, το λόγο συμπίεσης και το χρόνο κωδικοποίησης. Τέλος, προτείνεται μια νέα τεχνική για τον προσδιορισμό του κατάλληλου επαναληπτικού συστήματος συναρτήσεων κατά τη φάση της κωδικοποίησης, η οποία βασίζεται στην ελαχιστοποίηση μιας μη γραμμικής συνάρτησης κόστους. Αποτιμάται η απόδοσή της και συγκρίνεται με αυτή άλλων γνωστών τεχνικών κωδικοποίησης. / The term ‘fractal’ was first introduced by B. Mandelbrot, in 1975. It denotes the limit of an iterative process, when the number of iterations is infinite. Through the multiple photocopy machine, we define fractal and its properties. Fractals have many applications, one of which is in image compression. This is the object of the present research. Starting with data compression, we aim at the definition of an iterative function system and the IFS theory, through which we can achieve image compression. The need of massive storage in memory made Barnsley think that instead of storing the whole image in memory we can store only the suitable IFS. The process consists of two phases. The encoding and decoding. In encoding we try to solve the inverse problem, i.e. finding the best IFS that when we apply it to a starting image we will get the attractor. In the second phase, after a number of iterations we approximate the attractor. Several fractal image compression methods that already exist, together with their techniques and variations are presented and implemented in this research, in order to achieve improvements in PSNR, compression ratio and encoding time. A new method for fractal image compression on grayscale images is proposed at the end of this research, based on the minimization of a cost function. The experimental as well as the comparative results are shown.

Στη διπλωματική αυτή εργασία ορίζουμε δυο νέα μοντέλα τυχαίων γραφημάτων τομής ετικετών και εξετάζονται ως προς ορισμένες σημαντικές γραφοθεωρητικές ιδιότητές τους. Ένα τυχαίο γράφημα τομής ετικετών παράγεται αντιστοιχώντας σε κάθε κορυφή ένα \\\\emph{τυχαίο} υποσύνολο ενός πεπερασμένου) σύμπαντος $M$ από $m$ στοιχεία και βάζοντας μια ακμή μεταξύ δυο κορυφών αν και μόνον εάν τα αντίστοιχα σύνολά τους έχουν μη κενή τομή. Συγκεκριμενοποιώντας την κατανομή που ακολουθεί το τυχαίο υποσύνολο που αντιστοιχείται σε κάθε κορυφή παίρνουμε διαφορετικά μοντέλα τυχαίων γραφημάτων τομής. Στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής κάθε στοιχείο $i$ του $M$ επιλέγεται ανεξάρτητα από κάθε κορυφή με πιθανότητα $p_i$. Το ομοιόμορφο μοντέλο τυχαίων γραφημάτων τομής ετικετών αποτελεί μια ειδική περίπτωση του γενικευμένου μοντέλου όπου η πιθανότητα επιλογής των στοιχείων του $M$ είναι ίση με $p$, δηλαδή ίδια για όλα τα στοιχεία του $M$. Όπως θα δούμε, για ορισμένες τιμές των παραμέτρων $m$ και $p$, το ομοιόμορφο μοντέλο είναι ισοδύναμο με το μοντέλο $G_{n, \\\\hat{p}}$, δηλαδή με το μοντέλο τυχαίων γραφημάτων στο οποίο κάθε πλευρά εμφανίζεται στοχαστικά ανεξάρτητα με πιθανότητα $\\\\hat{p}$. Τέλος, στο κανονικό μοντέλο τυχαίων γραφημάτων τομής ετικετών το υποσύνολο του $M$ που αντιστοιχείται σε κάθε κορυφή έχει σταθερό αριθμό στοιχείων. Λόγω της στοχαστικής εξάρτησης που υποννοείται για την ύπαρξη πλευρών, τα γραφήματα αυτά θεωρούνται αρκετά ρεαλιστικά μοντέλα (σε σχέση με τα κλασσικά τυχαία γραφήματα) σε πολλές πρακτικές εφαρμογές, ιδιαίτερα σε αλγοριθμικά θέματα δικτύων. Στην εργασία αυτή αρχικά παρουσιάζουμε μερικά χαρακτηριστικά αποτελέσματα από τη σχετική βιβλιογραφία για τα μοντέλα αυτά. Ακόμα, μελετάμε, για πρώτη φορά στη βιβλιογραφία, την ύπαρξη ανεξάρτητων συνόλων κορυφών μεγέθους $k$ στο γενικευμένο μοντέλο τυχαίων γραφημάτων τομής ετικετών, υπολογίζοντας τη μέση τιμή και τη διασπορά του αριθμού τους. Επίσης, προτείνουμε και αναλύουμε τρείς πιθανοτικούς αλγόριθμους που τρέχουν σε μικρό πολυωνυμικό χρόνο (ως προς τον αριθμό των κορυφών και τον αριθμό των στοιχείων του $M$) για την εύρεση αρκετά μεγάλων συνόλων ανεξάρτητων κορυφών. / In this Master thesis we define and analyse two new models of random intersection graphs. A random intersection graph is produced by assigning to each vertex a random subset of a (finite) universe $M$ of $m$ elements and by drawing an edge between two vertices if and only if their corresponding subsets have some elements in common. By specifying the distribution of the subsets assigned to each vertex, we get various models of random intersection graphs. In the generalized random intersection graphs model each element $i$ in $M$ is chosen independently with probability $p_i$. The uniform random intersection graphs model is a special case of the generalized model where the probability of selecting an element of $M$ is $p$, i.e. the same for every element. As we will see, for some range of values of the parameters $m$ and $p$, the uniform model is equivalent in some sense with the model $G_{n, \\\\hat{p}}$, i.e. the random graphs model in which each edge appears independently with probability $\\\\hat{p}$. Finally, in the regular random intersection graphs model, the subset of $M$ assigned to each vertex has a fixed number of elements. Due to the dependence implied in the appearance of edges, these models are considered to be more realistic (than classic random graphs) in many applications. This thesis begins by presenting several important results concearning these models. Also, we study for the first time the existence of independent sets of size $k$ in the generalized random intersection graphs model, and we give exact formulae for the mean and variance of their number. Additionally, we propose three randomized algorithms, that run in small polynomial time (with respect to the number of vertices and the number of elements of $M$), for finding large independent sets of vertices.

With commercial processor design tools, a designer can quickly design a C- programmable ASIP for a specific application domain. There are several such ASIPs available for both wireless (UWB baseband processing), encryption, and biomedical processing (particularly for ECG beat detection). In traditional CPUs and DSPs the impact of the instruction-set definition and the complexity of the instruction decoder can be substantial, especially in terms of power consumption. Fully orthogonal VLIW processors, do not incur the cost of an instruction decoder that severely. Instead the instruction word becomes very large, thereby shifting the (power-)cost to the program memory or instruction cache. For the purposes of this thesis a SIMD processor is developed and is compared to a soft-SIMD to observe its area, performance and energy efficiency for a bioimaging benchmark and how the processor description in the ASIP language nML, defines the generated HDL. This SIMD processor is turned into orthogonal and using iterative experiments it is investigated, what is the impact on power while manipulating the instruction-set architecture in combination with the program memory size. It is also investigated how instruction-set re-configuration can be exploited to improve power efficiency. Using this investigation guidelines for low-power ASIP design can be produced. / Με τη σύγχρονη τεχνολογία σχεδιασμού επεξεργαστών, ο σχεδιαστής μπορεί με ευκολία να σχεδιάσει ένα προγραμματιζόμενο Επεξεργαστή Συνόλου Εντολών Ειδικού Σκοπού (ASIP - Application-Specific Instruction-set Processor) για ένα συγκεκριμένο εύρος εφαρμογών. Υπάρχουν διάφοροι τέτοιοι επεξεργαστές διαθέσιμοι για ασύρματες εφαρμογές, κρυπτογράφηση και βιοϊατρικές εφαρμογές (π.χ. στον αλγόριθμο εντοπισμού χτύπου ηλεκτροκαρδιογραφήματος). Στους παραδοσιακούς επεξεργαστές και επεξεργαστές σήματος (DSP - Digital Signal Processor) ο ορισμός του συνόλου εντολών και η πολυπλοκότητα έχουν μεγάλη επίδραση, ειδικά στην κατανάλωση ισχύος. Μία πιθανή λύση σε αυτό το πρόβλημα είναι οι ορθογώνιοι επεξεργαστές μεγάλου μεγέθους λέξης εντολής (VLIW - Very Large Instruction Word). Με τον όρο ορθογώνιο επεξεργαστή, ορίζεται ένας επεξεργαστής οριζόντιου σύνολου εντολών, άρα ένας επεξεργαστής στον οποίο μπορεί να υπάρξει κάθε διαθέσιμος συνδυασμός μεταξύ των διαθέσιμων εντολών και των μεθόδων διευθυνσιοδότησης για πρόσβαση στη μνήμη και το αρχείο καταχωρητών. Οι ορθογώνιοι επεξεργαστές δεν επιβαρύνουν τόσο τον αποκωδικοποιητή εντολών. Αντί αυτού το μέγεθος της λέξης της εντολής γίνεται πολύ μεγάλο, και έτσι μετατίθεται το ενεργειακό κόστος στην μνήμη εντολών προγράμματος (program memory )ή την κρυφή μνήμη εντολών προγράμματος (instruction cache). Για τους σκοπούς αυτής της διπλωματικής εργασίας, αναπτύχθηκε ένας επεξεργαστής SIMD, ο οποίος συγκρίνεται με έναν soft-SIMD για να μελετηθούν η απαιτούμενη περιοχή στο ενσωματωμένο, επιδόσεις και κατανάλωση ενέργειας για μία βιοϊατρική εφαρμογή, καθώς και το πως η περιγραφή ενός επεξεργαστή στη γλώσσα περιγραφής επεξεργαστών ASIP nML ορίζει την παραγούμενη γλώσσα περιγραφής υλικού (HDL - Hardware Description Language). Ο επεξεργαστής αυτός μετατρέπεται σε ορθογώνιο, και με τη χρήση επαναληπτικών πειραμάτων μελετάται η επίδραση στην κατανάλωση ενέργειας κατά τη διάρκεια αλλαγών στην αρχιτεκτονική του συνόλου εντολών και του μεγέθους της μνήμης εντολών προγράμματος. Ακόμη μελετάται πως μπορεί να εκμεταλλευτεί ο σχεδιαστής την αναδιάρθρωση του συνόλου εντολών για να βελτιώσει την κατανάλωση ενέργειας.