1
$\begingroup$

I've spent about 2 days trying to understand this piece of code (from here) that applies an affine/projective transformation to an image. I will link bits of the code that I'm struggling to understand and add comments on what I think it's trying to do. In particular, the author's original comments I'll label as //.

//      COMPUTE NEW BASIS
// X1, Y1 : upleft corner
// X2, Y2 : upright corner
// X3, Y3 : downleft corner 
// sx     : x-size of output image
// sy     : y-size of output image
x12 = (X2-X1)/(float)(*sx); 
y12 = (Y2-Y1)/(float)(*sx);
x13 = (X3-X1)/(float)(*sy);
y13 = (Y3-Y1)/(float)(*sy);

Q1. I can see that this part as the comment says, finds a new normalized basis but I'm unsure exactly why we need to find one to model an affine transformation?

// x4, y4 : downright corner (for projective transform)

if (y4) 
{ 
    xx=((x4-X1)*(Y3-Y1)-(y4-Y1)*(X3-X1))/((X2-X1)*(Y3-Y1)-(Y2-Y1)*(X3-X1));
    yy=((x4-X1)*(Y2-Y1)-(y4-Y1)*(X2-X1))/((X3-X1)*(Y2-Y1)-(Y3-Y1)*(X2-X1));
    a = (yy-1.0)/(1.0-xx-yy);
    b = (xx-1.0)/(1.0-xx-yy);
} 
else 
{
    a=b=0.0;
}

After doing some internet search, I manage to find equations from here that the xx and yy equations solve for the "intersection point of two line segments in 2 dimensions". An image will be linked below.

START IMAGE. Intersection of two lines

END IMAGE.

Q2. I don't understand how he uses the xx and yy equations to solve for a & b?

Q3. I am unsure of what a and b are. My best guess is that they are the bottom row of a projective transformation matrix shown below:

$$ \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a & b & 1 \\ \end{bmatrix} $$

This is because the code sets a = b = 0.0 if we're not doing a projective transform, which should then make it an affine transformation matrix.

Now is where the main loop happens:

for (x=0;x<sx;x++) 
    for (y=0;y<sy;y++) {
        fx = (float)x + 0.5;
        fy = (float)y + 0.5;
        d = a*fx/(float)(*sx)+b*fy/(float)(*sy)+1.0;
        xx = (a+1.0)*fx/d;
        yy = (b+1.0)*fy/d;
        xp = X1 + xx*x12 + yy*x13;
        yp = Y1 + xx*y12 + yy*y13;
    }

Q4. Why does he add 0.5 to the original x and y coordinate? My best guess is that the code's trying to map the centre of each pixel rather than the edge to the new image:

Pixels

Q5. In

d = a*fx/(float)(*sx)+b*fy/(float)(*sy)+1.0;
xx = (a+1.0)*fx/d;
yy = (b+1.0)*fy/d;

what are they trying to accomplish here? My best guess is that d is the third component of the output homogeneous coordinate:

$$ \begin{bmatrix} xx\\ yy\\ d\\ \end{bmatrix} $$

calculated from the dot product of the third row of the (now normalised) transformation matrix from earlier and the input homogeneous vector:

$$ \begin{bmatrix} \frac{a}{sx} & \frac{b}{sy} & 1 \\ \end{bmatrix} \begin{bmatrix} fx\\ fy\\ 1\\ \end{bmatrix} = a*fx/sx+b*fy/sy+1.0 $$

Then the division

xx = (a+1.0)*fx/d;
yy = (b+1.0)*fy/d;

would just transform the homogeneous coordinates back to Euclidean coordinates, corresponding to the output image pixel location. I noted that if a=b=0.0 (so not projective), then (a+1.0)=(b+1.0)=d=1.0. I'm however not sure about why we have to multiply by (a+1.0) or (b+1.0). But again, I do not know if I'm on the right track or not as I do not have anyone to help me with this code.

Q7. The final operation

xp = X1 + xx*x12 + yy*x13;
yp = Y1 + xx*y12 + yy*y13;

I suppose is literally the dot product of the first two rows of the transformation matrix with the Euclidean coordinates as so:

$$ \begin{bmatrix} x12 & x13 & X_{1} \\ y12 & y13 & Y_{1} \end{bmatrix} \begin{bmatrix} xx\\ yy\\ 1\\ \end{bmatrix} = \begin{bmatrix} xp\\ yp\\ \end{bmatrix} $$

Which brings me to my question, how does this achieve an affine transformation?

I suspect my lack of formal training could be why I'm not understanding how the code models an affine transformation. I'd appreciate some light shed on this piece of code!

Cheers!

$\endgroup$
  • $\begingroup$ An affine transformation is is any transformation that preserves points, lines and planes. This can be translation, skewing and rotation - and combinations thereof. $\endgroup$ – beyond Sep 11 '18 at 8:23
  • $\begingroup$ Hi @beyond, thanks for your input. Are you able to shed some light on the code? $\endgroup$ – theunseen Sep 11 '18 at 9:00
  • $\begingroup$ To be honest, the code seems a bit elaborate for something as simple as applying an affine transformation to an image. The projection bit I don't get, so an example of input/expected output/actual output would be ideal. $\endgroup$ – beyond Sep 11 '18 at 12:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.