Minimum number of points in retrieval of affine transform?

E. Douglas picture E. Douglas · Nov 15, 2013 · Viewed 8.4k times · Source

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.

Answer

deltheil picture deltheil · Nov 16, 2013

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.