Ομαδοποίηση εικόνων με βάση το περιεχόμενο.

Abstract

Ομαδοποίηση ή διαφορετικά “clustering” είναι η διαδικασία κατά την οποία δεδομένα κατατάσσονται σε σημασιολογικά σύμφωνες ομάδες (clusters) με βάση κάποιο μέτρο ομοιότητας. Η έννοια του “cluster” δεν μπορεί να οριστεί επακριβώς και αυτό είναι ένας απ’ τους λόγους που υπάρχουν πάρα πολλοί αλγόριθμοι ομαδοποίησης. Επίσης, δεν μπορούμε να πούμε ότι υπάρχει ένας αντικειμενικά “σωστός” αλγόριθμος που να εφαρμόζεται σε όλες τις περιπτώσεις. Οι βασικοί αλγόριθμοι ομαδοποίησης διακρίνονται σε τέσσερις κύριες κατηγορίες: τους Ιεραρχικούς Αλγόριθμους (Hierarchical Algorithms), τους Αλγόριθμους κ – κέντρου (k – means), τους Διαμεριστικούς ή Κατανεμημένους Αλγόριθμους (Distribution-based clustering) και τους Βασισμένους στην Πυκνότητα (Density-based clustering). Η ομαδοποίηση εικόνων αναφέρεται στο πρόβλημα εύρεσης της κατάλληλης αντιστοίχισης των εικόνων σε ομάδες (clusters) έτσι ώστε κάθε ομάδα να αποτελείται από εικόνες με όμοια χαρακτηριστικά. Οι τεχνικές ομαδοποίησης εικόνων μπορούν να χωριστούν σε δύο κύριες κατηγορίες, στις supervised τεχνικές οι οποίες χαρακτηρίζονται από την ανθρώπινη παρέμβαση και στις unsupervised τεχνικές. Όλες οι τεχνικές, όμως, ανεξαρτήτως κατηγορίας βασίζονται στις ομοιότητες μεταξύ των χαρακτηριστικών των εικόνων και στο πλήθος των ομάδων. Μια μορφή ομαδοποίησης εικόνων θεωρείτε και το πρόβλημα της ταξινόμησης – προσπέλασης των εικόνων μιας μεγάλης βάσης δεδομένων με βάση το περιεχόμενο, με το οποίο θα ασχοληθούμε εκτενώς στα πλαίσια της παρούσας εργασίας. Η ταξινόμηση των εικόνων με βάση το περιεχόμενο είναι στην ουσία η δημιουργία μιας διαδρομής που θα περνάει απ’ όλες της εικόνες μια μόνο φορά, με τέτοια σειρά ώστε η επόμενη από την προηγούμενη φωτογραφία να έχουν όμοιο περιεχόμενο. Το πρόβλημα αυτό μοιάζει πολύ με το πρόβλημα του “Πλανόδιου Πωλητή”, γνωστό στη βιβλιογραφία ως The Travelling Salesman Problem (TSP). Το πρόβλημα του “Πλανόδιου Πωλητή” (TSP) αναφέρεται στην εύρεση της ιδανικής και ελάχιστης διαδρομής για τον πλανόδιο πωλητή ο οποίος ξεκινώντας από την αφετηρία του, θα πρέπει να επισκεφθεί μια σειρά από πόλεις και έπειτα να επιστρέψει στην αρχική τοποθεσία έτσι ώστε η συνολική απόσταση του ταξιδιού του να είναι η ελάχιστη δυνατή και με περιορισμό να επισκεφθεί κάθε πόλη μια και μόνο φορά. Ένας από τους πρώτους αλγορίθμους που χρησιμοποιήθηκε για την επίλυση του TSP προβλήματος είναι ο αλγόριθμος του κοντινότερου γείτονα (NN algorithm). Μια άλλη ευριστική μέθοδος, επίσης, που αποδίδει καλές λύσεις στο πρόβλημα αυτό είναι η Ant Colony Optimization (ACO) η οποία χρησιμοποιεί μια προσομοίωση μιας αποικίας μυρμηγκιών και βασίζεται στη συμπεριφορά που παρατηρείτε σε πραγματικά μυρμήγκια να εντοπίζουν το συντομότερο μονοπάτι μεταξύ της εκάστοτε πηγής τροφής και της φωλιάς τους. Τέλος, μια άλλη κατηγορία αλγορίθμων που χρησιμοποιούνται ευρέως για την επίλυση τέτοιου τύπου προβλημάτων, είναι οι Γενετικοί Αλγόριθμοι που ανήκουν στην κατηγορία των μετάευρετικών (metaheuristic) αλγορίθμων και είναι εμπνευσμένοι από τη διαδικασία της φυσικής επιλογής η οποία ανήκει στην μεγαλύτερη κατηγορία των εξελικτικών αλγορίθμων (Evolutionary Algorithms – EA).

Clustering is the process by which data is classified into semantic clusters based on a measure of similarity. The meaning of "cluster" cannot be defined precisely and this is one of the reasons why there are too many clustering algorithms. Additionally, we cannot say that there is an objectively "correct" algorithm that applies in all cases. The main clustering algorithms are divided into four main categories: The Hierarchical Algorithms, The K – means Algorithms, The Distribution-based Clustering Algorithms and the Density-based Clustering Algorithms. Image Clustering refers to the problem of finding the appropriate match of clusters so that each cluster consists of images with similar characteristics. The techniques of image clustering can be divided into two main categories: the supervised techniques, which are characterized by human intervention and the unsupervised techniques. All techniques, however, regardless of category, are based on the similarities between the characteristics of the images and the number of clusters. A kind of image clustering is considered to be also the problem of classification/sorting of images of a large database, which will be dealt in detail in the present work. Content-based image sorting is the creation of a route that will pass through all of the images once, in such order that the next one from the previous photo has similar content. This problem resembles with the problem known in the literature as “The Traveling Salesman Problem” (TSP). The Travelling Salesman Problem (TSP) refers to the problem of finding the ideal and minimum route for the trader who, starting at his starting point, should visit a number of cities and then return to the original location so that the total distance of his trip is the minimum possible and with limitation to visit each city once. One of the first algorithms used in the TSP is the Nearest Neighbour algorithm. Another heuristic method that also provides good solutions to this problem is the Ant Colony Optimization (ACO), which uses a simulation of the ant colony and is based on the behaviour observed in real ants to trace the shortest path between the food source and their nest. Finally, another class of algorithms that are widely used to solve such type of problems are the Genetic Algorithms which belong to the category of metaheuristic algorithms and are inspired by the natural selection process that belongs to the larger category of Evolutionary Algorithms (EA).