Rotation Averaging and Optimization on Manifolds

each year Microsoft Research hosts hundreds of influential speakers from around the world including leading scientists renowned experts in technology book authors and leading academics and makes videos of these lectures freely available good morning everyone it's my great pleasure to welcome back richard hartley who's visiting us for a few days he'll be here until next Wednesday richard is very well known in the computer vision field he was one of the pioneers in projective structure for motion and multi-view reconstruction and he and andrew zisserman wrote the very well-known book on that topic in the year 2000 richards also been a collaborator here with us he's come visit us several times he worked with us on some of the early work we did on 360 degree video walkthroughs and today he's gonna present us something he was just talking about at the cvpr Vision conference namely optimization techniques on manifolds Thanks so obviously we're a small group here so interrupt as much as you want to ask me questions on this as we go along so okay I'm talking about convex optimization on manifolds but also particularly something to do with structure from motion here and applied to structure from motion now convex optimization has been very popular fairly recently iron since really the The Book of Boyd and Vanderburgh came out and there's been increasing up increasing interest in in this subject reason is in fact that there are now efficient algorithms for doing convex optimization in lots of cases and there's a unique minimum and you know how to get to the minimum and all these sort of nice things any trouble is of course most problems particularly structure for motion problems we come across are not convex problems and so the question is to find out those ones that are and so you can take advantage of it now I'm going to talk in in general a little about convex optimization as applied to manifolds and what differences you have to do when you're working on manifolds and then I'm going to talk specifically about a structure and motion problem we're going to be talking about rotation averaging so we're doing work on the specific manifold of all 3-dimensional rotations which is known as so3 three dimensional manifold so just some introductory material about convex optimization then to be able to redefine convex sets convex function well convex functions need to have the idea of what a convex set is it's a fairly simple concept which you probably familiar with you have a set you take any two points in that set and you take the line that joins those then it lies in the set so this set is convex and this one does not because that line goes outside the set one of the nice properties intersection of convex sets is convex and then there's a convex function which really means that if you take if you have the graph of the function and you join two points on it then that line lies above the graph so in specifically there's the formula which expresses it but it's most easily thought of just in terms of that graphical concepts that goes down and you've got us a nice minimum you can find by in a sense going downhill so that's the convex optimization problem the generic problem is minimize some convex function over a convex set something here's a function and you find the minimum and the properties out in fact has a single minimum on a convex domain that's not quite true it can have a set of minimum or with the same value where it's sort of flat on the bottom but then it will be the minimum will be obtained at attained on a convex set itself so if it's as I said if it's flat on the bottom then there's several minima some convex functions is convex so if you if you're trying to optimize some function each of whose components which is the sum of several terms and each term is convex then the whole thing is convex and so you're in good shape linear functions are of course convex as well so you add linear functions to other convex functions what you have is a convex function now from elementary calculus we know we know these sort of things if you take the derivative of a function then you have a stationary point of the function with derivative zero and if the second derivative is less than zero it hits a maximum a minimum when it's greater than zero and if it's equal to zero then you might have a saddle or you might have something rather else but here's the case where we're interested in really where the second derivative is greater than or equal to zero second derivative positive then you got a convex function and the minimum so that's nice for functions in of a single variable and functions of several variables that goes like this that you have function from RN to R U it has a stationary point when there's Cobian is zero so potentially a minimum and then so there for instance derivative of zero and then you exterminates the maximum or a minimum or whatever it is in terms of the Hessian of the function okay so the Hessian is where you take all the second derivatives of the function with respect to X 1 X 2 or X I XJ so that's the Hessian okay now if you look at the Hessian you can tell in fact whether the functions convex concave whatever diagonalize it for instance by an orthogonal change of coordinates and the diagonals will with the eigenvalues so then if the eigenvalues are positive then it's convex ok so sorry the derivative is convex it is positive you have a convex function similarly in general if it's positive definite matrix positive eigenvalues it's convex and if it's negative its concave and if the mixed you have a saddle so it looks like this in the case where the function has all positive eigenvalues you have this nice sort of shape like this is all negative eigenvalues and his mixed positive and negative eigenvalues and you have saddles so now what about manifolds so for manifolds you've got to sort of define these same sort of ideas what's meant by a convex set on a manifold well first of all what's a manifold I hope you haven't got a slide for that you should think of a manifold as being in a sense a surface right so think of it as being a surface without any singularities embedded in some RN in some Euclidean space okay so now we'll see pictures of them so locally it's just sort of flat and linear and smooth and everything it's similar to some Euclidean space locally now so what are geodesics we use G determine the concept of geodesics instead of line segments when we're talking about manifolds so I'll tell so geodesic is in a bit so points in the set are joined by geodesics so generally therefore you talk about on manifolds a set is convex if points in that are joined by geodesics in those geodesics lie in the set so that gets a little bit more a little bit more technical than that as we'll see and functions the convex if they're convex functions on the geodesics as you'll see and so a function on the manifold is convex if the Hessian is positive definite and we'll say what it means by the Hessian of the function defined on a manifold in a bit and there's additional complexity because geodesics are not unique on this so it gets a little bit more complicated some things carry over from RN and some things don't so the first thing then is what is a geodesic so geodesic just big word for a fairly easy concept which you familiar with our guess so you think of in terms of curve what is it a curve on a manifold so a path on a manifold right is just a mapping from some interval of the real line into the manifold so just draw a path on on the sphere on for instance on the surface of the earth path one says yes an example of a curve and a geodesic is a particular curve which has these properties it's sort of locally distance minimizing locally distention right we'll see in a moment let me just fact go to the next pop up here so here's an example of a geodesic on a sphere right it happens to be a great circle of what the geodesics here there locally distance minimizing which means although this curve which goes around the backside of this here is not the shortest path from here to here nevertheless I can break this up into little bits right for instance think of the dots here this is definitely the shortest path from here to here and this is the shortest path from here to here so it's made up of shortest paths right in fact if you can divide up into intervals so therefore any two points and that intervals the shortest path okay so it's a locally distance minimizing curve you can also think of it in terms of other thing moving at constant velocity on the surface and then if the acceleration is always normal to the surface then that's the geodesics so for instance cost you you drive a car around the earth your velocity your acceleration is is radial so perpendicular to the surface or you can think of in terms of a taut piece of elastic band on the surface so if you take an elastic band here and let it pull it will settle on some curve and that will be a geodesic in this particular case here if you look at that that that curve if you that were made of rubber right it's still an equilibrium point for that curve it's not stable equilibrium I mean there's that this can be continually deformed into a shorter curve so but it is in stable equilibrium if you think of a force on a curve there so well not in this case it doesn't no it's sort of sitting on an unstable leaving if you move it slightly off it'll shrink one which goes as shorter than a complete half turn then it will certainly be in stable equilibrium and it goes from the pole to the polled it'll be in that sort of neither stable nor it'll be it'll be well will stable equilibrium okay so here are some examples geodesics can be quite calm complicated so here's our honor on a tourist these are all gdz curves on earth this is a so-called pretzel and curves you know they go round and round and round and round this one in fact happens to be closed which is unusual geodesics not generally closed in other words they don't come back to the same point in general honor on earth on a cone here's an interesting case where in fact here it's take two points there are at least three geodesics which join those two points right one two and round the other side in fact this this surface has interesting property that it's but it's flat in a sense that the so-called Gaussian curvature that services surfaces are zero which means that I can sort of cut the cone and wrap it out onto a flat surface right sphere you cannot do that you cannot cut it and flatten it likewise this you can't that means you can actually generate the geodesics on a cone by drawing a straight line with maybe in paint on the surface and rolling the cone and the paint will transfer to the cone in energy of these XML e with a cylinder so these examples all examples of geodesics this is a an important one to bear in mind the geodesics between two points are not unique right and there's the difference between what you have in our end where points between lines in our n are unique there's only one line but here there are several since well geodesics and sometimes they can even be a big length and on a sphere the geodesics are the great circles okay so intersections of a plane through the origin so the next concept which is important here this is a little bit of a tutorial on remaining in geometry here that I'm giving as the exponential map right now I was always confused when people talk about the exponential map thinking what does this actually got to do with Exponential's well in a way not so much all it is it's a fancy word for the following concept you you take a a manifold the dark gray thing and take a tangent plane I don't think these are surfaces take the tangent plane and you take a vector in the tangent plane and you wrap that vector you start out with a geodesic heading in that direction and go for the length of the vector in other words you sort of take that and wrap it around the manifold and that gives you a mapping from the tangent from the vector which lies in the tangent space to a point on the manifold so the exponential map is simply a mapping from the tangent space at a point to the manifold itself right and this thing called the logarithm map logarithmic map which does the opposite you take a point here and it goes back to the vector which you know would get you there so if you if you go back to the the cone for instance you can see that if I head out in this direction you know I think there's a little space around here where I little you know patch around here that I can go and map exponent by the exponential map down onto the sphere but the logarithm map is not unique just as the logarithm map in the complex plane is not in for complex numbers is not unique neither it is on a manifold there are several directions I can get to get from here to here I can go along here and get to there I go ahead like here you know straight across and so each of those vectors are the the logarithm of that with respect to the tangent space here so it's not unique okay finally gradient and Hessian remember I defined convex functions in terms of gradients and Hessians in terms of Hessians with the Hessian is positive definite if the gradient is zero you potentially have a maximum of function if the Hessian is positive definite then it is a maximum so let's let's just think how this works on manifolds suppose you have a manifold m and you've got a function from the manifold to the real numbers okay now and you supposin have the exponential map at a given point so at X this is the X this is the F the exponential maps at this point X and now if you take the function from the tangent space through the manifold and compose it with the function f that you're interested in then I have a function now from RN to R I'm going to I can find gradients and Hessian in the usual way you'll remember is defined in terms of functions from RN to R if I have F I can create such a function and then you have that the gradient defines a vector in the tangent space and the Hessian is in fact can be represented as usual by a symmetric matrix and if that Haitian is positive definite then the function is convex so a convex function of the manifold of function is convex at the point X if you only if the Hessian is positive definite index okay what it also means the other alternative definition for a convex function is just the same thing as as it is for well for same thing as it was for sets in RN if you have a function defined in a you know an area around here and you take a geodesic then that defines a function on that path along that geodesic and if that geodesic if that function defined can find that geodesic is convex then the function is convex so there are equivalent definitions as one can prove okay that's sort of general ideas about convex functions in in in our n good look now at rotation space because I'm particularly interested in applying this in fact to rotation spaces in fact I've said this is a sort of an area that I want to look at a bit this idea of functions in in convex convex functions on manifolds and the simplest sort of one that you at least non-trivial one that you might look at is rotation space and it's interesting interesting in in our area and I don't have much in results on anything other than rotation space some of the some of the results obviously do extend and others maybe don't so let's just look at rotation space as an example so I think we all understand rotations right you know rotations well there are things about rotations that perhaps we don't not everyone here is familiar with but let's go through some of these things one of the one of the most important representations of rotations is as quaternions okay we all know I suppose rotations can be represented by three by three matrices I'm thinking of three dimensional rotations right so there are presented by a three by three orthogonal matrix but another very important one is the quaternion representation quaternion is a four vector and rotation is represented by a unit quaternion and what it means is if you write the vector eschews cos theta on two and sine theta and two times V where V has a three vector in other words you take the last three and consider as a vector and that one q0 it's cos theta on two so that tells you the angle of rotation and the vector V tells you the axis if that's the axis and a rotation through the angle theta that is the rotation represented by that quaternion okay now one of the things here is that both important things but Q and minus Q represent the same rotation okay so that's because for instance a rotation about some angle about this axis is the same thing as a rotation through the negative angle about the oppositely directed axis so both Q and minus Q represent the same rotation these quaternions there's an interesting as a quote that I've found in a book which says that if you've spent all your life studying rotations and then you'd only then discovered quaternions you would think that your life had been wasted but maybe a lot of computer vision people wasted their life's thinking of rotations I don't know because they were it was really Burt old horn who really introduced quaternions into into our field field of computer vision probably quite a quite a while ago now maybe 20 years or more I can't remember the date of those papers but yes and now one of the interesting things about about about this representation is that if you have a quaternion and the rotation matrix that represents that which represents the same rotation there's thing called quaternion multiplication which i haven't defined but if you multiply two quaternions that gives you the same rotation as multiplying the matrices so this is an algebraic isomorphism you might call it but so in other ways you can you can use quaternions actually to multiply matrices and to work with matrices in fact quite efficiently it's more efficient in fact than multiplying matrices together in terms of operations but one of the other things about it is that it's not only algebraically like that isometrically quaternions are like rotations as well in that okay let's I'm getting a bit ahead here but how if you ask yourself how close are two rotations to each other I have two rotations how close is one to the other well what you'll normally do is take the r1 and r2 you take our 1 times r2 minus 1 that is a rotation from 1 think of them as coordinate frames a rotation thing the orientation of Gordon French so go one coordinate frame another one how do I get from one to the other will I rotate and by what angle do I do I rotate tells you about how far these are away from each other so that's the angle between two rotations and that is exactly the same thing as the distance between two quaternions if you think of the quaternions as a set as unit quaternion so they're points on a sphere in fact a three-dimensional sphere lying in r4 and if you take the the distance along that sphere from one vector to the other that is the the distance inquiry in the quaternion sphere and that happens to be exactly the same as the angle well it's a factor of two difference there as a matter of fact so you can think of all rotations which are close to it another one former a ball on the sphere or a a circle on the sphere there's actually just one little complexity there and that I said that both one rotation and it's negative form the same represent the same rotation so you really take the minimum distance from either their there or there to the opposite is what the the quaternion distance might be okay so quaternions very useful representation of rotations another one is angle axis where you are in a sense almost forget about the the first component of the quaternion which doesn't actually give you so much you've also you've got all the information in the last three in the last two because you've got the the vector V which was unit vector and you've got the sine theta but what the angle axis wrote method is is you sort of say a vector you take the vector V and multiply it by take the unit vector and multiply it by the angle of the rotation and you get the angle axis representation and that is sort of like taking the sphere the quaternions sphere and flattening it out think of a think of this things being a piece of rubber you cut it in half at the equator because you don't need both the bottom the top halves because that's then flatten it out and you get the angle axis rotation this is a map of the earth with what's known as the azimuth or equidistant projection which gives you the same thing so in other words you can think of this if you want a representation is actually my favorite representation of rotations for any computational purposes is through the angle axis method where you represent rotation by a vector which is the axis multiplied by the angle do you rotate through and so all rotations may be represented by a ball of radius pi because the maximum rotation you need is a rotation through pi there been a few papers recently on what's known as they know they haven't its equivalent but I'll just introduce this one just for a moment the gnomonic projection so if you know the word Noman it's AG Noman or Nouman I'm not quite sure how to pronounce it no Mon perhaps no Mon is anyone know not quite it's this very obscure word it's a little thing in the middle of a sundial which throws a shadow to tell you what time it is that's the glow month and I'm not sure what it has to do with this exactly because but that's what the word comes from and ok so if you think of this as being the quaternion sphere so it's a three-dimensional sphere and you take a plane tangent to the sphere so this is actually not a two-dimensional plane for a three dimensional plane in r4 and you project from the center of the sphere then that gives you a mapping from the quaternions sphere to the plane okay and it has the nice thing that opposite points on the quaternions sphere map to the same point which is good because opposite points the same thing and has the or the extra property that great circles here which are as I said geodesics map to straight lines in the plane ok so we can buy via the gnomonic projection we can take rotations to an r3 playing in our for to in other words three dimensional plane in which geodesics on this on in rotation space represent are represented by straight lines in space and furthermore in any sort of reasonable sense what you might call convex sets in rotation space are in fact convex sets in in this tend in RN and we are that are nr3 in this particular case it is represented to rep it is related to what's known as the Cayley transform which has come up in a few papers recently people have discovered the Cayley transform which is a way of representing rotations and what that is if you take a rotation are the Cayley transform is our plus I inverse times R minus I that gives you KT transform takes a rotation matrix and ends up with a skew symmetric matrix this is a skew symmetric matrix and alternatively if this was skew symmetric you end up with the rotation so it's a it's a by ejective mapping between rotations and skew symmetric matrices it's a zone inverse gives a one-to-one map between rotations and skew symmetric matrices and people have used this for computation now it is in fact as it turns out related to the gnomonic projection in that if you take okay now skew symmetric matrix of size three by three only has three elements which are nonzero I mean this was skew symmetric the diagonals zero and you've got one two three elements and these the same except with the opposite side so skew symmetric matrix has got three parameters now if you go from a matrix to the quaternion sphere and then via the goon harmonic mapping that's the same thing as going from our via the Cayley transform so the pneumonic mapping and the Cayley transform are effectively the same thing we're not going to talk about the K transform to note the gun or Manik mapping however is very useful because it allows you to understand well everything is your mapping into RN and you're preserving geodesics become straight lines and convex sets whatever so okay okay what a convex sets in rotation space so there are two ideas here weakly in strongly convex sets which defined like this sit as weekly convex of two points in a set are connected by a single geodesic lying in the set so two points are joined by a geodesic but not two of them because otherwise you get a confused and if that GEDs happens to be the shortest geodesic then you call the set convex now the sort of the things happen here if you have the catonian sphere here's a set which you'd think of should be convex by all sorts of any intuitive idea and there are two points in fact you can join them by a geodesic a great circle lying in the set however since this is a quaternion sphere yes you can join them but it's the same as what lies underneath as well and that point you know that a point here is the same as a point here remember in quaternion space that point is really the same as this in fact the shortest line from that rotation to this is that that line there which does not lie in the set so the shortest geodesic does not lie in the set so I call that set weakly convex there's the shortest geodesic weakly convex but not strongly convex it's only strongly convex if the shortest geodesic lies it now one of the of the nasty things about weakly convex sets that you can take two of them now if you go by the gunner monic projection a convex set can be split into two bits and you can get a situation where you can take two convex sets and the intersection can be two pieces right unlike in our n intersection of two convex sets is convex if you take weakly convex is in rotation space intersection of them can be there can be two parts and so here's us a rather full slide says much the same thing so it's weakly convex of two points instead of connected by a single geodesic convex if that's the shortest geodesic various properties convex sets a similar to convex it Cenarion you can map via the gnomonic projection and there you've got the same thing convicts it cannot be too large there's a limit on the size they can be in fact they must be contained in a ball of radius two pi on three it turns out and weakly convex are more difficult yes no a weekly convicts it must be connected because two points have to be joined by a geodesic but that geodesic may not be the shortest one right and if you take two of them here's the example right this is this is a weekly convex set in the two points are joined by a single geodesic inside the set but the shortest geodesic lives outside the set that is not the shortest geodesic from there to there this is well you can have you think of it in different ways you think it was the hemisphere or you think of it as the full sphere but opposite points are actually the same yes in fact so what you have is a sphere with opposite points identified it's actually projective space in fact so the rotation space is in fact topologically are three projective space p3 which we're familiar with through a structure and motions or in a different in a different way no you don't they're the same point it's really but in a sense it's a bit like thinking of rational numbers one on two is the same as 3 on 1 on 2 is the same as 2 on 4 is the same as 3 on 6 they're just different ways of representing the same thing and these are just two points which are the same right they're the same um okay better just get along with a little bit here distances between rotations okay we need to talk about distances between rotations many ways many people have talked about distance the rotations with different meanings of the usual meaning that I like is angular metric which they've got two rotations how far two frames how far do you have to rotate one to get to the other that's the angle metric and as I said it's very much the same as the distance on the quaternion sphere but there's also the chordal metric which is just take two rotations as rotate as matrices subtract them and take the Frobenius norm sum of squares of distances that's also a norm for distance nation for matrices and it's in a sense it's the Euclidean distance in the natural embedding of rotations in our and I yes yes so the rotation to listen by pi radians so no two rotations could be further than pi apartment and then there's a quaternion metric which is just the distance between these vectors as vectors not along the surface of the sphere but directly cut across the distance between these two things 15 - 4 vectors and so it's actually the minimum of our - s now + s because you have taken account of the fact that - quaternions represent the same rotation there's another one which is equivalent the first one which is the ratio of the two batarians right when you divide one returning by the other that gives you basically the angle that gives you a quaternion yes whose magnitude is the whose magnitude is the SS inverse is basically returning our / return s right there but R times s inverse is a union a unit quaternion though so it's magnitude is little one so there's not really correct okay it's not the magnitude is the part that is the coast of the sine theta partly returning well yes all that out so it's the angle representatives the second is the angle there's another way of writing down the angle metric which and false return deeds as opposed to a rotation basis are you saying that yes you because he's a chopping away yeah you can compute it from the yes you can compute as you computer with a specific formula are matrices in quite more stable and then the other one the quaternion metric you can get by taking the inner product of the two and that gives you the code well you can just do it like that that's the cosine of the angle in any case and so your tour is the heart and they sort of looked like this if the angle is Theta then the the his theta squared but the chordal metric looks like this and it's square looks like this and the quaternion metric looks like this and it's square looks like this interesting about the chordal metric neither it nor its square are convex on for all rotate on the whole set of rotations quaternion metrics this is not convex its square is and for the angle metric both the angle metric and its square are convex so this is a good one to work with though yeah so I said the angle metric is convex everywhere except on the plane at distance PI from this know what I'm okay I'm gonna get now to what I'm want to do is actually average rotations so if I take the sum of distances per thing I've got a bunch of rotations si and I take this distance metric that distance can be any of the ones that I want I want to find the are that minimizes this it's closest to all the SI in some sense whether some distance metric and piers some power so that would be corresponding to a P norm and usually P is one or two but I'm interested in its convex on open balls of Si around si with PI and on the intersection of these open balls the functions are going to be convex for my angle metric so these distance functions and nice and convex everywhere except on a set of planes in if you think of us or the set of rotations which are a distance PI in other words if you think of these in terms of on the on the quaternion sphere let's draw the catonian sphere look at all this will do if I take a point here and take the sphere which is the Hemisphere sorry the equator in a sense which is a distance PI away from this it's not there's a discontinuity there of derivative but if you got a bunch of rotations and you draw those those I call them planes this oblique then the function is convex except on those and on any convex set other which doesn't contain those it's convex so we're in in good shape so let's have a look at rotation averaging problems there are a couple of problems that want to look at there's this one where I want single rotation averaging given a set of rotations find the rotation s that minimizes this function of words its minimizes the distances to my RI okay and that's the cost of s and I want to minimize the cost of s usually as I said P is from 0 1 now there's multiple rotation averaging yes P is 0 or 1 so P is 1 or 2 it's equipment if you're doing LP norm or l1 norm real 2 norm right yes it's just a power just the power that's what's squared or it's just the distance itself so this is sum squares of distances just sum of distances right our multiple rotation averaging so in multiple rotation averaging what you have is you've got a bunch of relative rotations rij and we'll see this and you want to find the RI and the rj p maybe L 1 or 2 so let's have a look at this in the single rotation averaging problem you got this is the standard structure and motion thing you go moving camera which moves from here to here from five corresponding points in two images you can compute that motion right the first so-called five-point algorithm for computing relative orientation of two cameras very fast about 35 microseconds in in my implementation David claims about 20 microseconds which I believe he can probably do it in that time so very quick you can do this 30,000 times a second so you can take samples of five things and one way of estimating the rotation would be to take sets of five points compute the rotations and average them right rather than saying using a ransac approach just try averaging the rotations take many different sets of five points and average them individual estimates can be noisy the rotation you get from five points five points you use a bad can be quite not very good so you need a robust way of averaging those so in the single rotation averaging problem you have seen several estimates of rotation what are the best way of reconciling them from five points and two views as head said exactly the same thing again on that slide really now here's the multiple rotation averaging problem I move the camera through some paths we have several cameras and I can compute the relative you are one two which is the rotation from there to there I can compute that rotation and I can compute that rotation but they must be related you need for consistency that are one three has to be are two three times our one two rotations form a group and so what you want to do is actually find r1 r2 and r3 that come as close as possible to satisfying this relationship R IJ equals IJ times our I 4 minus 1 so you try and find the absolute rotations giving the relative ones so let's have a look at where this may be applied it's what I applied it to the nostrils are set right 569 images 280 thousand points it happen to be 42,000 pairs of overlapping images so more which have more than 30 points in common 42,000 so given that you can compute the relative orientation in 35 micro seconds you can you can easily handle 42,000 of these things so what you want to do is the task is find the orientations of all the cameras and as I said rotation averaging turns out to be a nice convex optimization problem on the rotation space so the strategy is for each pair of cameras find the relative orientation rij and to do that you take sets of 5 points and use the compute the relative sorry for each pair of cameras find the relative orientation rij right and that's used by it done by averaging five point take sets of five points and I average them average the individual rotations to get rij and then average there's multiple rotate average of disinvestments gets best average rotation yes that's sort of said then in this and then well yes you can I'm suggesting this is a possible way of doing it alternatively rather than do ransack but really since in a sense you need the rotation averaging the second step which is the multiple rotation so I'm just as an exercise see how well it applies to the single rotation averaging as an alternative to ransack you could use ransack in the first step alternately but in the second step as you'll see you need rotation averaging so since the papers about rotation averaging I'm using the rotation averaging instead of round sake then I initialize the absolute orientation orientation of all the cameras by propagating over a tree as we'll see how and then I do average rotation individually assuming the neighbors are known so that's that does a bit quick but let's have a look at it so each of these is supposed to represent a particular camera and they're joined by an arrow if you can compute the rotation between them right and so you have all you have this connected graph and you've got the world of orientations between two points so then I select any given point where I actually select the one with the greatest fan out and assume that the orientation that is the identity I mean you can assume that is your real reference frame and then just by propagating out from there since I know the relative orientation I can compute if I know that and I know the real property I can know that etc by going over a tree I can get an initial orientation for every rotation in the tree not necessarily very exact but it's what it is and the second step then it's a sort of a message passing algorithm as you know Noah was talking about it see the PR where in fact you now say I suppose first thing I know all the the other rotations and what I'm going to do is I'm going to re estimate this one the blue one now if all the rotations these ones are known and you know the relative orientations that gives you an estimate for different estimates in this case of that rotation so you average them right and and then do that over and over through the whole thing and get the result so the question is how do you advocate a shion's it is a convex problem where we came started out if P equals two it's at least squares averaging problem and it's usually simpler but it's not robust to outliers I'm looking here at l1 averaging because it is robust I've unfortunately gone a little bit slow at the beginning so I know to have to speed up a bit here there are various methods which have been proposed from l2 rotation averaging there are exact solutions for that in fact which minimize not the angle metric which minimize the chordal metric as it turns out you can minimize the chordal metric easily you can minimize the quaternion metric with a little bit more problem the only difficulty with quaternion metric is the ambiguity between the two different representations but for the chordal metric there are two different algorithms I will do that yes well if they're close together too close together yes there's no problem there's no problem if they're not close together it's Sorrenti hard type webbing whereas the chordal metric it's closed form difference it's very little difference but l1 averaging is what I'm interested in the motivation to doing l1 into our buses well this the difference between surgeons to get back I'm not going to show why the chordal metrics but the real difference is the chordal metric is very closely related to the angle metric it's just the site sign sign of theater on four and four theta small its sign and in theater itself the same thing right so but l 1 rotation air L 1 averaging is an interesting problem with long history even in RN ok in RN so you know you say now 1 the ill through averages several points the mean you just take a bunch of points real numbers take their mean that's the l to average the L 1 average turns out to be the median and we know the median is more robust to outliers you have thing which is way off doesn't make a lot of difference how far it is away it's just but in in so and you can desert in fact a linear time algorithm finding the median right but in our to the problems the classical problem goes back Center that's known as a fair MA sometimes the fair amount or a chilly problem 16:36 also sometimes the Weber problem fear my Weber problems are certain many names but and there's a bunch of recent work eventually so fear ma toward Shelly solved three points in the plane right very simple Weber gave an algorithm in 1906 which had to do it sort of worked like this you've got a bunch of points in the plane and you want to find the point which minimizes the distance sum of distances to all these points and why he was interested in is you may have ion or call water or something where do you put your factory to minimize the distances so this is a problem that's important in that sort of context so what his solution was was supposing you take a table and you mark all the points on it now you take an electric drill maybe in 1962 in ordinary and he drilled a hole through the table at each point and you hang a weight on a string and you connect all those strings together at one point and where it comes to an equilibrium as the point you're looking for so he had this solution for this so not practical in I suppose for us these days but nevertheless a solution vise felt in 1933 came up with a problem this is the paper written by vise filled Hungarian mathematician he wrote it in French and published it in a Japanese mathematical journal and it gives a nice closed form iterative not so an iterative approach for doing this which I'll discuss more recent work works is doing some stuff on manifolds including Romanian manifolds in 2009/2010 which in fact we discovered after we done this work and saw that had been we've been in a sense preempted in this but nevertheless it's where it is so for three points the ferme our point is the point in fact minimizes isn't sirs the point where those who reach 120 degrees means that if you have unit vectors going from there in each of those directions they're in equilibrium and that's really why it it works like that now it turns out in our in this is a gradient descent problem the cost function is distance from X I to Y X is given you have to find y find the distances which is that it's convex has a single minimum unless all the Exide collinear the gradient happens to be the sum of the unit vectors take all the vectors and take divide by their length and so you can think of a gradient descent algorithm where you take YT is your current estimate you take that current estimate plus some step size times the gradient okay here's the gradient direction and that gives you the next one so if you if you're working in l2 distance your gradient is the sum of the vectors in l1 distance of some of the unit vectors in all directions the only question here is how to find gamma T what is the step size right and normally gradient descent R is in a bit of a pain in neck because if you're going doing gradient you have to search along the gradient direction for the right step and that means evaluating the function many times and yeah but so what vice felt did he came up with a closed-form formula for the step size very simple you put the step size gamma T as one on the lengths some of one on the links and one on that right and that is your step size and a turn so the update step now has this very simple form will you take the vectors from X from X I to the current estimate divided by the length and then divide by this is the step size and that gives you the next so very simple very fast now how do you and provably convergent that's the point proved convergence in 1933 now if you do it on a manifold all you have to do is start at some point and you've got a whole bunch of points on the manifold you map them to the tangent space do a step of the vise feel though because in tangent space takes you to a new point map back to the map where you are back to the manifold and then take the new tangent space at that point so we're we're in a sensory parameter izing at each step just iteratively all you need to do this is have two maps the map which is logger than map which goes from the manifold to the tangent space and the exponential map which takes you back to the manifold and with those two things you can apply the vise field algorithm and it's in recent work can be proved to be to be convergent on an arbitrary manifold as long as the manifold a positive curvature so that's basically saying that so all I'll just get finally to the results so the steps you find initial estimate at any time apply logarithmic map to get to map to the tangent space apply advice fill step in the tangent space and then go back to the new point in the manifold and form the tangent space there and keep going okay results on rotation averaging this is result of l2 rotation everything this is l1 converges a lot faster it converges to a much better solution with respect to ground truth right yes that was my best best grab truth that I had so let's have a look how this works timing and accuracy on the multiple root affectation averaging problems with knotted arm set so here is the the method which I use for computing the individual rij the five-point algorithm and the 20 means that I've done at 20 20 sets of 5 points and 10 means that in the multiple rotation averaging problem I am a multiple rotation entering problem I'm going through and reading each rotation ten times ok he bundled means I'm actually using complete bundle the best algorithm I can think of really for computing the individual are IJ's yes so it's getting the robustness of the robustus events yes everything's l1 if you do a bundle so you get these are IJ's my bundling rotations it takes a lot lot longer there's a Samson distance which takes significantly longer as well and the results and so and this tight takes 36 seconds for the final rotation by a road rotation averaging this is the time it takes to compute each of the RI J's this is the time it takes to compute the absolute rotations by the multiple rotation every 36 seconds this is this is doing 42,000 4268 seconds to 42,000 RI J's okay 36 seconds to then do the device field averaging going keep going around ten times okay Isis yes so that's basically that bro is the corresponding gray color previous brokerages attack applied to the enemy that's fine I mean you broke the parameters down in the left column you see I'm sweaty grounds for each RI J and then rounds pretty global for the multiple yeah then you produce the sum number there and then break down okay I have instantly slightly more complete graph in the paper with which we've got slightly different parameters they are insuring the difference LTI being takes 10 seconds into 36 so the l1 is almost as fast as the l2 averaging here right well almost yes and the accuracy I'm getting more point nine three degrees so I'm getting an error of more point 93 degrees with respect to ground truth from these which i think is pretty accurate l2 clearly doesn't do as well so it's in some sense even maybe surprised and it does as well as it does given that sometimes your RI J's but you've got two steps of robustness here first you all you've got the averaging to get URI J's accurate and then you got the averaging of the of in the graph where you've got many many many estimates average fan-out is 80 in this graph so you're averaging 80 things and the 20 or 30 of those are bad then it doesn't really matter and because you're doing this till one happening so you can get quite accurate okay no less than one degree okay this will just shows the graph of l1 against l2 l1 again still - yes every average fan out in the graph each thing is connected on the average to 80 above their cameras correctly degree of that note yes yes it's quite highly connected okay I'm not going to go into this thing in a stop at this point but I have started work on working this out on the essential manifold and the only problem here is that you have to compute the what the geodesics are on the essential manifold which is quite a significantly different problem they have a quite a complex form like this is the product of three rotations in fact and you to get that you have to solve this set of five simultaneous differential equations to work out it's probably a better way in fact my coworker says he's got a better way but I just took yes you start you start with this and you say this is hopeless and then you start noticing things about it and then you eventually get it oh no no because having solved them you you get a close form of what the geodesic is this is the geodesic lens for you have necessary very simple and safe - the solution then this is the evolutions of that differential it's very simple actually and that's basically it just for the rest of the audience that may not work inspector commercials much what does it mean to be doing essential matrix averaging power use okay so that means that I'm taking once again five point algorithm and I'm getting not only rotation on getting rotation and translation right so I want to estimate I've got several estimates of rotation and translation I want to get the best estimate of rotation translation in this work that I've described so far I'm throwing away the translation not worrying about the translation to all views arriving busted by pairwise estimates you have started or maybe it's not possible through this multiple essential papers the only problem there is that you don't know the scale of the rotation yes yes if you have the skills yeah for actually working the essential matrix manifold because you don't know the scale and also because in that particular case you have these nice things of should buy it by invariant metrics se3 being a non compact manifold because of the e part there there's no left invariant you can't it's not invariant with respect to change of basis point in the sense and so but yeah sure you can if you want to estimate it separate the translations from the rotations and an average in that way yes you can do it you could do it that way yes you could get the scale insurance thank well I mean an earlier work with Christy sim for instance we we basically did that except we were using s OCP to find the final version of of this whole thing and that well we're using SACP to complete the wrote the translation haven't got the rotations that's a very slow way of doing it closed form in a sense but I mean you know you know there's a unique solution it's minimizing L infinity norm but it can be done so but there are lots of ways of getting translation once you've got rotation right Carsten Roth are yeah we did smoke earlier work and various things linear ways of doing it yep so okay okay thank you very much

Channel: Microsoft Research

Views: 3,314

Rating: 4.9058824 out of 5

Keywords: microsoft research

Id: JBoo0qdK8g0

Length: 60min 14sec (3614 seconds)

Published: Tue Aug 16 2016