CODEWITHSUNDEEP
matlabopencvcomputer-visioncurve-fittingdata-fitting
schmatz
schmatz

Reputation: 183

Detecting grid orientation and properties

I have a collection of many points arranged in a uniform grid-like fashion. Given these points, how do I detect properties of this grid, such as it's rotation, spacing between lines, etc? If there was some algorithm to fit many parallel and perpendicular lines to this data, then I could average the distance between lines, angle, and so on and so forth. What is the best way to do this?

UPDATE: The data that I'm working with looks roughly like this:

enter image description here

It will be cleaner in the future, but I just need some way to interpolate and analyze that grid like pattern.

Upvotes: 1

Views: 1681

Answers (3)

Michael Langbein
Michael Langbein

Reputation: 23

If you have each point's coordinates, things might be not so complicated.

It might be a good idea to do a PCA on those coordinates. The first principal component will be the axis along of the longer side of your grid, the second principal component will be the axis of the shorter side.

With those new axes, you could run a sweep-line algorithm along the principal axis, which will allow you to assign a row-number to each point. Another sweep along the second axis will allow you to assign a column-number.

Upvotes: 0

anandr
anandr

Reputation: 1662

If you have only image of the grid, you may try radon function from "Image processing toolbox". It will give you angles and from radon transform you can recalculate distance between lines of points on your image.

Here is a code sample for radon function

% First we generate a grid of points on image
ImgW        = 400;
ImgH        = 300;
DIdx                    = ImgH + round(rand(1)*ImgH/10);
ImgGrid                 = zeros(ImgH,ImgW);
ImgGrid(1:DIdx:end)     = 1;

% Then we calculate radon transform
theta                   = 0:0.1:180;
[R,xp]                  = radon(ImgGrid,theta);

% Then we calculate standard deviation for each angle of R
Rstd                    = std(R);
% and find maximal value of std(R) columnwise
[RstdMax,RstdIdx]       = max(Rstd);
ThMax                   = theta(RstdIdx);

% Now we show results
figure('Color','w');
subplot(2,2,1);     imshow( ImgGrid );
                    axis on;
                    colormap(hot(255));
                    title('Grid image');
                    line( ImgW/2+[-1 +1]*min(ImgW,ImgH)/2*cosd(-ThMax), ...
                          ImgH/2+[-1 +1]*min(ImgW,ImgH)/2*sind(-ThMax), 'Color','y' );
subplot(2,2,3);     plot(xp,R(:,RstdIdx),'.-');
                    title(sprintf('Profile at %.2f deg (the yellow line)',ThMax));

subplot(2,2,2);     imagesc( log10(R+1), 'Xdata',theta, 'Ydata',xp );
                    axis on;
                    colormap(hot(255));
                    xlabel('\theta (degrees)');
                    ylabel('x''');

subplot(2,2,4);     plot(theta,Rstd,'.-');
                    title('std(R)');

BUT in general case this will not give you lattice vectors for the grid! This will give you only distance between lines of points instead. If you need lattice vectors you have to recalculate them. But if you are lucky enough and your lattice is rectangular... hope you got the point ;o)

You are even more lucky if you have (x,y) coordinates of your points. The approach that CST-Link proposed is somewhat "too brute-force". I'd rather calculate the "structure factor" for your points (see http://en.wikipedia.org/wiki/Structure_factor and the tutorial links at the end of the article) and analyzed its maxima.

Upvotes: 0

user2271770
user2271770

Reputation:

If the points are placed on a grid, then the squared distance between 2 points is d²×(m² + n²) where d is the grid constant (assume that it is a 2D rectangular grid with the same constant in both principal directions), and m, n are integer numbers defining the (affine) difference between the two points (or, simpler, the number of grid intervals between the two points along the "x" and "y" axes) So:

  • compute the squared distances between a point and all other points;
  • by dividing them to the minimum one, you'll get rational numbers that give you hints about the grid constant d and the relative "coordinates" m, n.

Upvotes: 1

Related Questions