Επιστήμη Δεδομένων Και Βάσεις Δεδομένων

Βελτιστοποιημένος διαδοχικός μετασχηματισμός μέσου ποσοτικού προσδιορισμού

Ο αλγόριθμος διαδοχικού μέσου ποσοτικού μετασχηματισμού (SMQT) είναι ένας μη γραμμικός μετασχηματισμός που αποκαλύπτει την οργάνωση ή τη δομή των δεδομένων και αφαιρεί ιδιότητες όπως κέρδος και προκατάληψη. Σε ένα άρθρο με τίτλο Ο διαδοχικός μετασχηματισμός μέσου ποσοτικού προσδιορισμού , Το SMQT «εφαρμόζεται στην επεξεργασία ομιλίας και στην επεξεργασία εικόνων». Ο αλγόριθμος όταν εφαρμόζεται σε εικόνες 'μπορεί να θεωρηθεί ως προοδευτική εστίαση στις λεπτομέρειες μιας εικόνας'.

Ένας βελτιστοποιημένος διαδοχικός αλγόριθμος μετασχηματισμού μέσου ποσοτικού προσδιορισμού

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

Εφαρμόστε SMQT στη φωτεινότητα κάθε pixel - περιγράφει τον τύπο για τη λήψη της φωτεινότητας από το RGB κάθε pixel.
Εφαρμόστε SMQT σε κάθε κανάλι RGB ξεχωριστά - για τα κανάλια R, G και B ξεχωριστά.

Η παρακάτω εικόνα δείχνει το αποτέλεσμα των δύο τεχνικών:

Πηγή: Τελεστές χαρτογράφησης τόνου που βασίζονται σε SMQT για εικόνες υψηλής δυναμικής εμβέλειας

Εφαρμόζοντας τη δεύτερη τεχνική σε μια εικόνα του θεάτρου Bruin τη νύχτα, μπορούμε να δούμε πώς ο αλγόριθμος μεγεθύνει σταδιακά τις λεπτομέρειες της εικόνας και αποκαλύπτει λεπτομέρειες που αρχικά κρύβονται από το σκοτάδι:

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

Ο αλγόριθμος SMQT

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

Ας υποθέσουμε ότι έχουμε τον ακόλουθο φορέα (μπορείτε να το θεωρήσετε σαν πίνακα):

δεκαπέντε

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

Τα βήματα που περιλαμβάνονται στην εφαρμογή του αλγορίθμου SMQT είναι:

Υπολογίστε τον μέσο όρο του διανύσματος, ο οποίος σε αυτήν την περίπτωση είναι 29,58.
Χωρίστε το διάνυσμα σε δύο, αφήνοντας τους αριθμούς που είναι μικρότεροι ή ίσοι από 29,58 στο αριστερό μισό και τους αριθμούς που είναι μεγαλύτεροι στο δεξί μισό:

δεκαπέντε 4 0 5 18 32 48 60 64 59 47 31

0 0 0 0 0 ένας ένας ένας ένας ένας ένας ένας

