Obtain neighbours of vertices of a 1D, 2D, or 3D graph.
getNeighbors(mask, neiStruc)
| 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
neighbours of a graph.
All components of |
A matrix with each row giving the neighbours 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 neighbours of each vertex.
For a 1D graph, if each vertex has two neighbours,
The first column are the neighbours on the left-hand side of
corresponding vertices and the second column the right-hand side.
For the vertices on boundaries, missing neighbours 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 neighbours on the left-hand side of the vertices on the first column;
the forth column are the neighbours 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 neighbours 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 neighbours 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 neighbours 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 neighbours from the 1-2 perspective appear first and then the 1-3 perspective and finally the 2-3 perspective. For each perspective, the neighbours are arranged in the same way as in a 2D graph.
There could be more than one way to define the same 3D neighbourhood structure for a graph (see Example 3 for illustration).
Winkler, G. (2003) "Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A Mathematical Introduction" (2nd ed.) Springer-Verlag
Feng, D. (2008) "Bayesian Hidden Markov Normal Mixture Models with Application to MRI Tissue Classification" Ph. D. Dissertation, The University of Iowa
#Example 1: get all neighbours of a 1D graph. mask <- c(0,0,rep(1,4),0,1,1,0,0,1,1,1) getNeighbors(mask, neiStruc=2)#> [,1] [,2] #> [1,] 10 2 #> [2,] 1 3 #> [3,] 2 4 #> [4,] 3 10 #> [5,] 10 6 #> [6,] 5 10 #> [7,] 10 8 #> [8,] 7 9 #> [9,] 8 10#Example 2: get all neighbours of a 2D graph based on neighbourhood structure # corresponding to the second-order Markov random field. mask <- matrix(1, nrow=2, ncol=3) getNeighbors(mask, neiStruc=c(2,2,2,2))#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] #> [1,] 7 2 7 3 7 4 7 7 #> [2,] 1 7 7 4 7 7 7 3 #> [3,] 7 4 1 5 7 6 2 7 #> [4,] 3 7 2 6 1 7 7 5 #> [5,] 7 6 3 7 7 7 4 7 #> [6,] 5 7 4 7 3 7 7 7#Example 3: get all neighbours of a 3D graph based on 6 neighbours structure # where the neighbours 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)#> [1] TRUE#Example 4: get all neighbours of a 3D graph based on 18 neighbours structure # where the neighbours 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)#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] #> [1,] 28 2 28 4 28 5 28 28 28 10 28 11 28 #> [2,] 1 3 28 5 28 6 28 4 28 11 28 12 28 #> [3,] 2 28 28 6 28 28 28 5 28 12 28 28 28 #> [4,] 28 5 1 7 28 8 2 28 28 13 28 14 28 #> [5,] 4 6 2 8 1 9 3 7 28 14 28 15 28 #> [6,] 5 28 3 9 2 28 28 8 28 15 28 28 28 #> [7,] 28 8 4 28 28 28 5 28 28 16 28 17 28 #> [8,] 7 9 5 28 4 28 6 28 28 17 28 18 28 #> [9,] 8 28 6 28 5 28 28 28 28 18 28 28 28 #> [10,] 28 11 28 13 28 14 28 28 1 19 28 20 2 #> [11,] 10 12 28 14 28 15 28 13 2 20 1 21 3 #> [12,] 11 28 28 15 28 28 28 14 3 21 2 28 28 #> [13,] 28 14 10 16 28 17 11 28 4 22 28 23 5 #> [14,] 13 15 11 17 10 18 12 16 5 23 4 24 6 #> [15,] 14 28 12 18 11 28 28 17 6 24 5 28 28 #> [16,] 28 17 13 28 28 28 14 28 7 25 28 26 8 #> [17,] 16 18 14 28 13 28 15 28 8 26 7 27 9 #> [18,] 17 28 15 28 14 28 28 28 9 27 8 28 28 #> [19,] 28 20 28 22 28 23 28 28 10 28 28 28 11 #> [20,] 19 21 28 23 28 24 28 22 11 28 10 28 12 #> [21,] 20 28 28 24 28 28 28 23 12 28 11 28 28 #> [22,] 28 23 19 25 28 26 20 28 13 28 28 28 14 #> [23,] 22 24 20 26 19 27 21 25 14 28 13 28 15 #> [24,] 23 28 21 27 20 28 28 26 15 28 14 28 28 #> [25,] 28 26 22 28 28 28 23 28 16 28 28 28 17 #> [26,] 25 27 23 28 22 28 24 28 17 28 16 28 18 #> [27,] 26 28 24 28 23 28 28 28 18 28 17 28 28 #> [,14] [,15] [,16] [,17] [,18] #> [1,] 28 28 13 28 28 #> [2,] 10 28 14 28 28 #> [3,] 11 28 15 28 28 #> [4,] 28 28 16 28 10 #> [5,] 13 28 17 28 11 #> [6,] 14 28 18 28 12 #> [7,] 28 28 28 28 13 #> [8,] 16 28 28 28 14 #> [9,] 17 28 28 28 15 #> [10,] 28 28 22 4 28 #> [11,] 19 28 23 5 28 #> [12,] 20 28 24 6 28 #> [13,] 28 1 25 7 19 #> [14,] 22 2 26 8 20 #> [15,] 23 3 27 9 21 #> [16,] 28 4 28 28 22 #> [17,] 25 5 28 28 23 #> [18,] 26 6 28 28 24 #> [19,] 28 28 28 13 28 #> [20,] 28 28 28 14 28 #> [21,] 28 28 28 15 28 #> [22,] 28 10 28 16 28 #> [23,] 28 11 28 17 28 #> [24,] 28 12 28 18 28 #> [25,] 28 13 28 28 28 #> [26,] 28 14 28 28 28 #> [27,] 28 15 28 28 28