No description available.

In the present thesis, a novel gridding technique, as well as, two new segmentation methods applied to complementary DNA (cDNA) microarray images is proposed. More precise, a new gridding method based on continuous wavelet transform (CWT) was performed. Line profiles of x and y axis were calculated, resulting to 2 different signals. These signals were independently processed by means of CWT at 15 different levels, using daubechies 4 mother wavelet. A summation, point by point, was performed on the processed signals, in order to suppress noise and enhance spot’s differences. Additionally, a wavelet based hard thresholding filter was applied to each signal for the task of alleviating the noise of the signals. 10 real microarray images were used in order to visually assess the performance of our gridding method. Each microarray image contained 4 sub-arrays, each sub-array 40x40 spots, thus, 6400 spots totally. According to our results, the accuracy of our algorithm was 98% in all 10 images and in all spots. Additionally, processing time was less than 3 sec on a 1024×1024×16 microarray image, rendering the method a promising technique for an efficient and fully automatic gridding processing. Following the gridding process, the Gaussian Mixture Model (GMM) and the Fuzzy GMM algorithms were applied to each cell, with the purpose of discriminating foreground from background. In addition, markov random field (MRF), as well as, a proposed wavelet based MRF model (SMRF) were implemented. The segmentation abilities of all the algorithms were evaluated by means of the segmentation matching factor (SMF), the Coefficient of Determination (r2), and the concordance correlation (pc). Indirect accuracy performances were also tested on the experimental images by means of the Mean Absolute Error (MAE) and the Coefficient of Variation (CV). In the latter case, SPOT and SCANALYZE software results were also tested. In the former case, SMRF attained the best SMF, r2, and pc (92.66%, 0.923, and 0.88, respectively) scores, whereas, in the latter case scored MAE and CV, 497 and 0.88, respectively. The results and support the performance superiority of the SMRF algorithm in segmenting cDNA images. / Τα τελευταία χρόνια παρατηρείται ραγδαία ανάπτυξη της τεχνολογίας των μικροσυστοιχιών (microarrays) με αποτέλεσμα την ποιοτική και ποσοτική μέτρηση της έκφρασης χιλιάδων γονιδίων ταυτοχρόνως σ’ ένα και μόνο πείραμα. Εικόνες μικροσυστοιχιών, στις οποίες έχει λάβει χώρα υβριδοποίηση δείγματος DNA, χρησιμοποιούνται ευρέως για την εξαγωγή αξιόπιστων αποτελεσμάτων γονιδιακής έκφρασης και προσδιορισμό των μηχανισμών που ελέγχουν την ενεργοποίηση των γονιδίων σ’ έναν οργανισμό. Συνεπώς, η δημιουργία κατάλληλων υπολογιστικών τεχνικών για την επεξεργασία των εικόνων αυτών συντελεί καθοριστικά στην εξαγωγή ορθών και έγκυρων αποτελεσμάτων. Στη παρούσα Διδακτορική Διατριβή αναπτύχθηκε στο πρώτο στάδια μια νέα πλήρως αυτοματοποιημένη τεχνική διευθυνσιοδότησης και στο δεύτερο στάδιο δύο νέες τεχνικές τμηματοποίησης. Πιο συγκεκριμένα, αναπτύχθηκε μια νέα μέθοδος διευθυνσιοδότησης η οποία βασίζεται στο συνεχή μετασχηματισμό κυματιδίου (Continuous Wavelet Transform CWT) για την αυτόματη εύρεση των κέντρων των κηλίδων, καθώς και των ορίων μεταξύ δύο διαδοχικών κηλίδων. Στη συνέχεια αναπτύχθηκαν δύο νέες μέθοδοι κατάτμησης της εικόνας για τον διαχωρισμό των κηλίδων από το φόντο, οι οποίες βασίζονται στη τεχνική μίξης ασαφών μοντέλων Γκάους (Fuzzy Gaussian Mixture Models FGMM) καθώς και στη τεχνική συνδυασμού τυχαίων πεδίων Μαρκόφ (Markov Random Field MRF) και μετασχηματισμού κυματιδίου (Wavelet Transform WT) (SMRF). Με σκοπό την αξιολόγηση (validation) των προτεινόμενων μεθόδων της παρούσας Διδακτορικής Διατριβής, δημιουργήθηκαν και χρησιμοποιήθηκαν τόσο πραγματικές εικόνες μικροσυστοιχιών, καθώς και απομιμούμενες (simulated) σύμφωνα με μεθοδολογία η οποία προτείνεται απο τη διεθνή βιβλιογραφία. Όσον αφορά την διευθυνσιοδότηση, χρησιμοποιώντας οπτική ανασκόπηση για κάθε κηλίδα χωριστά σε όλες τις πραγματικές εικόνες, δημιουργήθηκαν δύο κατηγορίες, ανάλογα με το αν οι γραμμές του πλέγματος εφάπτονταν πάνω σε κάποια κηλίδα ή όχι. Η προτεινόμενη μεθοδολογία ήταν ακριβής σε ποσοστό 98% στον ακριβή εντοπισμό των κηλίδων σε όλες τις εικόνες. Σύγκριση ανάμεσα στην απόδοση των GMM, FGMM, MRF και SMRF στις απομιμούμενες εικόνες σε διαφορετικά επίπεδα θορύβου πραγματοποιήθηκε και τα αποτελέσματα σε όλα τα μετρικά, segmentation matching factor (SMF), coefficient of variation ( ), και coefficient of determination ( ), μας έδειξαν ότι η μέθοδος SMRF είναι πιο αξιόπιστη στο να μπορέσει να αναδείξει την πραγματική περιφέρεια της κηλίδας, τόσο σε εικόνες με μεγάλο λόγο σήματος προς θόρυβο, όσο και σε μικρό λόγο. Ενδεικτικά αποτελέσματα σε 1 db SNR για την περίπτωση του SMRF είναι SMF = 92.66, =0.923, και = 0.88, ακολουθούμενο από το MRF ( SMF = 92.15, =0.91, και = 0.85), FGMM ( SMF = 91.07, =0.92, και = 0.86)και GMM (SMF = 90.73, =0.89, και = 0.83). Στη συνέχεια πάρθηκαν αποτελέσματα τα οποία προέκυψαν από τη χρήση πραγματικών εικόνων μικροσυστοιχιών. Και σε αυτή τη περίπτωση, αναδείχθηκε η υπεροχή του WMRF, έναντι των άλλων αλγορίθμων ταξινόμησης μέση τιμή MAE = 497 και CV = 0.88. Τέλος, θα πρέπει να τονιστεί ότι τα παραπάνω μετρικά υπολογίστηκαν και σε αποτελέσματα από δύο ευρέως χρησιμοποιούμενα πακέτα επεξεργασίας εικόνων μικροσυστοιχιών, τα οποία χρησιμοποιούνται και είναι διαθέσιμα. Πιο συγκεκριμένα, χρησιμοποιήθηκαν το SCANALYSE και το SPOT, τα οποία χρησιμοποιούν τις τεχνικές τμηματοποίησης Fixed Circle και Seeded Region Growing, αντίστοιχα. Στη περίπτωση αυτή η τεχνική SMRF κατάφερε να υπολογίσει καλύτερα αποτελέσματα από τα δύο αυτά πακέτα. Πιο συγκεκριμένα η τεχνική GMM πέτυχε MAE = 1470 και CV = 1.29, η τεχνική FGMM πέτυχε MAE = 1430 και CV = 1.21, η τεχνική MRF πέτυχε MAE = 1215 και CV = 1.15, η τεχνική WMRF πέτυχε MAE = 497 και CV = 0.88, η τεχνική FC του λογισμικού πακέτου SCANALYZE πέτυχε MAE = 503 και CV = 0.90, και τέλος η τεχνική SRG του λογισμικού πακέτου SPOT πέτυχε MAE = 1180 και CV = 0.93.

