Image Segmentation with Snake (Matlab) | Turkish Tutorial

Giriş
Bu projede eşik yöntem dışında bir yöntem ile bölütleme işlemi gerçekleştirilmiştir. Kullanılan yöntem, Active Contour olarak da bilinen yılan(snake) yöntemidir. Uygulama MATLAB R2008b üzerinde geliştirilmiştir.

Uygulama, medikal görüntülerde test edilmiştir ve başarımının oval nesnelerin tespitinde daha başarılı olduğu görülmüştür.

Uygulama
Bu çalışmada nesne tespitinde kullanılan algoritmaya yardımcı olarak DIPImage kütüphanesi kullanılmıştır. Nesne tespitinde yapılan işlemler aşağıda sıralanmıştır:

Kullanıcıdan nesne tespitine başlamak için 4 adet nokta girmesi istenir.
Alınan 4 nokta yardımı ile bir ilk sınır çizilir. Alınan 4 noktanın x ve y koordinatlarının ortalaması alınarak merkez nokta belirlenir. Her nokta arası uzaklıklar birbirleri ile kıyaslanarak en büyük farkın olduğu x ve y değerleri çap olacak şekilde bir daire çizilir.

Şekil 1. Alınan Noktalar ile Oluşturulan Daire

Alpha, beta, gamma ve iterasyon parametreleri aranacak nesnelerin tipine göre belirlenmiştir. Test için daha çok oval nesneler arandığından dolayı beta yüksek verilmiştir. Çünkü betanın yüksek olması aramanın daha oval hale getirilmesine sebep olur. Alpha ve beta parametreleri de gamma parametreleri ile zıt hareket etmektedir. Alpha ve beta ne kadar yüksek ise gamma aynı biçimde küçük olur.
Parametreler de verildikten sonra yılan modeli yerleştirilmeye çalışılır. Yılan yerleştirilirken toplam enerjinin minimizasyonuna çalışılır. Toplam enerji iç ve dış enerjilerin toplamına eşittir.
Toplam enerji her iterasyonda hesaplandığında belli bir enerji eşik değerinden yüksek ise iç enerji oranınca sınırlar yeniden hesaplanır. Bu sayede aranılan bölgeye doğru kayma gerçekleştirilmiş olur.
İstenen eşik enerjisine ulaşıldığında veya belli bir iterasyon sayısına ulaşıldığında sistem en son bulunduğu noktayı gösterir.

Snake (Active Contour) Algoritması

Yılan modelini oluştururken belirlenen sınırın iç ve dış olmak üzere iki farklı enerjisinin olduğu kabul edilmektedir. İç enerji belirlenen şeklin yuvarlaksı ya da keskin hatlara sahip olup olmamasına göre belirlenmektedir. Dış enerji ise belirlenen şeklin görüntü üzerinde işaretlenmesi sonucunda eşitlenen noktaların komşu piksellerdeki değerlerinin gradyanı alınarak hesaplanmaktadır. Bulunan her iki enerjinin toplamının belirlenen değerden küçük olması istenmektedir; eğer küçük değilse, noktalar iç ve dış kuvvetlerin etkisinde hareket ettirilerek tekrardan iç ve dış enerjileri hesaplanmaktadır. İç ve dış kuvvetlerin neler oldugu ve nasıl hesaplanacağı ilerleyen kısımlarda anlatılacaktır. Terim olarak hesaplanan bu değerlere kuvvet denilmesinin sebebi ise, aynı fizikteki kuvvet terimi gibi burada da bulunan değerlerin vektörel olması yani hem büyüklük hem de yön bilgisine sahip olmasıdır. Sınırı oluşturacak noktaların yeni yerleri belirlenirken, sanki noktaları yeni yerlerine dogru iten bir kuvvet oldugu kabul edilerek hesaplamalar yapılır.

Yılan modelinde enerji minimizasyonu prensibine göre yapılmaktadır. Enerjimizi nasıl minimize edecegimizi belirlemek için,

Etoplam = Eiç + Edış

Burada Eiç iç enerji olarak adlandırılmaktadır ve çizilen şeklin sınırlarının yuvarlaksı hatlara sahip olup olmadığını gösteren bir değerdir. Çok girintili çıkıntılı keskin köşeli şekiller istediğimiz bir sonuç değildir. Bu gibi durumlarda iç enerjinin düşük çıkması gerekmektedir. Edış dış enerji olarak adlandırılır ve bunu hesaplayabilmek için görüntünün gradyanı alınır. Görüntünün gradyanı yüksek çıkarsa, dış enerji düşük demektir. Çünkü belirlenen nokta için komşu piksellerindeki gri seviyeleri ile olan farkı yüksek demektir. Farkın yüksek oldugu noktalarda sınırlar yer almaktadır ve amaç sınırların belirlenmesi oldugu için, dış enerji düşük olmalıdır. Zaten yılan modelinde enerji minimizasyonu hedeflenmektedir.

Snake bölütleme algoritmasının işleyişi şu şekildedir:

Başlangıç sınırları belirlenir.
Sınırlar üzerinden iç enerji hesaplanır. (Eiç)
Dış enerji hesaplanır. (Edıs)
Toplam enerji hesaplanır. (Etoplam)
Toplam enerjinin önceden tanımlanan bir minimum değere (bir parametre)
ulaşıp ulaşmadığı kontrol edilir. Minimuma ulaşmış ise işlem sonlandırılır.

Toplam enerjiyi minimize edecek şekilde iç ve dış kuvvetlerin boyutu ve
yönüne göre noktalar içe doğru kaydırılır.

Sınırlar tekrar oluş Adım 2’den devam edilir.
Yılan modelinin doğru çalısabilmesi için birinci adım çok önemlidir. Çok gereksiz bir ayrıntı gibi görülse de, doğru nesnenin sınırlarını belirtmek için ilk başta doğru nokta seçmek gerekmektedir. Yılan algoritması çalışırken ilk noktalara göre hesaplama yapıldığında beklenen sonuca ulaşılamadığında noktalar içeriye dogru kaydırılarak algoritma tekrar işletilmektedir.

Adım 1’i tamamlayıp ilk noktaları doğru belirledikten sonra algoritmamızın ikinci adımına geçebiliriz. Burada iç enerjiyi hesaplamamız gerekmektedir. İç enerjiyi hesaplarken sınırlarımızdaki keskinlik ve yumuşaklığa bakıyorduk, bunun en kolay yolu noktaların türevini alarak eğimine bakmaktır.

Sınırımızın x ve y koordinatlarını birbirinden ayırıp x’e ve y’ye göre ayrı ayrı kısmi türev almamız gerekmektedir. Bu nedenle elimizdeki x ve y koordinatlarına sahip noktaları x(s) ve y(s) fonksiyonları haline dönüştürmemiz gerekmektedir. İlk noktamız s=0 olarak, son noktamız ise s=1 olarak kabul edilir. Buradaki s, kolay kısmi türev alabilmemiz için tanımlanmış ve doğrusal artan değerlerden oluşan bir ara degişkendir. Belirlenen sınırdan yapılacak örnekleme için s düzleminde s=0’dan s=1’e kadar olan alanda eşit aralıklarla farklı s degerileri elde edilir. Her s değeri için karşılık gelen x değeri x(s), y değeri ise y(s) olarak iki ayrı dizide saklanır.

Gerekli dönüşümü yaptıktan sonra iç kuvvetin hesaplanabilmesi için v(x(si), y(si)) fonksiyonunun s’ye göre birinci kısmi türevi alınır. Kısmi türev (v fonksiyonunun eğimi) daha önceden tanımlanan bir değerden küçük ise, iç enerji düşüktür. Daha sonra yine iç kuvvetin hesaplanmasında kullanılmak üzere v(x(si), y(si)) fonksiyonunun s’ye göre ikinci derece kısmi türevi alınır. Eğer ikinci türevde bir kırılma yoksa, bu da iç enerjinin düşük yani istenen değerde oldugunu göstermektedir. Hatırlanacağı gibi yüksek enerji kötü bir sonuçtur ve iç enerjinin düşük çıkması istenmektedir.
Dış enerjiyi hesaplamadan önce görüntüde bazı ön işlemler yapmamız daha yararlı olacaktır. Görüntüde yer alan gürültülerden kurtulmak için görüntümüzde yumuşatma işlemi yapabiliriz. Bu amaçla genellikle Gauss süzgeci kullanılmaktadır. Daha sonra yumuşatılmış görüntünün gradyanı hesaplanır. Eğer işlem sonunda gradyanı yüksek çıkıyorsa dış enerjisi düşük demektir ki, bu da bizim istedigimiz bir durumdur.

Bu toplam enerjinin daha önce tanımlanan kabul edilebilir minimum enerji değerinden küçük olup olmadığı kontrol edilir. Toplam enerji yeteri kadar küçük ise, sonuç bulunmuş demektir ve işlem tamamlanır. Toplam enerji yeteri kadar küçük değil ise, toplam enerjiyi minimize edecek şekilde noktaları kaydırmamız gerekmektedir; bu kaydırma işlemini yapabilmek için de gerilme kuvveti, eğilme dayanım kuvveti, duraklama kuvveti ve görüntü kuvveti olarak adlandırılan değerler hesaplanır.

Hesaplanan bu kuvvetlerin etkisi ile görüntüdeki noktalarımızın kayması sağlanarak, Adım 2’den itibaren algoritmamız tekrarlanır. Minimum enerjiye ulaşıldığı anda hedeflenen sınır belirlenmiş durumdadır.

GerilmeKuvveti = 2v(si)-v(si-1)-v(si+1)

Burada v fonksiyonunda s noktası için bu noktadan bir önceki ve bir sonraki noktaların x ve y koordinatları dikkate alınarak hesaplama yapılmaktadır.

EgilmeDayanimKuvveti= 2a(si)-a(si-1)-a(si+1)

