Sort or place several points into the nearst point in an unknown a x b grid, and get each point's (i,j) index in the grid.

Hi I encountered a problem when I try to allocate K points into a horzontal/vertical grid of unkonwn size.

Suppose there are variable number (k) points, each have a coordination recorded in a Kx2 matrix M.

M(:,1) is the x coordinates for all these k points, and M(:,2) is the y coordinates for all these k points.

These points could be roughly fitted into unknown a x unknown b grid with the minimum of offset for each point..

Is there a way to get the number a and b, and get the index (i,j) for each ppint so that each point could be fitted to the nearest grid point.

The grid is always in perfect horzontal/vertical direction without skew.

Thanks.

% demo for M
M = [ -539.7520  572.6035
    -365.0520  573.6035
    -190.3520  572.6035
    -15.6520  574.6035
    159.0480  571.6035
    333.7480  572.6035
    -536.8940 -292.9921
    -362.1940 -296.9921
    -187.4940 -293.9921
    -12.7940 -296.9921
    161.9060 -296.9921
    336.6060 -296.9921
    -536.8940 -122.2920
    -362.1940 -124.2920
    -187.4940 -122.2920
    -12.7940 -121.2920
    161.9060 -122.2920
    336.6060 -122.2920
    -536.8940  223.7002
    -362.1940  224.7002
    -187.4940  222.7002
    -12.7940  221.7002
    161.9060  224.7002
    336.6060  224.7002
    -536.8940  399.0250
    -362.1940  398.0250
    -187.4940  399.0250
    -12.7940  397.0250
    161.9060  397.0250
    336.6060  399.0250
    -536.8940   51.2372
    -362.1940   51.2372
    -187.4940   56.2372
    -12.7940   53.2372
    161.9060   51.2372
    336.6060   51.2372
    -536.8940  752.0284
    -362.1940  750.0284
    -187.4940  752.0284
    -12.7940  751.0284
    161.9060  752.0284
    336.6060  752.0284
    -536.8940  927.7109
    -362.1940  925.7109
    -187.4940  927.7109
    -12.7940  926.7109
    161.9060  927.7109
    336.6060  927.7109];
aLeftMost = min(M(:,1));
aTopMost = min(M(:,2));
aLeftTopCornerDist = arrayfun(@(x) abs(M(x,1)-aLeftMost) + abs(M(x,2)-aTopMost),1:size(M,1));
aLeftTopCornerHit = find(aLeftTopCornerDist==min(aLeftTopCornerDist));
aRightBotCornerHit = find(aLeftTopCornerDist==max(aLeftTopCornerDist));
eva = evalclusters(aLeftTopDistAss(:,1),'kmeans','CalinskiHarabasz','KList',1:20);
eva.OptimalK  % often does not get the real optimal rows or columns

Answer 1

[Image Analyst]

You might want to use pdist2 to get an array of distances from every point to every other point. Then take the histogram and look for peaks. The "unit" distances should be one peak, then the diagonal distances would be the next peak, then you'd have additional peaks for distances at multiples of those distances.

[raym]

Works very well.

Below is my raw code:

D = pdist2(aLeftTopDistAss,aLeftTopDistAss);
a = hist(D(:),1000);
aUnitHit = find(a~=0,2);
aUnitDist = (max(D(:))-min(D(:)))*aUnitHit(2)/1000;
nHorSplits = round((aRightMost-aLeftMost)/aUnitDist)+1;
nVerSplits = round((aBotMost-aTopMost)/aUnitDist)+1;
end;assert(nHorSplits*nVerSplits==nImage,'Error:');end
for i =1:nImage
    aLeftTopDistAss(i,3) = round((aLeftTopDistAss(i,1) - aLeftMost)/aUnitDist)+1;
    aLeftTopDistAss(i,4) = round((aLeftTopDistAss(i,2) - aTopMost)/aUnitDist)+1;
end