Γρήγοροι αλγόριθμοι επεξεργασίας και ανάλυσης δυαδικών εικόνων

Abstract

In the present PhD thesis, a new binary image representation scheme, which is called Image Block Representation (IBR), is presented. This representation is a region representation method. In the Image Block Representation, the whole binary image is decomposed into a set of rectangular areas with object level, which are called blocks and have their edges parallel to the image axes. Each pixel of the image with object value belongs to one and only one block. The Image Block Representation is an information lossless process and therefore, from an information theory perspective, it is equivalent to the 2-D array image representation. In comparison with other region based representations schemes and specifically with the run length coding and the quadtree representation, the IBR is superior, since the number of the blocks is significantly smaller than the number of runs and the number of quadtree nodes with object level, respectively. As in every other region based method, the most important characteristic of the image block representation is that a perception of image parts greater than a pixel, is provided to the machine and therefore, all the operations on the pixels belonging to a block may be substituted by a simple operation on the block. Taking this feature into account, the implementation of new algorithms for binary image processing and analysis tasks, leads to substantial reduction of the required computational complexity. In this doctoral thesis, a number of basic image processing and analysis algorithms, which are implemented on block represented images are presented. These algorithms are characterized by low time complexity and are suitable for very fast processing rates, due to the substitution of image pixels by blocks. Specifically, these algorithms are: The fast implementation of the image shift, image scale, image rotation operations. The connected component labeling, operation that permits the detection of objects and the determination of the connectivity among image areas. The determination of the minimum and of the maximum distance from a point to an object, edge extraction, perimeter measurement and area measurement. The fast implementation of logic operations among blocks and images. The implementation of the Set Difference operator which is used as an auxiliary operator for the execution of the OR, XOR and NOT operations in block represented images is also presented. The real-time computation of statistical moments. Moments constitute a well-known tool for image analysis and have extensively used for pattern recognition tasks. However they suffer from a high computational cost. By exploiting the rectangular structure of the blocks, the moments computation with a rate greater than 50 fps (i.e. real-time) using a low cost serial computer, is achieved. The IBR process and the real-time moments computation on block represented binary images, using the parallel architecture Scan Line Array Processor (SLAP). SLAP is a linear array of N processors, operates in a SIMD (Single Instruction Multiple Data) mode and has been used for image processing tasks. Two fast algorithms for the moments computation on gray images. The first method provides the exact moment values and operates much faster than the conventional moment calculation and faster than other fast moment calculation technique. The second method provides approximated moment values, with small error of 2-3% and operates in real-time. The thinning and skeletonization of objects. The object’s skeleton provide useful information for its shape, which is also considered as independent from noise and from the scale of the object. Two thinning algorithms are presented in the thesis. Finally, some applications of the above algorithms are also presented.

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