Eğilme dayanım kuvveti olarak tanımlanan sınırımızın ne kadar sert geçislere sahip olup olmadıgını belirledigimiz degerin iç enerjiden nasıl hesaplanacagı gösterilmistir. Yine burada da bir nokta için önceki ve sonraki noktaların iç enerjileri de dikkate alınarak işlem yapılmaktadır.
Bütün bu fonksiyonlar ve enerji değerleri her bir nokta için uygulanır ve işlem sonucunda noktaların yeni yerleri belirlenir; Yılan modelini kullanarak bir görüntünün içindeki nesnenin kenarlarını bulmanın yanı sıra hareketli kenar yakalama-takip etme özelliğide bulunmaktadır. Dudak okuma ve öznel görüntü dediğimiz aslında bir sınırı olmayan bizim gözle hissedebildigimiz alanların bilgisayar tarafından da algılanabilmesi çarpıcı olan diger uygulamalardır.
Snake Uygulamasının Çalışması
Verilen ilk 4 noktayı iç ve dış kuvvetlere göre merkeze doğru çeken örnek Şekil 2’de gösterilmiştir.

Şekil 2. Dıştan Belirlenen Sınırların İçe Doğru Kayması

Şekil 2’de de görüleceği üzere en dıştaki yeşil çizgi ilk seçilen 4 noktaya göre çizilen dairedir. Bu daireden içeri doğru kayma yapılarak aranan nesneye ulaşılmaya çalışılır ve her 5 iterasyonda ekrana ara daireler çizilir. Mavi renkli daireler bu ara daireleri göstermektedir. Son olarak kırmızı daire nesnenin sınırlarını göstermektedir. Her iterasyonda enerji toplamları hesaplanmış ve dairenin içeri doğru kayması sağlanmıştır.

Şekil 3. İçten Belirlenen Sınırların Dışa Doğru Kayması

Şekil 3’de de görüleceği üzere en içteki yeşil çizgi ilk seçilen 4 noktaya göre çizilen dairedir. Bu daireden dışarı doğru kayma yapılarak aranan nesneye ulaşılmaya çalışılır ve her 5 iterasyonda ekrana ara daireler çizilir. Mavi renkli daireler bu ara daireleri göstermektedir. Son olarak kırmızı daire nesnenin sınırlarını göstermektedir. Her iterasyonda enerji toplamları hesaplanmış ve dairenin dışarı doğru kayması sağlanmıştır.

Sonuçlar
Uygulama, özellikle oval nesnelerde uygun sonuçlar üretmektedir. Bulunmak istenilen alan, çizilen çemberin dışında veya içinde olası durumlarında da kuvvetler etkisi ile toplam enerjinin minumum olduğu noktalara doğru hareket etmektedir. Bu uygulama da basit bir snake uygulaması olduğu için bazı parametreler ayarlanarak daha istenilen sonuçlar üretilebilir. Alfa, beta, gamma ve iterasyon parametreleri değiştirilerek oval olmayan nesnelerin de tespiti sağlanabilir. Bu parametrelerden beta, ilk çizilen dairenin koordinatları üzerinde yumuşak geçiş olmasını sağlar. Böylece her nokta diğer noktaların hareket yönünden daha az etkilenir.

İlk çizilen daire daha önce anlatılan durumlara uymaması durumda bile algoritma doğru çalışmaktadır. Daha önce anlatılan durumlar olan ilk dairenin şeklin içinde veya dışında olması durumu dışında da şöyle bir olasılık vardır. İlk belirlenen daire bölgeyi kısmen kapsayabilir. Şekil 4’te bu durum görüntülenmiştir.

Şekil 4. Kullanıcının Noktalarının Bölgenin Bir Kısmını Kapsaması

Burada şeklin solundaki koordinatlar kuvvet etkisiyle içe doğru ilerlerken, şeklin sağındaki noktalar dışa doğru hareket etmiştir. Ara İterasyonlarda görünen çizgiler incelendiğinde bu geçiş kuvvet farkının büyük olduğu yerde sert, diğer durumlarda yumuşak geçiş şeklinde gözlenmiştir. Benzer durum Şekil 5’te de gerçekleştirilmiş ve başarılı sonuç elde edilmiştir.

Şekil 5. Kullanıcının Noktalarının Bölgenin Bir Kısmını Kapsaması

Benim web sitem: http://www.bulentsiyah.com/snake-ile-goruntu-bolutleme-matlab/

Kaynaklar
[1] Xu C. and Prince J. L., “Snakes, shape, and gradient vector flow”, IEEE Transactions on Image Processing

[2] İnternet: Sayısal Görüntü İşleme.

http://www.yildiz.edu.tr/~bayram/sgi/saygi.htm

[3] Yaman K., “Görüntü isleme yönteminin ankara hızlı raylı ulasım sistemi güzergahında sefer aralıklarının optimizasyonuna yönelik olarak incelenmesi”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara, 1-156

(2001).

[4] Makinacı M., “Patalojik görüntü analizi: normal ve kanserli prostat hücre çekirdeklerinin Gauss Markov rassal alanlar yöntemi ile modellenmesi ve sınıflandırılması”, 9. IEEE Sinyal İşleme ve Uygulamaları Kurultayı, G