Generate a weighted graph and an adjacency matrix from an image matrix

Hello every one,

i have a image matrix and i want from this matrix, generate a weighted graph G=(V,E) wich V is the vertex set and E is the edge set, for finaly obtain the adjacency matrix. and i don't know how??

thank you in advance.

[Guillaume]

a graph of what?

[Walter Roberson]

"Graph" is being used in the sense of Graph Theory.

Is the image one in which a graph has been drawn, and you want to extract the information? A sample would help.

[Guillaume]

Yes, I understood that the graph is in the sense of Graph Theory. There's no obvious link between a graph and an unspecified image unless as you say the question is about extracting the graph from an image of a graph.

[Mourchid]

Guillaume, is a graph of nodes, in which each node represents an image pixel.

[Mourchid]

Friends i want somthing like that (see the image):

[Guillaume]

Right, you have the algorithm fairly well explained, so what is your particular problem with generating the graph?

I'll note though that for any image of reasonable size, this algorithm is going to create a very large adjacency matrix. The number of elements in the adjacency matrix is going to be (image width * image height) ^ 2. An image of size 100 x 100 will result in an adjacency matrix around 800 MB.

[Mourchid]

Yes Guillaume sorry for the delay. yes my problem is how to generate the graphe from the image matrix, and how to obtain the adjacency matrix.

I want the matlab code to obtain the adjacency matrix.

thank you a lot.

[Rishabh Ramteke]

Can you tell me from which paper did you take the above mentioned algorithm?

Answer 1

[Walter Roberson]

numrow = size(YourImage,1);
numcol = size(YourImage,2);
[Y, X] = ndgrid(1:numrow, 1:numcol);   %indices array
x = X(:);
y = Y(:);
d = pdist2([x,y], [x,y]);  %pairwise euclidean distances
greyval = double(YourImage(:));
f = pdist2(greyval, greyval);          %pairwise grayscale distance %FIXED
A = (epsilon1 + f) ./ d;
A(f==0) = epsilon2 ./ d(f==0);  %fix up case of equal intensities

[Mourchid]

Thank you Walter Roberson for your answer, can you explain me why we use the variable greyval = double(YourImage(:));, and where is the test for the adjacency matrix when the intensites are differents or equals.

Thanks a lot.

[Walter Roberson]

Note: I have corrected a typo in my code about calculating the grayscale distance. See the revised answer.

Image arrays are usually coded as uint8, but the euclidean distance is not going to be a uint8 value. I do not have the toolbox that includes pdist2() so I cannot promise that it will return an accurate double-precision result when working on uint8 values. It might perform all of the arithmetic using the data class of the input. It is therefore safer to explicitly transform the input to pdist2() to floating point.

The (:) part is to re-form the array into a vector. The algorithm does not talk about "adjacent" pixels, it talks about any two pixels anywhere in the image, indexed by any arbitrary but consistent number system. Using MATLAB's "linear indexing" works fine for this purpose.

The test for different or equal intensities is the f==0 test. f is defined in terms of the difference between intensities. When the intensities are the same, the difference will be 0. One can thus test for the input intensities being the same by checking that the output difference was 0.

If you define the "difference" between intensities as abs(I1-I2) then you can replace

f = pdist2(greyval, greyval);

with

f = bsxfun(@minus, greyval, greyval.');
f = abs(f(:));

pdist2() to calculate the Euclidean distances can be replaced with a couple of bsxfun() calls.

d = sqrt(bsxfun(@minus, x, x.').^2 + bsxfun(@minus, y, y.').^2);
d = d(:);

[Mourchid]

Thank you soo much Walter Roberson for your help :)

Answer 2

[Thorsten]

If you have a image matrix like

10  3  4
12  5  8

you could interpret it as an adjacency matrix of a directed graph a follows

vertex   1  2  3
  1     10  3  4
  2     12  5  8

there is an edge from 1 to 1 weighted 10
                      1    2 weighted 12
                      2 to 1 weighted  3
                      2    2           5
                      3 to 1           4
                      3    2           8

Of course you could also interpret the directions the other way round, like from 2 to 1 weighted 12, from 1 to 2 weighted 3 etc.

[Mourchid]

Hello, thank you Thorsten for your answer, can you give me the matlab code for more understanding, for exemple i have the image matrix like that:

I=imread('myimage'); after this commande we have the matrix I of image, so how we can generate the graph and the adjacency matrix, from th matrix I.

thank you soo much.

[Thorsten]

I is already your adjacency matrix.

To plot the graph, you need to define the xy coordinates of the nodes and then you can use the gplot command or wgplot.

http://www.mathworks.com/matlabcentral/fileexchange/24035-wgplot-weighted-graph-plot--a-better-version-of-gplot-

[Mourchid]

i don't want plotting the graph, i want juste the adjacency matrix from the image matrix I which is the matrix of pixels. i want somthing like that: