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,^[1] 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^[2]).

İ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.^[3] Diğer uygulamalara da genişletilmiştir.

Algoritma başlangıçta Leo Grady 27 Haziran 2021 tarihinde Wayback Machine sitesinde arşivlendi. tarafından bir konferans makalesi^[4] ve daha sonra bir dergi makalesi olarak yayınlanmıştır.^[1]

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 ${\displaystyle L}$ 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, ${\displaystyle v_{i}}$ düğümünde ${\displaystyle g_{i}}$ görüntü yoğunluğu kullanıldığında, kenar ağırlıklandırma işlevinin kullanılması yaygındır.

${\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}$

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.

${\displaystyle Q(x)=x^{T}Lx=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}}$

Burada, ${\displaystyle x_{i}}$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:

${\displaystyle x_{i}=1}$ için ${\displaystyle v_{i}\in F}$ ve

${\displaystyle x_{i}=0}$ için ${\displaystyle v_{i}\in B}$,

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

${\displaystyle L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}$

burada alt simgeler, ilgili kümeler tarafından indekslenen Laplacian matrisi ${\displaystyle L}$ grafiğinin bölümünü belirtmek için kullanılmaktadır.

Algoritma olabilirlik (birli) terimlerini dahil etmek için,^[3] birinin enerjiyi optimize edebileceği

${\displaystyle Q(x)=x^{T}Lx+\gamma \left((1-x)^{T}F(1-x)+x^{T}Bx\right)=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}+\gamma \left(\sum _{v_{i}}f_{i}(1-x_{i})^{2}+\sum _{v_{i}}b_{i}x_{i}^{2}\right),}$

pozitif, köşegen ${\displaystyle F}$ ve ${\displaystyle B}$ matrisleri için gösterilmiştir. Bu enerjiyi optimize etmek, lineer denklemler sistemine yol açmaktadır.

${\displaystyle \left(L_{{\overline {S}},{\overline {S}}}+\gamma F_{{\overline {S}},{\overline {S}}}+\gamma B_{{\overline {S}},{\overline {S}}}\right)x_{\overline {S}}=-L_{{\overline {S}},S}x_{S}-\gamma F_{{\overline {S}},{\overline {S}}}.}$

Bu durumda tohumlanmış düğümlerin ${\displaystyle S}$ 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 ${\displaystyle f_{i}}$, ${\displaystyle v_{i}}$ düğümündeki rengin nesneye ait olacağına dair güveni temsil etmektedir. Ayrıca ${\displaystyle b_{i}}$, ${\displaystyle v_{i}}$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.^[1]

Elektrik devresi teorisi ve grafikler üzerinde rastgele yürüyüşler arasında iyi bilinen bağlantılar vardır.^[5] 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ç ${\displaystyle r_{ij}}$, kenar ${\displaystyle e_{ij}}$ ile ilişkilidir. Be eşitlik olarak ${\displaystyle r_{ij}={\frac {1}{w_{ij}}}}$ 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.

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

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

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^[18]
• Etkileşimli rotoskop^[19]
• Tıbbi görüntü segmentasyonu^[20][21][22]
• Birden çok segmentasyonu birleştirme^[23]
• Kafes segmentasyonu^[24][25]
• Ağ gürültü giderme^[26]
• Segmentasyon düzenleme^[27]
• Gölge ortadan kaldırılması^[28]
• Stereo eşleştirme (yani, tek boyutlu görüntü kaydı)^[29]
• Görüntü birleştirme^[14][17]

• "Orijinal rastgele yürüteç algoritmasını uygulayan Matlab kodu". 19 Temmuz 2011 tarihinde kaynağından arşivlendi. 
• "Ön hesaplama ile rastgele yürüteç algoritmasını uygulayan Matlab kodu". 6 Temmuz 2011 tarihinde kaynağından arşivlendi. 
• scikit-image 9 Temmuz 2021 tarihinde Wayback Machine sitesinde arşivlendi. görüntü işleme araç kutusunda "Orijinal rastgele yürüteç algoritmasının Python uygulaması". 14 Ekim 2012 tarihinde kaynağından arşivlendi.