Color wheel graphs of complex functions: Difference between revisions
en>Hmainsbot1 m →History: AWB general fixes and, delink dates per WP:DATELINK, WP:YEARLINK and MOS:UNLINKYEARS using AWB (8097) |
No edit summary |
||
Line 1: | Line 1: | ||
The '''random walker algorithm''' is an algorithm for [[image segmentation]]. In the first description of the algorithm,<ref name="grady2006random">L. Grady: [http://www.cns.bu.edu/~lgrady/grady2006random.pdf Random Walks for Image Segmentation], IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 28, No. 11, pp. 1768–1783, Nov., 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. This computation 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 (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: Multilabel Random Walker Image Segmentation Using Prior Models, Proc. of CVPR, Vol. 1, pp. 763–770, 2005. [http://www.cns.bu.edu/%7Elgrady/grady2005multilabel.pdf]</ref> It has also been extended to other applications, such as Image Matching (R. Shen, I. Cheng, X.li and A. Basu), ICPR 2008, and Image Fusion, (R. Shen, I. Cheng, J.Shi and A. Basu), IEEE Trans. on Image Processing, 2011, and other applications. | |||
The algorithm was initially published 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" /> | |||
==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). | |||
Assume that the image is represented by a [[Graph (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 | |||
:<math>w_{ij} = \exp{\left(-\beta (g_i - g_j)^2\right)}. | |||
</math> | |||
The nodes, edges and weights can then be used to construct the graph [[Laplacian matrix of a graph|Laplacian matrix]]. | |||
The random walker algorithm optimizes the energy | |||
:<math>Q(x) = x^T L x = \sum_{e_{ij}} w_{ij} \left(x_i - x_j\right)^2</math> | |||
where <math>x_i</math> represents a real-valued variable associated with each node in the graph and the optimization is constrained by <math>x_i = 1</math> for <math>v_i \in F</math> and <math>x_i = 0</math> for <math>v_i \in B</math>, where <math>F</math> and <math>B</math> represent the sets of foreground and background seeds, respectively. If we let <math>S</math> represent the set of nodes which are seeded (i.e., <math>S = F \cup B</math>) and <math>\overline{S}</math> represent the set of unseeded nodes (i.e., <math>S \cup \overline{S} = V</math> where <math>V</math> is the set of all nodes), then the optimum of the energy minimization problem is given by the solution to | |||
:<math> | |||
L_{\overline{S},\overline{S}} x_{\overline{S}} = - L_{\overline{S},S} x_{S}, | |||
</math> | |||
where the subscripts are used to indicate the portion of the graph Laplacian matrix <math>L</math> indexed by the respective sets. | |||
To incorporate likelihood (unary) terms into the algorithm, it was shown in <ref name="grady2005multilabel" /> that one may optimize the energy | |||
:<math>Q(x) = x^T L x + \gamma \left((1-x)^T F (1-x) + x^T B x\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),</math> | |||
for positive, diagonal matrices <math>F</math> and <math>B</math>. Optimizing this energy leads to the system of linear equations | |||
:<math> | |||
\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}}. | |||
</math> | |||
The set of seeded nodes, <math>S</math>, may be empty in this case (i.e., <math>\overline{S}=V</math>), 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 <math>f_i</math> would represent the confidence that the color at node <math>v_i</math> would belong to object (i.e., a larger value of <math>f_i</math> indicates greater confidence that <math>v_i</math> belonged to the object label) and <math>b_i</math> would represent the confidence that the color at node <math>v_i</math> belongs to the background. | |||
==Algorithm interpretations== | |||
The random walker algorithm was initially motivated by labeling 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.<ref name="grady2006random" /> | |||
===Circuit theory interpretations=== | |||
There are well-known connections between [[electrical circuit]] theory and random walks on graphs.<ref>P. G. Doyle, J. L. Snell: Random Walks and Electrical Networks, Carus Mathematical Monographs, 1984</ref> 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, <math>r_{ij}</math>, associated with edge <math>e_{ij}</math> is set equal to <math>r_{ij} = \frac{1}{w_{ij}}</math> (i.e., the edge weight equals [[electrical conductance]]). | |||
In the first interpretation, each node associated with a background seed, <math>v_i \in B</math>, is tied directly to [[Ground (electricity)|ground]] while each node associated with an object/foreground seed, <math>v_i \in F</math> is attached to a unit [[direct current]] ideal [[voltage source]] tied to ground (i.e., to establish a unit potential at each <math>v_i \in F</math>). 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, <math>x_i</math> at node <math>v_i</math> will equal the probability that a random walker dropped at node <math>v_i</math> 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<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> | |||
* 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> | |||
* Threshold selection<ref>S. Rysavy, A. Flores, R. Enciso, K. Okada: 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> | |||
* 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> | |||
* 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> | |||
* Fast random walker using offline [[precomputation]] <ref>L. Grady, A.K. Sinop: 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> | |||
==Applications== | |||
Beyond image segmentation, the random walker algorithm 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> | |||
* 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> | |||
* Medical image segmentation<ref>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</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> | |||
* 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> | |||
* 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 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> | |||
* Segmentation editing<ref>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</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> | |||
* Image matching<ref>R. Shen, I. Cheng, X. Li, A. Basu: Stereo matching using random walks, Proc. of ICPR 2008</ref> | |||
* Image Fusion<ref>R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011.</ref> | |||
==References== | |||
{{Reflist}} | |||
<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically --> | |||
==External links== | |||
*[http://www.cns.bu.edu/~lgrady/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://scikits-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://scikits-image.org/ scikits-image] | |||
[[Category:Image segmentation]] |
Revision as of 20:18, 19 January 2014
The random walker algorithm is an algorithm for image segmentation. In the first description of the algorithm,[1] 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. This computation 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, 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[2]).
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).[3] It has also been extended to other applications, such as Image Matching (R. Shen, I. Cheng, X.li and A. Basu), ICPR 2008, and Image Fusion, (R. Shen, I. Cheng, J.Shi and A. Basu), IEEE Trans. on Image Processing, 2011, and other applications.
The algorithm was initially published as a conference paper[4] and later as a journal paper.[1]
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 . 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 associated with a pixel and each edge connecting neighboring pixels and . 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 at node , it is common to use the edge weighting function
The nodes, edges and weights can then be used to construct the graph Laplacian matrix.
The random walker algorithm optimizes the energy
where represents a real-valued variable associated with each node in the graph and the optimization is constrained by for and for , where and represent the sets of foreground and background seeds, respectively. If we let represent the set of nodes which are seeded (i.e., ) and represent the set of unseeded nodes (i.e., where is the set of all nodes), then the optimum of the energy minimization problem is given by the solution to
where the subscripts are used to indicate the portion of the graph Laplacian matrix indexed by the respective sets.
To incorporate likelihood (unary) terms into the algorithm, it was shown in [3] that one may optimize the energy
for positive, diagonal matrices and . Optimizing this energy leads to the system of linear equations
The set of seeded nodes, , may be empty in this case (i.e., ), 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 would represent the confidence that the color at node would belong to object (i.e., a larger value of indicates greater confidence that belonged to the object label) and would represent the confidence that the color at node belongs to the background.
Algorithm interpretations
The random walker algorithm was initially motivated by labeling 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.[1]
Circuit theory interpretations
There are well-known connections between electrical circuit theory and random walks on graphs.[5] 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, , associated with edge is set equal to (i.e., the edge weight equals electrical conductance).
In the first interpretation, each node associated with a background seed, , is tied directly to ground while each node associated with an object/foreground seed, is attached to a unit direct current ideal voltage source tied to ground (i.e., to establish a unit potential at each ). 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, at node will equal the probability that a random walker dropped at node 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[6]
- Alpha matting[7]
- Threshold selection[8]
- Soft inputs[9]
- Run on a presegmented image[10]
- Scale space random walk[11]
- Fast random walker using offline precomputation [12][13]
Applications
Beyond image segmentation, the random walker algorithm has been additionally applied to several problems in computer vision and graphics:
- Image Colorization[14]
- Interactive rotoscoping[15]
- Medical image segmentation[16][17][18]
- Merging multiple segmentations[19]
- Mesh segmentation[20][21]
- Mesh denoising[22]
- Segmentation editing[23]
- Shadow elimination[24]
- Image matching[25]
- Image Fusion[26]
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
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 in the image processing toolbox scikits-image
- ↑ 1.0 1.1 1.2 L. Grady: Random Walks for Image Segmentation, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 28, No. 11, pp. 1768–1783, Nov., 2006.
- ↑ P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984
- ↑ 3.0 3.1 Leo Grady: Multilabel Random Walker Image Segmentation Using Prior Models, Proc. of CVPR, Vol. 1, pp. 763–770, 2005. [1]
- ↑ 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.
- ↑ P. G. Doyle, J. L. Snell: Random Walks and Electrical Networks, Carus Mathematical Monographs, 1984
- ↑ T. H. Kim, K. M. Lee, S. U. Lee: Generative Image Segmentation Using Random Walks with Restart, Proc. of ECCV 2008, pp. 264–275
- ↑ J. Wang, M. Agrawala, M. F. Cohen: Soft scissors: an interactive tool for realtime high quality matting, Proc. of SIGGRAPH 2007
- ↑ S. Rysavy, A. Flores, R. Enciso, K. Okada: Classifiability Criteria for Refining of Random Walks Segmentation, Proc. of ICPR 2008
- ↑ W. Yang, J. Cai, J. Zheng, J. Luo: User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs, IEEE Trans. on Image Proc., 2010
- ↑ C. Chefd'hotel, A. Sebbane: Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation, Proc. of ICV 2007
- ↑ 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
- ↑ L. Grady, A.K. Sinop: Fast approximate random walker segmentation using eigenvector precomputation. In IEEE Conf. CVPR, pp. 1–8, 2008
- ↑ S. Andrews, G. Hamarneh, A. Saad. Fast random walker with priors using precomputation for interactive medical image segmentation, Proc. of MICCAI 2010
- ↑ X. Liu, J. Liu, Z. Feng: Colorization Using Segmentation with Random Walk, Computer Analysis of Images and Patterns, pp. 468–475, 2009
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: A random walker based approach to combining multiple segmentations, Proc. of ICPR 2008
- ↑ 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
- ↑ J. Zhang, J. Zheng, J. Cai: Interactive Mesh Cutting Using Constrained Random Walks, IEEE Trans. on Visualization and Computer Graphics, 2010.
- ↑ 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
- ↑ 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
- ↑ G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008
- ↑ R. Shen, I. Cheng, X. Li, A. Basu: Stereo matching using random walks, Proc. of ICPR 2008
- ↑ R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011.