During the past two decades, techniques and devices were developed to transmit and receive signals with a phased array instead of a single coil in the MRI (Magnetic Resonance Imaging) system. The two techniques to simultaneously transmit and receive RF signals using phased arrays are called parallel excitation (pTx) and parallel imaging (PI), respectively. These two techniques lead to shorter transmit pulses for higher imaging quality and faster data acquisition correspondingly. This dissertation focuses on improving the efficiency of the pTx pulse design and the PI reconstruction in MRI. Both PI and pTx benefit from the increased number of elements of the array. However, efficiency concerns may arise which include: (1) In PI, the computation cost of the reconstructions and the achievable acceleration factors and (2) in pTx, the pulse design speed and memory cost. The work presented in this dissertation addresses these issues. First, a correlation based channel reduction algorithm is developed to reduce the computation cost of PI reconstruction. In conventional k-domain methods, the individual channel data is reconstructed via linear interpolation of the neighbourhood data from all channels. In this proposed algorithm, we choose only a subset of the channels based on the spatial correlation. The results have shown that the computation cost can be significantly reduced with similar or higher reconstruction accuracy. Then, a new parallel imaging method named parallel imaging using localized receive arrays with Sinc interpolation(PILARS) is proposed to improve the actual acceleration factor and to reduce the computation cost. It employs the local support of individual coils and pre-determines the magnitude of the reconstruction coefficients. Thus, it requires much less auto-calibration signals (ACS) data and achieves higher acceleration factors. The results show that this method can increase the acceleration factor and the reconstruction speed while achieving the same level of reconstruction quality. Finally, a fast pTx pulse design method is proposed to accelerate the design speed. This method is based on the spatial domain pulse design method and can be used to accelerate similar methods. We substitute the two computational expensive matrix- vector multiplications in the conjugate gradient (CG) solver with gridding and fast Fourier transform (FFT). Theoretical and simulation results have shown that the design speed can be improved by 10 times. Meanwhile, the memory cost is reduced by 103 times. This breaks the memory burden of implementing pulse designs on GPU which enables further accelerations.

<p>We show topological priors play an important role in solving the inverse problem of shape reconstruction. We classify the applications into 1D, 2D, and 3D cases:</p><p>In 1D, we show that the persistent extrema of the curvature function of a closed curve are useful for shape simplication. In 2D, we study how to label a scene into multiple tiers to approximate the actual scene layout. We use the number of extrema as a topological prior to bound the complexity of the shape of tiers and study 2D labeling under symmetry shape priors. In 3D, we recover the detailed 3D root shape using multiple 2D images. Three novel ideas are presented. First, we propose the use of harmonic images for background subtraction. Second, we develop the regularized visual hull to preserve the details of an example image in reconstruction. Third, we enforce the topological connectedness by an ecient algorithm that is inspired by the recent development of persistent homology.</p><p>Computational efficiency is emphasized throughout the thesis. We show that 1D topological persistence can be computed in O(n) time on a closed curve of n nodes. For 2D tiered labeling, we give an approximation algorithm to compute it in O(nK) time for K tiers on an image of n pixels. For 3D root reconstruction, we accelerate the computation using oct-trees and minimal spanning trees. With these ingredients, it takes only a few seconds to reconstruct a detailed root shape from 40 images of resolution 1600*1200 on a laptop.</p> / Dissertation

Master of Science / Department of Computing and Information Sciences / Gurdip Singh / Severe energy constraints and limited computing abilities of the nodes in a network present a major challenge in the design and deployment of a wireless sensor network. This thesis aims to present energy efficient algorithms for data fusion and information aggregation in a sensor network. The various methodologies of data fusion presented in this thesis intend to reduce the data traffic within a network by mapping the sensor network application task graph onto a sensor network topology. Partitioning of an application into sub-tasks that can be mapped onto the nodes of a sensor network offers opportunities to reduce the overall energy consumption of a sensor network. The first approach proposes a grid based coordinated incremental data fusion and routing with heterogeneous nodes of varied computational abilities. In this approach high performance nodes arranged in a mesh like structure spanning the network topology, are present amongst the resource constrained nodes. The sensor network protocol performance, measured in terms of hop-count is analysed for various grid sizes of the high performance nodes. To reduce network traffic and increase the energy efficiency in a randomly deployed sensor network, distributed clustering strategies which consider network density and structure similarity are applied on the network topology. The clustering methods aim to improve the energy efficiency of the sensor network by dividing the network into logical clusters and mapping the fusion points onto the clusters. Routing of network information is performed by inter-cluster and intra-cluster routing.

