Components of Random Walker (in a lower level than before)

1. Input image (and convert to "double precision image"???)
1. Input: Image
2. Output: Formatted image + additional info
3. Description:
1. Extract dimensions (and other information such as number of colour channels)
2. Check for correct format
3. Convert to correct format

 

2. Build an empty graph (lattice; all edges weight=1) using dimensions of image (in pixels)
1. Inputs: X, Y (dimensions of lattice)
2. Outputs: Vertices(Nx2 matrix), Edges(Mx2 matrix)
3. Description:
1. Create (X*Y) number of nodes
2. Create respective amount of edges with weight=1, connecting them accordingly. The connections will be such that each corner node will have 2 connections, each non-corner-outside node will have 3 connections, and each inside node will have 4 connections.
3. Output Mx2 ‘vertices’ array and Nx2 ‘edges’ array

 

3. Generate edge weights
1. Inputs: Mx2 edges matrix, NxK list of nodal values (this will be Nx1 for now (1channel), and Nx3(3channel)), scaling factor(this scaling factor will affect the precision of the segmentation)
2. Outputs: Mx1 matrix, indexed by the edges, containing the weight corresponding to that edge
3. Description: The edges matrix is solely used for indexing. The equation implemented for weights is:

will fix later--->

Where i and j are adjacent nodes and n_i and n_j are the values at nodes i and j provided in the NxK nodal value array.

 

4. Generate Laplacian matrix
1. Input: edges matrix, nodes matrix
2. Output: Laplacian matrix
3. Description: Applies algorithm to generate Laplacian matrix by first finding the adjacency matrix.

 

5. Determine locations of labels
1. Using labels information from input

 

6. Set up Dirichlet boundaries
1. Using locations of labels.

 

7. Solve Random Walker algorithm by solving the combinatorial Dirichlet problem
1. Inputs: NxN Laplacian matrix, Lx1 vector specifying the boundary nodes (from step 6),
2. Output: Nx1 vector specifying the new nodal values (which seed they belong to)
3. Description: Finds the values of the non-boundary nodes

 

8. Generate mask
1. Extracted from the vector generated in step 7.

Very High Level Algorithm for Implementing Random Walker

1. Input image (and convert to "double precision image"???)
2. Build an empty graph (lattice; all edges weight=1) using dimensions of image (in pixels)
3. Generate edge weights
4. Generate Laplacian matrix
5. Determine locations of labels
6. Set up Dirichlet boundaries
7. Solve Random Walker algorithm by solving the combinatorial Dirichlet problem
8. Generate mask