MeshAlign Graphics User Interface

MeshAlign allows to the user to align all the acquired range maps, which by definition represent the distance of the surface sampled points from the sensor location. Many different locations of the scanner are needed to get a complete coverage of the object surface. This means that all these range maps have a different coordinate system and we have to move them in a common reference system. This process, called alignment, is usually solved in a partially manual and partially automatic manner. Automatic approaches have been proposed but they are not sufficiently robust to work in any condition.

Our tool follows the standard semi-automatic range maps alignment approach:

• Initial Pairwise Placement: the first registration step is to locate all the range maps in a single common coordinate system and to provide a first rough registration. This process is done on range pairs: each pair of adjacent and overlapping scans is aligned (one towards another).

• Fine Pairwise Registration: after the first step, the scans are finely aligned, usually using an iterative process (ICP) which minimizes the alignment error between each pair of range maps.

• Global Registration: the pairwise registration produces good results but, since the error minimization takes place sequentially on mesh pairs, the error tends to accumulate and it may result in significant artifacts after a number of pairwise steps. A solution is to perform a global minimization process which distributes the residual error among all pairs in order to spread the error evenly among all range map pairs

The alignment task is the most time consuming phase of the entire 3D scanning pipeline, due to the substantial user contribution required by current systems. The initial placement is heavily user-assisted in most of the commercial and academic systems (and it requires the interactive selection and manipulation of the range maps). Moreover, this actions has to be repeated for all the possible overlapping range map pairs. This pairwise process can be considered as a graph problem where: given the nodes (i.e. the range maps), we have to select a subset of arcs such that every node is linked to some other nodes if they have to be aligned together. If the set of range maps is composed by hundreds of elements (the scanning of a statue 2 meters tall generally requires from 200 up to 500 range maps, depending on the shape complexity of the statue), then the user has a very complex task to perform: for each range map, find which are the partially-overlapping ones; given this set of overlapping range maps, determine which one to consider in pair-wise alignment (either all of them or a subset); process all those pair-wise initial alignments.

The main objectives for the design of a new and radically changed version of our alignment tool are:

• a significant architectural evolution was needed to support the management of really large set of range maps (from 100 up to 1000);

• the standard approach (user-assisted selection and initialization of all the overlapping pairs and the creation of the correspondent alignment arc) becomes impractical on large setof range maps; the only practical solution is to provide instruments for the automatic setup of most of the required alignment arcs. Moreover, the efficiency of the rendering phase and of the alignment kernel has to be improved;

• a more easy organization of the data has to be provided (possibly, following a hierarchical approach: it is impossible to manage a large set of elements as a simple list of items);

• finally, we need easy to use tools to monitor visually the intermediate status of the alignment process.

MeshAlign v.2 still follows the approach proposed by K. Pulli [Pul99], which is based on a variation of the Iterated Closest Point algorithm  [BesMcK92,CheMed92}. One of the main improvements of our new system is the hierarchical management of the project. In a classical alignment approach, the user should put the range maps in place one by one, manually specifying the alignment arcs between any possible pair of overlapping range maps. A different approach, based on a jigsaw puzzle metaphor can greatly reduce the processing time. The idea is to work in a hierarchical way, constructing small groups of well aligned range maps and using them as a single piece to build larger groups. Working with this approach the user has just to place any single range map (or any group of already processed range maps) in the correct position with respect to the others, without worrying about directly specify all the alignment arcs between the various range map. Once we placed this new element, MeshAlign v.2 is able to detect the adjacencies between the various range maps in a completely automatic manner, setting up the data structures needed for the alignment automatically.

MeshAlign supports the two alternative approaches for the initial manual placement: aligning
via interactive manipulation (top) or by the selection of 3 corresponding point pairs (bottom).

Therefore, to give an example, if we have a small group of 5 range maps already aligned and we want to align them with a group of 30 already processed, the only action demanded to the user is to ``align" these two groups considering them as a simple pair of elements (this action requires a few seconds). Once the two groups are placed in an approximate initial alignment, the system iterates on the single range maps which compose the groups; then, in a completely unattended manner, creates and initialize all needed arcs connecting pairs of overlapping range maps. A keen data organization and a spatial index are needed to implement the approach described above, making possible to detect automatically the range map overlaps once known an approximate alignment between two separate groups. Taking into account that the set of range maps that we have to manage can be really large, we implemented those structures in a most scalable way (in terms of both space and time efficiency).

Range maps are complex piece of geometry (up to 1000*1000 samples). To maintain interactive response of all the mesh manipulation and rendering actions, a multiresolution engine has been provided in  MeshAlign v.2. This engine automatically simplifies the range maps (simplification is run the first time a range map is included in a project, is run in background and the results are encoded in a multiresolution structure). The user is free to select the proper level of detail (LOD) at any time, in a very simple manner (with a simple slider). Choosing the right tradeoff between precision and user interaction speed is therefore very simple. Using a low-resolution model (obtained with an accurate simplifier) improves also the convergence of the first iterations of the ICP alignment; obviously, MeshAlign switches automatically to the high resolution data representation in order to get the maximum precision.

MeshAlign provides the standard rendering modes (wire frame, wire frame, flat and smooth shaded). The system assigns colors to the different rage maps, to make them more clearly distinguishable in rendering.

The user interface allows also managing the hierarchical project organization in a visual way. The sub-window in the bottom-left (with a layout similar to a hierarchical file-browser) displays: the groups defined by the user during the alignment (first level
items); for each group, all the range maps assigned (second level items); for each range map we have some info on the range map (size, bounding box) and the list of alignment arcs created by the system; and finally, numeric data are visualized for each arc, e.g. reporting the residual error associated to this arc after the alignment (a valuable information to feedback to the user to steer and improve the alignment).

[Pul99] K. Pulli, Multiview registration for large datasets, Proc 2nd Int.l Conf. on 3D Digital Imaging and Modeling, IEEE, 1999, 160-168.
[BesMcK92] P. J. Besl and N. D. McKay, A Method for Registration of 3-{D} Shapes, IEEE Transactions on Pattern Analysis and machine Intelligence, 239-258, 14(2), 1992.
[ChenMed92] Y. Chen and G. Medioni, Object Modelling by Registration of Multiple Range Images, International Journal of Image and Vision Computing, 10 (3), 145-155, 1992.