<p>The past decade has seen wide availability of solid-state drives (SSDs) in settings ranging from personal computing to enterprise storage. Their success over the hard disks is driven by performance considerations and cost savings. Besides SSDs based on flash memory, there have been ongoing efforts in developing other non-volatile memory technologies such as phase-change memory and MRAM. All these technologies enable what we refer to as random-access block devices. Unlike hard disks, these devices have fast random accesses; on the other hand, their writes are more expensive than their reads. In this work, we study how to optimize database and storage algorithms for the I/O characteristics of random-access block devices. Specifically, we tackle the following three problems.</p><p>The first one is about permuting data out-of-core. While external merge sort is popular for implementing permutation on hard disks, it carries unnecessary overhead in storing and comparing keys. We propose more efficient algorithms for a useful class of permutations called Address-Digit Permutations on random-access block devices.</p><p>The second problem is concurrency control for indexes on SSDs. Various indexes have been proposed for these devices, but to make such indexes practical, we must address the issue of concurrency control. We propose a novel indexing and concurrency control scheme which allows concurrent accesses during ongoing index reorganizations, and does so with minimal memory and block-level locking.</p><p>The third problem concerns log-structured merge, a popular indexing technique well-suited to random-access block devices. We show how an intelligent partial merge policy, combined with a block-preserving merge procedure, can ­significantly lower write traffic while preserving other advantages of log-structured merge.</p> / Dissertation

