Parallel Algorithms for Near-Realtime Visualization
Detailed panoramic views are essential in the operation of a mars rover for several tasks:
- Determination of exact location
- Science target identification
Mars rover cameras gather many individual images with a resolution of 480x640 that are stitched together in a larger mosaic. Before the images can be stitched together they may have to be warped into the reference frame of the final mosaic, since the the orientation and the individual images change from one to the next and since the final mosaic might be assembled in different views. The algorithm is such that for every pixel in the desired final mosaic a good corresponding point must be found in one or more of the original small images. This process depends strongly on a good camera model and a good correlation of the individual pixels with respect to their position in three dimensions (x,y,z).
The original algorithm takes about 90 minutes to complete a whole mosaic on a 450MHz Pentium III PC running Linux. It was desired to reduce this processing time down by at least an order of magnitude. We performed some algorithmic changes to the original software and we parallelized the existing mosaicing software on a Pentium III based beowulf cluster using MPI. A processing time from down to 1.5--6 from about 90 minutes was achieved (depending on the image and the processor speed). The images shown above were taken in a mars exploration rover (MER) test in the beginning of May 2001. The mosaic generation of this particular image (note that only about 1/4 of it is shown) took 3.3 minutes on 16 CPUs of a 450MHz Pentium III cluster.
The parallel algorithm divides the targeted mosaic into N slices, where N is the number of CPUs, as indicated by the blue lines in the above image. Once the each CPU has completed its tasks it reports the image to the manager CPU, which patches the slices together into one image and saves it to disk. The numerical scaling data can be found on another page.
Other algorithm changes:
The original mosaic algorithm was written for machines that have a limited amount of RAM available. That restriction limited the number of individual images that can be kept in memory during the mosaicing process. With about 256 MB on a CPU once can safely read in all of the about 130 images and keep a copy of the final mosaic in RAM. The algorithm was changed to enable this with the aid of some dynamic memory allocation.
This work was sponsored by the TMOD technology program under the Beowulf Application and Networking Environment (BANE) task.The original VICAR based software is maintained in the Multi-mission Image Processing Laboratory (MIPL). The work was performed in a collaboration between Gerhard Klimeck, Myche McAuley, Tom Cwik, Bob Deen, and Eric DeJong