Parallel computation of the Hausdorff distance between images (Q1315933)

The article presents a fast algorithm to calculate the Hausdorff distance between images, suitable for execution on a general-purpose MIMD parallel computer. The Hausdorff distance between sets is used in the construction of fractals for computer graphics and image compression. It is the measure of goodness of fit of a particular fractal representation of an image to the image itself (an iterated function system). The parallel algorithm is presented in details. The authors make some remarks about the serial optimal algorithm (closely related to the Delaunay triangulation and the growth algorithm described in the context of Voronoi polygons). The data decomposition, load balance, memory requirements are special issues in the construction of the new fast algorithm. Distributing the grid onto the processor network with some boundary overlap was found to be effective. The classical difficulties introduced by the communication overhead are largely obviate by keeping the problem size per processor constant, i.e. scaling the problem size with the computer size. The tests are suggesting that architecture specialised for data parallelism may be well suited to the proposed method.