ADAPTIVE MULTIRESOLUTION STRUCTURES FOR IMAGE-PROCESSING ON PARALLEL COMPUTERS

This paper presents a solution to the problem of creating region adjac ency graph (RAG) pyramids on parallel computers comprising the hypercu be topology. RAG pyramids represent hierarchies of irregular tesselati ons, with each tesselation generated in parallel by independent stocha stic processes, and can be used for multiresolution image analysis. Th e outcome of the stochastic processes depends on the input data allowi ng the adaptation of RAG pyramids to the image content. For the extrac tion of connected components from labeled images, different connected components are reduced to different roots which are interconnected in a final region adjacency graph. An algorithm for implementing RAG pyra mids on hypercube computers is discussed in detail and timing results are presented for the Connection Machine CM-2 supercomputer. The time complexity of the algorithm is found for the hypercube and the CRCW PR AM. The results show that the iterative process that creates a new lev el of the hierarchy from its preceding one does not heavily depend on the size of the graph, as its expected time is O(log N) for a random g raph, where N is the total number of vertices in the input graph. The total number of levels is O(log(image_size)), as for the regular pyram id. (C) 1994 Academic Press, Inc.