Fast perspective distortion of segments of warped mesh

[akamaus]

I'm working on a C++ project concerning flattening of images on warped surfaces.

Basically, I have two meshes, source and destination, and want to map each warped segment of source into the corresponding rectangle segment of destination.

I have troubles making Perspective distortion operator process small areas of image. The original plan was to crop needed area, distort it and then composite the result into the target image. But looks like nevertheless all the pixels of image are processed during distortion. At least, after cropping source image has black borders and after distortion their color changes.

Currently for each segment of the mesh I make distortion, cropping and composing. The result is correct, but the process is very slow.

Can someone point out, what's the correct and effective sequence of operations for such tasks.

[fmw42]

this is a tough problem.

Untested suggestions and it will likely never be terribly fast because of all the sections you have to process.

0) break up your output (destination) into small rectangular images
1) map the destination rectangle coordinates back to the source as a quadrilateral and crop the bounding area to make a new small image. You may need/want to mask the outside to transparent.
2) adjust the source quadrilateral coordinates for the new size
3) perform the perspective transformation using -virtual-pixel transparent and -mattecolor transparent so that everything outside the area in the transformed image is transparent. Note that the transformation is reverse mapping as it sequences through the whole output and maps that back to the input, gets the coordinate, interpolates and transfers that color to the output.
4) composite the result into your output image


Anthony may have better suggestions as he and I have been discussing doing a piece-wise perspective for some time. See what he has to say later today when he gets online.

[anthony]

This is something that I would like to implement. Both as a grid, and or Tirangular Mesh types of warps. Implementation however is tricky as we need some way
of inputting the coordinates in a form that works reasonably well. Triangular mesh for example needs more than just coordinates but also the joining structure of the coordinates.


As for other alternative techniques, you can limit the viewport of the areas being joined together, but you also need to ensure that all the masks when 'added' also join up correctly to 'unity' That is the addition of all masks for a specific point add to form
a full opaque point (alpha = 1.0) No more, No less.

In the mean time may I suggest you look at a more dedicated program for this. "XMorph"

[akamaus]

Oh, thanks for all the suggestions.

I should have given the additional details.

My destination mesh is always composed of rectangular segments ( I work with photos of printed documents). So I hope I can avoid all the hassle with alpha channel and masks.

Probably my biggest problem now is what I don't understand the semantics of crop operation (and it's friends like roll and extent) and it's interaction with distort. For example, then I tried to distort cropped piece, the resulting image was near the origin of coordinates, not on the place I specified as destination coordinates.

I said, I already have the working snippet. I just need to make it more effective. I post it here, hope it says more than my explanations.

Code: Select all

Image Deskewer::decrumple(const Image &crumpled_img, const Plate &crumpled, const Plate &rect) const {
    assert(rect.nx == crumpled.nx);
    assert(rect.ny == crumpled.ny);

    Point diag = rect.elems.at(rect.nx-1,rect.ny-1).pos - rect.elems.at(0,0).pos;

    Image mosaic(Geometry(diag.x, diag.y), "black");

    Point rect_pos = rect.elems.at(0,0).pos;

    for (int sy = 0; sy < rect.ny-1; sy++) {
        for (int sx = 0; sx < rect.nx-1; sx++) {
            Point c_nw = crumpled.elems.at(sx,sy).pos,
                c_ne = crumpled.elems.at(sx+1,sy).pos,
                c_se = crumpled.elems.at(sx+1,sy+1).pos,
                c_sw = crumpled.elems.at(sx,sy+1).pos;

            Point r_nw = rect.elems.at(sx,sy).pos,
                r_ne = rect.elems.at(sx+1,sy).pos,
                r_se = rect.elems.at(sx+1,sy+1).pos,
                r_sw = rect.elems.at(sx,sy+1).pos;

            Quadrangle c(c_nw, c_ne, c_se, c_sw),
                r(r_nw, r_ne, r_se, r_sw);

            Image piece = crumpled_img
            // Span returns rectangle spanning two quadrangles 
            Rectangle target_r = Span(r,r); target_r.center = target_r.center - rect_pos;
            // just wrapper for PerspectiveDistortion
            piece = QuadrangleDistortion(piece,c,target_r);
            piece.crop(rect2geo(target_r));
            mosaic.composite(piece,target_r.NW().x, target_r.NW().y, AtopCompositeOp);
            cerr << "." << flush;
        }
        cerr << endl;
    }
    return mosaic;
}

Probably I just need to figure out the proper way to make the cropping.

Antony, thanks for XMorph and libmorph. I had no idea something like this exists for Linux. Still I think it's too heavy solution for my particular problem.

[anthony]

-crop will leave the image located in its original position on the virtual canvas. That is with the original images virtual size and the approriate crop offset.

-distort will use those offsets! Clear them by using +repage after crop


See IM Examples, Crop
http://www.imagemagick.org/Usage/crop/

[akamaus]

-crop will leave the image located in its original position on the virtual canvas. That is with the original images virtual size and the approriate crop offset.

-distort will use those offsets! Clear them by using +repage after crop

suddenly I've understood everything I need )) I'm happy with performance now.

The working version follows:

Code: Select all

Image Deskewer::decrumple(const Image &crumpled_img, const Plate &crumpled, const Plate &rect) const {
    assert(rect.nx == crumpled.nx);
    assert(rect.ny == crumpled.ny);

    Point diag = rect.elems.at(rect.nx-1,rect.ny-1).pos - rect.elems.at(0,0).pos;

    Image mosaic(Geometry(diag.x, diag.y), "black");

    Point rect_pos = rect.elems.at(0,0).pos;

    for (int sy = 0; sy < rect.ny-1; sy++) {
        for (int sx = 0; sx < rect.nx-1; sx++) {
            Point c_nw = crumpled.elems.at(sx,sy).pos,
                c_ne = crumpled.elems.at(sx+1,sy).pos,
                c_se = crumpled.elems.at(sx+1,sy+1).pos,
                c_sw = crumpled.elems.at(sx,sy+1).pos;

            Point r_nw = rect.elems.at(sx,sy).pos,
                r_ne = rect.elems.at(sx+1,sy).pos,
                r_se = rect.elems.at(sx+1,sy+1).pos,
                r_sw = rect.elems.at(sx,sy+1).pos;

            Quadrangle c(c_nw, c_ne, c_se, c_sw),
                r(r_nw, r_ne, r_se, r_sw);

            Image piece = crumpled_img;

            Rectangle window_rect = Span(c, r);
            Point w_pos = window_rect.NW();

            Rectangle target_r = Span(r,r); target_r.center = target_r.center - rect_pos;
            piece.crop(rect2geo(window_rect));
            piece.page();

            piece = QuadrangleDistortion(piece,c-w_pos ,r-w_pos);

            w_pos = w_pos - rect_pos;
            mosaic.composite(piece,w_pos.x, w_pos.y, AtopCompositeOp);

            if (cfg.verbose > 2) {
                cerr << "." << flush;
            }
        }
        if (cfg.verbose > 2) {
            cerr << endl;
        }
    }

    return add_borders(mosaic);
}

Hope that would help someone in the future.
Thanks a lot for all the advises.

[anthony]

Please note that perspective distortion is not really suitable for this type of thing.
It keeps lines straight, but not distances.

What is needed is a Bilinear distortion, but so far only the forward mapped form implemented in the reversed sense, has been completed. Unlike perspective you can not simply swap coodinates to reverse the mapping!

the reason you want this is that distances are preserved along the edges. that is a point that is half way along a edge between mapping coordinates remains half way along that edge. With perspective that point shifts position!

Basically that means that the current (not-exampled) implementation can map non-rectangular quad to a rectangular quad will and get the correct result.
However the distortion needed to map a the rectanglar quad to a non-rectangular quad case (mathematically forward map the image using bi-linear) has not been
yet been built into IM. Fred Wienhaus however does have a slow FX test case.

In other words the distortion method needed for most grid to distorted-grid image morphing, is not available

I keep meaning to try and implement the bilinear 'forward map' (using the reversed form of the algorithm) but never seem to get time to do so.

That is especially the case right now where work and home commitments are conspiring against it.

[fmw42]

Any chance you can post a link to your input and output image? I think some of us would like to see what your script actually does.

[akamaus]

Any chance you can post a link to your input and output image? I think some of us would like to see what your script actually does.

In case someone still interested..

This is the input image:

This is the rectangular mesh we want to map input to.

And this is the resulting image:

[fmw42]

pretty neat!

[anthony]

A very neat example.

Note that at the time of the previous mail, ony one half of the bilienar distortion method was working. However as you are rectifying the quadragles, that was the method you wanted!

The Distortion function to rectify quadrangles (any quadrangle to rectangle) is called BilinearReverse. Look it up on the IM Usage Examples, in Distorting Images. Also now implemented after more than a year of set backs in BilinearFroward. (for distorting rectangles to quadrangles).

Next on my To Do for this is the conbining of both functions Quad -> Rect -> Quad. So as to allow the distortion of any quardangle to and quadrangle, while presenting distance ratios along the edges. Something that perspective will NOT do properly.