In this lecture we're going to see how we can compute the camera pose when we have 3D information in both sides. Both in the world coordinate system and in the camera coordinate system. This is also called the Procrustes Problem in mathematics. Why is it called a Procrustes Problem? Let's give some mythology background. Procrustes was a very mean person in ancient Greece, and he wanted really to fit people, unlike the person in the yellow square inside this specific bed. And in order to fit these people, he would actually squeeze them or even cut their legs. So this, getting two shapes, like a person, a full body, and a bed, and trying with scaling, rotation, translation, to fit to each other, is called in mathematics a Procrustes Problem. How can this be written? Let's say we have two yellow rectangles and one is described with points A and the other is described with points B. Then, we have rigid transformation the way we have seen it, rotation, translation, and then we have a scale. So we have one unknown for the scale, three unknowns for the rotation and three unknowns for the translation. This is called the Procrustes Problem. We will dear here with a simpler version where we just have the rotation, translation is unknown. One example is grasping an object if we have the object model is a 3D model. And then we have measurements taken with a depth camera, where we have a full 3D information. In this case, we have the full left-hand side like depth times the eye camera, equals to rotation times the current model of the object plus translation. Now we have seen in a P and P problem that we might have only the PI come, and in this case, we will have recovered the depths, and this reduces to the same problem as if we have a connect, like an RGB-D camera. So these are several objects from which we have the cut model and this is an example where we can estimate the position of the camera by seeing known objects. This is another example. We don't have a cut model of an object and the camera, we just have several depth views of a lion which is in front of the Museum of the University of Pennsylvania. And each color point cloud here represents a different depth measurement from the camera, and it was actually a depth camera. And by solving this Procrustes Problem, we can register them all together into the same coordinate frame. And have full 3D model which you can use for 3D printing or for any other purposes. Let's see really how many points we need in order to solve this transformation. Let's us start with four points, like four points in one camera view, four points in the other camera view, or four points in the objects, let's call it B, and four points in the camera, which we call them A. And we're going to apply some vector geometry here. Let's look what is the minimal number of points. We take the first point, and we subtract A2- A1 and A3- A1. Then B2- B1, and B3- B1. And this is just a triangle, three points, and we can get the perpendicular to this point, so A21, A31. And this pretty much gives us something like a coordinate system, where we have here B12, we have here B13. They're not orthogonal, they might be at an angle but we have a perpendicular. B21 across B31 and this gives us a fuller description of the coordinate system because even if the two axis, first axis are not a orthogonal, we can build a third action. Which orthogonal the way it is depicted with a dashed line in the picture. So this is indeed what we're going to do. We have the A21, which is like one vector. We have the last vector, which is A21, A31. And then with this complicated cross product, we're going to have really a full 300 coordinate system, A21 cross A31 cross A21. And the same, we can do it in the coordinate system B. These are two orthogonal basis, you see one for the B, and one for the A. And we can compute the rotation between these two orthogonal basis, and these rotation will be really unique. So three points are sufficient to compute the rotation between two coordinate systems. What can we say about more than three points? In this case, we have this minimization problem where we have A- RB- T and this has to be minimized. And, we do it over all end points, so this is sum of all these distances. What do we do usually in this problem is we take the derivative. Let's take the derivative with respect to T, and it would take the derivative respect to T, we're going to see actually that the translation is nothing else than the centroid of the A points and the centroid of the B points rotated. We can take this A bar and B bar, which are the centroids, like the center of masses and we can subtract them from A1 to AN and B1 to BN, and we arrive at the pure rotational problem, A- RB. How can we find the best rotation matrix that if you rotate all the B points, the way they have been normalized by subtracting the centroid, it will yield all the A points. Let's do some algebraic tricks here. We have this A- RB square. This is what is called a Frobenius Norm. It's nothing else than really A- RB transposed A- RB. And if you remember that the trace of the matrix is the sum of the diagonal elements, this is yielding the trace of A transposed A, which is constant. The trace of B transposed B, also constant does not have an R and two terms with an R. And these terms with an R, you can do a rearrangement of terms. And then you get this trace of RBA transposed. Remember, R is a rotation matrix, three by three, and B is three by N, and A transpose is N by three. So you have this problem, which is to maximize the trace, like the sum of diagonal elements of RBA transposed. Now there is a theorem which then you can see a very beautiful proof in the book by Golub and Van Loan called Matrix Computations. That if you take the singular value composition of BA transposed, and we replace it into this RBA transposed, we get a trace of Z, which is this matrix V transposed RU times S, which is just a diagonal matrix with elements sigma one, sigma two, sigma three. Now remember all the elements of the Z are less equal one. So if you take the diagonal [INAUDIBLE] of the Z because these are orthogonal, Z11, Z22, Z33 all of them are less than one. So at the end you'd get these trace to the less equal the sum of the singular values of this matrix BA transposed. So the upper bound is really obtained by just having the S equals to the identity. So if the S is equal to the identity, then you can set the R = UV transposed and this is our solution. And, again, a trick to guarantee that the determinant equals 1, we have seen it before, U and V might be orthogonal, UV transpose is orthogonal, but the determinant is not necessarily 1. To enforce the determinant to be equal to 1, we just add this very simple diagonal matrix 1, 1, and determinant UV transposed and this guarantees that the product of these three matrices has determinant 1. Let us see an example here of what we have built with this transformation. We have taken depth images of this statue of Benjamin Franklin on Penn campus. And we have taken many, many images with a camera called the Kinect camera, the RGB-D. We have done this during the night because this camera can record only during the night. And we have build this beautiful, 3D model of the Benjamin Franklin on the bench just by applying this Procrustes Problem.