Deform points in a plane

Question

Point :: (x y) is known.

I have points inside a triangular region.
I know the coordinates of the vertices in initial and final positions. I know the initial coordinates of all the points inside the triangular region.

Now I want to find out the final coordinates of all the points inside the triangular region.

The picture below shows the points in initial and final positions.

Can anyone tell me how to do this in OpenCV and C++ platform??

Can I do this for arbitary shaped contour also?

Answer 1

I'm using 3D coordinates to take account

• translation by vector [u v]
• 2D linear transformation made by matrixabcd

The overall transformation matrix will have the form

    [ a b u]
M = [ c d v]
    [ 0 0 1]

1. Take 3 points A=[x1 y1 1] and B=[x2 y2 1] and C=[x3 y3 1] from the triangle
2. Compare them with their position after transformation A' = [x1' y1' 1] and B'=[x2' y2' 1] and C'=[x3' y3' 1]. Id est: Do your math to get the transformation matrix M so that A' = M A and B' = M B and C' = M C
3. Apply x -> M x to every input points

Edit: Incorporate the translation in the matrix M using Translation in transformation matrix

Edit: It seems "do your math" is not clear for you.

You'll realize that the 3 equations can be written as:

[x1' x2' x3']     [x1 x2 x3]
[y1' y2' y3'] = M [y1 y2 y3]
[1   1   1  ]     [1  1  1 ]

or

X' = M X

Or

M = X . X'^-1

and yes, OpenCV has a function inv() on matrices.

Answer 2

Mathematically, you can do this by computing the barycentric coordinates of each point in the original triangle, and converting back to position using the new coordinates:

given initial triangle vertices A, B, and C, and point p,
find barycentric coordinates (a,b,c) such that a+b+c=1 and p = a*A + b*B + c*C:
  -> solve  [A.x B.x C.x]   [a]     [p.x]
            [A.y B.y C.y] * [b]  =  [p.y]
            [ 1   1   1 ]   [c]     [ 1 ]

then, given new vertices D, E, and F,
resulting point q = a*D + b*E + c*F:
  -> compute  [q.x]  =  [D.x E.x F.x] * [a]
              [q.y]     [D.y E.y F.y]   [b]
                                        [c]

So, in OpenCV:

float p_data[3] =
  { p.x,
    p.y,
    1.0
  };
Mat_<float> p(3, 1, p_data);

float m_data[9] =
  { A.x, B.x, C.x,
    A.y, B.y, C.y,
    1.0, 1.0, 1.0
  };
Mat_<float> M(3, 3, m_data);

Mat_<float> bary(3,1);
cv::solve(M, p, bary, DECOMP_LU);

float n_data[6] =
  { D.x, E.x, F.x,
    D.y, E.y, F.y
  };
Mat_<float> N(2, 3, n_data);

Mat_<float> result(2,1) = N * bary;

To map point_count points at the same time, set the number of columns of p, bary, and result to point_count instead of 1 (while increasing the size of p_data accordingly, etc.)

Depending on the application, it may be more convenient/efficient to explicitly compute the affine matrix first, and apply it directiy:

Mat_<float> Affine = N * M.inv();
Mat_<float> result = Affine * p;