how to connect edges to nodes in a image using minimum spanning tree approach

I am doing my project on graph matching in hand written image, i want to represent a given word image in graph, am using the below algorithm.

input image

output of my code

expected output in this form

Algorithm:

input: Binary image B, Grid width w, Grid height h
Output: Graph g = (V, E) with nodes V and edges E
1: function Grid(B,w,h)
2: for i ← 1 to number of columns C = Width of B/w do
3: for j ← 1 to number of rows R = Height of B/h do
4: V = V ∪ {(xm, ym) | (xm, ym) is the centre of mass of segment sij}
5: for Each pair of nodes (u, v) ∈ V × V do
6: E = E ∪ (u, v) if associated segments are connected by NNA, MST, or DEL
7: return g

am already find the center of mass using this am plotting the points after plotting the points i do not know how to add the edges to using minimum spanning tree approch

this my code

clc;
clear all;
close all;
X=imread('i2.jpg');
imfinfo('i2.jpg')
figure,imshow(X)

b = imresize(X,[100,100]);
si = size(b,1);
sj = size(b,2);
figure;imshow(b);

% Binarization
th = graythresh(b);
I = im2bw(b,th);

w = 10;
h = 10;
c=si/w;
r=sj/h;
kl=bwmorph(~I,'thin',inf);
figure,imshow(kl)

R(:,:)=kl(:,:);
I=1;
U1=w;
J=1;
U2=h;
E=1;
for i=1:r
  for j=1:c
B(I:U1,J:U2)=R(I:U1,J:U2);
[x,y]=find(B==1);
CX=mean(x);
CY=mean(y);
CXX(E)=CX
CYY(E)=CY
T(I:U1,J:U2)=B(I:U1,J:U2);
J=J+w;
U2=U2+h;
E=E+1;
clear B x y    
    end

I=I+w;
U1=U1+h;
J=1;
U2=h;

end
imshow(R)
hold on

hold on
plot(CYY,CXX,'.c')
hold off

am plotting using the CXX and CYY values i do not know how to add the edges to plotted points using minimum spanning tree approach. Please give me some code it will help me to complete my project

Answer 1

[Jaynik]

Hi Raghu,

MATLAB's built-in functions can be used to compute and plot the MST based on the coordinates of the centers of mass already calculated. These steps can be followed:

1. Calculate Pairwise Distances: Use the Euclidean distance between each pair of nodes (centers of mass).
2. Construct the MST: Use the graph and minspantree functions to construct the MST.

You can use the following code after obtaining the CXX and CYY values:

numPoints = length(CXX);
distances = zeros(numPoints);

for i = 1:numPoints
    for j = 1:numPoints
        distances(i, j) = sqrt((CXX(i) - CXX(j))^2 + (CYY(i) - CYY(j))^2);
    end
end

% Construct the graph
G = graph(distances);

% Compute the minimum spanning tree
T = minspantree(G);

% Plot the MST
figure;
plot(CYY, CXX, 'o'); % Plot points
hold on;
[x, y] = find(T.Edges.EndNodes);
for i = 1:length(x)
    plot([CYY(x(i)), CYY(y(i))], [CXX(x(i)), CXX(y(i))], '-r');
end
hold off;

You can refer to the following documentation to read more about these functions:

• graph: https://www.mathworks.com/help/matlab/ref/graph.html
• minspantree: https://www.mathworks.com/help/matlab/ref/graph.minspantree.html

Hope this helps!