• Images
• Videos
• Documents
• Books
• Articles

Mathematics

Although the algorithm was described in terms of random walks, the probability that each node sends a random walker to the seeds may be calculated analytically by solving a sparse, positive-definite system of linear equations with the graph Laplacian matrix, which we may represent with the variable L {\displaystyle L} . The algorithm was shown to apply to an arbitrary number of labels (objects), but the exposition here is in terms of two labels (for simplicity of exposition).

Assume that the image is represented by a graph, with each node v i {\displaystyle v_{i}} associated with a pixel and each edge e i j {\displaystyle e_{ij}} connecting neighboring pixels v i {\displaystyle v_{i}} and v j {\displaystyle v_{j}} . The edge weights are used to encode node similarity, which may be derived from differences in image intensity, color, texture or any other meaningful features. For example, using image intensity g i {\displaystyle g_{i}} at node v i {\displaystyle v_{i}} , it is common to use the edge weighting function

w i j = exp ⁡ ( − β ( g i − g j ) 2 ) . {\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}

The nodes, edges and weights can then be used to construct the graph Laplacian matrix.

The random walker algorithm optimizes the energy

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

where x i {\displaystyle x_{i}} represents a real-valued variable associated with each node in the graph and the optimization is constrained by x i = 1 {\displaystyle x_{i}=1} for v i ∈ F {\displaystyle v_{i}\in F} and x i = 0 {\displaystyle x_{i}=0} for v i ∈ B {\displaystyle v_{i}\in B} , where F {\displaystyle F} and B {\displaystyle B} represent the sets of foreground and background seeds, respectively. If we let S {\displaystyle S} represent the set of nodes which are seeded (i.e., S = F ∪ B {\displaystyle S=F\cup B} ) and S ¯ {\displaystyle {\overline {S}}} represent the set of unseeded nodes (i.e., S ∪ S ¯ = V {\displaystyle S\cup {\overline {S}}=V} where V {\displaystyle V} is the set of all nodes), then the optimum of the energy minimization problem is given by the solution to

L S ¯ , S ¯ x S ¯ = − L S ¯ , S x S , {\displaystyle L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}

where the subscripts are used to indicate the portion of the graph Laplacian matrix L {\displaystyle L} indexed by the respective sets.

To incorporate likelihood (unary) terms into the algorithm, it was shown in ⁶ that one may optimize the energy

Q ( x ) = x T L x + γ ( ( 1 − x ) T F ( 1 − x ) + x T B x ) = ∑ e i j w i j ( x i − x j ) 2 + γ ( ∑ v i f i ( 1 − x i ) 2 + ∑ v i b i x i 2 ) , {\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),}

for positive, diagonal matrices F {\displaystyle F} and B {\displaystyle B} . Optimizing this energy leads to the system of linear equations

( L S ¯ , S ¯ + γ F S ¯ , S ¯ + γ B S ¯ , S ¯ ) x S ¯ = − L S ¯ , S x S − γ F S ¯ , S ¯ . {\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}}}.}

The set of seeded nodes, S {\displaystyle S} , may be empty in this case (i.e., S ¯ = V {\displaystyle {\overline {S}}=V} ), but the presence of the positive diagonal matrices allows for a unique solution to this linear system.

For example, if the likelihood/unary terms are used to incorporate a color model of the object, then f i {\displaystyle f_{i}} would represent the confidence that the color at node v i {\displaystyle v_{i}} would belong to object (i.e., a larger value of f i {\displaystyle f_{i}} indicates greater confidence that v i {\displaystyle v_{i}} belonged to the object label) and b i {\displaystyle b_{i}} would represent the confidence that the color at node v i {\displaystyle v_{i}} belongs to the background.

Algorithm interpretations

The random walker algorithm was initially motivated by labelling a pixel as object/background based on the probability that a random walker dropped at the pixel would first reach an object (foreground) seed or a background seed. However, there are several other interpretations of this same algorithm which have appeared in.⁷

Circuit theory interpretations

There are well-known connections between electrical circuit theory and random walks on graphs.⁸ Consequently, the random walker algorithm has two different interpretations in terms of an electric circuit. In both cases, the graph is viewed as an electric circuit in which each edge is replaced by a passive linear resistor. The resistance, r i j {\displaystyle r_{ij}} , associated with edge e i j {\displaystyle e_{ij}} is set equal to r i j = 1 w i j {\displaystyle r_{ij}={\frac {1}{w_{ij}}}} (i.e., the edge weight equals electrical conductance).