Η δεύτερη σειρά είναι ο κωδικός που θα δημιουργήσουμε για κάθε τιμή. Οι τιμές μικρότερες ή ίσες με 29,58 λαμβάνουν 0 στον κωδικό της και οι αριθμοί μεγαλύτεροι από 29,58 παίρνουν 1 (αυτό είναι δυαδικό).
Τώρα και τα δύο προκύπτοντα διανύσματα χωρίζονται ξεχωριστά, με αναδρομικό τρόπο, ακολουθώντας τον ίδιο κανόνα. Στο παράδειγμά μας ο μέσος όρος του πρώτου διανύσματος είναι (15 + 4 + 0 + 5 + 18) / 5 = 8,4, και ο μέσος όρος του δεύτερου διανύσματος είναι (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48.7. Καθένας από αυτούς τους δύο διαχωρισμούς διαιρείται περαιτέρω σε δύο ακόμη διανύσματα, και ένα δεύτερο bit κώδικα προστίθεται σε καθένα ανάλογα με τη σύγκριση του με τον μέσο όρο. Αυτό είναι το αποτέλεσμα:

4 0 5 δεκαπέντε 18 32 47 31 48 60 64 59

00 00 00 01 01 10 10 10 έντεκα έντεκα έντεκα έντεκα

Σημειώστε ότι το 0 επισυνάφθηκε ξανά για αριθμούς χαμηλότερους από ή ίσους με το μέσο όρο (για κάθε διάνυσμα) και 1 για αριθμούς μεγαλύτερους από το μέσο όρο.
Αυτός ο αλγόριθμος επαναλαμβάνεται αναδρομικά:

0 4 5 δεκαπέντε 18 32 31 47 48 60 64 59

000 001 001 010 011 100 100 101 110 111 111 111

0 4 5 δεκαπέντε 18 31 32 47 48 60 59 64

0000 0010 0011 0100 0110 1000 1001 1010 1100 1110 1110 1111

0 4 5 δεκαπέντε 18 31 32 47 48 59 60 64

00000 00100 00110 01000 01100 10.000 10010 10100 11000 11100 11101 11110

Σε αυτό το σημείο κάθε διάνυσμα έχει μόνο ένα στοιχείο. Έτσι, για κάθε διαδοχικό βήμα ένα 0 θα επισυνάπτεται, καθώς ο αριθμός θα είναι πάντα ίσος με τον εαυτό του (η συνθήκη για το 0 είναι ότι ο αριθμός πρέπει να είναι μικρότερος ή ίσος με τον μέσο όρο, που είναι ο ίδιος).

Μέχρι στιγμής έχουμε επίπεδο ποσοτικοποίησης L = 5. Εάν επρόκειτο να χρησιμοποιήσουμε το L = 8, πρέπει να προσθέσουμε τρία 0 σε κάθε κωδικό. Το αποτέλεσμα της μετατροπής κάθε κώδικα από δυαδικό σε ακέραιο (για L = 8) θα ήταν:

0	4	5	δεκαπέντε	18	31	32	47	48	59	60	64
0	32	48	64	96	128	144	160	192	224	232	240

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

32	48	60	64	59	47	31	δεκαπέντε	4	0	5	18
144	192	232	240	224	160	128	64	32	0	48	96

Παρατηρήστε ότι στον προκύπτοντα φορέα:

Το κέρδος αφαιρέθηκε. Το αρχικό είχε χαμηλό κέρδος, με το εύρος του να κυμαίνεται από 0 έως 64. Τώρα το κέρδος του κυμαίνεται από 0 έως 240, το οποίο είναι σχεδόν ολόκληρο το εύρος των 8 bit. Λέγεται ότι το κέρδος αφαιρείται επειδή δεν έχει σημασία αν πολλαπλασιάσουμε όλα τα στοιχεία του αρχικού διανύσματος με έναν αριθμό, όπως το 2 ή εάν διαιρούμε όλα με το 2, το διάνυσμα εξόδου θα είναι περίπου το ίδιο. Το εύρος του θα είναι περίπου ολόκληρο το εύρος του διανύσματος προορισμού (8 bits για L = 8). Εάν πολλαπλασιάσουμε το διάνυσμα εισόδου με δύο, το διάνυσμα εξόδου θα είναι στην πραγματικότητα το ίδιο, γιατί σε κάθε βήμα οι ίδιοι αριθμοί που ήταν κάτω ή πάνω από το μέσο θα συνεχίσουν να είναι κάτω ή πάνω από αυτό και θα προσθέσουμε τα ίδια 0s ή 1s στην έξοδο. Μόνο αν διαιρούμε, το αποτέλεσμα θα είναι περίπου το ίδιο και όχι ακριβώς το ίδιο, γιατί οι περίεργοι αριθμοί όπως το 15 θα πρέπει να στρογγυλοποιηθούν και οι υπολογισμοί μπορεί να διαφέρουν τότε. Πήγαμε από μια σκοτεινή εικόνα σε μια εικόνα με τα εικονοστοιχεία της να κυμαίνονται από σκούρα χρώματα (0) έως ελαφρύτερα χρώματα (240), χρησιμοποιώντας ολόκληρο το εύρος.
Η μεροληψία αφαιρείται, αν και δεν μπορούμε να την παρατηρήσουμε σε αυτό το παράδειγμα. Αυτό συμβαίνει επειδή δεν έχουμε μεροληψία, καθώς η χαμηλότερη τιμή μας είναι 0. Εάν είχαμε πράγματι προκατάληψη, θα είχε καταργηθεί. Εάν πάρουμε οποιονδήποτε αριθμό «K» και τον προσθέσουμε σε κάθε στοιχείο του διανύσματος εισόδου, ο υπολογισμός των αριθμών πάνω και κάτω από τον μέσο όρο σε κάθε βήμα δεν θα διαφέρει. Η έξοδος θα παραμείνει η ίδια. Αυτό θα έκανε επίσης εικόνες πολύ φωτεινές για να γίνουν εικόνες που κυμαίνονται από σκούρα έως ανοιχτά χρώματα.
Έχουμε μια εικόνα με βελτιωμένες λεπτομέρειες. Σημειώστε πώς για κάθε αναδρομικό βήμα που κάνουμε πραγματικά κάνουμε ζουμ στις λεπτομέρειες και κατασκευάζουμε την έξοδο αποκαλύπτοντας αυτές τις λεπτομέρειες όσο το δυνατόν περισσότερο. Και δεδομένου ότι θα εφαρμόσουμε αυτήν την τεχνική σε κάθε κανάλι RGB, θα αποκαλύψουμε όσο το δυνατόν περισσότερες λεπτομέρειες, αν και χάνουμε πληροφορίες σχετικά με τους αρχικούς τόνους κάθε χρώματος.

Δίνεται μια εικόνα σαν ένα διάνυσμα με pixel RGB, με κάθε σημείο να είναι 8 bit για R, 8 για G και 8 για B · μπορούμε να εξαγάγουμε τρία διανύσματα από αυτό, ένα για κάθε χρώμα και να εφαρμόσουμε τον αλγόριθμο σε κάθε διάνυσμα. Στη συνέχεια, σχηματίζουμε ξανά το διάνυσμα RGB από αυτά τα τρία διανύσματα εξόδου και έχουμε την επεξεργασμένη εικόνα SMQT, όπως έγινε με αυτή του Bruin Theatre.

Περίπλοκο

Ο αλγόριθμος απαιτεί ότι για κάθε επίπεδο κβαντοποίησης (L), τα N στοιχεία πρέπει να επιθεωρούνται σε ένα πρώτο πέρασμα για να βρουν το μέσο όρο για κάθε διάνυσμα και στη συνέχεια σε ένα δεύτερο πέρασμα, καθένα από αυτά τα N στοιχεία πρέπει να συγκριθεί με τον αντίστοιχο μέσο στο για να χωρίσετε κάθε διάνυσμα με τη σειρά. Τέλος, τα στοιχεία N πρέπει να αντικατασταθούν από τους κωδικούς τους. Επομένως, η πολυπλοκότητα του αλγορίθμου είναι O ((L * 2 * N) + N) = O ((2 * L + 1) * N), που είναι O (L * N).

πώς να φτιάξετε προσαρμοσμένη γραμματοσειρά

Πηγή: Τελεστές χαρτογράφησης τόνου που βασίζονται σε SMQT για εικόνες υψηλής δυναμικής εμβέλειας

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

Βελτίωση

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

ένας

16	16	7	ένας	ένας	7	25	31	31	25
0	0	0	0	0	0	ένας	ένας	ένας	ένας

7	ένας	ένας	7	16	16	25	25	31	31
00	00	00	00	01	01	10	10	έντεκα	έντεκα

ένας	ένας	7	7	16	16	25	25	31	31
000	000	001	001	010	010	100	100	110	110

Τα διανύσματα δεν μπορούν να χωριστούν πια, και τα μηδενικά πρέπει να προσαρτηθούν μέχρι να φτάσουμε στο επιθυμητό L.

Για λόγους απλότητας, ας υποθέσουμε ότι η είσοδος μπορεί να κυμαίνεται από 0 έως 31 και η έξοδος από 0 έως 7 (L = 3), όπως φαίνεται στο παράδειγμα.

Σημειώστε ότι ο υπολογισμός του μέσου όρου του πρώτου διανύσματος (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 δίνει το ίδιο αποτέλεσμα με τον υπολογισμό του μέσου όρου ολόκληρου του διανύσματος, καθώς είναι ακριβώς το ίδιο διάνυσμα με τα στοιχεία με διαφορετική σειρά: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

Στο δεύτερο βήμα πρέπει να υπολογίσουμε κάθε διάνυσμα αναδρομικά. Υπολογίζουμε λοιπόν τον μέσο όρο των γκρίζων εισόδων, που είναι τα πρώτα 6 στοιχεία ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8), και ο μέσος όρος της κενής εισόδου, που είναι τα 4 τελευταία στοιχεία ((25 + 31 + 31 + 25) / 4 = 28):

ένας

Σημειώστε και πάλι ότι εάν χρησιμοποιήσουμε τον τελευταίο φορέα, αυτόν που έχει παραγγελθεί πλήρως, τα αποτελέσματα είναι τα ίδια. Για τα πρώτα 6 στοιχεία έχουμε: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8) και για τα τελευταία 4 στοιχεία: ((25 + 25 + 31 + 31) / 4 = 28) . Δεδομένου ότι είναι απλώς μια προσθήκη, η σειρά των καλοκαιριών δεν έχει σημασία.

ένας

Το ίδιο ισχύει για το επόμενο βήμα:

ένας

Οι υπολογισμοί είναι ίδιοι με τον τελευταίο φορέα: ((7 + 1 + 1 + 7) / 4 = 4) θα ισούται με ((1 + 1 + 7 + 7) / 4 = 4).

Και το ίδιο θα ισχύει για τα υπόλοιπα διανύσματα και βήματα.

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

Ας δούμε τα βήματα για να εφαρμόσουμε αυτό που θα ονομάσουμε αλγόριθμο FastSMQT στο παράδειγμά μας:

Δημιουργήστε έναν πίνακα με 32 στήλες και 3 σειρές όπως μπορείτε να δείτε παρακάτω. Η πρώτη σειρά στον πίνακα αντιπροσωπεύει το ευρετήριο του πίνακα (0 έως 31) και δεν είναι απαραίτητο να συμπεριληφθεί κατά την κωδικοποίηση του πίνακα. Ωστόσο, αποδεικνύεται ρητά ότι διευκολύνει την παρακολούθηση του παραδείγματος.
Επαναλάβετε τα στοιχεία Ν αφού μετρήσετε τη συχνότητα κάθε τιμής. Στο παράδειγμά μας, τα στοιχεία 1, 7, 16, 25 και 31 έχουν όλα συχνότητα 2. Όλα τα άλλα στοιχεία έχουν συχνότητα 0. Αυτό το βήμα έχει μια πολυπλοκότητα του O (N).

