Average distance between nearest neighbors of grain boundaries

I have an image which contains both grains and grain boundaries. I wanted to write a matlab code to determine the average distance from one grain boundary to its nearest grain boundary and to the second nearest neighbor and so forth.

[Matt J]

And...? What did you write and what questions does it raise?

[Prince]

The question is how do I determine the average distance from one grain boundary to its first, second and nth nearest grain boundary?

[Image Analyst]

Since the grain boundaries are the lines, and the lines separating one pair of grains from a different pair or grains touch, the average distance between the two closest boundaries is either 0 or 1 pixel, depending on how you define distance. Did you perhaps mean the average distance between "grain centroids" rather than grain boundaries?

[DGM]

Do you mean the distance between grains (e.g. between centroids), or between boundaries? If the latter, define how we should consider the extent and uniqueness of a grain boundary and what it means for grain boundaries to be nearest if their distance is yet unknown. Are we just finding all distances and sorting them, or are we looking specifically at the grains which share a boundary? What about all those open spurs and incomplete grains at the edges of the image? Do open spurs just get discarded, or are they even supposed to be open?

Also, bear in mind that the average distance between the members of two groups of points is not the distance between the centroids of the two groups. The average distance between points expresses both the group distance and the size of the groups. In other words, for two coincident sets of points, the distance you would get would not be zero.

% two unequal-size groups with only roughly coincident centroids
a = randn(1000,2)*100;
b = randn(100,2)*100;

% average distance between pixels
D1 = mean(hypot(a(:,1)-b(:,1).',a(:,2)-b(:,2).'),'all')

D1 = 172.6605

% distance between centroids
D2 = sqrt(sum((mean(a,1) - mean(b,1)).^2,2))

D2 = 3.4861

So which do you want? If it's the latter, then why does the boundary matter? Why not just use the grain centroid?

[Prince]

The question is specifically about the grain boundaries and not the grains. I want to find the average distances between grain boundaries and their nearest neighbor grain bondaries.

[DGM]

I assume now you want some sort of pairwise pixel distance.

You still haven't answered how you're defining the boundaries or nearest neighbors, or what should be done with spurs or partial grains.

For example, are boundary pixels shared? If they need to be treated that way, the lack of uniqueness complicates everything. Consider the boundaries of two blobs:

Is there any comment on the applicability of the example I gave below?

[Image Analyst]

His binary image of the boundary showed single lines separating the grains. So it's the right hand side image. So in the right image, the distance between the white part of the boundaries is zero. Do you want the average distance between ALL the coordinates, i.e. all the (purple+white) and the (green+white) coordinates? If so, label your grains with bwlabel then take a pair of grains and dilate each with imdilate to enlarge it one pixel layer then get the boundaries with bwboundaries. Then use pdist2 to get the distance of every perimeter point of one grain to every perimeter point of the other grain. Then take the mean of all those distances. Not sure what physical meaning this would have though (I'm not a metallurgist). Or maybe you want the average of the closest distances rather than all the distances.

Or maybe you want the Hausdorff distance. See http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

https://en.wikipedia.org/wiki/Hausdorff_distance

[DGM]

It would seem like the second image is what's being described, but:

• it's just more complicated (and slower) to calculate the second case (I did give a crude example below)
• the difference between the two is fairly small
• we don't know how accurately these lines actually correspond to the original image, so is that difference meaningful?

I don't know what the contextual meaning of the average pixel distance would be either.

Answer 1

[Jaimin]

Hi @Prince

To calculate the average distance from one grain boundary to its nearest grain boundaries, you can follow these general steps in MATLAB:

1. Preprocess the Image: Convert the image to a binary format where the grain boundaries are clearly distinguished from the grains.
2. Identify Grain Boundaries: Use edge detection or image segmentation techniques to identify the grain boundaries.
3. Extract Boundary Points: Get the coordinates of the boundary points.
4. Calculate Distances: For each boundary point, calculate distances to all other boundary points and find the nearest, second nearest, etc.
5. Compute Average Distances: Compute the average of these distances for the first, second, nth nearest neighbours.

For more information kindly refer following resources.

imbinarize: https://www.mathworks.com/help/images/ref/imbinarize.html

edge: https://www.mathworks.com/help/images/ref/edge.html

