Random walker algorithm

Last updated

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. 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, 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] ).

Contents

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.

The algorithm was initially published by Leo Grady 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 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. [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:

Applications

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

Related Research Articles

In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in a minimum cut, i.e., the smallest total weight of the edges which if removed would disconnect the source from the sink.

<span class="mw-page-title-main">Random walk</span> Mathematical formalization of a path that consists of a succession of random steps

In mathematics, a random walk, sometimes known as a drunkard's walk, is a random process that describes a path that consists of a succession of random steps on some mathematical space.

<span class="mw-page-title-main">Image segmentation</span> Partitioning a digital image into segments

In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics.

<span class="mw-page-title-main">Otsu's method</span> In computer vision and image processing

In computer vision and image processing, Otsu's method, named after Nobuyuki Otsu, is used to perform automatic image thresholding. In the simplest form, the algorithm returns a single intensity threshold that separate pixels into two classes, foreground and background. This threshold is determined by minimizing intra-class intensity variance, or equivalently, by maximizing inter-class variance. Otsu's method is a one-dimensional discrete analogue of Fisher's Discriminant Analysis, is related to Jenks optimization method, and is equivalent to a globally optimal k-means performed on the intensity histogram. The extension to multi-level thresholding was described in the original paper, and computationally efficient implementations have since been proposed.

<span class="mw-page-title-main">Conditional random field</span> Class of statistical modeling methods

Conditional random fields (CRFs) are a class of statistical modeling methods often applied in pattern recognition and machine learning and used for structured prediction. Whereas a classifier predicts a label for a single sample without considering "neighbouring" samples, a CRF can take context into account. To do so, the predictions are modelled as a graphical model, which represents the presence of dependencies between the predictions. What kind of graph is used depends on the application. For example, in natural language processing, "linear chain" CRFs are popular, for which each prediction is dependent only on its immediate neighbours. In image processing, the graph typically connects locations to nearby and/or similar locations to enforce that they receive similar predictions.

Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, or region extraction is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic. Connected-component labeling is not to be confused with segmentation.

As applied in the field of computer vision, graph cut optimization can be employed to efficiently solve a wide variety of low-level computer vision problems, such as image smoothing, the stereo correspondence problem, image segmentation, object co-segmentation, and many other computer vision problems that can be formulated in terms of energy minimization. Many of these energy minimization problems can be approximated by solving a maximum flow problem in a graph. Under most formulations of such problems in computer vision, the minimum energy solution corresponds to the maximum a posteriori estimate of a solution. Although many computer vision algorithms involve cutting a graph, the term "graph cuts" is applied specifically to those models which employ a max-flow/min-cut optimization.

<span class="mw-page-title-main">Watershed (image processing)</span>

In the study of image processing, a watershed is a transformation defined on a grayscale image. The name refers metaphorically to a geological watershed, or drainage divide, which separates adjacent drainage basins. The watershed transformation treats the image it operates upon like a topographic map, with the brightness of each point representing its height, and finds the lines that run along the tops of ridges.

<span class="mw-page-title-main">Random geometric graph</span> In graph theory, the mathematically simplest spatial network

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

<span class="mw-page-title-main">Spectral clustering</span> Clustering methods

In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as an input and consists of a quantitative assessment of the relative similarity of each pair of points in the dataset.

<span class="mw-page-title-main">Conductance (graph)</span> How quickly a random walk on a graph converges to steady state

In graph theory the conductance of a graph G = (V, E) measures how "well-knit" the graph is: it controls how fast a random walk on G converges to its stationary distribution. The conductance of a graph is often called the Cheeger constant of a graph as the analog of its counterpart in spectral geometry. Since electrical networks are intimately related to random walks with a long history in the usage of the term "conductance", this alternative name helps avoid possible confusion.

The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily concerned with graph theoretic approaches to image segmentation applying graph partitioning via minimum cut or maximum cut. Segmentation-based object categorization can be viewed as a specific case of spectral clustering applied to image segmentation.

Random walk closeness centrality is a measure of centrality in a network, which describes the average speed with which randomly walking processes reach a node from other nodes of the network. It is similar to the closeness centrality except that the farness is measured by the expected length of a random walk rather than by the shortest path.

<span class="mw-page-title-main">Hyperbolic geometric graph</span>

A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of spatial network where (1) latent coordinates of nodes are sprinkled according to a probability density function into a hyperbolic space of constant negative curvature and (2) an edge between two nodes is present if they are close according to a function of the metric (typically either a Heaviside step function resulting in deterministic connections between vertices closer than a certain threshold distance, or a decaying function of hyperbolic distance yielding the connection probability). A HGG generalizes a random geometric graph (RGG) whose embedding space is Euclidean.

<span class="mw-page-title-main">Biased random walk on a graph</span> Structural analysis of a network

In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various potential new states; unlike in a pure random walk, the probabilities of the potential new states are unequal.

Maximal entropy random walk (MERW) is a popular type of biased random walk on a graph, in which transition probabilities are chosen accordingly to the principle of maximum entropy, which says that the probability distribution which best represents the current state of knowledge is the one with largest entropy. While standard random walk chooses for every vertex uniform probability distribution among its outgoing edges, locally maximizing entropy rate, MERW maximizes it globally by assuming uniform probability distribution among all paths in a given graph.

<span class="mw-page-title-main">Teknomo–Fernandez algorithm</span>

The Teknomo–Fernandez algorithm , is an efficient algorithm for generating the background image of a given video sequence.

Graph cut optimization is a combinatorial optimization method applicable to a family of functions of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a graph representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function , if it is possible to construct a flow network with positive weights such that

In network science, the network entropy is a disorder measure derived from information theory to describe the level of randomness and the amount of information encoded in a graph. It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity

In the context of quantum computing, the quantum walk search is a quantum algorithm for finding a marked node in a graph.

References

  1. 1 2 3 Grady, L.: "Random walks for image segmentation". PAMI, 2006
  2. P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984
  3. 1 2 Leo Grady: "Multilabel Random Walker Image Segmentation Using Prior Models", Proc. of CVPR, Vol. 1, pp. 763–770, 2005.
  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.
  5. P. G. Doyle, J. L. Snell: Random Walks and Electrical Networks, Carus Mathematical Monographs, 1984
  6. T. H. Kim, K. M. Lee, S. U. Lee: Generative Image Segmentation Using Random Walks with Restart, Proc. of ECCV 2008, pp. 264–275
  7. 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
  8. S. Rysavy, A. Flores, R. Enciso, K. Okada: Classifiability Criteria for Refining of Random Walks Segmentation, Proc. of ICPR 2008
  9. W. Yang, J. Cai, J. Zheng, J. Luo: User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs, IEEE Trans. on Image Proc., 2010
  10. C. Chefd'hotel, A. Sebbane: Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation, Proc. of ICV 2007
  11. 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
  12. L. Grady, A.K. Sinop, "Fast approximate random walker segmentation using eigenvector precomputation". In IEEE Conf. CVPR, pp. 1–8, 2008
  13. S. Andrews, G. Hamarneh, A. Saad. Fast random walker with priors using precomputation for interactive medical image segmentation, Proc. of MICCAI 2010
  14. 1 2 R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011.
  15. 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
  16. 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
  17. 1 2 R. Shen, I. Cheng, A. Basu: QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF, IEEE Trans. on Image Processing, 2013.
  18. X. Liu, J. Liu, Z. Feng: Colorization Using Segmentation with Random Walk, Computer Analysis of Images and Patterns, pp. 468–475, 2009
  19. 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
  20. 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
  21. 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
  22. 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
  23. P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: A random walker based approach to combining multiple segmentations, Proc. of ICPR 2008
  24. 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
  25. J. Zhang, J. Zheng, J. Cai: Interactive Mesh Cutting Using Constrained Random Walks, IEEE Trans. on Visualization and Computer Graphics, 2010.
  26. 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
  27. 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
  28. G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008
  29. 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