Τώρα που έχει γεμίσει το διάνυσμα συχνότητας, πρέπει να επαναλάβουμε αυτό το διάνυσμα (το διάνυσμα συχνοτήτων, όχι το διάνυσμα εισόδου). Δεν επαναλαμβάνουμε πλέον στοιχεία N, αλλά το R (το R βρίσκεται στο εύρος: 2 ^ L), το οποίο στην περίπτωση αυτή είναι 32 (0 έως 31). Κατά την επεξεργασία εικονοστοιχείων, το Ν μπορεί να είναι πολλά εκατομμύρια (megapixels), αλλά το R είναι συνήθως 256 (ένα διάνυσμα για κάθε χρώμα). Στο παράδειγμά μας είναι 32. θα συμπληρώσουμε ταυτόχρονα τις ακόλουθες δύο σειρές του τραπεζιού. Η πρώτη από αυτές τις σειρές (η δεύτερη του πίνακα) θα έχει το άθροισμα των συχνοτήτων μέχρι στιγμής. Το δεύτερο (το τρίτο του πίνακα) θα έχει το άθροισμα της τιμής όλων των στοιχείων που εμφανίστηκαν μέχρι στιγμής.

Στο παράδειγμά μας, όταν φτάσουμε στο 1, βάζουμε ένα 2 στη δεύτερη σειρά του πίνακα, επειδή έχουν εμφανιστεί μέχρι τώρα δύο 1s. Και βάζουμε επίσης ένα 2 στην τρίτη σειρά του πίνακα, επειδή 1 + 1 = 2. Συνεχίζουμε να γράφουμε αυτές τις δύο τιμές σε καθεμία από τις επόμενες θέσεις μέχρι να φτάσουμε στο 7. Δεδομένου ότι ο αριθμός 7 εμφανίζεται δύο φορές, προσθέτουμε 2 στο συσσωρευτής της δεύτερης σειράς, επειδή τώρα εμφανίστηκαν μέχρι τώρα 4 αριθμοί (1, 1, 7, 7). Και προσθέτουμε 7 + 7 = 14 στην τρίτη σειρά, με αποτέλεσμα 2 + 14 = 16, επειδή 1 + 1 + 7 + 7 = 16. Συνεχίζουμε με αυτόν τον αλγόριθμο μέχρι να ολοκληρώσουμε την επανάληψη αυτών των στοιχείων. Η πολυπλοκότητα αυτού του βήματος είναι O (2 ^ L), το οποίο στην περίπτωσή μας είναι O (32) και όταν εργάζεστε με pixel RGB είναι O (256).

Εγώ	ένας	2	...	6	7	8	...	δεκαπέντε	16	17	...	24	25	26	...	30	31
ν	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
n-σωρευτικό	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
άθροισμα	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

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

