Μετασχηματισμό κυματιδίων: τον προσδιορισμό παράδειγμα εφαρμογής

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

Τι είναι μια ψηφιακή εικόνα

Οπτικές πληροφορίες στον υπολογιστή αντιπροσωπεύεται με τη μορφή των αριθμών. Με απλά λόγια, μια φωτογραφία που τραβήχτηκε με μια ψηφιακή συσκευή, είναι ένας πίνακας στον οποίο τα κύτταρα άρχισε τις αξίες της κάθε χρώμα pixel της. Όταν πρόκειται για μια μονόχρωμη εικόνα, τότε αντικαθίστανται από τιμές φωτεινότητας από το διάστημα [0, 1], όπου το 0 χρησιμοποιείται για να αναφερθεί σε μαύρο, και 1 - άσπρο. Άλλα χρώματα δοθεί κλασματική αριθμούς, αλλά με τους δύσκολο να λειτουργήσει, έτσι ώστε η περιοχή επεκτείνεται και η τιμή που έχει επιλεγεί από το διάστημα μεταξύ 0 και 255. Γιατί συμβαίνει αυτό; Είναι απλό! Με αυτή την επιλογή στην δυαδική αναπαράσταση για την κωδικοποίηση της φωτεινότητας του κάθε pixel απαιτεί ακριβώς ένα byte. Είναι προφανές ότι πολλοί μνήμης που απαιτείται για την αποθήκευση ακόμη και μια μικρή εικόνα. Για παράδειγμα, το μέγεθος εικόνας 256 χ 256 εικονοστοιχεία παίρνει 8 Kbytes.

Λίγα λόγια για μεθόδους συμπίεσης εικόνας

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

Για lossy αλγόριθμους συμπίεσης περιλαμβάνουν:

• JPEG. Αυτό είναι μακράν ένα από τα πιο δημοφιλή αλγορίθμων. Βασίζεται στη χρήση του διακριτού μετασχηματισμού συνημίτονου. Για να είμαστε δίκαιοι θα πρέπει να σημειωθεί ότι υπάρχουν επιλογές για JPEG συμπίεση απόδοση χωρίς απώλειες. Αυτές περιλαμβάνουν χωρίς απώλειες JPEG και JPEG-LS.
• JPEG 2000. Ο αλγόριθμος που χρησιμοποιείται σε κινητές εξέδρες, και βασίζεται στην εφαρμογή ενός διακριτού μετασχηματισμού κυματιδίων.
• fractal συμπίεση. Σε ορισμένες περιπτώσεις, σας επιτρέπει τη λήψη εικόνων εξαιρετικής ποιότητας ακόμα και με ισχυρή συμπίεση. Ωστόσο, λόγω προβλημάτων με την κατοχύρωση αυτής της μεθόδου εξακολουθεί να είναι εξωτικό.

Lossless αλγόριθμοι συμπίεσης που εκτελούνται από:

• RLE (χρησιμοποιείται ως η κύρια μέθοδος σε μορφή TIFF, BMP, TGA).
• LZW (που χρησιμοποιείται σε μορφή GIF).
• LZ-Huffman (που χρησιμοποιείται για μορφή PNG).

μετασχηματισμού Fourier

Πριν στρέφονται προς το κυματιδίων, είναι λογικό να διερευνήσει τις σχετικές λειτουργίες, περιγράφοντας τους συντελεστές της επέκτασης της αρχικής πληροφοριών σε στοιχειώδη συστατικά, δηλ. Ε Αρμονική δονήσεις με διαφορετικές συχνότητες. Με άλλα λόγια, ο μετασχηματισμός Fourier - ένα μοναδικό εργαλείο που συνδέει διακριτές και συνεχείς κόσμους.

Μοιάζει με αυτό:

Ο τύπος αναστροφής γράφεται ως εξής:

Τι είναι ένα wavelet

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

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

wavelet μετασχηματισμού

Αυτή η μέθοδος μετατροπής σήματος (λειτουργίες) επιτρέπει να μεταφράσει από μια φορά στην αναπαράσταση χρόνου-συχνότητας.

Για να κυματιδίων μετασχηματισμού ήταν δυνατό, για το αντίστοιχο κυματιδίων λειτουργία, πρέπει να πληρούνται οι εξής προϋποθέσεις:

• Αν για κάποιο ψ λειτουργία (t) -Fourier μετατρέψει έχει τη μορφή

ότι η κατάσταση πρέπει να πληρούνται:

Επιπλέον:

