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]

Matematiği değiştir

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,[3] 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ı değiştir

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]

Devre teorisi yorumları değiştir

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ç  , 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 değiştir

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]

Uygulamalar değiştir

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]

Kaynakça değiştir

  1. ^ a b c Grady, L. (Kasım 2006), "Random walks for image segmentation" (PDF), Transactions on Pattern Analysis and Machine Intelligence (PAMI), IEEE, 28 (11), 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  2. ^ P. Doyle & J. L. Snell (1984), Random Walks and Electric Networks, Mathematical Association of America 
  3. ^ a b Leo Grady (Haziran 2005), "Multilabel Random Walker Image Segmentation Using Prior Models" (PDF), Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), San Diego, 1, ss. 763-770, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  4. ^ Leo Grady & Gareth Funka-Lea (15 Mayıs 2004), "Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials" (PDF), Proceedings of the 8th ECCV04, Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, Prague, Czech Republic: Springer-Verlag, ss. 230-245, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  5. ^ P. G. Doyle & J. L. Snell (1984), "Random Walks and Electrical Networks" (PDF), Carus Mathematical Monographs, 7 Mayıs 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 16 Temmuz 2021 
  6. ^ T. H. Kim, K. M. Lee & S. U. Lee (2008), "Generative Image Segmentation Using Random Walks with Restart" (PDF), Proceedings of European Conference on Computer Vision (ECCV) 2008, ss. 264-275, doi:10.1007/978-3-540-88690-7_20 
  7. ^ J. Wang, M. Agrawala & M. F. Cohen (Temmuz 2007), "Soft scissors: an interactive tool for realtime high quality matting" (PDF), ACM Transactions on Graphics, 26 (3), doi:10.1145/1239451.1239460, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021, Article 9 
  8. ^ S. Rysavy, A. Flores, R. Enciso & K. Okada (2008), "Classifiability Criteria for Refining of Random Walks Segmentation" (PDF), Proceedings of International Conference on Pattern Recognition (ICPR) 2008, doi:10.1109/ICPR.2008.4761585, 24 Ekim 2020 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  9. ^ W. Yang, J. Cai, J. Zheng & J. Luo (Eylül 2010), "User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs" (PDF), IEEE Transactions on Image Processing, 19 (9), ss. 2470-2479, doi:10.1109/TIP.2010.2048611, ISSN 1941-0042 
  10. ^ C. Chefd'hotel & A. Sebbane (2007), "Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation", IEEE International Conference on Computer Vision (ICCV) 2007, 1, ss. 1-7, doi:10.1109/ICCV.2007.4409117, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  11. ^ R. Rzeszutek, T. El-Maraghi & D. Androutsos (2009), "Image segmentation using scale-space random walks", Proceedings of the 16th international conference on Digital Signal Processing, ss. 458-461, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  12. ^ L. Grady & A. K. Sinop (2008), "Fast approximate random walker segmentation using eigenvector precomputation" (PDF), IEEE Conf. CVPR, ss. 1-8, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  13. ^ S. Andrews, G. Hamarneh & A. Saad (2010), "Fast random walker with priors using precomputation for interactive medical image segmentation" (PDF), Proceedings of MICCAI 2010, 3 Mayıs 2019 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  14. ^ a b R. Shen, I. Cheng, J. Shi & A. Basu (2011), "Generalized Random Walks for Fusion of Multi-exposure Images", IEEE Trans. on Image Processing, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  15. ^ Camille Couprie, Leo Grady, Laurent Najman & Hugues Talbot (Temmuz 2011), "Power Watersheds: A Unifying Graph-Based Optimization Framework" (PDF), IEEE Transactions on Pattern Analysis and Machine Intelligence, 33 (7), ss. 1384-1399, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  16. ^ S. Ram & J. J. Rodriguez (Mayıs 2013), "Random Walker Watersheds: A New Image Segmentation Approach", IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vancouver, Canada, ss. 1473-1477, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  17. ^ a b R. Shen, I. Cheng & A. Basu (2013), "QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF", IEEE Trans. on Image Processing, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  18. ^ X. Liu, J. Liu & Z. Feng (2009), "Colorization Using Segmentation with Random Walk", Computer Analysis of Images and Patterns, ss. 468-475, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  19. ^ R. Rzeszutek, T. El-Maraghi & D. Androutsos, "Interactive rotoscoping through scale-space random walks", Proceedings of the 2009 IEEE international conference on Multimedia and Expo, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  20. ^ S. P. Dakua, J. S. Sahambi (Mayıs 2009), "LV Contour Extraction from Cardiac MR Images Using Random Walks Approach", Int. Journal of Recent Trends in Engineering, 1 (3), 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  21. ^ F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz & R. Dillmann ((Ed.)), "Automatic Liver Segmentation Using the Random Walker Algorithm" (PDF), Bildverarbeitung für die Medizin 2008, ISBN 978-3-540-78640-5 [ölü/kırık bağlantı]
  22. ^ P. Wighton, M. Sadeghi, T. K. Lee & M. S. Atkins (2009), "A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting" (PDF), Proceedings of MICCAI 2009, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  23. ^ P. Wattuya, K. Rothaus, J. S. Prassni & X. Jiang (2008), "A random walker based approach to combining multiple segmentations" (PDF), Proceedings of ICPR 2008 
  24. ^ Y.-K. Lai, S.-M. Hu, R. R. Martin & P. L. Rosin (2008), "Fast mesh segmentation using random walks" (PDF), Proceedings of the 2008 ACM symposium on Solid and physical modeling, 2 Aralık 2020 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  25. ^ J. Zhang, J. Zheng & J. Cai (2010), "Interactive Mesh Cutting Using Constrained Random Walks", IEEE Trans. on Visualization and Computer Graphics, 27 Haziran 2021 tarihinde kaynağından arşivlendi, erişim tarihi: 27 Haziran 2021 
  26. ^ X. Sun, P. L. Rosin, R. R. Martin & F. C. Langbein (Ekim 2008), "Random walks for feature-preserving mesh denoising" (PDF), Computer Aided Geometric Design, 25 (7), ss. 437-456, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  27. ^ L. Grady & G. Funka-Lea (2006), "An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes" (PDF), Proceedings of MICCAI, 2, ss. 888-895, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 
  28. ^ G. Li, L. Qingsheng & Q. Xiaoxu (2008), "Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features", Proceedings of IITA 2008 
  29. ^ R. Shen, I. Cheng, X. Li & A. Basu (2008), "Stereo matching using random walks" (PDF), Proceedings of ICPR 2008, 27 Haziran 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 27 Haziran 2021 

Ek bağlantılar değiştir