Random walker algorithm - Revision history

HDSQ: #suggestededit-add-desc 1.0

2024-01-06T08:37:35Z

#suggestededit-add-desc 1.0

← Previous revision		Revision as of 08:37, 6 January 2024
Line 1:		Line 1:
			{{Short description\|Image segmentation algorithm}}
	The '''random walker algorithm''' is an algorithm for [[image segmentation]]. In the first description of the algorithm,<ref name="grady2006random">Grady, L.: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf Random walks for image segmentation]". PAMI, 2006</ref> a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. These probabilities may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a [[Graph (discrete mathematics)\|graph]], in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs<ref>P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984</ref>).		The '''random walker algorithm''' is an algorithm for [[image segmentation]]. In the first description of the algorithm,<ref name="grady2006random">Grady, L.: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf Random walks for image segmentation]". PAMI, 2006</ref> a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. These probabilities may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a [[Graph (discrete mathematics)\|graph]], in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs<ref>P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984</ref>).

InternetArchiveBot: Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5) (AManWithNoPlan - 15896

2023-10-26T17:25:07Z

Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5) (AManWithNoPlan - 15896

← Previous revision		Revision as of 17:25, 26 October 2023
Line 74:		Line 74:
	* Segmentation editing<ref>L. Grady, G. Funka-Lea: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes]", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895</ref>		* Segmentation editing<ref>L. Grady, G. Funka-Lea: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes]", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895</ref>
	* Shadow elimination<ref>G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008</ref>		* Shadow elimination<ref>G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008</ref>
	* Stereo matching (i.e., one-dimensional [[image registration]])<ref>R. Shen, I. Cheng, X. Li, A. Basu: [https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf Stereo matching using random walks], Proc. of ICPR 2008</ref>		* Stereo matching (i.e., one-dimensional [[image registration]])<ref>R. Shen, I. Cheng, X. Li, A. Basu: [https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf Stereo matching using random walks] {{Webarchive\|url=https://web.archive.org/web/20210627220647/https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf \|date=2021-06-27 }}, Proc. of ICPR 2008</ref>
	* Image fusion <ref name="shen2011" /><ref name="shen2013" />		* Image fusion <ref name="shen2011" /><ref name="shen2013" />

InternetArchiveBot: Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.9.3) (Phuzion - 12296

2023-02-22T05:34:36Z

Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.9.3) (Phuzion - 12296

← Previous revision		Revision as of 05:34, 22 February 2023
Line 51:		Line 51:

	* Random walks with restart<ref>T. H. Kim, K. M. Lee, S. U. Lee: [https://pdfs.semanticscholar.org/080f/f994ebb101ac340e446344215f834eae0f6c.pdf Generative Image Segmentation Using Random Walks with Restart], Proc. of ECCV 2008, pp. 264–275</ref>		* Random walks with restart<ref>T. H. Kim, K. M. Lee, S. U. Lee: [https://pdfs.semanticscholar.org/080f/f994ebb101ac340e446344215f834eae0f6c.pdf Generative Image Segmentation Using Random Walks with Restart], Proc. of ECCV 2008, pp. 264–275</ref>
	* Alpha matting<ref>J. Wang, M. Agrawala, M. F. Cohen: [http://kucg.korea.ac.kr/new/seminar/2009/src/PA-09-11-25.pdf Soft scissors: an interactive tool for realtime high quality matting], Proc. of SIGGRAPH 2007</ref>		* Alpha matting<ref>J. Wang, M. Agrawala, M. F. Cohen: [http://kucg.korea.ac.kr/new/seminar/2009/src/PA-09-11-25.pdf Soft scissors: an interactive tool for realtime high quality matting] {{Webarchive\|url=https://web.archive.org/web/20210627220651/http://kucg.korea.ac.kr/new/seminar/2009/src/PA-09-11-25.pdf \|date=2021-06-27 }}, Proc. of SIGGRAPH 2007</ref>
	* Threshold selection<ref>S. Rysavy, A. Flores, R. Enciso, K. Okada: [http://bidal.sfsu.edu/~kazokada/research/okada_icpr08_dentalcad.pdf Classifiability Criteria for Refining of Random Walks Segmentation], Proc. of ICPR 2008</ref>		* Threshold selection<ref>S. Rysavy, A. Flores, R. Enciso, K. Okada: [http://bidal.sfsu.edu/~kazokada/research/okada_icpr08_dentalcad.pdf Classifiability Criteria for Refining of Random Walks Segmentation], Proc. of ICPR 2008</ref>
	* Soft inputs<ref>W. Yang, J. Cai, J. Zheng, J. Luo: [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 User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs], IEEE Trans. on Image Proc., 2010</ref>		* Soft inputs<ref>W. Yang, J. Cai, J. Zheng, J. Luo: [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 User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs], IEEE Trans. on Image Proc., 2010</ref>
Line 85:		Line 85:
	*[https://web.archive.org/web/20110719090821/http://leogrady.net/wp-content/uploads/2017/01/random_walker_matlab_code.zip Matlab code implementing the original random walker algorithm]		*[https://web.archive.org/web/20110719090821/http://leogrady.net/wp-content/uploads/2017/01/random_walker_matlab_code.zip Matlab code implementing the original random walker algorithm]
	*[http://fastrw.cs.sfu.ca/ Matlab code implementing the random walker algorithm with precomputation]		*[http://fastrw.cs.sfu.ca/ Matlab code implementing the random walker algorithm with precomputation]
	*[http://scikit-image.org/docs/dev/auto_examples/plot_random_walker_segmentation.html Python implementation of the original random walker algorithm] in the image processing toolbox [http://scikit-image.org/ scikit-image]		*[http://scikit-image.org/docs/dev/auto_examples/plot_random_walker_segmentation.html Python implementation of the original random walker algorithm] {{Webarchive\|url=https://web.archive.org/web/20121014010623/http://scikit-image.org/docs/dev/auto_examples/plot_random_walker_segmentation.html \|date=2012-10-14 }} in the image processing toolbox [http://scikit-image.org/ scikit-image]

	[[Category:Image segmentation]]		[[Category:Image segmentation]]

GreenC bot: Rescued 1 archive link; reformat 1 link. Wayback Medic 2.5

2022-07-18T00:15:21Z

Rescued 1 archive link; reformat 1 link. Wayback Medic 2.5

← Previous revision		Revision as of 00:15, 18 July 2022
Line 68:		Line 68:
	* Image Colorization<ref>X. Liu, J. Liu, Z. Feng: [https://link.springer.com/chapter/10.1007/978-3-642-03767-2_57 Colorization Using Segmentation with Random Walk], Computer Analysis of Images and Patterns, pp. 468–475, 2009</ref>		* Image Colorization<ref>X. Liu, J. Liu, Z. Feng: [https://link.springer.com/chapter/10.1007/978-3-642-03767-2_57 Colorization Using Segmentation with Random Walk], Computer Analysis of Images and Patterns, pp. 468–475, 2009</ref>
	* Interactive rotoscoping<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5202749/ Interactive rotoscoping through scale-space random walks], Proc. of the 2009 IEEE international conference on Multimedia and Expo</ref>		* Interactive rotoscoping<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5202749/ Interactive rotoscoping through scale-space random walks], Proc. of the 2009 IEEE international conference on Multimedia and Expo</ref>
	* Medical image segmentation<ref>S. P. Dakua, J. S. Sahambi: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.8840&rep=rep1&type=pdf LV Contour Extraction from Cardiac MR Images Using Random Walks Approach], Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009</ref><ref>F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: [http://www.academia.edu/download/44022280/p056.pdf Automatic Liver Segmentation Using the Random Walker Algorithm], Bildverarbeitung für die Medizin 2008</ref><ref>P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: [https://link.springer.com/content/pdf/10.1007/978-3-642-04271-3_134.pdf A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting], Proc. of MICCAI 2009</ref>		* Medical image segmentation<ref>S. P. Dakua, J. S. Sahambi: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.8840&rep=rep1&type=pdf LV Contour Extraction from Cardiac MR Images Using Random Walks Approach], Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009</ref><ref>F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: [http://www.academia.edu/download/44022280/p056.pdf Automatic Liver Segmentation Using the Random Walker Algorithm]{{dead link\|date=July 2022\|bot=medic}}{{cbignore\|bot=medic}}, Bildverarbeitung für die Medizin 2008</ref><ref>P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: [https://link.springer.com/content/pdf/10.1007/978-3-642-04271-3_134.pdf A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting], Proc. of MICCAI 2009</ref>
	* Merging multiple segmentations<ref>P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: [https://www.researchgate.net/profile/Xiaoyi_Jiang2/publication/220930791_A_Random_Walker_Based_Approach_to_Combining_Multiple_Segmentations/links/02bfe5110dd88cde72000000.pdf A random walker based approach to combining multiple segmentations], Proc. of ICPR 2008</ref>		* Merging multiple segmentations<ref>P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: [https://www.researchgate.net/profile/Xiaoyi_Jiang2/publication/220930791_A_Random_Walker_Based_Approach_to_Combining_Multiple_Segmentations/links/02bfe5110dd88cde72000000.pdf A random walker based approach to combining multiple segmentations], Proc. of ICPR 2008</ref>
	* Mesh segmentation<ref>Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: [https://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/segmentation-SPM.pdf Fast mesh segmentation using random walks], Proc. of the 2008 ACM symposium on Solid and physical modeling</ref><ref>J. Zhang, J. Zheng, J. Cai: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4665&rep=rep1&type=pdf Interactive Mesh Cutting Using Constrained Random Walks], IEEE Trans. on Visualization and Computer Graphics, 2010.</ref>		* Mesh segmentation<ref>Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: [https://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/segmentation-SPM.pdf Fast mesh segmentation using random walks], Proc. of the 2008 ACM symposium on Solid and physical modeling</ref><ref>J. Zhang, J. Zheng, J. Cai: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4665&rep=rep1&type=pdf Interactive Mesh Cutting Using Constrained Random Walks], IEEE Trans. on Visualization and Computer Graphics, 2010.</ref>

Loew Galitz at 05:47, 31 March 2022

2022-03-31T05:47:39Z

← Previous revision		Revision as of 05:47, 31 March 2022
Line 1:		Line 1:
	The '''random walker algorithm''' is an algorithm for [[image segmentation]]. In the first description of the algorithm,<ref name="grady2006random">Grady, L.: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf Random walks for image segmentation]". PAMI, 2006</ref> a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. These probabilities may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a [[Graph (discrete mathematics)\|graph]], in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs<ref>P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984</ref>).		The '''random walker algorithm''' is an algorithm for [[image segmentation]]. In the first description of the algorithm,<ref name="grady2006random">Grady, L.: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006random.pdf Random walks for image segmentation]". PAMI, 2006</ref> a user interactively labels a small number of pixels with known labels (called seeds), e.g., "object" and "background". The unlabeled pixels are each imagined to release a random walker, and the probability is computed that each pixel's random walker first arrives at a seed bearing each label, i.e., if a user places K seeds, each with a different label, then it is necessary to compute, for each pixel, the probability that a random walker leaving the pixel will first arrive at each seed. These probabilities may be determined analytically by solving a system of linear equations. After computing these probabilities for each pixel, the pixel is assigned to the label for which it is most likely to send a random walker. The image is modeled as a [[Graph (discrete mathematics)\|graph]], in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels. Therefore, the random walk occurs on the weighted graph (see Doyle and Snell for an introduction to random walks on graphs<ref>P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984</ref>).

	Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a data fidelity term (e.g., an intensity prior).<ref name="grady2005multilabel">Leo Grady: "[http://leogrady.net/wp-content/uploads/2017/01/grady2005multilabel.pdf Multilabel Random Walker Image Segmentation Using Prior Models]", Proc. of CVPR, Vol. 1, pp. 763–770, 2005.</ref> It has also been extended to other applications.		Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a [[data fidelity]] term (e.g., an intensity prior).<ref name="grady2005multilabel">Leo Grady: "[http://leogrady.net/wp-content/uploads/2017/01/grady2005multilabel.pdf Multilabel Random Walker Image Segmentation Using Prior Models]", Proc. of CVPR, Vol. 1, pp. 763–770, 2005.</ref> It has also been extended to other applications.

	The algorithm was initially published by [http://leogrady.net/ Leo Grady] as a conference paper<ref>Leo Grady, Gareth Funka-Lea: [http://leogrady.net/wp-content/uploads/2017/01/grady2004multilabel.pdf 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.</ref> and later as a journal paper.<ref name="grady2006random" />		The algorithm was initially published by [http://leogrady.net/ Leo Grady] as a conference paper<ref>Leo Grady, Gareth Funka-Lea: [http://leogrady.net/wp-content/uploads/2017/01/grady2004multilabel.pdf 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.</ref> and later as a journal paper.<ref name="grady2006random" />

SdkbBot: /* Extensions */General fixes, removed erroneous space

2021-06-29T03:39:05Z

Extensions: General fixes, removed erroneous space

← Previous revision		Revision as of 03:39, 29 June 2021
Line 56:		Line 56:
	* Run on a presegmented image<ref>C. Chefd'hotel, A. Sebbane: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.6511&rep=rep1&type=pdf Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation], Proc. of ICV 2007</ref>		* Run on a presegmented image<ref>C. Chefd'hotel, A. Sebbane: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.6511&rep=rep1&type=pdf Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation], Proc. of ICV 2007</ref>
	* Scale space random walk<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5201062/ Image segmentation using scale-space random walks], Proc. of the 16th international conference on Digital Signal Processing, pp. 458–461, 2009</ref>		* Scale space random walk<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5201062/ Image segmentation using scale-space random walks], Proc. of the 16th international conference on Digital Signal Processing, pp. 458–461, 2009</ref>
	* Fast random walker using offline [[precomputation]] <ref>L. Grady, A.K. Sinop, "[http://leogrady.net/wp-content/uploads/2017/01/grady2008fast.pdf Fast approximate random walker segmentation using eigenvector precomputation]". In IEEE Conf. CVPR, pp. 1–8, 2008</ref><ref>S. Andrews, G. Hamarneh, A. Saad. [https://link.springer.com/content/pdf/10.1007/978-3-642-15711-0_2.pdf Fast random walker with priors using precomputation for interactive medical image segmentation], Proc. of MICCAI 2010</ref>		* Fast random walker using offline [[precomputation]]<ref>L. Grady, A.K. Sinop, "[http://leogrady.net/wp-content/uploads/2017/01/grady2008fast.pdf Fast approximate random walker segmentation using eigenvector precomputation]". In IEEE Conf. CVPR, pp. 1–8, 2008</ref><ref>S. Andrews, G. Hamarneh, A. Saad. [https://link.springer.com/content/pdf/10.1007/978-3-642-15711-0_2.pdf Fast random walker with priors using precomputation for interactive medical image segmentation], Proc. of MICCAI 2010</ref>
	* Generalized random walks allowing flexible compatibility functions <ref name="shen2011">R. Shen, I. Cheng, J. Shi, A. Basu: [https://ieeexplore.ieee.org/abstract/document/5762601/ Generalized Random Walks for Fusion of Multi-exposure Images], IEEE Trans. on Image Processing, 2011.</ref>		* Generalized random walks allowing flexible compatibility functions <ref name="shen2011">R. Shen, I. Cheng, J. Shi, A. Basu: [https://ieeexplore.ieee.org/abstract/document/5762601/ Generalized Random Walks for Fusion of Multi-exposure Images], IEEE Trans. on Image Processing, 2011.</ref>
	* Power watersheds unifying graph cuts, random walker and shortest path <ref>Camille Couprie, Leo Grady, Laurent Najman and Hugues Talbot, "[http://leogrady.net/wp-content/uploads/2017/01/couprie2011power.pdf 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</ref>		* Power watersheds unifying graph cuts, random walker and shortest path <ref>Camille Couprie, Leo Grady, Laurent Najman and Hugues Talbot, "[http://leogrady.net/wp-content/uploads/2017/01/couprie2011power.pdf 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</ref>

Jarble: linking

2019-09-09T21:56:58Z

linking

← Previous revision		Revision as of 21:56, 9 September 2019
Line 74:		Line 74:
	* Segmentation editing<ref>L. Grady, G. Funka-Lea: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes]", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895</ref>		* Segmentation editing<ref>L. Grady, G. Funka-Lea: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes]", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895</ref>
	* Shadow elimination<ref>G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008</ref>		* Shadow elimination<ref>G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008</ref>
	* Stereo matching (i.e., one-dimensional image registration)<ref>R. Shen, I. Cheng, X. Li, A. Basu: [https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf Stereo matching using random walks], Proc. of ICPR 2008</ref>		* Stereo matching (i.e., one-dimensional [[image registration]])<ref>R. Shen, I. Cheng, X. Li, A. Basu: [https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf Stereo matching using random walks], Proc. of ICPR 2008</ref>
	* Image fusion <ref name="shen2011" /><ref name="shen2013" />		* Image fusion <ref name="shen2011" /><ref name="shen2013" />

72.174.72.232: /* Mathematics */

2019-07-04T16:08:05Z

Mathematics

← Previous revision		Revision as of 16:08, 4 July 2019
Line 7:		Line 7:
	==Mathematics==		==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 of a graph\|Laplacian matrix]], which we may represent with the variable <math>L</math>. 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).		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 of a graph\|Laplacian matrix]], which we may represent with the variable <math>L</math>. 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 (discrete mathematics)\|graph]], with each node <math>v_i</math> associated with a pixel and each edge <math>e_{ij}</math> connecting neighboring pixels <math>v_i</math> and <math>v_j</math>. 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 <math>g_i</math> at node <math>v_i</math>, it is common to use the edge weighting function		Assume that the image is represented by a [[Graph (discrete mathematics)\|graph]], with each node <math>v_i</math> associated with a pixel and each edge <math>e_{ij}</math> connecting neighboring pixels <math>v_i</math> and <math>v_j</math>. 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 <math>g_i</math> at node <math>v_i</math>, it is common to use the edge weighting function

Jarble: fixed a typo

2019-05-27T21:46:03Z

fixed a typo

← Previous revision		Revision as of 21:46, 27 May 2019
Line 68:		Line 68:
	* Image Colorization<ref>X. Liu, J. Liu, Z. Feng: [https://link.springer.com/chapter/10.1007/978-3-642-03767-2_57 Colorization Using Segmentation with Random Walk], Computer Analysis of Images and Patterns, pp. 468–475, 2009</ref>		* Image Colorization<ref>X. Liu, J. Liu, Z. Feng: [https://link.springer.com/chapter/10.1007/978-3-642-03767-2_57 Colorization Using Segmentation with Random Walk], Computer Analysis of Images and Patterns, pp. 468–475, 2009</ref>
	* Interactive rotoscoping<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5202749/ Interactive rotoscoping through scale-space random walks], Proc. of the 2009 IEEE international conference on Multimedia and Expo</ref>		* Interactive rotoscoping<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5202749/ Interactive rotoscoping through scale-space random walks], Proc. of the 2009 IEEE international conference on Multimedia and Expo</ref>
	* Medical image segmentation<ref>S. P. Dakua, J. S. Sahambi: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.8840&rep=rep1&type=pdf LV Contour Extraction from Cardiac MR		* Medical image segmentation<ref>S. P. Dakua, J. S. Sahambi: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.8840&rep=rep1&type=pdf LV Contour Extraction from Cardiac MR Images Using Random Walks Approach], Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009</ref><ref>F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: [http://www.academia.edu/download/44022280/p056.pdf Automatic Liver Segmentation Using the Random Walker Algorithm], Bildverarbeitung für die Medizin 2008</ref><ref>P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: [https://link.springer.com/content/pdf/10.1007/978-3-642-04271-3_134.pdf A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting], Proc. of MICCAI 2009</ref>
	Images Using Random Walks Approach], Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009</ref><ref>F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: [http://www.academia.edu/download/44022280/p056.pdf Automatic Liver Segmentation Using the Random Walker Algorithm], Bildverarbeitung für die Medizin 2008</ref><ref>P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: [https://link.springer.com/content/pdf/10.1007/978-3-642-04271-3_134.pdf A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting], Proc. of MICCAI 2009</ref>
	* Merging multiple segmentations<ref>P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: [https://www.researchgate.net/profile/Xiaoyi_Jiang2/publication/220930791_A_Random_Walker_Based_Approach_to_Combining_Multiple_Segmentations/links/02bfe5110dd88cde72000000.pdf A random walker based approach to combining multiple segmentations], Proc. of ICPR 2008</ref>		* Merging multiple segmentations<ref>P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: [https://www.researchgate.net/profile/Xiaoyi_Jiang2/publication/220930791_A_Random_Walker_Based_Approach_to_Combining_Multiple_Segmentations/links/02bfe5110dd88cde72000000.pdf A random walker based approach to combining multiple segmentations], Proc. of ICPR 2008</ref>
	* Mesh segmentation<ref>Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: [https://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/segmentation-SPM.pdf Fast mesh segmentation using random walks], Proc. of the 2008 ACM symposium on Solid and physical modeling</ref><ref>J. Zhang, J. Zheng, J. Cai: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4665&rep=rep1&type=pdf Interactive Mesh Cutting Using Constrained Random Walks], IEEE Trans. on Visualization and Computer Graphics, 2010.</ref>		* Mesh segmentation<ref>Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: [https://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/segmentation-SPM.pdf Fast mesh segmentation using random walks], Proc. of the 2008 ACM symposium on Solid and physical modeling</ref><ref>J. Zhang, J. Zheng, J. Cai: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4665&rep=rep1&type=pdf Interactive Mesh Cutting Using Constrained Random Walks], IEEE Trans. on Visualization and Computer Graphics, 2010.</ref>

Jarble: adding links to references using Google Scholar

2019-05-27T21:45:24Z

adding links to references using Google Scholar

← Previous revision		Revision as of 21:45, 27 May 2019
Line 3:		Line 3:
	Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a data fidelity term (e.g., an intensity prior).<ref name="grady2005multilabel">Leo Grady: "[http://leogrady.net/wp-content/uploads/2017/01/grady2005multilabel.pdf Multilabel Random Walker Image Segmentation Using Prior Models]", Proc. of CVPR, Vol. 1, pp. 763–770, 2005.</ref> It has also been extended to other applications.		Although the initial algorithm was formulated as an interactive method for image segmentation, it has been extended to be a fully automatic algorithm, given a data fidelity term (e.g., an intensity prior).<ref name="grady2005multilabel">Leo Grady: "[http://leogrady.net/wp-content/uploads/2017/01/grady2005multilabel.pdf Multilabel Random Walker Image Segmentation Using Prior Models]", Proc. of CVPR, Vol. 1, pp. 763–770, 2005.</ref> It has also been extended to other applications.

	The algorithm was initially published by [http://leogrady.net/ Leo Grady] as a conference paper<ref>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.</ref> and later as a journal paper.<ref name="grady2006random" />		The algorithm was initially published by [http://leogrady.net/ Leo Grady] as a conference paper<ref>Leo Grady, Gareth Funka-Lea: [http://leogrady.net/wp-content/uploads/2017/01/grady2004multilabel.pdf 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.</ref> and later as a journal paper.<ref name="grady2006random" />

	==Mathematics==		==Mathematics==
Line 50:		Line 50:
	The traditional random walker algorithm described above has been extended in several ways:		The traditional random walker algorithm described above has been extended in several ways:

	* Random walks with restart<ref>T. H. Kim, K. M. Lee, S. U. Lee: Generative Image Segmentation Using Random Walks with Restart, Proc. of ECCV 2008, pp. 264–275</ref>		* Random walks with restart<ref>T. H. Kim, K. M. Lee, S. U. Lee: [https://pdfs.semanticscholar.org/080f/f994ebb101ac340e446344215f834eae0f6c.pdf Generative Image Segmentation Using Random Walks with Restart], Proc. of ECCV 2008, pp. 264–275</ref>
	* Alpha matting<ref>J. Wang, M. Agrawala, M. F. Cohen: Soft scissors: an interactive tool for realtime high quality matting, Proc. of SIGGRAPH 2007</ref>		* Alpha matting<ref>J. Wang, M. Agrawala, M. F. Cohen: [http://kucg.korea.ac.kr/new/seminar/2009/src/PA-09-11-25.pdf Soft scissors: an interactive tool for realtime high quality matting], Proc. of SIGGRAPH 2007</ref>
	* Threshold selection<ref>S. Rysavy, A. Flores, R. Enciso, K. Okada: Classifiability Criteria for Refining of Random Walks Segmentation, Proc. of ICPR 2008</ref>		* Threshold selection<ref>S. Rysavy, A. Flores, R. Enciso, K. Okada: [http://bidal.sfsu.edu/~kazokada/research/okada_icpr08_dentalcad.pdf Classifiability Criteria for Refining of Random Walks Segmentation], Proc. of ICPR 2008</ref>
	* Soft inputs<ref>W. Yang, J. Cai, J. Zheng, J. Luo: User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs, IEEE Trans. on Image Proc., 2010</ref>		* Soft inputs<ref>W. Yang, J. Cai, J. Zheng, J. Luo: [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 User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs], IEEE Trans. on Image Proc., 2010</ref>
	* Run on a presegmented image<ref>C. Chefd'hotel, A. Sebbane: Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation, Proc. of ICV 2007</ref>		* Run on a presegmented image<ref>C. Chefd'hotel, A. Sebbane: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.6511&rep=rep1&type=pdf Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation], Proc. of ICV 2007</ref>
	* Scale space random walk<ref>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</ref>		* Scale space random walk<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5201062/ Image segmentation using scale-space random walks], Proc. of the 16th international conference on Digital Signal Processing, pp. 458–461, 2009</ref>
	* Fast random walker using offline [[precomputation]] <ref>L. Grady, A.K. Sinop, "[http://leogrady.net/wp-content/uploads/2017/01/grady2008fast.pdf Fast approximate random walker segmentation using eigenvector precomputation]". In IEEE Conf. CVPR, pp. 1–8, 2008</ref><ref>S. Andrews, G. Hamarneh, A. Saad. Fast random walker with priors using precomputation for interactive medical image segmentation, Proc. of MICCAI 2010</ref>		* Fast random walker using offline [[precomputation]] <ref>L. Grady, A.K. Sinop, "[http://leogrady.net/wp-content/uploads/2017/01/grady2008fast.pdf Fast approximate random walker segmentation using eigenvector precomputation]". In IEEE Conf. CVPR, pp. 1–8, 2008</ref><ref>S. Andrews, G. Hamarneh, A. Saad. [https://link.springer.com/content/pdf/10.1007/978-3-642-15711-0_2.pdf Fast random walker with priors using precomputation for interactive medical image segmentation], Proc. of MICCAI 2010</ref>
	* Generalized random walks allowing flexible compatibility functions <ref name="shen2011">R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011.</ref>		* Generalized random walks allowing flexible compatibility functions <ref name="shen2011">R. Shen, I. Cheng, J. Shi, A. Basu: [https://ieeexplore.ieee.org/abstract/document/5762601/ Generalized Random Walks for Fusion of Multi-exposure Images], IEEE Trans. on Image Processing, 2011.</ref>
	* Power watersheds unifying graph cuts, random walker and shortest path <ref>Camille Couprie, Leo Grady, Laurent Najman and Hugues Talbot, "[http://leogrady.net/wp-content/uploads/2017/01/couprie2011power.pdf 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</ref>		* Power watersheds unifying graph cuts, random walker and shortest path <ref>Camille Couprie, Leo Grady, Laurent Najman and Hugues Talbot, "[http://leogrady.net/wp-content/uploads/2017/01/couprie2011power.pdf 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</ref>
	* Random walker watersheds <ref>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</ref>		* Random walker watersheds <ref>S. Ram, J. J. Rodriguez: [https://ieeexplore.ieee.org/abstract/document/6637896/ 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</ref>
	* Multivariate Gaussian conditional random field <ref name="shen2013">R. Shen, I. Cheng, A. Basu: QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF, IEEE Trans. on Image Processing, 2013.</ref>		* Multivariate Gaussian conditional random field <ref name="shen2013">R. Shen, I. Cheng, A. Basu: [https://ieeexplore.ieee.org/abstract/document/6392943/ QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF], IEEE Trans. on Image Processing, 2013.</ref>

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

	* Image Colorization<ref>X. Liu, J. Liu, Z. Feng: Colorization Using Segmentation with Random Walk, Computer Analysis of Images and Patterns, pp. 468–475, 2009</ref>		* Image Colorization<ref>X. Liu, J. Liu, Z. Feng: [https://link.springer.com/chapter/10.1007/978-3-642-03767-2_57 Colorization Using Segmentation with Random Walk], Computer Analysis of Images and Patterns, pp. 468–475, 2009</ref>
	* Interactive rotoscoping<ref>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</ref>		* Interactive rotoscoping<ref>R. Rzeszutek, T. El-Maraghi, D. Androutsos: [https://ieeexplore.ieee.org/abstract/document/5202749/ Interactive rotoscoping through scale-space random walks], Proc. of the 2009 IEEE international conference on Multimedia and Expo</ref>
	* Medical image segmentation<ref>S. P. Dakua, J. S. Sahambi: LV Contour Extraction from Cardiac MR		* Medical image segmentation<ref>S. P. Dakua, J. S. Sahambi: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.381.8840&rep=rep1&type=pdf LV Contour Extraction from Cardiac MR
	Images Using Random Walks Approach, Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009</ref><ref>F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: Automatic Liver Segmentation Using the Random Walker Algorithm, Bildverarbeitung für die Medizin 2008</ref><ref>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</ref>		Images Using Random Walks Approach], Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009</ref><ref>F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: [http://www.academia.edu/download/44022280/p056.pdf Automatic Liver Segmentation Using the Random Walker Algorithm], Bildverarbeitung für die Medizin 2008</ref><ref>P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: [https://link.springer.com/content/pdf/10.1007/978-3-642-04271-3_134.pdf A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting], Proc. of MICCAI 2009</ref>
	* Merging multiple segmentations<ref>P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: A random walker based approach to combining multiple segmentations, Proc. of ICPR 2008</ref>		* Merging multiple segmentations<ref>P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: [https://www.researchgate.net/profile/Xiaoyi_Jiang2/publication/220930791_A_Random_Walker_Based_Approach_to_Combining_Multiple_Segmentations/links/02bfe5110dd88cde72000000.pdf A random walker based approach to combining multiple segmentations], Proc. of ICPR 2008</ref>
	* Mesh segmentation<ref>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</ref><ref>J. Zhang, J. Zheng, J. Cai: Interactive Mesh Cutting Using Constrained Random Walks, IEEE Trans. on Visualization and Computer Graphics, 2010.</ref>		* Mesh segmentation<ref>Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: [https://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/segmentation-SPM.pdf Fast mesh segmentation using random walks], Proc. of the 2008 ACM symposium on Solid and physical modeling</ref><ref>J. Zhang, J. Zheng, J. Cai: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.190.4665&rep=rep1&type=pdf Interactive Mesh Cutting Using Constrained Random Walks], IEEE Trans. on Visualization and Computer Graphics, 2010.</ref>
	* Mesh denoising<ref>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</ref>		* Mesh denoising<ref>X. Sun, P. L. Rosin, R. R. Martin, F. C. Langbein: [http://users.cs.cardiff.ac.uk/Paul.Rosin/resources/papers/denoise-CAGD-postprint.pdf Random walks for feature-preserving mesh denoising], Computer Aided Geometric Design, Vol. 25, No. 7, Oct. 2008, pp. 437–456</ref>
	* Segmentation editing<ref>L. Grady, G. Funka-Lea: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes]", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895</ref>		* Segmentation editing<ref>L. Grady, G. Funka-Lea: "[http://leogrady.net/wp-content/uploads/2017/01/grady2006energy.pdf An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes]", Proc. of MICCAI, Vol. 2, 2006, pp. 888–895</ref>
	* Shadow elimination<ref>G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008</ref>		* Shadow elimination<ref>G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008</ref>
	* Stereo matching (i.e., one-dimensional image registration)<ref>R. Shen, I. Cheng, X. Li, A. Basu: Stereo matching using random walks, Proc. of ICPR 2008</ref>		* Stereo matching (i.e., one-dimensional image registration)<ref>R. Shen, I. Cheng, X. Li, A. Basu: [https://sites.ualberta.ca/~rshen/files/2008ICPR_RuiSHEN.pdf Stereo matching using random walks], Proc. of ICPR 2008</ref>
	* Image fusion <ref name="shen2011" /><ref name="shen2013" />		* Image fusion <ref name="shen2011" /><ref name="shen2013" />