Repository navigation
Map Registration Transformation
The goal is to define a bijective transform between two maps. That is, all (real) points should correspond to exactly one other (real) point. However, the pixels in the maps may not be a bijection.
For the purposes of this walk-through, we will go from a semantic map to a slam map. The transformation can, of course, be reversed by doing the same steps on the other map.
The transformation is represented by a set of affine transformations over a triangulated map. Each local affine is continuous, and the borders between triangles share a transformation. Thus, the entire transformation is continuous, yet still piecewise.
As an example, we will walk through the transformation of a map that has been inverted and partially skewed:
The user will select at least 3 points in both maps. Each pair should represent one physical location, such as the corner of a desk. The transformation will be bounded by the convex hull of these points, so it is advised to put a few border points around the map being registered. More points will result in a larger set of transformations and more accuracy over curves. Adding more points does not necessarily make a better transform over straight lines or undistributed regions.
The above image shows both maps with key points labeled. To see why adding more points will not improve the transformation, consider the line defined by point AB. That line corresponds to the line defined by the points ab. This line is straight in both maps (and in the "real world"). They are proportional to each other (and the "real world"). Adding another point will not improve their correspondence with the real world since it is already good. However, we do need the points E and F (and e and f) because they define the bend in the line between AC.
Many SLAM maps generated by robots will be mostly correct. They will have some (or all) straight walls. Most SLAM maps of hallways will be bent or have a curve. This is when adding lots of points is useful.
The semantic map is split into regions using Delaunay triangulation, though the method of triangulation does not matter too much.
The Left image shows the Delaunay Triangulation of the map using the points defined above. The right image draws the triangles on the skewed image using the same corners.
Say there is a point Q in triangle CDF. We want to find the corresponding point q in skewed map. Because Q is in CDF, we say that q is in cdf. Triangle cdf is a transformation of CDF, so we can apply that transformation to point Q. An easy way to apply this to a single point is to use Barycentric coordinates. We find Qs local position in CDF as x_1 * C + x_2 * D + x_3 * F, where C, D, and F refer to their (x, y) position in the global frame. The coefficients x_1, x_2, and x_3 can be found using the known global position of point Q.
Now, using the same coefficients, we can find the global position of point q as x_1 * c + x_2 * d + x_3 * f.
When the point to be transformed is on the edge of a triangle, it is in two triangles at once. It does not matter which triangle is used to compute the coordinates. In the above example, point Q is along the line CF and in triangles CEF and CDF. In both triangles, one of the coefficients is zero, so the transformation is a simple linear interpolation along the line CF.