Organize randomly distributed grid points into a 2D matrix

Hello, I have a few pictures for calibrating images with a poster containing grid points. The picture is thresholded and points are extracted through regionprops. I then use the bounding box of the regions to recalculate the centroid with the actual grey levels of the image (more accurate in my opinion).

My question is that I have now an array of X(:) and Y(:) positions that give the positions of the grid on the image.

Now I want to organize these values into I(:) and J(:) values where I and J contain the point coordinate on the grid on the X and Y axis. Something like the point in the middle (doesn't matter the exact middle) is (0,0), the the point on the right is (1,0) and the one up is (0,1).

The problem is the image distortion. I cannot make a simple sorting algorithm like for example [~,index]=sort(X+1000*Y). But the image is regular enough to know the points at left right up and down of any point.

Here is an example image:

You should look at the closer and smaller points (around 10000 points) not the 42 big ones.

I did an algorithm that detects the closest point on the right of any point and below any point. This way:

dx=x'*ones(size(x))-ones(size(x))'*x;
dy=y'*ones(size(y))-ones(size(y))'*y;
xdist=(dx/10).^2+dy.^2;
ydist=dx.^2+(dy/10).^2;
right=xdist;right(dx<=0)=Inf;
down=ydist;down(dy<=0)=Inf;
[minx,mx]=min(right);
mx(minx>5)=0;
[miny,my]=min(down);
my(miny>5)=0;

This will make a 10000x10000 matrix of all distances from any point to any point distorted in x and y directions. And then take their minima (in the positive values). This is quite brutal for me...

After that 'mx' points to the index of the closest rightwards point for any point. And 'my' does the same thing. Then I do an algorithm with for loops to iterate starting from the center (0,0) until I fill all the points into I and J. Kind of like bucket tool in Paint. Remaining unfilled are left NaN. Anyway this for loop in MATLAB takes a lot of time.

Isn't there any tool in MATLAB to rearrange 2D grid points such as sort? But sort2D?

Cheers,

Amid.

Answer 1

[Daniel]

Hello @hmi amid,

I stumbled accross your question because I have a similar problem. The image you have isn't ideal for my solution but others might have something similar which favours my solution a little better.

Also, I didn't check the introduction date of all functions I used. So this approach might not be possible for your release (back in 2017). Version R2021b works just fine, though.

In summary this algorithm runs a lot faster. It is based around a labled matrix creation in horizontal and vertical direction which is later on used as row and column index.

img = imread("dotgridMatlabQuestion.jpeg");
img = rgb2gray(img);
imi = imcomplement(img); %invert the image (dark to bright)
bw = imbinarize(imi); %binarize to a logical mask
bws = bwpropfilt(bw,'Area',[20 100]); %filter out too small or too big regions
props = regionprops('table',bws);
shor = strel('line',60,0); %horizontal structural element with 60 pixels 0° rotation
sver = strel('line',60,90); %vertical structural element with 60 pixels 90° rotation
bwhor = imdilate(bws,shor);
bwver = imdilate(bws,sver);
% show the intermediate step
% figure()
% imshowpair(bwhor,bwver)

Now that I created two images where the detected dots were connected horizontally and vertically, respectively, I can create a label matrix for each of them. Afterwards, the label for each reagion is also the index of each row and column, respectively.

rc = round(props.Centroid); %these rounded centroids will be used to inded into the labled matrix image
cchor = bwconncomp(bwhor');
labledhor = labelmatrix(cchor)'; %label matrix horizontally
ccver = bwconncomp(bwver);
labledver = labelmatrix(ccver); %label matrix vertically
props.row = labledhor(sub2ind(size(labledhor),rc(:,2),rc(:,1)));
props.col = labledver(sub2ind(size(labledver),rc(:,2),rc(:,1)));
sortedProps = sortrows(props,{'col','row'}); %sort them according to column and row
sortedProps(1:5,:)

ans = 5x5 table
    Area        Centroid                BoundingBox            row    col
    ____    ________________    ___________________________    ___    ___

     24       10.5    2.2917    6.5     0.5       8       4     1      1 
     41     10.171     14.78    6.5    11.5       8       7     3      1 
     42     9.9762    28.667    6.5    24.5       7       8     4      1 
     37     9.7568    42.432    6.5    39.5       7       6     5      1 
     39     9.2564    56.256    5.5    52.5       7       7     6      1 

I created an index mask to illustrate the row and column index of each detected centroid of the original image in a rectangular matrxi.

indxMask = false(max(props.row),max(props.col)); %pre allocate
indxMask(sub2ind(size(indxMask),sortedProps.row,sortedProps.col)) = true;
figure()
imshow(indxMask)

As you can see, it has a problem with the edges just because that's how the labeling of Matlab works. I still believe it is a good approach since it works without any loop.

If your grid is not always equally spaced or rotated, it is possible to detect the point spacing and rotation via a FourierTransform first (which I did in the end). The length of the structural elements (strel) may be smaller but all holes need to be spanned so the algorithm can work. If the grid is too heavily warped, this may also break the connection of a dot grid.

Many regards