• Wavelet πρέπει να έχει πεπερασμένη ενέργεια?
• θα πρέπει να είναι ολοκληρώσιμη συνεχής και έχουν συμπαγή υποστήριξη?
• κυματιδίων πρέπει να εντοπίζεται τόσο στη συχνότητα και στο χρόνο (χώρο).

τύποι

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

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

Vayvlet Haar

Για να συμπιέσετε μια εικόνα, είναι απαραίτητο να βρεθεί μια ορισμένη κανονικότητα μεταξύ των δεδομένων του, και ακόμα καλύτερα αν θα είναι μακριές αλυσίδες μηδενικά. Αυτό είναι όπου μπορεί να είναι χρήσιμο για τον μετασχηματισμό κυματιδίων αλγόριθμο. Ωστόσο, συνεχίζουμε να επανεξετάσει τις μεθόδους εργασίας στην τάξη.

Πρώτον, είναι αναγκαίο να υπομνησθεί ότι οι εικόνες η φωτεινότητα των παρακείμενων πίξελ χαρακτηρίζεται συνήθως από ένα μικρό ποσό. Ακόμα κι αν υπάρχουν εικόνες σε πραγματικό περιοχές με έντονη, σε αντίθεση διαφορές φωτεινότητας, καταλαμβάνουν μόνο ένα μικρό μέρος της εικόνας. Ως παράδειγμα, να αναλάβει τη γνωστή δοκιμή Lenna κλίμακα του γκρι της εικόνας. Αν πάρουμε έναν πίνακα της φωτεινότητας των εικονοστοιχείων του, τότε το μέρος της πρώτης γραμμής θα εμφανιστεί ως μια ακολουθία αριθμών 154, 155, 156, 157, 157, 157, 158, 156.

μπορείτε να εφαρμόσετε τη λεγόμενη μέθοδο δέλτα για να πάρει μηδενικά σε αυτό. Για να γίνει αυτό, να κρατήσει μόνο τον πρώτο αριθμό, και για τους άλλους να πάρει μόνο τις διαφορές του κάθε προηγούμενο με το σύμβολο «+» ή «-».

Το αποτέλεσμα είναι μία ακολουθία 154,1,1,1,0,0,1, -2.

Ένα μειονέκτημα της δέλτα-κωδικοποίησης είναι μη-τόπο της. Με άλλα λόγια, είναι αδύνατο να πάρει μόνο ένα κομμάτι της σειράς και ανακαλύψτε τι φωτεινότητα που κωδικοποιείται, αποκωδικοποιείται, αν όχι όλες οι τιμές που έχει μπροστά του.

Για να ξεπεραστεί αυτό το μειονέκτημα, ο αριθμός διαιρείται σε ζεύγη και καθένα είναι το ήμισυ του αθροίσματος των (ν. Α) και το ήμισυ της διαφοράς (v. D), m. F. Για (154,155) (156,157) (157,157) (158,156) έχουν (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1.0). Σε αυτή την περίπτωση, είναι πάντα δυνατό να βρούμε την τιμή των δύο αριθμών σε ένα ζευγάρι.

Σε γενικές γραμμές, το διακριτό μετασχηματισμό κυματιδίων του σήματος S, έχουμε:

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

συμπίεση

Όπως ήδη αναφέρθηκε, μία από τις εφαρμογές της μετασχηματισμό κυματιδίων αλγόριθμος είναι η μέθοδος συμπίεσης JPEG 2000 χρησιμοποιώντας Haar βασίζεται στο φορέα μετάφραση των δύο εικονοστοιχείων στο Χ και διάνυσμα Υ (Χ + Υ) / 2 και (Χ - Y) / 2. Αρκεί να πολλαπλασιάσει το αρχικό διάνυσμα στο παρακάτω πίνακα.

Εάν τα σημεία περισσότερο, να διαρκέσει περισσότερο μήτρας, τα οποία είναι διατεταγμένα σε μια διαγώνια H. μήτρα Ως εκ τούτου, η αρχική διάνυσμα ανεξάρτητα του μήκους της σε επεξεργασία σε ζευγάρια.

φίλτρα

Το προκύπτον «μισό-αθροίσματος» - είναι οι μέσες τιμές φωτεινότητας των εικονοστοιχείων σε ζεύγη. Αυτή είναι η αξία όταν μετατρέπονται σε εικόνα θα πρέπει να του δώσει ένα αντίγραφο, μειωμένο κατά 2 φορές. Σε αυτό το μισό-αθροίσματος κατά μέσο όρο φωτεινότητα, t. Ε «φιλτραρισμένο» τυχαίες ριπές των τιμών τους και ενεργούν ως φίλτρα συχνοτήτων.

