graphics - extracting a quadrilateral image to a rectangle

Question

BOUNTY UPDATE

Following Denis's link, this is how to use the threeblindmiceandamonkey code:

// the destination rect is our 'in' quad
int dw = 300, dh = 250;
double in[4][4] = {{0,0},{dw,0},{dw,dh},{0,dh}};
    // the quad in the source image is our 'out'
double out[4][5] = {{171,72},{331,93},{333,188},{177,210}};
double homo[3][6];
const int ret = mapQuadToQuad(in,out,homo);
    // homo can be used for calculating the x,y of any destination point
// in the source, e.g.
for(int i=0; i<4; i++) {
    double p1[3] = {out[i][0],out[i][7],1};
    double p2[3];
    transformMatrix(p1,p2,homo);
    p2[0] /= p2[2]; // x
    p2[1] /= p2[2]; // y
    printf("%2.2f%2.2f
",p2[0],p2[1]);
}

This provides a transform for converting points in destination to the source - you can of course do it the other way around, but it's tidy to be able to do this for the mixing:

for(int y=0; y<dh; y++) {
    for(int x=0; x<dw; x++) {
        // calc the four corners in source for this
        // destination pixel, and mix

For the mixing, I'm using super-sampling with random points; it works very well, even when there is a big disparity in the source and destination area

---

BACKGROUND QUESTION

In the image at the top, the sign on the side of the van is not face-on to the camera. I want to calculate, as best I can with the pixels I have, what it'd look like face on.

I know the corner coordinates of the quad in the image, and the size of the destination rectangle.

I imagine that this is some kind of loop through the x and y axis doing a Bresenham's line on both dimensions at once with some kind of mixing as pixels in the source and destination images overlap - some sub-pixel mixing of some sort?

What approaches are there, and how do you mix the pixels?

Is there a standard approach for this?

Answer 1

What you want is called planar rectification, and it's not all that simple, I'm afraid. What you need to do is recover the homography that maps this oblique view of the van side onto the front-facing view. Photoshop / etc. have tools to do this for you given some control points; if you want to implement it for yourself you'll have to start delving into computer vision.

Edit - OK, here you go: a Python script to do the warping, using the OpenCV library which has convenient functions to calculate the homography and warp the image for you:

import cv

def warpImage(image, corners, target):
    mat = cv.CreateMat(3, 3, cv.CV_32F)
    cv.GetPerspectiveTransform(corners, target, mat)
    out = cv.CreateMat(height, width, cv.CV_8UC3)
    cv.WarpPerspective(image, out, mat, cv.CV_INTER_CUBIC)
    return out

if __name__ == '__main__':
    width, height = 400, 250
    corners = [(171,72),(331,93),(333,188),(177,210)]
    target = [(0,0),(width,0),(width,height),(0,height)]
    image = cv.LoadImageM('fries.jpg')
    out = warpImage(image, corners, target)
    cv.SaveImage('fries_warped.jpg', out)

And the output:

OpenCV also has C and C++ bindings, or you can use EmguCV for a .NET wrapper; the API is fairly consistent across all languages so you can replicate this in whichever language suits your fancy.