User:Andrew Nikitin/Projective transformation

From J Wiki
Jump to: navigation, search

This calculator determines parameters of projective transformation that maps four given points into 4 given points.


Projective plane

Let's consider all triplets of real numbers (x,y,z). We will call triplets (x_1,y_1,z_1) and (x_2,y_2,z_2) equivalent when \exists c: x_1=c x_2, y_1=c y_2, z_1=c z_2. We will call the set of equivalence classes the projective plane and each equivalence class a point on this plane.

Point (x,y) of the regular plane can be identified wit point (x,y,1) of the projective plane and point (x,y,z), z \ne 0 can be identified with point (x/z,y/z) of the regular plane.

Points (x,y,0), x\ne 0 \,\mathrm{or}\, y\ne 0 of the projective plane do not have corresponding points on the regular plane and are called inifinite points.

Point (0,0,0) constitutes a class in itself.

For any given set of coefficients (a,b,c) the set of points defined by a x+b y+c z=0 is called a projective straight line.

Projective transformation

Linear transformation in the projective plane

x'=a_1 x + b_1 y + c_1 z \\
y'=a_2 x + b_2 y + c_2 z \\
z'=a_3 x + b_3 y + c_3 z

corresponds to projective transformation of the regular plane

x'=\frac{a_1 x + b_1 y + c_1}{a_3 x + b_3 y + c_3}\, \\
y'=\frac{a_2 x + b_2 y + c_2}{a_3 x + b_3 y + c_3} .

The important property of this transformation is that it transforms straight lines into straight lines.

The following J verb implements a projective transformation. It accepts a 3-element vector, which represents an arbitrary point on the projective plane. Alternatively, as a shortcut, 2-element vector (x,y) corresponds to finite point (x,y,1). Download script: projective transformation

NB. M is in transposed form compared to natural
amv=:(}:%{:)@(+/ . * 3&({.!.1))"2 1

To visualise the transformation, we will use grid G0 as defined below and transform it to a projected grid. Then we will plot both grids. We will define a variant of the amv verb, called amc, which treats complex numbers as finite points of the projective plane and transforms them appropriately. Download script: projective transformation

amc=: (j./"1@amv +.)
G0=:(<: %~ [: j./~ i.)11

Choosing a projective transformation

A projective transformation is defined by its 9 coefficients, but since projective transformation remains the same if all coefficients are multiplied by a non-zero number, only 8 of them are independent.

If we want point (x_0,y_0,1) to become (x_1,y_1,1) under some projective transformation, then coefficients of this transformation must satisfy

x_1=(a_1 x_0 + b_1 y_0 + c_1)/(a_3 x_0 + b_3 y_0 + c_3) \\
y_1=(a_2 x_0 + b_2 y_0 + c_2)/(a_3 x_0 + b_3 y_0 + c_3)


x_1 (a_3 x_0 + b_3 y_0 + c_3)=(a_1 x_0 + b_1 y_0 + c_1)\, \\
y_1 (a_3 x_0 + b_3 y_0 + c_3)=(a_2 x_0 + b_2 y_0 + c_2) .

0 : 0
x0 y0 1 0  0  0 -x1x0 -x1y0 -x1
0  0  0 x0 y0 1 -y1x0 -y1y0 -y1

   straight lines are set of points (x,y,z) so that ax+by+cz=0, denoted (a,b,c)
   lx0=.1 0 0 NB. vertical line x=0
   lx1=.1 0 _1 NB. vertical line x=1
   lx2=.1 0 _2 NB. vertical x=2
   cleanup (1 0 _2 mp %. M) mp |:1,.~ M amv t


If M is a transformation, then straight line L=(a,b,c) transforms into L·inv(M) Indeed, (L·inv(M))·(M p)=L p=0.