Τα ασύρματα δίκτυα μικροαισθητήρων αποτελούνται από ένα πολύ μεγάλο πλήθος συσκευών που τοποθετούνται σε μία περιοχή ενδιαφέροντος και αυτοοργανώνονται σε ένα αδόμητο δίκτυο, προκειμένου να καταγράψουν/μετρήσουν/παρακολουθήσουν κάποια περιβαλλοντική μετρική ή φαινόμενο και εν συνεχεία να μεταφέρουν τα δεδομένα σε κάποιο κέντρο ελέγχου. Λόγω των πολύ περιορισμένων δυνατοτήτων των συσκευών, ειδικά όσον αφορά την εμβέλεια επικοινωνίας και τα αποθέματα ενέργειας, αλλά και λόγω του πλήθους τους, είναι απαραίτητη η ανάπτυξη νέων αλγορίθμων και πρωτοκόλλων σχεδιασμένων για τα ιδιαίτερα προβλήματα των δικτύων αισθητήρων. Στην παρούσα διατριβή παρουσιάζουμε έρευνα επικεντρωμένη στην ανάπτυξη, προσομοίωση και αξιολόγηση ενεργειακά αποδοτικών αλγορίθμων, δηλαδή βασικός στόχος είναι η ελαχιστοποίηση της κατανάλωσης ενέργειας. Παρά τη ραγδαία εξέλιξη της τεχνολογίας του υλικού το πρόβλημα βελτιστοποίησης της ενέργειας των συσκευών αισθητήρων παραμένει επίκαιρο αφού οι υπάρχουσες και άμεσα διαφαινόμενες λύσεις μέσω υλικού δεν έχουν δώσει ικανοποιητική απάντηση. Επικεντρώνουμε την έρευνά μας σε τρεις βασικές κατευθύνσεις που στοχεύουν στην εξοικονόμηση και βελτιστοποίηση της κατανάλωσης ενέργειας σε διαφορετικά επίπεδα. Κοινός στόχος είναι η μείωση του κόστους επικοινωνίας, μέσω της ανάδειξης καινοτόμων τεχνικών που δίνουν ώθηση στην ανάπτυξη νέων αλγορίθμων. Συγκεκριμένα, διερευνήσαμε τεχνικές κατανεμημένης προσαρμογής της λειτουργίας ενός πρωτοκόλλου όπου χρησιμοποιούμε πληροφορία διαθέσιμη τοπικά σε κάθε κόμβο ώστε με καθαρά τοπικές επιλογές, να βελτιώσουμε τη συνολική συμπε- ριφορά ενός πρωτοκόλλου. Επίσης προτείνουμε τεχνικές τοπικής συλλογής και εκμετάλλευσης περιορισμένης γνώσης των συνθηκών του δικτύου. Με ενεργειακά αποδοτικό τρόπο συλλέγουμε επιπλέον πληροφορία που χρησιμοποιούμε προκειμένου να επιτευχθούν βελτιστοποιήσεις όπως ο σχηματισμός ενεργειακά αποδοτικών, χαμηλής καθυστέρησης και ανθεκτικών σε σφάλματα μονοπατιών για μετάδοση δεδομένων. Ακόμα, διερευνούμε τεχνικές διαχείρισης της κινητικότητας σε περιπτώσεις δικτύων όπου χαρακτηριστικό είναι η κίνηση τόσο του κέντρου ελέγχου όσο και των συσκευών αισθητήρων. Εξετάσαμε μεθόδους διαπέρασης και κάλυψης του δικτύου από κινητά κέντρα ελέγχου που βασίζονται σε πιθανοτική κίνηση που ευνοεί την επίσκεψη κάποιων περιοχών με βάση τοπικά κριτήρια (συχνότητα προηγούμενων επισκέψεων, τοπική πυκνότητα δικτύου). Οι αλγόριθμοι που αναπτύσσουμε βασισμένοι σε αυτές τις τεχνικές λειτουργούν α) σε επίπεδο διαχείρισης της ίδιας της συσκευής, β) σε επίπεδο πρωτοκόλλου δρομολόγησης και γ) συνολικά σε επίπεδο δικτύου, αναδεικνύοντας μακροσκοπική συμπεριφορά από τοπικές αλληλεπιδράσεις. Οι αλγόριθμοι εφαρμόζονται σε περιπτώσεις δικτύων με διαφορές στην πυκνότητα, κατανομή κόμβων, διαθέσιμη ενέργεια αλλά και με ριζικές διαφοροποιήσεις στο μοντέλο αφού εξετάζουμε δίκτυα με παρουσία σφαλμάτων, σταδιακή ανάπτυξη κόμβων ακόμα και με κινούμενους κόμβους. Σε όλες αυτές τις περιπτώσεις οι τεχνικές μας πετυχαίνουν σημαντικά οφέλη γεγονός που αναδεικνύει την αξία τους σαν εργαλεία αλγοριθμικής σχεδίασης. / -

[pt] As redes de sensores sem fio se constituem numa área que outorga grandes oportunidades para a oferta de uma série de aplicações inovadoras e com baixo custo. Os dispositivos destas redes são bastantes pequenos e sua fonte de alimentação são baterias. O tempo de vida destas é limitado, limitando assim o tempo da vida dos sensores e da rede como um todo. Por esta razão nos últimos anos o tema de eficiência energética tem atraído grande interesse de pesquisadores. O aumento do custo da energia e do consumo global da energia pelo setor de ICT (Information and Communications Technologies) têm crescido vertiginosamente devido ao aumento continuo do número de clientes e da demanda por aplicações de maior complexidade. Por tudo isso têm sido desenvolvidos distintos métodos e técnicas para economizar energia nas RSSF. Neste trabalho se implementam dois algoritmos que levam em conta critérios para economizar os custos de energia da rede e através de experimentos de simulação se avalia os mesmos. Nos resultados pode se observar as vantagens de trabalhar com sistemas que visam a eficiência energética. / [en] The WSNs (Wireless Sensor Networks) belong to an area that gives rise to great opportunities to spread innovative and low cost applications. These kinds of networks are composed of tiny devices with limited energy. The main source of power supply for WSNs are batteries, which are limited in cycle life, thus limiting the sensors lifetime and the network as a whole. Due to that fact, the energy efficiency network is becoming the main concern to be addressed by researchers. Rising energy prices and global energy consumption by the ICT (Information and Communications Technologies) sector have grown dramatically due to the continuous increase in customer number and the demand for more complex applications. For the reasons outlined above, different energy-saving techniques for WSNs have been developed. Two energy-saving algorithms for WSNs were implemented in this thesis, and they were tested by experimental evaluation using simulation. The results obtained from the simulations showed the advantages of working with systems aiming at energy efficiency.