find: https://www.mathworks.com/help/matlab/ref/find.html

I hope this will be helpful.

Answer 2

[DGM]

Maybe a start, maybe not:

% the image as a logical mask
inpict = imread('unettestfile.png')>128;

% if we're not going to fix open edges
% then just get rid of them
lastpix = nnz(inpict);
currpix = lastpix - 1;
while lastpix ~= currpix
	inpict = inpict & ~bwmorph(inpict,'endpoints');
	lastpix = currpix;
	currpix = nnz(inpict);
end

% convert to a mask describing complete grains
grainmask = imclearborder(~inpict,4);

% of course this won't show up well unless it's displayed at full-scale
imshow(grainmask)

% if boundaries are "shared" by neighboring grains,
% i don't see a simple way to do that without loops
% dilating and evaluating each blob independently.
% it's not clear that it's necessary to treat the boundaries that way.

% instead, just consider the boundary of each blob
% in this case, no boundary pixels are shared between blobs
grbound2 = bwboundaries(grainmask,4);

% find distance between interior boundary centroids
nblobs = size(grbound2,1);
Db = zeros(nblobs);
for kr = 1:nblobs
    groupA = grbound2{kr};
    for kc = kr+1:nblobs
        groupB = grbound2{kc};
        Db(kr,kc) = sqrt(sum((mean(groupA,1) - mean(groupB,1)).^2,2));
    end
end
Db = Db + Db.'; % make symmetric for easier sorting

% find distance between the actual blob centroids
% in this case, we don't need grbound2
CC = bwconncomp(grainmask,4);
S = regionprops(CC,'PixelList');
Dgr = zeros(nblobs);
for kr = 1:nblobs
    groupA = S(kr).PixelList;
    for kc = kr+1:nblobs
        groupB = S(kc).PixelList;
        Dgr(kr,kc) = sqrt(sum((mean(groupA,1) - mean(groupB,1)).^2,2));
    end
end
Dgr = Dgr + Dgr.'; % make symmetric for easier sorting

% the difference is small.  does it matter?
immse(Db,Dgr)

ans = 1.1059

% alternatively, we can calculate Dgr quite a bit more easily
% since we don't really need to deal with many lists of points
CC = bwconncomp(grainmask,4);
S = regionprops(CC,'Centroid');
c = vertcat(S.Centroid);
Dgr2 = pdist2(c,c); % same thing

% find average distance between individual boundary pixels
nblobs = size(grbound2,1);
Dpxpx = zeros(nblobs);
for kr = 1:nblobs
    groupA = grbound2{kr};
    for kc = kr+1:nblobs
        groupB = grbound2{kc};
        dr = groupA(:,1) - groupB(:,1).';
        dc = groupA(:,2) - groupB(:,2).';
        Dpxpx(kr,kc) = mean(hypot(dr,dc),'all');
    end
end
Dpxpx = Dpxpx + Dpxpx.'; % make symmetric for easier sorting

Here are three different distance matrices:

• Dpxpx: the average distance between groups of boundary pixels
• Db: the distance between the centroids of boundary pixel groups
• Dgr/Dgr2: the distance between the grain centroids

These rows/columns of these matrices are ordered based on how the connected groups are extracted from the image. You will have to sort them according to whatever your goals are. For example:

[Dpxpx idx] = sort(Dpxpx,2);

... will sort the rows of Dpxpx and return the sorted neighbor indices. The first column of Dpxpx will be the self-distance (0), and the following columns will be the distance to the nearest neighbors. The first column of idx will be the blob/boundary index, and the following columns will be the indices of its nearest neighbors.

[DGM]

Assuming we're talking about the average distance between all members of two pixel sets, we can disregard the centroid-based examples. So that leaves us with two different definitions of what the boundaries are:

% the image as a logical mask
inpict = imread('unettestfile.png')>128;

% if we're not going to fix open edges
% then just get rid of them
lastpix = nnz(inpict);
currpix = lastpix - 1;
while lastpix ~= currpix
    inpict = inpict & ~bwmorph(inpict,'endpoints');
    lastpix = currpix;
    currpix = nnz(inpict);
end

% convert to a mask describing complete grains
grainmask = imclearborder(~inpict,4);

