Generate a weighted graph and an adjacency matrix from an image matrix
28 views (last 30 days)
Show older comments
Mourchid
on 21 May 2015
Commented: Rishabh Ramteke
on 29 Oct 2019
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.
8 Comments
Rishabh Ramteke
on 29 Oct 2019
Can you tell me from which paper did you take the above mentioned algorithm?
Accepted Answer
Walter Roberson
on 23 May 2015
Edited: Walter Roberson
on 23 May 2015
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
3 Comments
Walter Roberson
on 23 May 2015
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(:);
More Answers (1)
Thorsten
on 21 May 2015
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.
3 Comments
Thorsten
on 21 May 2015
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.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!