CODEWITHSUNDEEP
c++graph-theoryadjacency-matrix
Mandar
Mandar

Reputation: 131

Adjacency matrix from gradient image

In reference to calculating adjacency matrix from gradient of image, I found something in python. large-adjacency-matrix-from-image-in-python

I want to calculate an adjacency matrix based on 4 or 8 neighboring pixels. I also found http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3408910/

How can i do this with 4 or 8 neighbors? I want to do this in C++. I already have gradient image for use.

Upvotes: 0

Views: 591

Answers (1)

collapsar
collapsar

Reputation: 17238

For the sake of simplicity, assume that the gradient image is a square pixel bitmap of size n x n. Assign an ordinal number to each pixel by row-major counting starting in the northwestern corner.

Define the (n^2 x n^2) adjacency matrix A = (a_ij)_i,j=1..n^2 as follows:

a_i(i-n) = 1; i > n             // northern neighbour
a_i(i+1) = 1; (i-1) mod n < n-1 // eastern neighbour
a_i(i-1) = 1; (i-1) mod n > 0   // western neighbour
a_i(i+n) = 1; i <= n^2 - n      // southern neighbour
a_ij     = 0; else

For 8 neighbours per pixel add

a_i(i-n+1) = 1; i > n and (i-n-1) mod n < n-1          // northeastern neighbour
a_i(i-n-1) = 1; i > n and (i-n-1) mod n > 0            // northwestern neighbour
a_i(i+n+1) = 1; i <= n^2 - n and (i+n-1) mod n < n-1   // southeastern neighbour
a_i(i+n-1) = 1; i <= n^2 - n and (i+n-1) mod n > 0     // southwestern neighbour

Instead of 1 you may assign the weights calculated from the gradient between adjacent pixels. Note that 0 entries would change to M, M representing a sufficiently large number ( infinite, since the respective cells are no neighbours, but that requires the implementation take special provisions ).

A will be sparse and will have a regular structure, for efficiency you should probably employ a class for sparse matrix processing. This SO question provides some suggestions.

Upvotes: 1

Related Questions