Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Finding a grid from intersections

Subject: Finding a grid from intersections

From: Chenge Qu

Date: 14 Jan, 2013 02:20:14

Message: 1 of 7

Hello all,

I'd like to extract a grid from the (approximate) location of a few intersections (say, ~5 intersections for a 10x10 grid). The grid spacing is known, but the grid itself may be skewed, rotated, or both relative to the intersection coordinates I have. In other words, I want to find how the grid is skewed/rotated relative to my coordinates.

Hopefully that was clear enough! Any ideas?

Thanks in advance!

Chenge

Subject: Finding a grid from intersections

From: Roger Stafford

Date: 14 Jan, 2013 02:48:11

Message: 2 of 7

"Chenge Qu" wrote in message <kcvq0u$8ie$1@newscl01ah.mathworks.com>...
> I'd like to extract a grid from the (approximate) location of a few intersections (say, ~5 intersections for a 10x10 grid). The grid spacing is known, but the grid itself may be skewed, rotated, or both relative to the intersection coordinates I have. In other words, I want to find how the grid is skewed/rotated relative to my coordinates.
- - - - - - - - - -
  If I understand you correctly, you have a grid of points that has undergone an affine transformation from some kind of standard grid with orthogonal lines. If you can establish a correspondence between three nonlinear new intersections and three of the original grid, that is sufficient to uniquely determine the transformation.

  Just write the equations:

 X = a*x+b*y+c
 Y = d*x+e*y+f

The coordinates of the new and old intersections give you six linear equations in the six unknown coefficients which is sufficient to solve them unless they are for colinear points. Use matlab's backslash operator to solve them.

Roger Stafford

Subject: Finding a grid from intersections

From: Chenge Qu

Date: 14 Jan, 2013 02:56:11

Message: 3 of 7

"Roger Stafford" wrote in message <kcvrlb$dkf$1@newscl01ah.mathworks.com>...
> "Chenge Qu" wrote in message <kcvq0u$8ie$1@newscl01ah.mathworks.com>...
> > I'd like to extract a grid from the (approximate) location of a few intersections (say, ~5 intersections for a 10x10 grid). The grid spacing is known, but the grid itself may be skewed, rotated, or both relative to the intersection coordinates I have. In other words, I want to find how the grid is skewed/rotated relative to my coordinates.
> - - - - - - - - - -
> If I understand you correctly, you have a grid of points that has undergone an affine transformation from some kind of standard grid with orthogonal lines. If you can establish a correspondence between three nonlinear new intersections and three of the original grid, that is sufficient to uniquely determine the transformation.
>
> Just write the equations:
>
> X = a*x+b*y+c
> Y = d*x+e*y+f
>
> The coordinates of the new and old intersections give you six linear equations in the six unknown coefficients which is sufficient to solve them unless they are for colinear points. Use matlab's backslash operator to solve them.
>
> Roger Stafford

Thanks for the reply! The problem is that I don't have any coordinates from the original grid. All I know is that it's a standard grid with orthogonal lines, like you said, and also the grid spacing.

Sorry for the confusion.

Subject: Finding a grid from intersections

From: Matt J

Date: 14 Jan, 2013 03:25:11

Message: 4 of 7

"Chenge Qu" wrote in message <kcvs4b$f7o$1@newscl01ah.mathworks.com>...
>
> Thanks for the reply! The problem is that I don't have any coordinates from the original grid. All I know is that it's a standard grid with orthogonal lines, like you said, and also the grid spacing.
================

Since you know the grid-spacing, that's enough to construct the original points of the grid up to an irrelevant translation.

Subject: Finding a grid from intersections

From: Roger Stafford

Date: 14 Jan, 2013 04:29:10

Message: 5 of 7