% INNER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% this is the same as in the prior example
% find the inner (unique) boundary pixels
grbound2 = bwboundaries(grainmask,4);

% find average distance between individual boundary pixels
nblobs = size(grbound2,1);
Dpxinner = zeros(nblobs);
for kr = 1:nblobs
    groupA = grbound2{kr};
    for kc = kr+1:nblobs
        groupB = grbound2{kc};
        dr = groupA(:,1) - groupB(:,1).';
        dc = groupA(:,2) - groupB(:,2).';
        Dpxinner(kr,kc) = mean(hypot(dr,dc),'all');
    end
end
Dpxinner = Dpxinner + Dpxinner.'; % make symmetric for easier sorting

% show a sample
Dpxinner(1:10,1:10)

ans = 10×10

0 38.6842 253.4496 292.2867 157.0359 93.2967 243.3661 111.2087 191.2937 334.2809 38.6842 0 279.8504 318.6600 183.2188 118.6020 217.0137 139.6145 166.0334 361.3864 253.4496 279.8504 0 45.2916 99.3726 162.5487 494.7403 155.3794 442.2797 85.6063 292.2867 318.6600 45.2916 0 137.3130 201.1675 533.8492 193.3119 481.3837 48.0564 157.0359 183.2188 99.3726 137.3130 0 66.6109 397.8376 68.5614 345.4273 179.5353 93.2967 118.6020 162.5487 201.1675 66.6109 0 333.3337 51.0511 281.0786 243.6131 243.3661 217.0137 494.7403 533.8492 397.8376 333.3337 0 346.5923 57.8965 575.7140 111.2087 139.6145 155.3794 193.3119 68.5614 51.0511 346.5923 0 293.6259 233.0580 191.2937 166.0334 442.2797 481.3837 345.4273 281.0786 57.8965 293.6259 0 522.9972 334.2809 361.3864 85.6063 48.0564 179.5353 243.6131 575.7140 233.0580 522.9972 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

% OUTER %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% find the outer (potentially shared) boundary pixels
[L nblobs] = bwlabel(grainmask,4);
grbound1 = cell(nblobs,1);
for k = 1:nblobs
    thisgrain = L == k;
    thisgrain = imdilate(thisgrain,ones(3)) & inpict;
    [r c] = find(thisgrain); % if order doesn't matter, this is faster
    grbound1{k} = [r c];
end

% find average distance between individual boundary pixels
nblobs = size(grbound1,1);
Dpxouter = zeros(nblobs);
for kr = 1:nblobs
    groupA = grbound1{kr};
    for kc = kr+1:nblobs
        groupB = grbound1{kc};
        dr = groupA(:,1) - groupB(:,1).';
        dc = groupA(:,2) - groupB(:,2).';
        Dpxouter(kr,kc) = mean(hypot(dr,dc),'all');
    end
end
Dpxouter = Dpxouter + Dpxouter.'; % make symmetric for easier sorting

% show a sample
Dpxouter(1:10,1:10)

ans = 10×10

0 38.8836 256.0646 292.9621 157.2747 94.9365 242.9023 111.2669 191.3583 334.9411 38.8836 0 281.6243 318.6924 182.5756 119.6882 217.1652 138.9380 166.8476 361.2383 256.0646 281.6243 0 44.3306 102.1022 163.6398 496.6991 159.7471 444.7430 84.1015 292.9621 318.6924 44.3306 0 138.0294 200.3558 533.8864 195.1572 481.8518 47.6309 157.2747 182.5756 102.1022 138.0294 0 65.4950 397.3298 71.1878 345.4262 180.2352 94.9365 119.6882 163.6398 200.3558 65.4950 0 334.2367 50.5794 282.4115 242.6293 242.9023 217.1652 496.6991 533.8864 397.3298 334.2367 0 345.3144 58.0566 575.7692 111.2669 138.9380 159.7471 195.1572 71.1878 50.5794 345.3144 0 292.6533 235.1868 191.3583 166.8476 444.7430 481.8518 345.4262 282.4115 58.0566 292.6533 0 523.5029 334.9411 361.2383 84.1015 47.6309 180.2352 242.6293 575.7692 235.1868 523.5029 0

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

Some of this might simplify, but we're not at that point yet.