Keywords: parallelization, multiprocessing, cluster, image registration, matching.

Free-form curve matching has been recently used to geometrically match heterogeneous geoscientific and remote sensing data, such as images, maps and vector data. The matching of the curves is done by an in-house developed algorithm which is based on the iterative closest point algorithm (ICP) and the least squares method (LSM). In order to achieve generality and robustness, the algorithm splits the curves into a large number of consecutive interpolated points and seeks closest point pairs between the curves. The algorithm is thus very processor intensive.

Parallel computing is a form of computation in which many computations are carried out simultaneously operating on the principle that large problems can be divided into smaller ones, which are then solved concurrently using special hardware (multicore computing, symmetric multiprocessing, distributed computing).

In this paper it is shown that the matching algorithm can benefit from parallelization. Since each iteration of ICP depends directly on the outcome of the previous iteration, only the computations within each iteration are investigated for parallelization. It is shown that the computations can be split into hundreds of almost independent groups, and each group can be evaluated using a different processor.

The volume, in bytes, of the outcome of each group of computations is very small, so that it can be sent through the network with negligible overhead (delay). Thus, the algorithm does not need special hardware and it can be executed equally well by an ordinary, off-the-shelf, symmetric multiprocessor computer, as well as by a typical computer cluster of comparatively low bandwidth (100MBits/sec).

The algorithm was designed so that it can be implemented using coarrays as described in the upcoming Fortran 2008 standard. The biggest advantage of Fortran 2008 is that remote memory is referred to directly, like an array with the instance identity as index, instead of having to call a subroutine for loading and storing data. A small but sufficient set of easily learned commands and constructs are defined, which make the program much clearer. A program that runs over several processors is inherently more complicated than a single-threaded program so that clear and well understood commands are extremely important.

The algorithm was implemented in Fortran 2008 and it was compiled using the G95 compiler. The Fortran 2008 code will be platform independent when the standard finalizes and more compilers implement it. For efficiency, convenience and user-friendliness, the algorithm was integrated within an open source CAD system.

The algorithm was tested with the registration of two heterogeneous topographic maps through free-form curve matching. A computer cluster in a local area network was used for the execution with promising results.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £72 +P&P)