Τώρα ας ασχοληθεί με εκείνους που δείχνουν τη διαφορά. Έχουν «απομονωμένο» interpixel «ριπές», αφαιρώντας τη συνεχή συνιστώσα, δηλ. Ε «φιλτραρισμένο» τιμές σε χαμηλές συχνότητες.

Ακόμα και από τα παραπάνω Haar κυματιδίων μετασχηματισμό για τα «ανδρείκελα» γίνεται φανερό ότι είναι ένα ζεύγος φίλτρων που διαιρούν ένα σήμα σε δύο συνιστώσες: το υψηλής συχνότητας και χαμηλής συχνότητας. απλά εκ νέου ενωθούν αυτά τα στοιχεία για να ληφθεί το αρχικό σήμα.

παράδειγμα

Ας υποθέσουμε ότι θέλουμε να συμπιέσει τη φωτογραφία (δοκιμαστική εικόνα Lenna). Εξετάστε το παράδειγμα του κύματος μετατρέψει τη μήτρα της λαμπρότητας pixel. Το εξάρτημα υψηλής συχνότητας εικόνας είναι υπεύθυνη για την εμφάνιση λεπτομέρεια και περιγράφει το θόρυβο. Όσο για το χαμηλής-συχνότητας, που περιέχει πληροφορίες σχετικά με το σχήμα του προσώπου και την ομαλή κλίσεις της φωτεινότητας.

Χαρακτηριστικά φωτογραφίες της ανθρώπινης αντίληψης είναι τέτοια ώστε το τελευταίο είναι πιο σημαντικό συστατικό. Αυτό σημαίνει ότι όταν συμπιέζεται ένα ορισμένο τμήμα των δεδομένων υψηλής συχνότητας μπορεί να απορρίπτεται. Το περισσότερο επειδή έχει λιγότερη αξία και κωδικοποιείται πιο συμπαγή.

Για να αυξηθεί ο βαθμός συμπίεσης μπορεί να εφαρμοστεί αρκετές φορές μετασχηματισμού Haar σε δεδομένα χαμηλής συχνότητας.

Η χρήση των δύο διαστάσεων συστοιχίες

Όπως ήδη αναφέρθηκε, η ψηφιακή εικόνα στον υπολογιστή είναι υπό τη μορφή μιας μήτρας των εντάσεων τιμών των εικονοστοιχείων του. Έτσι, θα πρέπει να ενδιαφέρονται για ένα δισδιάστατο Haar wavelet μετασχηματισμό. Για την εφαρμογή απαιτείται απλά να εκτελέσει διαστάσεων μετατροπή του σε κάθε σειρά και κάθε στήλη του πίνακα των εντάσεων των pixels στην εικόνα.

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

Όλα αυτά τα βήματα έχει ως αποτέλεσμα το ότι η μήτρα αποκτάται το οποίο περιέχει μεγάλες ποσότητες 0. Θα πρέπει να γραφτεί γραμμή προς γραμμή σε ένα αρχείο κειμένου και να συμπιέσει οποιοδήποτε archiver.

αποκρυπτογράφηση

Το αντίστροφο μετασχηματισμό στην εικόνα στο παρακάτω αλγόριθμο:

• Είναι αποσυμπιέζει ένα αρχείο?
• ισχύει αντίστροφη Haar μετασχηματισμό?
• Η αποκωδικοποιημένη εικόνα μετατρέπεται σε μία μήτρα.

Πλεονεκτήματα σε σύγκριση με το JPEG

было сказано, что он основан на ДКП. Κατά την εξέταση του αλγορίθμου Joint Photographic Experts Group είπαν ότι βασίζεται σε DCT. Αυτή η μετατροπή διεξάγεται σε μπλοκ (8 χ 8 εικονοστοιχεία). Ως αποτέλεσμα, αν μια ισχυρή συμπίεση περί της μειωμένης εικόνα γίνεται αισθητή δομή μπλοκ. Κατά τη διάρκεια της συμπίεσης που χρησιμοποιούν κυματίδια ένα τέτοιο πρόβλημα είναι απούσα. Ωστόσο, ο θόρυβος μπορεί να εμφανιστεί διαφορετικό τύπο που έχουν την εμφάνιση των κυματισμών γύρω από τις άκρες. Πιστεύεται ότι παρόμοια αντικείμενα κατά μέσο όρο λιγότερο αισθητή από ό, τι «τετράγωνα» που δημιουργούνται κατά τη χρήση αλγορίθμου JPEG.

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