Minimum yayılan ağaç tabanlı sıralı görüntü bölütleme
Minimum spanning tree-based sequential image segmentation
Yazar: ALİ SAĞLAM
Danışman: YRD. DOÇ. NURDAN BAYKAN
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Görüntü bölütleme = Image segmentation

Özet:
Bir görüntüyü belirli açılardan benzer piksellerden oluşan bölümlere (bölütlere) ayıran görüntü bölütleme (segmentasyon) işlemi görüntü işleme uygulamaları için çok önemli bir aşamadır. Görüntü bölütleme işlemi için birçok yöntem önerilmiştir. Graf tabanlı görüntü bölütleme de bu yöntemlerden birisidir.  Temsil gücü ve kullanım kolaylı gibi avantajlarından dolayı graflar birçok görüntü işleme çalışmasında önemli araçlar olarak sıklıkla kullanılmaktadır. Görüntü bölütleme ile veri kümeleme konuları birbirleriyle daima bağlantılı olmuşlardır. Birçok graf tabanlı görüntü bölütleme ve graf tabanlı veri kümeleme yöntemi içerisinde minimum yayılan ağaç (MYA) tabanlı yaklaşımlar, işlem kolaylığı ve düşük hesaplama karmaşıklığından dolayı kritik bir rol oynamaktadırlar.
Bu tez çalışmasında, ilk olarak, daha önceden literatürde sunulmuş bir algoritma olan, Prim'ın sıralı MYA temsili ile kümeleme algoritması görüntü bölütleme amacıyla gerçek görüntüler üzerinde uygulanmıştır. Bu algoritma ile bir veri kümesinin Prim algoritması ile çıkarılmış bütün bir MYA yapısının sıralı temsili taranmaktadır. Tarama sırasında MYA yapısı üzerindeki, hat kesme kriterini karşılayan uyumsuz hatlar belirlenerek ağaçtan çıkarılmakta (kesilmekte) ve bölütleme işlemi gerçekleşmektedir. Tez kapsamında ayrıca bu sıralı kümeleme algoritmasından geliştirilen bir metot önerilmiştir. Önerilen metoda göre, belirlenen uyumsuz hat kesildiği zaman oluşacak alt ağaçlar gürültü özelliğine sahip olacaksa bu hat kesilmemektedir. Böylece, algoritmanın sonunda ortaya çıkan bölütleme çıktısı, işlem sonrasında ortaya çıkabilecek ve gürültü olarak tanımlanabilecek istenmeyen küçük parçacıkları yok etmek için herhangi bir ek işleme gerek duymamaktadır. Uyumsuz hatların belirlenmesi için, uyarlanan sıralı kümeleme algoritmasında kullanılan kesme kriteri yerine, literatürden de faydalanılarak daha iyi sonuç veren ve farklı görüntü özelliklerine göre uyarlanabilen yeni bir karşılaştırma kriteri de tez kapsamında sunulmuştur. Son olarak önerilen metot gerçek görüntülerden oluşan veri setleri üzerinde test edilmiştir. Elde edilen sonuçlara göre, önerilen metot düşük işlem süresi ile en popüler görüntü bölütleme metotları ile doğruluk oranı açısından rekabet edebilecek düzeyde sonuçlar vermiştir. Test sonuçları görsel, grafiksel ve sayısal olarak tezin son bölümünde sunulmuştur.

Abstract:
The image segmentation process that separates an image to segments formed similar pixels in specific aspects is a very important stage for various image-processing applications. Many methods are proposed for the process of image segmentation. Graph-based image segmentation is also one of them. Due to their advantages such as representation convenience and ease of use, graphs are used as important tools in many image-processing studies. Image segmentation and data clustering issues are always been connected to each other. In many graph-based data clustering methods and many graph-based image segmentation methods, minimum spanning tree (MST)-based approaches play a crucial role due to ease of operation and low computational complexity.
In this thesis work, firstly, the algorithm of clustering with Prim's sequential representation of MST, which is proposed in the literature in advance, is applied on real images for the purpose of image segmentation. The sequential representation of the complete MST structure of a data set is scanned by the algorithm. During the scanning, the inconsistent edges on the MST structure, which satisfy the cut criterion, are removed from the tree (cut) and the segmentation is accomplished. In the scope of the thesis, additionally, a method improved from the sequential clustering algorithm is proposed. According to the proposed method, if the sub trees, which would occur when the determined inconsistent edge is cut, have the noise feature, this edge would not be cut. In this way, the output of the segmentation does not need to be done any post-processing for eliminating the undesired small particles, which might be emerged after the processing and can be defined as noise. For defining the inconsistent edges, instead of the cut criterion used in the data-clustering algorithm implemented, a novel comparison criterion, which performs better and can be adapted for images that have different features, is developed by benefiting from the literature. Finally, the proposed algorithm is tested on real image data sets. According to the results obtained, the proposed algorithm yields results at a level that it can challenge with the most popular image segmentation algorithms in terms of accuracy within low execution time. The results are showed in this thesis visually, graphically, and numerically.