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.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.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: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.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.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.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.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: