getNeighbors {PottsUtils}

Get Neighbors of All Vertices of a Graph

Description

Obtain neighbors of vertices of a 1D, 2D, or 3D graph.

Usage

   getNeighbors(mask, neiStruc)

Arguments

mask

a vector, matrix, or 3D array specifying vertices within a graph. Vertices of value 1 are within the graph and 0 are not.

neiStruc

a scalar, vector of four components, or 3\times4 matrix corresponding to 1D, 2D, or 3D graphs. It gives the definition of neighbors of a graph. All components of neiStruc should be positive (\ge 0) even numbers. For 1D graphs, neiStruc gives the number of neighbors of each vertex. For 2D graphs, neiStruc[1] specifies the number of neighbors on vertical direction, neiStruc[2] horizontal direction, neiStruc[3] north-west (NW) to south-east (SE) diagonal direction, and neiStruc[4] south-west (SW) to north-east (NE) diagonal direction. For 3D graphs, the first row of neiStruc specifies the number of neighbors on vertical direction, horizontal direction and two diagonal directions from the 1-2 perspective, the second row the 1-3 perspective, and the third row the 2-3 perspective. The index to perspectives is represented with the leftmost subscript of the array being the smallest.

Details

There could be more than one way to define the same 3D neighborhood structure for a graph (see Example 3 for illustration).

Value

A matrix with each row giving the neighbors of a vertex. The number of the rows is equal to the number of vertices within the graph and the number or columns is the number of neighbors of each vertex.

For a 1D graph, if each vertex has two neighbors, The first column are the neighbors on the left-hand side of corresponding vertices and the second column the right-hand side. For the vertices on boundaries, missing neighbors are represented by the number of vertices within a graph plus 1. When neiStruc is bigger than 2, The first two columns are the same as when neiStruc is equal to 2; the third column are the neighbors on the left-hand side of the vertices on the first column; the forth column are the neighbors on the right-hand side of the vertices on the second column, and so on and so forth. And again for the vertices on boundaries, their missing neighbors are represented by the number of vertices within a graph plus 1.

For a 2D graph, the index to vertices is column-wised. For each vertex, the order of neighbors are as follows. First are those on the vertical direction, second the horizontal direction, third the NW to SE diagonal direction, and forth the SW to NE diagonal direction. For each direction, the neighbors of every vertex are arranged in the same way as in a 1D graph.

For a 3D graph, the index to vertices is that the leftmost subscript of the array moves the fastest. For each vertex, the neighbors from the 1-2 perspective appear first and then the 1-3 perspective and finally the 2-3 perspective. For each perspective, the neighbors are arranged in the same way as in a 2D graph.

References

Gerhard Winkler (1995) Image Analysis, Random Fields and Dynamic Monte Carlo Methods Springer-Verlag

Dai Feng (2008) Bayesian Hidden Markov Normal Mixture Models with Application to MRI Tissue Classification Ph. D. Dissertation, The University of Iowa

Examples

  #Example 1: get all neighbors of a 1D graph.
  mask <- c(0,0,rep(1,4),0,1,1,0,0,1,1,1)
  getNeighbors(mask, neiStruc=2)

  #Example 2: get all neighbors of a 2D graph based on neighborhood structure
  #           corresponding to the second-order Markov random field.
  mask <- matrix(1, nrow=2, ncol=3)
  getNeighbors(mask, neiStruc=c(2,2,2,2))

  #Example 3: get all neighbors of a 3D graph based on 6 neighbors structure
  #           where the neighbors of a vertex comprise its available
  #           N,S,E,W, upper and lower adjacencies. To achieve it, there
  #           are several ways, including the two below.
  mask <- array(1, dim=rep(3,3))
  n61 <- matrix(c(2,2,0,0,
                  0,2,0,0,
                  0,0,0,0), nrow=3, byrow=TRUE)
  n62 <- matrix(c(2,0,0,0,
                  0,2,0,0,
                  2,0,0,0), nrow=3, byrow=TRUE)
  n1 <- getNeighbors(mask, neiStruc=n61)
  n2 <- getNeighbors(mask, neiStruc=n62)
  n1 <- apply(n1, 1, sort)
  n2 <- apply(n2, 1, sort)
  all(n1==n2)

  #Example 4: get all neighbors of a 3D graph based on 18 neighbors structure
  #           where the neighbors of a vertex comprise its available
  #           adjacencies sharing the same edges or faces.
  #           To achieve it, there are several ways, including the one below.

  n18 <- matrix(c(2,2,2,2,
                  0,2,2,2,
                  0,0,2,2), nrow=3, byrow=TRUE)  
  mask <- array(1, dim=rep(3,3))
  getNeighbors(mask, neiStruc=n18)