In the first interpretation, each node associated with a background seed, v i ∈ B {\displaystyle v_{i}\in B} , is tied directly to ground while each node associated with an object/foreground seed, v i ∈ F {\displaystyle v_{i}\in F} is attached to a unit direct current ideal voltage source tied to ground (i.e., to establish a unit potential at each v i ∈ F {\displaystyle v_{i}\in F} ). The steady-state electrical circuit potentials established at each node by this circuit configuration will exactly equal the random walker probabilities. Specifically, the electrical potential, x i {\displaystyle x_{i}} at node v i {\displaystyle v_{i}} will equal the probability that a random walker dropped at node v i {\displaystyle v_{i}} will reach an object/foreground node before reaching a background node.

In the second interpretation, labeling a node as object or background by thresholding the random walker probability at 0.5 is equivalent to labeling a node as object or background based on the relative effective conductance between the node and the object or background seeds. Specifically, if a node has a higher effective conductance (lower effective resistance) to the object seeds than to the background seeds, then node is labeled as object. If a node has a higher effective conductance (lower effective resistance) to the background seeds than to the object seeds, then node is labeled as background.

Extensions

The traditional random walker algorithm described above has been extended in several ways:

• Random walks with restart⁹
• Alpha matting¹⁰
• Threshold selection¹¹
• Soft inputs¹²
• Run on a presegmented image¹³
• Scale space random walk¹⁴
• Fast random walker using offline precomputation¹⁵¹⁶
• Generalized random walks allowing flexible compatibility functions ¹⁷
• Power watersheds unifying graph cuts, random walker and shortest path ¹⁸
• Random walker watersheds ¹⁹
• Multivariate Gaussian conditional random field ²⁰

Applications

Beyond image segmentation, the random walker algorithm or its extensions has been additionally applied to several problems in computer vision and graphics:

• Image Colorization²¹
• Interactive rotoscoping²²
• Medical image segmentation²³²⁴²⁵
• Merging multiple segmentations²⁶
• Mesh segmentation²⁷²⁸
• Mesh denoising²⁹
• Segmentation editing³⁰
• Shadow elimination³¹
• Stereo matching (i.e., one-dimensional image registration)³²
• Image fusion ³³³⁴

External links

• Matlab code implementing the original random walker algorithm
• Matlab code implementing the random walker algorithm with precomputation
• Python implementation of the original random walker algorithm Archived 2012-10-14 at the Wayback Machine in the image processing toolbox scikit-image

References

1. Grady, L.: "Random walks for image segmentation". PAMI, 2006 http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf ↩

2. P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984 ↩

3. Leo Grady: "Multilabel Random Walker Image Segmentation Using Prior Models", Proc. of CVPR, Vol. 1, pp. 763–770, 2005. http://leogrady.net/wp-content/uploads/2017/01/grady2005multilabel.pdf ↩

4. Leo Grady, Gareth Funka-Lea: Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials, Proc. of the 8th ECCV Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, pp. 230–245, 2004. http://leogrady.net/wp-content/uploads/2017/01/grady2004multilabel.pdf ↩

5. Grady, L.: "Random walks for image segmentation". PAMI, 2006 http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf ↩

6. Leo Grady: "Multilabel Random Walker Image Segmentation Using Prior Models", Proc. of CVPR, Vol. 1, pp. 763–770, 2005. http://leogrady.net/wp-content/uploads/2017/01/grady2005multilabel.pdf ↩

7. Grady, L.: "Random walks for image segmentation". PAMI, 2006 http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf ↩

8. P. G. Doyle, J. L. Snell: Random Walks and Electrical Networks, Carus Mathematical Monographs, 1984 ↩

9. T. H. Kim, K. M. Lee, S. U. Lee: Generative Image Segmentation Using Random Walks with Restart, Proc. of ECCV 2008, pp. 264–275 https://pdfs.semanticscholar.org/080f/f994ebb101ac340e446344215f834eae0f6c.pdf ↩

10. J. Wang, M. Agrawala, M. F. Cohen: Soft scissors: an interactive tool for realtime high quality matting Archived 2021-06-27 at the Wayback Machine, Proc. of SIGGRAPH 2007 http://kucg.korea.ac.kr/new/seminar/2009/src/PA-09-11-25.pdf ↩

11. S. Rysavy, A. Flores, R. Enciso, K. Okada: Classifiability Criteria for Refining of Random Walks Segmentation, Proc. of ICPR 2008 http://bidal.sfsu.edu/~kazokada/research/okada_icpr08_dentalcad.pdf ↩

12. W. Yang, J. Cai, J. Zheng, J. Luo: User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs, IEEE Trans. on Image Proc., 2010 https://www.researchgate.net/profile/Jianfei_Cai/publication/45694526_User-Friendly_Interactive_Image_Segmentation_Through_Unified_Combinatorial_User_Inputs/links/00b49522aab2066d55000000/User-Friendly-Interactive-Image-Segmentation-Through-Unified-Combinatorial-User-Inputs.pdf ↩

