Εξακρίβωση παραμέτρων και αλγοριθμική κατασκευή μορφοκλασματικών συναρτήσεων παρεμβολής: Εφαρμογές στον ψηφιακό εικονισμό και την οπτικοποίηση

Abstract

The subject of this dissertation belongs to the greater field of knowledge of fractal geometry and its applications, such as data imaging, computer vision and visualization. Its main contribution is in the parameter identification, the algorithmic construction and applications of fractal interpolation. We focus on self-affine and piecewise self-affine fractal interpolation functions that are based on the theory of iterated function systems.

The generic problem we intend to solve is the following. Given a set of points, we select a subset of them as interpolation points and construct a fractal function that passes through them. The identification of the parameters, free or not, of such a function is important since it determines the quality of interpolation with respect to the initial set of points. Specifically, we present two novel methods for parameter identification that are based on minimising the symmetric difference between bounding volumes of appropriately chosen points, achieving lower errors compared to existing methods. Furthermore, we present a novel method that aims at preserving the fractal dimension of the initial set of points.

Beyond these, we introduce a new method for curve fitting using fractal interpolation, allowing a more economical representation compared to existing methods, thus achieving lower error for a given compression ratio. Moreover, we present a new method for constructing continuous fractal interpolation surfaces by extending and correcting an existing one.

As far as the applications of fractal interpolation are concerned, we focus on data imaging, including visualization and computer vision, as well as data modelling. Specifically, we present (a) a new algorithm for triangulating isosurfaces using fractal interpolation surfaces; it is based on the methodology of the well-known marching cubes algorithm, achieving better results for a given grid resolution, while producing an adjustable amount of output primitives, (b) a new method for modelling point clouds based on fractal interpolation, which achieves considerable compression ratios and allows multiresolution reconstruction, (c) active shape models using fractal interpolation, which present the advantage of requiring a considerably smaller number of landmark points and thus a simpler annotation process, (d) the application of fractal interpolation to medical and geographic data, demonstrating its suitability in these cases.

Το αντικείμενο της διατριβής εντάσσεται στην ευρύτερη περιοχή της μορφοκλασματικής γεωμετρίας και των εφαρμογών της, όπως ο εικονισμός δεδομένων, η τεχνητή όραση και η οπτικοποίηση. Η κύρια συνεισφορά της συνίσταται στην εξακρίβωση των παραμέτρων, την αλγοριθμική κατασκευή και τις εφαρμογές της μορφοκλασματικής παρεμβολής. Εστιάζουμε στις αυτοκηδεστικές και τμηματικώς αυτοκηδεστικές μορφοκλασματικές συναρτήσεις παρεμβολής βασιζόμενες στα επαναλαμβανόμενα συστήματα συναρτήσεων.

Το γενικό πρόβλημα το οποίο καλούμαστε να επιλύσουμε είναι το εξής. Δεδομένου ενός συνόλου σημείων, επιλέγουμε υποσύνολό τους ως σημεία παρεμβολής και κατασκευάζουμε μία μορφοκλασματική συνάρτηση η οποία διέρχεται από αυτά. Η εξακρίβωση των παραμέτρων είναι σημαντική καθώς προσδιορίζει την ακρίβεια της παρεμβολής ως προς το αρχικό συνόλο. Συγκεκριμένα, παρουσιάζουμε δύο νέες μεθόδους εξακρίβωσης παραμέτρων βασιζόμενες στη χρήση περιβαλλόντων όγκων καταλλήλως επιλεγμένων σημείων και επιτυγχάνουν χαμηλότερο σφάλμα ως προς τις υπάρχουσες μεθόδους. Επιπλέον, παρουσιάζουμε μια νέα μέθοδο η οποία στοχεύει στην διατήρηση της μορφοκλασματικής διάστασης του αρχικού συνόλου.

Πέραν αυτών, προτείνουμε μία νέα μέθοδο προτυποποίησης καμπυλών βασισμένη στην μορφοκλασματική παρεμβολή, η οποία παρέχει οικονομικότερη αναπαράσταση σε σχέση με αντίστοιχες υπάρχουσες μεθόδους, επιτυγχάνοντας έτσι χαμηλότερο σφάλμα για δεδομένο λόγο συμπίεσης. Περαιτέρω, παρουσιάζουμε μία νέα μεθοδοδολογία κατασκευής συνεχών μορφοκλασματικών επιφανειών παρεμβολής, επεκτείνοντας και διορθώνοντας μία υπάρχουσα.

Όσον αφορά στις εφαρμογές της μορφοκλασματικής παρεμβολής, εστιάζουμε στον εικονισμό δεδομένων και την προτυποποίηση δεδομένων. Παρουσιάζουμε (α) έναν νέο αλγόριθμο τριγωνοποίησης ισοεπιφανειών με τη χρήση μορφοκλασματικών επιφανειών παρεμβολής παρέχοντας την δυνατότητα ακριβέστερης τριγωνοποίησης για δεδομένη ανάλυση πλέγματος καθώς και παραγωγής ρυθμιζομένου πλήθους τριγώνων, (β) μία νέα μεθοδολογία προτυποποίησης νεφών σημείων βασιζόμενη στην μορφοκλασματική παρεμβολή, η οποία παρέχει τη δυνατότητα επίτευξης αξιόλογου λόγου συμπίεσης και ανακατασκευής σε ρυθμιζόμενο βαθμό λεπτομέρειας, (γ) τα πρότυπα ενεργών μορφών με τη χρήση μορφοκλασματικής παρεμβολής, τα οποία απαιτούν σημαντικά μικρότερο πλήθος οροθέσιων σημείων και συνεπώς απλούστερη διαδικασία σήμανσης, (δ) εφαρμογή της μορφοκλασματικής παρεμβολής σε ιατρικά και γεωγραφικά δεδομένα επιδεικνύοντας την καταλληλότητά της.