Is there an algorithm for solving such projection reconstruction geometric problem?

Question

We have a grid with red squares on it. Meaning we have an array of 3 squares (with angles == 90 deg) which as we know have same size, lying on the same plane and with same rotation relative to the plane they are lying on, and are not situated on same line on plane.

We have a projection of the space which contains the plane with squares.

We want to turn our plane projection with squares so that we would see it like it's facing us, in general we need a formula for turning each point of that original plane projection so that it would be facing us like on the image below.

What formulas can be used for solving such problem, how to solve it, has any one faced something like this before?

Astigmatic

Do you want the transformation in screen space (pixels, 2d), or in world pace (3D)? – Mb

What data structures do you have as input? Points? Pixels? Straight lines? – Catwalk

Straight lines and objects (but I generate tham from pixels=)) – Astigmatic

Answer 1

This is a special case of finding mappings between quadrilaterals that preserve straight lines. These are generally called homographic transforms. Here, one of the quads is a square, so this is a popular special case. You can google these terms ("quad to quad", etc) to find explanations and code, but here are some for you.

Perspective Transform Estimation

a gaming forum discussion

extracting a quadrilateral image to a rectangle

Projective Warping & Mapping

ProjectiveMappings for ImageWarping by Paul Heckbert.

The math isn't particularly pleasant, but it isn't that hard either. You can also find some code from one of the above links.

Peaceful

OK, +1 for being right, but the comment about the math being unpleasant is waaaayyyyy tooooooooo mild. It's not hard per set, but moving between the analytic side (the pure math), the computers discrete representation, and then the horribly deresolved representation of the rendered image is going to be very very very ugly. Also, the math gets extremely squiffy when the camera is set 'interestingly', i.e. fisheye or extreme telephoto - bottom line is that the image characteristics need to be very carefully constrained for this to work. <sigh> – Sauterne

@Mark: agreed - OP hasn't been terribly clear so far about constraints and objectives. And arguably the problem is, given a perspective view of 3 red squares sans grid, to bring the 3 red squares into a 2D view. Maybe this is less an image processing problem, and more a registration problem. So we'll wait for OP to clarify. In the meantime, this was my best stab at an answer. – Peaceful

The resuting formulas are too computing intensive for transforming POINTS as the OP requested ... but in the problem as stated by the OP I think that straight lines transformation is the way to go. I did the math for a projective transformation with two escape points (using a CAS) but it's too long and boring to post as an answer here. – Catwalk

@Kabumbus You've accepted the answer. Why are you still asking for ideas to solve the problem? – Catwalk

Hey, I got the same answer, now I don't feel as special :) #4217870 – Burglarize