Εγώ ένας 7 16 25 31

ν 2 4 6 8 10

άθροισμα 2 16 48 98 160
Θυμηθείτε ότι θα μπορούσαμε να χρησιμοποιήσουμε τον τελευταίο (πλήρως παραγγελθέντα) φορέα για να κάνουμε τους υπολογισμούς για κάθε βήμα και τα αποτελέσματα θα παραμείνουν τα ίδια. Σημειώστε ότι εδώ, σε αυτόν τον πίνακα, έχουμε τον τελευταίο φορέα με όλους τους προκαταρκτικούς υπολογισμούς που έχουν ήδη γίνει.

Βασικά πρέπει να κάνουμε τον αλγόριθμο SMQT σε αυτόν τον μικρό φορέα, αλλά σε αντίθεση με τον αρχικό φορέα που ξεκινήσαμε, αυτός θα είναι πολύ πιο εύκολος.

Πρώτα πρέπει να υπολογίσουμε τη μέση τιμή όλων των δειγμάτων. Μπορούμε να το βρούμε εύκολα με: άθροισμα [31] / n [31] = 160/10 = 16. Έτσι χωρίσαμε τον πίνακα σε δύο διανύσματα και ξεκινήσαμε να γράφουμε τον δυαδικό κώδικα για καθένα:

Εγώ ένας 7 16 25 31

ν 2 4 6 8 10

άθροισμα 2 16 48 98 160

κώδικας 0 0 0 ένας ένας

Τώρα χωρίζουμε ξανά κάθε διάνυσμα. Ο μέσος όρος του πρώτου διανύσματος είναι: άθροισμα [16] / n [16] = 48/6 = 8. Και ο μέσος όρος του δεύτερου διανύσματος είναι: (άθροισμα [31] - άθροισμα [16]) / (ν [31] - n [16]) = (160 - 48) / (10 - 6) = 112/4 = 28.

Εγώ ένας 7 16 25 31

ν 2 4 6 8 10

άθροισμα 2 16 48 98 160

κώδικας 00 00 01 10 έντεκα

Απομένει μόνο ένα διάνυσμα για διαχωρισμό. Ο μέσος όρος είναι: άθροισμα [7] / n [7] = 16/4 = 4.

Εγώ ένας 7 16 25 31

ν 2 4 6 8 10

άθροισμα 2 16 48 98 160

κώδικας 000 001 010 100 110

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

Η πολυπλοκότητα αυτού του βήματος είναι O (L * (2 ^ L)), το οποίο για ένα L = 8, και σε πρακτικές ανάγκες επεξεργασίας εικόνας, είναι O (8 * (256)) = O (2048) = σταθερό.
Το τελευταίο βήμα είναι να επαναλάβουμε τα στοιχεία Ν αντικαθιστώντας ξανά το στοιχείο από τον κωδικό του για κάθε στοιχείο: στοιχείο [i] = κωδικός [i]. Η πολυπλοκότητα είναι O (N). Η πολυπλοκότητα του FastSMQT είναι O (N) + O (2 ^ L) + O (L * (2 ^ L)) + O (N) = O (2 * N) + O ((L + 1) * (2 ^ L)) = O (N + L * (2 ^ L)).

Παραλληλισμός

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

Για να παραλληλίσουμε τον αλγόριθμο SMQT, όταν διαιρούμε ένα διάνυσμα σε δύο, μπορούμε να επεξεργαστούμε κάθε υπο-διάνυσμα σε έναν νέο πυρήνα εάν υπάρχει ένας πυρήνας (στην πραγματικότητα ένας υπο-φορέας στον τρέχοντα πυρήνα και ο άλλος σε έναν νέο πυρήνα). Αυτό μπορεί να γίνει αναδρομικά μέχρι να φτάσουμε στον συνολικό αριθμό των διαθέσιμων πυρήνων. Οι αντικαταστάσεις τιμών με κωδικούς μπορούν επίσης να γίνουν παράλληλα για.

Ο αλγόριθμος FastSMQT μπορεί επίσης να παραλληλιστεί. Στο πρώτο βήμα, ο φορέας εισόδου πρέπει να χωριστεί στον αριθμό των διαθέσιμων πυρήνων (C). Πρέπει να δημιουργηθεί ένα διάνυσμα μέτρησης συχνότητας για κάθε ένα από αυτά τα μέρη και να συμπληρωθεί παράλληλα. Στη συνέχεια προσθέτουμε τις τιμές αυτών των διανυσμάτων σε έναν προκύπτον φορέα συχνοτήτων. Το επόμενο βήμα που μπορεί να παραλληλιστεί είναι το τελευταίο, όταν αντικαθιστούμε τις τιμές με τους κωδικούς τους. Αυτό μπορεί να γίνει παράλληλα για.

