Rastgele yürüten algoritması

[bullvar_katip]

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 Kategori:Görüntü işleme Kategori:Bilgisayarlı görme