Graph cuts have emerged as an important combinatorial optimization tool for many problems in vision. Most of the computer vision problems are discrete labeling problems. For example, in stereopsis, labels represent disparity and in image restoration, labels correspond to image intensities. Finding a good labeling involves optimization of an Energy Function. In computer vision, energy functions for discrete labeling problems can be elegantly formulated through Markov Random Field (MRF) based modeling and graph cut algorithms have been found to efficiently optimize wide class of such energy functions. The main contribution of this thesis lies in developing an efficient combinatorial optimization algorithm which can be applied to a wide class of energy functions. Generally, graph cut algorithms deal sequentially with each label in the labeling problem at hand. The time complexity of these algorithms increases linearly with number of labels. Our algorithm, finds a solution/labeling in logarithmic time complexity without compromising on quality of solution. In our work, we present an improved Logcut algorithm [24]. Logcut algorithm [24] deals with finding individual bit values in integer representation of labels. It has logarithmic time complexity, but requires training over data set. Our improved Logcut (Heuristic-Logcut or H-Logcut) algorithm eliminates the need for training and obtains comparable results in respect to original Logcut algorithm. Original Logcut algorithm cannot be initialized by a known labeling. We present a new algorithm, Sequential Bit Plane Correction (SBPC) which overcomes this drawback of Logcut algorithm. SBPC algorithm starts from a known labeling and individually corrects each bit of a label. This algorithm too has logarithmic time complexity. SBPC in combination with H-Logcut algorithm, further improves rate of convergence and quality of results. Finally, a hierarchical approach to graph cut optimization is used to further improve on rate of convergence of our algorithm. Generally, in a hierarchical approach first, a solution at coarser level is computed and then its result is used to initialize algorithm at a finer level. Here we have presented a novel way of initializing the algorithm at finer level through fusion move [25]. The SBPC and H-Logcut algorithms are extended to accommodate for hierarchical approach. It is found that this approach drastically improves the rate of convergence and attains a very low energy labeling. The effectiveness of our approach is demonstrated on stereopsis. It is found that the algorithm significantly out performs all existing algorithms in terms of quality of solution as well as rate of convergence.