2

I am trying find a 2-D affine tranform given two points using the solution given by Kloss, and Kloss in “N-Dimensional Linear Vector Field Regression with NumPy.” (2010, The Python Papers Source Codes 2).

Article source code.

They give an approach to finding the affine transform connecting two sets of points y and x where the transform is represented by a matrix A and a vector b ( i.e. the matrix equation y = Ax+b).

In two dimensions you have 6 unknowns, four defining the 2x2 A matrix and 2 defining b.

However, in the example script and in the paper describing it they have unknowns t=n^2+n where n is the number of points, which means you need six points, which for the 2D case is actually 12 known values (i.e. x and y values of each point on an image).

they test this via:

def solve(point_list):
    """
    This function solves the linear equation system involved in the n
    dimensional linear extrapolation of a vector field to an arbitrary point.

    f(x) = x * A + b

    with:
       A - The "slope" of the affine function in an n x n matrix.
       b - The "offset" value for the n dimensional zero vector.

    The function takes a list of n+1 point-value tuples (x, f(x)) and returns
    the matrix A and the vector b. In case anything goes wrong, the function
    returns the tuple (None, None).

    These can then be used to compute directly any value in the linear
    vector field.
    """dimensions = len(point_list[0][0])
    unknowns = dimensions ** 2 + dimensions
    number_points = len(point_list[0]) 
    # Bail out if we do not have enough data.
    if number_points < unknowns:
        print ’For a %d dimensional problem I need at least %d data points.’ \ % (dimensions, unknowns)  
        print ’Only %d data points were given.’ % number_points return None, None.

...

The question:

Why do they say you need 6 points to get a 2D affine transform?

opencv getAffineTransform only needs 3 data points to find a point in 2D, which is the intuitive number, since 3 points define a plane. And when I take the above conditional test out of the Kloss and Kloss code, it works for 3 points in 2D.

E. Douglas
  • 234
  • 1
  • 3
  • 11

3 Answers3

6

Why do they say you need 6 points to get a 2D affine transform?

For such transformations, it is convenient to work with homogenous coordinates that introduce a third w coordinate, i.e:

  • (x, y) becomes (x, y, w),
  • two points are equivalent iff x'/w' = x/w and y'/w'= y/w.

So you can typically use w = 1.

With this system you can represent 2D transformations (translation, rotation, etc) with a matrix multiplication:

[x']       [x]
[y'] = A . [y]
[1 ]       [1]

An affine transformation is a combination of a translation, scaling and rotation transformations, which can be expressed as:

    [1 0 tx]   [Sx 0  0]   [cos(a) -sin(a) 0]   [a b c]
A = [0 1 ty] . [0  Sy 0] . [sin(a)  cos(a) 0] = [d e f]
    [0 0 1 ]   [0  0  1]   [0       0      1]   [0 0 1]

So you have 6 parameters (a.k.a unknowns), thus you need 3 pairs of points to solve the system since each pair of points will give you 2 equations.

In other words you need (at least) 6 points (= 3 pairs) to compute your transformation.

Note: you need at least 6 points in the sense that if you get more than that, then your system is overdetermined which means you can find an approximate solution e.g with least squares, which is the point of your article.

deltheil
  • 15,496
  • 2
  • 44
  • 64
  • In comment to your edit, you do not need 6 points to approach the problem in a least squared sense. – gg349 Nov 16 '13 at 00:44
  • and their definition of points is not your definition of points, that coincides always with the number of unknowns anyway. – gg349 Nov 16 '13 at 09:50
  • @flebool: if you have > 3 pairs then the least squares is the way to go. With exactly 3 pairs, there is no need. Otherwise: my last edit adds some more precisions vs. the number of points/pairs (indeed we have `unknowns/dimensions = dimensions + 1`). – deltheil Nov 16 '13 at 18:35
  • after your edits, you are presenting the criterion that I posted in the first place, `m>=n+1`. and there are many ways for estimating an affine transform, with least squares being just the most well known. – gg349 Nov 16 '13 at 19:00
  • The question concerns the min. nb. of points for 2D affine transform retrieval: my answer focuses on this. The other part (as with my edits) are no more than additions. Also I don't see the point with your 1st comment (?), plus, as far as the least squares are concerned I used `e.g` precisely to indicate that this is one of the possible methods. – deltheil Nov 16 '13 at 19:14
  • The question is clear and in italic, about the article and why they say what they say, and this comes from their discussion of the general case in the article, then applied to 2D. The point of the first comment is that it is perfectly fine to set up the least square approach for an estimate on an underdetermined problem (though less common). While you suggest above that since the system is overdetermined, then you can use least squares. – gg349 Nov 16 '13 at 20:32
  • I've re-edited my answer to get rid of these (minor) additions that your answer covered. – deltheil Nov 17 '13 at 13:35
4

Getting to the point,

Why do they say you need 6 points to get a 2D affine transform?

I guess you are referring to the bit just before eq. (4) of the article, where they say that you need at least m>=n^2+n. There, m is the number of couples of points and n is the number of dimensions.

I think they were not paying much attention, and they meant m>=n+1.

This would mean that in 2D you would need n+1=3 couples of points in , and in 3D we would need n+1=4 couples of points to fully define the affine transformation. Notice that you will be able to find a solution as long as the points are not collinear.

This is consistent with the opencv link you posted, with 3x2=6 input nubers (3 source points, each with two coordinates) and similarly 6 output numbers:

(x1,y1,x2,y2,x3,y3) into X[x1,y1],Y[x1,y1],X[x2,y2],Y[x2,y2],X[x3,y3],Y[x3,y3]

(Notice however that opencv evaluates the exact affine transformation, while the article doesn't)

Said that, you often don't care about this.

You may need an affine transformation with fewer points then m, and you are interested in one of the many solutions.

You more often need an estimate of the transformation and minimize the error, for example in the least square sense, and this is what the article is about: do it fast and with numpy.

gg349
  • 21,996
  • 5
  • 54
  • 64
  • Thank you for seeing to the point of my question. You answer concurs with my understanding. Although, I have now found m>n^2+n in three places, in the code and paper I mentioned, as well as in a peer reviewed article: Späth, H. (2004), Fitting affine and orthogonal transformations between two sets of points, Mathematical Communications, 9(1), 27–34. The same error in the three places is troubling, but I have found no other explanation. I will try to contact the authors and see if there is any subtler explanation. http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=1425&lang=en – E. Douglas Nov 19 '13 at 18:21
  • I checked the article out, and the setup and nomenclature of the names is so similar that I wouldn't be surprised if Kloss&Kloss simply copied over Spath's structure. I wouldn't blame them for that, as they clearly state they use Spath's algorithm. Please write here at SO what they reply to you, I am rather curious now.. – gg349 Nov 19 '13 at 19:11
  • 1
    emailed the authors of both papers, but have not heard back from them. Sadly, I did discover that original paper's author, Dr. Späth, has passed away, a memorial talk in his honor is scheduled at the University of Oldenburg: http://www.uni-oldenburg.de/index.php?id=12676&veranid=502 – E. Douglas Apr 29 '14 at 22:27
1

To retrieve 2D affine transformation you need exactly 3 points and they should not lie on one line. For N-dimensional space there is a simple rule: to unambiguously recover affine transformation you should know images of N+1 points that form a simplex --- triangle for 2D, pyramid for 3D, etc. A good explanation of why it's the way it should be, you may find in "Beginner's guide to mapping simplexes affinely". UPD: Authors of the guide have recently published "Workbook on mapping simplexes affinely" that contains many examples of retrieving affine transformation by its action on a certain number of points, maybe you can find something useful there.