In der klassischen Komplexitätstheorie werden worst-case Laufzeiten von Algorithmen typischerweise einzig abhängig von der Eingabegröße angegeben. In dem Kontext der parametrisierten Komplexitätstheorie versucht man die Analyse der Laufzeit dahingehend zu verfeinern, dass man zusätzlich zu der Eingabengröße noch einen Parameter berücksichtigt, welcher angibt, wie strukturiert die Eingabe bezüglich einer gewissen Eigenschaft ist. Ein parametrisierter Algorithmus nutzt dann diese beschriebene Struktur aus und erreicht so eine Laufzeit, welche schneller ist als die eines besten unparametrisierten Algorithmus, falls der Parameter klein ist. Der erste Hauptteil dieser Arbeit führt die Forschung in diese Richtung weiter aus und untersucht den Einfluss von verschieden Parametern auf die Laufzeit von bekannten effizient lösbaren Problemen. Einige vorgestellte Algorithmen sind dabei adaptive Algorithmen, was bedeutet, dass die Laufzeit von diesen Algorithmen mit der Laufzeit des besten unparametrisierten Algorithm für den größtmöglichen Parameterwert übereinstimmt und damit theoretisch niemals schlechter als die besten unparametrisierten Algorithmen und übertreffen diese bereits für leicht nichttriviale Parameterwerte. Motiviert durch den allgemeinen Erfolg und der Vielzahl solcher parametrisierten Algorithmen, welche eine vielzahl verschiedener Strukturen ausnutzen, untersuchen wir im zweiten Hauptteil dieser Arbeit, wie man solche unterschiedliche homogene Strukturen zu mehr heterogenen Strukturen vereinen kann. Ausgehend von algebraischen Ausdrücken, welche benutzt werden können, um von Parametern beschriebene Strukturen zu definieren, charakterisieren wir klar und robust heterogene Strukturen und zeigen exemplarisch, wie sich die Parameter tree-depth und modular-width heterogen verbinden lassen. Wir beschreiben dazu effiziente Algorithmen auf heterogenen Strukturen mit Laufzeiten, welche im Spezialfall mit den homogenen Algorithmen übereinstimmen. / In classical complexity theory, the worst-case running times of algorithms depend solely on the size of the input. In parameterized complexity the goal is to refine the analysis of the running time of an algorithm by additionally considering a parameter that measures some kind of structure in the input. A parameterized algorithm then utilizes the structure described by the parameter and achieves a running time that is faster than the best general (unparameterized) algorithm for instances of low parameter value. In the first part of this thesis, we carry forward in this direction and investigate the influence of several parameters on the running times of well-known tractable problems. Several presented algorithms are adaptive algorithms, meaning that they match the running time of a best unparameterized algorithm for worst-case parameter values. Thus, an adaptive parameterized algorithm is asymptotically never worse than the best unparameterized algorithm, while it outperforms the best general algorithm already for slightly non-trivial parameter values. As illustrated in the first part of this thesis, for many problems there exist efficient parameterized algorithms regarding multiple parameters, each describing a different kind of structure. In the second part of this thesis, we explore how to combine such homogeneous structures to more general and heterogeneous structures. Using algebraic expressions, we define new combined graph classes of heterogeneous structure in a clean and robust way, and we showcase this for the heterogeneous merge of the parameters tree-depth and modular-width, by presenting parameterized algorithms on such heterogeneous graph classes and getting running times that match the homogeneous cases throughout.

