Reordering bounding box coordinates in a cell array from left to right, top to bottom.

Hello! I am finding the centroids of a grid of spots. Once the centroids are found, I am creating a bounding boxes that I call my Area of Interests (AOIs). The centroiding and boxing process is working wonderfully! However, the centroids(shown as red stars below), and by extension the AOIs, need to be reordered for further processing. For instance, the image below shows the centroids and bounding boxes for my entire image... This is a 1536x1536 image. 15 columns of boxes , and 16 rows of boxes . Each box is 100x100 pixels. (Yes, they overlap). I discovered that the centroids are put into an array "out of order" for my purposes. My question is, how do I find the centroids, then reorder the centroid xy coordinate pairs so that they are in order from left to right, top to bottom (as shown in the enlarged image). Although they look like perfect rows and columns, they are not, and looking for common x-values and y-values failed me. My centroiding code and bounding box code is shown below. I have heard suggestions using ginput to define a template, but was wondering if there is a more automated way? Thank you for any help you may provide!

aoi_size=100; %define aoi of dimensions 100x100 pixels

% Find centroids
cc = bwconncomp(combined_ref_image); 
s = regionprops(cc, 'Centroid');
ref_Centroids = cat(1, s.Centroid);

%plot centroids and bounding boxes on my original image. 
figure
imshow(combined_ref_image);
hold on;
for i = 1:size(ref_Centroids,1)
    plot(ref_Centroids(i,1), ref_Centroids(i,2), 'r*');
    x1 = ref_Centroids(i,1) - aoi_size / 2;
    y1 = ref_Centroids(i,2) - aoi_size / 2;
    boundingBox = [x1 y1 aoi_size aoi_size];
    AOIs{i}=boundingBox;
    rectangle('Position', boundingBox, 'EdgeColor', 'r', 'LineWidth', 2);
end

Answer 1

[Scott Kaiser]

I found a solution that worked after some trial and error! I sorted the 2d array based on the y-values first. Then I pulled out a subset of the array. this subset isolated one row of spots at a time. I then sorted this subset based on their x positions, and stored it back in the sorted_ref_centroids array. I iterated through every row and it worked great!

% Sort the entire coordinate array based on y-values
X=ref_Centroids(:,1);
Y=ref_Centroids(:,2);
[sortedY, sortIndex] = sort(Y);
sortedX = X(sortIndex);
sorted_ref_Centroids(:,1)=sortedX;
sorted_ref_Centroids(:,2)=sortedY;

for i=0:N_r-1 %N_r is the number of rows of spots
% Now sort portions of the array. (y-values between 1-102,102-204, etc)
    
     idx =i*N_c+1:(i+1)*N_c;%N_c is the number of columns of spots
   
    %extract only part of the ref_centroids to sort 
    X=sorted_ref_Centroids(idx(1):idx(end),1);
    Y=sorted_ref_Centroids(idx(1):idx(end),2);
    
    %now sort this subset based on x-values.
    [sortedX, sortIndex] = sort(X);
    sortedY = Y(sortIndex);
    
    %put this reordered subset back into ref_centroids
    sorted_ref_Centroids(idx(1):idx(end),1)=sortedX;
    sorted_ref_Centroids(idx(1):idx(end),2)=sortedY;
  
end

Answer 2

[Image Analyst]

If you know how many rows and columns there are I'd use kmeans() and sort() to reorder the AOIs in a logical left-to-right, top-to-bottom manner.