Centroids distance in pixel

Hello everyone,

I am writing to ask for a suggestions.

I am working on high resolution images ( 5MP ) showing a evenly space dots grid. I would need to compute the euclidean distance between the dots centroids.

I used the "imfindcircles" function, which uses the CHT algorithm, to obtain the centers and radii of the dots of the images with good accuracy, Here the code lines and the resulting image:

 [centers,radii] = imfindcircles(maskedImage,[4 18],'ObjectPolarity','dark','Sensitivity',0.9,'Method','twostage','EdgeThreshold',0.4);
        viscircles(centers, radii,'LineStyle','--');

The varialble "centers" found is a matrix of two columns defining the x and y coordinates of all the centroids of the dots found in the image. I have not understood which is the order meaning of the dots centroids coordinates in this variable, it seems to be quite random.

Now what I would need to do is to compute the distance between each dot centroid and the centroids of the four closest dots. I would then obtain a matrix in which I will have 4 columns relatives to the four distances found for each dot. Attached an image for better explanation:

Do you have any idea of which could be an easy way to proceed? Is there any built in function I can use?

Please, let me know if something is not clear or I need to provide more information.

Thanks so much for your help!

[DGM]

If you want, it might help if you attached a lower-res example of one such image.

That said, there are a number of similar questions

https://www.mathworks.com/matlabcentral/answers/827315-how-to-find-the-distance-of-all-objects-in-given-image

This one was looking for the nearest neighbor, but could easily be changed to the 4-neighbors using mink() instead of min(). Sorting them by relative direction might be a bit of a complication.

Answer 1

[DGM]

Eh. This is a kludgy extension of the example I linked to. I just used a modified copy of your screenshot:

inpict = logical(255-imread('dotgridfull.png'));
inpict = inpict & ~bwareaopen(inpict,500); % remove corner objects

C0 = regionprops(inpict,'centroid');
C = vertcat(C0.Centroid);
npoints = numel(C0);

% distance from every object to every other object
D = sqrt((C(:,1)-C(:,1).').^2 + (C(:,2)-C(:,2).').^2);
D(D<1E-6) = NaN; % remove self-distances
[Dn Nn] = mink(D,4,2); % nearest 4 neighbor distances, indices

% it might be worthwhile to discard distances significantly greater 
% than the mean.  that would be a simple method of dealing with
% points on the edge without a full 4-neighborhood
%C = [C; [NaN NaN]];
%baddist = Dn>(1.1*mean(Dn(:)));
%Dn(baddist) = NaN;
%Nn(baddist) = npoints+1;

% sort point locations [NW NE SE SW]
for p = 1:npoints
	thisC = C(p,:);
	Cnn = C(Nn(p,:),:);
	eastof = Cnn(:,1)>thisC(1);
	northof = Cnn(:,2)<thisC(2); % origin is in NW corner
	
	neworder = [find(northof & ~eastof); find(northof & eastof); ...
				find(~northof & eastof); find(~northof & ~eastof)];
	Dn(p,:) = Dn(p,neworder);
	Nn(p,:) = Nn(p,neworder);
end

% show image and plot lines between each point and its 4-neighbors
% of course, half the lines are overlapping each other, so ...
imshow(~inpict); hold on % web-view is easier to see inverted
linespec = {'r','k','m','b'};
for p = 1:npoints
	for dir = 1:4
		pts = C([p Nn(p,dir)],:);
		plot(pts(:,1),pts(:,2),linespec{dir})
	end
end

As mentioned, you're going to have to deal with the fact that the edge dots don't have a full 4-neighborhood. Simply finding the 4 nearest neighbors will result in finding dots that might not intend to be considered neighbors.

[Image Analyst]

If you want just the distances that are about 1 unit, and not those that are about sqrt(2) = 1.4 units then you could easily threshold the distances at around 1.2 units and discard those that are greater than that.

[DGM]

That's (roughly) what the commented-out section does, though I used a factor of 1.1, since I assumed the mean would be an overestimate of the nominal distance. It seems to work for this example.

There are also what look like fiducial markers which aren't on the same grid. I don't know if those distances are meaningful.

There are also what I think are some partial dots and noise specks that can be cleaned up. Bear in mind that I'm not using the original image. I took the captured figure and removed the padding and markers from it. At that point, I assume most noise features are my own creation and not representative of the source.

I suppose that the fiducials and some of the edge issues can be removed the same way:

Dm = mean(Dn(:));
baddist = Dn>(1.1*Dm) | Dn<(0.9*Dm);

[benl23]

Hi DGM,

I really want to thank you for your help, It really helped me understanding how to deal with dots on the edge and not considering "Bad distances". I was able to modify your script on mine images dealing with noise and inaccuracies.. The image I attached was a "Good case"...

Another thing I would like to do now is measuring the radius dimension, in pixel, on 4 different preferential directions for each dot of the image.

If you have suggestions, I would really appreciate it.

Thanks again!

[DGM]

You mean the radius of the dot itself?

Does it matter whether we measure radius in the exact direction of the dot's neighbors or can we just assume some nominal angles based on the pattern?

Considering the relative size of the dots I have a feeling that the results are going to be significantly influenced by the image resolution and where exactly the edge pixels happen to line up. I'm not sure what exactly you're using it for, but metrics like EquivDiameter would tend to avoid issues with the jaggedness. Metrics like Eccentricity or the Feret properties might provide shape/orientation information (since EquivDiameter doesn't). That's just a thought. I don't know if it would help for what you need.

[Image Analyst]

In code, for the binary image of your dots:

props = regionprops(binaryImage, 'EquivDiameter');
allDiameters = [props.EquivDiameter];
allRadii = sqrt(allDiameters/pi);

which seems reasonable. Given the very small number of pixels in each dot, I think measuring the radius of each dot in the 4 major directions would give you very quantized value. Like either 1, 2, or 3 pixels.

[benl23]

Hi Image Analyst,

thanks for you help first of all. The image I shared was a low resolution one and I would consider it a "good case".

As you can see in the new image attached, the dots diamaters can be really different and I want to investigate if there is an expansion / reduction of the dots dimention along preferential directions. I will increase the resolution ( higher number of pixels for each dot ) to have more robust results and better visualize the resultsI

[Image Analyst]

Do you have a question? You can maybe rotate the image so the blobs are in a rectangular array using radon(). See attached demo. Then find rows and columns by taking a sum of gray levels vertically and horizontally. Then you can get the average area or diameter for each row and each column. Write back if you have any questions, and be sure to state your question or need clearly.

Answer 2

[KSSV]

Read about the function knnsearch, this will give you the specified number of nearest points from a set of points for a given point along with distance.

https://in.mathworks.com/help/stats/knnsearch.html

Answer 3

[Image Analyst]

Looks like you could easily just threshold this to find the blobs

mask = grayImage < someThreshold;

Then call regionprops to get centroids

props = regionprops(mask, 'Centroid');
xy = vertcat(props.Centroid)

The numbering is not random, though it may seem like it. It numbers blobs from left to right as it scans the image and encounters them. And from top to bottom in the event two blobs start in the same column, like blobs 11 and 12 in the image below. See attached demo.

Use knnsearch() or pdist2() to find distance between points or sets of points, if you have the Statistics and Machine Learning Toolbox.