Γρήγοροι αλγόριθμοι επεξεργασίας και ανάλυσης δυαδικών εικόνων
Authors: Σπηλιώτης Ηρακλής 
Published: August 2021

Στην παρούσα διδακτορική διατριβή παρουσιάζεται μια νέα καινοτόμος μέθοδος για την αναπαράσταση δυαδικών εικόνων, η αναπαράσταση εικόνων με ομάδες. Η μέθοδος αυτή εντάσσεται στις μεθόδους αναπαράστασης εικόνων με βάση τις περιοχές. Ομάδα καλείται μια ορθογώνια περιοχή της εικόνας, με πλευρές παράλληλες προς τους άξονες, που περιέχει εικονοστοιχεία της ίδιας φωτεινότητας. Κάθε εικονοστοιχείο της εικόνας με φωτεινότητα αντικειμένου, ανήκει σε μία και μόνο μία ομάδα. Έτσι η αναπαράσταση δυαδικών εικόνων με ομάδες, είναι μια μέθοδος αναπαράστασης που δεν προκαλεί απώλεια πληροφορίας και είναι ισοδύναμη με την αναπαράσταση εικόνων με δισδιάστατο πίνακα. Η αναπαράσταση εικόνων με ομάδες υπερτερεί σε σύγκριση με άλλες μεθόδους αναπαράστασης περιοχών, όπως είναι η αναπαράσταση με μήκη τρεξίματος και η αναπαράσταση με τετραδικά δένδρα. Η αναπαράσταση με ομάδες οδηγεί σε μικρότερο πλήθος ομάδων σε σχέση με το πλήθος των μηκών τρεξίματος και το πλήθος των κόμβων του τετραδικού δένδρου. Όπως σε κάθε άλλη μέθοδο αναπαράστασης περιοχών, το κύριο πλεονέκτημα που μας παρέχει η αναπαράσταση εικόνων με ομάδες, είναι η παροχή μηχανικής αντίληψης για περιοχές μεγαλύτερες του εικονοστοιχείου. Επομένως είναι δυνατή η υποκατάσταση λειτουργιών που θα απαιτούνταν για όλα τα εικονοστοιχεία μιας ομάδας, με μία μόνο λειτουργία στην ομάδα. Το χαρακτηριστικό αυτό οδηγεί στην υλοποίηση αλγορίθμων επεξεργασίας και ανάλυσης εικόνων που απαιτούν μειωμένη υπολογιστική πολυπλοκότητα. Στην παρούσα διδακτορική διατριβή, έχουν προταθεί γρήγοροι αλγόριθμοι επεξεργασίας και ανάλυσης εικόνων, που υλοποιούνται σε εικόνες που παριστάνονται με ομάδες και επιτυγχάνουν σημαντική μείωση του απαιτούμενου υπολογιστικού κόστους. Συγκεκριμένα, οι αλγόριθμοι αυτοί αφορούν: Τη γρήγορη ολίσθηση, κλιμάκωση και περιστροφή δυαδικών εικόνων. Την ετικετοποίηση συνδεδεμένων τμημάτων, λειτουργία η οποία βασίζεται στο σχηματισμό αλυσίδων συνδεδεμένων ομάδων και επιτρέπει την ανίχνευση αντικειμένων και τον έλεγχο της σύνδεσης περιοχών της εικόνας. Την εύρεση ελάχιστης και μέγιστης απόστασης μεταξύ σημείου και αντικειμένου, την ανίχνευση ακμών, τη μέτρηση περιμέτρου και επιφάνειας αντικειμένου. Την υλοποίηση λογικών πράξεων μεταξύ ομάδων και εικόνων. Για την εκτέλεση των λογικών πράξεων ανάμεσα στις ομάδες των εικόνων χρησιμοποιείται ο τελεστής διαφοράς συνόλων ως βοηθητικός τελεστής για την εκτέλεση των τελεστών OR, XOR και NOT. Τον υπολογισμό των στατιστικών ροπών σε πραγματικό χρόνο. Οι ροπές αυτές χρησιμοποιούνται για διάφορες εργασίες ανάλυσης εικόνων, αναγνώρισης αντικειμένων, ταίριασμα σκηνών κ.λπ. Ο υπολογισμός τους όμως απαιτεί μεγάλο υπολογιστικό κόστος. Σε δυαδικές εικόνες που αναπαριστώνται με ομάδες, η εκμετάλλευση της ορθογώνιας μορφής της ομάδας οδηγεί σε δραστική μείωση της απαιτούμενης υπολογιστικής πολυπλοκότητας, σε σημείο τέτοιο ώστε να είναι δυνατή η επεξεργασία με ρυθμό μεγαλύτερο από 50 εικόνων/sec σε σειριακό προσωπικό υπολογιστή χαμηλού κόστους, δηλαδή σε πραγματικό χρόνο. Την αναπαράσταση δυαδικών εικόνων με ομάδες καθώς και τον υπολογισμό των ροπών σε πραγματικό χρόνο, στην παράλληλη αρχιτεκτονική Scan Line Array Processor (SLAP). Το SLAP είναι ένας γραμμικός πίνακας Ν επεξεργαστών που έχει χρησιμοποιηθεί για εφαρμογές επεξεργασίας εικόνας. Όλα τα στοιχεία επεξεργασίας λειτουργούν ταυτόχρονα με SIMD (Single Instruction Multiple Data) τρόπο. Επίσης παρουσιάζονται δύο γρήγοροι αλγόριθμοι για τον υπολογισμό των γεωμετρικών ροπών σε πολυτονικές εικόνες. Ο ένας αλγόριθμος υπολογίζει με ακρίβεια τις ροπές ενώ ταυτόχρονα απαιτεί υποπολλαπλάσιο χρόνο υπολογισμού σε σχέση με τον κλασσικό τρόπο υπολογισμού των ροπών. Ο δεύτερος αλγόριθμος υπολογίζει προσεγγιστικά τις τιμές των ροπών, αλλά με μικρό σφάλμα της τάξης του 2-3% που δεν επηρεάζει σημαντικά τη διαδικασία αναγνώρισης αντικειμένων και ταυτόχρονα υλοποιείται σε πραγματικό χρόνο, επιτρέποντας ρυθμό εισόδου εικόνων μεγαλύτερο από 30 εικόνες/sec σε σειριακό προσωπικό υπολογιστή χαμηλού κόστους. Τη λέπτυνση και τον υπολογισμό του σκελετού αντικειμένων. Ο σκελετός των αντικειμένων παρέχει χρήσιμη πληροφορία για τη μορφή επιμηκυμένων κυρίως αντικειμένων, ενώ επιπρόσθετα η πληροφορία αυτή μπορεί να θεωρηθεί ανεξάρτητη από το θόρυβο και το μέγεθος του αντικειμένου. Στην παρούσα διατριβή παρουσιάζονται δύο αλγόριθμοι λέπτυνσης αντικειμένων. Επίσης παρουσιάζονται κάποιες εφαρμογές των παραπάνω αλγορίθμων.