Η αντιστοίχιση εικόνων έχει σαν σκοπό την εύρεση γεωμετρικών και άλλων διαφορών ανάμεσα σε δύο ή περισσότερες εικόνες. Η ψηφιακή υδατογράφηση εικόνων προσφέρει κατοχύρωση των πνευματικών δικαιωμάτων, εισάγοντας στις εικόνες ένα αδιόρατο σήμα, ένα υδατογράφημα, με τέτοιο τρόπο ώστε να είναι δύσκολο να αφαιρεθεί. Η αντιστοίχιση μπορεί να αποτελέσει τμήμα της ψηφιακής υδατογράφησης, στη φάση της ανίχνευσης του υδατογραφήματος. Επιπλέον, για την ανίχνευση του υδατογραφήματος χρησιμοποιούνται παρόμοιες ή και ίδιες μετρικές ομοιότητας με αυτές που χρησιμοποιούνται στην αντιστοίχιση. Έτσι, οποιαδήποτε βελτίωση αφορά την αντιστοίχιση ή τις μετρικές ομοιότητας μπορεί να έχει θετικές επιδράσεις και στην ψηφιακή υδατογράφηση. Η έρευνα που έγινε στα πλαίσια της διδακτορικής διατριβής σε σχέση με το πρόβλημα της αντιστοίχισης αφορά τη συσχέτιση των εικόνων στο χωρικό πεδίο, η οποία έχει το εξής μειονέκτημα: η περιοχή γύρω από τη μέγιστη τιμή της μπορεί να έχει μεγάλο εύρος και να επηρεάζει την ακρίβεια της αντιστοίχισης. Για την αντιμετώπιση αυτού του προβλήματος, προτείνεται μια διαδικασία προ-λεύκανσης των εικόνων, βασισμένη στο φίλτρο σφάλματος πρόβλεψης. Επίσης, αναπτύσσεται ένας επαναληπτικός αλγόριθμος αντιστοίχισης για μετατοπίσεις και περιστροφές, ο οποίος εφαρμόζεται σε ακολουθίες ιατρικών εικόνων με σκοπό τη διάγνωση δυσπλασιών και κακοηθειών. Ένα δεύτερο μειονέκτημα της χωρικής συσχέτισης είναι το μεγάλο υπολογιστικό της κόστος. Στη διδακτορική διατριβή προτείνεται ένα γρήγορο σχήμα υπολογισμού της, το οποίο βασίζεται σε κατάλληλη τμηματοποίηση της εικόνας και στη χρήση του μετασχηματισμού Fourier. Επίσης, το πιο απαιτητικό κομμάτι της διαδικασίας αντιστοίχισης είναι ο υπολογισμός της χρησιμοποιούμενης μετρικής σαν συνάρτηση της σχετικής θέσης των εικόνων. Έτσι, αναπτύσσεται ένας αποδοτικός επαναληπτικός αλγόριθμος, ο οποίος μειώνει σημαντικά τις αναζητήσεις που απαιτούνται για την εύρεση του μεγίστου του συντελεστή συσχέτισης και παρέχει ακρίβεια εικονοστοιχείου. Τέλος, προτείνεται μια τεχνική η οποία παρέχει ακρίβεια υποδιαίρεσης εικονοστοιχείου και βασίζεται στη μεγιστοποίηση του συντελεστή συσχέτισης. Η τεχνική αυτή δεν απαιτεί ανακατασκευή των τιμών της έντασης και παρέχει μια λύση κλειστού τύπου για την εκτίμηση της μετατόπισης. Όσο αφορά το πρόβλημα της υδατογράφησης, η έρευνα που έγινε στα πλαίσια της διδακτορικής διατριβής στοχεύει στην ένθεση ισχυρών υδατογραφημάτων στο χωρικό πεδίο και στη βελτίωση της ανίχνευσής τους. Καταρχήν, προτείνεται μια χωρική αντιληπτική μάσκα, η οποία βασίζεται στην τοπική διασπορά του σφάλματος πρόβλεψης της αρχικής εικόνας. Παράλληλα, αναπτύσσεται ένα «τυφλό» σύστημα ανίχνευσης και η βελτιωμένη απόδοσή του σε σχέση με υπάρχοντες ανιχνευτές αποδεικνύεται θεωρητικά για τη γενική περίπτωση επίθεσης με γραμμικό φίλτρο και θόρυβο. Στη συνέχεια, παράγεται μια νέα χωρική μάσκα η οποία επιτρέπει την ένθεση υδατογραφημάτων με εξαιρετικά μεγάλη ενέργεια, διατηρώντας ταυτόχρονα την ποιότητα της εικόνας σε πολύ καλό επίπεδο. Η απόδοσή της συγκρίνεται με πολύ γνωστές και ευρέως χρησιμοποιούμενες μάσκες και αποδεικνύεται σημαντικά καλύτερη. Επίσης, αναπτύσσεται ένα βελτιωμένο σχήμα ανίχνευσης, το οποίο σε συνδυασμό με την προτεινόμενη μάσκα έχει πολύ καλή απόδοση. Τέλος, προτείνεται μια μέθοδος εισαγωγής υδατογραφήματος στην εικόνα με πολλαπλασιαστικό τρόπο, χρησιμοποιώντας χωρο-χρονική κωδικοποίηση μπλοκ και ειδικότερα μια 4x4 πραγματική, ορθογώνια διάταξη συμβόλων. Το σχήμα αυτό αποδεικνύεται να έχει πολύ καλύτερη απόδοση σε σχέση με την επαναληπτική υδατογράφηση. / Image registration aims at finding geometrical or other differences between two or more images. Image watermarking offers copyright protection by embedding in the images an invisible signal, a watermark, in such a way that it is difficult to be removed. Image registration can be part of a watermark detector. Moreover, similar (or the same) similarity measures are used for both image registration and watermark detection. Thus, any improvement concerning the image registration or the similarity measures can have positive effects on image watermarking, too. Our research concerning the image registration problem deals with the spatial cross-correlation, which has the following drawback: the region around its maximum value can be rather wide, affecting the registration accuracy. This problem can be solved, by properly pre-whitening the images with the prediction error filter. Furthermore, an iterative algorithm is proposed for registering images with translation and rotation differences, which is then applied in sequences of medical images for cancer diagnosis. A second disadvantage of the spatial correlation is its computational cost. A fast computation scheme is proposed, based on a proper partitioning of the images and the Fourier transform. Also, the most computationally intensive part of a registration process is the evaluation of the involved measure for different relative image positions. Thus, an efficient iterative algorithm is developed that considerably reduces the number of searches required for finding the correlation coefficient maximum value and provides pixel accuracy. Finally, an image registration technique with subpixel accuracy is proposed, which is based on the correlation coefficient maximization. This technique does not require the reconstruction of the intensity values and provides a closed form solution to the subpixel translation estimation problem. As far as the problem of image watermarking is concerned, our research aims at embedding robust watermarks in spatial domain and improving their detection. First, a spatial perceptual mask is proposed, based on the local variance of the initial image prediction error. A blind detector is also developed, which performs better than the existing ones. This is theoretically proved for the general attack case with linear filter and noise. Furthermore, a new spatial perceptual mask is proposed that allows for a significantly increased strength of the watermark, while at the same time the image quality remains very good. Its performance is compared to known and widely used masks and is proved to be much better. Moreover, an improved detector is developed, which, combined with the new mask, performs very well. Finally, a new multiplicative watermark embedding is proposed, which uses space-time block coding (specifically a 4x4 real orthogonal design). This scheme is proved to perform much better than the repetitive watermarking.