"Chenge Qu" wrote in message <kcvs4b$f7o$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <kcvrlb$dkf$1@newscl01ah.mathworks.com>...
> > "Chenge Qu" wrote in message <kcvq0u$8ie$1@newscl01ah.mathworks.com>...
> > > I'd like to extract a grid from the (approximate) location of a few intersections (say, ~5 intersections for a 10x10 grid). The grid spacing is known, but the grid itself may be skewed, rotated, or both relative to the intersection coordinates I have. In other words, I want to find how the grid is skewed/rotated relative to my coordinates.
> > - - - - - - - - - -
> > If I understand you correctly, you have a grid of points that has undergone an affine transformation from some kind of standard grid with orthogonal lines. If you can establish a correspondence between three nonlinear new intersections and three of the original grid, that is sufficient to uniquely determine the transformation.
> >
> > Just write the equations:
> >
> > X = a*x+b*y+c
> > Y = d*x+e*y+f
> >
> > The coordinates of the new and old intersections give you six linear equations in the six unknown coefficients which is sufficient to solve them unless they are for colinear points. Use matlab's backslash operator to solve them.
> >
> > Roger Stafford
>
> Thanks for the reply! The problem is that I don't have any coordinates from the original grid. All I know is that it's a standard grid with orthogonal lines, like you said, and also the grid spacing.
>
> Sorry for the confusion.
- - - - - - - - -
  You have said that you have a "10x10 grid". What exactly do you mean by that? Does this mean you have two sets of uniformly-spaced parallel lines defined and are able to determine any intersection of one in one set with any one in the other set? Presumably this means if you were to find an intersection between two of these lines you would also have information about which pair of lines were used.

  If we also assume that you know which of the two sets of lines was originally oriented in the x-direction with the other set being in the y-direction, and if you know the grid spacing in the old set, then you can hypothesize an original grid as beginning at (0,0) with the first pair of lines from the two sets and with the known grid spacing after that. This suffices to establish all the coordinates of intersections in this artificial old grid that correspond to three (non-colinear) intersections in the new grid and to thereby determine the six coefficients I previously mentioned. Of these it is only 'c' and 'f' that are dependent on having commenced at (0,0) and are therefore also artificial. The remaining four coefficients, 'a', 'b', 'd', 'e', which are independent of this arbitrary starting point are sufficient to determine what you have called the rotation/skewness, though they
also express a scale factor change as well.

  Does this help you?

Roger Stafford

Subject: Finding a grid from intersections

From: Chenge Qu

Date: 15 Jan, 2013 03:25:14

Message: 6 of 7

> You have said that you have a "10x10 grid". What exactly do you mean by that? Does this mean you have two sets of uniformly-spaced parallel lines defined and are able to determine any intersection of one in one set with any one in the other set? Presumably this means if you were to find an intersection between two of these lines you would also have information about which pair of lines were used.
>
> If we also assume that you know which of the two sets of lines was originally oriented in the x-direction with the other set being in the y-direction, and if you know the grid spacing in the old set, then you can hypothesize an original grid as beginning at (0,0) with the first pair of lines from the two sets and with the known grid spacing after that. This suffices to establish all the coordinates of intersections in this artificial old grid that correspond to three (non-colinear) intersections in the new grid and to thereby determine the six coefficients I previously mentioned. Of these it is only 'c' and 'f' that are dependent on having commenced at (0,0) and are therefore also artificial. The remaining four coefficients, 'a', 'b', 'd', 'e', which are independent of this arbitrary starting point are sufficient to determine what you have called the rotation/skewness, though they

> also express a scale factor change as well.
>
> Does this help you?
>
> Roger Stafford

Okay, well, the real problem is this--I have a very large lattice (which may be square or skewed) which contains atoms in some of its cells, and also a camera that is not necessarily aligned with the lattice. I'd like to find the alignment of the camera with the lattice, as well as the skew of the lattice, from an image of a section of the lattice. The image contains roughly 100 cells of the lattice, of which roughly 5 are filled with atoms. I'm able to find find the (image) coordinates of the atoms present, but I don't actually know which sites they're in either coordinate system.

What I'm currently trying is this:

1) Choose any known atom location as the origin.
2) Using angles theta, alpha (rotation, skew), construct a lattice.
3) Evaluate how close the other atoms are to the sites of this lattice (perhaps with some kind of least-squares estimator).
4) Optimize this "closeness" wrt theta, alpha.

Subject: Finding a grid from intersections

From: Matt J

Date: 15 Jan, 2013 20:40:21

Message: 7 of 7

"Chenge Qu" wrote in message <kd2i6q$mtj$1@newscl01ah.mathworks.com>...
>
> Okay, well, the real problem is this--I have a very large lattice (which may be square or skewed) which contains atoms in some of its cells, and also a camera that is not necessarily aligned with the lattice. I'd like to find the alignment of the camera with the lattice, as well as the skew of the lattice, from an image of a section of the lattice. The image contains roughly 100 cells of the lattice, of which roughly 5 are filled with atoms. I'm able to find find the (image) coordinates of the atoms present, but I don't actually know which sites they're in either coordinate system.
>
> What I'm currently trying is this:
>
> 1) Choose any known atom location as the origin.
> 2) Using angles theta, alpha (rotation, skew), construct a lattice.
> 3) Evaluate how close the other atoms are to the sites of this lattice (perhaps with some kind of least-squares estimator).
> 4) Optimize this "closeness" wrt theta, alpha.



http://www.mathworks.com/matlabcentral/fileexchange/28760-2d-2d-projective-homography-3x3-estimation

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us