13. C. Chefd'hotel, A. Sebbane: Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation, Proc. of ICV 2007 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.6511&rep=rep1&type=pdf ↩

14. R. Rzeszutek, T. El-Maraghi, D. Androutsos: Image segmentation using scale-space random walks, Proc. of the 16th international conference on Digital Signal Processing, pp. 458–461, 2009 https://ieeexplore.ieee.org/abstract/document/5201062/ ↩

15. L. Grady, A.K. Sinop, "Fast approximate random walker segmentation using eigenvector precomputation". In IEEE Conf. CVPR, pp. 1–8, 2008 http://leogrady.net/wp-content/uploads/2017/01/grady2008fast.pdf ↩

16. S. Andrews, G. Hamarneh, A. Saad. Fast random walker with priors using precomputation for interactive medical image segmentation, Proc. of MICCAI 2010 https://link.springer.com/content/pdf/10.1007/978-3-642-15711-0_2.pdf ↩

17. R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011. https://ieeexplore.ieee.org/abstract/document/5762601/ ↩

18. Camille Couprie, Leo Grady, Laurent Najman and Hugues Talbot, "Power Watersheds: A Unifying Graph-Based Optimization Framework”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, pp. 1384-1399, July 2011 http://leogrady.net/wp-content/uploads/2017/01/couprie2011power.pdf ↩

19. S. Ram, J. J. Rodriguez: Random Walker Watersheds: A New Image Segmentation Approach, in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 1473-1477, Vancouver, Canada, May 2013 https://ieeexplore.ieee.org/abstract/document/6637896/ ↩

20. R. Shen, I. Cheng, A. Basu: QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF, IEEE Trans. on Image Processing, 2013. https://ieeexplore.ieee.org/abstract/document/6392943/ ↩

21. X. Liu, J. Liu, Z. Feng: Colorization Using Segmentation with Random Walk, Computer Analysis of Images and Patterns, pp. 468–475, 2009 https://link.springer.com/chapter/10.1007/978-3-642-03767-2_57 ↩

22. R. Rzeszutek, T. El-Maraghi, D. Androutsos: Interactive rotoscoping through scale-space random walks, Proc. of the 2009 IEEE international conference on Multimedia and Expo https://ieeexplore.ieee.org/abstract/document/5202749/ ↩

23. S. P. Dakua, J. S. Sahambi: LV Contour Extraction from Cardiac MR Images Using Random Walks Approach, Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.8840&rep=rep1&type=pdf ↩

24. F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: Automatic Liver Segmentation Using the Random Walker Algorithm[dead link‍], Bildverarbeitung für die Medizin 2008 http://www.academia.edu/download/44022280/p056.pdf ↩

25. P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting, Proc. of MICCAI 2009 https://link.springer.com/content/pdf/10.1007/978-3-642-04271-3_134.pdf ↩

26. P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: A random walker based approach to combining multiple segmentations, Proc. of ICPR 2008 https://www.researchgate.net/profile/Xiaoyi_Jiang2/publication/220930791_A_Random_Walker_Based_Approach_to_Combining_Multiple_Segmentations/links/02bfe5110dd88cde72000000.pdf ↩

27. Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: Fast mesh segmentation using random walks, Proc. of the 2008 ACM symposium on Solid and physical modeling https://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/segmentation-SPM.pdf ↩

28. J. Zhang, J. Zheng, J. Cai: Interactive Mesh Cutting Using Constrained Random Walks, IEEE Trans. on Visualization and Computer Graphics, 2010. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4665&rep=rep1&type=pdf ↩

29. X. Sun, P. L. Rosin, R. R. Martin, F. C. Langbein: Random walks for feature-preserving mesh denoising, Computer Aided Geometric Design, Vol. 25, No. 7, Oct. 2008, pp. 437–456 http://users.cs.cardiff.ac.uk/Paul.Rosin/resources/papers/denoise-CAGD-postprint.pdf ↩

30. L. Grady, G. Funka-Lea: "An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895 http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf ↩

31. G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008 ↩

32. R. Shen, I. Cheng, X. Li, A. Basu: Stereo matching using random walks Archived 2021-06-27 at the Wayback Machine, Proc. of ICPR 2008 https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf ↩

33. R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011. https://ieeexplore.ieee.org/abstract/document/5762601/ ↩

34. R. Shen, I. Cheng, A. Basu: QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF, IEEE Trans. on Image Processing, 2013. https://ieeexplore.ieee.org/abstract/document/6392943/ ↩