Tez No	İndirme	Tez Künye	Durumu
100808		Color image segmentation: Multithresholding and constraint satisfaction methods / Renkli imge bölütleme: Çoklueşikleme ve kısıt sağlama metodları Yazar:FATİH KURUGÖLLÜ Danışman: PROF. DR. A. EMRE HARMANCI Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Bölütleme = Segmentation ; Görüntü bölütleme = Image segmentation ; Kısıt sağlama = Constraint satisfaction ; Çoklu eşikleme = Multi-thresholding	Onaylandı Doktora İngilizce 2000 172 s.
imge bölütleme verilen bir imgeyi belli bir tekdüzelik kriterine göre homojen bölgelere ayırma sürecidir. Bölütleme bir çok imge çözümleme uygulamasında kullanılır. Bölütlemenin başarımı çözümlemede kendisini izleyen adımların başarımını doğrudan etkilediğinden uygulamanın istenen başarımı, bölütleme evresinin başarımına sıkı bir şekilde bağlıdır. Dolayısıyla bölütlemenin imge çözümlemenin en kritik evresi olduğunu söylemek yanlış olmaz. Bölütleme yöntemleri kabaca iki ana gruba ayrılabilir: Probleme yönelik yöntemler ve genel-geçer yöntemler. Probleme yönelik yöntemler verilen problemin doğasına ve bazı önsel bilgilere göre geliştirilirken genel-geçer yöntemler bölütlemeyi sahne hakkında herhangi bir önsel bilgi olmadan yerine getirmeyi amaçlar. Bu nedenle genel-geçer yöntemler daha çok buluşsal ve sezgisel yaklaşımlara dayanır. Genel- geçer yöntemler, bölge tabanlı, sınır tabanlı, ölçüm uzayı tabanlı ve melez yöntemler olmak üzere dört alt gruba ayrılabilir. Bölge tabanlı yöntemler bölge içindeki piksellerin benzerliğini temel alırken sınır tabanlı yöntemler bölgeler arasındaki süreksizliği sezmeyi temel alırlar. Ölçüm uzayı tabanlı yöntemler ise bölütlemeyi uzamsal kısıtları göz ardı ederek ölçüm uzayında gerçekleştirirler. Melez yöntemler yukarıdaki üç yaklaşımın herhangi bir kombinasyonunu kullanır. Bölütlemede önemli bir problem bölütlemenin değerlendirilmesi ve bölütleme başarımının sıralanmasıdır. Değerlendirme ve sıralama kriterleri çeşitli yöntemlerden belli bir uygulama için en iyi başarım gösteren yöntemi seçmede kullanılabilir. Öte yandan birçok bölütleme yöntemi bazı önsel parametre ayarı gerektirmektedir. Bölütleme sonucu bu parametre ayarına bağlı olmaktadır. Verilen bir uygulama için en doğru parametre seçimi, değerlendirme kriteri ile yapılabilir. Değerlendirme kriterinin diğer önemli bir kullanım alanı geribeslemeli image analizidir. Bu tip uygulamalarda sürecin her adımında imge bölütleme sonucu değerlendirilir ve gerekli parametre ve strateji değişiklikleri bu değerlendirmeye göre yapılır. Burada sonucun nicel değerlendirilmesi anahtar rol oynamaktadır. Bu tezde XVIIsınıflama hatasını ve şekil bozukluklarını birleştiren yeni bir değerlendirme yöntemi önerilmiştir. Herhangi bir deneysel değerlendirme yöntemi sınıflama hatasını ve şekil bozulmalarını nicel olarak ölçmelidir. Daha açıkça, değerlendirme yöntemi uzamsal olarak dayanak haritasıyla daha iyi örtüşen ve şekil olarak referansa daha yakın ~~bütütter üreten bir algoritmaya daha fazla puan vermelidir. Bu tezde Yasnoff et.al. (1977) da önerilen sınıflama hatası ölçütü sınıflama hatasını değerlendirmede kullanılırken, şekil bozulmaları için nesnelerin dönme açısına dayalı yeni bir yöntem önerilmiştir. Dönme açısı işlevi nesnelerin şekil karakteristiğini yansıtmaktadır. Dönme açısı ve sınıflama hatası kimi durumlarda birbirini tamamlayıcı özelliğe sahiptir. Sınıflama hatası ölçütü doğru sınıflamayı sezmede başarılı olurken şekil bozulmalarını ortaya çıkaramamaktadır. Dönme açısı ölçütü ise şekil bozulmalarını başarılı bir şekilde sezerken sınıflama başarımını göz ardı etmektedir. Dolayısıyla bu iki ölçütün birleştirilmesiyle elde edilecek yeni bir ölçüt, hem sınıflama hatasını hem de şekil bozulmalarını göz önüne almaktadır. Bu tezde her iki ölçüt Minkowski toplamı ile birleştirilerek bölütlemenin değerlendirilmesinde kullanılabilecek yeni bir kriter önerilmiştir, önerilen kriteri değişik algoritmaların başarımını sıralamada kullanmak için bir dizi test imgesine de gerek vardır. Bu amaçla bazı koşulları otomatik olarak sağlayan bir test imge üretme yordamı da geliştirilmiştir. Bölütlemedeki diğer ilginç bir problem de renkli imgelerin çoklu-eşiklenmesidir. Çoklu-eşikleme imge histogramma dayalı oldukça basit ve sıkça başvurulan bir bölütleme yöntemidir. Gri tonlu imgeler üzerinde çoklu- eşiklemeyi gerçekleştiren bir çok yöntem mevcuttur. Ancak renkli imgeler için çoklu- eşikleme renk histogramının üç boyutlu olması nedeniyle aynı kolaylıkla kullanılamamaktadır. Bu tezde renkli imgeler için iki boyutlu renk histogramlarına ve tümleştirmeye dayalı yeni bir çoklu-eşikleme yöntemi önerilmiştir. Bu yöntemde renk bileşenleri ikişer ikişer eşlenerek her bir renk bileşen çifti için iki boyutlu histogramlar oluşturulur. Bu iki boyutlu histogramlar, eşik yüzeyleri oluşturmak amacıyla doruklarına göre bölüntülenir. Her bir bileşen çifti, ilgili bölümlenmiş iki boyutlu histogramdaki eşik yüzeylerine göre bölütlenir. Elde edilen üç bölüt haritası etiket uyumlaştırma ve bir tümleştirme yöntemi ile birleştirilerek sonuç bölütleme haritası elde edilir. Ortaya çıkabilecek küçük bölütleri yok etmek için sonuç bölütleme haritası morfolojik kapama süzgeci ile süzgeçlenir. önerilen yöntem bir boyutlu ve üç boyutlu histograma dayalı eşdeğer yöntemler ile karşılaştırılmıştır. Bir boyutlu yöntemde ortaya çıkan tek renk geçişi ile oluşan bölütlerin kaybolması problemi önerilen yöntemle giderilmiştir, önerilen yöntemin yürütüm süresinin, bir boyutlu yöntemin yürütüm süresinin sadece iki katı olduğu gözlenmiştir, öte yandan üç boyutlu histograma dayalı yöntem doğası gereği önerilen yönteme göre biraz daha iyi sonuçlar üretmesine rağmen yürütüm süresi iki boyutlu yönteme göre yaklaşık XVIIIdörtyüz kat daha fazla olmaktadır. Sonuçta iki boyutlu histograma dayalı yöntem bir boyutlu eşdeğerine göre daha iyi başarıma sahip, üç boyutlu eşdeğerine göre ise işlemsel olarak daha etkin bir bölütleme yöntemi sunmaktadır. Bil tezde ölçüm uzayında topaklama ve imge uzayında gevşeme işlemlerini bir yapay sinir ağı mimarisinde birleştirerek bir arada kullanan Kısıt Sağlayan Yapay Sinir Ağı (KSYSA) da irdelenmiştir. KSYSA istenen kısıtları gerçekleştiren basit mimarisi nedeniyle bölütleme için etkin bir araç sağlamaktadır. KSYSA aslında kısıt sağlama problemine yapay sinir ağı çözümü getirmek için tasarlanmış olmasına rağmen olasılıksal gevşeme yöntemine dayalı bir bölütleme yöntemi olarak da yorumlanabilmektedir. Yöntemin bir dizi olumsuzlukları vardır. Bunlar i) Bölüt sayısının algoritmaya önceden verilmesi zorunluluğu ii) Sadece gri tonlu imgelerde kullanılmak üzere tasarlanmış olması iii) Önerilen yapay sinir ağının ilklendirilmesinin SOM a dayalı sezgisel bir yöntemle gerçekleştirilmesi iv) Yakınsama süresinin çok uzun olması ve buna bağlı olarak genellikle çok fazla yumuşatılmış sonuç üretmesi olarak sıralanabilir. Bu tezde yöntemin bu olumsuzluklarını ortadan kaldırmak üzere bir dizi iyileştirmeler gerçekleştirilmiştir, öncelikle bölüt sayısının verilen imgeden otomatik olarak belirlenmesine yönelik bir topak geçerlilik ölçütü kullanılmıştır. İkinci olarak yapay sinir ağının ön koşullanmasında kullanılan ön sınıflama evresi renkli imgeleri de kullanacak şekilde genişletilmiştir. Son olarak ön sınıflamada SOM yöntemi yerine bulanık c- ortalamaları yöntemi kullanılmıştır. Böylece SOM da önce etiket kararı verip sonra sezgisel olarak bulanıklaştırma yerine doğrudan bulanık çıkış üreten bir yöntem kullanılmıştır. Yumuşatılmış çıkış ve uzun yakınsama süresi problemlerini aşmak için KSYSA'nın mimarisini değiştiren dört yeni yöntem önerilmiştir. Birinci yöntem Sınır kısıtı sağlayan yapay sinir ağı olarak adlandırılmaktadır. Bu yöntemde KSYSA da mevcut kısıtların yanı sıra kaba ölçekte çalışan bir Marr-Hildreth ayrıt sezicisinden elde edilen sınır kısıtlan da kullanılmıştır. İkinci yöntem Çoklu-taramalı KSYSA yöntemidir. Bu yöntemde KSYSA nın performansı çoklu-çözünürlük yaklaşımı ile iyileştirilmiştir. Çoklu-çözünürlüğü gerçekleştirmek için çoklu-tarama yaklaşımı kullanılmıştır. Çoklu-çözünürlük kullanılarak gerçekleştirilen diğer bir yöntem de piramit temelli KSYSA dır. Burada piramitin her katmanında ayrı bir KSYSA kullanılmıştır. Son olarak Markov rasgele alanları (MRA) yaklaşımı ile KSYSA birleştirilerek yeni bir yöntem önerilmiştir. KSYSA sadece komşululuklara göre enerji azaltma işlevi görmektedir, önerilen yöntemde KSYSA nın mimarisine, MRA temelli enerji azaltmayı gerçekleştirmek üzere veriye bağımlılık terimi de eklenmiştir. XIXBu tezde önerilen bütün yeni yöntemlerin başarımları önerilen değerlendirme kriteri ve test imge yordamı kullanılarak değerlendirilmiş ve karşılaştırılmıştır. önerilen yöntemlerin literatürdeki rakiplerine göre daha üstün bölütleme başarımına sahip olduğu, ayrıca yürütüm sürelerin de daha kısa olduğu gözlenmiştir. XX
Image segmentation is the process that divides the given image into regions in terms of specific uniformity criteria. Segmentation is used in many image processing applications. The desired performance of this processing is tightly coupled to the performance of the segmentation stage since it directly affects the consecutive steps of analysis. Thus the segmentation can be viewed as the most critical stage in the image analysis. The segmentation methods could be broadly divided into two classes: Problem- oriented and general methods. Problem-oriented methods are developed according to the nature of the given problem while general methods try to carry out the segmentation without any a-priori knowledge about the scene so that they are bound to be ad hoc and intuitive approaches. General methods can be subdivided into four categories: Region-based, boundary-based, measurement space-based and hybrid approaches. Region-based methods take into account pixel similarity in the region while boundary-based methods use assumption of discontinuity between the regions. Measurement-space-based methods carry out the segmentation task in the measurement domain usually without spatial constraints. In the hybrid methods, a combination of the above approaches is employed. An important issue is the evaluation and assessment of the goodness of an image segmentation algorithm. Evaluation and assessment criterion could firstly provide guidance for the selection among several algorithms. Secondly, most of the image segmentation methods require some initial setting or subsequent adjustment of parameters, and the segmentation outcome often depends upon the choice of these parameters. Choosing the correct parameters for the given application can also be instrumented via a performance criterion. Finally, the third importance of performance indicators comes up in the feedbacked image analysis operations. These types of systems try to improve their performance by modifying their strategy according to the feedback from the current result. Then the quantitative measure of XIVthe performance plays the key role in providing a feedback path from the current outcome to the algorithm. Consequently, the performance evaluation and comparison of image segmentation algorithms is an indispensable tool in the segmentation problem. In this thesis a novel evaluation criterion that combines classification error and shape deformation has been proposed. Segmentation evaluation criteria must be able to quantify two important aspects: Good detection of classification and good detection of shape formation. Thus the evaluation criterion must give high score the algorithms that generate segments more closely to the reference one in the spatial domain and generate segments whose shapes are more similar to the reference one. In this thesis classification error measure proposed by Yasnoff etal (1977) is adopted as detection of classification error. Shape deformation is detected by a measure based on comparison of the turning angle function of objects. These two measures have sometimes-complementary properties. In fact, classification error measure has good detection of classification but poor shape distortion monitoring ability, while turning angle function has good shape distortion monitoring but poor detection of classification capability. It has been conjectured that their linear combination of these two criteria will satisfy both the localization and shape requirements. In addition, an automatic test image generation procedure has also been proposed in this thesis. Among the two novel segmentation algorithms, proposed the first one relies on multithresholding. Multithresholding is an attractive and widely used tool that is based on image histogram. While multithresholding for gray level images is relatively straightforward, it becomes a complex problem for color images since their histograms are three-dimensional. In this thesis, a novel multithresholding technique based on 2-Dimensional (2D) histograms and decision fusion has been proposed. In this technique, pairs of three color bands are selected and their three 2D histograms are constituted. These histograms are partitioned according to their dominant peaks. Each band pair image is segmented using its corresponding partitioned 2D histogram. The three segmented maps are fused to obtain a final segmentation by taking into account label concordances in each segmented map. This result is filtered morphologically so that small segments are eliminated. The proposed method has been compared with its 1 -Dimensional (1D) histogram and 3- Dimensional (3D) histogram based counterparts. It is observed that the proposed method can catch segments that can be missed in the 1 D-histogram based method Thus its performance is superior with respect to the 1 D case while its computational complexity is only about two times that of 1'D case. Although the 3D~histogram based method gives the best results since the threshold blobs are inherently delineated very well, the computational complexity of 3D case is about four hundred xvtimes that of the 2D case. Consequently, the proposed method is an attractive alternative to its 1D and 3D counterparts in the manner both computational complexity and segmentation performance. The second innovation proposed consists of various adaptations of the Constraint Satisfaction Neural Network (CSNN) based segmentation, which is proposed by Lin et al. (1992). Although it is proposed as a neural network implementation of the constraint satisfaction problem, it can be interpreted as a probabilistic relaxation scheme. Various drawbacks of the algorithm can be summarized as follows: i) The number of segments are given the algorithm by means of a-priori information, ii) Only gray level image is used in CSNN. iii) Initialization of CSNN is carried out by an ad hoc method using SOM clustering, iv) Convergence time of CSNN is very long. Depending on this long convergence time, CSNN generates generally oversmoothed segments. Some modifications to overcome the shortcomings of the original algorithm will be presented. First, the number of segments is determined automatically from a given image by means of a cluster validity criterion. For this purpose, a modified AIC cluster validity measure is used. Second, the initial architecture is generalized to color images. Third, the initialization stage is modified by using the fuzzy c-means algorithm rather than the SOM algorithm to avoid the ad hoc fuzzification in the initialization. To overcome oversmoothing and long convergence time problems, some structural modifications have been imposed to CSNN. For example, boundary constraints obtained from a coarse scale Marr- Hildreth edge detector have been added to CSNN interconnections. The proposed multi-scan CSNN (MS-CSNN) or multi-grid sampling CSNN algorithm introduced a multiresolution nature to CSNN. A second way to provide multiresolution behaviors was the pyramid architectural applied to CSNN. This yields third method called pyramidal CSNN (P-CSNN). Finally, CSNN has been altered to solve the Markov Random Field (MRF) segmentation problem. Since it was observed that CSNN actually carries out overall energy minimization but using only neighborhood contributions, it was sufficient to add a data dependency term to the CSNN formulation to implement the MRF-based minimization. The performance of all proposed methods are compared by using the proposed evaluation criteria and test images that are generated by proposed test image generation procedure. It has been observed that the segmentation performances of the proposed methods are better than those of the competitor methods in the literature. The computational complexities of the proposed methods have been also reduced in terms of their competitors. xvi