next up previous contents
Next: ΛΟΓΙΣΜΙΚΟ ΓΙΑ Up: Ταχύς Μετασχηματισμός Previous: Γρήγορος Πολυωνυμικός Πολλαπλασιασμός   Contents

ΚΥΜΑΤΑΚΙΑ

Οι συναρτήσεις ημίτονου και συνημίτονου που χρησιμοποιήθηκαν στην ανάλυση 21#21 έχουν πολύ χρήσιμα χαρακτηριστικά μεγάλης πρακτικής σημασίας σε έναν ευρύ φάσμα εφαρμογών, αλλά δεν είναι ιδανικές για όλες τις περιπτώσεις. Συγκεκριμένα, αυτές οι συναρτήσεις είναι πολύ ομαλές (απείρως διαφορήσιμες) και πολύ γενικές (μη μηδενικές σχεδόν παντού πάνω στην ευθεία των πραγματικών). Ως αποτέλεσμα, δεν είναι πολύ αποτελεσματικές για την αναπαράσταση συναρτήσεων οι οποίες αλλάζουν απότομα ή έχουν πολύ περιορισμένη υποστήριξη. Το φαινόμενο 1733#1733 στην αναπαράσταση 21#21 ενός τετραγωνικού κύματος (το ξεκάθαρο σημείο είναι οι γωνίες) είναι μία υλοποίησή του.

Σαν απάντηση σε αυτή την ατέλεια, έχουμε δώσει έντονο ενδιαφέρον τα τελευταία χρόνια σε έναν νέο τύπο βασικών συναρτήσεων που λέγονται κυματάκια. Μία δοσμένη βάση από κυματάκια παράγεται από μία και μόνο συνάρτηση 1734#1734, που λέγεται μητρικό κυματάκι ή κλιμακούμενη συνάρτηση, με διεύρυνση και μετασχηματισμό συντεταγμένων, δηλ., 1735#1735, όπου 431#431 και 365#365 είναι πραγματικοί αριθμοί με 1736#1736. Υπάρχουν πολλοί διαφορετικοί τρόποι να επιλέξουμε το μητρικό κυματάκι. Το βασικό θέμα είναι η εξισορρόπηση μεταξύ της ομαλότητας και της οικονομίας αποθηκευτικού χώρου. Ένα μέλος μίας από τις συχνότερα χρησιμοποιούμενες οικογένειες από κυματάκια, προς τιμήν του 1737#1737, παρουσιάζεται στο Σχήμα 12.3.

Συνηθισμένες επιλογές για παραμέτρους διεύρυνσης και μετασχηματισμού συντεταγμένων είναι 1738#1738 και 1739#1739, όπου 573#573 και 432#432 είναι ακέραιοι, ώστε να ισχύει 1740#1740. Αν το μητρικό κυματάκι 1734#1734 έχει αρκετά περιορισμένη υποστήριξη, τότε


1741#1741

όποτε οι δείκτες δεν είναι ίδιοι μεταξύ τους, δηλ., η διπλού δείκτη βάση συναρτήσεων 1742#1742 είναι ορθογώνια. Επαναλαμβάνοντας το μητρικό κυματάκι σε πολλές διαφορετικές κλίμακες, είναι δυνατόν να μιμηθούμε τη συμπεριφορά οποιασδήποτε συνάρτησης σε πολλές διαφορετικές κλίμακες. Αυτή η ιδιότητα που έχουν τα κυματάκια λέγεται πολλαπλή ανάλυση. Οι βασικές συναρτήσεις 21#21 περιορίζονται στη συχνότητα, αλλά όχι και στο χρόνο: μικρές αλλαγές στη συχνότητα προκαλούν αλλαγές παντού στο πεδίο του χρόνου. Τα κυματάκια περιορίζονται τόσο στη συχνότητα (μέσω της διεύρυνσης) όσο και στο χρόνο (μέσω του μετασχηματισμού συντεταγμένων). Αυτός ο περιορισμός τείνει να κάνει την αναπαράσταση από τα κυματάκια πολύ αραιή.

ΣΧΗΜΑ 12.3 Μητρικό κυματάκι 1743#1743 του 1737#1737

Όπως και με τον μετασχηματισμό 21#21, υπάρχει ένας ανάλογος διακριτός κυματικός μετασχηματισμός, ή ΔΚΜ. Ο ΔΚΜ και ο αντίστροφός του μπορούν να υπολογιστούν πολύ αποτελεσματικά μέσω ενός πυραμιδικού, ή ιεραρχικού, αλγορίθμου. Στην πραγματικότητα, η αραιότητα της βάσης από κυματάκια κάνει τον υπολογισμό του ΔΜΚ ακόμα πιο γρήγορο και από του 22#22 -απαιτεί μόνο 1673#1673 εργασία αντί για 1710#1710 για μία ακολουθία μήκους 366#366. Εξαιτίας της αποδοτικότητάς τους, τόσο στον υπολογισμό όσο και στην κατάληψη μικρού χώρου κατά την αναπαράσταση, τα κυματάκια παίζουν όλο και πιο σημαντικό ρόλο σε πολλούς τομείς της επεξεργασίας σημάτων και εικόνων, όπως η συμπίεση δεδομένων, η αφαίρεση του θορύβου, και η οπτική υπολογιστών, και αρχίζουν να χρησιμοποιούνται ακόμα και ως βασικές συναρτήσεις για την επίλυση διαφορικών εξισώσεων.



Manolis Vavalis 2000-03-24