Rastgele yürüten algoritması

Rastgele yürüten algoritması, görüntü segmentasyonu için bir algoritmadır. Algoritmanın ilk açıklamasında, bir kullanıcı etkileşimli olarak az sayıda pikseli bilinen etiketlerle (tohum olarak adlandırılır), örneğin "nesne" ve "arka plan" olarak etiketlemektedir. Etiketlenmemiş piksellerin her birinin rastgele bir yürüteç serbest bıraktığı düşünülmektedir. Her pikselin rastgele yürüteçlerinin ilk olarak her etiketi taşıyan bir tohuma ulaşma olasılığı hesaplanmaktadır. Yani bir kullanıcı her biri farklı bir etikete sahip K tohum yerleştirirse, o zaman gereklidir. Her piksel için, pikselden ayrılan rastgele bir yürüyenin her bir tohuma ilk varma olasılığını hesaplanır. Bu olasılıklar, bir lineer denklem sistemi çözülerek analitik olarak belirlenmektedir. Her piksel için bu olasılıkları hesapladıktan sonra, piksel, rastgele bir yürüteç gönderme olasılığı en yüksek olan etikete atanmaktadır. Görüntü, her pikselin komşu piksellere kenarlarla bağlanan bir düğüme karşılık geldiği ve kenarların pikseller arasındaki benzerliği yansıtacak şekilde ağırlıklandırıldığı bir grafik olarak modellenmektedir. Bu nedenle, rastgele yürüyüş ağırlıklı grafikte geçekleşmektedir (grafiklerde rastgele yürüyüşlere giriş için Doyle ve Snell'e bakınız).

İlk algoritma, görüntü segmentasyonu için etkileşimli bir yöntem olarak formüle edilmiş olsa da, bir veri doğruluğu terimi (örneğin, bir yoğunluk öncesi) verilen tam otomatik bir algoritma olacak şekilde genişletilmiştir. Diğer uygulamalara da genişletilmiştir.

Algoritma başlangıçta Leo Grady  tarafından bir konferans makalesi ve daha sonra bir dergi makalesi olarak yayınlanmıştır.

Matematiği

Algoritma rastgele yürüyüşler açısından tanımlansa da, her düğümün tohumlara rastgele bir yürüteç gönderme olasılığı, Laplacian matrisi ile temsil edebileceğimiz bir seyrek, pozitif tanımlı doğrusal denklem sistemi ile analitik olarak  değişkeni hesaplanmaktadır.  Algoritmanın rastgele sayıda etikete (nesneye) uygulandığı gösterilmiştir. Ancak buradaki açıklama iki etiket cinsindendir (açıklamanın basitliği için).

Görüntünün bir grafikle temsil edildiğini, her düğümün bir pikselle ilişkili olduğunu ve her kenarın komşu pikselleri ve kenar ağırlıkları, görüntü yoğunluğu, renk, doku veya diğer anlamlı özelliklerdeki farklılıklardan türetilebilen düğüm benzerliğini kodlamak için kullanılmaktadır. Örneğin,  düğümünde  görüntü yoğunluğu kullanıldığında, kenar ağırlıklandırma işlevinin kullanılması yaygındır.

Düğümler, kenarlar ve ağırlıklar daha sonra Laplacian matrisinin grafiğini oluşturmak için kullanılmaktadır.

Rastgele yürüyen algoritma, enerjiyi optimize etmektedir.

Burada, grafikteki her düğümle ilişkili gerçek değerli bir değişkeni temsil eder ve optimizasyon şu şekilde sınırlandırılmaktadır:

 için  ve

 için ,

Burada  ve  rsırasıyla ön plan ve arka plan tohumlarının kümelerini temsil etmektedir.  'nin tohumlanmış düğümler kümesini ve 'nin tohumlanmamış düğümler kümesini temsil etmesine izin verilirse, enerji minimizasyon probleminin optimumu aşağıdaki çözümle verilmektedir.

burada alt simgeler, ilgili kümeler tarafından indekslenen Laplacian matrisi  grafiğinin bölümünü belirtmek için kullanılmaktadır.
Algoritma olabilirlik (birli) terimlerini dahil etmek için, birinin enerjiyi optimize edebileceği 

pozitif, köşegen  ve  matrisleri için gösterilmiştir. Bu enerjiyi optimize etmek, lineer denklemler sistemine yol açmaktadır.

Bu durumda tohumlanmış düğümlerin  kümesi boş olabilir, ancak pozitif diyagonal matrislerin varlığı bu lineer sistem için benzersiz bir çözüme izin vermektedir.

Örneğin, nesnenin bir renk modelini dahil etmek için olabilirlik/birli terimleri kullanılırsa, o zaman ,  düğümündeki rengin nesneye ait olacağına dair güveni temsil etmektedir. Ayrıca , düğümündeki rengin ait olduğu güveni temsil etmektedir.

Algoritma yorumları

Rastgele yürüteç algoritması başlangıçta, piksele düşen bir rastgele yürütecin önce bir nesne (ön plan) çekirdeğine veya bir arka plan çekirdeğine ulaşma olasılığına dayalı olarak bir pikseli nesne/arka plan olarak etiketleyerek motive edilmiştir. Bununla birlikte, bu aynı algoritmanın ortaya çıkmış birkaç başka yorumu vardır.

Devre teorisi yorumları 

Elektrik devresi teorisi ve grafikler üzerinde rastgele yürüyüşler arasında iyi bilinen bağlantılar vardır.  Sonuç olarak, rastgele yürüyen algoritmanın bir elektrik devresi açısından iki farklı yorumu vardır. Her iki durumda da grafik, her bir kenarın pasif bir doğrusal dirençle değiştirildiği bir elektrik devresi olarak görülmektedir.Direnç , kenar  ile ilişkilidir. Be eşitlik olarak  ayarlanmaktadır.

İkinci yorumda, rastgele yürüteç olasılığını 0,5'te eşikleyerek bir düğümü nesne veya arka plan olarak etiketlemek, bir düğümü, düğüm ile nesne veya arka plan tohumları arasındaki göreli etkin iletkenliğe dayalı olarak nesne veya arka plan olarak etiketlemeye eşdeğerdir. Spesifik olarak, bir düğümün nesne tohumlarına karşı arka plan tohumlarına göre daha yüksek bir etkili iletkenliği (düşük etkili direnç) varsa, o zaman düğüm nesne olarak etiketlenmesi gerekmektedir. Bir düğümün arka plan tohumlarına karşı nesne tohumlarına göre daha yüksek bir etkili iletkenliği (düşük etkili direnç) varsa, o zaman düğüm arka plan olarak etiketlenmektedir.

Uzantılar 

Yukarıda açıklanan geleneksel rastgele yürüyen algoritma birkaç şekilde genişletilmiştir:

 Yeniden başlatma ile rastgele yürüyüşler
 Alfa paspas
 Eşik seçimi
 Yumuşak girişler
 Önceden bölümlere ayrılmış bir görüntü üzerinde çalıştırın
 Ölçek alanı rastgele yürüyüş
 Çevrimdışı ön hesaplamayı kullanarak hızlı rastgele yürüteç 
 Esnek uyumluluk işlevlerine izin veren genelleştirilmiş rastgele yürüyüşler 
 Grafik kesimlerini, rastgele yürüyeni ve en kısa yolu birleştiren güç havzaları 
 Rastgele yürüteç havzaları 
 Çok değişkenli Gauss koşullu rastgele alan

Uygulamalar 

Görüntü segmentasyonunun ötesinde, rastgele yürüteç algoritması veya uzantıları, bilgisayarla görme ve grafiklerdeki çeşitli problemlere ek olarak uygulanmıştır:

 Görüntü Renklendirme
 Etkileşimli rotoskop
 Tıbbi görüntü segmentasyonu
 Birden çok segmentasyonu birleştirme
 Kafes segmentasyonu
 Ağ gürültü giderme
 Segmentasyon düzenleme
 Gölge ortadan kaldırılması
 Stereo eşleştirme (yani, tek boyutlu görüntü kaydı)
 Görüntü birleştirme

Kaynakça

Ek bağlantılar
 
 
 scikit-image  görüntü işleme araç kutusunda 

Görüntü işleme
Bilgisayarlı görme