Μέτρα ασαφούς υποσυνολότητας και εντροπίας και η εφαρμογή τους σε θέματα πληροφορικής

Abstract

This research concerns fuzzy inclusion and entropy measures and their use on image thresholding. It is composed of two basic parts which involve our theoretical study on these inclusion and entropy measures (first part) and our experimentations on their application on image binarization (second part). Fuzzy inclusion and entropy measurements are important to fuzzy set theory and they are used in a wide range of applications where fuzziness may be involved (e.g. fuzzy controllers, feature selection, fuzzy clustering, image processing). Several authors and researchers have dealt with such measures. Some of them have tried to axiomatize these indicators while others have introduced such measures based on specific desired properties. Significant results have been obtained; results that have led to several alternative approaches and solutions of various problems. Apart from these interesting and innovative ideas, in these studies, open matters of further discussion and research have occurred as well. In the theoretical part of our research we tried to produce new possible fuzzy inclusion measures based on a specific formula. These indicators are formed by using in our formula binary operations on [0,1] and they include some already known and widely used measures. At the same time, we tried to subsume these inclusion and entropy measures to a more general theoretical context by setting specific rules in order for them to satisfy an axiomatic base. The axiomatization we followed, concerning fuzzy inclusion, was Young’s (1996) axiomatization. Young was skeptical about Sihna and Dougherty’s (1993) axioms and tried to include these measures in the context of Kosko’s (1986, 1990, 1992, 1993) general research. Her axiomatic properties were chosen so that a specific theorem, which connects fuzzy inclusion measures with fuzzy entropy measures, could be valid. According to this theorem, the latter are directly produced by the former by using a specific math formula. The binary operations which we used in our formula were the usual fuzzy intersections (t-norms) along with the most common fuzzy implications. This was mainly because we wanted a connection and a consistency with crisp logic. However, this doesn’t mean that we are restricted to these operations since we saw that our formula is still effective while being used with other binary operations on [0,1] as well. As far as fuzzy intersections and implications are concerned, the initial difficulty in our study lay in finding such proper couples (intersection – implication) which could return new fuzzy inclusion measures satisfying Young’s axioms. In fact, what we obtained was only Kosko’s measures. Then we observed that this was due to a certain part of Young’s third axiom which was stricter than needed in the context in which it was proposed. By “loosing” this specific part (in two phases) and reformulating our propositions, we were able to produce several new possible fuzzy inclusion indicators. This interference didn’t invalidate Young’s theorem which means that these measures returned their respective entropy measures as well. While we were studying these indicators and their behavior in fuzzy measurements, we observed that they have – at least some of them – some very interesting (or even unique) attributes. Our next step was towards the evaluation of the reliability of these measures and their capability of being used in specific applications.We believe that these measures could be used in applications which require or properly exploit fuzzy inclusion and entropy measurements. Possibly they could offer us more information or lead to alternative ways of solving specific problems of these areas of research. In order to support these arguments, during the second part of this research, we introduce an open, general and adaptive method of global and local image thresholding which effectively uses some of these measures. Image thresholding or image binarization deals with its foreground – background segmentation by turning the image into binary and it’s the first step of many advanced techniques of image processing or computer vision processes. This may look like a simple procedure, but in fact, it is a difficult problem – considering the vast variety of images of different characteristics – whose research is still open despite the large number of techniques which have been proposed. Our proposition significantly varies from the usual thresholding methods and it always (regardless of our input) relies on specific measurements obtained by our fuzzy inclusion and entropy measures. As far as global thresholding is concerned (here our image is binarized using a single threshold), our method doesn’t depend on histogram analysis nor does it rely on optimizing some statistical measure (e.g. variance minimization) of the gray – level information. It only needs specific attributes of the image which are measured by some of our fuzzy inclusion and entropy indicators. These attributes can be connected with the proper threshold mathematically (e.g. using some proper function) or automatically (e.g. using some neuro – fuzzy network). It’s more of an open and adjustable process than a strict mathematical method which can be easily adapted to the demands of different domains or fields of research. So, our transition to local thresholding was immediate. Local thresholding methods calculate a different threshold for each pixel based on the information of its adjoining pixels and they are used in cases of “difficult” images where global thresholding is inadequate. They are far more complicated and they demand more attention during their development and their testing. Our main area of interest, regarding local thresholding, were degraded or unevenly illuminated document images. The recognition of the content of such images is often achieved through their binarization and it’s fundamental for document analysis systems or OCR (Optical Character Recognition) processes. This doesn’t mean that we didn’t experiment with other categories of images as well, seizing on the flexibility of our method. During our experimentations, we tried to maintain the automatic character of our method by avoiding any sensitivity or bias parameters.The results of our algorithms on global and local thresholding were very encouraging and led us to the conclusion that our fuzzy inclusion – entropy measurements are definitely connected with the threshold of the image. This drove us to our most recent part of our research which includes the automatic thresholding of an image using a corresponding ANFIS (Adaptive Neuro – Fuzzy Inference System). These systems were trained with the aid of our measures and they returned a lot of good and promising results during their testing on global and local thresholding. This way, our work is led to a new level and we believe that in the long term and after much additional study and experimentation, we will have some safe and definite propositions which will become a constitutive and useful part of this field of research. All of these would be much easier if there were corresponding, specialized databases of the form image – proper threshold, however, at this point we are obligated to collect our own essential data in order to proceed to our experimentations. Of course, something like this demands a whole lot of time and study. So, this thesis is separated in nine chapters and our research is divided in two basic parts. The first four chapters are introductory and they contain information and preliminaries concerning fuzzy logic area and fuzzy systems as well as image binarization. Chapter 5 is about our aforementioned theoretical study while chapters 6, 7 and 8 contain our algorithms and experimental results on image thresholding. Chapters 6 and 7 are about our inquiry for proper math functions which connect our measures with the desired threshold while chapter 8 contains our conclusions of the automatic connection achieved with ANFIS. In chapter 9, which is our conclusion, besides the summary of this thesis, we also include the most important aspects of our future research concerning image thresholding and fuzzy inclusion and entropy measures. Finally, there, we also mention further applications which could possibly use our measures as well as various studies which could be linked or even incorporated with ours.

Η παρούσα έρευνα σχετίζεται με τις συναρτήσεις μέτρησης της ασαφούς υποσυνολότητας και εντροπίας και την χρήση τους σε προβλήματα κατωφλίωσης εικόνας (image thresholding). Αποτελείται από δύο κυρίως μέρη τα οποία περιλαμβάνουν την θεωρητική μας έρευνα πάνω στα μέτρα υποσυνολότητας και εντροπίας (πρώτο μέρος) και τους πειραματισμούς μας σχετικά με την χρήση τους σε προβλήματα δυαδικοποίησης εικόνων (δεύτερο μέρος). Οι μετρήσεις υποσυνολότητας και εντροπίας των ασαφών συνόλων είναι σημαντικές για το πεδίο της ασαφούς λογικής και χρησιμοποιούνται σε ένα ευρύ φάσμα εφαρμογών που μπορεί να περιλαμβάνουν ασάφεια (π.χ. ασαφείς ελεγκτές – fuzzy controllers, επιλογή χαρακτηριστικών – feature selection, ασαφής ομαδοποίηση – fuzzy clustering, επεξεργασία εικόνας – image processing). Διάφοροι συγγραφείς και ερευνητές έχουν ασχοληθεί με τα μέτρα αυτά. Κάποιοι από αυτούς επιχειρήσαν να εντάξουν τα μέτρα αυτά σε ένα πιθανό αξιωματικό πλαίσιο ενώ άλλοι εισήγαγαν ανάλογα μέτρα βασιζόμενοι σε συγκεκριμένες επιθυμητές ιδιότητες. Όλη αυτή η έρευνα απέφερε σημαντικά αποτελέσματα τα οποία οδήγησαν σε αρκετές εναλλακτικές προσεγγίσεις και λύσεις μιας ποικιλίας προβλημάτων. Πέρα όμως από αυτές τις ενδιαφέρουσες και καινοτόμες ιδέες, σε αυτές τις εργασίες προέκυψαν και πολλά ζητήματα ανοιχτά για περαιτέρω συζήτηση και έρευνα. Σε ότι αφορά το θεωρητικό κομμάτι της έρευνας μας, προσπαθήσαμε να κατασκευάσουμε νέους πιθανούς δείκτες της ασαφούς υποσυνολότητας με βάση έναν συγκεκριμένο τύπο – φόρμουλα. Ο δείκτες αυτοί σχηματίζονται χρησιμοποιώντας στον τύπο αυτό δυαδικές πράξεις του διαστήματος [0,1] και περιλαμβάνουν ακόμα και κάποια ήδη γνωστά και χρησιμοποιούμενα μέτρα. Ταυτόχρονα όμως προσπαθήσαμε να εντάξουμε τις συναρτήσεις αυτές και σε ένα ευρύτερο θεωρητικό πλαίσιο ορίζοντας συγκεκριμένες συνθήκες προκειμένου να ικανοποιούν μια βάση αξιωμάτων. Η αξιωματική λογική που ακολουθήσαμε, σε ότι αφορά την ασαφή υποσυνολότητα, είναι αυτή της Young (1996) η οποία αντιμετώπισε με σκεπτικισμό τα αξιώματα των Sihna and Dougherty (1993) και προσπάθησε να εντάξει τους δείκτες αυτούς στα πλαίσια της γενικότερης έρευνας του Kosko (1986, 1990, 1992, 1993). Οι ιδιότητες – αξιώματα που έθεσε επελέγησαν προκειμένου να ικανοποιείται ένα συγκεκριμένο θεώρημα σύνδεσης των μέτρων ασαφούς υποσυνολότητας με τα μέτρα ασαφούς εντοπίας. Με βάση το θεώρημα αυτό, τα δεύτερα παράγονται απ’ ευθείας από τα πρώτα με χρήση μιας συγκεκριμένης μαθηματικής φόρμουλας. Οι δυαδικές πράξεις που χρησιμοποιήσαμε στον γενικό μας τύπο είναι οι βασικές ασαφείς τομές (fuzzy intersections ή t – norms) και οι συνήθεις ασαφείς συνεπαγωγές (fuzzy implications). Αυτό έγινε, σε πρώτη φάση, επιχειρώντας μια σύνδεση και μια «συνέπεια» με την κλασσική λογική. Δεν σημαίνει όμως ότι κάτι τέτοιο είναι και δεσμευτικό αφού όπως είδαμε ο τύπος μας «λειτουργεί» και με άλλες δυαδικές πράξεις του [0,1] γενικότερα. Επιστρέφοντας στις ασαφείς τομές και συνεπαγωγές, η δυσκολία που αντιμετωπίσαμε αρχικά βρισκόταν στην εύρεση κατάλληλων τέτοιων ζευγών (τομή – συνεπαγωγή) που θα μας επέστρεφαν καινούργια μέτρα υποσυνολότητας που ικανοποιούν τα αξιώματα Young. Ουσιαστικά μπορέσαμε να πάρουμε ως αποτέλεσμα μόνο τον δείκτη Kosko. Παρατηρώντας όμως ότι αυτό συμβαίνει λόγω ενός μέρους του τρίτου αξιώματος Young το οποίο ήταν περισσότερο δεσμευτικό από ότι χρειάζεται ώστε να ισχύει η λογική με την οποία αυτό συντάχθηκε, καταφέραμε μετά την χαλάρωση του (σε δύο φάσεις) και την επαναδιατύπωση των προτάσεων μας να παραγάγουμε αρκετούς νέους πιθανούς δείκτες ασαφούς υποσυνολότητας. Η παρέμβαση αυτή δεν ακύρωσε το θεώρημα Young και αυτό σημαίνει ότι αυτοί επιστρέψαν και τα αντίστοιχα μέτρα εντροπίας. Μελετώντας τα μέτρα αυτά και την συμπεριφορά τους στις ασαφείς μετρήσεις, παρατηρήσαμε ότι παρουσιάζουν – έστω κάποια από αυτά – μερικές ενδιαφέρουσες (ή και μοναδικές) ιδιότητες. Το επόμενο μας βήμα αφορούσε τον έλεγχο της αξιοπιστίας των μέτρων αυτών καθώς και την καταλληλότητα τους για χρήση σε συγκεκριμένες εφαρμογές. Πιστεύουμε ότι οι δείκτες αυτοί μπορούν να χρησιμοποιηθούν στην επίλυση προβλημάτων που απαιτούν ή εκμεταλλεύονται κατάλληλα μετρήσεις ασαφούς υποσυνολότητας και εντροπίας. Πεποίθηση μας είναι ακόμα ότι θα μπορούσαν να προσφέρουν περισσότερη και κατάλληλη «πληροφορία» και να οδηγήσουν σε εναλλακτικές μεθόδους αντιμετώπισης προβλημάτων αυτού του ερευνητικού πεδίου. Προκειμένου να στηρίξουμε την πίστη μας και αυτά μας τα επιχειρήματα, στο δεύτερο κομμάτι της παρούσας έρευνας (το «πρακτικό») εισάγουμε μια γενική, ανοιχτή και προσαρμοστική μέθοδο κατωφλίωσης εικόνων τόσο σε καθολικό όσο και σε τοπικό επίπεδο, η οποία χρησιμοποιεί αποτελεσματικά κάποια από τα μέτρα μας. Η κατωφλίωση ή δυαδικοποίηση εικόνας αφορά τον διαχωρισμό προσκηνίου – παρασκηνίου μιας εικόνας με την μετατροπή της σε δυαδική και αποτελεί το εισαγωγικό βήμα πολλών άλλων πιο εξειδικευμένων τεχνικών στον χώρο της επεξεργασίας εικόνας ή της μηχανικής οπτικής (computer vision). Παρότι φαντάζει ως μια απλή διαδικασία, στην πραγματικότητα είναι ένα δύσκολο πρόβλημα – αν αναλογιστούμε την τεράστια ποικιλία εικόνων διαφορετικών χαρακτηριστικών που υπάρχει – το οποίο είναι ακόμα ανοιχτό στην έρευνα παρά το πλήθος των τεχνικών που έχουν κατά καιρούς προταθεί. Η πρόταση μας διαφέρει σημαντικά από τις γνωστές μεθόδους κατωφλίωσης και στηρίζεται ουσιαστικά και πάντα (ανεξαρτήτως της εικόνας που «δουλεύουμε») σε συγκεκριμένες μετρήσεις των μέτρων μας ασαφούς υποσυνολότητας και εντροπίας. Σχετικά με την καθολική κατωφλίωση (κατά την οποία όλη η εικόνα δυαδικοποιείται με βάση ένα συγκεκριμένο κατώφλι), η μέθοδος μας δεν χρησιμοποιεί την μορφή του ιστογράμματος της εικόνας ούτε στηρίζεται στην βελτιστοποίηση στατιστικών μέτρων (π.χ. ελαχιστοποίηση της διακύμανσης) της ασπρόμαυρης (gray – level) πληροφορίας. Απαιτεί μόνο την γνώση συγκεκριμένων ιδιοτήτων της εικόνας μετρημένων από κάποια από τα μέτρα μας, οι οποίες μπορούν να συνδεθούν με το κατάλληλο σημείο κατωφλίωσης είτε μαθηματικά (π.χ. με κάποια συνάρτηση) είτε αυτοματοποιημένα (π.χ. με κάποιο νεύρο – ασαφές δίκτυο). Πρόκειται περισσότερο για μια ανοιχτή και προσαρμόσιμη διαδικασία παρά για μια αυστηρή μαθηματική μέθοδο, η οποία μπορεί εύκολα να τροποποιηθεί ή να παραλλαχθεί ώστε να ικανοποιήσει τις ανάγκες και απαιτήσεις διαφορετικών πεδίων ή ερευνητικών κλάδων. Μετά από αυτό, η μετάβαση μας στο πεδίο της τοπικής κατωφλίωσης είναι «φυσική» και άμεση. Η τοπική κατωφλίωση υπολογίζει ένα διαφορετικό κατώφλι για κάθε εικονοστοιχείο (pixel) της εικόνας ξεχωριστά με βάση την πληροφορία από τα γειτονικά του εικονοστοιχεία και χρησιμοποιείται σε περιπτώσεις «δύσκολων» εικόνων όπου η καθολική κατωφλίωση δεν επαρκεί. Είναι σίγουρα πιο περίπλοκη και απαιτεί πολύ περισσότερη προσοχή κατά την ανάπτυξη αλλά και τον έλεγχο των ανάλογων τεχνικών της. Το κύριο πεδίο της έρευνας μας στην τοπική κατωφλίωση ήταν «υποβαθμισμένες» ή ανομοιογενώς φωτισμένες εικόνες εγγράφων. Η αναγνώριση του περιεχομένου τέτοιων εικόνων επιτυγχάνεται σε μεγάλο βαθμό μέσω της δυαδικοποίησης τους και είναι σημαντική για τα συστήματα ανάλυσης εγγράφων ή για τις διαδικασίες οπτικής αναγνώρισης χαρακτήρων. Αυτό δεν σημαίνει ότι δεν πειραματιστήκαμε και σε άλλου είδους εικόνες αφού μας το επιτρέπει εύκολα η ευελιξία της μεθόδου μας. Καθ’ όλη την διάρκεια των πειραματισμών μας προσπαθήσαμε η τεχνική μας να παραμείνει αυτοματοποιημένη και απαλλαγμένη από την χρήση μεταβλητών ευαισθησίας ή μεροληψίας. Τα αποτελέσματα των αλγορίθμων μας τόσο στην καθολική όσο και στην τοπική κατωφλίωση ήταν πολύ ενθαρρυντικά και μας οδήγησαν στο συμπέρασμα ότι πράγματι υφίσταται η σύνδεση μεταξύ μετρήσεων υποσυνολότητας – εντροπίας και κατωφλίου. Αυτό μας οδήγησε στο τελευταίο και πιο πρόσφατο κομμάτι της έρευνας μας το οποίο περιλαμβάνει την αυτοματικοποιημένη δυαδικοποίηση εικόνας με χρήση ενός αντίστοιχου ANFIS (Adaptive Neuro – Fuzzy Inference System). Η εκπαίδευση των σχετικών ANFIS γίνεται με την βοήθεια των μετρήσεων από τους δείκτες μας και κατά την αξιολόγηση τους στην καθολική και τοπική κατωφλίωση πήραμε πολλά καλά και ενθαρρυντικά αποτελέσματα. Έτσι, η όλη μας δουλειά οδηγείται σε ένα νέο επίπεδο και πιστεύουμε ότι σε βάθος χρόνου και μετά από επιπλέον έρευνα και πειραματισμό, θα έχουμε κάποιες πολύ ασφαλείς και αδιαμφισβήτητες προτάσεις οι οποίες θα γίνουν βασικό και χρήσιμο κομμάτι της όλης σχετικής έρευνας. Όλα αυτά θα ήταν πολύ πιο εύκολα αν υπήρχαν σχετικές, εξειδικευμένες βάσεις δεδομένων του τύπου εικόνα – κατάλληλο σημείο κατωφλίωσης, παρόλα αυτά στη φάση αυτή είμαστε αναγκασμένοι να συγκεντρώνουμε μόνοι μας τα απαραίτητα στοιχεία προκειμένου να προβούμε στους ανάλογους πειραματισμούς. Όλο αυτό απαιτεί πολύ χρόνο και αναζήτηση. Η διατριβή αυτή λοιπόν αποτελείται από εννέα κεφάλαια και η έρευνα μας χωρίζεται σε δύο βασικά μέρη. Τα πρώτα τέσσερα κεφάλαια είναι εισαγωγικά και περιλαμβάνουν πληροφορίες και προαπαιτούμενα από τον χώρο της ασαφούς λογικής και των ασαφών συστημάτων καθώς και από τον χώρο της δυαδικοποίησης εικόνας. Το κεφάλαιο 5 σχετίζεται με την προαναφερθείσα θεωρητική μας έρευνα ενώ τα κεφάλαια 6, 7, 8 περιλαμβάνουν τους αλγορίθμους και τα αποτελέσματα μας από τους πειραματισμούς μας πάνω στην κατωφλίωση. Τα κεφάλαια 6 και 7 αφορούν την έρευνα μέσω αναζήτησης κατάλληλων μαθηματικών συναρτήσεων σύνδεσης των μέτρων μας με το κατάλληλο κατώφλι ενώ το κεφάλαιο 8 περιλαμβάνει τα συμπεράσματα μας από την αυτοματοποιημένη σύνδεση μέσω ANFIS. Στο κεφάλαιο 9, το οποίο αποτελεί τον επίλογο μας, πέρα από την ανακεφαλαίωση της διατριβής αυτής περιλαμβάνονται και οι κυριότεροι άξονες της μελλοντικής μας αναζήτησης και έρευνας τόσο στην κατωφλίωση εικόνας όσο και στα μέτρα ασαφούς υποσυνολότητας και εντροπίας. Τέλος, εκεί αναφέρουμε και άλλες εφαρμογές στις οποίες θα μπορούσαν να χρησιμοποιηθούν αλλά και διάφορες έρευνες οι οποίες θα μπορούσαν να συνδεθούν ή ακόμα και να ενσωματωθούν με τη δική μας.