The rampant growth of the Internet has been coupled with an equivalent growth in cyber crime over the Internet. With our increased reliance on the Internet for commerce, social networking, information acquisition, and information exchange, intruders have found financial, political, and military motives for their actions. Network Intrusion Detection Systems (NIDSs) intercept the traffic at an organization’s periphery and try to detect intrusion attempts. Signature-based NIDSs compare the packet to a signature database consisting of known attacks and malicious packet fingerprints. The signatures use regular expressions to model these intrusion activities. This thesis presents a memory efficient pattern matching system for the class of regular expressions appearing frequently in the NIDS signatures. Proposed Cascaded Automata Architecture is based on two stage automata. The first stage recognizes the sub-strings and character classes present in the regular expression. The second stage consumes symbol generated by the first stage upon receiving input traffic symbols. The basic idea is to utilize the research done on string matching problem for regular expression pattern matching. We formally model the class of regular expressions mostly found in NIDS signatures. The challenges involved in using string matching algorithms for regular expression matching has been presented. We introduce length-bound transitions, counter-based states, and associated counter arrays in the second stage automata to address these challenges. The system uses length information along with counter arrays to keep track of overlapped sub-strings and character class based transition. We present efficient implementation techniques for counter arrays. The evaluation of the architecture on practical expressions from Snort rule set showed compression in number of states between 50% to 85%. Because of its smaller memory footprint, our solution is suitable for both software based implementations on network chips as well as FPGA based designs.