Σύγκριση πολυπλοκότητας

Η συνολική πολυπλοκότητα του αρχικού αλγορίθμου SMQT είναι O ((2 * L + 1) * N), που είναι O (L * N).

Η πολυπλοκότητα του FastSMQT είναι O (N) + O (2 ^ L) + O (L * (2 ^ L)) + O (N) = O (2 * N) + O ((L + 1) * (2 ^ L)) = O (N + L * (2 ^ L)).

Με δεδομένο ένα σταθερό L, η πολυπλοκότητα γίνεται μόνο O (N) και για τα δύο. Αλλά η σταθερά που πολλαπλασιάζει το Ν είναι πολύ μικρότερη για το FastSMQT και κάνει μεγάλη διαφορά στον χρόνο επεξεργασίας όπως θα δούμε.

Το παρακάτω γράφημα συγκρίνει την απόδοση τόσο των αλγορίθμων SMQT όσο και FastSMQT για L = 8, που ισχύει για την επεξεργασία εικόνας. Το γράφημα δείχνει το χρόνο (σε χιλιοστά του δευτερολέπτου) που χρειάζεται για την επεξεργασία των στοιχείων Ν. Σημειώστε ότι η πολυπλοκότητα (με σταθερές) του SMQT για L = 8 είναι O (17 * N), ενώ για το FastSMQT είναι O (2 * N + 2304).

Όσο μεγαλύτερο είναι το Ν, τόσο περισσότερο χρειάζεται το SMQT για την επεξεργασία της εικόνας. Για το FastSMQT από την άλλη πλευρά, η ανάπτυξη είναι πολύ πιο αργή.

Για ακόμη μεγαλύτερες τιμές Ν, η διαφορά στην απόδοση είναι πολύ πιο εμφανής:

Εδώ το SMQT χρειάζεται έως και πολλά δευτερόλεπτα χρόνου για την επεξεργασία ορισμένων εικόνων, ενώ το FastSMQT εξακολουθεί να βρίσκεται εντός της ζώνης «λίγα χιλιοστά του δευτερολέπτου».

Ακόμα και με πολλούς πυρήνες (δύο, σε αυτήν την περίπτωση), το FastSMQT είναι σαφώς ακόμα ανώτερο από το SMQT:

Το FastSMQT δεν εξαρτάται από το L.

τι είναι η αρχιτεκτονική πληροφοριών;

συμπέρασμα

Δεν ισχύουν όλες οι τεχνικές βελτιστοποίησης για όλους αλγόριθμοι , και το κλειδί για τη βελτίωση της απόδοσης ενός αλγορίθμου κρύβεται συχνά μέσα από μια εικόνα για το πώς λειτουργεί ο αλγόριθμος. Αυτός ο αλγόριθμος FastSMQT εκμεταλλεύεται τις δυνατότητες προκαθορισμού τιμών και τη φύση των μέσων υπολογισμών. Ως αποτέλεσμα, επιτρέπει ταχύτερη επεξεργασία από το αρχικό SMQT. Η ταχύτητα δεν επηρεάζεται από την αύξηση του L, αν και το L δεν μπορεί να είναι πολύ μεγαλύτερο από το συνηθισμένο 8, επειδή η χρήση μνήμης είναι 2 ^ L, η οποία για το 8 είναι αποδεκτή 256 (αριθμός στηλών στον πίνακα συχνοτήτων μας), αλλά το κέρδος απόδοσης έχει προφανή πρακτικά οφέλη.

Αυτή η βελτίωση της ταχύτητας επέτρεψε στο MiddleMatter να εφαρμόσει τον αλγόριθμο σε ένα Εφαρμογή iOS (και ένα Εφαρμογή Android ) που βελτιώνει τις εικόνες και τα βίντεο που τραβήχτηκαν σε συνθήκες χαμηλού φωτισμού. Με αυτήν τη βελτίωση, ήταν δυνατή η εκτέλεση επεξεργασίας βίντεο στην εφαρμογή, η οποία διαφορετικά θα ήταν πολύ αργή ios συσκευές.

Ο κωδικός C ++ για αλγόριθμους SMQT και FastSMQT είναι διαθέσιμο στο GitHub .